Generic Decomposition Algorithms for Integer Programs

DFG Priority Program 1307 Algorithm Engineering, 01/2010-12/2011


Head: undefinedMarco Lübbecke
Researcher: undefinedMartin Bergner



There is no alternative to integer programming when it comes to computing proven quality or even optimal solutions to large-scale hard combinatorial optimization problems. In practical applications, matrices often have special structures exploitable in decomposition algorithms, in particular in brance-and-price. This opened the way to the solution of mixed integer programs (MIPs) of enormous size and complexity, both from industry and within mathematics, computer science, and operations research.

Yet, as the state-of-the-art, branch-and-price is implemented ad hoc for every new problem. Various frameworks are very helpful in this respect, still, this requires a solid expert knowledge. This project aims at making a significant contribution towards a generic implementation of decomposition algorithms. As a longterm vision, a MIP solver should be able to apply a decomposition algorithm without any user interaction. A precondition for such an automation is the answer to important algorithmic and theoretical questions, among them:

  • recognition of decomposable structures in matrices and/or MIPs
  • development of a theory (and appropriate algorithms) for evaluating the quality of a decomposition

In this project we address these questions. From a mathematical point of view, there are interesting relations to polyhedral combinatorics, graph theory, and linear algebra. A generic implementation of our findings is planned to be provided to the research community. To this end we closely cooperate with developers of MIP solvers (such as SCIP) and modeling languages (such as GAMS).






« September 2018 »
Mo Tu We Th Fr Sa Su
35 1 2
36 3 4 5 6 7 8 9
37 10 11 12 13 14 15 16
38 17 18 19 20 21 22 23
39 24 25 26 27 28 29 30


Research Group Optimization 

Constanze Drechsel
Office: S4|10 138
Phone: +49 (0)6151 16-23444
Fax: +49 (0)6151 16-23445
drechsel (at)


Monika Kammer
Office: S4|10 136
Phone: +49 (0) 6151 16-23448
Fax: +49 (0) 6151 16-23445
kammer (at)


Dolivostraße 15
64293 Darmstadt

A A A | Print Drucken | Impressum Impressum | Contact Kontakt
    zum Seitenanfangzum Seitenanfang