Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • Treffer 9 von 9
Zurück zur Trefferliste

A Status Report on Conflict Analysis in Mixed Integer Nonlinear Programming

  • Mixed integer nonlinear programs (MINLPs) are arguably among the hardest optimization problems, with a wide range of applications. MINLP solvers that are based on linear relaxations and spatial branching work similar as mixed integer programming (MIP) solvers in the sense that they are based on a branch-and-cut algorithm, enhanced by various heuristics, domain propagation, and presolving techniques. However, the analysis of infeasible subproblems, which is an important component of most major MIP solvers, has been hardly studied in the context of MINLPs. There are two main approaches for infeasibility analysis in MIP solvers: conflict graph analysis, which originates from artificial intelligence and constraint programming, and dual ray analysis. The main contribution of this short paper is twofold. Firstly, we present the first computational study regarding the impact of dual ray analysis on convex and nonconvex MINLPs. In that context, we introduce a modified generation of infeasibility proofs that incorporates linearization cuts that are only locally valid. Secondly, we describe an extension of conflict analysis that works directly with the nonlinear relaxation of convex MINLPs instead of considering a linear relaxation. This is work-in-progress, and this short paper is meant to present first theoretical considerations without a computational study for that part.

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar Statistik - Anzahl der Zugriffe auf das Dokument
Metadaten
Verfasserangaben:Jakob WitzigORCiD, Timo BertholdORCiD, Stefan Heinz
Dokumentart:Konferenzbeitrag
Titel des übergeordneten Werkes (Englisch):Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2019
Band:11494
Erste Seite:84
Letzte Seite:94
Serie:LNCS
Verlag:Springer
Jahr der Erstveröffentlichung:2019
Preprint:urn:nbn:de:0297-zib-71170
DOI:https://doi.org/10.1007/978-3-030-19212-9_6
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.