Dagstuhl Seminar 18081
Designing and Implementing Algorithms for Mixed-Integer Nonlinear Optimization
( Feb 18 – Feb 23, 2018 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/18081
Organizers
- Pierre Bonami (IBM Spain - Madrid, ES)
- Ambros Gleixner (Konrad-Zuse-Zentrum - Berlin, DE)
- Jeff Linderoth (University of Wisconsin - Madison, US)
- Ruth Misener (Imperial College London, GB)
Contact
- Shida Kunz (for scientific matters)
- Simone Schilke (for administrative matters)
Impacts
- Extended formulations for convex hulls of some bilinear functions : article : 30 pp. - Gupte, Akshay; Kalinowski, Thomas; Rigterink, Fabian; Waterer, Hamish - Amsterdam : Elsevier, 2020 - (Discrete Optimization ; 36. 2020, Article 100566).
- Intersection cuts for factorable MINLP - Serrano, Felipe - Berlin : Zuse Institut, 2018. - 15 pp. - (ZIB Report ; 18-59).
- Intersection disjunctions for reverse convex sets - Towle, Eli; Luedtke, James - Cornell University : arXiv.org, 2019. - 24 pp..
- Mixed-Integer Convex Nonlinear Optimization with Gradient-Boosted Trees Embedded - Mistry, Miten; Letsios, Dimitrios; Krennrich, Gerhard; Lee, Robert M.; Misener, Ruth - Cornell University : arXiv.org, 2018. - 35 pp..
- Mixed-Integer Nonlinear Programming 2018 : Special issue - Sahinidis, Nikolaos V. - Berlin : Springer, 2019. - pp. 301-682 - (Optimization and engineering ; 20. 2019, 2).
- On the Relation between the Extended Supporting Hyperplane Algorithm and Kelley's Cutting Plane Algorithm - Serrano, Felipe; Schwarz, Robert; Gleixner, Ambros M. - Berlin : Zuse Institut, 2019. - 16 pp. - (ZIB Report ; 19-18).
- Selecting cutting planes for quadratic semidefinite outer-approximation via trained neural networks - Baltean-Lugojan, Radu; Bonami, Pierre; Misener, Ruth; Tramontani, Andrea - Philadelphia : Optimization Online, 2018. - 37 pp..
- The running intersection relaxation of the multilinear polytope / - Pia, Alberto Del ; Khajavirad, Aida - http://www.optimization-online.org/, 2018. - 35 pp..
Schedule
Mathematical models for optimal decisions often require both nonlinear and discrete components. These mixed-integer nonlinear programs (MINLP) may be used to optimize the energy use of large industrial plants, integrate renewable sources into energy networks, design biological and biomedical systems, and address numerous other applications of societal importance. The first MINLP algorithms and software were designed by application engineers. While these efforts initially proved useful, scientists, engineers, and practitioners have realized that a transformational shift in technology will be required for MINLP to achieve its full potential. MINLP has transitioned to a forefront position in computer science, with researchers actively developing MINLP theory, algorithms, and implementations. Even with their concerted effort, algorithms and available software are often unable to solve practically-sized instances of these important models. Current obstacles include characterizing the computability boundary, effectively exploiting known optimization technologies for specialized classes of MINLP, and effectively using logical formulas holistically throughout algorithms.
This seminar aims to address this mismatch between natural optimization models for important scientific problems and practical optimization solvers for their solution. A significant seminar outcome will be the accelerated development of powerful new solver technology for mixed-integer nonlinear programs.
By bringing together experts in both theory and implementation, this seminar will energize efforts making MINLP as ubiquitous a paradigm for both modeling and solving important decision problems as mixed-integer linear programming (MIP) and nonlinear programming (NLP) have become in recent years. In particular, we plan to highlight:
- MINLP Solver Software. Early in the seminar, the main developers of MINLP software packages will outline the current state of their software. This will serve as a needs analysis for the community to identify crucial areas for future development. We will also dedicate one or two sessions to discuss best practices for conducting scientifically-meaningful computational experiments in MINLP.
- Intersecting Mixed-Integer & Nonlinear Programming. MINLP is a superset of both MIP and NLP, so we aim to leverage the best methods from both.
- Complexity & Convergence Analysis. Studying complexity unpacks the border of tractability in MINLP. Convergence analysis helps motivate which algorithmic components to develop.
- Submodular Optimization. Some important MINLP problems reduce to maximizing submodular functions.
- Driving Applications. Applications experts, e.g. in petrochemicals, manufacturing, and gas networks, will offer their perspectives on what practitioners need from MINLP solvers.
Creative Commons BY 3.0 DE
Pierre Bonami, Ambros M. Gleixner, Jeff Linderoth, and Ruth Misener
This workshop aimed to address this mismatch between natural optimization models for important scientific problems and practical optimization solvers for their solution. By bringing together experts in both theory and implementation, this workshop energized efforts making MINLP as ubiquitous a paradigm for both modeling and solving important decision problems as mixed-integer linear programming (MIP) and nonlinear programming (NLP) have become in recent years. In particular, we highlighted:
- MINLP Solver Software Early in the workshop, the main developers of MINLP software packages outlined the current state of their software. This served as a needs analysis for the community to identify crucial areas for future development. We also dedicated a break-out session discussing best practices for conducting scientifically-meaningful computational experiments in MINLP.
- Intersecting Mixed-Integer & Nonlinear Programming MINLP is a superset of both mixed integer linear optimization and nonlinear optimization, so we leveraged the best methods from both by incorporating both sets of experts.
- Driving Applications Applications experts, e.g. in petrochemicals, manufacturing, and gas networks, offered their perspectives on what practitioners need from MINLP solvers. We dedicated an entire break-out session to energy applications and explored what are the needs for MINLP within the energy domain. During the open problem session, several other applications experts outlined other open problems in engineering.
- Connections between MINLP and machine learning Many machine learning challenges can be formulated as MINLP. Also, machine learning can significantly improve MINLP solver software. We explored these connections at length in a break-out session.
This seminar brought together an assortment of computer scientists with expertise in mathematical optimization. Many of the presentations were more theoretical and suggested new technologies that the solver software could incorporate. Other presentations were more practical and discussed building solver software or applying that software to specific domain applications.
As a result of this seminar, we are planning a special issue in the journal "Optimization & Engineering". We are also working to turn the notes from our open problem session into a larger document that will start a conversation with the entire mathematical optimisation community. Participants broadly expressed that this week at Dagstuhl helped them workshop their papers, so several academic papers will explicitly mention the Dagstuhl seminar. Finally, a new set of metrics for comparing MINLP solvers were developed at this meeting and will greatly aid future solver testing.
Pierre Bonami, Ambros M. Gleixner, Jeff Linderoth, and Ruth Misener
- Tobias Achterberg (Konrad-Zuse-Zentrum - Berlin, DE) [dblp]
- Claire Adjiman (Imperial College London, GB) [dblp]
- Shabbir Ahmed (Georgia Institute of Technology - Atlanta, US) [dblp]
- Kurt M. Anstreicher (University of Iowa, US) [dblp]
- Radu Baltean-Lugojan (Imperial College London, GB) [dblp]
- Pietro Belotti (Fair Isaac, GB) [dblp]
- David Bernal Neira (Carnegie Mellon University - Pittsburgh, US)
- Timo Berthold (FICO - Berlin, DE) [dblp]
- Christian Bliek (IBM - Valbonne, FR) [dblp]
- Pierre Bonami (IBM Spain - Madrid, ES) [dblp]
- Fani Boukouvala (Georgia Institute of Technology - Atlanta, US) [dblp]
- Andrea Callia D'Iddio (Imperial College London, GB) [dblp]
- Sanjeeb Dash (IBM TJ Watson Research Center - Yorktown Heights, US) [dblp]
- Alberto Del Pia (University of Wisconsin - Madison, US) [dblp]
- Santanu Dey (Georgia Institute of Technology - Atlanta, US) [dblp]
- Matteo Fischetti (University of Padova, IT) [dblp]
- Ambros Gleixner (Konrad-Zuse-Zentrum - Berlin, DE) [dblp]
- Ignacio Grossmann (Carnegie Mellon University - Pittsburgh, US) [dblp]
- Andreas Grothey (University of Edinburgh, GB) [dblp]
- Oktay Gunluk (IBM TJ Watson Research Center - Yorktown Heights, US) [dblp]
- Akshay Gupte (Clemson University, US) [dblp]
- Hassan Hijazi (Los Alamos National Laboratory, US) [dblp]
- Aida Khajavirad (Carnegie Mellon University - Pittsburgh, US) [dblp]
- Carl Damon Laird (Sandia National Labs - Albuquerque, US) [dblp]
- Amélie Lambert (CNAM - Paris, FR) [dblp]
- Jon Lee (University of Michigan - Ann Arbor, US) [dblp]
- Sven Leyffer (Argonne National Laboratory - Lemont, US) [dblp]
- Leo Liberti (CNRS & Ecole Polytechnique - Palaiseau) [dblp]
- Frauke Liers (Universität Erlangen-Nürnberg, DE) [dblp]
- Jeff Linderoth (University of Wisconsin - Madison, US) [dblp]
- Andrea Lodi (Polytechnique Montreal, CA) [dblp]
- James Luedtke (University of Wisconsin - Madison, US) [dblp]
- Ashutosh Mahajan (Indian Institute of Technology - Mumbai, IN) [dblp]
- Alexander Martin (Universität Erlangen-Nürnberg, DE) [dblp]
- Ruth Misener (Imperial College London, GB) [dblp]
- Miten Mistry (Imperial College London, GB) [dblp]
- Benjamin Müller (Konrad-Zuse-Zentrum - Berlin, DE) [dblp]
- Sebastian Sager (Universität Magdeburg, DE) [dblp]
- Nikolaos V. Sahinidis (Carnegie Mellon University - Pittsburgh, US) [dblp]
- Felipe Serrano (Konrad-Zuse-Zentrum - Berlin, DE) [dblp]
- Mohit Tawarmalani (Purdue University - West Lafayette, US) [dblp]
- Juan Pablo Vielma (MIT - Camridge, US) [dblp]
- Stefan Vigerske (GAMS Software GmbH, DE) [dblp]
- Robert Weismantel (ETH Zürich, CH) [dblp]
- Angelika Wiegele (Alpen-Adria-Universität Klagenfurt, AT) [dblp]
- Sven Wiese (MOSEK ApS - Copenhagen, DK) [dblp]
Classification
- data structures / algorithms / complexity
- optimization / scheduling
