Invited Session Wed.3.H 2032

Wednesday, 15:15 - 16:45 h, Room: H 2032

Cluster 11: Integer & mixed-integer programming [...]

Branch-and-price I: Generic solvers


Chair: Marco Lübbecke



Wednesday, 15:15 - 15:40 h, Room: H 2032, Talk 1

Marco Lübbecke
A generic branch-price-and-cut solver

Coauthors: Martin Bergner, Gerald Gamrath, Christian Puchert


We implemented GCG, a branch-price-and-cut solver based on the
branch-price-and-cut framework SCIP. Given a MIP, the solver performs
a Dantzig-Wolfe reformulation (based on user input, or in some cases
the solver suggests a reformulation), does column generation and full
branch-price-and-cut. GCG inherits advanced MIP solving features from
SCIP, like presolving, propagation, (combinatorial) cutting planes,
pseudo-costs etc. A number of additional plugins are implemented
which are specific to exploiting the availability of having an
original compact and an extended column generation formulation, like
primal heuristics or branching rules. We report on computational
experiments on a number of applications and discuss what can be
learned from a generic solver.



Wednesday, 15:45 - 16:10 h, Room: H 2032, Talk 2

Theodore Ralphs
Dip and DipPy: Towards a generic decomposition-based MIP solver

Coauthors: Matthew Galati, Michael O'Sullivan, Jiadong Wang


DIP is a software framework for simplifying the implementation of a range of decomposition-based algorithms for solving mixed integer linear optimization problems. It is based on an underlying theoretical framework that unifies a number of decomposition methods, such as Dantzig-Wolfe decomposition, Lagrangian elaxation, and cutting plane methods. Recent efforts have focused on the development of a generic decomposition-based solver, capable of automatically detecting block structure and utilizing an appropriate decomposition method to solve the problem. DipPy is a modeling language front end to DIP, which allows block structure to be explicitly identified in cases where such block structure is known to the modeler. This is done in a very natural way, making it easy for unsophisticated users to experiment with powerful methods such as column generation. In this talk, we discuss the latest developments and present computational results.



Wednesday, 16:15 - 16:40 h, Room: H 2032, Talk 3

Matthew Galati
The new decomposition solver in SAS/OR


This talk demonstrates the new DECOMP feature in the SAS/OR suite of optimization solvers for using decomposition-based techniques for solving linear and mixed-integer linear programs. Using the modeling language provided by the OPTMODEL procedure in SAS/OR software, a user can easily experiment with different decompositions simply by defining the partition of constraints in the original compact space. All algorithmic details in the reformulated (Dantzig-Wolfe) space are automatically managed by DECOMP. We will discuss the overall software design motivated by the goal to minimize user burden and reduce the need for algorithmic expertise. We will then present results from several client applications where DECOMP was successfully used, including results in both shared and distributed memory parallel environments.


  There are three major facts that should be watched out for in all payday loans in the United States. If you have already decided to take Generic Levitra, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.