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.
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.