## 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**

**Abstract:**

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**

**Abstract:**

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

**Abstract:**

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.