Tags:Global constraint, Lagrangian relaxation and N values

Abstract:

The reduced cost filtering is a technique that consists in filtering a constraint using the reduced cost of a linear program that encodes this constraint. Sellmann [13] shows that while doing a Lagrangian relaxation of a constraint, suboptimal Lagrange multipliers can provide more filtering than optimal ones. Boudreault and Quimper [5] make an algorithm that locally alters the Lagrange multipliers for the WeightedCircuit constraint to enhance filtering and achieve a speedup of 30%. We seek to design an algorithm like Boudreault and Quimper, but for the AtMostNValue constraint. Based on the work done by Cambazard and Fages [6] on this constraint, we use a subgradient algorithm which takes into consideration the reduced cost to boost the Lagrange multipliers in the optimal filtering direction. We test our methods on the dominating queens and the p-median problem. On the first, we record a speed up of 72% on average. On the second, there are three classes of instances. On the first two, we have an average speed up of 33% and 8%. On the hardest class, we find up to 13 better solutions than the previous algorithm on the 30 instances in the class.

Local Alterations of the Lagrange Multipliers for Enhancing the Filtering of the AtMostNValue