On branching rules for convex mixed-integer nonlinear optimization

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

*Corresponding author for this work

Research output: Contribution to journalConference article

5 Citations (Scopus)

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 languageEnglish (US)
Article number2532568
JournalACM Journal of Experimental Algorithmics
Volume18
DOIs
StatePublished - Jan 1 2013
Event9th International Symposium on Experimental Algorithms, SEA 2010 - Naples, Italy
Duration: May 20 2010May 22 2010

Fingerprint

Branching Rules
Mixed Integer Nonlinear Programming
Nonlinear programming
Nonlinear Optimization
Branching
Integer
Quadratic Program
Mixed Integer Linear Programming
Branch-and-bound
Linear Program
Global Solution
Linear programming
Approximation

Keywords

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

ASJC Scopus subject areas

  • Theoretical Computer Science

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",
year = "2013",
month = "1",
day = "1",
doi = "10.1145/2532568",
language = "English (US)",
volume = "18",
journal = "Journal of Experimental Algorithmics",
issn = "1084-6654",
publisher = "Association for Computing Machinery (ACM)",

}

On branching rules for convex mixed-integer nonlinear optimization. / Bonami, Pierre; Lee, Jon; Leyffer, Sven; Wachter, Andreas.

In: ACM Journal of Experimental Algorithmics, Vol. 18, 2532568, 01.01.2013.

Research output: Contribution to journalConference article

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/1/1

Y1 - 2013/1/1

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

VL - 18

JO - Journal of Experimental Algorithmics

JF - Journal of Experimental Algorithmics

SN - 1084-6654

M1 - 2532568

ER -