On branching rules for convex mixed-integer nonlinear optimization

Pierre Bonami; Jon Lee; Sven Leyffer; Andreas Wachter

doi:10.1145/2532568

On branching rules for convex mixed-integer nonlinear optimization

Pierre Bonami^*, Jon Lee, Sven Leyffer, Andreas Wachter

^*Corresponding author for this work

Industrial Engineering and Management Sciences

Research output: Contribution to journal › Conference article › peer-review

11 Scopus citations

Abstract

Branch-and-Bound (B&B) is perhaps the most fundamental algorithm for the global solution of convex Mixed-Integer Nonlinear Programming (MINLP) problems. It is well-known that carrying out branching in a nonsimplistic manner can greatly enhance the practicality of B&B in the context of Mixed-Integer Linear Programming (MILP). No detailed study of branching has heretofore been carried out for MINLP. In this article, we study and identify useful sophisticated branching methods for MINLP, including novel approaches based on approximations of the nonlinear relaxations by linear and quadratic programs.

Original language	English (US)
Article number	2532568
Journal	ACM Journal of Experimental Algorithmics
Volume	18
DOIs	https://doi.org/10.1145/2532568
State	Published - 2013
Event	9th International Symposium on Experimental Algorithms, SEA 2010 - Naples, Italy Duration: May 20 2010 → May 22 2010

Keywords

Branch-and-bound
Mixed-integer nonlinear programming
Strong-Branching

ASJC Scopus subject areas

Theoretical Computer Science

Access to Document

10.1145/2532568

Cite this

@article{0c21ea0d62cf442a96210dcbbbf294e2,

title = "On branching rules for convex mixed-integer nonlinear optimization",

abstract = "Branch-and-Bound (B&B) is perhaps the most fundamental algorithm for the global solution of convex Mixed-Integer Nonlinear Programming (MINLP) problems. It is well-known that carrying out branching in a nonsimplistic manner can greatly enhance the practicality of B&B in the context of Mixed-Integer Linear Programming (MILP). No detailed study of branching has heretofore been carried out for MINLP. In this article, we study and identify useful sophisticated branching methods for MINLP, including novel approaches based on approximations of the nonlinear relaxations by linear and quadratic programs.",

keywords = "Branch-and-bound, Mixed-integer nonlinear programming, Strong-Branching",

author = "Pierre Bonami and Jon Lee and Sven Leyffer and Andreas Wachter",

note = "Publisher Copyright: {\textcopyright} 2013 ACM.; 9th International Symposium on Experimental Algorithms, SEA 2010 ; Conference date: 20-05-2010 Through 22-05-2010",

year = "2013",

doi = "10.1145/2532568",

language = "English (US)",

volume = "18",

journal = "ACM Journal of Experimental Algorithmics",

issn = "1084-6654",

publisher = "Association for Computing Machinery",

}

TY - JOUR

T1 - On branching rules for convex mixed-integer nonlinear optimization

AU - Bonami, Pierre

AU - Lee, Jon

AU - Leyffer, Sven

AU - Wachter, Andreas

PY - 2013

Y1 - 2013

N2 - Branch-and-Bound (B&B) is perhaps the most fundamental algorithm for the global solution of convex Mixed-Integer Nonlinear Programming (MINLP) problems. It is well-known that carrying out branching in a nonsimplistic manner can greatly enhance the practicality of B&B in the context of Mixed-Integer Linear Programming (MILP). No detailed study of branching has heretofore been carried out for MINLP. In this article, we study and identify useful sophisticated branching methods for MINLP, including novel approaches based on approximations of the nonlinear relaxations by linear and quadratic programs.

AB - Branch-and-Bound (B&B) is perhaps the most fundamental algorithm for the global solution of convex Mixed-Integer Nonlinear Programming (MINLP) problems. It is well-known that carrying out branching in a nonsimplistic manner can greatly enhance the practicality of B&B in the context of Mixed-Integer Linear Programming (MILP). No detailed study of branching has heretofore been carried out for MINLP. In this article, we study and identify useful sophisticated branching methods for MINLP, including novel approaches based on approximations of the nonlinear relaxations by linear and quadratic programs.

KW - Branch-and-bound

KW - Mixed-integer nonlinear programming

KW - Strong-Branching

UR - http://www.scopus.com/inward/record.url?scp=84908680622&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84908680622&partnerID=8YFLogxK

U2 - 10.1145/2532568

DO - 10.1145/2532568

M3 - Conference article

AN - SCOPUS:84908680622

SN - 1084-6654

VL - 18

JO - ACM Journal of Experimental Algorithmics

JF - ACM Journal of Experimental Algorithmics

M1 - 2532568

T2 - 9th International Symposium on Experimental Algorithms, SEA 2010

Y2 - 20 May 2010 through 22 May 2010

ER -

On branching rules for convex mixed-integer nonlinear optimization

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this