开始使用MiniZinc

MiniZinc是一个用来描述整数和实数的优化约束和决策问题的语言,它允许用户以接近问题的数学公式的方式编写模型。

MiniZinc界面如下:

MiniZinc IDE

着色问题

首先来看一个简单的着色问题:以州为单位,用3种颜色为澳大利亚地图着色,相邻的两个州不能用同一种颜色。澳大利亚地图如下:

澳大利亚地图

在MiniZinc中写入如下代码:

% 用nc种颜色为澳大利亚地图着色
int: nc = 3;

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;

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;

output ["wa=\(wa) \t nt=\(nt) \t sa=\(sa)\n",
        "q=\(q) \t nsw=\(nsw) \t v=\(v)\n",
        "t=\(t)\n"];

第一行是注释,注释用%开头。

int: nc = 3; 这一行定义并赋值了nc这个参数,它是int(整数)类型,值为3.

var 1..nc : wa; 这一条语句定义了一个名为wa的决策变量,他的范围是1~nc(都包含),类型是整数。

constraint wa != nt; 这是一条约束,约束以constraint开头,这一条语句的意思是决策变量wa不能与nt相等。

solve satisfy; 这一条语句是表示这是一个满足问题。

output ["wa=\(wa) \t nt=\(nt) \t sa=\(sa)\n",
        "q=\(q) \t nsw=\(nsw) \t v=\(v)\n",
        "t=\(t)\n"];

这是输出语句,在求解之后,我们希望看到求解的结果,\(wa)表示取出wa变量的值并显示。

在界面上点击“Run”按钮,输出如下:

Compiling aust.mzn
Running aust.mzn
wa=3     nt=2    sa=1
q=3      nsw=2   v=3
t=1
----------
Finished in 398msec

最后的----------表示这是一个解。

背包问题

假设我们有一个背包,背包的容量有限。有3中水果(假设是香蕉、苹果和橙子),每种物品都有各自的价值和重量,怎样拿水果可以使背包内水果的价值最大?

背包容量:18

水果 香蕉 苹果 橙子
价值 8 19 29
重量 3 5 8

程序如下:

enum FRUIT = {BANANA, APPLE, ORGANGE};
int: capacity = 18;
array[FRUIT] of int: value = [8, 19, 29];
array[FRUIT] of int: size = [3, 5, 8];

array[FRUIT] of var int: amt;

constraint forall(i in FRUIT)(amt[i] >= 0);
constraint sum(i in FRUIT)(size[i] * amt[i]) <= capacity;

solve maximize sum(i in FRUIT)(value[i] * amt[i]);

output["Amount=", show(amt)];

enum FRUIT = {BANANA, APPLE, ORGANGE}; 这条语句定义并赋值了一个枚举型变量。

此程序还增加了数组变量:array[FRUIT] of int: value = [8, 19, 29];

此外,还用了函数forallsum。以forall函数为例,第1个()内是迭代变量,第2个()内是表达式。

constraint forall(i in FRUIT)(amt[i] >= 0); 语句表示以FRUIT中的量为迭代变量,amt中迭代变量相应的值都不小于0.

建立模型

假设有下面的生产约束模型:

生产多种产品,已知每种产品的利润和生产过程种消耗的资源,每种资源都有限。每种产品生产多少才能使利润最大?

程序如下:

enum PRODUCT;
array[PRODUCT] of float: profit;

enum RESOURCE;
array[RESOURCE] of float: capacity;

array[PRODUCT, RESOURCE] of float: consumption;

array[PRODUCT] of var int: produce;

constraint forall(p in PRODUCT)(produce[p] >= 0);
constraint forall(r in RESOURCE)(
    sum(p in PRODUCT)(consumption[p, r] * produce[p]) <= capacity[r]
    );

solve maximize sum(p in PRODUCT)(profit[p] * produce[p]);

在程序中,一些参数需要使用数据文件给定,在更改数据时只需要更改数据文件即可。模型文件的后缀名为.mzn,数据文件的后缀名为.dzn。数据文件的一个例子如下:

% filename.dzn
PRODUCT = {AP, BP, CP, DP, EP}; 
profit =  [12.0, 16.0, 13.0, 11.0, 14.0]; 
RESOURCE = {AR, BR, CR, DR}; 
capacity = [5567, 3200, 4000, 2800]; 
consumption = [| 1.3, 1.3, 1.3, 0.5
    | 0.1, 1.5, 0.3, 0.1 
    | 1.5, 0.5, 1.0, 1.0 
    | 1.6, 1.4, 1.4, 0.1 
    | 1.8, 0.7, 0.1, 1.6 |];

其中consumption是一个二维数组,其中每行以|开头,最后以|结尾。

发表评论

电子邮件地址不会被公开。 必填项已用*标注