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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

The Theory of Lagrangian Filtering Zones: A Case Study on the Knapsack Constraint

  • Frédéric Berthiaume,
  • Claude-Guy Quimper

摘要

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.