**Friday, 15:45 - 16:10 h, Room: MA 041**

**Leo Liberti**

On feasibility-based bounds tightening

**Coauthors: Pietro Belotti, Sonia Cafieri, Jon Lee**

**Abstract:**

Mathematical programming problems involving nonconvexities are usually solved to optimality using a spatial branch-and-bound (sBB) algorithm. Algorithmic efficiency depends on many factors, among which the widths of the bounding box for the problem variables at each branch-and-bound node naturally plays a critical role. The practically fastest box-tightening algorithm is known as FBBT (feasibility-based bounds tightening): an iterative procedure to tighten the variable ranges. Depending on the instance, FBBT may not converge finitely to its limit ranges, even in the case of linear constraints. Tolerance-based termination criteria yield finite termination, but not in worst-case polynomial time. We model FBBT by using fixed-point equations in terms of the variable bounding box, and we treat these equations as constraints of an auxiliary mathematical program. We demonstrate that the auxiliary mathematical problem is a linear program, which can of course be solved in polynomial time. We demonstrate the usefulness of our approach by improving the open-source sBB solver Couenne.

Talk 2 of the invited session Fri.3.MA 041

**"Modelling, reformulation and solution of MINLPs"** [...]

Cluster 14

**"Mixed-integer nonlinear programming"** [...]