linear-programming - 二进制 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