优化建模之MiniZinc(四) 复杂逻辑约束和调度问题实例

2020-11-30 本文已影响0人 ChaoesLuol

笔者对MiniZinc的学习多有赖于Coursera上的modelling for discrete modeling》系列以及MiniZinc的tutorial，如果对离散优化建模有兴趣，花些时间去上墨尔本大学和香港中文大学的这一系列课程必然能有所裨益。

约束的本质

实际上在求解器中，约束就是一系列的True or False。无论多么复杂的约束，本质上也就是布尔表达式。

既然明了约束的本质，那么复杂逻辑约束也无非就是通过逻辑联结词串联的一系列简单逻辑约束的组合。

值得一提的是，通常在求解器中，会用整数0和1来替代False和True，通过MiniZinc中内置的bool2int函数，我们可以将布尔表达式显式转化为整数。

逻辑联结词(Logical Connectives)

在数理逻辑中，常用的联结词有5个，下面一一介绍在MiniZinc中的对应形式

合取(Conjunction)：MiniZinc中用/\表示，a /\ b用自然语言描述就是 a and b
析取(Disjunction)：MiniZinc中用\/表示，a \/ b用自然语言描述就是a or b
等价(Biconditional)：MiniZinc中用<->表示，a <-> b 用自然语言表示就是a if and only if b
蕴含(Material implication)：MiniZinc中用->表示，a -> b用自然语言表示就是if a then b
否定(Negation)：MiniZinc中用not表示，not a意义就等同于自然语言表示了

求解器中对复杂逻辑约束的处理

各个求解器中有不同的处理复杂逻辑约束的技术，但是总体来说，求解器对于非合取约束会使用一种称为具体化的奇数。

对于非合取约束(否定式、析取式)，求解器会为该约束附上一个布尔变量，使得：

如果该约束满足，那么变量取true
如果约束不满足，那么变量取false

例如constraint x>y \/ not p(x,y);会被求解器拆分为：

constraint b1 <-> x>y; constraint b2 <-> p(x,y); constraint b1 \/ not b2;

了解这一点，可以帮助我们明了不同的约束表达效率的高下。

低效的约束表达

约束优化的求解器很多都是基于”约束满足“技术来实现求解的，它们一般接受一组变量以及一组处于合取关系的约束，并尝试返回解。

其中一些类型的约束是求解器处理起来效率比较低的：

否定式not x = y：求解器比较难以处理否定形式，因此我们通常希望把它替换为取反形式x != y
析取式c1 \/ c2：尽可能尝试化简或者在可能的情况下用合取式来替换
bool2int：
蕴含式c1->c2：最好令c1特别简单
存在exists([...])：效率比较低，尽可能不要使用，在循环操作中forall要比exists高效的多

调度问题

调度问题通常指一系列任务需要分配到一些资源上，满足某些约束，并且优化一个特定的目标函数。经典的调度问题有车间生产调度、计算机中任务的调度等等。

涉及的概念：

任务：每个任务都具有开始时间，持续时间，其他属性。

array[TASK] of var int: start;

array[TASK] of var int: duration;

优先次序：某个任务要先于另一个任务完成。这在调度问题中是非常常见的一类约束，例如一个零件必须要先进行热处理才能进行机加工，例如洗车时要先完成清洗才能打蜡，等等。

start[t1] + duration[t1] <= start[t2]

资源受限项目调度问题(Resource constrained project scheduling problem, RCPSP)

资源受限项目调度问题是调度问题中非常经典的一类。在这类调度问题中，我们的每个资源都有若干个副本，也就是说在同一时间任意一种资源都有有限的数量，能用于满足各种工作需求。在实际场景中，比如我们对应每种机加工的机床都有若干台，或者我们任务调度时，有若干个CPU核心可供使用，或者我们在每家医院中，都有给定数量的病床等。

对资源占用的建模

解决RCPSP的主要难点在于怎么对多个资源副本的占用情况进行建模：

我们假设任务 $t$ 使用 $res[t]$ 份资源
假设在任何时刻，对某种资源的占用都有个最大限度 $L$

那么我们可以顺着时间或者任务的思路，对这个约束进行建模：

基于时间的分解：在每个时间点 $i$ ，资源的使用都少于给定的限度 $L$

