0

我试图制定变量 x,y,z 必须全部不同，并且它们只接受值 1、2 或 3（这当然是一个玩具示例）：

min: x+y+z;

1 <= x <= 3;
1 <= y <= 3;
1 <= z <= 3;

但要完成这项工作，我仍然需要访问布尔运算符或 != 运算符，这在 lpsolve 中似乎不存在！我该怎么办？我想这样做：

x != y;
x != z;
y != z;

谢谢

编辑：

这是我当前的代码：

/* Objective function */
min: 1;

/* Variable bounds */
1 <= x1 <= 4;
1 <= x2 <= 4;
1 <= x3 <= 4;
1 <= x4 <= 4;


x1 + x2 + x3 + x4 = 10;

x1 < x2;
x2 < x3;
x3 < x4;

int x1;
int x2;
int x3;
int x4;

lpsolve 给我的结果是：

x1 = 1
x2 = 3
x3 = 3
x4 = 3

这是错误的。为什么？

4

1 回答 1

0

总的来说，我同意 Michael Laffargue 的观点，即在 lpSolve 中不可能有像a < b真正的 a,b 这样的东西。但是对于整数表达式，情况有点不同。

也许我们可以从一个更简化的问题开始。让我们考虑两个整数变量 x 和 y 以及一个常数 M 使得 1 <= x <= M and 1<=y<=M。如果 x 和 y 可能不相等，则 x>y 或 y>x。但由于两者都是整数，因此只有以下不等式之一成立

x+1 <= y
y+1 <= x

我们可以通过引入一个二元变量 r 来强制上述不等式中只有一个成立，使得对于 x,y, r 以下不等式同时成立：

(i)   x+1 <= y+ Mr
(ii)  y+1 <= x+M-Mr

因为如果r=0then(i) x+1 <=y和 (ii) 是微不足道的，但如果r=1then(ii) y+1 <= x和 (i) 是微不足道的。

当我们现在将上面的解决方案应用于 OP 问题时，我们可以为来自 OP 问题的所有变量对和 建立一个具有不等式 (i) 和 (ii) 的线性程序M=4：

/* Objective function */
min: 1;

/* Variable bounds */
1 <= x1 <= 4;
1 <= x2 <= 4;
1 <= x3 <= 4;
1 <= x4 <= 4;
r_12 <= 1;
r_13 <= 1;
r_14 <= 1;
r_23 <= 1;
r_24 <= 1;
r_34 <= 1;

/* This is done automatically because all x1,..,x4 are different
   x1 + x2 + x3 + x4 = 10;
*/

/*  Apply (i) and (ii) to all pairs of x1,..x4
(i)  x+1 <= y + Mr
(ii) y+1 <= x + M-Mr
*/

x1 + 1 <= x2 + 4 r_12;
x2 + 1 <= x1 + 4 - 4 r_12;

x1 + 1 <= x3 + 4 r_13;
x3 + 1 <= x1 + 4 - 4 r_13;

x1 + 1 <= x4 + 4 r_14;
x4 + 1 <= x4 + 4 - 4 r_14;

x2 + 1 <= x3 +  4 r_23;
x3 + 1 <= x2 + 4 - 4 r_23;

x2 + 1 <= x4 + 4 r_24;
x4 + 1 <= x2 + 4 - 4 r_24;

x3 + 1 <= x4 + 4 r_34;
x4 + 1 <= x3 + 4 - 4 r_34;

/*
x1 < x2;
x2 < x3;
x3 < x4;
*/

int r_12;
int r_13;
int r_14;
int r_23;
int r_24;
int r_34;
int x1;
int x2;
int x3;
int x4;

解决上面的 MILP 会得到一个完全x1,..,x4不同的解决方案：

x1=3
x2=1
x3=2
x4=4
于 2018-10-21T00:29:59.813 回答