Core-guided model reformulation

Kevin Leo; Graeme Gange; Maria Garcia De La Banda; Mark Wallace

doi:10.1007/978-3-030-58475-7_26

Core-guided model reformulation

Kevin Leo, Graeme Gange, Maria Garcia De La Banda, Mark Wallace

Department of Data Science & AI

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

1 Citation (Scopus)

Abstract

Constraint propagation and SAT solvers often underperform when dealing with optimisation problems that have an additive (or separable) objective function. The core-guided search introduced by MaxSAT solvers can overcome this weakness by detecting and exploiting cores: subsets of the objective components that cannot collectively take their lower bounds. This paper shows how to use the information collected during core-guided search, to reformulate the objective function for an entire class of problems (those captured by the problem model). The resulting (currently manual) method is examined on several case studies, with very promising results.

Original language	English
Title of host publication	Principles and Practice of Constraint Programming
Subtitle of host publication	26th International Conference, CP 2020 Louvain-la-Neuve, Belgium, September 7–11, 2020 Proceedings
Editors	Helmut Simonis
Place of Publication	Cham Switzerland
Publisher	Springer
Pages	445-461
Number of pages	17
ISBN (Electronic)	9783030584757
ISBN (Print)	9783030584740
DOIs	https://doi.org/10.1007/978-3-030-58475-7_26
Publication status	Published - 2020
Event	International Conference on Principles and Practice of Constraint Programming 2020 - Louvain-la-Neuve, Belgium Duration: 7 Sept 2020 → 11 Sept 2020 Conference number: 26th https://link.springer.com/book/10.1007/978-3-030-58475-7 (Proceedings) https://cp2020.a4cp.org (Website)

Publication series

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

Conference

Conference	International Conference on Principles and Practice of Constraint Programming 2020
Abbreviated title	CP2020
Country/Territory	Belgium
City	Louvain-la-Neuve
Period	7/09/20 → 11/09/20
Internet address	https://link.springer.com/book/10.1007/978-3-030-58475-7 (Proceedings) https://cp2020.a4cp.org (Website)

Access to Document

10.1007/978-3-030-58475-7_26

321976982-oaAccepted author manuscript, 598 KB
321976982-oaFinal published version, 420 KB

Cite this

Leo, K., Gange, G., Garcia De La Banda, M., & Wallace, M. (2020). Core-guided model reformulation. In H. Simonis (Ed.), Principles and Practice of Constraint Programming : 26th International Conference, CP 2020 Louvain-la-Neuve, Belgium, September 7–11, 2020 Proceedings (pp. 445-461). (Lecture Notes in Computer Science ; Vol. 12333 ). Springer. https://doi.org/10.1007/978-3-030-58475-7_26

@inproceedings{6995a0ef6665442c9127e67b8ec413a4,

title = "Core-guided model reformulation",

abstract = "Constraint propagation and SAT solvers often underperform when dealing with optimisation problems that have an additive (or separable) objective function. The core-guided search introduced by MaxSAT solvers can overcome this weakness by detecting and exploiting cores: subsets of the objective components that cannot collectively take their lower bounds. This paper shows how to use the information collected during core-guided search, to reformulate the objective function for an entire class of problems (those captured by the problem model). The resulting (currently manual) method is examined on several case studies, with very promising results.",

author = "Kevin Leo and Graeme Gange and {Garcia De La Banda}, Maria and Mark Wallace",

year = "2020",

doi = "10.1007/978-3-030-58475-7_26",

language = "English",

isbn = "9783030584740",

series = "Lecture Notes in Computer Science ",

publisher = "Springer",

pages = "445--461",

editor = "Helmut Simonis",

booktitle = "Principles and Practice of Constraint Programming",

note = "International Conference on Principles and Practice of Constraint Programming 2020, CP2020 ; Conference date: 07-09-2020 Through 11-09-2020",

url = "https://link.springer.com/book/10.1007/978-3-030-58475-7, https://cp2020.a4cp.org",

}

Leo, K, Gange, G, Garcia De La Banda, M & Wallace, M 2020, Core-guided model reformulation. in H Simonis (ed.), Principles and Practice of Constraint Programming : 26th International Conference, CP 2020 Louvain-la-Neuve, Belgium, September 7–11, 2020 Proceedings. Lecture Notes in Computer Science , vol. 12333 , Springer, Cham Switzerland, pp. 445-461, International Conference on Principles and Practice of Constraint Programming 2020, Louvain-la-Neuve, Belgium, 7/09/20. https://doi.org/10.1007/978-3-030-58475-7_26

Core-guided model reformulation. / Leo, Kevin; Gange, Graeme; Garcia De La Banda, Maria et al.
Principles and Practice of Constraint Programming : 26th International Conference, CP 2020 Louvain-la-Neuve, Belgium, September 7–11, 2020 Proceedings. ed. / Helmut Simonis. Cham Switzerland: Springer, 2020. p. 445-461 (Lecture Notes in Computer Science ; Vol. 12333 ).

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

TY - GEN

T1 - Core-guided model reformulation

AU - Leo, Kevin

AU - Gange, Graeme

AU - Garcia De La Banda, Maria

AU - Wallace, Mark

N1 - Conference code: 26th

PY - 2020

Y1 - 2020

N2 - Constraint propagation and SAT solvers often underperform when dealing with optimisation problems that have an additive (or separable) objective function. The core-guided search introduced by MaxSAT solvers can overcome this weakness by detecting and exploiting cores: subsets of the objective components that cannot collectively take their lower bounds. This paper shows how to use the information collected during core-guided search, to reformulate the objective function for an entire class of problems (those captured by the problem model). The resulting (currently manual) method is examined on several case studies, with very promising results.

AB - Constraint propagation and SAT solvers often underperform when dealing with optimisation problems that have an additive (or separable) objective function. The core-guided search introduced by MaxSAT solvers can overcome this weakness by detecting and exploiting cores: subsets of the objective components that cannot collectively take their lower bounds. This paper shows how to use the information collected during core-guided search, to reformulate the objective function for an entire class of problems (those captured by the problem model). The resulting (currently manual) method is examined on several case studies, with very promising results.

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

U2 - 10.1007/978-3-030-58475-7_26

DO - 10.1007/978-3-030-58475-7_26

M3 - Conference Paper

AN - SCOPUS:85091319936

SN - 9783030584740

T3 - Lecture Notes in Computer Science

SP - 445

EP - 461

BT - Principles and Practice of Constraint Programming

A2 - Simonis, Helmut

PB - Springer

CY - Cham Switzerland

T2 - International Conference on Principles and Practice of Constraint Programming 2020

Y2 - 7 September 2020 through 11 September 2020

ER -

Leo K, Gange G, Garcia De La Banda M , Wallace M. Core-guided model reformulation. In Simonis H, editor, Principles and Practice of Constraint Programming : 26th International Conference, CP 2020 Louvain-la-Neuve, Belgium, September 7–11, 2020 Proceedings. Cham Switzerland: Springer. 2020. p. 445-461. (Lecture Notes in Computer Science ). doi: 10.1007/978-3-030-58475-7_26

Core-guided model reformulation

Abstract

Publication series

Conference

Access to Document

Other files and links

Cite this