CPLEX

Question

我目前正在使用 cplex 并试图确定 LP 的降低成本。我对结果有点困惑。我目前对降低成本的理解是，它描述了 objective 函数系数在变量成为解决方案的一部分之前必须提高的量（值 = 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 [=12=]$ 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 改变了最优基础（因为不同的路径是最优的）因此相应的对偶值可能没有意义。

对降低成本的另一种解释是将其视为非负性约束的双重价格（即显示 objective 函数将增加多少基本或零级基本变量被迫进入第 1 级的基础 - 假设非负性约束）。同样，如果此更改改变了最优基础，其值可能不正确。

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

希望对您有所帮助。

CPLEX - 降低成本

CPLEX - Reduced Costs

c++

linear-programming