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 ef-
ficiently 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