模型的抽象化

具體模型與抽象模型

具體模型

在第一篇文章中我們介紹了MiniZinc程序的基本組成部分。

作為復(fù)習(xí)，我們可以看一個生產(chǎn)規(guī)劃問題：

我們在邊境和印軍相持，因為不能開槍，我們要生產(chǎn)一批冷兵器來武裝部隊，可選的選項有長矛、劍和錘子；生產(chǎn)武器需要消耗一些資源和工匠的時間，武器對應(yīng)的資源消耗如下：

我們的資源是有限的：

每樣武器對應(yīng)一定的戰(zhàn)斗力：

我們希望充分利用有限的資源來最大化我們的部隊?wèi)?zhàn)斗力，那么每樣武器需要生產(chǎn)多少件呢？

對應(yīng)的模型如下：

% 混料問題的模型
%--------------------------
% 數(shù)據(jù)部分
enum RESOURCES = {wood, iron, blacksmith_hour, carpenter_hour}; % 需要的資源
enum WEAPONS = {spear, sword, hammer}; % 生產(chǎn)的武器
array[WEAPONS, RESOURCES] of float: consumption = [|2.5, 0.5, 1.0, 3.7
                                                   |0.4, 4.2, 5.1, 1.2
                                                   |3.5, 4.5, 7.0, 2.7|]; % 生產(chǎn)每種武器需要的資源
array[RESOURCES] of float: res_amount = [5000.0, 2000.0, 4000.0, 3250.5]; % 每種資源的數(shù)量
array[WEAPONS] of float: power = [12.5, 17.0, 23.8]; % 每種武器的威力

%--------------------------
% 決策變量
array[WEAPONS] of var int: weapon_amount;

%--------------------------
% 約束
% 每種武器的數(shù)量都必須為非負(fù)數(shù)
constraint forall(w in WEAPONS)(weapon_amount[w] >= 0);
% 武器的資源消耗要不大于最大資源數(shù)量
constraint forall(r in RESOURCES)(
                 (sum(w in WEAPONS)(consumption[w, r] * weapon_amount[w])) <= res_amount[r]);

%--------------------------
% 目標(biāo)函數(shù)
var float: total_power = sum(w in WEAPONS)(power[w] * weapon_amount[w]);
solve maximize total_power;

%--------------------------
% 輸出
output ["Amount of weapon " ++ show(w) ++ " : " ++ show_int(8, weapon_amount[w]) ++ "\n" | w in WEAPONS]
        ++ ["Total power: " ++ show_float(6, 2, total_power)];

通過求解，我們可以得到答案：

Amount of weapon spear :      603
Amount of weapon sword :        0
Amount of weapon hammer :      377
Total power: 16510.10
----------
==========

模型中關(guān)于數(shù)組和一些內(nèi)置函數(shù)，可以往下拉到后面看對MiniZinc語法的解釋。

抽象模型

上面這個模型看起來沒有什么問題，求解也很順利。但是在很多情況下，我們建模時會面臨一系列what-if的問題：如果我資源多一些，會怎么樣？如果我增加一些兵器種類供選擇，會怎么樣？

我們需要不斷修改上面的具體模型，來應(yīng)付不斷變動的數(shù)據(jù)。

如果我們不是在求解一個武器生產(chǎn)問題，而是在規(guī)劃我們的期末復(fù)習(xí)計劃呢？我們是不是需要重寫整個模型呢？

在軟件工程的實踐中，設(shè)計模式給我們的重要啟示就是將變動的部分和相對穩(wěn)定的部分分開，對我們的模型來說也是一樣，同一類的生產(chǎn)規(guī)劃模型中有一些共同點，我們可以抽取其想通部分，然后將數(shù)據(jù)單獨分開。

生產(chǎn)規(guī)劃模型

在生產(chǎn)規(guī)劃模型中，我們可以提取一些共同之處：

