The Theory of Lagrangian Filtering Zones: A Case Study on the Knapsack Constraint
摘要
CP-based Lagrangian filtering has proven to be a reliable method for enhancing constraint programming solvers. The general theory lacks a uniform framework to explain many known observations. This paper introduces such a framework, along with theoretical results and illustrations. We show why optimal Lagrange multipliers are not always the most effective for filtering. We propose a strategy to move the Lagrange multipliers away from the optimal one to launch a gradient descent that leads to filtering. This paper presents an application of this framework to the versatile Multidimensional Knapsack constraint. The algorithm is tested on two well-known problems : the multidimensional knapsack problem and the uncapacitated facility location problem. The results show a significant speed up compared to the traditional CP-based Lagrangian filtering method on both problems.