Optimization Online


On feasibility based bounds tightening

Pietro Belotti(pbelott***at***clemson.edu)
Sonia Cafieri(sonia.cafieri***at***enac.fr)
Jon Lee(jonxlee***at***umich.edu)
Leo Liberti(leoliberti***at***gmail.com)

Abstract: Mathematical programming problems involving nonconvexities are usually solved to optimality using a (spatial) Branch-and-Bound 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 an existing Branch-and-Bound implementation.

Keywords: global optimization, MINLP, spatial Branch-and-Bound, range reduction

Category 1: Global Optimization (Theory )

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )


Download: [PDF]

Entry Submitted: 01/24/2012
Entry Accepted: 01/24/2012
Entry Last Modified: 01/24/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society