• 對給定的資源種類，每種資源都有量的限制
• 生產(chǎn)每種產(chǎn)品會消耗不同數(shù)量的各類資源
• 不同產(chǎn)品能帶來不同的收益
• 通常我們需要最大化收益

根據(jù)這些共同特點，我們可以生成一個抽象的模型(2_2_AbstractProductionModel.mzn)：

% 抽象的生產(chǎn)問題模型

%--------------------------
% 數(shù)據(jù)部分
enum RESOURCES; % 用于生產(chǎn)的資源
enum PRODUCTS; % 生產(chǎn)的產(chǎn)品
array[PRODUCTS, RESOURCES] of float: consumption; % 生產(chǎn)每種產(chǎn)品所需要的資源數(shù)量
array[RESOURCES] of float: capacity; % 每種資源的額度
array[PRODUCTS] of float: profit; % 每種產(chǎn)品可以提供的收益

%--------------------------
% 決策變量
array[PRODUCTS] of var int: produce_num;

%--------------------------
% 約束
% 資源消耗少于額度
constraint forall(r in RESOURCES)
        (sum(p in PRODUCTS)(consumption[p, r] * produce_num[p]) <= capacity[r]);
% 每種產(chǎn)品數(shù)量必須為非負(fù)
constraint forall(p in PRODUCTS)(produce_num[p] >= 0);

%--------------------------
% 目標(biāo)函數(shù)
var float: total_profit = sum(p in PRODUCTS)(produce_num[p] * profit[p]);
solve maximize total_profit;

%--------------------------
% 輸出
output ["Amount of product " ++ show(p) ++ " : " ++ show_int(8, produce_num[p]) ++ "\n" | p in PRODUCTS]
        ++ ["Total profit: " ++ show_float(6, 2, total_profit)];

我們可以看到在抽象模型中，沒有包含任何數(shù)據(jù)。這樣我們就分開了模型和數(shù)據(jù)，對于同樣一個模型，我們可以用來求解性質(zhì)相同的不同數(shù)據(jù)集了。

為了驗證，我們可以將我們上面的武器生產(chǎn)問題建立一個獨立的數(shù)據(jù)集2_2_WeaponProduction.dzn如下：

RESOURCES= {wood, iron, blacksmith_hour, carpenter_hour};
PRODUCTS = {spear, sword, hammer};
consumption = [|2.5, 0.5, 1.0, 3.7
               |0.4, 4.2, 5.1, 1.2
               |3.5, 4.5, 7.0, 2.7|];
capacity = [5000.0, 2000.0, 4000.0, 3250.5];
profit = [12.5, 17.0, 23.8];

在命令行中運(yùn)行minizinc --solver CBC 2_2_AbstractProductionModel.mzn 2_2_WeaponProduction.dzn指定數(shù)據(jù)集和求解器進(jìn)行求解，得到結(jié)果：

Amount of product spear :      603
Amount of product sword :        0
Amount of product hammer :      377
Total profit: 16510.10
----------
==========

可以看到對于武器生產(chǎn)問題，我們得到的結(jié)果和前面一樣。

自習(xí)時間分配問題

抽象模型的好處在于可以用同一個模型處理一類問題。用之前建立的生產(chǎn)問題模型，我們可以來看看下面的一個時間分配問題：

我們面臨有三門課的期末考試，分別是運(yùn)籌學(xué)、離散數(shù)學(xué)和C語言，對于每種課程的復(fù)習(xí)，一種較理想的方案是分別分配一定的上機(jī)復(fù)習(xí)、討論和書本自習(xí)，各門課程理想復(fù)習(xí)方案的時間比例如下：

但是由于機(jī)房、討論室和自習(xí)室各自有一定時間限制，我們在考試來之前能夠約到的時間如下：

每花一個小時在不同科目上，我們能夠提高不同的平均GPA：

假設(shè)我們起點很低，這輪復(fù)習(xí)不會將任何科目的GPA刷滿，但是我們希望將GPA盡量刷高一點，那么應(yīng)該怎么分配剩余的復(fù)習(xí)時間呢？

