2 Search Results for "Gleixner, Ambros M."

Document
DOI: 10.4230/LIPIcs.CP.2023.27
Improving Conflict Analysis in MIP Solvers by Pseudo-Boolean Reasoning

Authors: Gioni Mexi, Timo Berthold, Ambros Gleixner, and Jakob Nordström

Published in: LIPIcs, Volume 280, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)

Abstract
Conflict analysis has been successfully generalized from Boolean satisfiability (SAT) solving to mixed integer programming (MIP) solvers, but although MIP solvers operate with general linear inequalities, the conflict analysis in MIP has been limited to reasoning with the more restricted class of clausal constraint. This is in contrast to how conflict analysis is performed in so-called pseudo-Boolean solving, where solvers can reason directly with 0-1 integer linear inequalities rather than with clausal constraints extracted from such inequalities. In this work, we investigate how pseudo-Boolean conflict analysis can be integrated in MIP solving, focusing on 0-1 integer linear programs (0-1 ILPs). Phrased in MIP terminology, conflict analysis can be understood as a sequence of linear combinations and cuts. We leverage this perspective to design a new conflict analysis algorithm based on mixed integer rounding (MIR) cuts, which theoretically dominates the state-of-the-art division-based method in pseudo-Boolean solving. We also report results from a first proof-of-concept implementation of different pseudo-Boolean conflict analysis methods in the open-source MIP solver SCIP. When evaluated on a large and diverse set of 0-1 ILP instances from MIPLIB2017, our new MIR-based conflict analysis outperforms both previous pseudo-Boolean methods and the clause-based method used in MIP. Our conclusion is that pseudo-Boolean conflict analysis in MIP is a promising research direction that merits further study, and that it might also make sense to investigate the use of such conflict analysis to generate stronger no-goods in constraint programming.
Cite as

Gioni Mexi, Timo Berthold, Ambros Gleixner, and Jakob Nordström. Improving Conflict Analysis in MIP Solvers by Pseudo-Boolean Reasoning. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 27:1-27:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{mexi_et_al:LIPIcs.CP.2023.27,
  author =	{Mexi, Gioni and Berthold, Timo and Gleixner, Ambros and Nordstr\"{o}m, Jakob},
  title =	{{Improving Conflict Analysis in MIP Solvers by Pseudo-Boolean Reasoning}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{27:1--27:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-300-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{280},
  editor =	{Yap, Roland H. C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.27},
  URN =		{urn:nbn:de:0030-drops-190641},
  doi =		{10.4230/LIPIcs.CP.2023.27},
  annote =	{Keywords: Integer programming, pseudo-Boolean solving, conflict analysis, cutting planes proof system, mixed integer rounding, division, saturation}
}
Document
DOI: 10.4230/DagRep.8.2.64
Designing and Implementing Algorithms for Mixed-Integer Nonlinear Optimization (Dagstuhl Seminar 18081)

Authors: Pierre Bonami, Ambros M. Gleixner, Jeff Linderoth, and Ruth Misener

Published in: Dagstuhl Reports, Volume 8, Issue 2 (2018)

Abstract
Mathematical models for optimal decisions often require both nonlinear and discrete components. These mixed-integer nonlinear programs (MINLP) may be used to optimize the energy use of large industrial plants, integrate renewable sources into energy networks, design biological and biomedical systems, and address numerous other applications of societal importance. The first MINLP algorithms and software were designed by application engineers. While these efforts initially proved useful, scientists, engineers, and practitioners have realized that a transformational shift in technology will be required for MINLP to achieve its full potential. MINLP has transitioned to a forefront position in computer science, with researchers actively developing MINLP theory, algorithms, and implementations. Even with their concerted effort, algorithms and available software are often unable to solve practically-sized instances of these important models. Current obstacles include characterizing the computability boundary, effectively exploiting known optimization technologies for specialized classes of MINLP, and effectively using logical formulas holistically throughout algorithms.
Cite as

Pierre Bonami, Ambros M. Gleixner, Jeff Linderoth, and Ruth Misener. Designing and Implementing Algorithms for Mixed-Integer Nonlinear Optimization (Dagstuhl Seminar 18081). In Dagstuhl Reports, Volume 8, Issue 2, pp. 64-87, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Article{bonami_et_al:DagRep.8.2.64,
  author =	{Bonami, Pierre and Gleixner, Ambros M. and Linderoth, Jeff and Misener, Ruth},
  title =	{{Designing and Implementing Algorithms for Mixed-Integer Nonlinear Optimization (Dagstuhl Seminar 18081)}},
  pages =	{64--87},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2018},
  volume =	{8},
  number =	{2},
  editor =	{Bonami, Pierre and Gleixner, Ambros M. and Linderoth, Jeff and Misener, Ruth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.8.2.64},
  URN =		{urn:nbn:de:0030-drops-92909},
  doi =		{10.4230/DagRep.8.2.64},
  annote =	{Keywords: Complexity, Mathematical optimization, Mathematical software, Mixed-integer optimization, Nonlinear optimization, Numerical issues, Optimization algorithms}
}
  • Refine by Author
  • 1 Berthold, Timo
  • 1 Bonami, Pierre
  • 1 Gleixner, Ambros
  • 1 Gleixner, Ambros M.
  • 1 Linderoth, Jeff
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Solvers
  • 1 Theory of computation → Discrete optimization

  • Refine by Keyword
  • 1 Complexity
  • 1 Integer programming
  • 1 Mathematical optimization
  • 1 Mathematical software
  • 1 Mixed-integer optimization
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2018
  • 1 2023

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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact