Modelling with Option Types in MiniZinc?

Abstract. Option types are a powerful abstraction that allows the concise mod-elling of combinatorial problems where some decisions are relevant only if other decisions are made. They have a wide variety of uses: for example in modelling optional tasks in scheduling, or exceptions to a usual rule. Option types represent objects which may or may not exist in the constraint problem being modelled, and can take an ordinary value or a special value> indicating they are absent. The key property of variables of option types is that if they take the value> then the constraints they appear in should act as if the variable was not in the origi-nal definition. In this paper, we explore the different ways that basic constraints can be extended to handle option types, and we show that extensions of global constraints to option types cover existing and common variants of these global constraints. We demonstrate how we have added option types to the constraint modelling language MINIZINC. Constraints over variables of option types can either be handled by transformation into regular variables without extending the requirements on underlying solvers, or they can be passed directly to solvers that support them natively.