Arc-consistency and linear programming duality: an analysis of reduced cost based filtering - Université Grenoble Alpes Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2022

Arc-consistency and linear programming duality: an analysis of reduced cost based filtering

Résumé

In Constraint Programming (CP), achieving arc-consistency (AC) of a global constraint with costs consists in removing from the domains of the variables all the values that do not belong to any solution whose cost is below a fixed bound. We analyse how linear duality and reduced costs can be used to find all such inconsistent values. In particular, when the constraint has an ideal Linear Programming (LP) formulation, we show that n dual solutions are always enough to achieve AC (where n is the number of variables). This analysis leads to a simple algorithm with n calls to an LP solver to achieve AC, as opposed to the naive approach based on one call for each value of each domain. It extends the work presented in [German et al., 2017] for satisfaction problems and in [Claus et al., 2020] for the specific case of the minimum weighted alldifferent constraint. We propose some answers to the following questions: does there always exists a dual solution that can prove a value consistent/inconsistent ? given a dual solution, how do we know which values are proved consistent/inconsistent ? can we identify simple conditions for a family of dual solutions to ensure arc-consistency ?
Fichier principal
Vignette du fichier
AC_by_ERC.pdf (264.79 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03728504 , version 1 (20-07-2022)

Licence

Paternité

Identifiants

Citer

Guillaume Claus, Hadrien Cambazard, Vincent Jost. Arc-consistency and linear programming duality: an analysis of reduced cost based filtering. 2022. ⟨hal-03728504⟩
23 Consultations
47 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More