Skip navigation
Skip navigation

Constraint-based lagrangian relaxation

Fontaine, Daniel; Michel, Laurent; Van Hentenryck, Pascal

Description

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...[Show more]

dc.contributor.authorFontaine, Daniel
dc.contributor.authorMichel, Laurent
dc.contributor.authorVan Hentenryck, Pascal
dc.coverage.spatialLyon France
dc.date.accessioned2015-12-13T22:31:31Z
dc.date.createdSeptember 8-12 2014
dc.identifier.isbn9783319104270
dc.identifier.urihttp://hdl.handle.net/1885/75287
dc.description.abstractThis 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.
dc.publisherSpringer Verlag
dc.relation.ispartofseries20th International Conference on the Principles and Practice of Constraint Programming, CP 2014
dc.sourceLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
dc.titleConstraint-based lagrangian relaxation
dc.typeConference paper
local.description.notesImported from ARIES
local.description.refereedYes
dc.date.issued2014
local.identifier.absfor080200 - COMPUTATION THEORY AND MATHEMATICS
local.identifier.ariespublicationU3488905xPUB4554
local.type.statusPublished Version
local.contributor.affiliationFontaine, Daniel, University of Connecticut
local.contributor.affiliationMichel, Laurent, University of Connecticut
local.contributor.affiliationVan Hentenryck, Pascal, College of Engineering and Computer Science, ANU
local.description.embargo2037-12-31
local.bibliographicCitation.startpage324
local.bibliographicCitation.lastpage339
local.identifier.doi10.1007/978-3-319-10428-7_25
dc.date.updated2015-12-11T09:01:12Z
local.identifier.scopusID2-s2.0-84906232704
CollectionsANU Research Publications

Download

File Description SizeFormat Image
01_Fontaine_Constraint-based_lagrangian_2014.pdf311.32 kBAdobe PDF    Request a copy


Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  19 May 2020/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator