如何在lpsolve中公式化x!= y [英] How to formulate x != y in lpsolve?
问题描述
我试图表述变量x,y,z必须全部不同,并且它们仅接受值1、2或3(当然,这是一个玩具示例):
I'm trying to formulate that the variables x,y,z must all be different and that they accept only the values 1, 2 or 3 (this is, of course, a toy example):
min: x+y+z;
1 <= x <= 3;
1 <= y <= 3;
1 <= z <= 3;
但是要完成这项工作,我仍然需要访问布尔运算符或!=运算符,它们似乎在lpsolve中不存在!我该怎么办?我想这样做:
but to make this work I still need either access to boolean operators or to a != operator, which don't seem to exist in lpsolve! How can I go about this? I wanted to do this:
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给我的结果是
lpsolve is giving me as result:
x1 = 1
x2 = 3
x3 = 3
x4 = 3
这是错误的.为什么?
推荐答案
总的来说,我会同意迈克尔·拉法格(Michael Laffargue)的观点,不可能在lpSolve中使用像a < b
这样的实数a,b.但是对于整数表达式则有些不同.
In general I would agree with Michael Laffargue that it is not possible to have something like a < b
for real a,b in lpSolve. But for integer expressions that is a bit different.
也许我们可以从一个更简单的问题开始.
让我们考虑两个整数变量x和y以及一个常数M,使得
1 <= x <= M and 1<=y<=M
.
如果x和y不相等,则x> y或y> x.但是由于这两个整数都是仅以下一个不等式成立
Maybe we can start with a more simplified problem.
Let us think of two integer variables x and y and a constant M such that
1 <= x <= M and 1<=y<=M
.
If x and y may not be equal then x>y or y>x. But as both are integers only one of the following inequalities hold
x+1 <= y
y+1 <= x
我们可以通过引入二进制变量r来强制上述不等式成立,这样对于x,y,r的以下不等式都都:
We can enforce that only one of the inequalities above holds by introducing a binary variable r such that for x,y, r the following inequalities hold both :
(i) x+1 <= y+ Mr
(ii) y+1 <= x+M-Mr
因为如果r=0
则(i) x+1 <=y
和(ii)是微不足道的,但是如果r=1
则(ii) y+1 <= x
和(i)则微不足道.
because if r=0
then (i) x+1 <=y
and (ii) is trivial, but if r=1
then (ii) y+1 <= x
and (i) is trivial.
现在我们从上方将解决方案应用于OP问题时,我们可以针对OP问题和M=4
的所有变量对构建具有不等式(i)和(ii)的线性程序:>
When we now apply the solution from above to the problem of the OP, then we can build a linear program with inequalities (i) and (ii) for all pairs of variables from the OP's problem and 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
均不同:
Solving the MILP above renders a solution with all x1,..,x4
different:
x1=3
x2=1
x3=2
x4=4
这篇关于如何在lpsolve中公式化x!= y的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!