# Column generation when intractable variables appear in the objective function

Is it possible to implement a column generation for a problem that the variables in the "complicating" constraint appear in the objective function?

Suppose the MIP is:

\begin{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}

Where constraint set (2) are the complicating constraints. If we ignore (2), then what happens to the objective function?

P.S. I don't have the experience in implementing a column generation.

EDIT: I thank Rob for the great answer. For those unfamiliar with column generation, like me, there is additional information in the comments of his post as well.

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$$.
• Oh, my bad Rob. it is indeed $c_{ij}$. Sorry for the mistake. Now corrected in the OP. – Mostafa Jul 17 at 3:03
• In column generation, the complicating constraints appear in the master, and the other constraints appear in the subproblem. The idea is that the subproblem should be relatively easy, and the subproblem objective reflects the complicating constraints via the master dual variables. Each $x^k$ satisfies the easy constraints, so every convex combination of $x^k$ does, too. – RobPratt Jul 17 at 4:25
• Additional easy constraints that involve only $x$ go in the subproblem. Additional complicating constraints go in the master, with any appearance of $x$ replaced with the convex combination in terms of $\lambda$. – RobPratt Jul 17 at 12:37
• $\pi$ and $\alpha$ are master dual variables and are typically available as an output from the LP solver. – RobPratt Jul 17 at 15:21