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


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.


Talk 1 of the invited session Thu.2.H 2032
"Branch-and-price III: New techniques" [...]
Cluster 11
"Integer & mixed-integer programming" [...]


  Online lending company provides a wide range of ways to get money by means of Tennessee Payday Loans. But at the same time, it acts only with sexual arousal. Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.