Learn to Relax: Integrating 0-1 Integer Linear Programming with Pseudo-Boolean Conflict-Driven Search

Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt

Standard

Learn to Relax : Integrating 0-1 Integer Linear Programming with Pseudo-Boolean Conflict-Driven Search. / Devriendt, Jo; Gleixner, Ambros; Nordström, Jakob.

I: Constraints, Bind 26, 2021, s. 26–55.

Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt

Harvard

Devriendt, J, Gleixner, A & Nordström, J 2021, 'Learn to Relax: Integrating 0-1 Integer Linear Programming with Pseudo-Boolean Conflict-Driven Search', Constraints, bind 26, s. 26–55. https://doi.org/10.1007/s10601-020-09318-x

APA

Devriendt, J., Gleixner, A., & Nordström, J. (2021). Learn to Relax: Integrating 0-1 Integer Linear Programming with Pseudo-Boolean Conflict-Driven Search. Constraints, 26, 26–55. https://doi.org/10.1007/s10601-020-09318-x

Vancouver

Devriendt J, Gleixner A, Nordström J. Learn to Relax: Integrating 0-1 Integer Linear Programming with Pseudo-Boolean Conflict-Driven Search. Constraints. 2021;26:26–55. https://doi.org/10.1007/s10601-020-09318-x

Author

Devriendt, Jo ; Gleixner, Ambros ; Nordström, Jakob. / Learn to Relax : Integrating 0-1 Integer Linear Programming with Pseudo-Boolean Conflict-Driven Search. I: Constraints. 2021 ; Bind 26. s. 26–55.

Bibtex

@article{0818e6207cd74a4cb99cb6b113b02509,
title = "Learn to Relax: Integrating 0-1 Integer Linear Programming with Pseudo-Boolean Conflict-Driven Search",
abstract = "Conflict-driven pseudo-Boolean solvers optimize 0-1 integer linear programs by extending the conflict-driven clause learning (CDCL) paradigm from SAT solving. Though pseudo-Boolean solvers have the potential to be exponentially more efficient than CDCL solvers in theory, in practice they can sometimes get hopelessly stuck even when the linear programming (LP) relaxation is infeasible over the reals. Inspired by mixed integer programming (MIP), we address this problem by interleaving incremental LP solving with cut generation within the conflict-driven pseudo-Boolean search. This hybrid approach, which for the first time combines MIP techniques with full-blown conflict analysis operating directly on linear inequalities using the cutting planes method, significantly improves performance on a wide range of benchmarks, approaching a “best-of-both-worlds” scenario between SAT-style conflict-driven search and MIP-style branch-and-cut.",
author = "Jo Devriendt and Ambros Gleixner and Jakob Nordstr{\"o}m",
year = "2021",
doi = "10.1007/s10601-020-09318-x",
language = "English",
volume = "26",
pages = "26–55",
journal = "Constraints",
issn = "1383-7133",
publisher = "Springer",

}

RIS

TY - JOUR

T1 - Learn to Relax

T2 - Integrating 0-1 Integer Linear Programming with Pseudo-Boolean Conflict-Driven Search

AU - Devriendt, Jo

AU - Gleixner, Ambros

AU - Nordström, Jakob

PY - 2021

Y1 - 2021

N2 - Conflict-driven pseudo-Boolean solvers optimize 0-1 integer linear programs by extending the conflict-driven clause learning (CDCL) paradigm from SAT solving. Though pseudo-Boolean solvers have the potential to be exponentially more efficient than CDCL solvers in theory, in practice they can sometimes get hopelessly stuck even when the linear programming (LP) relaxation is infeasible over the reals. Inspired by mixed integer programming (MIP), we address this problem by interleaving incremental LP solving with cut generation within the conflict-driven pseudo-Boolean search. This hybrid approach, which for the first time combines MIP techniques with full-blown conflict analysis operating directly on linear inequalities using the cutting planes method, significantly improves performance on a wide range of benchmarks, approaching a “best-of-both-worlds” scenario between SAT-style conflict-driven search and MIP-style branch-and-cut.

AB - Conflict-driven pseudo-Boolean solvers optimize 0-1 integer linear programs by extending the conflict-driven clause learning (CDCL) paradigm from SAT solving. Though pseudo-Boolean solvers have the potential to be exponentially more efficient than CDCL solvers in theory, in practice they can sometimes get hopelessly stuck even when the linear programming (LP) relaxation is infeasible over the reals. Inspired by mixed integer programming (MIP), we address this problem by interleaving incremental LP solving with cut generation within the conflict-driven pseudo-Boolean search. This hybrid approach, which for the first time combines MIP techniques with full-blown conflict analysis operating directly on linear inequalities using the cutting planes method, significantly improves performance on a wide range of benchmarks, approaching a “best-of-both-worlds” scenario between SAT-style conflict-driven search and MIP-style branch-and-cut.

U2 - 10.1007/s10601-020-09318-x

DO - 10.1007/s10601-020-09318-x

M3 - Journal article

VL - 26

SP - 26

EP - 55

JO - Constraints

JF - Constraints

SN - 1383-7133

ER -

ID: 255840888