为 AMPL 中的约束索引添加边界

Question

我正在尝试解决棋盘优化问题，我的约束之一是检查附近的单元格是否被占用：

subject to attack_each_cell {i in 1..n,j in 1..n}:

    P[i,j]+P[i-1,j+2]+P[i-1,j-2]+P[i+1,j+2]+P[i+1,j-2]+P[i-2,j+1]+P[i-2,j-1]+P[i+2,j+1]+P[i+2,j-1]>=1

上述约束的问题是，对于边界单元格，我得到了一个越界错误，所以我的第二种方法是在 (i,j) 索引上的 if-else 语句：

P[i,j]
+ if i>1   and j<n-2 then P[i-1,j+2] 
+ if i>1   and j>2   then P[i-1,j-2] 
+ if i<n-1 and j<n-2 then P[i+1,j+2] 
+ if i<n-1 and j>2   then P[i+1,j-2] 
+ if i>2   and j<n-1 then P[i-2,j+1] 
+ if i>2   and j>1   then P[i-2,j-1] 
+ if i<n-2 and j<n-1 then P[i+2,j+1] 
+ if i<n-2 and j>1   then P[i+2,j-1]
>=1

这不起作用，因为看起来语句是嵌套的，而不是按顺序执行的。关于如何修复代码的任何建议？

Answer 1

选项 1：添加括号以固定计算顺序。

选项 2：重新制定您的约束条件。与其检查马相对于参考单元格的移动位置然后不得不处理越界情况，不如检查棋盘上的所有位置并接受来自参考单元格的马移动的位置：

subject to attack_each_cell {i in 1..n,j in 1..n}: 
  P[i,j] 
+ sum{i1 in 1..n, j1 in 1..n: abs(i-i1) = 2 and abs(j-j1) = 1} P[i1,j1]
+ sum{i1 in 1..n, j1 in 1..n: abs(i-i1) = 1 and abs(j-j1) = 2} P[i1,j1]
>= 1;

选项 3：同上，但首先创建一个定义合法移动的集合，然后通过引用该集合定义约束：

set KnightMoves := {(i,j) in 
  ({-1,1} cross {-2,2})
  union 
  ({-2,2} cross {-1,1})
  }; # this defines the set of moves {(-1,-2),(-1,2), ... (2,1)}

subject to attack_each_cell {i in 1..n,j in 1..n}: 
  P[i,j] + sum{i1 in 1..n, j1 in 1..n: (i-i1,j-j1) in KnightMoves} P[i1,j1]
>= 1;

我最喜欢#3，因为它从约束"any cell that doesn't contain a knight must be threatened by a knight" 中分离出逻辑"how knights move"。这使得定制更容易一些，例如如果你需要解决不同类型的问题，并且它巧妙地扩展到不止一种类型的问题：

subject to attack_each_cell {i in 1..n,j in 1..n}: 
  P[i,j] 
+ sum{i1 in 1..n, j1 in 1..n: (i-i1,j-j1) in KnightMoves} Knights[i1,j1]
+ sum{i1 in 1..n, j1 in 1..n: (i-i1,j-j1) in BishopMoves} Bishops[i1,j1]
+ sum{i1 in 1..n, j1 in 1..n: (i-i1,j-j1) in Pawn} Pawns[i1,j1]
+ ...
>= 1;

（编辑：好吧，如果你忽略不跳棋被别人挡住的问题就可以了。）

为 AMPL 中的约束索引添加边界

Add bounds to constraint´s indexes in AMPL

optimization

ampl