c++ - 为什么我的 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 .为此，我将定义更改为:

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 也有一个整数的最优解。验证这一点的一种快速方法是添加绑定(bind)削减以强制其采用一些小数值。

修改X1的lb和ub:取0 <= x1 <= 1并让它(比如说)0.01 <= x1 <= 0.99现在解决LP。对原始公式中所有二元变量执行此操作。

换句话说，制作IloNumVarArray的ub和lb是分数，如果您在最优解中得到分数值，您就知道您已经正确地进行了松弛。