2.3. 谓词和函数

MiniZinc中的谓词允许我们用简洁的方法来表达模型中的复杂约束。 MiniZinc中的谓词利用预先定义好的全局约束建模,同时也让建模者 获取以及定义新的复杂约束。MiniZinc中的函数用来捕捉模型中的共同结构。 实际上,一个谓词就是一个输出类型为 var bool 的函数。

2.3.1. 全局约束

MiniZinc中定义了很多可以在建模中使用的全局约束。 由于全局约束的列表一直在慢慢增加,最终确定的列表可以在发布的文档中找到。 下面我们讨论一些最重要的全局约束。

2.3.1.1. Alldifferent

约束 alldifferent 的输入为一个变量数组,它约束了这些变量取不同的值。
alldifferent 的使用有以下格式
alldifferent(array[int] of var int: x)

即,参数是一个整型变量数组。

alldifferent 是约束规划中被最多研究以及使用的全局约束之一。 它被用来定义分配子问题,人们也给出了 alldifferent 的高效全局传播器。 send-more-money.mzn (Listing 2.2.4) 和 sudoku.mzn (Listing 2.2.5) 是使用 alldifferent 的模型例子。

2.3.1.2. Cumulative

约束 cumulative 被用来描述资源累积使用情况。

cumulative(array[int] of var int: s, array[int] of var int: d,
           array[int] of var int: r, var int: b)

规定对于一个起始时间为 s ,持续时间为 d 以及资源需求量为 r 的任务集合,在任何时间对资源的需求量都不能超过一个全局资源量界限 b

Listing 2.3.1 使用 cumulative 来建模搬运家具问题的模型 (moving.mzn).
include "cumulative.mzn";

enum OBJECTS;
array[OBJECTS] of int: duration; % 移动的持续时间
array[OBJECTS] of int: handlers; % 需要的搬运工的数量
array[OBJECTS] of int: trolleys; % 需要的手推车的数量

int: available_handlers;
int: available_trolleys;
int: available_time;

array[OBJECTS] of var 0..available_time: start;
var 0..available_time: end;

constraint cumulative(start, duration, handlers, available_handlers);
constraint cumulative(start, duration, trolleys, available_trolleys);
 
constraint forall(o in OBJECTS)(start[o] +duration[o] <= end);

solve minimize end;

output [ "start = \(start)\nend = \(end)\n"];
Listing 2.3.2 使用 cumulative 来建模搬运家具问题的数据 (moving.dzn).
OBJECTS = { piano, fridge, doublebed, singlebed, 
            wardrobe, chair1, chair2, table };

duration = [60, 45, 30, 30, 20, 15, 15, 15];
handlers = [3, 2, 2, 1, 2, 1, 1, 2];
trolleys = [2, 1, 2, 2, 2, 0, 0, 1];

available_time = 180;
available_handlers = 4;
available_trolleys = 3;

Listing 2.3.1 中的模型为搬运家具规划一个行程表使得每一份家具在搬运的过程中都有足够的搬用工和足够的手推车可以使用。允许的时间,可以使用的搬运工以及手推车被给出,每个物体的搬运持续时间,需要的搬运工和手推车的数量等数据也被给出。使用 Listing 2.3.2 中的数据,命令

$ minizinc moving.mzn moving.dzn

可能会得到如下输出

start = [0, 60, 60, 90, 120, 0, 15, 105]
end = 140
----------
==========

Fig. 2.3.1 and Fig. 2.3.2 给出了这个解中搬运时每个时间点所需要的搬运工和手推车。

images/handlers.svg

Fig. 2.3.1 搬运时搬运工使用量直方图

images/trolleys.svg

Fig. 2.3.2 搬运时手推车使用量直方图

2.3.1.3. Table

约束 table 强制变量元组从一个元组集合中取值。由于MiniZinc中没有元组,我们用数组来描述它。 根据元组是布尔型还是整型, table 的使用有以下两种格式

table(array[int] of var bool: x, array[int, int] of bool: t)
table(array[int] of var int:  x, array[int, int] of int:  t)

强制约束了 \(x \in t\) ,其中 \(x\)\(t\) 中的每一行是元组, \(t\) 是一个元组集合。