forall(i in TIME)(sum(t in TASK)((start[t] <= i /\ start[t] + duration[t] > i) * res[t]) <= L);

这种分解存在一些问题：

约束数目为 $card(TIME)*card(TASK)$ ，规模太大，通常来说主要问题在于我们的 $card(TIME)$ 可能会很大
当时间区间为浮点数时，区间的分割方式就并不那么显而易见了

基于任务的分解：注意到资源使用超量的情况只会发生在某个任务开始时，因此我们只需要在任务的开始时间检查资源的使用情况即可：

forall(t2 in TASK)(sum(t in TASK)((start[t] <= start[t2] /\ start[t] + duration[t] > start[t2]) * res[t]) <= L);

当然，考虑到 t 和 t2应该是不等的，上面的表述还可以进行一定优化：

forall(t2 in TASK)(sum(t in TASK where t != t2)((start[t] <= start[t2] /\ start[t] + duration[t] > start[t2]) * res[t]) + res[t2] <= L);

此时的约束数目为 $card(TASK)^2$ ，在通常情况下要比基于时间的分解少很多。

MiniZinc的全局约束cumulative

cumulative(<开始时间数组>, <持续时间数组>, <资源使用数组>, <资源使用限度>)

保证任务进行时任何时间点资源的使用量都不超过限度

注意cumulative中开始时间数组可以不是确切的值，也可以以一个范围的形式给出，如cumulative([0..3, 0..3, 2..3, 0..4], [4,3,2,3],[2,1,2,3],4)

实例与模型求解

我们可以来看一个例子，假设我们在处理多CPU下的任务调度，我们有3个处理器和7个任务，每个任务的用时分别为2, 14, 4, 16, 6, 5, 3个单位时间。同时任务有一定的先后顺序要求，任务1要先于任务4完成，任务3要先于任务7完成。求一个总用时最少的任务分配方案。

这里我们用第二种方式，也就是基于任务的分解对问题进行建模，得到如下模型文件4_1_JobScheduling.mzn

% 分离调度问题

%--------------------------
% 数据部分
enum TASK; % 所有工作的枚举类型
enum RESOURCE; % 所有资源的枚举类型，在这个问题中，使我们的CPU
int: n_task; % 工作的数量
int: n_resource; % 资源的数量
int: n_pred; % 优先次序关系的数量
int: max_time = 100; % 估算一个最大用时
array[TASK] of int: duration; % 完成每个任务需要的时长
array[1..n_pred, 1..2] of TASK: precedence; % 要求的优先次序


%--------------------------
% 决策变量
array[TASK] of var 0..max_time: start;

%--------------------------
% 约束
% 1. 由于我们的资源副本之间没有区别，并不需要额外区分放在哪个CPU中执行，因此要求每个时间点的资源使用数 < 给定资源数量即可
constraint forall(t2 in TASK)(sum(t in TASK where t != t2)
    (start[t] <= start[t2] /\ start[t] + duration[t] > start[t2]) <= n_resource - 1);
% 2. 保证任务的先后次序
constraint forall(i in 1..n_pred)
    (start[precedence[i, 1]] + duration[precedence[i,1]] <= start[precedence[i, 2]]);

%--------------------------
% 目标函数
var 0..max_time: makespan = max([start[t] + duration[t] | t in TASK]);
solve minimize makespan;

%--------------------------
% 输出
output ["Starting time of jobs: \(start)\nMinimal time span: \(makespan)"];

建立数据文件4_1_JobScheduling.dzn：

TASK = {t1, t2, t3, t4, t5, t6, t7}; % 所有工作
RESOURCE = {c1, c2, c3}; % 所有资源
n_task = 7; % 工作的数量
n_resource = 3; % 资源的数量
n_pred = 2; % 优先次序关系的数量
duration = [2, 14, 4, 16, 6, 5, 3];
precedence = [| t1, t4
              | t3, t7|]; % 任务的优先次序

求解之后得到答案：

Starting time of jobs: [0, 1, 5, 2, 9, 0, 15]
Minimal time span: 18
----------
==========

可视化之后，可以得到下面的一个类甘特图，可以看到我们的任务优先次序也得到了满足：

4_1 JobScheduling