Conflict Analysis for MINLP

  • The generalization of MIP techniques to deal with nonlinear, potentially non-convex, constraints have been a fruitful direction of research for computational MINLP in the last decade. In this paper, we follow that path in order to extend another essential subroutine of modern MIP solvers towards the case of nonlinear optimization: the analysis of infeasible subproblems for learning additional valid constraints. To this end, we derive two different strategies, geared towards two different solution approaches. These are using local dual proofs of infeasibility for LP-based branch-and-bound and the creation of nonlinear dual proofs for NLP-based branch-and-bound, respectively. We discuss implementation details of both approaches and present an extensive computational study, showing that both techniques can significantly enhance performance when solving MINLPs to global optimality.

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Jakob WitzigORCiD, Timo Berthold
Document Type:Article
Parent Title (English):INFORMS Journal on Computing
Volume:33
Issue:2
First Page:421
Last Page:435
Year of first publication:2021
Preprint:urn:nbn:de:0297-zib-78964
DOI:https://doi.org/10.1287/ijoc.2020.1050
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.