title: 离散优化模型的进阶 week1-1
tags:

notebook: 6- 英文课程-16-Advanced modeling for discrete optimization

离散优化模型的进阶 week1

对于解的丢失问题

我们在进行离散优化建模的时候，经常会出现建模错误的情况，minizinc对于建模也提供了很多有效的调试工具。

问题是这样的：
关羽想要从左上角的节点跑到右下角的节点，中间有很多红色的小兵挡路，关羽想要找到一条挡路的小兵人数最少的线路。

我们首先建立了下面的模型：

首先是数据：

这个模型中，
表示节点的数量。
表示每个节点中敌军的数量，其中有些节点是没有敌军的。
表示节点间的边的数量。
描述了边。
是休息次数。
是起始的节点。
是结束的节点。
是可以走的最大的步数。

然后是数据的抽象描述：

上面是对数据的描述，
其中定义了一个节点的集合，一个边的集合。
通过这两个集合

然后是决策变量：
定义了一个可变的决策变量step，
并且定义了每一步走的节点STEP

在这里还要介绍一个新的全局约束：

table这个函数有两个输入，一个输入是变量，一个是表格，表明变量必须满足表格中的某一行。

如：

那么约束条件就可以这样描述

第一个公式描述初始点为start
第二个公式描述路径中的前后两点一定存在一条边链接。

在这样的问题描述上，需要设定一个路程的猜测值，如果值设的过大会让问题变得很难解。

并且特意加入了一个selfedge来解决设定的边的数量过长的问题。也就是说我们允许节点在终点重复。

比如说一个解是这样的：

最后重复的节点就是终点。

另一个有用的全局约束函数是，slding_sum 函数，这是一个约束，描述为

第一个是序列相加的最小值，第二个是序列相加的最大值。第三个是序列的窗口大小。
举一个使用的例子如下：

例子中上面的那个序列是满足约束的，下面的那个序列是不满足约束的。
如何在本文模型中使用呢，

这样就可以来约束休息的次数。

整个的模型我们写在下面

int: n;
set of int: NODE = 1..n;
array[NODE] of int: guard;
int: m; % number of edges
set of int: EDGE = 1..m;
array[EDGE,1..2] of NODE: edge;
NODE: start;
NODE: dest;
int: rest; % resting every rest junctions
  
int: maxstep;
set of int: STEP = 1..maxstep;
var STEP: step;
array[STEP] of var NODE: path;
  
include "table.mzn";
include "sliding_sum.mzn";
constraint path[1] = start;
constraint forall(i in STEP)(i >= step -> path[i] = dest);
constraint forall(i in 1..maxstep-1)
       (
%      trace("table([\(path[i]),\(path[i+1])],edge)\n",
             table([path[i],path[i+1]],edge))
%      )
       ;
constraint sliding_sum(1,rest,rest,
            [guard[path[i]] = 0| i in STEP]); 
  
solve minimize sum(i in STEP)(guard[path[i]]);
  
% path = [1,10,6,11,14,15,9,9,9,9];
% step = 7;
  

模型遇到了经常出现的一种情况，那就是找不到合理的解。

一般出现这种问题的时候，有这样的几种可能，

1. 你所建立的模型使用太长的时间。
2. 找不到任何一个解。
   当你的模型需要太多时间的时候，你可以进行这两项操作：
3. 给模型加入初始解，
4. 或者对约束进行松弛。

尝试将一个解加入该模型，重新求解，然后你就会发现你哪里建模出现了错误。

松弛约束

尝试一个接着一个的去松弛你的约束，缩小有问题的约束的条数。

比如这个问题，我们加入下面的设定值。

path = [1,10,6,11,14,15,9,9,9,9];
step = 7;

再次尝试，我们没有错误信息，还是无解。

然后尝试去掉一些约束。
使用trace函数进行分析：

加上trace 后，会打印出路径的路线：

可以看到，

得到的输入如上，加重的两个是不存在的边，因此问题出在这里。

因此将模型进行修正，如下

int: n;
set of int: NODE = 1..n;
array[NODE] of int: guard;
int: m; % number of edges
set of int: EDGE = 1..m;
array[EDGE,1..2] of NODE: edge;
  
array[1..2*m, 1..2] of NODE: uedge =
     array2d(1..2*m,1..2, [ edge[i,j]   | i in EDGE, j in 1..2 ] ++
                          [ edge[i,3-j] | i in EDGE, j in 1..2 ]);
  
NODE: start;
NODE: dest;
int: rest; % resting every rest junctions
  
int: maxstep;
set of int: STEP = 1..maxstep;
var STEP: step;
array[STEP] of var NODE: path;
  
include "table.mzn";
include "sliding_sum.mzn";
constraint path[1] = start;
constraint forall(i in STEP)(i >= step -> path[i] = dest);
constraint forall(i in 1..maxstep-1)
      (table([path[i],path[i+1]],uedge));
constraint sliding_sum(1,rest,rest,
            [guard[path[i]] = 0| i in STEP]); 
  
solve minimize sum(i in STEP)(guard[path[i]]);