离散优化模型的进阶 week1-2
对基本模型的提升
问题描述
一个优化问题描述如下，张飞要通过使用稻草人布置疑阵的方式来虚张声势有这样的约束：
- 疑阵有n行和n列
- 所有的稻草人高度相同
- 所有的稻草人必须临近一个真实的士兵
- 所有的稻草人前边一定要有一个比他高的真实的士兵
- 目标是将疑阵填充的最大
数据定义：
nsoldier 是真实士兵的人数
soldier代表一个士兵
soldier0代表这个位置是一个士兵或者是一个稻草人。
strawheight 是稻草人的身高
height 是所有的真实士兵的身高
还定义了最大的行数和最大的列数
决策变量
其中定义了士兵和稻草人的位置，
还有排列的行数和列数。
约束条件：
约束描述了一个士兵出现最多一次，具体来说对任意不同行且不同列的两个位置，要么其中一个是稻草人，要么两个士兵不是同一个人。
这是一个非常直观的描述，但是同时这个描述非常的没有效率。
因为我们要在我们的约束表中加入x[r1,r2]=0这个约束非常多次。以及对任何的约束，循环都会让他们加入两次。
对于一个高效的模型，一般有一下的几个特点：
- 确保不加入一个约束多次
- 确保不在循环中重复约束
- 确保尽早的在循环中加入约束
然后修改上述的模型描述
这样的修改使用了let语句定义了临时的变量，将多余的约束删除掉了。
不过我们还有更好的方法。
如果你熟悉minizinc的全局约束
可以使用
下面需要约束的是士兵出现最少一次
这样的模型同样是非常的没有效率的，这种模型的约束非常的分离。
我们使用下面的方法来修正这种模型。
下面的约束是，每一个稻草人周围都有一个真实的士兵。
这种描述使用if语句进行，但是通常优秀的模型都没有使用if语句
然后是关于身高的约束：
不过这种模型同样效率不高，我们使用一个新的变量变量来更好的描述这个问题。
在建模中应该尽量避免如下的几个问题的使用：
- not函数，如果想要使用 not a=b 请修改成 a != b
- 析取模型，如果 如 a/b如果必须使用，请确保这个模型尽量简单。
- 推断， 如果必须使用，请确保这个模型尽量简单。
- 不要在循环中使用 exist
上面的做法都会让模型变得十分的复杂。
最后建立的模型就是这个样子的：
% Parading the soldiers
int: nsoldier;
set of int: SOLDIER = 1..nsoldier;
set of int: SOLDIER0 = 0..nsoldier;
array[SOLDIER] of int: height;
int: strawheight;
int: maxr;
set of int: ROW = 1..maxr;
int: maxc;
set of int: COL = 1..maxc;
var ROW: nrow; % size of rectangle of soldiers
var COL: ncol;
array[ROW,COL] of var SOLDIER0: x;
% all real soldiers appear in the first nrow rows and ncol cols
%constraint forall(r in nrow+1..maxr, c in ncol+1..maxc)
% (x[r,c] = 0);
constraint forall(r in ROW, c in COL)
( (r > nrow -> x[r,c] = 0)
/\ (c > ncol -> x[r,c] = 0));
% soldiers are different positions
%constraint forall(r1, r2 in ROW, c1, c2 in COL where r1 != r2 \/ c1 != c2)
% (x[r1,c1] = 0 \/ x[r1,c1] != x[r2,c2]);
%constraint forall(i in 1..maxr*maxc)
% (let {int: r1 = (i-1) div maxc + 1;
% int: c1 = (i-1) mod maxc + 1; } in
% x[r1,c1] = 0 \/
% forall(j in i+1..maxr*maxc)
% (let {int: r2 = (j-1) div maxc + 1;
% int: c2 = (j-1) mod maxc + 1; } in
% trace("x[\(r1),\(c1)] != x[\(r2),\(c2)]\n",
% x[r1,c1] != x[r2,c2]
% )
% ));
include "alldifferent_except_0.mzn";
constraint alldifferent_except_0([x[r,c] | r in ROW, c in COL]);
% all soldiers get a position
%constraint forall(s in SOLDIER)(exists(r in ROW, c in COL)(r <= nrow /\ c <= ncol /\ x[r,c] = s));
%include "global_cardinality_low_up.mzn";
%constraint global_cardinality_low_up([x[r,c] | r in ROW, c in COL],
% [s | s in SOLDIER], [1 | s in SOLDIER], [1| s in SOLDIER]);
constraint sum(r in ROW, c in COL)(x[r,c] != 0) = nsoldier;
% no straw soldier has only soldiers of less or equal height in front of them
%constraint not exists(r1 in ROW, c in COL)
% (r1 in 1..nrow /\ c in 1..ncol /\ x[r1,c] = 0 /\
% forall(r2 in ROW)(r2 < r1 -> (x[r2,c] = 0 \/
% height[x[r2,c]] <= strawheight)));
array[SOLDIER0] of int: heightx = array1d(SOLDIER0,[strawheight] ++ height);
%constraint not exists(r1 in ROW, c in COL)
% (r1 in 1..nrow /\ c in 1..ncol /\ x[r1,c] = 0 /\
% forall(r2 in ROW)(r2 < r1 -> heightx[x[r2,c]] <= strawheight));
constraint forall(r1 in ROW, c in COL)
(r1 in 1..nrow /\ c in 1..ncol /\ x[r1,c] = 0 ->
exists(r2 in ROW)(r2 < r1 /\ heightx[x[r2,c]] > strawheight));
% Each straw soldier has a real soldier adjacent
constraint forall(r in ROW, c in COL)
((r <= nrow /\ c <= ncol /\ x[r,c] = 0) ->
( if c < maxc then x[r,c+1] != 0 else false endif
\/ if c > 1 then x[r,c-1] != 0 else false endif
\/ if r < maxr then x[r+1,c] != 0 else false endif
\/ if r > 1 then x[r-1,c] != 0 else false endif));
% Each soldier has enough strength to support the straw soldiers
%constraint forall(r in ROW, c in COL)
% (x[r,c] > 0 -> sum(r1 in max(1,r-1)..min(maxr,r+1), c1 in max(1,c-1)..min(maxc,c+1))
% (r <= nrow /\ c <= ncol /\ x[r,c] = 0) < strength[x[r,c]]);
% minimize the sum of height differences in each row
%set of int: DIFF = 0..max(height);
%
%array[ROW,COL] of var DIFF: hd;
%constraint forall(r in ROW)
% (forall(c in 1..ncol-1)
% (if r > nrow \/ c > ncol then
% hd[r,c] = 0
% else if x[r,c] = 0 then
% if x[r,c+1] = 0 then
% hd[r,c] = 0
% else hd[r,c] = abs(strawheight - height[x[r,c+1]])
% endif
% else if x[r,c+1] = 0 then
% hd[r,c] = abs(height[x[r,c]] - strawheight)
% else hd[r,c] = abs(height[x[r,c]] - height[x[r,c+1]])
% endif
% endif
% endif));
%constraint forall(c in COL)(hd[nrow,c] = 0);
%array[ROW,1..maxc-1] of var DIFF: hd;
%constraint forall(r in ROW)
% (forall(c in 1..ncol-1)
% (if x[r,c] != 0 /\ x[r,c+1] != 0
% then hd[r,c] = abs(height[x[r,c]] - height[x[r,c+1]])
% else hd[r,c] = 0
% endif));
%constraint forall(r in ROW)
% (forall(c in 1..ncol-1)
% (hd[r,c] = if x[r,c] != 0 /\ x[r,c+1] != 0
% then abs(height[x[r,c]] - height[x[r,c+1]])
% else 0
% endif));
%constraint forall(r in ROW)
% (forall(c in 1..ncol-1)
% (hd[r,c] = (x[r,c] != 0 /\ x[r,c+1] != 0)*abs(heightx[x[r,c]] - heightx[x[r,c+1]])));
%var int: obj = sum(r in ROW,c in 1..maxc-1)(hd[r,c]);
solve maximize nrow*ncol;
output [ if fix(x[r,c]) = 0 then " ." else show_int(2,height[x[r,c]]) endif ++
if c = maxc then "\n" else " " endif | r in ROW, c in COL]
++ ["x = array2d(ROW,COL,\(x));\n"]
++ ["nrow = \(nrow);\nncol = \(ncol);\n"]
% ++ ["hd = \(hd);\n"]
% ++ ["obj = \(obj);\n"]
;
写在最后，一个问题有很多种建模的方法，但是如何建立一个高效率的模型非常的重要。在minizinc 中我们有很多中工具帮助我们建立模型，但是这种工具都不能处理规模较大的问题。比如exist 函数，推断函数，等等，这些工具在那些商用的求解器Gurobi中是没有的。
