Margaux SCHMIED

Efficient Implementation of the Global Cardinality Constraint with Costs

Margaux SCHMIED, Jean-Charles REGIN

CP 2024

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.

Jouer avec des Cryptarithmes en Programmation par Contraintes

Arnaud MALAPERT, Margaux SCHMIED, Davide FISSORE, Marie PELLEAU, Ambre PICARD MARCHETTO

JFPC 2023

Un cryptarithme est un casse-tête mathématique et logique dans lequel des mots forment une équation où les lettres représentent des chiffres à déterminer dans une base donnée. Ce problème est populaire en mathématiques récréatives, dans l’enseignement, et en programmation par contraintes. Nous proposons une approche générale, efficace et simple d’utilisation pour résoudre ce problème NP-Complet. La suite naturelle est une approche hiérarchique pour leur génération. Les évaluations expérimentales ont engendré une vaste collection, variée et remarquable.

• Visit to Christophe Lecoutre, at CRIL in Lens, France
• "Assignment problem with costs in constraint programming", presentation, Dialogue Objectif Ressources I3S/CNRS
• "Improving cost global cardinality constraint filtering algorithm", poster, seminar 3IA

• "Efficient search for upper bounds for assignment problems with costs", presentation, C&A I3S team
• "Constraint First : A New MDD-based Model To Generate Sentences Under Constraints", presentation, Dialogue Objectif Ressources I3S/CNRS

• Selection committee for STIC doctoral school thesis grants
• I3S laboratory life committee
• Association of doctoral students of the STIC doctoral school

• CPAIOR 2023 conference organising committee
• I3S laboratory life committee
• Association of doctoral students of the STIC doctoral school

Internship

• Sayf Eddine HALMI, 4th year of a computer engineering school (Polytech) - equivalent to master 1, 4 months, "Modeling and improving large-scale sudoku solving"
• Justin DITER, 2nd year of computer science degree, 2 months, "Integer array compression"
• Karl Alwyn SOP DJONKAM, 1st year of master of computer science, 2 months, "Designing and building an ia for starcraft 2"

• Databases, 24h, 1st year of master maths
• Algorithms and Complexity, 30h, 4th year of a computer engineering school (Polytech) - equivalent to master 1
• Engineering assistant internship, 10h, 4th year of a computer engineering school (Polytech) - equivalent to master 1