Invited Session Thu.2.H 2032

Thursday, 13:15 - 14:45 h, Room: H 2032

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

Branch-and-price III: New techniques


Chair: Marco Lübbecke



Thursday, 13:15 - 13:40 h, Room: H 2032, Talk 1

Martin Bergner
Packing cuts with column generation

Coauthor: Marco Lübbecke


In our talk, we propose an exact algorithm for the cut packing problem in
general graphs via a column generation approach. It is known that packing
cuts in general graphs is NP-hard and cannot be approximated better than
with a factor of O(n/log2 n) in general graphs. Cut packing
has applications in both network design and, via its dual formulation as
a cycle packing problem, in computational biology. For our approach, we
discuss both combinatorial algorithms and a mixed-integer linear
programming (MIP) formulation for solving the pricing problems. In order
to further improve the dual bound, cutting planes from the literature are
separated during the solution process and their integration in the
pricing problems is explained. Furthermore, we highlight a novel
application for detecting structures in constraint matrices of MIPs and
use heuristics tailored to this application for finding solutions during
the branch-and-price algorithm. Finally, we present computational results
both on graphs from the literature as well as from our application and
discuss the peculiarities of these instance.



Thursday, 13:45 - 14:10 h, Room: H 2032, Talk 2

Mette Gamst
An exact approach for aggregated formulations

Coauthor: Simon Spoorendonk


Aggregating formulations is a powerful trick for transforming problems into taking more tractable forms. An example is Dantzig-Wolfe decomposition, which shows superior performance across many applications especially when part of a branch-and-price algorithm. Variable aggregation, however, may lead to mathematical formulations with a different solution space than that for the original formulation, i.e., the aggregated formulation may be a relaxation of the original problem. In a branch-and-bound context, variable aggregation can also lead to a formulation where branching is not trivial, for example when optimality cannot be guaranteed by branching on the aggregated variables.
In this presentation, we propose a general method for solving aggregated formulations, such that the solution is optimal to the original problem. The method is based on applying Benders' decomposition on a combination of the original and aggregated formulations. Put in a branch-and-bound context, branching can be performed on the original variables to ensure optimality.
We show how to apply the method on well-known optimization problems.



Thursday, 14:15 - 14:40 h, Room: H 2032, Talk 3

Jacques Desrosiers
Row-reduced column generation for highly degenerate master problems

Coauthors: Jean Bertrand Gauthier, Marco E. Lübbecke


Column generation alternately solves a master problem and a pricing subproblem to add variables to the master problem as needed. The method is known to suffer from degeneracy, exposing what is known as tailing-off effect. Inspired by recent advances in coping with degeneracy in the primal simplex method, we propose a row-reduced column generation that takes advantage of degenerate solutions. The idea is to reduce the number of constraints to the current number of positive basic variables. The advantage of this row-reduction is a smaller basis, and thus a faster re-optimization of the master problem. This comes at the expense of a more involved pricing subproblem that needs to generate variables compatible with the row-reduction, if possible. Otherwise, incompatible variables may need to be added, and the row-reduction is dynamically updated. We show that, in either case, a strict improvement in the objective function value occurs.


  Getting California Loans Online should be thought of many times. Since its introduction in the market buying Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.