Listing 2.3.3 使用 table 约束来建模食物规划问题的模型 (meal.mzn).
% 规划均衡的膳食
include "table.mzn";
int: min_energy;
int: min_protein;
int: max_salt;
int: max_fat;
set of FOOD: desserts;
set of FOOD: mains;
set of FOOD: sides;
enum FEATURE = { name, energy, protein, salt, fat, cost}; 
enum FOOD; 
array[FOOD,FEATURE] of int: dd; % 食物数据库

array[FEATURE] of var int: main;
array[FEATURE] of var int: side;
array[FEATURE] of var int: dessert;
var int: budget;

constraint main[name] in mains;
constraint side[name] in sides;
constraint dessert[name] in desserts;
constraint table(main, dd);
constraint table(side, dd);
constraint table(dessert, dd);
constraint main[energy] + side[energy] + dessert[energy] >=min_energy;
constraint main[protein]+side[protein]+dessert[protein] >=min_protein;
constraint main[salt] + side[salt] + dessert[salt] <= max_salt;
constraint main[fat] + side[fat] + dessert[fat] <= max_fat;
constraint budget = main[cost] + side[cost] + dessert[cost];

solve minimize budget; 

output ["main = ",show(to_enum(FOOD,main[name])),
        ", side = ",show(to_enum(FOOD,side[name])),
        ", dessert = ",show(to_enum(FOOD,dessert[name])),
        ", cost = ",show(budget), "\n"];
Listing 2.3.4 定义 table 的食物规划的数据 (meal.dzn).
FOOD = { icecream, banana, chocolatecake, lasagna, 
          steak, rice, chips, brocolli, beans} ;

dd = [| icecream,      1200,  50,  10, 120,  400     % 冰淇淋
      | banana,         800, 120,   5,  20,  120     % 香蕉
      | chocolatecake, 2500, 400,  20, 100,  600     % 巧克力蛋糕
      | lasagna,       3000, 200, 100, 250,  450     % 千层面
      | steak,         1800, 800,  50, 100, 1200     % 牛排
      | rice,          1200,  50,   5,  20,  100     % 米饭
      | chips,         2000,  50, 200, 200,  250     % 薯条
      | brocolli,       700, 100,  10,  10,  125     % 花椰菜
      | beans,         1900, 250,  60,  90,  150 |]; % 黄豆

min_energy = 3300;
min_protein = 500;
max_salt = 180;
max_fat = 320;
desserts = { icecream, banana, chocolatecake };
mains = { lasagna, steak, rice };
sides = { chips, brocolli, beans };

Listing 2.3.3 中的模型寻找均衡的膳食。每一个食物项都有一个名字(用整数表示),卡路里数,蛋白质克数,盐毫克数,脂肪克数以及单位为分的价钱。这些个项之间的关系用一个 table 约束来描述。 模型寻找拥有最小花费,最少卡路里数 min_energy ,最少蛋白质量 min_protein ,最大盐分 max_salt 以及脂肪 max_fat 的膳食。

2.3.1.4. Regular

约束 regular 用来约束一系列的变量取有限自动机定义的值。 regular 的使用有以下方式

regular(array[int] of var int: x, int: Q, int: S,
        array[int,int] of int: d, int: q0, set of int: F)

它约束了 x 中的一列值(它们必须是在范围 range 1..S 内)被一个有 Q 个状态,输入为 1..S ,转换函数为 d<1..Q, 1..S> 映射到 0..Q ),初始状态为 q0 (必须在 1..Q 中)和接受状态为 F`(必须在 :mzn:`1..Q 中)的 DFA 接受。 状态0被保留为总是会失败的状态。

images/dfa.svg

Fig. 2.3.3 判定正确排班的DFA。

我们来看下护士排班问题。每一个护士每一天被安排为以下其中一种:(d)白班(n)夜班或者(o)休息。 每四天,护士必须有至少一天的休息。每个护士都不可以被安排为连续三天夜班。这个问题可以使用 Fig. 2.3.3 中的不完全DFA来表示。我们可以把这个DFA表示为初始状态是 1 ,结束状态是 1..6 ,转换函数为

  d n o
1 2 3 1
2 4 4 1
3 4 5 1
4 6 6 1
5 6 0 1
6 0 0 1

注意状态表中的状态0代表一个错误状态。 Listing 2.3.5 中给出的模型为 num_nurses 个护士 num_days 天寻找一个排班,其中我们要求白天有 req_day 个护士值班,晚上有 req_night 个护士值班,以及每个护士至少有 min_night 个夜班。

Listing 2.3.5 使用 regular 约束来建模的护士排班问题模型 (nurse.mzn)
% 简单护士排班问题
include "regular.mzn";
enum NURSE;
enum DAY;
int: req_day;
int: req_night;
int: min_night;

enum SHIFT = { d, n, o };
int: S = card(SHIFT);

int: Q = 6; int: q0 = 1; set of int: STATE = 1..Q;
array[STATE,SHIFT] of int: t =
     [| 2, 3, 1    % 状态1
      | 4, 4, 1    % 状态2
      | 4, 5, 1    % 状态3
      | 6, 6, 1    % 状态4
      | 6, 0, 1    % 状态5
      | 0, 0, 1|]; % 状态6

array[NURSE,DAY] of var SHIFT: roster;

constraint forall(j in DAY)(
             sum(i in NURSE)(roster[i,j] == d) == req_day /\
             sum(i in NURSE)(roster[i,j] == n) == req_night
           );
constraint forall(i in NURSE)(
             regular([roster[i,j] | j in DAY], Q, S, t, q0, STATE) /\
             sum(j in DAY)(roster[i,j] == n) >= min_night
           );

solve satisfy;

output [ show(roster[i,j]) ++ if j==card(DAY) then "\n" else " " endif
       | i in NURSE, j in DAY ]; 

运行命令

$ minizinc nurse.mzn nurse.dzn

找到一个给7个护士10天的排班,要求白天有3个人值班,夜晚有2个人值班,以及每个护士最少有2个夜班。 一个可能的结果是

o d n n o n n d o o
d o n d o d n n o n
o d d o d o d n n o
d d d o n n d o n n
d o d n n o d o d d
n n o d d d o d d d
n n o d d d o d d d
----------

另外一种regular约束是 regular_nfa 。它使用NFA(没有 \epsilon 弧)来定义regular表达式。此约束有以下格式

regular_nfa(array[int] of var int: x, int: Q, int: S,
        array[int,int] of set of int: d, int: q0, set of int: F)

它约束了数组 x 中的数值序列(必须在范围 1..S 中)被含有 Q 个状态,输入为 1..S ,转换函数为 d (映射 <1..Q, 1..S>1..Q 的子集),初始状态为 q0 (必须在范围 1..Q 中)以及接受状态为 F (必须在范围 1..Q 中)的 NFA 接受。 在这里,我们没必要再给出失败状态0,因为转换函数可以映射到一个状态的空集。

2.3.2. 定义谓词

MiniZinc的其中一个最强大的建模特征是建模者可以定义他们自己的高级约束。这就使得他们可以对模型进行抽象化和模块化。也允许了在不同的模型之间重新利用约束以及促使了用来定义标准约束和类型的特殊库应用的发展。

Listing 2.3.6 使用谓词的车间作业调度问题模型 (jobshop2.mzn)
int: jobs;                                    % 作业的数量
set of int: JOB = 1..jobs;
int: tasks;                                   % 每个作业的任务数量
set of int: TASK = 1..tasks;
array [JOB,TASK] of int: d;                   % 任务持续时间
int: total = sum(i in JOB, j in TASK)(d[i,j]);% 总持续时间
int: digs = ceil(log(10.0,total));            % 输出的数值
array [JOB,TASK] of var 0..total: s;          % 起始时间
var 0..total: end;                            % 总结束时间

% nooverlap
predicate no_overlap(var int:s1, int:d1, var int:s2, int:d2) =
    s1 + d1 <= s2 \/ s2 + d2 <= s1;

constraint %% 保证任务按照顺序出现
    forall(i in JOB) (
        forall(j in 1..tasks-1) 
            (s[i,j] + d[i,j] <= s[i,j+1]) /\
        s[i,tasks] + d[i,tasks] <= end
    );

constraint %% 保证任务之间没有重叠
    forall(j in TASK) (
        forall(i,k in JOB where i < k) (
            no_overlap(s[i,j], d[i,j], s[k,j], d[k,j])
        )
    );

solve minimize end;

output ["end = \(end)\n"] ++
       [ show_int(digs,s[i,j]) ++ " " ++ 
         if j == tasks then "\n" else "" endif |
         i in JOB, j in TASK ];

我们用一个简单的例子开始,回顾下前面章节中的车间作业调度问题。这个模型在 Listing 2.3.6 中给出。我们感兴趣的项是 谓词 项:

predicate no_overlap(var int:s1, int:d1, var int:s2, int:d2) =
    s1 + d1 <= s2 \/ s2 + d2 <= s1;

它定义了一个新的约束用来约束起始时间为 s1 ,持续时间为 d1 的任务不能和起始时间为 s2 ,持续时间为 d2 的任务重叠。它可以在模型的任何(包含决策变量的) 布尔型表达式 可以出现的地方使用。

和谓词一样,建模者也可以定义只涉及到参数的新的约束。和谓词不一样的是,它们可以被用在条件表达式的测试中。它们被关键字 test 定义。例如

test even(int:x) = x mod 2 = 0;

谓词定义

使用以下形式的语句,我们可以定义谓词

predicate <谓词名> ( <参数定义>, ..., <参数定义> ) = <布尔表达式>

<谓词名> 必须是一个合法的MiniZinc标识符,每个 <参数定义> 都是一个合法的MiniZinc类型 type 声明。

参数 定义的一个松弛是数组的索引类型可以是 没有限制地 写为 int

类似的,使用以下形式的语句,我们定义测试

test <谓词名> ( <参数定义>, ..., <参数定义> ) = <布尔表达式>

其中的 <布尔表达式> 必须是固定的。

另外我们介绍一个谓词中使用到的 assert 命令的新形式。

assert ( <布尔表达式>, <字符串表达式>, <表达式> )

assert 表达式的类型和最后一个参数的类型一样。 assert 表达式检测第一个参数是否为假,如果是则输出第二个参数字符串。如果第一个参数是真,则输出第三个参数。

注意 assert表达式 中的第三个参数是延迟的,即如果第一个参数是假,它就不会被评估。所以它可以被用来检查

predicate lookup(array[int] of var int:x, int: i, var int: y) =
    assert(i in index_set(x), "index out of range in lookup"
           y = x[i]
    );

此代码在 i 超出数组 x 的范围时不会计算 x[i]

2.3.3. 定义函数

MiniZinc中的函数和谓词一样定义,但是它有一个更一般的返回类型。

下面的函数定义了一个数独矩阵中的第 \(a^{th}\) 个子方块的第 \(a1^{th}\) 行。

function int: posn(int: a, int: a1) = (a-1) * S + a1;

有了这个定义之后,我们可以把 Listing 2.2.5 中的数独问题的最后一个约束替换为

constraint forall(a, o in SubSquareRange)(
                  alldifferent([ puzzle [ posn(a,a0), posn(o,o1) ] |
                                         a1,o1 in SubSquareRange ] ) );

函数对于描述模型中经常用到的复杂表达式非常有用。 例如,想象下在 \(n \times n\) 的方格的不同位置上放置数字1到 \(n\) 使得任何两个数字 \(i\)\(j\) 之间的曼哈顿距离比这两个数字其中最大的值减一还要大。我们的目的是最小化数组对之间的总的曼哈顿距离。曼哈顿距离函数可以表达为:

function var int: manhattan(var int: x1, var int: y1,
                            var int: x2, var int: y2) =
         abs(x1 - x2) + abs(y1 - y2);

完整的模型在 Listing 2.3.7 中给出。

Listing 2.3.7 阐释如何使用函数的数字放置问题模型 (manhattan.mzn).
int: n;
set of int: NUM = 1..n;

array[NUM] of var NUM: x;
array[NUM] of var NUM: y;
array[NUM,NUM] of var 0..2*n-2: dist = 
     array2d(NUM,NUM,[ 
     if i < j then manhattan(x[i],y[i],x[j],y[j]) else 0 endif
                     | i,j in NUM ]);

% manf
function var int: manhattan(var int: x1, var int: y1,
                            var int: x2, var int: y2) =
         abs(x1 - x2) + abs(y1 - y2);

constraint forall(i,j in NUM where i < j)
                 (dist[i,j] >= max(i,j)-1);

