IBM Nonlinear Discrete Optimization and Mixed Integer NonLinear Programming Project

Research on solution techniques for Nonlinear Discrete Optimization and Mixed Integer Nonlinear Optimization

HOT 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

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.