Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
I am attempting to solve a linear program via Dantzig-Wolfe decomposition.
It is the first time I implement this method. Before the pricing iterations start, I need to provide an initial set of columns to the Restricted Master Problem. I know I can probably just feed a number of random columns initially. However, is there a smarter way of doing it?
As Rob said, one option is to initialize your CG with a set of columns coming from a feasible solution. The rationale behind is to start from a set of near-optimal (from a MP perspective!) columns. Assuming the dual bound you get from your CG is sufficiently tight, a set of columns coming from a near-optimal feasible solution to your problem should be sufficiently good for the MP.
Another possibility is to add slack variables to all of your constraints, with very high cost coefficients, so your RMP is always feasible. Actually, adding such slack variables is even NECESSARY if you embed your CG within branch-and-price later on.
There is much more than just this (stabilization, cutting planes, DOIs, etc), but for a beginner these two observations should suffice to have a first implementation of CG.
As for tutorials, you may first go and read "A primer on column generation" by J Desrosiers and M Lubbecke. The book containing it (Column generation, G Desaulniers, J Desrosiers and MM Solomon, Eds.) is a great source for beginners. If you are into CG for vehicle routing, there is a recent survey that we (L Costa, C Contardo and G Desaulniers) wrote in the spirit of make the life of students giving their first steps in CG for VRP less painful.
Best regards
Besides the options mentioned by Rob and Claudio, a third one is to use Farkas Pricing. In this approach, which is based on Farkas' Lemma, we do not include any initial columns or slack variables, but instead solve a sub-problem similar to the typical pricing problem. First, we retrieve Farkas duals from the master problem, which represent a proof of infeasibility (I believe most solvers have such a functionality). Then, we search for a column in the sub-problem that "corrupts" this proof of infeasibility. The sub-problem is the same as the regular pricing problem, except for a change in the objective. We add the column to the master and iterate.
The advantage of Farkas Pricing is that you do not need to worry about guaranteeing that your master problem will always be feasible using slack variables or initial columns. Especially if you apply branch-and-price, this can be cumbersome. For some more details, I refer to this thesis about the GCG solver.
One natural approach to generate initial columns is to solve each subproblem using the original cost (instead of reduced cost) as the objective. This is equivalent to taking all master dual variables equal to 0.
