Optimization Online


A Probing Algorithm for MINLP with Failure Prediction by SVM

Giacomo Nannicini(nannicin***at***andrew.cmu.edu)
Pietro Belotti(pbelott***at***clemson.edu)
Jon Lee(jonlee***at***us.ibm.com)
Jeff Linderoth(linderoth***at***wisc.edu)
Francois Margot(fmargot***at***andrew.cmu.edu)
Andreas Waechter(andreasw***at***us.ibm.com)

Abstract: Bound tightening is an important component of algorithms for solving nonconvex Mixed Integer Nonlinear Programs. A {\em probing} algorithm is a bound-tightening procedure that explores the consequences of restricting a variable to a subinterval with the goal of tightening its bounds. We propose a variant of probing where exploration is based on iteratively applying a truncated Branch-and-Bound algorithm. As this approach is computationally expensive, we use a Support-Vector-Machine classifier to infer whether or not the probing algorithm should be used. Computational experiments demonstrate that the use of this classifier saves a substantial amount of CPU time at the cost of a marginally weaker bound tightening.

Keywords: jonlee@us.ibm.com

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

Category 2: Global Optimization

Citation: IBM Research Report RC25103 (01/28/2011)

Download: [PDF]

Entry Submitted: 01/28/2011
Entry Accepted: 01/28/2011
Entry Last Modified: 01/28/2011

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 Programming Society