Lagrangian bounds from decision diagrams

Authors: David Bergman Andre A Cire WillemJan van Hoeve

Publish Date: 2015/04/21

Volume: 20, Issue: 3, Pages: 346-361

PDF Link

Abstract

Relaxed decision diagrams have recently been used in constraint programming to improve constraint propagation and optimization reasoning In most applications however a decision diagram is compiled with respect to a single combinatorial structure We propose to expand this representation by incorporating additional constraints in the decision diagram via a Lagrangian relaxation With this generic approach we can obtain stronger bounds from the same decision diagram while the associated costbased filtering allows for further refining the relaxation Experimental results on the traveling salesman problem with time windows show that the improved Lagrangian bounds can drastically reduce solution times

Keywords: