Constraint Programming Minizinc 约束性编程学习笔记_约束求解 minizinc

前言

简单点说约束性编程就是解决“鸡兔同笼”这类的问题，也就是说一个笼子里放多少个兔子放多少个鸡这种有约束条件的问题。创作出模型而让计算机代替大量的计算可能性。个人感觉这个在我们日常生活中真的很实用。比如给几个员工拍个工作时间表，在某些时段不能冲突，或者某些人在某个时段不能安排。通过设定一些约束条件然后得出结果。我们需要做的就是输入限制条件，所有的计算都由程序来做。我觉得是很贴近生活并实用的一门编程方法。

当然用比较常用的编程语言也可以实现约束性编程，但是Minizinc是用来做约束性编程的一个实用的语言，用它可以更简洁直观的完成约束性编程。直接去他的官网下载IDE并有教程，但是教程主要是英文版，语言学习部分有中文版，但是感觉翻译的很牵强，甚至没有英文版明白的透彻。下面的学习主要通过解决问题来学习这门语言。

开始

安装：不同的系统这个可以直接下载对应的包，并安装，很简单，我用的是mac。可以下载他的MINIZINC IDE但是这个IDE没有terminal，我用IDE是VSCODE因为习惯了。VSCODE上下载一个MINIZINC的插件，VSCODE本身带有terminal所以不用再重新打开terminal更方便一些。mac上要设置一下环境变量
export PATH=/Applications/MiniZincIDE.app/Contents/Resources:$PATH
不然terminal中输入Minizinc会找不到命令。

教程（正式学习）

1.给澳大利亚涂色

要求：相邻各州颜色不能相同。

由于该Markdown不支持minizinc语法高亮，所以建议把代码拷贝到Minizinc IDE或VSCODE中查看更为方便直观

第一行注释为运行该程序命令行，直接复制在terminal中运行

aust.mzn

% minizinc --solver Gecode aust.mzn
% Colouring Australia using nc colours
% 要求：相邻区域颜色不能相同

% 设置要用的颜色数量
int: nc = 3;


% 设置决策变量取值范围
/*
设置变量可能的颜色取值，带var的是决策变量，决策变量的值是不知道的，也就是要求的值，他可以被 赋值，也可以给定一个范围，最后求出该值， 决策变量 是数学的或者逻辑的变量。 和一般的编程语言中的参数和变量不同，建模者不需要给决策变量一个值。 而是在开始时，一个决策变量的值是不知道的。只有当MiniZinc模型被执行的时候，求解系统才来决定决策变量是否可以被赋值从而满足模型中的约束。若满足，则被赋值。
*/
var 1..nc: wa;   var 1..nc: nt;  var 1..nc: sa;   var 1..nc: q;
var 1..nc: nsw;  var 1..nc: v;   var 1..nc: t;
% 按照要求图，做出限制，比如wa不能和nt值相等，并且不能和sa值相等，依次类推

constraint wa != nt;
constraint wa != sa;
constraint nt != sa;
constraint nt != q;
constraint sa != q;
constraint sa != nsw;
constraint sa != v;
constraint q != nsw;
constraint nsw != v;
solve satisfy;% 解决目标： 满足上述条件

% 输出，变量用\(x)来表示 \t为制表符，也可以用show(x)来输出变量
output [
        "wa=", show(wa),"\tnt=",show(nt),"\tsa=",show(sa),"\n",
        "q=\(q)\t nsw=\(nsw)\t v=\(v)\n",
         "t=", show(t),  "\n"];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

输出

wa=3    nt=2    sa=1
q=3      nsw=2   v=3
t=1
----------
1
2
3
4

对于每一个决策变量，我们需要给出变量可能的取值集合。这个被称为变量的 定义域 。 定义域部分可以在 变量声明 的时候同时给出， 这时决策变量的 类型 就会从定义域中的数值的类型推断出。通过使用 var 声明， 我们的每一个决策变量 被声明为定义域为一个整数类型的范围表示 1…nc ， 来表明集合 {1,2,…,nc} 。 所有数值的类型为整型，所以模型中的所有的变量是整型决策变量。

solve satisfy;
1

表明了它是什么类型的问题。 在这个例子中，它是一个 满足 问题： 我们希望给决策变量找到一个值使得约束被满足。

2.蛋糕制作问题

要求：
一个香蕉蛋糕的制作需要：
250克自发酵的面粉，
2个香蕉，
75克糖
100克黄油。
一个巧克力蛋糕的制作需要：
200克自发酵的面粉，
75克可可粉，
150克糖
150克黄油。

