8
$\begingroup$

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?

$\endgroup$
10
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks. As a follow-up question, is there any resource you would suggest as a primer for a beginner, with an implementation perspective? $\endgroup$ – k88074 Apr 7 at 15:23
  • $\begingroup$ actually, you may need both, columns of a feasible solution and artificial variables, for otherwise you cannot form a basis $\endgroup$ – Marco Lübbecke Apr 7 at 15:35
10
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ The following happened to me. Assume all the subproblems are identical as they often are in multicommodity network flows. Then you can easily add duplicate columns to the master problem in the Farkas pricing phase. I mean if you add 1 column per subproblem. Must admit I worked on this 20 years ago so... $\endgroup$ – ErlingMOSEK Apr 8 at 6:00
5
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks. But what if I need to generate more columns. My understanding is that I need at least as many initial columns as there are constraints in RMP in order to give RMP the possibility to find an initial basis. What if I have fewer subproblems that constraints in RMP? Would it be reasonable to use random values for the RMP dual variables? $\endgroup$ – k88074 Apr 7 at 14:18
  • $\begingroup$ You can introduce artificial variables in the master and then use two-phase simplex, where the first phase eliminates the artificial variables to get a feasible solution and the second phase improves the feasible solution to an optimal solution. $\endgroup$ – RobPratt Apr 7 at 14:29
  • $\begingroup$ Just to clarify, although you can initialize with the columns from a feasible solution (which might be difficult to find), my suggestion was a little different. I proposed solving each subproblem independently, without regard to the linking constraints. $\endgroup$ – RobPratt Apr 9 at 12:26

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.