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


4

是否可以針對"複雜"約束中的變量出現在目標函數中的問題實現列生成?

假設MIP為:

\開始{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}

其中約束集(2)是複雜的約束。如果我們忽略(2),那麼目標函數會發生什麼?

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

編輯:感謝羅伯的出色回答。對於像我這樣不熟悉列生成的人,他的評論中也包含其他信息。

7

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$.