我們發(fā)現(xiàn)這個問題其實也是生產(chǎn)問題的一類，我們并不需要對模型進(jìn)行任何的改動，只需要將數(shù)據(jù)集進(jìn)行修改即可。我們建立一個數(shù)據(jù)文件2_2_SwotUp.dzn放入相應(yīng)的課程、用時和收益：

RESOURCES= {computer_work, discussion_room, desk_work};
PRODUCTS = {operation_research, discrete_math, C_language};
consumption = [|0.3, 0.5, 0.2
               |0.2, 0.4, 0.4
               |0.6, 0.1, 0.3|];
capacity = [10.5, 7.0, 12.0];
profit = [0.2, 0.15, 0.1];

在命令行運(yùn)行minizinc --solver CBC 2_2_AbstractProductionModel.mzn 2_2_SwotUp.dzn進(jìn)行求解：

得到結(jié)果：

Amount of product operation_research :        6
Amount of product discrete_math :        7
Amount of product C_language :       12
Total profit:   3.45
----------
==========

小節(jié)

• 具體模型中，數(shù)據(jù)及其定義是放在一起的，不能靈活修改，因此只能用來解決特定的問題。

• 通過將數(shù)據(jù)和模型分開， 并對模型進(jìn)行抽象化，我們可以用同一個模型來應(yīng)對不同規(guī)模的數(shù)據(jù)集，此外這個模型還可以用來解決一類問題，而非僅僅針對某一個特定問題。

• 除了應(yīng)用更加方便外，定義抽象模型和一個較小的數(shù)據(jù)，可以方便我們對復(fù)雜模型進(jìn)行debug。

因此，在建模時，通常建議對模型進(jìn)行抽象化，將模型文件和數(shù)據(jù)文件分開來。

MiniZinc中的一些語法知識

數(shù)組和推導(dǎo)式

在上面的程序中，我們用到了如下語句：

array[WEAPONS, RESOURCES] of float: consumption = [|2.5, 0.5, 1.0, 3.7
                                                   |0.4, 4.2, 5.1, 1.2
                                                   |3.5, 4.5, 7.0, 2.7|]; % 生產(chǎn)每種武器需要的資源

這條語句定義了一個二維數(shù)組consumption，其維度分別為WEAPONS和RESOURCES。

數(shù)組是一個比較常用的數(shù)據(jù)結(jié)構(gòu)，下面我們會介紹一下數(shù)組的相關(guān)知識：

數(shù)組的聲明

數(shù)組可以是一維或者多維的，在聲明時使用如下格式：

array[index_set1, index_set2,...] of <type>

數(shù)組下標(biāo)的集合可以是枚舉類型或者是某個集合表達(dá)式。

數(shù)組內(nèi)的元素可以是除了數(shù)組以外的任何內(nèi)置類型，也就是說MiniZinc不支持?jǐn)?shù)組嵌套。

數(shù)組的初始化

一維數(shù)組

對于一維數(shù)組，我們可以用列表的方式進(jìn)行初始化，這和大多數(shù)其他語言一樣，比如下面這些例子：

profit = [100, 200, 300];
cost = [0.2, 0.3, 0.5];

二維數(shù)組

MiniZinc中二維數(shù)組的初始化有特定的語法：

• 起始于符號[|
• 用|來分割行
• 結(jié)束于符號|]

一個例子就是我們上面定義的二維數(shù)組：

consumption = [|2.5, 0.5, 1.0, 3.7
                     |0.4, 4.2, 5.1, 1.2
                             |3.5, 4.5, 7.0, 2.7|];

特別需要注意結(jié)尾，不要忘記|符號。

內(nèi)置函數(shù)初始化任意維度數(shù)組

對于任何維度k不大于6的數(shù)組，我們都可以用內(nèi)置函數(shù)arraykd來進(jìn)行初始化，例如：

profit = array1d(1..3, [100, 200, 300]);
consumption = array2d(1..3, 1..4,
                            [2.5, 0.5, 1.0, 3.7,
                     0.4, 4.2, 5.1, 1.2,
                             3.5, 4.5, 7.0, 2.7]);

分別等價于我們上面的一維和二維數(shù)組初始化方式。

推導(dǎo)式

除了使用內(nèi)置函數(shù)或者列表形式來進(jìn)行初始化意外，MiniZinc也提供了和Python一樣的推導(dǎo)式方式對數(shù)組進(jìn)行初始化。其語法為：

[<expression>| <generator-expr1>, <generator-expr2>,...]

在推導(dǎo)過程中我們也可以進(jìn)行一些檢驗：

[<expression>| <generator-expr1>, <generator-expr2>, ..., where <bool-expr>]

例如

array[int] of int: u = [i + j | i in 1..3, j in 2..5];
array[int] of int: v = [i * j | i in 2..6, j in 3..7 where i * j <= 20];

會生成下面的兩個數(shù)組

[3, 4, 5, 6, 4, 5, 6, 7, 5, 6, 7, 8]
[6, 8, 10, 12, 14, 9, 12, 15, 18, 12, 16, 20, 15, 20, 18]

注意這里因為我們事先不知道數(shù)組的長度，我們用了array[int]來讓求解器自己推導(dǎo)數(shù)組長度。

相應(yīng)的，集合也可以用推導(dǎo)式的方式生成，唯一的不同就是用{}替換[]。

獲得數(shù)組的下標(biāo)

因為在列表推導(dǎo)式的運(yùn)用，我們可能產(chǎn)生不知道列表下標(biāo)范圍的情況。此時我們可以使用內(nèi)置函數(shù)index_set來獲得一維數(shù)組的下標(biāo)范圍。

例如：

array[int] of int: u = [i + j | i in 1..3, j in 2..5];
set of int: k = index_set(u);

這里我們的k會得到范圍1..12。

對于多維數(shù)組，我們需要指定數(shù)組的總維度k和我們想知道具體哪個維度m的下標(biāo)。

MiniZinc中內(nèi)置了一系列函數(shù)index_set_<m>of<k>來幫助我們得到下標(biāo)，其中k<=6。例如我們想得到二維數(shù)組第二個維度的下標(biāo)，我們就可以使用函數(shù)index_set_2of2。

基礎(chǔ)運(yùn)算

四則運(yùn)算

MiniZinc中支持的整數(shù)運(yùn)算有基礎(chǔ)的四則運(yùn)算加減乘除：+, -, *, div。對于浮點數(shù)，除法表示為/。

<u>注意這里的整數(shù)除法是div而非/，/在MiniZinc中特指浮點數(shù)的除法</u>，處理整數(shù)時可能得到意料之外的結(jié)果。

除此之外還有我們常用的取余mod，整數(shù)的取余運(yùn)算a mod b會得到和a同號的結(jié)果，也就是說一定有a = b * (a div b) + (a mod b)。

內(nèi)置的運(yùn)算函數(shù)

下面給出一些在MiniZinc中常用的內(nèi)置運(yùn)算函數(shù)。

對于數(shù)字：

• abs(n) - 返回數(shù)字n的絕對值。
• pow(n, k) - 返回n的k次冪。

對于數(shù)組：

• product(array) -返回數(shù)組array的連乘，注意對于空數(shù)組，product返回1。
• sum(array) - 返回數(shù)組array的和，對于空數(shù)組，返回0。
• min(array) - 返回數(shù)組array的最小值，對于空數(shù)組，是未定義行為，會返回一個run-time error。
• max(array) - 返回數(shù)組array的最大值，對于空數(shù)組，是未定義行為，會返回一個run-time error。
• has_element(e, array) - 返回一個bool類型，如果array中含有e，返回true否則返回false