Two clicks for more data protection: Only if you click here, the button will be active and you can send your recommendation to Facebook. Yet at activating data is transmitted to third parties.Two clicks for more data protection: Only if you click here, the button will be active and you can send your recommendation to Twitter. Yet at activating data is transmitted to third parties.Two clicks for more data protection: Only if you click here, the button will be active and you can send your recommendation to Google. Yet at activating data is transmitted to third parties.Two clicks for more data protection: Only if you click here, the button will be active and you can send your recommendation to Xing. Yet at activating data is transmitted to third parties.

Generic decomposition algorithms for integer programs


Project Image
Abstract: 

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).