# 當目標函數中出現棘手的變量時生成列

\開始{align}z = \ min＆\ quad \ sum_ {ij} c_ {ij} x_ {ij} + \ sum_i w_i \\\ text {s.t。}＆\ quad A（x）\ leq a，\ tag1 \\＆\ quad w_i \ geq c_ {ij} x_ {ij}，\ quad \ forall i，j \ tag2 \\＆\ quad x_ {ij} \ in \ {0,1 \}，\\＆\ quad w_ {i} \ geq 0。\ end {align}

P.S。我沒有實現列生成的經驗。

Suppose $$K$$ is the set of columns, where the $$k$$th column $$x^k \in \{0,1\}^n$$ satisfies $$A(x^k) \le a$$. Now express $$x$$ as a convex combination of the columns $$x^k$$. Explicitly, substitute $$x_{i,j} = \sum_{k\in K} \lambda_k x_{i,j}^k$$, where $$\sum_{k\in K} \lambda_k = 1$$ and $$\lambda_k \ge 0$$ for all $$k\in K$$. You then obtain the following master problem over $$\lambda$$ and $$w$$, with dual variables in parentheses: \begin{align} &\text{minimize} &\sum_{k\in K} \left(\sum_{i,j} c_{i,j} x_{i,j}^k\right) \lambda_k + \sum_i w_i \\ &\text{subject to} &w_i - c_{i,j} \sum_{k\in K} x_{i,j}^k \lambda_k &\ge 0 &&\text{for all i,j} &&(\pi_{i,j} \ge 0)\\ &&\sum_{k\in K} \lambda_k &= 1 &&&&(\text{\alpha free})\\ &&\lambda_k &\ge 0 &&\text{for all k} \\ &&w_i &\ge 0 &&\text{for all i} \end{align}

The column generation subproblem over $$x$$ is then to minimize the reduced cost of $$\lambda_k$$. That is, minimize $$\sum_{i,j} c_{i,j} (1+\pi_{i,j}) x_{i,j} - \alpha$$ subject to $$A(x) \le a$$ and $$x \in\{0,1\}^n$$.