离散优化模型的进阶 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 中是没有的.
来源: https://yq.aliyun.com/articles/674295