Local Rapid Learning for integer programs

Timo Berthold; Peter J. Stuckey; Jakob Witzig

doi:10.1007/978-3-030-19212-9_5

Local Rapid Learning for integer programs

Timo Berthold
, Peter J. Stuckey
, Jakob Witzig

Department of Data Science & AI

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

5 Citations (Scopus)

Abstract

Conflict learning algorithms are an important component of modern MIP and CP solvers. But strong conflict information is typically gained by depth-first search. While this is the natural mode for CP solving, it is not for MIP solving. Rapid Learning is a hybrid CP/MIP approach where CP search is appliedat the root to learn information to support the remaining MIP solve. This has been demonstrated to be beneficial for binary programs. In this paper, we extend the idea of Rapid Learning to integer programs, where not all variables are restricted to the domain and rather than just running a rapid CP search at the root, we will apply it repeatedly at local search nodes within the MIP search tree. To do so efficiently, we present six heuristic criteria to predict the chance for local Rapid Learning to be successful. Our computational experiments indicate that our extended Rapid Learning algorithm significantly speeds up MIP search and is particularly beneficial on highly dual degenerate problems.

Original language	English
Title of host publication	Integration of Constraint Programming, Artificial Intelligence, and Operations Research
Subtitle of host publication	16th International Conference, CPAIOR 2019 Thessaloniki, Greece, June 4–7, 2019 Proceedings
Editors	Louis-Martin Rousseau, Kostas Stergiou
Place of Publication	Cham Switzerland
Publisher	Springer
Pages	67-83
Number of pages	17
ISBN (Electronic)	9783030192129
ISBN (Print)	9783030192112
DOIs	https://doi.org/10.1007/978-3-030-19212-9_5
Publication status	Published - 2019
Event	International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2019 - Thessaloniki, Greece Duration: 4 Jun 2019 → 7 Jun 2019 Conference number: 16th https://cpaior2019.uowm.gr/ (Conference website) https://link.springer.com/book/10.1007/978-3-030-19212-9 (Proceedings)

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	11494
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2019
Abbreviated title	CPAIOR 2019
Country/Territory	Greece
City	Thessaloniki
Period	4/06/19 → 7/06/19
Internet address	https://cpaior2019.uowm.gr/ (Conference website) https://link.springer.com/book/10.1007/978-3-030-19212-9 (Proceedings)

Access to Document

10.1007/978-3-030-19212-9_5

Cite this

Berthold, T., Stuckey, P. J., & Witzig, J. (2019). Local Rapid Learning for integer programs. In L.-M. Rousseau, & K. Stergiou (Eds.), Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 16th International Conference, CPAIOR 2019 Thessaloniki, Greece, June 4–7, 2019 Proceedings (pp. 67-83). (Lecture Notes in Computer Science ; Vol. 11494). Springer. https://doi.org/10.1007/978-3-030-19212-9_5

Berthold, Timo ; Stuckey, Peter J. ; Witzig, Jakob. / Local Rapid Learning for integer programs. Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 16th International Conference, CPAIOR 2019 Thessaloniki, Greece, June 4–7, 2019 Proceedings. editor / Louis-Martin Rousseau ; Kostas Stergiou. Cham Switzerland : Springer, 2019. pp. 67-83 (Lecture Notes in Computer Science ).

@inproceedings{c041eb71e37e445880764199d0c9e3da,

title = "Local Rapid Learning for integer programs",

abstract = "Conflict learning algorithms are an important component of modern MIP and CP solvers. But strong conflict information is typically gained by depth-first search. While this is the natural mode for CP solving, it is not for MIP solving. Rapid Learning is a hybrid CP/MIP approach where CP search is appliedat the root to learn information to support the remaining MIP solve. This has been demonstrated to be beneficial for binary programs. In this paper, we extend the idea of Rapid Learning to integer programs, where not all variables are restricted to the domain and rather than just running a rapid CP search at the root, we will apply it repeatedly at local search nodes within the MIP search tree. To do so efficiently, we present six heuristic criteria to predict the chance for local Rapid Learning to be successful. Our computational experiments indicate that our extended Rapid Learning algorithm significantly speeds up MIP search and is particularly beneficial on highly dual degenerate problems.",

author = "Timo Berthold and Stuckey, \{Peter J.\} and Jakob Witzig",

year = "2019",

doi = "10.1007/978-3-030-19212-9\_5",

language = "English",

isbn = "9783030192112",

series = "Lecture Notes in Computer Science ",

publisher = "Springer",

pages = "67--83",

editor = "Louis-Martin Rousseau and Kostas Stergiou",

booktitle = "Integration of Constraint Programming, Artificial Intelligence, and Operations Research",

address = "Switzerland",

note = "International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2019<br/>, CPAIOR 2019 ; Conference date: 04-06-2019 Through 07-06-2019",

url = "https://cpaior2019.uowm.gr/, https://link.springer.com/book/10.1007/978-3-030-19212-9",

}

