4
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ Oh, my bad Rob. it is indeed $c_{ij}$. Sorry for the mistake. Now corrected in the OP. $\endgroup$ – Mostafa Jul 17 at 3:03
  • $\begingroup$ So based on the answer, does it mean that you ignored Constraints (1) in the master problem? My question is that, Constraints (2) are the source of making the problem intractable. If we ignore Constraints (2), the problem is polynomially solvable. $\endgroup$ – Mostafa Jul 17 at 3:27
  • 2
    $\begingroup$ 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. $\endgroup$ – RobPratt Jul 17 at 4:25
  • 1
    $\begingroup$ 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$. $\endgroup$ – RobPratt Jul 17 at 12:37
  • 1
    $\begingroup$ $\pi$ and $\alpha$ are master dual variables and are typically available as an output from the LP solver. $\endgroup$ – RobPratt Jul 17 at 15:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.