A probing algorithm for MINLP with failure prediction by SVM

Giacomo Nannicini*, Pietro Belotti, Jon Lee, Jeff Linderoth, François Margot, Andreas Wächter

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

Bound tightening is an important component of algorithms for solving nonconvex Mixed Integer Nonlinear Programs. A 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.

Original languageEnglish (US)
Title of host publicationIntegration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems - 8th International Conference, CPAIOR 2011, Proceedings
Pages154-169
Number of pages16
DOIs
StatePublished - 2011
Event8th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, CPAIOR 2011 - Berlin, Germany
Duration: May 23 2011May 27 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6697 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other8th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, CPAIOR 2011
CountryGermany
CityBerlin
Period5/23/115/27/11

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'A probing algorithm for MINLP with failure prediction by SVM'. Together they form a unique fingerprint.

Cite this