2.4. Option Types¶
Option types are a powerful abstraction that allows for concise modelling. An
option type decision variable represents a decision that has another
possibility \(\top\), represented in MiniZinc as <>
indicating the variable is absent.
Option type decisions are useful for modelling problems where a decision is
not meaningful unless other decisions are made first.
2.4.1. Declaring and Using Option Types¶
Option type Variables
An option type variable is declared as:
var opt <type> : <var-name>:
where <type>
is one of int
, float
or bool
or
a fixed range expression.
Option type variables can be parameters but this is rarely useful.
An option type variable can take the additional value
<>
indicating absent.
Three builtin functions are provided for option type variables:
absent(v)
returns true
iff option type variable v
takes the value
<>
,
occurs(v)
returns true
iff option type variable v
does not take the value
<>
,
and
deopt(v)
returns the normal value of v
or fails if it takes the
value <>
.
The most common use of option types is for optional tasks in scheduling.
In the flexible job shop scheduling problem we have n
tasks to perform
on k
machines, and the time to complete each task on each machine
may be different. The aim is to minimize the completion time of all tasks.
A model using option types to encode the problem is given in
Listing 2.4.1. We model the problem using \(n \times k\) optional
tasks representing the possibility of each task run on each machine.
We require that start time of the task and its duration spans the optional
tasks that make it up, and require only one actually runs using the
alternative
global constraint.
We require that at most one task runs on any machine using the
disjunctive
global constraint extended to optional tasks.
Finally we constrain that at most k
tasks run at any time, a redundant
constraint that holds on the actual (not optional) tasks.
int: horizon; % time horizon
set of int: Time = 0..horizon;
enum Task;
enum Machine;
array[Task,Machine] of int: d; % duration on each machine
int: maxd = max([ d[t,m] | t in Task, m in Machine ]);
int: mind = min([ d[t,m] | t in Task, m in Machine ]);
array[Task] of var Time: S; % start time
array[Task] of var mind..maxd: D; % duration
array[Task,Machine] of var opt Time: O; % optional task start
constraint forall(t in Task)(alternative(S[t],D[t],
[O[t,m]|m in Machine],[d[t,m]|m in Machine]));
constraint forall(m in Machine)
(disjunctive([O[t,m]|t in Task],[d[t,m]|t in Task]));
constraint cumulative(S,D,[1|i in Task],k);
solve minimize max(t in Task)(S[t] + D[t]);