列生成

列生成（column generation）用于变量数量极多的优化模型：先只保留一小部分变量解限制主问题，再利用对偶价格求解定价子问题，寻找值得加入的新变量。变量对应矩阵的列，因此称“生成列”。它最常用于线性松弛；得到完整线性规划的最优值，不等于已经解决整数要求。

取一个很小的下料问题：母材长度十，成品规格六与四，各需一根。每种切割模式为一列。初始只放入“切一根六”的模式 $a^1=(1,0)$ 与“切两根四”的模式 $a^2=(0,2)$，暂把模式次数放宽为连续数。

限制主问题与对偶价格

初始主问题为 $$\begin{array}{cc}min& x_1+x_2,\\ x_1& \ge 1,2x_2\ge 1,x_1,x_2\ge 0.\end{array}$$ 最优取 $x_1=1,x_2=1/2$，值为 $3/2$ 根。这里二分之一根母材只是线性松弛，尚不是可执行切割方案。

给两项需求定非负价格 ${\pi }_1,{\pi }_2$，每个已知模式产出的价格总和不得超过一根母材的成本一，故对偶为 $$\begin{array}{cc}max& {\pi }_1+{\pi }_2,\\ {\pi }_1& \le 1,2{\pi }_2\le 1,{\pi }_i\ge 0.\end{array}$$ 最优价格为 $(1,1/2)$，与主问题同为 $3/2$。这些价格只受已生成列约束，还未必对所有合法模式可行。

定价子问题与约化成本

对一个合法模式 $a$，一根母材产出 ${\pi }^{𝖳}a$ 的需求价格，总成本为一，其约化成本是 $${\bar{c}}_a=1-{\pi }^{𝖳}a.$$ 因此应找价格总和最大的可行模式： $$\begin{array}{cc}max& {\pi }_1{a}_1+{\pi }_2{a}_2,\\ 6a_1+4a_2& \le 10,\\ a_i& \in {\mathbb{Z}}_{\ge 0}(i=1,2).\end{array}$$ 主例 $(1,1)$ 的价格为一点五，约化成本为负二分之一，说明旧价格违反该列对应的完整对偶约束。把这列加入，再优化主问题。

定价寻找的不是最长余料，而是当前对偶价格下最有价值的合法模式。新增列后必须重新解主问题，不能一直沿用旧价格。

新主问题允许 $x_3=1$、其他为零，恰好满足两项订单，成本一。完整模式还包括 $(0,1)$；取新对偶价格 $(1/2,1/2)$，对全部非空模式 $(1,0),(1,1),(0,1),(0,2)$ 的价格均不超过一，需求价格合计一。因此这一根母材方案与完整对偶下界相等，证明新主问题和完整LP都最优。此例还碰巧是整数方案，故整数原问题也最优。

停止证书与整数边界

一般最小化主问题 $min\{c^{𝖳}x:Ax\ge b,x\ge 0\}$ 的对偶约束为 $A^{𝖳}\pi \le c,\pi \ge 0$。若当前最优对偶价格经定价检查，对全部未生成列都没有负约化成本，它就对完整对偶可行；当前主问题方案扩充零变量后又对完整原问题可行，且二者目标相等，弱对偶立即证明完整LP最优。

定价只找到一列“似乎不改善”，不能证明全部列都不改善；需要定价子问题的全局最优值或可靠界。数值求解还须区分负值容差与真正的负约化成本。列生成停止后只把现有列改回整数，并不保证整数全局最优，因为某些整数有用列在LP最优解中并不需要；完整整数求解通常还要结合分支定价等框架。

整数长度定价的动态规划

下例独立实现可重复切同一规格的定价背包，返回最优模式、总价格及约化成本。价格用有理数，避免把本例负二分之一仅作为浮点近似判断。

Python 3

from fractions import Fraction

def price_pattern(lengths, prices, stock):
    lengths, prices = tuple(lengths), tuple(map(Fraction,prices))
    if type(stock) is not int or stock < 0 or len(lengths) != len(prices):
        raise ValueError("integer stock and matching prices required")
    if any(type(x) is not int or x <= 0 for x in lengths):
        raise ValueError("positive integer lengths required")
    if any(x < 0 for x in prices):
        raise ValueError("nonnegative prices required")
    best, choice = [Fraction(0)]*(stock+1), [-1]*(stock+1)
    for cap in range(1,stock+1):
        best[cap] = best[cap-1]
        for i, length in enumerate(lengths):
            if length <= cap and best[cap-length]+prices[i] > best[cap]:
                best[cap], choice[cap] = best[cap-length]+prices[i], i
    count, cap = [0]*len(lengths), stock
    while cap:
        i = choice[cap]
        if i == -1:
            cap -= 1
        else:
            count[i] += 1; cap -= lengths[i]
    return tuple(count), best[stock], 1-best[stock]

print(price_pattern([6,4],[Fraction(1),Fraction(1,2)],10))
# ((1, 1), Fraction(3, 2), Fraction(-1, 2))

容量状态记录不超过该长度的最大价格。最优模式若不占最后一个长度单位可继承上一格；否则删去其中一件后仍是较小容量问题，逐格归纳证明转移。回溯时容量严格减小，所以停止；$m$ 种规格、母材整数长 $L$ 时，算术操作数为 $O(mL)$、空间为 $O(L+m)$，有理数位复杂度另计。

变式。 初始两项订单都改为两根，初始连续成本为三；新混合列用两次成本二。对偶价格仍可取二分之一、二分之一，完整下界为二，证书同样成立。新列的出现改变的是可选切法，不是凭空把原订单或母材长度改小。