Модель накопительного VRP в Cplex

Question

Я новичок в Cplex IBM ILOG CPLEX Optimization Studio и в настоящее время программирую накопительную модель VRP (ссылка: DOI: 10.5772 / 5812), например:

Это мой код:

{string} CIUDADES = ...;
 int READY_TIME[CIUDADES] = ...;
 int DUE_TIME[CIUDADES] = ...;
 int SERVICETIME[CIUDADES] = ...;
 int DISTANCIA[CIUDADES, CIUDADES] = ...;
 int CLIENTES=11;
 int Penalizacion = 10;
 int DEMANDAS[CIUDADES] = ...;
 int NROCIUDADES[CIUDADES] = ...;
int PESO_VACIO = 6350;
int PESO_LLENO = 3650;
int VELOCIDAD_MINIMA = 20;
int VELOCIDAD_MAXIMA = 90;
int UMBRAL_RETRASO = 300;
int aux = 0;
int CARGAT = sum(ci in CIUDADES) DEMANDAS[ci];
int vehiculos =1;

//DV
dvar int X[CIUDADES,CIUDADES] in 0..1;
dvar int Y[CIUDADES, CIUDADES] in 0..(CARGAT+PESO_VACIO);

minimize
    sum(ci in CIUDADES) 
        sum(cj in CIUDADES)
          DISTANCIA[ci,cj]*Y[ci,cj];

subject to {
    restriccion1: 
            sum(ci in CIUDADES) 
                X["Kingston_upon_Hull",ci]==1;  

    restriccion2: 
            sum(ci in CIUDADES) 
                X[ci,"Kingston_upon_Hull"]==1;

    forall(cj in CIUDADES) {
    restriccion3: 
            sum(ci in CIUDADES: ci!=cj) 
                (X[ci,cj])==1;
}

    forall(ci in CIUDADES) {
    restriccion4: 
            sum(cj in CIUDADES: ci!=cj) 
                (X[ci,cj])==1;
}   

forall(ci in CIUDADES) {
    restriccion5: 
            ((sum(cj in CIUDADES: ci!=cj) 
                (Y[cj,ci]))
                -
            (sum(cj in CIUDADES: ci!=cj) 
                (Y[ci,cj])))
            == DEMANDAS[ci];

}   

forall(ci in CIUDADES) {
    restriccion6:
     Y[ci,"Kingston_upon_Hull"]== PESO_VACIO*X[ci,"Kingston_upon_Hull"];
}   

forall(ci in CIUDADES, cj in CIUDADES) {
    restriccion7:
     Y[ci,cj] <= ((77777777)-DEMANDAS[ci])*X[ci,cj];

}

forall(ci in CIUDADES, cj in CIUDADES) {
    restriccion8:
     Y[ci,cj] >= ((PESO_VACIO)-DEMANDAS[cj])*X[ci,cj];
}

forall(ci in CIUDADES) {
    restriccion9:
     Y["Kingston_upon_Hull",ci]== (PESO_VACIO+CARGAT)*X["Kingston_upon_Hull",ci];
}
}

Но при компиляции с использованием CPLEX я получаю следующий результат:

/ solution (feasible relaxed sum of infeasibilities) with objective 5671
// Quality Incumbent solution:
// MILP objective                                 6.6464998100e+09
// MILP solution norm |x| (Total, Max)            1.02485e+05  1.20210e+04
// MILP solution error (Ax=b) (Total, Max)        0.00000e+00  0.00000e+00
// MILP x bound error (Total, Max)                0.00000e+00  0.00000e+00
// MILP x integrality error (Total, Max)          0.00000e+00  0.00000e+00
// MILP slack bound error (Total, Max)            5.67100e+03  5.67100e+03
Y = [[0
             0 0 0 0 0 0 0 0 0 12021]
             [0 0 10186 0 0 0 0 0 0 0 0]
             [0 0 0 9372 0 0 0 0 0 0 0]
             [0 0 0 0 0 0 0 0 8752 0 0]
             [0 10907 0 0 0 0 0 0 0 0 0]
             [0 0 0 0 11218 0 0 0 0 0 0]
             [6350 0 0 0 0 0 0 0 0 0 0]
             [0 0 0 0 0 0 6863 0 0 0 0]
             [0 0 0 0 0 0 0 0 0 7989 0]
             [0 0 0 0 0 0 0 7431 0 0 0]
             [0 0 0 0 0 11385 0 0 0 0 0]];
