Assume one have an integer problem.

Is the master problem in the column generation algorithm the original integer problem, or its linear relaxation?

Thank you in advance.


1 Answer 1


As suggested by @LarrySnyder610, I am pasting my comment as an answer :

Neither one !

It is the linear relaxation of the original integer problem, after applying a Dantzig-Wolfe decomposition, which in essence, consists in reformulating variables as a convex combination of the extreme points of the polytope defined by the constraints of the original problem.

You can check this, and the references mentioned there. It shows you an example of the original formulation, the master problem and the subproblem for the well known cutting stock problem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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