0

つまり、現在、IQPをILPに変更しようとしています。古い実装では約2日かかりましたが、現在は線形ツールを使用しています。速度が上がるはずです。基本的に問題は最大化することです（約50のバイナリ変数で）：

$$ \ sum_ {g = 1} ^ {5} sum_ {p = 1} ^ {10}（S [p] x[g][p]-倦怠感[g][p]-眠気[g][p ]）$$

アップデート

デビッドは正しい方向に進んでいると思いますが、ボーナス変数を使用して式を最大化しようとすると、毎回ゼロになります。なぜですか。いくつかのコードの下では、スコアはのようになり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];

    }

};
4

1 に答える 1

1

のような表現

x1 * x2

x1、x2が両方とも変数の場合、は2次式です。50変数の整数二次計画問題があります。また、目的関数は凹型ではないため、CPLEXは特に困難になります。
ただし、すべての0-1変数があるため、追加の変数を追加することで、これを線形問題に変換できます。たとえば、正の係数を持つ式のボーナスと負の係数を持つ式のペナルティを追加して、それらを目的関数の代わりに目的関数に入れます。二次項と次の制約の追加

bonus <= x1
bonus <= x2

または負の係数の場合

penalty >= x1 + x2 - 1

最大化しているので、cplexは最適なソリューションで正しい値にボーナスまたはペナルティを強制します。ペナルティ変数とボーナス変数は、非負であると宣言する必要があります

dvar float+ penalty;
dvar float+ bonus;

すべての2次式に対してこれを行うと、問題は線形整数問題になり、はるかに高速に解決されます。

于 2011-11-08T16:44:31.983 に答える