Constraint-based lagrangian relaxation

Daniel Fontaine; L. Laurentmichel; Pascal Van Hentenryck

doi:10.1007/978-3-319-10428-7_25

Constraint-based lagrangian relaxation

Daniel Fontaine, L. Laurentmichel, Pascal Van Hentenryck

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

14 Citations (Scopus)

Abstract

This paper studies how to generalize Lagrangian relaxation to high-level optimization models, including constraint-programming and local search models. It exploits the concepts of constraint violation (typically used in constraint programming and local search) and constraint satisfiability (typically exploited in mathematical programming). The paper considers dual and primal methods, studies their properties, and discusses how they can be implemented in terms of high-level model combinators and algorithmic templates. Experimental results suggest the potential benefits of Lagrangian methods for improving high-level constraint programming and local search models.

Original language	English
Title of host publication	Principles and Practice of Constraint Programming - 20th International Conference, CP 2014, Proceedings
Publisher	Springer Verlag
Pages	324-339
Number of pages	16
ISBN (Print)	9783319104270
DOIs	https://doi.org/10.1007/978-3-319-10428-7_25
Publication status	Published - 2014
Event	20th International Conference on the Principles and Practice of Constraint Programming, CP 2014 - Lyon, France Duration: 8 Sept 2014 → 12 Sept 2014

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8656 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	20th International Conference on the Principles and Practice of Constraint Programming, CP 2014
Country/Territory	France
City	Lyon
Period	8/09/14 → 12/09/14

Access to Document

10.1007/978-3-319-10428-7_25

Cite this

Fontaine, D., Laurentmichel, L., & Van Hentenryck, P. (2014). Constraint-based lagrangian relaxation. In Principles and Practice of Constraint Programming - 20th International Conference, CP 2014, Proceedings (pp. 324-339). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8656 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-10428-7_25

Fontaine, Daniel ; Laurentmichel, L. ; Van Hentenryck, Pascal. / Constraint-based lagrangian relaxation. Principles and Practice of Constraint Programming - 20th International Conference, CP 2014, Proceedings. Springer Verlag, 2014. pp. 324-339 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{4b2fb00ec57d4359a77810235b49f6e3,

title = "Constraint-based lagrangian relaxation",

abstract = "This paper studies how to generalize Lagrangian relaxation to high-level optimization models, including constraint-programming and local search models. It exploits the concepts of constraint violation (typically used in constraint programming and local search) and constraint satisfiability (typically exploited in mathematical programming). The paper considers dual and primal methods, studies their properties, and discusses how they can be implemented in terms of high-level model combinators and algorithmic templates. Experimental results suggest the potential benefits of Lagrangian methods for improving high-level constraint programming and local search models.",

author = "Daniel Fontaine and L. Laurentmichel and {Van Hentenryck}, Pascal",

year = "2014",

doi = "10.1007/978-3-319-10428-7_25",

language = "English",

isbn = "9783319104270",

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

publisher = "Springer Verlag",

pages = "324--339",

booktitle = "Principles and Practice of Constraint Programming - 20th International Conference, CP 2014, Proceedings",

address = "Germany",

note = "20th International Conference on the Principles and Practice of Constraint Programming, CP 2014 ; Conference date: 08-09-2014 Through 12-09-2014",

}

Fontaine, D, Laurentmichel, L & Van Hentenryck, P 2014, Constraint-based lagrangian relaxation. in Principles and Practice of Constraint Programming - 20th International Conference, CP 2014, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8656 LNCS, Springer Verlag, pp. 324-339, 20th International Conference on the Principles and Practice of Constraint Programming, CP 2014, Lyon, France, 8/09/14. https://doi.org/10.1007/978-3-319-10428-7_25

Constraint-based lagrangian relaxation. / Fontaine, Daniel; Laurentmichel, L.; Van Hentenryck, Pascal.
Principles and Practice of Constraint Programming - 20th International Conference, CP 2014, Proceedings. Springer Verlag, 2014. p. 324-339 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8656 LNCS).

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

TY - GEN

T1 - Constraint-based lagrangian relaxation

AU - Fontaine, Daniel

AU - Laurentmichel, L.

AU - Van Hentenryck, Pascal

PY - 2014

Y1 - 2014

N2 - This paper studies how to generalize Lagrangian relaxation to high-level optimization models, including constraint-programming and local search models. It exploits the concepts of constraint violation (typically used in constraint programming and local search) and constraint satisfiability (typically exploited in mathematical programming). The paper considers dual and primal methods, studies their properties, and discusses how they can be implemented in terms of high-level model combinators and algorithmic templates. Experimental results suggest the potential benefits of Lagrangian methods for improving high-level constraint programming and local search models.

AB - This paper studies how to generalize Lagrangian relaxation to high-level optimization models, including constraint-programming and local search models. It exploits the concepts of constraint violation (typically used in constraint programming and local search) and constraint satisfiability (typically exploited in mathematical programming). The paper considers dual and primal methods, studies their properties, and discusses how they can be implemented in terms of high-level model combinators and algorithmic templates. Experimental results suggest the potential benefits of Lagrangian methods for improving high-level constraint programming and local search models.

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

U2 - 10.1007/978-3-319-10428-7_25

DO - 10.1007/978-3-319-10428-7_25

M3 - Conference contribution

SN - 9783319104270

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

SP - 324

EP - 339

BT - Principles and Practice of Constraint Programming - 20th International Conference, CP 2014, Proceedings

PB - Springer Verlag

T2 - 20th International Conference on the Principles and Practice of Constraint Programming, CP 2014

Y2 - 8 September 2014 through 12 September 2014

ER -

Fontaine D, Laurentmichel L, Van Hentenryck P. Constraint-based lagrangian relaxation. In Principles and Practice of Constraint Programming - 20th International Conference, CP 2014, Proceedings. Springer Verlag. 2014. p. 324-339. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-10428-7_25

Constraint-based lagrangian relaxation

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this