11
$\begingroup$

I know that the Column Generation algorithm delivers an exact solution when you are solving a linear programming optimization problem. I want to know that, does this column generation approach deliver the exact solution when integer variables come into the problem and we have actually MILP? Does Branch and Price algorithm deliver the exact solution? What extra must I do in implementing dual optimization problems (subproblems of the algorithm) when there are integer variables?

I appreciate your help, advice, or any clue to find my answer.

$\endgroup$
12
$\begingroup$

To answer your question, it is good to have in mind the following concepts:

  1. Dantzig-Wolfe decomposition : in essence, this is a change of variables. The initial variables are expressed as a convex combination of the extreme points of the polygon defined by the constraints of the problem.

  2. Column generation : once this change of variables has been done, you are often left with a problem with an exponential number of variables and typically you cannot solve it as is. This is where column generation comes in: variables of this huge problem are dynamically created. Once you have generated all of your "good" columns, you have everything you need to solve your continuous problem. If the problem has integer variables, typically the continuous relaxation of the problem will not yield integer variables.

  3. Branch-and-price : after doing your column generation, you typically have a fractional solution, so you have to embed this procedure in a branch-and-bound tree. Branch-and-price refers to this branching tree, where at every node, a column generation algorithm is used to compute the continuous solution.

So to explicitly answer your questions :

does this column generation approach deliver the exact solution when integer variables come into the problem and we have actually MILP?

No : column generation will deliver the exact solution of the continuous relaxation of the MILP. Note however that it can be shown that the integrality gap cannot be larger than the integrality gap obtained without the Dantzig-Wolfe decomposition. Usually this integrality is "quite small" and the solution obtained at the root node is quite good. This however depends on the nature of the problem.

Does Branch and Price algorithm deliver the exact solution?

Yes : since branch-and-bound delivers the exact solution of a MILP, and branch-and-price is a variation of branch-and-bound.

Check out this cool article for more tricks and tips on the subject !

| improve this answer | |
$\endgroup$

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.