var int: obj = sum(i,j in NUM where i < j)(dist[i,j]);
solve minimize obj; 

% 简单地显示结果
include "alldifferent_except_0.mzn";
array[NUM,NUM] of var 0..n: grid;
constraint forall(i in NUM)(grid[x[i],y[i]] = i);
constraint alldifferent_except_0([grid[i,j] | i,j in NUM]);

output ["obj = \(obj);\n"] ++
       [ if fix(grid[i,j]) > 0 then show(grid[i,j]) else "." endif
         ++ if j = n  then "\n" else "" endif 
       | i,j in NUM ]; 

函数定义

函数用以下格式的语句定义

function <返回类型> : <函数名> ( <参数定义>, ..., <参数定义> ) = <表达式>

<函数名> 必须是一个合法的MiniZinc标识符。每一个 <参数定义> 是一个合法的MiniZinc类型声明。 <返回类型> 是函数的返回类型,它必须是 <表达式> 的类型。参数和谓词定义中的参数有一样的限制。

MiniZinc中的函数可以有任何返回类型,而不只是固定的返回类型。 在定义和记录多次出现在模型中的复杂表达式时,函数是非常有用的。

2.3.4. 反射函数

为了方便写出一般性的测试和谓词,各种反射函数会返回数组的下标集合,var集合的定义域以及决策变量范围的信息。关于下标集合的有以下反射函数 index_set(<1-D array>), index_set_1of2(<2-D array>), index_set_2of2(<2-D array>), 以及关于更高维数组的反射函数。

车间作业问题的一个更好的模型是把所有的对于同一个机器上的不重叠约束结合为一个单个的析取约束。 这个方法的一个优点是虽然我们只是初始地把它建模成一个 non-overlap 约束的连接,但是如果下层的求解器对于解决析取约束有一个更好的方法,在对我们的模型最小改变的情况下,我们可以直接使用它。这个模型在 Listing 2.3.8 中给出。

Listing 2.3.8 使用 disjunctive 谓词的车间作业调度问题模型 (jobshop3.mzn).
include "disjunctive.mzn";

int: jobs;                                    % 作业的数量
set of int: JOB = 1..jobs;
int: tasks;                                   % 每个作业的任务数量
set of int: TASK = 1..tasks;
array [JOB,TASK] of int: d;                   % 任务持续时间
int: total = sum(i in JOB, j in TASK)(d[i,j]);% 总持续时间
int: digs = ceil(log(10.0,total));            % 输出的数值
array [JOB,TASK] of var 0..total: s;          % 起始时间
var 0..total: end;                            % 总结束时间

constraint %% 保证任务按照顺序出现
    forall(i in JOB) (
        forall(j in 1..tasks-1) 
            (s[i,j] + d[i,j] <= s[i,j+1]) /\
        s[i,tasks] + d[i,tasks] <= end
    );

constraint %% 保证任务之间没有重叠
    forall(j in TASK) (
        disjunctive([s[i,j] | i in JOB], [d[i,j] | i in JOB])
    );

solve minimize end;

output ["end = \(end)\n"] ++
       [ show_int(digs,s[i,j]) ++ " " ++ 
         if j == tasks then "\n" else "" endif |
         i in JOB, j in TASK ];

约束 disjunctive 获取每个任务的开始时间数组以及它们的持续时间数组,确保每次只有一个任务是被激活的。 我们定义析取约束为一个有以下特征的 谓词

predicate disjunctive(array[int] of var int:s, array[int] of int:d);

Listing 2.3.8 中,我们可以用这个析取约束定义任务之间不重叠。 我们假设 disjunctive 谓词的定义已经在模型中引用的文件 disjunctive.mzn 中给出。

如果下层的系统直接支持 disjunctive ,则会在它的全局目录下包含一个 disjunctive.mzn 文件(拥有上述特征定义内容)。 如果我们使用的系统不直接支持析取,通过创建文件 disjunctive.mzn ,我们可以给出我们自己的定义。最简单的实现是单单使用上面定义的 no_overlap 谓词。 一个更好的实现是利用全局约束 cumulative ,假如下层求解器支持它的话。 Listing 2.3.9 给出了一个 disjunctive 的实现。 注意我们使用 index_set 反射函数来(a)检查 disjunctive 的参数是有意义的,以及(b)构建 cumulative 的合适大小的资源利用数组。另外注意这里我们使用了 assert 的三元组版本。

Listing 2.3.9 使用 cumulative 来定义一个 disjunctive 谓词 (disjunctive.mzn).
include "cumulative.mzn";

predicate disjunctive(array[int] of var int:s, array[int] of int:d) =
          assert(index_set(s) == index_set(d), "disjunctive: " ++
          "first and second arguments must have the same index set",
            cumulative(s, d, [ 1 | i in index_set(s) ], 1)
          );

2.3.5. 局部变量

在谓词,函数或者测试中,引进 局部变量 总是非常有用的。 表达式 let 允许你去这样做。 它可以被用来引进决策变量 决策变量 和 参数 ,但是参数必须被初始化。 例如:

var s..e: x;
let {int: l = s div 2; int: u = e div 2; var l .. u: y;} in x = 2*y

引进了参数 lu 以及变量 ylet 表达式虽然在 谓词 , 函数 和测试定义中最有用,它也可以被用在其他的表达式中。例如,来消除共同的子表达式:

constraint let { var int: s = x1 + x2 + x3 + x4 } in
           l <= s /\ s <= u;

局部变量可以被用在任何地方,在简化复杂表达式时也很有用。 通过使用局部变量来定义目标 objective 函数而不是显式地加入很多个变量, Listing 2.3.10 给出了稳定婚姻模型的一个改进版本。

Listing 2.3.10 使用局部变量来定义一个复杂的目标函数 (wedding2.mzn).
enum Guests = { bride, groom, bestman, bridesmaid, bob, carol, 
  ted, alice, ron, rona, ed, clara}; 
set of int: Seats = 1..12;
set of int: Hatreds = 1..5;
array[Hatreds] of Guests: h1 = [groom, carol, ed, bride, ted];
array[Hatreds] of Guests: h2 = [clara, bestman, ted, alice, ron];
set of Guests: Males = {groom, bestman, bob, ted, ron,ed};
set of Guests: Females = {bride,bridesmaid,carol,alice,rona,clara}; 

array[Guests] of var Seats: pos; % 客人的座位

include "alldifferent.mzn";
constraint alldifferent(pos);

constraint forall(g in Males)( pos[g] mod 2 == 1 );
constraint forall(g in Females)( pos[g] mod 2 == 0 );

constraint not (pos[ed] in {1,6,7,12});
constraint abs(pos[bride] - pos[groom]) <= 1 /\ 
           (pos[bride] <= 6 <-> pos[groom] <= 6);

solve maximize sum(h in Hatreds)(
          let {  var Seats: p1 = pos[h1[h]];
                 var Seats: p2 = pos[h2[h]];
                 var 0..1: same = bool2int(p1 <= 6 <-> p2 <= 6); } in   
          same * abs(p1 - p2) + (1-same) * (abs(13 - p1 - p2) + 1));

output [ show(g)++" " | s in Seats,g in Guests where fix(pos[g]) == s]
       ++ ["\n"]; 

2.3.6. 语境

有一个局限,即含有决策变量并且在声明时没有初始化的谓词和函数不可以被用在一个否定语境下。下面例子是非法的

predicate even(var int:x) =
          let { var int: y } in x = 2 * y;

constraint not even(z);

原因是求解器只解决存在约束的问题。如果我们在否定语境下引入了一个局部变量,则此变量是 普遍地量化 了,因此超出下层求解器的解决范围。例如, \(\neg \mathit{even}(z)\) 等价于 \(\neg \exists y. z = 2y\) ,然后等价于 \(\forall y. z \neq 2y\)

如果局部变量被赋了值,则它们可以被用在否定语境中。下面的例子是合法的

predicate even(var int:x) =
          let { var int: y = x div 2; } in x = 2 * y;

constraint not even(z);

注意,现在 even 的意思是正确的,因为如果 x 是偶数,则 \(x = 2 * (x ~\mbox{div}~ 2)\) 。 由于 math:y\(z\) 功能性定义了, \(\neg \mathit{even}(z)\) 等价于 \(\neg \exists y. y = z ~\mbox{div}~ 2 \wedge z = 2y\) ,同时等价于 \(\exists y. y = z ~\mbox{div}~ 2 \wedge \neg z \neq 2y\)

