如何访问对偶单纯形求解器的解决方案？

Question

我有一个 objective 函数，其中包含数百个二次项，我想将其最小化；在这种情况下，我尝试最小化几个变量之间的绝对距离。所以我的问题的结构看起来像这样（高度简化）：

Minimize
obj: [ a^2 - 2 a * b + b^2 ] / 2
Subject To
c1: a + b >= 10
c2: a <= 100
End

我使用PythonAPI解决问题的方式如下：

import cplex

cpx = cplex.Cplex()
cpx.read('quadratic_obj_so.lp')  
# use the dual simplex   
cpx.parameters.lpmethod.set(cpx.parameters.lpmethod.values.dual)
cpx.solve()
print cpx.solution.get_values()[0:15]
print cpx.solution.status[cpx.solution.get_status()]
print cpx.solution.get_objective_value()

然后对于上面的示例，我收到（仅显示迭代 16-18）：

Itn      Primal Obj        Dual Obj  Prim Inf Upper Inf  Dual Inf
  16   1.4492800e-19  -1.0579911e-07  3.81e-14  7.11e-15  5.17e-25
  17   9.0580247e-21  -2.6449779e-08  1.91e-14  3.55e-15  2.33e-25
  18   5.6612645e-22  -6.6124446e-09  5.45e-14  7.11e-15  6.46e-27

[73.11695794600045, 73.11695794603409]
optimal
0.0

所以 a 和 b 是相等的，这是有道理的，因为我试图最小化它们的距离并且显然满足了约束。

然而，我的实际问题要复杂得多，我收到：

Itn      Primal Obj        Dual Obj  Prim Inf Upper Inf  Dual Inf
92   1.4468496e+06   1.2138985e+06  1.80e+02  2.64e-12  5.17e-02
  93   1.4468523e+06   1.2138969e+06  2.23e+02  2.17e-12  1.08e-02
  94   1.4468541e+06   1.2138945e+06  2.93e+02  2.31e-12  5.62e-02
  *    1.4457132e+06   1.2138598e+06  7.75e+00  7.61e-09  2.76e-02

num_best
1445714.46525

我现在有几个关于输出的问题，这些问题紧密相关：

1) 显然，它不是打印的对偶单纯形的 objective 值。为什么会这样，因为我将求解器设置为对偶单纯形？！

2) 我现在如何访问对偶单纯形的结果？由于 objective 值较小，我会对这些结果更感兴趣。

3) num_best 状态是否保证满足所有约束，即解决方案是否有效但不能保证是最优的？

4) Primal Obj 和 Dual Obj 差别很大。有什么策略可以减少它们的差异吗？

Answer 1

据我所知，get_objective_value 总是 returns 最好的原始边界（不管 lpmethod 是什么）。
可以使用 get_dual_values 检索有关对偶解的信息。
num_best 解决方案状态意味着解决方案可用，但没有最优性证明（参见 here）。关于这里的其余问题，这可能是最重要的一点。
您可以尝试打开 numerical emphasis parameter to see if that helps. There are also various tolerances you can adjust (e.g., optimality tolerance)。

请注意，我在上面使用的所有链接都是针对 CPLEX 12.6.3 的 C 可调用库（Python API 在内部调用）。

如何访问对偶单纯形求解器的解决方案？

How to access solution for dual simplex solver?

python

linear-programming

cplex

constraint-programming