二进制线性规划与整数线性规划

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

- someonr

---

由于某种原因，添加“可选约束名称”似乎有所帮助。我开始认为这可能是一个错误... - someonr

Answer 1

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

在您的问题 A 中，设置“bin x”会覆盖约束条件“x >=1”。这就是为什么最优解为0的原因。

来自文档：

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

- Ram Narasimhan

---

我无法从文档中读取到 bin 覆盖任何约束的信息。这种行为是否是有意的？ - someonr