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

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

您指定了一个纯整数规划问题。大多数实际应用通常涉及所谓的混合整数规划，其中只有一些变量是整数。一个相当简洁的教程和有关该主题的论文可以在这里找到：

http://mat.gsia.cmu .edu/orclass/integer/integer.html

IP 问题的典型解决技术是动态规划或分支定界。搜索这些术语应该可以帮助您找到一些免费软件、共享软件或学术代码。

祝你好运

Answer 2

Mathematica

Mathematica 内置了这个功能。（注意：Mathematica 不是免费软件。）

LinearProgramming[c, m, b, Automatic, Integers]

输出：

{1, 1, 0}

Answer 3

Python：PULP

Answer 4

这些类型的简单问题也可以使用称为约束规划的技术来解决。您可以从相应的维基百科条目<中找到有关该技术以及可用于解决这些问题的免费和商业求解器的更多详细信息/a>.
如果涉及整数变量的问题比您提到的更复杂，最好考虑通用线性规划/整数规划求解器（如 GLPK）。它们有很多，一些名称是：LPSOLVE（免费）、IBM ILOG CPLEX（商业）。

Answer 5

我正在使用 Python &皮莫。项目网站上有一个很好的优势概述：http://www.pyomo.org

Answer 6

scicomp.stackexchange.com 上有类似的问题并且列出了一些库的答案。

Answer 7

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

example.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