An algorithmic framework for convex mixed integer nonlinear programs

Pierre Bonami; Lorenz T. Biegler; Andrew R. Conn; Gérard Cornuéjols; Ignacio E. Grossmann; Carl D. Laird; Jon Lee; Andrea Lodi; François Margot; Nicolas Sawaya; Andreas Wächter

doi:10.1016/j.disopt.2006.10.011

An algorithmic framework for convex mixed integer nonlinear programs

Pierre Bonami, Lorenz T. Biegler, Andrew R. Conn, Gérard Cornuéjols, Ignacio E. Grossmann, Carl D. Laird, Jon Lee, Andrea Lodi, François Margot, Nicolas Sawaya, Andreas Wächter^*

^*Corresponding author for this work

Industrial Engineering and Management Sciences

Research output: Contribution to journal › Article › peer-review

616 Scopus citations

Abstract

This paper is motivated by the fact that mixed integer nonlinear programming is an important and difficult area for which there is a need for developing new methods and software for solving large-scale problems. Moreover, both fundamental building blocks, namely mixed integer linear programming and nonlinear programming, have seen considerable and steady progress in recent years. Wishing to exploit expertise in these areas as well as on previous work in mixed integer nonlinear programming, this work represents the first step in an ongoing and ambitious project within an open-source environment. COIN-OR is our chosen environment for the development of the optimization software. A class of hybrid algorithms, of which branch-and-bound and polyhedral outer approximation are the two extreme cases, are proposed and implemented. Computational results that demonstrate the effectiveness of this framework are reported. Both the library of mixed integer nonlinear problems that exhibit convex continuous relaxations, on which the experiments are carried out, and a version of the software used are publicly available.

Original language	English (US)
Pages (from-to)	186-204
Number of pages	19
Journal	Discrete Optimization
Volume	5
Issue number	2
DOIs	https://doi.org/10.1016/j.disopt.2006.10.011
State	Published - May 2008

Funding

Pierre Bonami, Carl D. Laird and Nicolas Sawaya were supported in part by a grant from IBM. Gérard Cornuéjols was supported in part by NSF grant CMMI-0653419, ANR grant BLAN06-1-138894 and ONR grant N00014-03-1-0188. Part of this research was carried out when Andrea Lodi was a Herman Goldstine Fellow in the Department of Mathematical Sciences of the IBM T.J. Watson Research Center, whose support is strongly acknowledged. François Margot was supported in part by a grant from IBM and ONR grant N00014-03-1-0188.

Keywords

Branch-and-bound
MINLP test problems
Mixed integer nonlinear programming
Open-source
Outer-approximation

ASJC Scopus subject areas

Theoretical Computer Science
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1016/j.disopt.2006.10.011

Cite this

@article{9451a0a105b2410bb9df8f22ac57e96e,

title = "An algorithmic framework for convex mixed integer nonlinear programs",

abstract = "This paper is motivated by the fact that mixed integer nonlinear programming is an important and difficult area for which there is a need for developing new methods and software for solving large-scale problems. Moreover, both fundamental building blocks, namely mixed integer linear programming and nonlinear programming, have seen considerable and steady progress in recent years. Wishing to exploit expertise in these areas as well as on previous work in mixed integer nonlinear programming, this work represents the first step in an ongoing and ambitious project within an open-source environment. COIN-OR is our chosen environment for the development of the optimization software. A class of hybrid algorithms, of which branch-and-bound and polyhedral outer approximation are the two extreme cases, are proposed and implemented. Computational results that demonstrate the effectiveness of this framework are reported. Both the library of mixed integer nonlinear problems that exhibit convex continuous relaxations, on which the experiments are carried out, and a version of the software used are publicly available.",

keywords = "Branch-and-bound, MINLP test problems, Mixed integer nonlinear programming, Open-source, Outer-approximation",

author = "Pierre Bonami and Biegler, {Lorenz T.} and Conn, {Andrew R.} and G{\'e}rard Cornu{\'e}jols and Grossmann, {Ignacio E.} and Laird, {Carl D.} and Jon Lee and Andrea Lodi and Fran{\c c}ois Margot and Nicolas Sawaya and Andreas W{\"a}chter",

note = "Funding Information: Pierre Bonami, Carl D. Laird and Nicolas Sawaya were supported in part by a grant from IBM. G{\'e}rard Cornu{\'e}jols was supported in part by NSF grant CMMI-0653419, ANR grant BLAN06-1-138894 and ONR grant N00014-03-1-0188. Part of this research was carried out when Andrea Lodi was a Herman Goldstine Fellow in the Department of Mathematical Sciences of the IBM T.J. Watson Research Center, whose support is strongly acknowledged. Fran{\c c}ois Margot was supported in part by a grant from IBM and ONR grant N00014-03-1-0188.",

year = "2008",

month = may,

doi = "10.1016/j.disopt.2006.10.011",

language = "English (US)",

volume = "5",

pages = "186--204",

journal = "Discrete Optimization",

issn = "1572-5286",

publisher = "Elsevier",

number = "2",

}

