Conference Proceedings

Lagrangian Decomposition via Sub-problem Search

G Chu, G Gange, PJ Stuckey, C-G Quimper (ed.)

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Springer International Publishing | Published : 2016


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. ..

View full abstract