Margaux SCHMIED

The Distance Constraint on Sequence Variable

Margaux Schmied, Augustin Delecluse, Pierre Schaus, Jean-Charles Régin

CP 26

Insertion sequence variables have recently been introduced as a computational domain for modeling routing and sequencing problems in constraint programming. Typically, search heuristics guide the insertion process of new nodes into a partial growing path, while constraints eliminate infeasible insertions. This paper investigates filtering for the (minimum) distance constraint over insertion sequence variables. This global constraint links a sequence to a distance variable based on a given distance matrix. So far, only a simple filtering algorithm has been proposed, which considers the partial path but ignores mandatory nodes. Our contribution is to introduce stronger lower bounds that also take mandatory nodes into account. These bounds further enable the derivation of additional filtering rules for node insertions. An experimental evaluation on the \emph{TourMustSee} problem shows that the proposed filtering rules significantly reduce the search space compared to the existing filtering approach.

Cryptarithmetic Playtime

Arnaud Malapert, Marie Pelleau, Margaux Schmied, Davide Fissore

ICTAI 25

A cryptarithm is a mathematical and logical puzzle in which words form an equation where the letters represent numbers to be determined in a given base. This problem is popular in recreational mathematics, education, and constraint programming. We propose a general, efficient and easy-to-use approach to solve this NP-Complete problem, as well as a hierarchical approach for their generation. The experimental evaluation has generated a large, diverse, and remarkable collection of new cryptarithms.

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.

Filtrage de la contrainte de distance pour les variables séquences

Margaux Schmied, Augustin Delecluse, Pierre Schaus, Jean-Charles Régin

JFPC 2026

Les variables séquence offrent un cadre compact pour modéliser les problèmes de routage et d’ordonnancement en programmation par contraintes, en construisant les solutions par insertions successives de nœuds dans une séquence partielle. Nous étudions la propagation d’une contrainte de distance sur ces variables et proposons de nouvelles bornes inférieures admissibles sur le coût de toute extension réalisable. Ces bornes, issues de relaxations du processus d’insertion, permettent de détecter et d’éliminer les insertions irréalisables. Des expériences sur le problème du voyageur de commerce avec fenêtres de temps et collecte de prix montrent que ces règles de filtrage réduisent significativement l’espace de recherche par rapport aux méthodes existantes.

Amélioration de la contrainte globale de cardinalité avec coûts par l’introduction de points de repère

Margaux SCHMIED, Jean-Charles REGIN

JFPC 2025

Le succès de la programmation par contraintes repose en partie sur l’efficacité des contraintes globales et de leurs algorithmes de filtrage. Nous étudions ici la contrainte globale de cardinalité avec coûts, qui généralise la contrainte de différence en limitant le nombre d’affectations par valeur et en imposant une contrainte sur le coût des affectations. L’algorithme classique de filtrage repose sur le calcul systématique de plus courts chemins, ce qui le rend coûteux en pratique. Nous proposons une approche plus rapide, fondée sur des bornes supérieures obtenues via des points de repère (landmarks en anglais), réduisant ainsi significativement les calculs explicites nécessaires. Les expériences montrent que, dans le meilleur des cas, elle peut être en moyenne 57 fois plus rapide.

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.

• Best Paper Award, ICTAI 2025

• Visit to Pierre Schaus during 5 weeks, at ICTEAM Université Catholique de Louvain-La-Neuve, Belgium
• "Solver and Generator of Cryptarithm Using Constraint Programming", presentation, 3IA
• Participation to DM une scientifique

• "Efficient Algorithms for Cost-based Assignment Problems", presentation, workshop SKAIOR
• Visit to Pierre Schaus during 4 weeks, at ICTEAM Université Catholique de Louvain-La-Neuve, Belgium
• "Improved resolution of cost-based assignment problems using landmarks", presentation, COALA, Université Aix-Marseille
• "Using landmarks to improve the global cardinality constraint with costs", poster, seminar 3IA
• Presentation, Girl’s Day Boy’s Day

• Visit to Christophe Lecoutre, at CRIL in Lens, France
• "Improving assignment problems with costs", presentation, 3IA
• "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 team
• "Constraint First : A New MDD-based Model To Generate Sentences Under Constraints", presentation, Dialogue Objectif Ressources I3S/CNRS
• "Constraint Programming: All Different - the difference constraint", presentation, Pint Of Science

• Doctoral program committee CP2026
• Selection committee for STIC doctoral school thesis grants
• I3S laboratory life committee
• President of the association of doctoral students of the STIC doctoral school

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

• 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

2026

• Alexis Dubarry, 1st year of master of computer science, "Development of a web application to solve and generate cryptarithmetic puzzles"
• Florent Belot, 1st year of master of computer science, "Development of a web application to solve and generate cryptarithmetic puzzles"
• Allah-Eddine Cherigui, 1st year of master of computer science, "Development of a web application to solve and generate cryptarithmetic puzzles"
• Shanti Noel, 1st year of master of computer science, "Development of a web application to solve and generate cryptarithmetic puzzles"

2025

• Yanis M'RAD, 2nd year of a computer engineering school (Polytech) - equivalent to bachelor 2, 2 months, "Solving and generating nonograms using constraint programming"

2024

• 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"
• Matthias CARRE, 1st year of master of computer science, "Efficient transfer of an array of integers over a network

2024

• Dorian BOUCHARD , 4th year of a computer engineering school (Polytech) - equivalent to master 1, 4 months, "Développement web et transformation mobile pour une application d'apprentissage et de jeux intellectuels chez Webenla"
• Julien ORIOL, 4th year of a computer engineering school (Polytech) - equivalent to master 1, 4 months, "Transformation de Convention Organizer en plateforme en ligne"
• Lucie ANDRES, 4th year of a computer engineering school (Polytech) - equivalent to master 1, 4 months, "Ingénieur logiciel fullstack (Java et Angular) chez AirFrance KLM"

• 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