A Branch-and-Bound Method for Box Constrained Integer Polynomial Optimization

Invited abstract in session TE-11: Advances in Combinatorial Optimization, stream Combinatorial Optimization.

Area: 06. Discrete Optimization, Geometry & Graphs

Tuesday, 16:00-17:30
Room: Room 113

Authors (first author is the speaker)

1. Claudia D'Ambrosio
LIX, CNRS - Ecole Polytechnique
2. Christoph Buchheim
Fakultät für Mathematik, Technische Universität Dortmund


We consider the problem of minimizing an arbitrary polynomial subject to box and integrality constraints. We propose a new class of under-estimators composed of separable functions of the original variables and use it within branch-and-bound scheme to easily and quickly compute lower bounds. Computational results on randomly generated instances show good performance with respect to the ones of different open-source solvers like Couenne, Gloptipoly, and SCIP.


Status: accepted

Back to the list of papers