离散优化模型的进阶-什么是效率低的模型如何改进他们 week1-2

离散优化模型的进阶 week1-2

对基本模型的提升

问题描述

一个优化问题描述如下,张飞要通过使用稻草人布置疑阵的方式来虚张声势有这样的约束:

  1. 疑阵有n行和n列
  2. 所有的稻草人高度相同
  3. 所有的稻草人必须临近一个真实的士兵
  4. 所有的稻草人前边一定要有一个比他高的真实的士兵
  5. 目标是将疑阵填充的最大

数据定义:

离散优化模型的进阶-什么是效率低的模型如何改进他们 week1-2
nsoldier 是真实士兵的人数
soldier代表一个士兵
soldier0代表这个位置是一个士兵或者是一个稻草人。
strawheight 是稻草人的身高
height 是所有的真实士兵的身高
还定义了最大的行数和最大的列数

决策变量

离散优化模型的进阶-什么是效率低的模型如何改进他们 week1-2
其中定义了士兵和稻草人的位置,
还有排列的行数和列数。

约束条件:

离散优化模型的进阶-什么是效率低的模型如何改进他们 week1-2
约束描述了一个士兵出现最多一次,具体来说对任意不同行且不同列的两个位置,要么其中一个是稻草人,要么两个士兵不是同一个人。
这是一个非常直观的描述,但是同时这个描述非常的没有效率。
因为我们要在我们的约束表中加入x[r1,r2]=0这个约束非常多次。以及对任何的约束,循环都会让他们加入两次。

对于一个高效的模型,一般有一下的几个特点:

  1. 确保不加入一个约束多次
  2. 确保不在循环中重复约束
  3. 确保尽早的在循环中加入约束

然后修改上述的模型描述
离散优化模型的进阶-什么是效率低的模型如何改进他们 week1-2
这样的修改使用了let语句定义了临时的变量,将多余的约束删除掉了。

不过我们还有更好的方法。
如果你熟悉minizinc的全局约束
可以使用
离散优化模型的进阶-什么是效率低的模型如何改进他们 week1-2

下面需要约束的是士兵出现最少一次
离散优化模型的进阶-什么是效率低的模型如何改进他们 week1-2
这样的模型同样是非常的没有效率的,这种模型的约束非常的分离。
我们使用下面的方法来修正这种模型。

下面的约束是,每一个稻草人周围都有一个真实的士兵。
离散优化模型的进阶-什么是效率低的模型如何改进他们 week1-2
这种描述使用if语句进行,但是通常优秀的模型都没有使用if语句

然后是关于身高的约束:
离散优化模型的进阶-什么是效率低的模型如何改进他们 week1-2
不过这种模型同样效率不高,我们使用一个新的变量变量来更好的描述这个问题。
离散优化模型的进阶-什么是效率低的模型如何改进他们 week1-2

在建模中应该尽量避免如下的几个问题的使用:

  1. not函数,如果想要使用 not a=b 请修改成 a != b
  2. 析取模型,如果 如 a/b如果必须使用,请确保这个模型尽量简单。
  3. 推断, 如果必须使用,请确保这个模型尽量简单。
  4. 不要在循环中使用 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中是没有的。

上一篇:关于Arrays.asList()方法的使用


下一篇:2018 数学建模美国赛思路