4

找到一个使 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}

解决此类问题的好工具有哪些，以及如何使用它们的示例？

4

7 回答 7

5

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
于 2009-12-28T18:14:46.043 回答
2

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

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

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

祝你好运

于 2009-12-29T19:38:45.270 回答
1

数学

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

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

输出：

{1, 1, 0}
于 2009-12-28T18:01:04.043 回答
1

蟒蛇：纸浆

于 2009-12-28T18:07:33.360 回答
1

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

于 2009-12-30T21:58:39.773 回答
1

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

于 2015-02-14T16:08:23.437 回答
0

scicomp.stackexchange.com 上有一个类似的问题和一个列出几个库的答案。

于 2012-01-11T02:22:39.297 回答