TY - JOUR

T1 - An algorithmic framework for convex mixed integer nonlinear programs

AU - Bonami, Pierre

AU - Biegler, Lorenz T.

AU - Conn, Andrew R.

AU - Cornuéjols, Gérard

AU - Grossmann, Ignacio E.

AU - Laird, Carl D.

AU - Lee, Jon

AU - Lodi, Andrea

AU - Margot, François

AU - Sawaya, Nicolas

AU - Wächter, Andreas

N1 - Funding Information: Pierre Bonami, Carl D. Laird and Nicolas Sawaya were supported in part by a grant from IBM. Gérard Cornuéjols was supported in part by NSF grant CMMI-0653419, ANR grant BLAN06-1-138894 and ONR grant N00014-03-1-0188. Part of this research was carried out when Andrea Lodi was a Herman Goldstine Fellow in the Department of Mathematical Sciences of the IBM T.J. Watson Research Center, whose support is strongly acknowledged. François Margot was supported in part by a grant from IBM and ONR grant N00014-03-1-0188.

PY - 2008/5

Y1 - 2008/5

N2 - This paper is motivated by the fact that mixed integer nonlinear programming is an important and difficult area for which there is a need for developing new methods and software for solving large-scale problems. Moreover, both fundamental building blocks, namely mixed integer linear programming and nonlinear programming, have seen considerable and steady progress in recent years. Wishing to exploit expertise in these areas as well as on previous work in mixed integer nonlinear programming, this work represents the first step in an ongoing and ambitious project within an open-source environment. COIN-OR is our chosen environment for the development of the optimization software. A class of hybrid algorithms, of which branch-and-bound and polyhedral outer approximation are the two extreme cases, are proposed and implemented. Computational results that demonstrate the effectiveness of this framework are reported. Both the library of mixed integer nonlinear problems that exhibit convex continuous relaxations, on which the experiments are carried out, and a version of the software used are publicly available.

AB - This paper is motivated by the fact that mixed integer nonlinear programming is an important and difficult area for which there is a need for developing new methods and software for solving large-scale problems. Moreover, both fundamental building blocks, namely mixed integer linear programming and nonlinear programming, have seen considerable and steady progress in recent years. Wishing to exploit expertise in these areas as well as on previous work in mixed integer nonlinear programming, this work represents the first step in an ongoing and ambitious project within an open-source environment. COIN-OR is our chosen environment for the development of the optimization software. A class of hybrid algorithms, of which branch-and-bound and polyhedral outer approximation are the two extreme cases, are proposed and implemented. Computational results that demonstrate the effectiveness of this framework are reported. Both the library of mixed integer nonlinear problems that exhibit convex continuous relaxations, on which the experiments are carried out, and a version of the software used are publicly available.

KW - Branch-and-bound

KW - MINLP test problems

KW - Mixed integer nonlinear programming

KW - Open-source

KW - Outer-approximation

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

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

U2 - 10.1016/j.disopt.2006.10.011

DO - 10.1016/j.disopt.2006.10.011

M3 - Article

AN - SCOPUS:41149102529

SN - 1572-5286

VL - 5

SP - 186

EP - 204

JO - Discrete Optimization

JF - Discrete Optimization

IS - 2

ER -

An algorithmic framework for convex mixed integer nonlinear programs

Abstract

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this