19
$\begingroup$

When trying a decomposition technique such as column generation, most of the times my approach is to look at the problem and then:

  1. Decide what a column should represent
  2. Write the Master Problem
  3. Write the expression of the reduced cost, the subproblem, and use the duals of the Master Problem to generate a new column of minimum (or maximum) reduced cost to be added in the Master problem.

This process is hard to automate since it involves looking at the specific problem.
Also, for the same problem, decisions about what a column should represent can vary, and this may lead to different master and subproblems and to restart again the process and recode it from scratch.

Is there a generic procedure to automatically build a master and one or many subproblems according to how the 2 sets of constraints of the LP (Master and Subproblem constraints) are assigned?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
21
$\begingroup$

You should take a look at GCG, a plugin for SCIP and part of the SCIP Optimization Suite.

After the standard presolving process of SCIP, GCG performs a Dantzig-Wolfe decomposition of the problem to obtain an extended formulation of the problem. The decomposition is based on a structure either provided by the user or automatically detected by one of the structure detectors included in GCG .

Another software is DIP, formerly known as DECOMP:

Given a compact formulation and a relaxation, the framework takes care of all algorithmic details associated with implementing any of a wide range of decomposition-based algorithms, such as branch and cut, branch and price, branch and cut and price, subgradient-based Lagrangian relaxation, branch and relax and cut, and decompose and cut.

Yet another software is Coluna:

Coluna is a branch-and-price-and-cut framework that decomposes and solves a mixed-integer program (MIP). The user introduces his "original" problem formulation using the JuMP modeling language and our specific extension BlockDecomposition.

With SAS/OR there is also a commercial software with automatic decomposition techniques:

The decomposition algorithm for LPs is based on the original Dantzig-Wolfe method (Dantzig and Wolfe 1960). [...] This method is also commonly referred to as column generation, although the algorithm implemented here is only one specific variant of this wider class of algorithms.

Improve this answer
$\endgroup$
12
$\begingroup$

Or, if you want a commercial implementation - SAS/OR has a Decomposition feature.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ How could I forget about SAS/OR? thanks (and shamelessly adding it to my answer for completeness) $\endgroup$
    – Michael Feldmeier
    Jun 17, 2019 at 18:46

Your Answer

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

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