在 ILP 中查找最大值花费了太多时间,为什么?
简而言之,我们现在正在尝试将 IQP 更改为 ILP。旧的实现大约需要 2 天才能完成,现在使用线性工具——它应该会加快速度。基本上问题是最大化(大约 50 个二进制变量):
$$\sum_{g=1}^{5}sum_{p=1}^{10} ( S[p]x[g][p]- Tiredness[g][p]-Sleepness[g][p] )$$
更新
我认为 David 走在正确的轨道上,但是当我尝试使用额外变量最大化表达式时,它们为零每次, 为什么?在某些代码下面,分数可能类似于 S[1..10]=[1,2,3,4,5,6,7,8,9,10];
。
int S[1..10] = ...; // Scores per player =s
dvar int x1[1..10] in 0..1;
dvar int x2[1..10] in 0..1;
dvar int x3[1..10] in 0..1;
dvar int x4[1..10] in 0..1;
dvar int x5[1..10] in 0..1;
dvar int b1[1..10] in 0..100;
dvar int b2[1..10] in 0..100;
//ERR: the values of b1 and b2 should be maximized...
// WHY not here so?
maximize
sum(i in 1..10)
(
S[i] *
(
(x1[i]+x2[i]+x3[i]+x4[i]+x5[i])
- 1/10 * ( b1 +b2)
)
);
subject to
{
//We must play in 5 games.
//It means that there are 5 players in each game.
sum(i in 1..10) x1[i]==5;
sum(i in 1..10) x2[i]==5;
sum(i in 1..10) x3[i]==5;
sum(i in 1..10) x4[i]==5;
sum(i in 1..10) x5[i]==5;
// IQP problem into ILP -problem
forall (i in 1..10)
{
//ERROR HERE!
//it returns zero for b1 and b2, they should be maximized...
//I am trying to use the tip by David here, see his answer.
// EQ1: x2[i] * (x1[i]+x3[i])
b1 <= 2*x2[i];
b1 <= x1[i]+x3[i];
// EQ2: x4[i] * (x3[i]+x5[i]+x1[i])
b2 <= 3*x4[i];
b2 <= x3[i]+x5[i]+x1[i];
}
};
In short, we are now trying to change the IQP into the ILP. It took about 2 days with the old implementation to finish, now with linear tools -- it should speed up. Basically the problem is to maximize (with about 50 binary vars):
$$\sum_{g=1}^{5}sum_{p=1}^{10} ( S[p]x[g][p]-Tiredness[g][p]-Sleepness[g][p] )$$
Update
I think David is on the right track but when I try to maximize the expression with bonus -variables, they are zero every time, why? Below some code, scores could be like S[1..10]=[1,2,3,4,5,6,7,8,9,10];
.
int S[1..10] = ...; // Scores per player =s
dvar int x1[1..10] in 0..1;
dvar int x2[1..10] in 0..1;
dvar int x3[1..10] in 0..1;
dvar int x4[1..10] in 0..1;
dvar int x5[1..10] in 0..1;
dvar int b1[1..10] in 0..100;
dvar int b2[1..10] in 0..100;
//ERR: the values of b1 and b2 should be maximized...
// WHY not here so?
maximize
sum(i in 1..10)
(
S[i] *
(
(x1[i]+x2[i]+x3[i]+x4[i]+x5[i])
- 1/10 * ( b1 +b2)
)
);
subject to
{
//We must play in 5 games.
//It means that there are 5 players in each game.
sum(i in 1..10) x1[i]==5;
sum(i in 1..10) x2[i]==5;
sum(i in 1..10) x3[i]==5;
sum(i in 1..10) x4[i]==5;
sum(i in 1..10) x5[i]==5;
// IQP problem into ILP -problem
forall (i in 1..10)
{
//ERROR HERE!
//it returns zero for b1 and b2, they should be maximized...
//I am trying to use the tip by David here, see his answer.
// EQ1: x2[i] * (x1[i]+x3[i])
b1 <= 2*x2[i];
b1 <= x1[i]+x3[i];
// EQ2: x4[i] * (x3[i]+x5[i]+x1[i])
b2 <= 3*x4[i];
b2 <= x3[i]+x5[i]+x1[i];
}
};
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(1)
则此类表达式
如果 x1、x2 都是变量, 是二次的。您有一个 50 变量的整数二次规划问题。此外,您的目标函数不是凹的,因此 CPLEX 将会遇到特别困难的时期。
但是,由于您拥有所有 0-1 变量,因此您可以通过添加附加变量将其转换为线性问题,例如对于具有正系数的表达式,表示“奖励”;对于具有正系数的表达式,则表示“惩罚”那些具有负系数的,将它们放入目标函数而不是二次项中,并添加以下约束
,或者在负系数的情况下,
因为您正在最大化,cplex将强制奖励或惩罚< /em> 到最佳解决方案的正确值。
惩罚变量和奖励变量应声明为非负数
对所有二次表达式执行此操作,您的问题将变成线性整数问题并且求解速度更快。
Expressions like
are quadratic if x1, x2 are both variables. You have a 50-variable integer quadratic programming problem. Also, your objective function isn't concave so CPLEX is going to have an especially hard time.
However, since you have all 0-1 variables, you can convert this into an linear problem by adding an additional variable, say bonus for the expression with positive coefficients and penalty for those with negative coefficients, putting them in the objective function instead of the quadratic terms and adding the following constraints
or in case of a negative coeficient
Since you are maximizing, cplex will force bonus or penalty to the correct values at optimal solutions.
The penalty and bonus variables should be declared to be non-negative
Do this for for all the quadratic expressions and your problem will become a linear integer problem and solve much faster.