Research on solution techniques for Nonlinear Discrete Optimization and Mixed Integer Nonlinear Optimization
IMA Hot Topics Workshop:
Mixed-Integer Nonlinear Optimization: Algorithmic Advances and Applications, November 17-21, 2008
Mixed Integer Nonlinear Programming @IBM
New Exploratory Computer Science Research Projects
Open Collaborative Research
Joao Goncalves
Oktay Günlük
Jon Lee
Andreas Wächter
Collaboration with Carnegie Mellon University
Open Cyberinfrastructure for Mixed-integer Nonlinear Programming: Collaboration and Deployment via Virtual Environments
Bonmin
(Basic Open-source Nonlinear Mixed INteger programming) and
Couenne
(Convex Over and Under ENvelopes for Nonlinear Estimation):
Open-source C++ codes for MINLP (Mixed Integer NonLinear Programming) problems. Bonmin is aimed at problems with convex relaxation, though its B&B algorithmic option has parameters that can be set to make it a good heuristic for
non-convex models. Couenne is an experimental global optimization solver using a spatial B&B approach.
Bonmin and Couenne are distributed under the CPL (Common Public
License) on
COIN-OR
. The CPL is a license approved by the OSI (Open Source
Initiative), thus Bonmin and Couenne are OSI Certified Open Source Software
Bonmin@NEOS
(Bonmin is also available for use on the
NEOS Server for Optimization
)
A CMU-IBM MINLP webpage at CMU
Pietro Belotti
Lorenz T. Biegler
Gérard P. Cornuéjols
Ignacio E. Grossmann
François Margot
Nikolaos V. Sahinidis
Collaboration with University of California, Davis
Jesús A. De Loera
Peter Malkin
Susan Margulies
Other collaborators
Pierre Bonami (Marseilles)
Yael Berstein (Technion)
Christiana Bragalli (Bologna)
Andrew Conn (IBM)
Claudia D'Ambrosio (Bologna)
Carl Laird (TAMU>
Leo Liberti (LIX, Ecole Polytechnique, Palaiseau, France)
Jeff Linderoth (Wisconsin)
Andrea Lodi (Bologna)
Shmuel Onn (Technion)
Nicolas Sawaya
Paolo Toth (Bologna)
Stefan Vigerske (Humboldt-University Berlin)
Robert Weismantel (Magdeberg)
Papers
Jon Lee, Maxim Sviridenko and Jan Vondrák.
Submodular Maximization Over Multiple Matroids via Generalized Exchange Properties, IBM Research Report RC24695, 03/2009.
Non-monotone submodular maximization under matroid and knapsack constraints, Jon Lee, Vahab S. Mirrokni, Viswanath Nagarajan, Maxim Sviridenko, 41st ACM Symposium on Theory of Computing (STOC 2009). To appear.
Convex Relaxations of Non-Convex Mixed Integer Quadratically Constrained Programs: Projected Formulations, Anureet Saxena, Pierre Bonami and Jon Lee. IBM Research Report RC24695, 11/2008.
Efficient high-precision dense matrix algebra on parallel architectures for nonlinear discrete optimization, John Gunnels, Jon Lee, Susan Margulies. IBM Research Report RC24682, 10/2008.
Maximizing Non-monotone Submodular Functions under Matroid and Knapsack Constraints, Jon Lee, Vahab S. Mirrokni, Viswanath Nagarajan, Maxim Sviridenko. IBM Research Report RC24679, 10/2008.
Primal Heuristics for Mixed Integer Nonlinear Programs, Pierre Bonami; João P. M. Gonçalves. IBM Research Report RC24639, 9/2008.
Branching and bounds tightening techniques for non-convex MINLP, Pietro Belotti, Jon Lee, Leo Liberti, Francois Margot, Andreas Waechter. IBM Research Report RC24620, 08/2008.
Convex Relaxations of Non-Convex Mixed Integer Quadratically Constrained Programs: Extended Formulations, Anureet Saxena, Pierre Bonami and Jon Lee. IBM Research Report RC24621, 08/2008.
Nonlinear optimization for matroid intersection and extensions,
Yael Berstein, Jon Lee, Shmuel Onn and Robert Weismantel.
IBM Research Report RC24610, 07/2008.
Nonlinear optimization over a weighted independence system,
Jon Lee, Shmuel Onn and Robert Weismantel.
IBM Research Report RC24513, 05/2008.
Disjunctive cuts for non-convex mixed integer quadratically constrained programs,
Anureet Saxena, Pierre Bonami and Jon Lee.
In: “Integer programming and combinatorial optimization (Bertinoro, 2008)“, A. Lodi, A. Panconesi, and G. Rinaldi, Eds., Lecture Notes in Computer Science volume 5035, pp. 17–33. Springer-Verlag Berlin Heidelberg, 2008.
Perspective relaxation of mixed integer nonlinear programs with indicator variables,
O. Gunluk and J. T. Linderoth. In: “Integer programming and combinatorial optimization (Bertinoro, 2008)“, A. Lodi, A. Panconesi, and G. Rinaldi, Eds., Lecture Notes in Computer Science volume 5035, pp. 1-16. Springer-Verlag Berlin Heidelberg, 2008.
Water Network Design by MINLP, Cristiana Bragalli, Claudia D'Ambrosio, Jon Lee, Andrea Lodi, Paolo Toth. IBM Research Report RC24495, 02/2008.
Hilbert's Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility,
Jesus A. De Loera, Jon Lee, Peter Malkin, Susan Margulies.
Proceedings of the 21st International Symposium on Symbolic and Algebraic Computation (ISSAC 2008, Linz/Hagenberg, Austria), Association for Computing Machinery, 197-206, 2008.
Rapid development of an MINLP solver with COIN-OR,
Pierre Bonami, John Forrest, Jon Lee and Andreas Wächter.
Optima. 75:1-5, December 2007.
On test sets for nonlinear integer maximization. Jon Lee, Shmuel Onn and Robert Weismantel. Operations Research Letters 36:439–443, 2008.
Nonlinear Matroid Optimization and Experimental Design, Yael Berstein, Jon Lee, Hugo Maruri-Aguilar, Shmuel Onn, Eva Riccomagno, Robert Weismantel, Henry Wynn. SIAM J. on Discrete Mathematics 22(3):901-919, 2008.
Expressing Combinatorial Optimization Problems by Systems of Polynomial Equations and the Nullstellensatz, Jesus A. De Loera, Jon Lee, Susan Margulies, Shmuel Onn. IBM Research Report RC24276, 06/2007. To appear in: Combinatorics Probability and Computing.
Mixed Integer Nonlinear Programming: Some Modeling and Solution Issues, Jon Lee. In B. Schieber ed., "Business Optimization", IBM Journal of Research and Development, 51(3/4): 489-497, 2007.
MINLP Strengthening for Separable Convex Quadratic Transportation-Cost UFL, Oktay Gunluk, Jon Lee and Robert Weismantel. IBM Research Report RC24213, 03/2007.
An Exact Solution Approach for Portfolio Optimization Problems under Stochastic and Integer Constraints, Pierre Bonami and Miguel Lejeune. IBM Research Report RC24215, 02/2007. To appear in: Operations Research.
An MINLP Solution Method for a Water Network Problem,
Christiana Bragalli, Claudia D'Ambrosio, Jon Lee, Andrea Lodi, Paolo Toth. 2/28/06.
Algorithms - ESA 2006 (14th Annual European Symposium. Zurich, Switzerland, September 2006, Proceedings),
Y. Azar and T. Erlebach, Eds., pages 696-707. Springer, 2006.
An Algorithmic Framework for Convex Mixed Integer Nonlinear Programs,
Pierre Bonami, Lorenz Biegler, Andrew Conn, Gerard Cornuejols, Ignacio Grossmann, Carl Laird, Jon Lee, Andrea Lodi, Francois Margot, Sawaya Nicolas, Andreas Waechter. Discrete Optimization, 5:186–204, 2008.
A Feasibility Pump for Mixed Integer Nonlinear Programs,
Pierre Bonami, Gérard Cornuéjols, Andrea Lodi, François Margot. IBM Research Report RC23862, 2/02/06. To appear in: Mathematical Programming.
In Situ Column Generation for a Cutting-Stock Problem,
Jon Lee. Computers & Operations Research,
Volume 34, Issue 8, August 2007, Pages 2345-2358.
Other resources
COIN-OR
(our outlet for open-source software)
Using Bonmin (and other COIN-OR solvers) with GAMS
NEOS Server for Optimization
(a server for remote solution of optimization problems)
MINLP World (GAMS)
Other MINLP test problems
MacMINLP : ampl collection of Mixed Integer Nonlinear Programs
Other MINLP solvers
AlphaECP
BARON
DICOPT
FilMINT
LOGMIP
MINLPBB (Dundee solvers for MINLP)
MINOPT
SBB
Biq Mac Solver - Binary quadratic and Max cut Solver
Other MINLP researchers
Christodoulos A. Floudas
Sven Leyffer
Ivo Nowak
Mohit Tawarmalani
Tapio Westerlund
By Jon Lee:
Last updated 1 Apr 2009