Document Open Access Logo

Automatic Reformulations for Convex Mixed-Integer Nonlinear Optimization: Perspective and Separability

Authors Meenarli Sharma , Ashutosh Mahajan

PDF
Thumbnail PDF

File

LIPIcs.SEA.2022.23.pdf
  • Filesize: 0.89 MB
  • 20 pages

Document Identifiers

Author Details

Meenarli Sharma
  • Institute of Mathematics, University of Augsburg, Germany
Ashutosh Mahajan
  • Industrial Engineering and Operations Research, Indian Institute of Technology Bombay, India

Cite As Get BibTex

Meenarli Sharma and Ashutosh Mahajan. Automatic Reformulations for Convex Mixed-Integer Nonlinear Optimization: Perspective and Separability. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 23:1-23:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.SEA.2022.23

Abstract

Tight reformulations of combinatorial optimization problems like Convex Mixed-Integer Nonlinear Programs (MINLPs) enable one to solve these problems faster by obtaining tight bounds on optimal value. We consider two techniques for reformulation: perspective reformulation and separability detection. We develop routines for automatic detection of problem structures suitable for these reformulations, and implement new extensions. Since detecting all "on-off" sets for perspective reformulation in a problem can be as hard as solving the original problem, we develop heuristic methods to automatically identify them. The LP/NLP branch-and-bound method is strengthened via "perspective cuts" derived from these automatic routines. We also provide methods to generate tight perspective cuts at different nodes in the branch-and-bound tree. The second structure, i.e., separability of nonlinear functions, is detected by means of the computational graph of the function. Our routines have been implemented in the open-source Minotaur solver for general convex MINLPs. Computational results show an improvement of up to 45% in the solution time and the size of the branch-and-bound tree for convex instances from benchmark library MINLPLib. On instances where reformulation using function separability induces structures that are amenable to perspective reformulation, we observe an improvement of up to 88% in the solution time.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorial optimization
  • Mathematics of computing → Solvers
  • Applied computing → Operations research
