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


Leo Liberti
On feasibility-based bounds tightening

Coauthors: Pietro Belotti, Sonia Cafieri, Jon Lee


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" [...]


  The best way to go for you to know the credible Michigan Loans Online providers. You can buy Levitra Super Force profitably on our web-site; we offer the medications only of the highest quality and at reasonable prices.