1

我正在学习 AMPL，以便稍后在我的程序中使用它。我有一个小问题想解决。正如标题所述，我正在尝试使用一些迭代操作来最小化约束的数量。所以问题如下：假设我有 2 套A和B并假设我有代码：

set A:= (1, 2, 3) (4, 5, 6);
set B:= a b c;
var x{A,B} binary;    
**some_objective** ;
subject to constraint   { (i,j,k) in A, b in B   }:  x[i,b] + x[j,b] + x[k,b] <= 1;

现在，如果我们扩展之前的约束，将形成以下约束：

x[1,a] + x[2,a] + x[3,a] <=1;

x[1,b] + x[2,b] + x[3,b] <=1;

x[1,c] + x[2,c] + x[3,c] <=1;

x[4,a] + x[5,a] + x[6,a] <=1;

x[4,b] + x[5,b] + x[6,b] <=1;

x[4,c] + x[5,c] + x[6,c] <=1;

这意味着，对于A中的y子集和B中的z元素，我们将得到总共y*z约束（在我们的例子中是 2 x 3 = 6 个约束）。

现在，如果我们将约束更改为：

subject to constraint   { (i,j,k) in A   }:  prod {   b in B   }    (x[i,b] + x[j,b] + x[k,b])    <= 1;

这将导致：

{(x[1,a] + x[2,a] + x[3,a]) * (x[1,b] + x[2,b] + x[3,b]) * (x[1,c] + x[2,c] + x[3,c])} <= 1;

{(x[4,a] + x[5,a] + x[6,a]) * (x[4,b] + x[5,b] + x[6,b]) * (x[4,c] + x[5,c] + x[6,c])} <= 1;

它应该与之前的形式具有相同的结果，但我们将约束数量从y*z减少到y，这是一个很好的改进！另一个改进是逻辑和约束：

subject to constraint   { (i,j,k) in A   }:  forall {   b in B   }   (   (x[i,b] + x[j,b] + x[k,b])    <= 1  );

这将导致：

{(x[1,a] + x[2,a] + x[3,a]) <= 1} && {(x[1,b] + x[2,b] + x[3,b]) <= 1} && {(x[1,c] + x[2,c] + x[3,c]) <= 1};

{(x[4,a] + x[5,a] + x[6,a]) <= 1} && {(x[4,b] + x[5,b] + x[6,b]) <= 1} && {(x[4,c] + x[5,c] + x[6,c]) <= 1};

问题是，当我们这样做时，我们正在将问题从线性或二次方程变为非二次方程，而cplex无法再解决它：/

是否有任何解决方法或任何技巧使我能够做到这一点而不将问题转换为非二次问题（至少要使用cplex解决）？

这么说也很有用，这对于Ax[1,a] + x[1,b] + x[1,c] = 1中的任何其他元素都是如此。感谢您的帮助，并提前感谢您。

4

1 回答 1

1

首先，我想指出使用 product 的约束不等同于原始约束。例如，x[1,a] = 1, x[2,a] = 1, x[3,a] = 1余数x等于 0 的解满足用prod因为制定的约束(x[1,a] + x[2,a] + x[3,a]) * (x[1,b] + x[2,b] + x[3,b]) * (x[1,c] + x[2,c] + x[3,c]) = 3 * 0 * 0 = 0 <= 1，但不满足原始约束x[1,a] + x[2,a] + x[3,a] = 3 <= 1。

您可以使用逻辑或&&IBM /ILOG CPLEX CP Optimizer (ilogcp)，它适用于所有 AMPL/CPLEX 用户，但我怀疑这会比单独的约束更好。您可以在“逻辑”和约束编程扩展页面上找到更多信息，其中还包括有关如何获取它的信息（如果您有 CPLEX 许可证，您也应该能够获得 ilogcp）。此求解器将接受以下形式的约束：forallilogcp

subject to c{(i,j,k) in A}: forall {b in B} (x[i,b] + x[j,b] + x[k,b] <= 1);
于 2014-07-16T16:25:25.023 回答