X = [[0 0 0 0 0 0 0 0 0 0 1]
             [0 0 1 0 0 0 0 0 0 0 0]
             [0 0 0 1 0 0 0 0 0 0 0]
             [0 0 0 0 0 0 0 0 1 0 0]
             [0 1 0 0 0 0 0 0 0 0 0]
             [0 0 0 0 1 0 0 0 0 0 0]
             [1 0 0 0 0 0 0 0 0 0 0]
             [0 0 0 0 0 0 1 0 0 0 0]
             [0 0 0 0 0 0 0 0 0 1 0]
             [0 0 0 0 0 0 0 1 0 0 0]
             [0 0 0 0 0 1 0 0 0 0 0]];

и компиляцию через cmd в windows с oplrun -p folder и я получаю следующее:

Version identifier: 12.10.0.0 | 2019-11-26 | 843d4de2ae    
Infeasibility row 'restriccion1':  0  = 1.
Presolve time = 0.02 sec. (0.76 ticks)  

Моя программа присваивает переменные Xij и Yij, но не оптимизирует целевую функцию. Где бы у меня была ошибка? Ваша помощь будет оценена.

Спасибо!

Answer 1

В IDE вы получаете расслабление, потому что ваша модель неосуществима, а с помощью командной строки вы получаете только крошечное сообщение.

Если вы хотите увидеть расслабление с помощью командной строки, выполните oplrun -relax

Очень просто пример .

Позвольте нам go продолжить с

https://www.linkedin.com/pulse/what-optimization-how-can-help-you-do-more-less-zoo-buses-fleischer/

и решить новую проблему: невозможность!

Предположим, у нас есть новая задача: использовать менее 7 автобусов в общей сложности.

Затем мы пишем

int nbKids=300;
float costBus40=500;
float costBus30=400;

dvar int+ nbBus40;
dvar int+ nbBus30;

minimize
 costBus40*nbBus40  +nbBus30*costBus30;

subject to
{
 ctAllKidsNeedToGo:
     40*nbBus40+nbBus30*30>=nbKids;

 ctMaxTotalBuses:
     nbBus30+nbBus40<=7;
}

ctAllKidsNeedTo Go и ctMaxTotalBuses являются метками для ограничений.

Но тогда проблема становится неосуществимой, поскольку даже с 7 автобусами на 40 мест вы можете взять только 280 = 7 * 40 детей, что меньше 300 детей.

Когда мы запускаем эту модель, мы получаем конфликт

, который означает, что у нас есть конфликт в пределах этих двух ограничений и ослабление, что означает, что если мы ослабим 7 автобусов до 8 автобусов, то у нас будет возможное решение.

Это не очень полезно для этого Крошечный пример, но для реальных моделей это может быть ключевым.

Для получения дополнительной информации см. Расслабление недопустимых моделей в Учебниках по IDE в документации по CPLEX

Примечание:

Вы также можете получить это информация через управление потоком в сценариях:

int nbKids=300;
float costBus40=500;
float costBus30=400;

dvar int+ nbBus40;
dvar int+ nbBus30;

minimize
 costBus40*nbBus40  +nbBus30*costBus30;

subject to
{
 ctAllKidsNeedToGo:
     40*nbBus40+nbBus30*30>=nbKids;

 ctMaxTotalBuses:
     nbBus30+nbBus40<=7;
}

main
{
thisOplModel.generate();
if (!cplex.solve())
{
writeln(thisOplModel.printRelaxation());
writeln(thisOplModel.printConflict());
}
}

дает

ctMaxTotalBuses
    relax [-Infinity,7] to [-Infinity,8] value is -Infinity

ctAllKidsNeedToGo
  is in conflict
ctMaxTotalBuses
  is in conflict