二进制 LP 与整数 LP

Question

我想知道为什么以下线性程序之间存在差异。它们写在LP file format中。我认为 x=1 在这两种情况下都是最佳解决方案。

程序A：

min: x;
x >= 1;
bin x;

输出：

Value of objective function: 0

Actual values of the variables:
x                               0

程序 B（用整数约束和两个附加约束模拟二元约束）：

min: x;
x >= 1;
x <= 1;
x >= 0;
int x;

输出：

Value of objective function: 1.00000000

Actual values of the variables:
x                               1

Answer 1

是的，这是 lpSove 的一个小怪癖，与单变量约束有关。

在您的问题 A 中，设置 'bin x' 最终会覆盖约束 'x >=1.' 这就是为什么给出 0 作为最优解的原因。

来自documentation：

Note that for bounds on variables, you should not put labels before them. This is because lp_solve then makes this an extra restriction. If you don't put a label before single variables then lp_solve doesn't have to create an extra row for bounds on variables, resulting in better performance.

So it is better to write:
 x1 >= 1;
than
 r_x1: x1 >= 1;
Note that this is only for single variables, so myrow: x1 + x2 >= 2;

performs as well as
x1 + x2 >= 2;

在你的问题 A 中，你有一个单一的变量约束。如果未明确命名，'bin' 声明将覆盖该约束。正如您正确指出的那样，如果您通过 命名它 来明确约束，那么 lpSolve 将为 x1 创建一个新行，从而遵守约束并且 'bin' 无法覆盖它。

min: x;
a: x >= 1.0;
bin x;

会给你：

Value of objective function: 1.00000000

Actual values of the variables:
x                               1

二进制 LP 与整数 LP

binary LP vs. integer LP

linear-programming

lpsolve