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


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


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 ∈ Rn and hyperplane with parameters (w, γ ) ∈ Rn+1, their distance is |aT w - γ | subject to wT 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 Pc of polyhedron P. We represent Pc 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%.


  payday loan . 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.