Constraint-based lagrangian relaxation

Daniel Fontaine, L. Laurentmichel, Pascal Van Hentenryck

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

    13 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 languageEnglish
    Title of host publicationPrinciples and Practice of Constraint Programming - 20th International Conference, CP 2014, Proceedings
    PublisherSpringer Verlag
    Pages324-339
    Number of pages16
    ISBN (Print)9783319104270
    DOIs
    Publication statusPublished - 2014
    Event20th International Conference on the Principles and Practice of Constraint Programming, CP 2014 - Lyon, France
    Duration: 8 Sept 201412 Sept 2014

    Publication series

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

    Conference

    Conference20th International Conference on the Principles and Practice of Constraint Programming, CP 2014
    Country/TerritoryFrance
    CityLyon
    Period8/09/1412/09/14

    Fingerprint

    Dive into the research topics of 'Constraint-based lagrangian relaxation'. Together they form a unique fingerprint.

    Cite this