🤖 AI

Constraint acquisition needs better benchmarks

This paper introduces MPMMine, a comprehensive and standardized benchmark suite designed to overcome the limitations of existing resources by providing diverse models, instances, and domain knowledge artifacts to facilitate the evaluation and maturation of Constraint Acquisition algorithms.

Original authors: Rafał Stachowiak, Tomasz P. Pawlak

Published 2026-05-27

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Rafał Stachowiak, Tomasz P. Pawlak

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot how to bake the perfect cake. You have a recipe (the mathematical model), but the robot doesn't know it yet. To teach it, you show it examples of cakes that turned out great (solutions) and cakes that were burnt or flat (non-solutions). This process of teaching the robot the rules of baking by showing it examples is called Constraint Acquisition.

However, the researchers in this paper, Rafał Stachowiak and Tomasz Pawlak, found a major problem: There are no good "training schools" for these robots.

The Problem: A Messy Classroom

Currently, researchers trying to teach these robots are working in a chaotic classroom.

No Standard Textbooks: Some researchers use one type of cake recipe, others use another. Some write the recipes in English, others in French, and some use secret codes.
Missing Ingredients: Often, the "training data" is incomplete. You might have the recipe, but no examples of what a good cake looks like, or no examples of what a bad cake looks like.
Unfair Tests: Because everyone is using different tools and different sets of examples, it's impossible to say which robot is actually the best baker. It's like comparing a chef who uses a gas stove to one who uses a wood fire without controlling for the heat source.

The authors argue that this mess is slowing down progress. We can't improve the robots if we can't fairly compare them.

The Solution: MPMMine (The "Perfect Bakery" Kit)

To fix this, the authors built MPMMine. Think of this as a brand-new, ultra-organized, standardized "Bakery Starter Kit" designed specifically for training these robots.

Here is what makes MPMMine special, using simple analogies:

1. The Uniform Box (Consistency & Standardization)
Imagine every single problem (like "Car Sequencing" or "Cutting Stock") comes in an identical, clear plastic box.

Inside every box, you find the exact same folders: one for the recipe, one for the ingredients, one for the "good cake" photos, and one for the "bad cake" photos.
They use universal languages (like MiniZinc for the recipe and JSON for the labels) so any computer can read them without needing a translator.

2. The Massive Photo Album (Completeness)
Previous kits often had just one or two photos of a cake. MPMMine provides thousands.

For every single problem, they generated thousands of examples of perfect solutions and thousands of examples of "almost perfect but failed" solutions.
They even included problems that are purely about numbers (like arranging cars) and problems that involve smooth, continuous measurements (like mixing liquids), ensuring the robots get a well-rounded education.

3. The Storyteller (Natural Language)
To help robots that learn by reading, MPMMine includes natural language descriptions.

It's not just a list of math equations; it's a story. "We need to load a ship so that the heaviest containers are at the bottom."
They used both human experts and advanced AI (like large language models) to write these stories, then had humans double-check them to make sure the story matched the math perfectly.

4. The "Do Not Touch" Rule (Version Control)
Once a box is sealed and labeled with a specific date (a "tag"), the contents are frozen in time.

If a researcher finds a typo in a recipe from 2024, they can't just erase it and rewrite it. They must add a new, corrected box with a new label.
This ensures that if you run an experiment today and someone else runs the same experiment next year, they are using the exact same data, making the results fair and reproducible.

What's Inside the Box Right Now?

The kit currently contains 16 different "baking challenges" (problems).

Some are about integer math (counting whole items like cars or people).
Some are about continuous math (measuring fluids or weights).
Some are a mix of both.

The Bottom Line

The authors are saying: "We built a standardized, open, and massive library of problems, solutions, and stories. It's designed to stop researchers from reinventing the wheel and to let them finally compare their AI algorithms fairly."

They admit the kit isn't finished yet (it only has 16 problems, and they want 100), but it's a solid foundation. They are inviting the whole community to help add more recipes and examples to this shared library, ensuring that the future of mathematical modeling is built on a level playing field.

Technical Summary: Constraint Acquisition Needs Better Benchmarks

Problem Statement

The field of Constraint Acquisition (CA) and the broader domain of Mathematical Programming (MP) model mining (MPMM)—which encompasses the discovery, conformance checking, and enhancement of MP models using domain knowledge artifacts—is currently hindered by a lack of adequate benchmarks. Existing benchmark suites (e.g., CSPLib, MiniZinc Challenge, MIPLIB) were primarily designed to evaluate solver performance rather than algorithms that mine models from domain knowledge. These legacy benchmarks suffer from several critical deficiencies:

Inconsistency: They lack standardized file organization, use heterogeneous modeling languages, and inconsistently store or omit essential domain knowledge artifacts (e.g., example solutions, counterexamples, natural language descriptions).
Non-reproducibility: Experimental protocols often omit crucial details regarding instance generation, constraint cardinality bounds, and data distributions.
Limited Scope: They predominantly focus on combinatorial problems, often overlooking continuous and mixed-integer problems despite their practical relevance.
Ad-hoc Evaluation: Researchers frequently employ custom, undocumented procedures to generate missing artifacts, making cross-study comparison impossible and preventing the maturation of CA methods beyond Technology Readiness Level 3.

Methodology: MPMMine

To address these gaps, the authors introduce MPMMine, a benchmark suite specifically designed to evaluate algorithms that discover, validate, and enhance MP models. The development of MPMMine is guided by six core principles: Consistency, Standardization, Completeness, Extensibility, Openness, and Version Control.

1. Structural Standardization

MPMMine enforces a uniform, four-layer hierarchical directory structure for all problems:

Problem: A root directory for each problem (e.g., P001).
MP Models: Subdirectories for different encodings/formulations of the problem.
Abstract Descriptions & Instances: Separation of instance-independent descriptions and concrete data instances.
Artifacts: Storage for instance-specific solutions, non-solutions, and text descriptions.

The dataset relies exclusively on open formats: MiniZinc (.mzn) for models, CommonMark (.md) for text descriptions, JSON for metadata, and .dzn for instance data. A strict naming convention (e.g., MPMMine-P003M002I003S00055) ensures unique global referencing of every file.

2. Artifact Generation

Exemplary Solutions: To generate uniform samples from feasible regions, the authors employ a "best-effort" uniform sampling technique. This involves encoding models as Linear Programming (LP) or Mixed-Integer LP (MILP) problems and collecting intermediate solutions found by the Gurobi solver (using Branch-and-Cut and Simplex algorithms). To avoid bias, random objective functions are drawn periodically. For continuous models, convex combinations of existing solutions are constructed to populate the interior of the feasible region. Constraints are tightened by $10^{-4}$ to avoid numerical instability near boundaries.
Exemplary Non-Solutions: These are generated to resemble valid solutions but contain deliberate, small errors that violate constraints while respecting variable domains. For integer problems, values are resampled from domains; for continuous problems, random values are sampled. Constraints are loosened slightly during sampling to ensure robust classification.
Natural Language Descriptions: Descriptions are curated for consistency with the MP models. They are sourced from original repositories, written by human experts, or generated by Large Language Models (LLMs) and subsequently manually revised to ensure accuracy.

3. Scope and Content

The initial release of MPMMine comprises 16 problems (ranging from P001 to P016), including combinatorial, continuous, and mixed types. Notably, six problems are continuous, addressing a gap in existing literature. Each problem is associated with:

Multiple models (encodings).
Tens of instances per model.
Thousands of solutions and non-solutions per instance.
Natural language descriptions in English.

Key Contributions

First Dedicated MPMM Benchmark: MPMMine is presented as the first dataset explicitly created to evaluate MP model mining methods, distinguishing it from solver-centric benchmarks.
Standardized Infrastructure: It provides a consistent, open, and version-controlled framework that facilitates reproducibility and fair comparison across studies.
Comprehensive Artifact Coverage: Unlike previous datasets, it includes the full spectrum of domain knowledge artifacts required for CA: structured models, diverse instances, thousands of labeled solutions/non-solutions, and natural language descriptions.
Extensibility: The design allows for the seamless addition of new problem types, models, and artifacts via community contributions (pull requests).

Results and Validation

The paper does not present experimental results comparing specific CA algorithms, as the benchmark is a new infrastructure. Instead, the "results" focus on the validation of the dataset's construction:

Uniformity Verification: Principal Component Analysis (PCA) was used to visualize solution and non-solution distributions in 4D. The visualizations (Figures 1a–1d) demonstrate that the sampled points uniformly fill the feasible regions for both integer and continuous models, with explained variances ranging from 31% to 52%.
Robustness: The sampling procedures were tested against standard methods (Monte Carlo, Hit-and-Run, Gibbs), which were found to fail or produce biased distributions for the target problem types. The proposed best-effort sampling successfully generated valid datasets.
Classification Accuracy: The correctness of solution/non-solution classification was verified using independent tools, ensuring robustness against floating-point inaccuracies.

Significance and Claims

The authors claim that MPMMine addresses the primary bottleneck in the maturation of Constraint Acquisition research: the absence of a dedicated, standardized research infrastructure. By providing a consistent, open, and artifact-rich environment, MPMMine aims to:

Enable reproducible experiments by documenting generation protocols.
Facilitate cross-study comparability by eliminating the need for ad-hoc experimental setups.
Support the development of text-to-model and mixed-artifact-to-model methods through the inclusion of natural language descriptions.
Bridge the gap between basic research and practical application by covering continuous and mixed problems often overlooked in MPMM literature.

The paper concludes modestly, acknowledging that the current 16-problem collection is an initial step. The long-term objective is to scale the dataset to at least 100 problems and to release a dedicated software suite to support the creation of future versions and systematic algorithmic evaluation.