Нахождение максимума занимает слишком много времени в ILP, почему? - PullRequest
Новая
       37

Нахождение максимума занимает слишком много времени в ILP, почему?

0 голосов
/ 08 ноября 2011

Короче говоря, сейчас мы пытаемся преобразовать 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];

    }

};

1 Ответ

1 голос
/ 08 ноября 2011

Выражения типа 

x1 * x2

являются квадратичными, если x1, x2 обе переменные. У вас есть проблема целочисленного квадратичного программирования с 50 переменными. Кроме того, ваша целевая функция не вогнута, поэтому CPLEX будет особенно трудно.
Однако, поскольку у вас есть все 0-1 переменные, вы можете преобразовать это в линейную задачу, добавив дополнительную переменную, скажем бонус для выражения с положительными коэффициентами и штраф для тех, у отрицательные коэффициенты, помещая их в целевую функцию вместо квадратичных слагаемых и добавляя следующие ограничения 

bonus <= x1
bonus <= x2

или в случае отрицательного коэффициента 

penalty >= x1 + x2 - 1

Поскольку вы максимизируете, cplex заставит бонус или штраф к правильным значениям при оптимальных решениях. Штрафные и бонусные переменные должны быть объявлены неотрицательными 

dvar float+ penalty;
dvar float+ bonus;

Сделайте это для всех квадратичных выражений, и ваша задача станет линейной целочисленной задачей и решится гораздо быстрее.

...