## Invited Session Thu.1.MA 042

#### Thursday, 10:30 - 12:00 h, Room: MA 042

**Cluster 14: Mixed-integer nonlinear programming** [...]

### MINLP theory and algorithms

**Chair: Giacomo Nannicini**

**Thursday, 10:30 - 10:55 h, Room: MA 042, Talk 1**

**Emiliano Traversi**

Separable underestimators for quadratic combinatorial optimization

**Coauthor: Christoph Buchheim**

**Abstract:**

We propose a method to obtain separable underestimators for quadratic

combinatorial optimization problems. By exploiting separability we can

provide lower bounds by solving an integer linear problem and use them

in a branch and bound scheme. This is useful in practice when the

underlying linear counterpart is easy to solve.

We investigate the tightness of the bounds and their effect on the

running time of the algorithm.

Computational results are provided concerning the quadratic binary

unconstrained problem and the quadratic spanning tree problem.

**Thursday, 11:00 - 11:25 h, Room: MA 042, Talk 2**

**Stefano Coniglio**

Spatial branch-and-bound for nonconvex Euclidean norm constrained mathematical programs

**Coauthor: Francois Margot**

**Abstract:**

We are interested in mathematical programs involving Euclidean point-to-hyperplane distances. In particular, we focus on the Euclidean Linear Classification problem (ELC) of finding a hyperplane which best separates two sets of points by minimizing the sum of its Euclidean distance to the points on the wrong side. Given a point *a ∈ R*^{n} and hyperplane with parameters *(w, γ ) ∈ R*^{n+1}, their distance is *|a*^{T} w - γ | subject to *w*^{T} w ≥ 1, whose feasible region is the nonconvex complement of the unit ball.

First, we observe that standard spatial branch-and-bound (sBB) methods employ not tight relaxations which yield nontrivial bounds only after many iterations. Then, we propose a novel sBB method where the complement of the unit ball is approximated with the complement *P*^{c} of polyhedron *P*. We represent *P*^{c} as a disjunction with a subproblem for each facet of *P* and, at each sBB iteration, we refine it by adding a new vertex to *P* which corresponds to the new infeasible solution. Compared to a standard sBB on random ELC instances, our method reduces, on average, the computing time by 36%, the number of tree nodes by 63%, and the tree depth by 55%.