Почему я получаю только целочисленные решения для моего LP?

Question

У меня целочисленная модель программирования, и я хочу решить ее линейную релаксацию с помощью CPLEX. Первоначально я определил мои переменные как:

BoolVarMatrix X(env,I);
for(IloInt i = 0; i < I; i++){
  X[i] = IloBoolVarArray(env, J);
}

IloBoolVarArray y(env,J);

но теперь я должен ослабить их до диапазона 0 <= x <= 1, 0 <= Y <= 1. Для этого я изменил определение на: </p>

NumVarMatrix X(env,I, 0, 1);
for(IloInt i = 0; i < I; i++){
  X[i] = IloNumVarArray(env, J, 0, 1);
}

IloNumVarArray y(env,J, 0, 1);

но это все еще дает мне целочисленное решение. Что я должен был сделать вместо этого?

Answer 1

Вам не нужно преобразовывать двоичные переменные в ILOFLOAT.Определите новый экземпляр модели, такой как LPRelax, и используйте IloConversion, как показано ниже:

IloModel LpRelax(env); 
LpRelax.add(model); 
LpRelax.add(IloConversion(env, vars, ILOFLOAT));

IloCplex cplex(env); 
cplex.extract(LpRelax); 
cplex.solve();

Если вы все еще получаете интегральное решение, ваша проблема может быть интегральной.Я имею в виду, что ваш коэффициент имеет особые свойства, такие как ПОЛНОСТЬЮ УНИМОДУЛЯРНОСТЬ, вместе с интегральной RHS дают интегральное решение.

Надеюсь, это поможет: -).

Answer 2

Вполне возможно, что ваш расслабленный LP также имеет оптимальное решение, которое является целым числом.Один быстрый способ убедиться в этом - добавить связывающие сокращения , чтобы заставить его принять некоторые дробные значения.

Измените lb и ub для X1: возьмите 0 <= x1 <= 1 и сделайте это (скажем)0.01 <= x1 <= 0.99 и теперь решайте ЛП.Сделайте это для всех переменных, которые были двоичными в вашей первоначальной формулировке.

Другими словами, сделайте ub и lb из IloNumVarArray дробными, и если вы получите дробные значения в своем оптимальном решении, вы знаете, что имеетесделал расслабление правильно.

Answer 3

Возможно, ваша матрица коэффициентов ограничения A (AX = b) является унимодулярной.