**Thursday, 13:15 - 13:40 h, Room: H 3012**

**Laura Klein**

Separation algorithms for quadratic combinatorial optimization problems

**Coauthor: Christoph Buchheim**

**Abstract:**

Binary quadratic optimization problems (BQP) are known to be NP-hard even in the unconstrained case. The standard linearization, where auxiliary variables replace the quadratic monomials, yields an exact IP-formulation, but the resulting LP-bounds are weak in general.

For BQPs whose underlying linear problem is efficiently solvable, we propose an improved approach. We consider the corresponding problem with only one monomial in the objective function and observe that valid inequalities of the single monomial problem remain valid for the general case. With the aid of an extended formulation, a polynomial time separation algorithm for the single monomial problem is presented, which exploits the simple structure of the linear case and is extendable to BQP with a constant number of monomials.

The idea of separating valid inequalities in the single monomial case is applied to the quadratic minimum spanning tree problem (QMST). We present a new class of facets for QMST with one monomial and, similarly to the linear case, exploit its combinatorial structure for obtaining an efficient separation algorithm.

Computational results show the advantages of the resulting inequalities for QMST.

Talk 1 of the contributed session Thu.2.H 3012

**"Nonlinear combinatorial optimization"** [...]

Cluster 2

**"Combinatorial optimization"** [...]