c++ - CPLEX - 降低成本

Question

我目前正在使用 cplex 并试图确定 LP 的降低成本。我对结果有点困惑。我目前对降低成本的理解是，它描述了在变量成为解决方案的一部分之前目标函数系数必须提高的量(值 = 1)。

因此，所有基本变量(解决方案中的非零值)的成本都降低为零。我读到，不属于当前解决方案的变量如果处于其极限之一，也可以将成本降低为零。是真的吗？

以下 LP 的成本降低让我感到困惑:

minimize 100*x1 + 3*x5
0 <= x0, x1, x2, x3, x4, x5, x6, x7, x8
x0 = 1
x0 - x1 - x2 = 0
x3 = 1
x3 - x4 = 0
x1 - x6 = 0
x2 - x7 = 0
-x4 + x5 - x8 = 0
-x5 + x6 + x7 + x8 = 0

如果我使用 cplex 来计算减少的成本，我会得到以下结果。

Objective Value = 3
Solution = [1, 0, 1, 1, 1, 1, 0, 1, 0]
Reduced Cost = [0 0 0 0 0 0 100 0 3]

我不明白为什么变量 x1 的成本降低为零，它既不是解决方案的一部分，也不是上限。对于变量 x7，x1 的减少值是否应该不是 100。如果我将 x1 的值增加 1，我得到的解决方案会更糟 100(成本)，对吗？

在这里，我的 C++ 代码:

#include <ilcplex/ilocplex.h>

int main () {
  IloEnv             env;
  IloModel     model(env);
  IloNumVarArray   x(env);
  x.add(IloNumVar(env)); //default: between $0$ and $+\infty$ 
  x.add(IloNumVar(env));
  x.add(IloNumVar(env)); 
  x.add(IloNumVar(env));
  x.add(IloNumVar(env)); 
  x.add(IloNumVar(env));
  x.add(IloNumVar(env));
  x.add(IloNumVar(env));
  x.add(IloNumVar(env));
  model.add(x[0] == 1);
  model.add(x[0]-x[1]-x[2] == 0);
  model.add(x[3] == 1);
  model.add(x[3]-x[4] == 0);
  model.add(x[1]-x[6] == 0);
  model.add(x[2]-x[7] == 0);
  model.add(-x[4]+x[5]-x[8] == 0);
  model.add(-x[5]+x[6]+x[7]+x[8] == 0);
  model.add(IloMinimize(env, 100*x[1] + 3*x[5]));
  IloCplex cplex(model);
  cplex.solve();
  std::cout << "Min=" << cplex.getObjValue() << std::endl;
  IloNumArray v(env);
  cplex.getReducedCosts(v, x);
  std::cout << v << std::endl;
  env.end();
}

Answer 1

I read that variables that are not part of the current solution can also have a reduced cost of zero if they are at one of their limits. Is that true?

是的。如果变量不在其极限范围内，则它们的成本降低为零。如果它们处于其极限之一，它们仍然可以将成本降低为零，以防存在多个原始最优解。

那么，你的问题可以看做是以下网络的流量问题:

每条弧代表它进入的节点的变量值(例如，1 = x0)。最优解对应于路径 0-2-7-5-4-3，总成本为 3。如果您强制 x1(或 x6)等于 1，则解决方案将更改为 x0=x1=x6=x5=x4=x3=1.

现在，只有当最优基础保持不变时，对偶值和影子价格才有意义。强制 x1=1 会改变最优基础(因为不同的路径是最优的)，因此相应的对偶值可能没有意义。

降低成本的另一种解释是将其视为非负性约束的双重价格(即，显示在非基本或零级基本的一个单位的情况下目标函数将增加多少变量被迫进入第 1 级的基础 - 假设非负性约束)。同样，如果这种改变改变了最优基础，它的值可能不正确。

由于降低的成本是相应非负性约束的对偶值，您可以尝试的另一个实验是显式添加非负性约束作为约束，然后检查它们的对偶值。对于 x6>=0，我得到一个对偶值 100 和右侧的允许增加 = 1，而对于 x1>=0，我得到一个对偶值0 的值和 0 的右侧的允许增加。这实际上意味着对偶值(在这种情况下是降低的成本)没有意义。

希望对您有所帮助。