在 ILP 中查找最大值花费了太多时间,为什么?

发布于 2024-12-14 01:47:37 字数 1489 浏览 2 评论 0原文

简而言之,我们现在正在尝试将 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 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(1

人生百味 2024-12-21 01:47:37

则此类表达式

x1 * x2

如果 x1、x2 都是变量, 是二次的。您有一个 50 变量的整数二次规划问题。此外,您的目标函数不是凹的,因此 CPLEX 将会遇到特别困难的时期。
但是,由于您拥有所有 0-1 变量,因此您可以通过添加附加变量将其转换为线性问题,例如对于具有正系数的表达式,表示“奖励”;对于具有正系数的表达式,则表示“惩罚”那些具有负系数的,将它们放入目标函数而不是二次项中,并添加以下约束

bonus <= x1
bonus <= x2

,或者在负系数的情况下,

penalty >= x1 + x2 - 1

因为您正在最大化,cplex将强制奖励惩罚< /em> 到最佳解决方案的正确值。
惩罚变量和奖励变量应声明为非负数

dvar float+ penalty;
dvar float+ bonus;

对所有二次表达式执行此操作,您的问题将变成线性整数问题并且求解速度更快。

Expressions like

x1 * x2

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

bonus <= x1
bonus <= x2

or in case of a negative coeficient

penalty >= x1 + x2 - 1

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

dvar float+ penalty;
dvar float+ bonus;

Do this for for all the quadratic expressions and your problem will become a linear integer problem and solve much faster.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文