Local Rapid Learning for integer programs

Timo Berthold, Peter J. Stuckey, Jakob Witzig

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

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 languageEnglish
Title of host publicationIntegration of Constraint Programming, Artificial Intelligence, and Operations Research
Subtitle of host publication16th International Conference, CPAIOR 2019 Thessaloniki, Greece, June 4–7, 2019 Proceedings
EditorsLouis-Martin Rousseau, Kostas Stergiou
Place of PublicationCham Switzerland
PublisherSpringer
Pages67-83
Number of pages17
ISBN (Electronic)9783030192129
ISBN (Print)9783030192112
DOIs
Publication statusPublished - 2019
EventInternational Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2019
- Thessaloniki, Greece
Duration: 4 Jun 20197 Jun 2019
Conference number: 16th
https://cpaior2019.uowm.gr/
https://cpaior2019.uowm.gr

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume11494
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2019
Abbreviated titleCPAIOR 2019
CountryGreece
CityThessaloniki
Period4/06/197/06/19
Internet address

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