Rapid learning for binary programs

Timo Berthold; Thibaut Feydy; Peter J. Stuckey

doi:10.1007/978-3-642-13520-0_8

Rapid learning for binary programs

Timo Berthold, Thibaut Feydy, Peter J. Stuckey

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

11 Citations (Scopus)

Abstract

Learning during search allows solvers for discrete optimization problems to remember parts of the search that they have already performed and avoid revisiting redundant parts. Learning approaches pioneered by the SAT and CP communities have been successfully incorporated into the SCIP constraint integer programming platform. In this paper we show that performing a heuristic constraint programming search during root node processing of a binary program can rapidly learn useful nogoods, bound changes, primal solutions, and branching statistics that improve the remaining IP search.

Original language	English
Title of host publication	Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems - 7th International Conference, CPAIOR 2010, Proceedings
Publisher	Springer
Pages	51-55
Number of pages	5
ISBN (Print)	3642135196, 9783642135194
DOIs	https://doi.org/10.1007/978-3-642-13520-0_8
Publication status	Published - 16 Aug 2010
Externally published	Yes
Event	International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2010 - Bologna, Italy Duration: 16 Jun 2010 → 18 Jun 2010 Conference number: 7th https://link.springer.com/book/10.1007/978-3-642-13520-0 (Proceedings)

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	6140 LNCS
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 2010
Abbreviated title	CPAIOR 2010
Country/Territory	Italy
City	Bologna
Period	16/06/10 → 18/06/10
Internet address	https://link.springer.com/book/10.1007/978-3-642-13520-0 (Proceedings)

Access to Document

10.1007/978-3-642-13520-0_8

Cite this

Berthold, T., Feydy, T., & Stuckey, P. J. (2010). Rapid learning for binary programs. In Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems - 7th International Conference, CPAIOR 2010, Proceedings (pp. 51-55). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6140 LNCS). Springer. https://doi.org/10.1007/978-3-642-13520-0_8

Berthold, Timo ; Feydy, Thibaut ; Stuckey, Peter J. / Rapid learning for binary programs. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems - 7th International Conference, CPAIOR 2010, Proceedings. Springer, 2010. pp. 51-55 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{fdf667da523442bfb0423908a2dfad79,

title = "Rapid learning for binary programs",

abstract = "Learning during search allows solvers for discrete optimization problems to remember parts of the search that they have already performed and avoid revisiting redundant parts. Learning approaches pioneered by the SAT and CP communities have been successfully incorporated into the SCIP constraint integer programming platform. In this paper we show that performing a heuristic constraint programming search during root node processing of a binary program can rapidly learn useful nogoods, bound changes, primal solutions, and branching statistics that improve the remaining IP search.",

author = "Timo Berthold and Thibaut Feydy and Stuckey, {Peter J.}",

year = "2010",

month = aug,

day = "16",

doi = "10.1007/978-3-642-13520-0_8",

language = "English",

isbn = "3642135196",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "51--55",

booktitle = "Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems - 7th International Conference, CPAIOR 2010, Proceedings",

note = "International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2010, CPAIOR 2010 ; Conference date: 16-06-2010 Through 18-06-2010",

url = "https://link.springer.com/book/10.1007/978-3-642-13520-0",

}

Berthold, T, Feydy, T & Stuckey, PJ 2010, Rapid learning for binary programs. in Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems - 7th International Conference, CPAIOR 2010, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6140 LNCS, Springer, pp. 51-55, International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2010, Bologna, Italy, 16/06/10. https://doi.org/10.1007/978-3-642-13520-0_8

Rapid learning for binary programs. / Berthold, Timo; Feydy, Thibaut; Stuckey, Peter J.
Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems - 7th International Conference, CPAIOR 2010, Proceedings. Springer, 2010. p. 51-55 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6140 LNCS).

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

TY - GEN

T1 - Rapid learning for binary programs

AU - Berthold, Timo

AU - Feydy, Thibaut

AU - Stuckey, Peter J.

N1 - Conference code: 7th

PY - 2010/8/16

Y1 - 2010/8/16

N2 - Learning during search allows solvers for discrete optimization problems to remember parts of the search that they have already performed and avoid revisiting redundant parts. Learning approaches pioneered by the SAT and CP communities have been successfully incorporated into the SCIP constraint integer programming platform. In this paper we show that performing a heuristic constraint programming search during root node processing of a binary program can rapidly learn useful nogoods, bound changes, primal solutions, and branching statistics that improve the remaining IP search.

AB - Learning during search allows solvers for discrete optimization problems to remember parts of the search that they have already performed and avoid revisiting redundant parts. Learning approaches pioneered by the SAT and CP communities have been successfully incorporated into the SCIP constraint integer programming platform. In this paper we show that performing a heuristic constraint programming search during root node processing of a binary program can rapidly learn useful nogoods, bound changes, primal solutions, and branching statistics that improve the remaining IP search.

UR - http://www.scopus.com/inward/record.url?scp=77955460519&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-13520-0_8

DO - 10.1007/978-3-642-13520-0_8

M3 - Conference Paper

AN - SCOPUS:77955460519

SN - 3642135196

SN - 9783642135194

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 51

EP - 55

BT - Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems - 7th International Conference, CPAIOR 2010, Proceedings

PB - Springer

T2 - International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2010

Y2 - 16 June 2010 through 18 June 2010

ER -

Berthold T, Feydy T, Stuckey PJ. Rapid learning for binary programs. In Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems - 7th International Conference, CPAIOR 2010, Proceedings. Springer. 2010. p. 51-55. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-13520-0_8

Rapid learning for binary programs

Abstract

Publication series

Conference

Access to Document

Other files and links

Cite this