我们一共有
4000的自发酵面粉，
6个香蕉，
2000的糖，
500克的黄油
500克的可可粉。

一个香蕉蛋糕可以卖$4.00
一个巧克力蛋糕可以卖$4.50
解决目标：
各烤多少个香蕉蛋糕或巧克力蛋糕可以得到最大的利润。

cakes.mzn

% minizinc --solver Gecode cakes.mzn


%决策变量
var 0..6: b; % no. of banana cakes 因为只有6个香蕉所以香蕉蛋糕个数在0-6范围
var 0..6: c; % no. of chocolate cakes因为只有500黄油所以可以设置巧克力最多为6个

% 设置限制条件:所有材料不能超过总材料数量
% flour
constraint 250*b + 200*c <= 4000;
% bananas
constraint 2*b  <= 6;
% sugar
constraint 75*b + 150*c <= 2000;
% butter
constraint 100*b + 150*c <= 500;
% cocoa
constraint 75*c <= 500;

% maximize our profit 解决目标： 最大化（keyword)
solve maximize 400*b + 450*c;

% 输出变量，默认输出是输出决策变量
output ["no. of banana cakes = \(b)\n",
        "no. of chocolate cakes = \(c)\n"];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

输出：

no. of banana cakes = 2
no. of chocolate cakes = 2
----------
==========
1
2
3
4

双下划线为最优解

蛋糕制作问题用数据文件来做为输入：

cakes2.mzn

% minizinc cakes2.mzn pantry2.dzn

%设置固定变量，可以从文件读取
int: flour;  %no. grams of flour available
int: banana; %no. of bananas available
int: sugar;  %no. grams of sugar available
int: butter; %no. grams of butter available
int: cocoa;  %no. grams of cocoa available

% 检查data文件中的数据，做出限制，比如这里，保持数值不能是负数用assert关键字来做安全限制
constraint assert(flour >= 0,"Invalid datafile: " ++
                  "Amount of flour should be non-negative");%判断如果是false则输出错误并停止运行
constraint assert(banana >= 0,"Invalid datafile: " ++
                  "Amount of banana should be non-negative");
constraint assert(sugar >= 0,"Invalid datafile: " ++
                  "Amount of sugar should be non-negative");
constraint assert(butter >= 0,"Invalid datafile: " ++
                  "Amount of butter should be non-negative");
constraint assert(cocoa >= 0,"Invalid datafile: " ++
                  "Amount of cocoa should be non-negative");

% 设置决策变量
var 0..100: b; % no. of banana cakes
var 0..100: c; % no. of chocolate cakes

% flour
constraint 250*b + 200*c <= flour;
% bananas
constraint 2*b  <= banana;
% sugar
constraint 75*b + 150*c <= sugar;
% butter
constraint 100*b + 150*c <= butter;
% cocoa
constraint 75*c <= cocoa;

% maximize our profit
solve maximize 400*b + 450*c;

output ["no. of banana cakes = \(b)\n",
        "no. of chocolate cakes = \(c)\n"];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

pantry2.dzn

flour = 8000; 
banana = 11; 
sugar = 3000; 
butter = 1500; 
cocoa = 800; 
1
2
3
4
5

通过使用 命令行标示 -D string ， 小的数据文件可以被直接输入而不是必须要创建一个 .dzn 文件， 其中 string 是数据文件里面的内容。

$ minizinc cakes2.mzn -D \
     "flour=4000;banana=6;sugar=2000;butter=500;cocoa=500;"
1
2

3.偿还贷款问题

4季度分期偿还的一年短期贷款问题。

loan.mzn

% minizinc --solver osicbc loan.mzn loan1.dzn

% 变量，每个变量值能被赋值一次，变量看
var float: R;        % 季度还款
var float: P;        % 初始借贷本金
var 0.0 .. 10.0: I;  % 利率

% 中间变量
var float: B1; % 一个季度后的欠款
var float: B2; % 两个季度后的欠款
var float: B3; % 三个季度后的欠款
var float: B4; % 最后欠款
% 设置条件
constraint B1 = P * (1.0 + I) - R;
constraint B2 = B1 * (1.0 + I) - R;
constraint B3 = B2 * (1.0 + I) - R; 
constraint B4 = B3 * (1.0 + I) - R;

solve satisfy;

output [
 "Borrowing ", show_float(0, 2, P), " at ", show(I*100.0), 
 "% interest, and repaying ", show_float(0, 2, R), 
  "\nper quarter for 1 year leaves ", show_float(0, 2, B4), " owing\n"
];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

loan1.dzn

I = 0.04;
P = 1000.0;
R = 260.0;
1
2
3