решение LP с cplex

Question

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

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

IloBoolVarArray y(env,J); 

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

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

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

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

Другими словами, сделать иь и фунтов из IloNumVarArray быть дробным и если вы получите дробные значения в вашем оптимальном решении, вы знаете, что вы сделали релаксацию правильно.

Answer 2

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

Answer 3

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

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

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

Если вы все еще получаете комплексное решение, ваша проблема может быть интеграл. Я имею в виду, что ваш коэффициент имеет особое свойство, например TOTALY UNIMODULARITY, вместе со встроенным RHS - интегральное решение.

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