1 Search Results for "Sharma, Meenarli"

Document

DOI: 10.4230/LIPIcs.SEA.2022.23

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

Authors: Meenarli Sharma and Ashutosh Mahajan

Published in: LIPIcs, Volume 233, 20th International Symposium on Experimental Algorithms (SEA 2022)

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.

Cite as

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)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.SEA.2022.23},
  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}
}

Refine by Type
1 Document/PDF

Refine by Publication Year
1 2022

Refine by Author
1 Mahajan, Ashutosh
1 Sharma, Meenarli

Refine by Series/Journal
1 LIPIcs

Refine by Classification
1 Applied computing → Operations research
1 Mathematics of computing → Combinatorial optimization
1 Mathematics of computing → Solvers

Refine by Keyword
1 Convex MINLP
1 branch-and-bound
1 function separability
1 outer approximation
1 perspective reformulation

1 Search Results for "Sharma, Meenarli"

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

Abstract

Cite as

Thanks for your feedback!

Could not send message