Item


Efficient Implementation of the Global Cardinality Constraint with Costs

Margaux Schmied from the University of Côte d’Azur, France, tells us that the success of Constraint Programming relies partly on the global constraints and implementation of the associated filtering algorithms. Recently, new ideas emerged to improve these implementations in practice, especially regarding the all different constraint. In this paper, we consider the cardinality constraint with costs. The cardinality constraint is a generalization of the all different constraint that specifies the number of times each value must be taken by a given set of variables in a solution. The version with costs introduces an assignment cost and bounds the total sum of assignment costs. The arc consistency filtering algorithm of this constraint is difficult to use in practice, as it systematically searches for many shortest paths. We propose a new approach that works with upper bounds on shortest paths based on landmarks. This approach is fast and avoids, in practice, a large number of explicit computations of shortest paths

7768.mp4 7768.mp3

Universitat de Girona. Departament d’Informàtica, Matemàtica Aplicada i Estadística

Other contributions: Universitat de Girona. Departament d’Informàtica, Matemàtica Aplicada i Estadística
Author: Schmied, Margaux
Régin, Jean-Charles
Date: 2024 September 3
Abstract: Margaux Schmied from the University of Côte d’Azur, France, tells us that the success of Constraint Programming relies partly on the global constraints and implementation of the associated filtering algorithms. Recently, new ideas emerged to improve these implementations in practice, especially regarding the all different constraint. In this paper, we consider the cardinality constraint with costs. The cardinality constraint is a generalization of the all different constraint that specifies the number of times each value must be taken by a given set of variables in a solution. The version with costs introduces an assignment cost and bounds the total sum of assignment costs. The arc consistency filtering algorithm of this constraint is difficult to use in practice, as it systematically searches for many shortest paths. We propose a new approach that works with upper bounds on shortest paths based on landmarks. This approach is fast and avoids, in practice, a large number of explicit computations of shortest paths
7768.mp4 7768.mp3
Format: audio/mpeg
video/mp4
Document access: http://hdl.handle.net/10256.1/7768
Language: eng
Publisher: Universitat de Girona. Departament d’Informàtica, Matemàtica Aplicada i Estadística
Collection: 30th International Conference on Principles and Practice of Constraint Programming
Rights: Attribution-NonCommercial-ShareAlike 4.0 International
Rights URI: http://creativecommons.org/licenses/by-nc-sa/4.0/
Subject: Programació per restriccions (Informàtica) -- Congressos
Constraint programming (Computer science) -- Congresses
Title: Efficient Implementation of the Global Cardinality Constraint with Costs
Type: info:eu-repo/semantics/lecture
Repository: DUGiMedia

Subjects

Authors