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


  There are three major facts that should be watched out for in all payday loans in the United States. Since its introduction in the market buying Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.