2.4. 选项类型

选项类型是一个强大的抽象，使得简洁建模成为可能。一个选项类型决策变量代表了一个有其他可能 $\top$ 的变量，在MiniZinc中表达为 <> ，代表了这个变量是 缺失的 。选项类型变量在建模一个包含在其他变量没做决定之前不会有意义的变量的问题时是很有用的。

2.4.1. 声明和使用选项类型

选项类型变量

一个选项类型变量被声明为：

var opt <类型> : <变量名>:

其中 <类型> 是 int ， float 或 bool 中的一个，或者是一个固定范围的表达式。选项类型变量可以是参数，但是这个不常用。

一个选项类型变量可以有附加值 <> 表明它是 缺失的 。

三个内建函数被提供给选项类型变量： absent(v) 只有在选项类型变量 v 取值 <> 时返回 true ， occurs(v) 只有在选项类型变量 v 不取值 <> 时返回 true ，以及 <> 返回 v 的正常值或者当它取值 <> 时返回失败。

选项类型最常被用到的地方是调度中的可选择任务。在灵活的车间作业调度问题中，我们有 n 个在 k 个机器上执行的任务，其中完成每个机器上每个任务的时间可能是不一样的。我们的目标是最小化所有任务的总完成时间。一个使用选项类型来描述问题的模型在列表 2.4.1 中给出。在建模这个问题的时候，我们使用 $n \times k$ 个可选择的任务来代表每个机器上每个任务的可能性。我们使用 alternative 全局约束来要求任务的起始时间和它的持续时间跨越了组成它的可选择任务的时间，同时要求只有一个会实际运行。我们使用 disjunctive 全局变量在每个机器上最多有一个任务在运行，这里我们延伸到可选择的任务。最后我们约束任何时候最多有$k$个任务在运行，利用一个在实际（不是可选择的）任务上作用的冗余约束。

列表 2.4.1 使用选项类型的灵活车间作业调度模型 (flexible-js.mzn). ▶

include "globals.mzn";

int: horizon;                  % 时间范围
set of int: Time = 0..horizon;
enum Task;
enum Machine; 

array[Task,Machine] of int: d; % 每个机器上的持续时间
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;             % 起始时间
array[Task] of var mind..maxd: D;       % 持续时间
array[Task,Machine] of var opt Time: O; % 可选择的任务起始

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],card(Machine));

solve minimize max(t in Task)(S[t] + D[t]);

2.4.2. 隐藏选项类型

当列表推导式是从在变量集合迭代上创建而来，或者 where 从句中的表达式还没有固定时，选项类型变量会隐式地出现。

例如，模型片段

var set of 1..n: x;
constraint sum(i in x)(i) <= limit;

是以下的语法糖

var set of 1..n: x;
constraint sum(i in 1..n)(if i in x then i else <> endif) <= limit;

内建函数 sum 实际上在一列类型-实例化 var opt int 上操作。由于 <> 在+中表现为标识0，我们会得到期望的结果。

类似地，模型片段

array[1..n] of var int: x;
constraint forall(i in 1..n where x[i] >= 0)(x[i] <= limit);

是以下的语法糖

array[1..n] of var int: x;
constraint forall(i in 1..n)(if x[i] >= 0 then x[i] <= limit else <> endif);

同样地，函数 forall 实际上在一列类型-实例化 var opt bool 上操作。由于 <> 在 /\ 上表现为标识 true ，我们可以得到期望的结果。

尽管我们已经很小心了，隐式的使用可能会导致意外的行为。观察

var set of 1..9: x;
constraint card(x) <= 4;
constraint length([ i | i in x]) > 5;
solve satisfy;

它本应该是一个不可满足的问题。它返回 x = {1,2,3,4} 作为一个解例子。这个是正确的因为第二个约束等于

constraint length([ if i in x then i else <> endif | i in 1..9 ]) > 5;

而可选择整数列表的长度总会是9，所以这个约束总是会满足。

我们可以通过不在变量集合上创建迭代或者使用不固定的 where 从句来避免隐式的选项类型。例如，上面的两个例子可以不使用选项类型重写为

var set of 1..n: x;
constraint sum(i in 1..n)(bool2int(i in x)*i) <= limit;

和

array[1..n] of var int: x;
constraint forall(i in 1..n)(x[i] >= 0 -> x[i] <= limit);