  


On feasibility based bounds tightening
Pietro Belotti(pbelottclemson.edu) Abstract: Mathematical programming problems involving nonconvexities are usually solved to optimality using a (spatial) BranchandBound algorithm. Algorithmic efficiency depends on many factors, among which the widths of the bounding box for the problem variables at each BranchandBound node naturally plays a critical role. The practically fastest boxtightening algorithm is known as FBBT (FeasibilityBased 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. Tolerancebased termination criteria yield finite termination, but not in worstcase polynomialtime. We model FBBT by using fixedpoint 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 BranchandBound implementation. Keywords: global optimization, MINLP, spatial BranchandBound, range reduction Category 1: Global Optimization (Theory ) Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming ) Citation: Download: [PDF] Entry Submitted: 01/24/2012 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  