时间戳

首页 > 解决方案 > 对于线性规划求解器，我们可以期待什么样的求解质量？

linear-programming - 对于线性规划求解器，我们可以期待什么样的求解质量？

问题描述

我正在尝试解决线性约束满足问题。所以我拿起“GNU 线性编程工具包”，写下我的约束，并用一些简单的目标函数让它松散。

GLPK 声称找到了解决方案，但如果我根据约束条件检查它，他们并不满意。即应该为 <= 0 的表达式实际上在 1e-10 左右。即略大于0。

通过设置约束以返回多面体的切比雪夫中心，我可能可以解决这个问题，但我想知道线性规划求解器是否会出现这种差异，或者我应该将其报告为 GLPK 人员的错误。

标签： linear-programmingglpk

解决方案

所有 LP 求解器都使用可行性和其他公差。这些是必需的，因为浮点计算不精确。您可以稍微拧紧它们，但一般来说，最好不要触摸它们。

因此，您应该期待具有以下属性的解决方案：

  • 变量稍微超出其范围
  • 约束可能会被少量违反
  • 二进制和整数变量略为非整数

推荐阅读