Margaux SCHMIED

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.

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, Belgique
• "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, Belgique
• "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

• 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

Academic internship

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

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

Industrial internship (academic referent)

• 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