Keywords
  • Convex MINLP
  • perspective reformulation
  • branch-and-bound
  • outer approximation
  • function separability

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. K. Abhishek, S. Leyffer, and J. T. Linderoth. FilMINT: An outer-approximation-based solver for nonlinear mixed integer programs. Preprint ANL/MCS-P1374-0906, Mathematics and Computer Science Division, Argonne National Laboratory, 2006. Google Scholar
  2. S. Aktürk, A. Atamtürk, and S. Gürel. A strong conic quadratic reformulation for machine-job assignment with controllable processing times. Operations Research Letters, 37:187-191, 2009. Google Scholar
  3. Ksenia Bestuzheva, Ambros Gleixner, and Stefan Vigerske. A computational study of perspective cuts. arXiv preprint arXiv:2103.09573, 2021. Google Scholar
  4. Pierre Bonami and Jon Lee. BONMIN user’s manual. Numer Math, 4:1-32, 2007. Google Scholar
  5. Michael R Bussieck, Arne Stolbjerg Drud, and Alexander Meeraus. MINLPLib - a collection of test models for mixed-integer nonlinear programming. INFORMS Journal on Computing, 15(1):114-119, 2003. Google Scholar
  6. Elizabeth Dolan and Jorge Moré. Benchmarking optimization software with performance profiles. Mathematical Programming, 91:201-213, 2002. Google Scholar
  7. A. Frangioni and C. Gentile. Perspective cuts for a class of convex 0-1 mixed integer programs. Mathematical Programming, 106:225-236, 2006. Google Scholar
  8. Antonio Frangioni, Fabio Furini, and Claudio Gentile. Approximated perspective relaxations: a project and lift approach. Computational Optimization and Applications, 63(3):705-735, 2016. Google Scholar
  9. Antonio Frangioni and Claudio Gentile. Perspective cuts for a class of convex 0-1 mixed integer programs. Mathematical Programming, 106(2):225-236, 2006. Google Scholar
  10. Antonio Frangioni and Claudio Gentile. A computational comparison of reformulations of the perspective relaxation: SOCP vs. cutting planes. Operations Research Letters, 37(3):206-210, 2009. Google Scholar
  11. Antonio Frangioni, Claudio Gentile, and Fabrizio Lacalandra. Solving unit commitment problems with general ramp constraints. International Journal of Electrical Power & Energy Systems, 30(5):316-326, 2008. Google Scholar
  12. Kevin C Furman, Nicolas W Sawaya, and Ignacio E Grossmann. A computationally useful algebraic representation of nonlinear disjunctive convex sets using the perspective function. Computational Optimization and Applications, pages 1-26, 2020. Google Scholar
  13. Oktay Günlük and Jeff Linderoth. Perspective reformulations of mixed integer nonlinear programs with indicator variables. Mathematical programming, 124(1-2):183-205, 2010. Google Scholar
  14. Hassan Hijazi, Pierre Bonami, and Adam Ouorou. An outer-inner approximation for separable mixed-integer nonlinear programs. INFORMS Journal on Computing, 26(1):31-44, 2014. Google Scholar
  15. Norbert J Jobst, Michael D Horniman, Cormac A Lucas, Gautam Mitra, et al. Computational aspects of alternative portfolio selection models in the presence of discrete asset choice constraints. Quantitative finance, 1(5):489-501, 2001. Google Scholar
  16. KNITRO. KNITRO Documentation. Ziena Optimization., December 2012. Google Scholar
  17. Jan Kronqvist, Andreas Lundell, and Tapio Westerlund. Reformulations for utilizing separability when solving convex MINLP problems. Journal of Global Optimization, 71(3):571-592, 2018. Google Scholar
  18. Andreas Lundell, Jan Kronqvist, and Tapio Westerlund. The supporting hyperplane optimization toolkit for convex minlp. Journal of Global Optimization, pages 1-41, 2022. Google Scholar
  19. Andreas Lundell and Tapio Westerlund. Solving global optimization problems using reformulations and signomial transformations. Computers & Chemical Engineering, 116:122-134, 2018. Google Scholar
  20. Ashutosh Mahajan, Sven Leyffer, Jeff Linderoth, James Luedtke, and Todd Munson. Minotaur: A mixed-integer nonlinear optimization toolkit. Mathematical Programming Computation, pages 1-38, 2020. Google Scholar
  21. Wendel Melo, Marcia Fampa, and Fernanda Raupp. An overview of minlp algorithms and their implementation in muriqui optimizer. Annals of Operations Research, 286(1):217-241, 2020. Google Scholar
  22. Ivo Nowak, Norman Breitfeld, Eligius MT Hendrix, and Grégoire Njacheun-Njanzoua. Decomposition-based inner-and outer-refinement algorithms for global optimization. Journal of Global Optimization, 72(2):305-321, 2018. Google Scholar
  23. Ignacio Quesada and Ignacio E Grossmann. An LP/NLP based branch and bound algorithm for convex MINLP optimization problems. Computers & chemical engineering, 16(10-11):937-947, 1992. Google Scholar
  24. M. W. P. Savelsbergh. Preprocessing and probing techniques for mixed integer programming problems. ORSA Journal on Computing, 6:445-454, 1994. Google Scholar
  25. Meenarli Sharma, Mirko Hahn, Sven Leyffer, Lars Ruthotto, and Bart van Bloemen Waanders. Inversion of convection-diffusion equation with discrete sources. Optimization and Engineering, pages 1-39, 2020. Google Scholar
  26. Meenarli Sharma, Prashant Palkar, and Ashutosh Mahajan. Linearization and parallelization schemes for convex mixed-integer nonlinear optimization. Computational Optimization and Applications, pages 1-56, 2022. Google Scholar
  27. Mohit Tawarmalani and Nikolaos V Sahinidis. A polyhedral branch-and-cut approach to global optimization. Mathematical Programming, 103(2):225-249, 2005. Google Scholar
  28. Stephen J Wright, Robert D Nowak, and Mário AT Figueiredo. Sparse reconstruction by separable approximation. IEEE Transactions on Signal Processing, 57(7):2479-2493, 2009. Google Scholar
  29. Juan M Zamora and Ignacio E Grossmann. A global MINLP optimization algorithm for the synthesis of heat exchanger networks with no stream splits. Computers & Chemical Engineering, 22(3):367-384, 1998. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact