整数线性规划：示例和好工具？

Question

找到最小化 c 的向量 x 。x 受约束 m 。x >= b，x 整数。

这是一个示例输入集：

c : {1,2,3}
m : {{1,0,0},
     {0,1,0},
     {1,0,1}}
b : {1,1,1}

有输出：

x = {1,1,0}

什么是解决此类问题的好工具，以及如何使用它们的示例？

Answer 1

GLPK

我使用GLPK 的 glpsol提供了一个答案，但我希望有更好的方法来做到这一点（对于线性规划问题的这种简单的特殊情况，GLPK 似乎过于强大/通用）：

为了生成下面给出的 .mps 文件，您必须将矩阵逐行拆分为方程组，因此问题描述变为：

minimize

cost = 1 x_1 + 2 x_2 + 3 x_3

s.t. constraints:

S1 = 1 x_1 + 0 x_2 + 0 x_3
S2 = 0 x_1 + 1 x_2 + 0 x_3
S3 = 1 x_1 + 0 x_2 + 1 x_3

S1 >= 1
S2 >= 1
S3 >= 1

0 <= x1 <= 1
0 <= x2 <= 1
0 <= x3 <= 1

GLPK 文档有关于 .mps 格式的详细信息，但您可以指定行、列、rhs 和边界。在 ROWS 部分，'N' 和 'G' 指定约束的类型（分别为数字和大于）。在 BOUNDS 部分，'UI' 指定边界是上整数类型，强制解决方案为整数。

要在问题规范上运行求解器：

> glpsol --freemps example.mps -o example.out

示例.mps 文件：

NAME          VM
ROWS
 N cost
 G S1
 G S2
 G S3
COLUMNS
 x_1    cost    1.0
 x_1    S1      1.0
 x_1    S3      1.0
 x_2    cost    2.0
 x_2    S2      1.0
 x_3    cost    3.0
 x_3    S3      1.0
RHS 
 RHS1 cost   0.0
 RHS1 S1     1.0
 RHS1 S2     1.0
 RHS1 S3     1.0
BOUNDS
 UI BND1 x_1 1.0
 UI BND1 x_2 1.0
 UI BND1 x_3 1.0
ENDATA

输出：

Problem:    VM
Rows:       4
Columns:    3 (3 integer, 3 binary)
Non-zeros:  7
Status:     INTEGER OPTIMAL
Objective:  cost = 3 (MINimum)

   No.   Row name        Activity     Lower bound   Upper bound
------ ------------    ------------- ------------- -------------
     1 cost                        3
     2 S1                          1             1
     3 S2                          1             1
     4 S3                          1             1

   No. Column name       Activity     Lower bound   Upper bound
------ ------------    ------------- ------------- -------------
     1 x_1          *              1             0             1
     2 x_2          *              1             0             1
     3 x_3          *              0             0             1

Integer feasibility conditions:

INT.PE: max.abs.err. = 0.00e+00 on row 0
        max.rel.err. = 0.00e+00 on row 0
        High quality

INT.PB: max.abs.err. = 0.00e+00 on row 0
        max.rel.err. = 0.00e+00 on row 0
        High quality

End of output

另外，我不清楚如何直接获得解决问题的 x 向量，尽管它在本节上面的输出中进行了编码：

  No. Column name       Activity     
------ ------------    ------------- 
     1 x_1          *              1 
     2 x_2          *              1 
     3 x_3          *              0