Lagrangian decomposition via sub-problem search

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

2 Citations (Scopus)

Abstract

One of the critical issues that affect the efficiency of branch and bound algorithms in Constraint Programming is how strong a bound on the objective function can be inferred at each search node. The stronger the bound that can be inferred, the earlier failed subtrees can be detected, leading to an exponentially smaller search tree. Normal CP solvers are only capable of inferring a bound on the objective function via propagating the problem constraints. Unfortunately, for many problem classes, this does not yield a very strong bound. Recently, Lagrangian decomposition methods have been adapted and applied to Constraint Programming in order to yield stronger bounds on the objective function. While these methods yield some success, they are somewhat limited in the types of problems they can be effectively applied to. In particular, the set of constraints has to be divided into subsets such that each subset can be solved efficiently via a specialized propagator, e.g.,consists of a knapsack problem, or a cost-MDD problem. For many more practical problem classes, such a division of constraints is simply not possible and thus those methods cannot be applied. In this paper, we propose a Lagrangian decomposition method where the sub-problems are solved via search rather than through a specialized propagator. This has the benefit that the method can be applied to a much wider range of problems. We present experiments to show the effectiveness of our method.

Original languageEnglish
Title of host publicationIntegration of AI and OR Techniques in Constraint Programming
Subtitle of host publication13th International Conference, CPAIOR 2016 Banff, AB, Canada, May 29 – June 1, 2016 Proceedings
EditorsClaude-Guy Quimper
Place of PublicationCham Switzerland
PublisherSpringer
Pages65-80
Number of pages16
ISBN (Electronic)9783319339542
ISBN (Print)9783319339535
DOIs
Publication statusPublished - 2016
Externally publishedYes
EventInternational Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2016 - Banff, Canada
Duration: 29 May 20161 Jun 2016
Conference number: 13th
https://symposia.cirrelt.ca/CPAIOR2016/en/home

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume9676
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2016
Abbreviated titleCPAIOR 2016
CountryCanada
CityBanff
Period29/05/161/06/16
Internet address

Cite this

Chu, G., Gange, G., & Stuckey, P. J. (2016). Lagrangian decomposition via sub-problem search. In C-G. Quimper (Ed.), Integration of AI and OR Techniques in Constraint Programming: 13th International Conference, CPAIOR 2016 Banff, AB, Canada, May 29 – June 1, 2016 Proceedings (pp. 65-80). (Lecture Notes in Computer Science ; Vol. 9676). Springer. https://doi.org/10.1007/978-3-319-33954-2_6