## Contributed Session Thu.2.H 3012

#### Thursday, 13:15 - 14:45 h, Room: H 3012

**Cluster 2: Combinatorial optimization** [...]

### Nonlinear combinatorial optimization

**Chair: Laura Klein**

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

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

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

**Agnès Gorge**

Quadratic cuts for semidefinite relaxation of combinatorial problems

**Coauthors: Abdel Lisser, Riadh Zorgati**

**Abstract:**

Semidefinite Programming is well-known for providing tight relaxations of combinatorial problems. In practice, only few real-world applications of this approach have been reported, especially on 0/1 Linear Programming, which is yet a large part of practical combinatorial problems. The reasons for this are twofold. First, some powerful MILP software are already available. Furthermore, for such problems, it is necessary to tighten the basic semidefinite relaxation with cuts, since as it is, it is equivalent to the linear relaxation. Then, we face the difficulty of picking the right cuts to tighten the relaxation in the most relevant fashion. These cuts might be quadratic, in order to outperform the linear relaxation.

We present here a systematic approach to compute such cuts. This method extends naturally to binary programs with non convex quadratic constraints, for which no dedicated software are currently available.

Finally, we apply this technique to a well-known problem of energy management i.e., the scheduling of the nuclear outages, a combinatorial problem with quadratic objective and non-convex quadratic constraints. Numerical results on real life instances are given.

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

**Marta Cecilia Vidal**

A new proposal for a lower bound in a generalized quadratic assignment problem applied to the zoning problem

**Coauthor: María Cristina Maciel**

**Abstract:**

Zoning is a key prescriptive tool for administration and management of protected areas. However, the lack of zoning is common for most protected areas in developing countries and, as a consequence, many protected areas are not effective in achieving the goals for which they were created. In this work we introduce a quantitative method to expeditiously zone protected areas.

Zoning problem was mathematically modeled as a generalized quadratic assignment problem (GQAP), this problem generalizes the well known quadratic assignment problem, one of the most difficult problems in the combinatorial optimization field, it belongs to the NP- hard class. To solve it we applied a simulated annealing heuristic, obtaining satisfactory results in both academic problems of different dimensions as a real large scale problem.

In this work we propose a lower bound for the GQAP based on a new Lagrangean relaxation, which will be applied to the simulated annealing algorithm.