二元LP与整数LP

Question

我想知道为什么下面的线性规划会有区别。它们是用LP文件格式编写的。我假设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作为最优解的原因。

来自文档

注意，对于变量的界限，不应该将标签放在它们前面。这是因为lp_solve使这成为一个额外的限制。如果您不将标签放在单个变量之前，那么lp_solve就不必为变量的边界创建额外的行，从而提高性能。 所以最好写： x1 >= 1； 比 r_x1: x1 >= 1； 请注意，这仅适用于单变量，所以myrow: x1 + x2 >= 2； 表现得和 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