MiniZinc中的任意表达式都出现在以下四种 语境 中的一种中: 根 , 肯定 , 否定 ,或者 混合 。 非布尔型表达式的语境直接地为包含其最近的布尔型表达式的语境。唯一的例外是目标表达式出现在一个根语境下(由于它没有包含其的布尔型表达式)。

为了方便定义语境,我们把蕴含表达式 e1 -> e2 等价地写为 not e1 \/ e2e1 <- e2 等价地写为 e1 \/ not e2

一个布尔型表达式的语境可能有:

根语境是任何作为 constraint 的参数或者作为一个赋值项 assignment 出现的表达式 \(e\) 的语境,或者作为一个出现在根语境中的 e1 /\ e2 的子表达式 e1e2 的语境。

根语境下的布尔型表达式必须在问题的任何模型中都满足。

肯定

肯定语境是任何作为一个出现在根语境或者肯定语境中的 e1 \/ e2 的子表达式 e1e2 的语境,或者是作为一个出现在肯定语境中的 e1 /\ e2 的子表达式 e1e2`的语境,或者是作为一个出现在否定语境中的 :mzn:`not e 的子表达式 e 的语境。

肯定语境下的布尔型表达式不是必须要在模型中满足,但是满足它们会增加包含其的约束被满足的可能性。对于一个肯定语境下的表达式,从包含其的根语境到此表达式有偶数个否定。

否定

否定语境是任何作为一个出现在根语境或者否定语境中的 e1 \/ e2e1 /\ e2 的子表达式 e1e2 ,或者是作为一个出现在肯定语境中的 not e 的子表达式 e 的语境。

否定语境下的布尔型表达式不是必须要满足,但是让它们成假会增加包含其的约束被满足的可能性。对于一个否定语境下的表达式,从包含其的根语境到此表达式有奇数个否定。

混合

混合语境是任何作为一个出现在 e1 <-> e2 , e1 = e2 或者 bool2int(e) 中的子表达式 e1e2 的语境。

混合语境下的表达式实际上既是肯定也是否定的。通过以下可以看出:e1 <-> e2 等价于 (e1 /\ e2) \/ (not e1 /\ not e2) 以及 x = bool2int(e) 等价于 (e /\ x=1) \/ (not e /\ x=0)

观察以下代码段

constraint x > 0 /\ (i <= 4 -> x + bool2int(x > i) = 5);

其中 x > 0 在根语境中, i <= 4} 在否定语境中, x + bool2int(x > i) = 5 在肯定语境中, x > i 在混合语境中。

2.3.7. 局部约束

Let表达式也可以被用来引入局部约束,通常用来约束局部变量的行为。 例如,考虑只利用乘法来定义开根号函数:

function var float: mysqrt(var float:x) =
         let { var float: y;
               constraint y >= 0;
               constraint x = y * y; } in y;

局部约束确保了 y 取正确的值;而此值则会被函数返回。

局部约束可以在let表达式中使用,尽管最普遍的应用是在定义函数时。

Let表达式

局部变量 可以在任何以下格式的emph{let表达式}中引入:

let { <声明>; ... <声明> ; } in <表达式>

声明 <dec> 可以是决策变量或者参数(此时必须被初始化)或者约束项的声明。 任何声明都不能在一个新的声明变量还没有引进时使用它。

注意局部变量和约束不可以出现在测试中。局部变量不可以出现在 否定 或者 混合 语境下的谓词和函数中,除非这个变量是用表达式定义的。

2.3.8. 定义域反射函数

其他重要的反射函数有允许我们对变量定义域进行访问的函数。表达式 lb(x) 返回一个小于等于 x 在一个问题的解中可能取的值的数值。 通常它会是 x 声明的下 限 。如果 x 被声明为一个非有限类型,例如, 只是 var int ,则它是错误的。 类似地,表达式 dom(x) 返回一个$x$在问题的任何解中的可能值的(非严格)超集。 再次,它通常是声明的值,如果它不是被声明为有限则会出现错误。

Listing 2.3.11 使用反射谓词 (reflection.mzn).
var -10..10: x;
constraint x in 0..4;
int: y = lb(x);
set of int: D = dom(x);
solve satisfy;
output ["y = ", show(y), "\nD = ", show(D), "\n"];

