License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2022.23
URN: urn:nbn:de:0030-drops-165579
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16557/
Go to the corresponding LIPIcs Volume Portal

Sharma, Meenarli ; Mahajan, Ashutosh

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

pdf-format:
LIPIcs-SEA-2022-23.pdf (0.9 MB)

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.

BibTeX - Entry

@InProceedings{sharma_et_al:LIPIcs.SEA.2022.23,
  author =	{Sharma, Meenarli and Mahajan, Ashutosh},
  title =	{{Automatic Reformulations for Convex Mixed-Integer Nonlinear Optimization: Perspective and Separability}},
  booktitle =	{20th International Symposium on Experimental Algorithms (SEA 2022)},
  pages =	{23:1--23:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-251-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{233},
  editor =	{Schulz, Christian and U\c{c}ar, Bora},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16557},
  URN =		{urn:nbn:de:0030-drops-165579},
  doi =		{10.4230/LIPIcs.SEA.2022.23},
  annote =	{Keywords: Convex MINLP, perspective reformulation, branch-and-bound, outer approximation, function separability}
}

Keywords: Convex MINLP, perspective reformulation, branch-and-bound, outer approximation, function separability
Collection: 20th International Symposium on Experimental Algorithms (SEA 2022)
Issue Date: 2022
Date of publication: 11.07.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI