Source-linked AI summary
Learning Size Independent Constraint Models from Input Data and Positive and Negative Example Solutions
Helmut Simonis
TL;DR
Constraint acquisition has largely focused on instance-specific models, while acquiring size-independent models across multiple instances has received relatively little attention. This paper presents a tool that learns and generalizes models from structured examples and input data, producing MiniZinc code and textual descriptions. The tool achieves 100% accuracy on classification data and demonstrates feasibility for the broader use case.
Problem
Method
The tool learns instance-specific models from structured positive and negative examples, generalizes their patterns across sizes, and produces MiniZinc code and textual descriptions.
Source: §1 · pp. 1–3, §4.1.2 · p. 7Results
100% accuracy on classification data; the authors also report that the approach demonstrates feasibility for this more realistic acquisition use case.
Source: §5 · p. 14, §6 · p. 15Takeaways & Limitations
The system demonstrates the feasibility of constraint acquisition for a more realistic use case involving problem types and sizes.
Source: §6 · p. 15The current patterns miss a constraint in the extended n-queen problem, while the Golomb ruler’s optimal-solution bound has no identified generic formula for unseen sizes.
Source: §5 · p. 14
Abstract
from arXiv · showhide
In this paper we describe a Constraint Acquisition Tool that generates size independent constraint programs from input data and positive and negative example solutions of multiple problem instances. The system finds size specific models based on typical constraint patterns over global and binary constraints, then generalizes the models to a size independent model that can be run on unseen input data. The system produces MiniZinc code as well as a textual description of the model. We evaluate the tool on the example problems of the PTHG21 Challenge and show the feasibility of the approach.
1 Introduction
The paper targets constraint acquisition across differently sized instances and changing input data, rather than learning a model limited to one instance. It proposes a tool that learns and generalizes models from structured positive and negative examples, then produces executable and explainable output.
1 Introduction
- The use case requires a model to reflect how variables, domains, and constraints depend on input data and to work on previously unseen data.The introduction contrasts this with learning a single-instance model that may only transfer to changed domain bounds.Source: §1 · p. 1
- The tool takes input data and positive and negative examples from multiple problem instances, then produces a generic model for solving new instances.Users can accept or reject constraints and understand or extend the generated model.Source: §1 · p. 1
- A generic acquisition tool should handle structured variables, including collections, vectors, and matrices, and exploit that structure to identify likely links between them.Samples may omit derived variables, especially cost variables, so the system should reconstruct hidden variables.Source: §1 · pp. 1–2
- The model should generalize across instances, accept all positive samples, reject all negative samples, and omit constraints that are not required.The system does not currently handle incorrectly labelled examples.Source: §1 · p. 2
- The contributions include size-independent models from structured examples, executable MiniZinc code, textual explanations, and feasibility results on all PTHG21 Challenge benchmark problems.The approach simplifies ModelSeeker’s partition generator for more straightforward generalization, with some loss of flexibility.Source: §1 · pp. 2–3
2 Related Work
Prior constraint-acquisition work largely learned instance-specific models or focused on active querying, while size-independent acquisition from multiple instances had received relatively little attention. This system builds on ModelSeeker and the global-constraint catalog.
2 Related Work
- Constraint acquisition developed along passive learning from labelled solutions and nonsolutions, and active learning through queries to a user who knows the problem.Active-acquisition work studies query counts and query forms.Source: §2 · p. 3
- Acquisition has also been extended to integer programming, SMT, SAT, MAX-CSP, spreadsheets, and specialized domains such as timetabling and scheduling.Domain-specific methods can exploit specialized vocabularies and background knowledge.Source: §2 · p. 3
- Relatively little work addressed size-independent models learned from multiple instances, and noisy-data acquisition lacked a clearly defined realistic use case.The paper positions its use case against these gaps.Source: §2 · p. 3
- The system extends ModelSeeker’s partition generator to generalize patterns over structured data, while retaining its subsumption checks and candidate-constraint ranking.It restricts itself to 50 global constraints available in MiniZinc or simple to decompose.Source: §2 · p. 3
3 A Running Example
The running example uses a Balanced Incomplete Block Design (BIBD) to illustrate learning a model from instances of different sizes and applying it to new input parameters.
3 A Running Example
- A BIBD arranges objects into blocks so each block has k objects, each object occurs in r blocks, and each pair of objects occurs together in λ blocks.The values of b and r can be deduced from λ, v, and k.Source: §3 · p. 4
- The equivalent 0/1 incidence-matrix formulation requires r ones per row, k ones per column, and λ shared ones for each pair of rows.The acquisition process learns constraints over 0/1 variables, not the original integer formulation.Source: §3 · p. 4
- The example dataset contains 20 differently sized instances with solutions and nonsolutions; larger instances may provide only a fraction of all solutions.Nonsolutions were generated randomly or by modifying existing solutions and checking that they were invalid.Source: §3 · p. 4
- The task is to use new parameter values to find a correctly sized 0/1 solution matrix satisfying the problem constraints.The inputs include λ, v, and k.Source: §3 · p. 4
4 System Description
The system first learns instance-specific models, generalizes them into a size-independent model, and then generates executable and explainable output. In evaluation, it also classifies test cases and generates additional solutions.
4 System Description
- The first stage produces an instance-specific model for each problem instance and uses it to check test cases at that size.This is the first of three high-level system parts.Source: §4 · p. 4
- The second stage generalizes size-specific models into one model for all sizes, then reduces it by removing subsumed constraints and ranking candidates.Constraint ranking is based on interest.Source: §4 · p. 4
- The third module generates executable MiniZinc code, a natural-language description, and an acquisition report for users.The code can be used to find solutions for unseen instances.Source: §4 · p. 4
- The evaluation uses the tool both to classify test cases as solutions or nonsolutions and to produce additional solutions beyond the samples and test cases.The architecture separates the acquisition process into components, most of which are described as relatively simple.Source: §4 · pp. 4–5
4.1 Generating Size Specific Models
The system builds size-specific models by testing structured constraint patterns over original and transformed variables, then checks candidates against positive and negative examples. Its patterns exploit known structure in the data, keeping the search manageable while supporting later generalization.
4.1 Generating Size Specific Models
- Structured variable subsets and input index sets define constraint scopes, avoiding an exponential search over possible subsets while extending beyond regular structures.This stage builds size-specific models from conjunctions of global constraints that hold over multiple structured subsets.Source: §4.1 · p. 5
4.1.1 Transformation Generator
- The transformation generator considers differences, absolute values, cost variables, and projections, generating them speculatively and retaining only transformations used by constraints.Cost variables use input cost vectors or matrices; projections require input data that maps decision values to projected domains.Source: §4.1.1 · p. 5
4.1.2 Pattern Generator
- The simpler pattern generator trades some ModelSeeker partition flexibility for patterns that generalize trivially and exploit input structure.For matrices, patterns include whole-matrix or index-selected lists, rows and columns, blocks and diagonals, and pairs of rows or columns.Source: §4.1.2 · pp. 7–8
4.1.3 Binary Pattern Generator
- Binary patterns test constraints between all, ordered, or consecutive elements of a list, and between corresponding elements of two lists.The system assumes structured constraints are regular or specified by input index sets, and tests only small fixed integer constants.Source: §4.1.3 · p. 8
4.1.4 Finding Candidate Constraint Patterns
- Candidates must hold for every positive sample; negative samples help identify constraints that reject at least some non-solutions.The pattern check outputs tuples of pattern, variable, transformations, and constraints before subsumption checks or constraint ranking.Source: §4.1.4 · pp. 8–9
4.1.5 Checker
- The generalized constraint checker applies patterns, variables, transformations, and constraints to samples and tests whether the constraints are satisfied.The tool implements a checker for each modeled global constraint.Source: §4.1.5 · p. 9
4.2 Generalizing Models
The system generalizes instance models by retaining shared constraint patterns, explaining changing parameter values from input data, and reducing redundant or unlikely constraints. The resulting model is intended to transfer across problem sizes while remaining minimal.
4.2.1 Generalizer
- A generic model retains only constraints shared by all instance models, with structural patterns enabling comparison across sizes despite changing parameter values.The generalizer delays subsumption checks until after identifying shared patterns.Source: §4.2 · p. 9, §4.2.1 · p. 9
4.2.2 Formula Generator
- Parameter formulas use constants, input parameters, primitive functions, or nested arithmetic formulas, with user input requested when none explains a value.The bottom-up search found formulas in all benchmark cases in a few milliseconds; more complex equation-discovery methods could be added for harder cases.Source: §4.2.2 · p. 10
4.2.3 Model Reduction
- Model reduction eliminates unneeded constraints using subsumption, then ranks constraints to eliminate unlikely model elements: nvalue(2) over all variables is removed because domain 0..1 implies it, while scalar_product is kept only for AllDifferentRows.Source: §4.2.3 · p. 11
4.3 Producing Working CP Program
The final system stage turns the generic model into executable MiniZinc code and provides users with a textual description and a report on the acquisition process.
4.3 Producing Working CP Program
- The final stage generates executable MiniZinc code, a natural-language model description, and a report documenting the acquisition process.The report records extracted information and decisions, including found or rejected constraints and formulas generated from the data.Source: §4.3 · p. 12, §4.3.3 · p. 13
4.3.1 Code Generator
- Code generation defines input and computed parameters, variables, selected constraints, and a default feasible-solution search, or an optimal search when an objective is detected.A separate module converts JSON input into .dzn files, and a library supplies some global constraints and primitive functions.Source: §4.3.1 · p. 12
4.3.2 Description Generator
- The description generator uses templates to produce a basic textual account of the model, but detailed global-constraint descriptions are available only for specific constraints.The authors suggest adapting descriptions to problem domains as future work.Source: §4.3.2 · p. 13
4.3.3 Report Generator
- The report generator exposes intermediate acquisition steps, including extracted information, decisions, rejected constraints, and formulas derived from the input data.Users who need only the generated code and description may not need this additional report.Source: §4.3.3 · p. 13
5 Evaluation
Across the PTHG21 benchmark, generated models accepted all positive examples, rejected all negative examples, and achieved 100% classification accuracy. The evaluation also found limits in extra-solution generation and variation in runtime compared with handwritten models.
5 Evaluation
- The PTHG21 evaluation covered 15 problems with multiple instances, positive and negative examples, and known- and unknown-size test cases.The benchmark also allowed participants to submit new solutions; its overall score combined test-classification correctness with the number and correctness of extra solutions.Source: §5 · p. 13
- Extra-solution generation was limited by an unavailable formula for Golomb-ruler optima and a missed repeated-knight-move constraint in problem 16.The missed constraint led to many generated solutions being rejected, although it was not needed to classify the test cases; the authors note the method depends heavily on sample quality.Source: §5 · p. 14
- All benchmark programs ran with at least one MiniZinc backend solver and produced initial solutions in seconds, though some could not enumerate every solution within 300 seconds.The authors attribute enumeration limits to either the number of solutions or deep solver backtracking after initial solutions.Source: §5 · p. 14
- Generated code was comparable to handwritten models in most, but not all, cases.For Costas Arrays, the generated model used a lex-different constraint on difference tuples, while the handwritten models used multiple alldifferent constraints.Source: §5 · pp. 14–15
- 100% classification accuracy accompanied generated models' acceptance of all positive examples and rejection of all negative examples.The reported classification result indicates generalization on the benchmark tests, but does not establish that generated code matches the original problems perfectly.Source: §5 · p. 14, Table 3 · p. 15
6 Conclusions and Future Work
The authors conclude that the system demonstrates the feasibility of constraint acquisition for more realistic problem types and sizes, while identifying limitations that remain before operational use.
6 Conclusions and Future Work
- The current approach can identify typical objective functions but does not handle cases where only optimal or near-optimal solutions are accepted.Source: §6 · p. 15
- Current index-set support is limited, and the authors identify more complicated index filtering as a needed extension.One example is selecting tasks according to whether their duration exceeds an input parameter.Source: §6 · p. 15
- Identifying which input data define a model remains a major challenge when practical datasets contain unrelated items and tables.Source: §6 · p. 15
- A problem requiring a global constraint absent from the catalog and system can only be modeled partially.Source: §6 · p. 15
- The evaluation focused on automated acquisition with limited user involvement; the authors call for studying useful interaction without excessive or repetitive questions.Source: §6 · p. 15
- The system demonstrates the feasibility of constraint acquisition for a more realistic use case and suggests that more powerful tools for real-world problem types and sizes are possible.Source: §6 · p. 15