Theoretical Foundations of CP-Based Lagrangian Relaxation

CP-based Lagrangian Relaxation allows us to reason on local substructures while maintaining a global view on an entire optimization problem. While the idea of cost-based filtering with respect to systematically changing objective functions has been around for more than three years now, so far some important observations have not been explained. In this paper, we prove a simple theorem that explains a variety of effects that are encountered in practice, the most counter-intuitive being the fact that suboptimal Lagrangian multipliers can have stronger filtering abilities than optimal ones.