例如, Listing 2.3.11 中的模型或者输出

y = -10
D = -10..10
----------

y = 0
D = {0, 1, 2, 3, 4}
----------

或任何满足 \(-10 \leq y \leq 0\)\(\{0, \ldots, 4\} \subseteq D \subseteq \{-10, \ldots, 10\}\) 的答案。

变量定义域反射表达式应该以在任何安全近似下都正确的的方式使用。但是注意这个是没有被检查的!例如加入额外的代码

var -10..10: z;
constraint z <= y;

不是一个定义域信息的正确应用。因为使用更紧密(正确的)近似会比使用更弱的初始近似产生更多的解。

定义域反射

我们有查询包含变量的表达式的可能值的反射函数:

  • dom(<表达式>) 返回 <表达式> 所有可能值的安全近似。
  • lb(<表达式>) 返回 <表达式> 下限值的安全近似。
  • ub(<表达式>) 返回 <表达式> 上限值的安全近似。

lbub 的表达式必须是 intboolfloat 或者 set of int 类型。 dom 中表达式的类型不能是 float 。 如果 <表达式> 中的一个变量有一个 非有限声明类型 (例如, var intvar float 类型),则会出现一个错误。

我们也有直接作用于表达式数组的版本(有类似的限制):

  • dom_array(<数组表达式>): 返回数组中出现的表达式的所有可能值的并集的一个安全近似。
  • lb_array(<数组表达式>) 返回数组中出现的所有表达式的下限的安全近似。
  • ub_array(<数组表达式>) 返回数组中出现的所有表达式的下限的安全近似。

谓词,局部变量和定义域反射的结合使得复杂全局约束通过分解定义变为可能。 利用 Listing 2.3.12 中的代码,我们可以定义 cumulative 约束的根据时间的分解。

Listing 2.3.12 利用分解来定义一个 谓词 (cumulative.mzn).
%--------------------------------------------------------------------%
% 需要给出一个任务集合,其中起始时间为's', 
% 持续时间'd'以及资源需求量'r',
% 任何时候需求量都不能超过
% 一个全局资源界限'b'。
% 假设:
% - forall i, d[i] >= 0 and r[i] >= 0
%--------------------------------------------------------------------%
predicate cumulative(array[int] of var int: s,
                     array[int] of var int: d,
                     array[int] of var int: r, var int: b) =
   assert(index_set(s) == index_set(d) /\ 
          index_set(s) == index_set(r),
     "cumulative: the array arguments must have identical index sets",
   assert(lb_array(d) >= 0 /\ lb_array(r) >= 0,
     "cumulative: durations and resource usages must be non-negative",
           let { 
               set of int: times =
                 lb_array(s) ..
                 max([ ub(s[i]) + ub(d[i]) | i in index_set(s) ]) 
               } 
           in
              forall( t in times ) (
                 b >= sum( i in index_set(s) ) (
                    bool2int( s[i] <= t /\ t < s[i] + d[i] ) * r[i]
                 )
              )
       )
   );

这个分解利用 lbub 来决定任务可以执行的时间范围集合。 接下来,它对 times 中的每个时间 times 都断言在此时间 t 激活的所有任务所需要的资源量总和小于界限 b

2.3.9. 作用域

MiniZinc中声明的作用域值得我们简单地介绍下。 MiniZinc只有一个作用域,所以出现在声明中的所有变量都可以在模型中的每个表达式中可见。 用以下几个方式,MiniZinc引进局部作用域变量:

  • 推导式表达式 中的 迭代器
  • 使用 let 表达式
  • 谓词和函数中的 参数

任何局部作用域变量都会覆盖同名称的外部作用域变量。

Listing 2.3.13 阐述变量作用域的模型 (scope.mzn).
int: x = 3;
int: y = 4;
predicate smallx(var int:y) = -x <= y /\ y <= x;
predicate p(int: u, var bool: y) = 
      exists(x in 1..u)(y \/ smallx(x));
constraint p(x,false);
solve satisfy;

例如,在 Listing 2.3.13 中给出的模型中, -x <= y 中的 x 是全局 xsmallx(x) 中的 x 是迭代器 x in 1..u ,而析取中的 y 是谓词的第二个参数。