Generic Decomposition Algorithms for Integer Programs

Description

Prof. Dr. Marco Lübbecke; RWTH Aachen University

 

Project website

 

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

  
  

Publications

  • M. E. Lübbecke. "Automatic decomposition and branch-and-price: A status report". Experimental Algorithms. R. Klasing ed. 2012. pp. 1-8. [More] 
  • F. Hennig, B. Nygreen and M. E. Lübbecke. "Nested column generation applied to the crude oil tanker routing and scheduling problem with split pickup and split delivery", Naval Research Logistics, Vol. 59. 2012, pp. 298-310. [More] 
  • W. Höhn, F. G. König, M. E. Lübbecke and R. H. Möhring. "Integrated sequencing and scheduling in coil coating", Management Science, Vol. 57. 2011, pp. 647-666. [More] 
  • M. Bastubbe. "Algorithms for Detecting Block Structures in Matrices". Diplomarbeit. Technische Universität Berlin. 2011. [More] 
  • J. Desrosiers and M. E. Lübbecke. "Branch-Price-and-Cut Algorithms". J. J. Cochran ed. Chichester : John Wiley & Sons. 2011. [More] 
  • M. E. Lübbecke. "Column Generation". J. J. Cochran ed. Chichester : John Wiley & Sons. 2011. [More] 
  • C. Puchert. "Primal Heuristics for Branch-and-Price Algorithms". Technische Universität Darmstadt. 2011. [More] 
  • M. Bergner, A. Caprara, F. Furini, M. E. Lübbecke, E. Malaguti and E. Traversi. "Partial convexification of general MIPs by Dantzig-Wolfe reformulation". Integer Programming and Combinatorial Optimization. 2011. pp. 39-51. [More] 
  • E. T. Coughlan, M. E. Lübbecke and J. Schulz. "A Branch-and-Price Algorithm for Multi-Mode Resource Leveling". Proceedings of the 9th International Symposium on Experimental Algorithms (SEA). 2010. pp. 226-238. [More] 
  • G. Gamrath and M. E. Lübbecke. "Experiments with a Generic Dantzig-Wolfe Decomposition for Integer Programs". Proceedings of the 9th International Symposium on Experimental Algorithms (SEA). P. Festa ed. 2010. pp. 239-252. [More] 
View less
  

Projects

[ Back ]