Acquiring Integer Programs from Data

Mohit Kumar, Stefano Teso, Luc De Raedt

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:

  1. 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.
  2. 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.
  3. 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.
General-to-specific search tree illustrating the refinement of constraints from permissive to strict.

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.

Precision and recall metrics for ARNOLD across ten benchmark problems with varying sample sizes (n=1 and n=25).

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

Abstract

Integer programming (IP) is widely used within operations research to model and solve complex combinatorial problems such as personnel rostering and assignment problems. Modelling such problems is difficult for non-experts and expensive when hiring domain experts to perform the modelling. For many tasks, however, examples of working solutions are readily available. We propose ARNOLD, an approach that partially automates the modelling step by learning an integer program from example solutions. Contrary to existing alternatives, ARNOLD natively handles multi-dimensional quantities and non-linear operations, which are at the core of IP problems, and it only requires examples of feasible solution. The main challenge is to efficiently explore the space of possible programs. Our approach pairs a general-to-specific traversal strategy with a nested lexicographic ordering in order to prune large portions of the space of candidate constraints while avoiding visiting the same candidate multiple times. Our empirical evaluation shows that ARNOLD can acquire models for a number of realistic benchmark problems
BibTeX
@inproceedings{kumar2019acquiring,
  author = {Mohit Kumar and Stefano Teso and Luc De Raedt},
  title = {{Acquiring Integer Programs from Data}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/158},
}
Figure