Generic Dantzig-Wolfe Decomposition

Hits: 0
Research Area: Generic Decomposition Algorithms for Integer Programs
Status: In progress  
 
Description:

Many recent successful approaches to solve structured mathematical programs build explicitly or implicitly on Dantzig-Wolfe reformulation (DWR). "Structurued" in this context refers to the property that a complex optimization problem may contain (much) easier to solve (rather local) subproblems which are linked by (rather global) constraints. In order to allow also non-experts to benefit from the advantages of the method, and to give experts a platform for standardized computational experiements, we develop a mixed integer programming solver which is based on DWR and which automatically detects decomposable structures in mixed integer programs.


Our implementation based on the branch-cut-and-price framework SCIP, and in fact turns it into a branch-cut-and-price solver. It detects matrix structures (block-diagonal, bordered block-diagonal, arrowhead) and performs a full DWR without any user interaction. The package inherits the state-of-the-art MIP solving machinery, and complements it by several features particular to column generation and branch-and-price, among them tailored branching rules (eg., Ryan/Foster), branching and cutting on original variables, etc.

 

GCG 1.0.0 has been released on August, 1 and is available for download here.

[ Back ]