Invited Session Fri.2.H 3005

Friday, 13:15 - 14:45 h, Room: H 3005

Cluster 2: Combinatorial optimization [...]

Nonlinear combinatorial optimisation problems I


Chair: Adam Nicholas Letchford



Friday, 13:15 - 13:40 h, Room: H 3005, Talk 1

Frank Baumann
Exact algorithms for combinatorial optimization problems with submodular objective functions

Coauthors: Sebastian Berckey, Christoph Buchheim


Many combinatorial optimization problems have natural formulations as submodular minimization problems over well-studied combinatorial structures. A standard approach to these problems is to linearize the objective function by introducing new variables and constraints, yielding an extended formulation. We propose two new approaches for constrained submodular minimization problems. The first is a linearization approach that requires only a small number of additional variables. We exploit a tight polyhedral description of this new model and an efficient separation algorithm. The second approach uses Lagrangean decomposition to create two subproblems which are solved with polynomial combinatorial algorithms; the first subproblem corresponds to the objective function while the second consists of the constraints. The bounds obtained from both approaches are then used in a branch and bound-algorithm. We apply our general results to problems from wireless network design and mean-risk optimization. Our experimental results show that both approaches compare favorably to the standard techniques.



Friday, 13:45 - 14:10 h, Room: H 3005, Talk 2

Frauke Liers
A polyhedral approach to the quadratic matching problem

Coauthor: Bernhard Stöcker


In the quadratic matching (QM) problem, we are given a real cost for
each edge in a graph. Furthermore, for each pair of edges
a real cost is specified as well. The task is to determine a (not
necessarily perfect) matching that minimizes its associated cost,
i.e., the sum of the costs of the matched edges plus the sum of the
product costs for any pair of matched edges. The QM problem is closely
related to classical combinatorial optimization tasks such as the
quadratic assignment problem. Applications of QM exist in computer
vision and, more generally, when `highly similar' subgraphs of two
graphs shall be determined. In this work, we study the polyhedral
structure of the corresponding QM polytope. Based on these results, we
design and implement an exact branch-and-cut approach and report
computational results.



Friday, 14:15 - 14:40 h, Room: H 3005, Talk 3

Vishnu Narayanan
Some properties of integer hulls of convex sets


We study properties of integer hulls of (unbounded) closed convex sets. We examine existence of facets, dimensions of faces and their properties, and derive results on representation of integer hulls using well studied sets. We derive necessary and sufficient conditions for semidefinite representation of these integer hulls.


  Getting California Loans Online should be thought of many times. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Cialis is the one that definitely differs from all other products.