Berthold, T, Stuckey, PJ & Witzig, J 2019, Local Rapid Learning for integer programs. in L-M Rousseau & K Stergiou (eds), Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 16th International Conference, CPAIOR 2019 Thessaloniki, Greece, June 4–7, 2019 Proceedings. Lecture Notes in Computer Science , vol. 11494, Springer, Cham Switzerland, pp. 67-83, International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2019
, Thessaloniki, Greece, 4/06/19. https://doi.org/10.1007/978-3-030-19212-9_5

Local Rapid Learning for integer programs. / Berthold, Timo; Stuckey, Peter J.; Witzig, Jakob.
Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 16th International Conference, CPAIOR 2019 Thessaloniki, Greece, June 4–7, 2019 Proceedings. ed. / Louis-Martin Rousseau; Kostas Stergiou. Cham Switzerland: Springer, 2019. p. 67-83 (Lecture Notes in Computer Science ; Vol. 11494).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - Local Rapid Learning for integer programs

AU - Berthold, Timo

AU - Stuckey, Peter J.

AU - Witzig, Jakob

N1 - Conference code: 16th

PY - 2019

Y1 - 2019

N2 - Conflict learning algorithms are an important component of modern MIP and CP solvers. But strong conflict information is typically gained by depth-first search. While this is the natural mode for CP solving, it is not for MIP solving. Rapid Learning is a hybrid CP/MIP approach where CP search is appliedat the root to learn information to support the remaining MIP solve. This has been demonstrated to be beneficial for binary programs. In this paper, we extend the idea of Rapid Learning to integer programs, where not all variables are restricted to the domain and rather than just running a rapid CP search at the root, we will apply it repeatedly at local search nodes within the MIP search tree. To do so efficiently, we present six heuristic criteria to predict the chance for local Rapid Learning to be successful. Our computational experiments indicate that our extended Rapid Learning algorithm significantly speeds up MIP search and is particularly beneficial on highly dual degenerate problems.

AB - Conflict learning algorithms are an important component of modern MIP and CP solvers. But strong conflict information is typically gained by depth-first search. While this is the natural mode for CP solving, it is not for MIP solving. Rapid Learning is a hybrid CP/MIP approach where CP search is appliedat the root to learn information to support the remaining MIP solve. This has been demonstrated to be beneficial for binary programs. In this paper, we extend the idea of Rapid Learning to integer programs, where not all variables are restricted to the domain and rather than just running a rapid CP search at the root, we will apply it repeatedly at local search nodes within the MIP search tree. To do so efficiently, we present six heuristic criteria to predict the chance for local Rapid Learning to be successful. Our computational experiments indicate that our extended Rapid Learning algorithm significantly speeds up MIP search and is particularly beneficial on highly dual degenerate problems.

UR - https://www.scopus.com/pages/publications/85066860163

U2 - 10.1007/978-3-030-19212-9_5

DO - 10.1007/978-3-030-19212-9_5

M3 - Conference Paper

AN - SCOPUS:85066860163

SN - 9783030192112

T3 - Lecture Notes in Computer Science

SP - 67

EP - 83

BT - Integration of Constraint Programming, Artificial Intelligence, and Operations Research

A2 - Rousseau, Louis-Martin

A2 - Stergiou, Kostas

PB - Springer

CY - Cham Switzerland

T2 - International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2019<br/>

Y2 - 4 June 2019 through 7 June 2019

ER -

Berthold T, Stuckey PJ, Witzig J. Local Rapid Learning for integer programs. In Rousseau LM, Stergiou K, editors, Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 16th International Conference, CPAIOR 2019 Thessaloniki, Greece, June 4–7, 2019 Proceedings. Cham Switzerland: Springer. 2019. p. 67-83. (Lecture Notes in Computer Science ). doi: 10.1007/978-3-030-19212-9_5

Local Rapid Learning for integer programs

Abstract

Publication series

Conference

Access to Document

Other files and links

Cite this