Introduction
Integer Programming (IP) serves as the mathematical foundation for critical logistics and optimization tasks, ranging from nurse rostering to complex flight scheduling. Despite its utility, a significant "modeling bottleneck" persists: translating real-world requirements into formal mathematical constraints requires specialized expertise and is notoriously time-consuming.
Existing approaches to automated constraint acquisition often suffer from three primary limitations: they struggle with multi-dimensional data, they are frequently restricted to linear relationships, and they typically require negative examples (infeasible solutions) which are rarely available in real-world datasets. To address these challenges, we present ARNOLD (AcquiRing NOn-Linear moDels), a framework designed to learn multi-dimensional, non-linear IP constraints using only positive examples.
Methodology
ARNOLD’s architecture is built upon three technical pillars that enable efficient search through a vast space of potential mathematical models:
- Tensor-Based Language: Rather than treating variables as isolated scalars, ARNOLD operates on tensors. This allows the system to express complex constraints—such as shift requirements across a multi-dimensional grid of staff and days—in a compact and natural mathematical form.
- General-to-Specific Search: The algorithm employs a refinement strategy, starting with the most permissive constraints and iteratively increasing their strictness. This hierarchical approach allows ARNOLD to prune entire branches of the search space; if a permissive constraint is violated by a known valid example, all stricter versions of that constraint are also guaranteed to be invalid.
- Nested Lexicographic Ordering: To ensure computational efficiency, ARNOLD utilizes a strict internal ordering for exploring tensors, indices, and operations. This prevents the algorithm from redundantly evaluating the same constraint through different paths.
To maintain the efficiency of this search, ARNOLD categorizes tensors into "good" (values $\ge 1$), "bad" (values between 0 and 1), and "ugly" (mixed or negative values). This classification is essential for maintaining monotonicity, ensuring that increasing constraint complexity consistently leads to greater specificity.
Experimental Evaluation
ARNOLD was evaluated using 10 benchmark problems from the MiniZinc library, representing a mix of classic puzzles (e.g., Knapsack, Social Golfers) and industrial applications (e.g., Shipping, Nurse Rostering, and Capital Budgeting). Training data was generated using the Gecode solver, from which small subsets—ranging from 1 to 25 examples—were sampled to test the framework's ability to recover original rules from minimal data.
Key Results and Insights
ARNOLD demonstrated a remarkable ability to reconstruct complex models with high fidelity. In 8 out of 10 benchmark scenarios, the framework achieved over 90% precision and recall using a sample size of just 25 positive examples.
Beyond accuracy, the framework's pruning and ordering strategies proved vital for performance. In complex problem settings, ARNOLD operated eight times faster than a naive search and explored 40 times fewer candidate constraints. These results confirm that ARNOLD can handle sophisticated problems involving multiple decision variables and constants, moving beyond simple "toy" examples.
Limitations and Future Directions
While ARNOLD represents a significant step forward, several areas for improvement remain. The current system struggles with strict equality constraints, which are prevalent in problems like "Social Golfers." Additionally, "ugly" tensors—those with highly varied or negative values—can break the pruning logic, necessitating slower, more exhaustive searches. Future work will focus on refining these representations and extending the framework to learn objective functions, allowing ARNOLD to identify not just valid solutions, but optimal ones.
Summary updated