# Efficient Implementation of the Global Cardinality Constraint with Costs

arXiv: https://arxiv.org/abs/2502.02688 · HTML: https://mlsanity.com/paper/2502.02688/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 0 of its 21 references that are in the map.
- First posted on arXiv 4 Feb 2025.

## Built on by (most cited first, 1 of 1)

- [Exact Synthetic Populations for Scalable Societal and Market Modeling](https://mlsanity.com/paper/2512.07306/) (2025)

## Abstract (arXiv)

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 can be seen as a preprocessing. It is fast and avoids, in practice, a large number of explicit computations of shortest paths.