寻找一个向量x，它最小化了c . 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
什么工具适合解决这种问题，有哪些使用示例？
- Bee
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
- Bee
2
你如何指定整数限制？ - dreeves
我编辑了上面的回答..看看它在哪里描述了BOUNDS部分。 - Bee
2
您指定了一个纯整数规划问题。大多数实际应用通常涉及所谓的混合整数规划，只有一些变量是整数。可以在此找到关于该主题的相当简明的教程和论文：http://mat.gsia.cmu.edu/orclass/integer/integer.html。
IP问题的典型解决技术是动态规划或分支定界法。搜索这些术语应该会帮助您找到一些免费软件、共享软件或学术代码。
祝好运！
IP问题的典型解决技术是动态规划或分支定界法。搜索这些术语应该会帮助您找到一些免费软件、共享软件或学术代码。
祝好运！
- Grembo
1
Mathematica
Mathematica 已经内置了此功能。（注：Mathematica 不是免费软件。）
LinearProgramming[c, m, b, Automatic, Integers]
输出：
{1, 1, 0}
- dreeves
1
Python: PULP
- Hamish Grubijan
2
除了线性规划，它能进行整数规划吗？ - dreeves
1@dreeves，我知道这个问题很旧，但是可以通过指定变量的类型（例如
x = LpVariable("Some Variable", cat="Integer")）来进行整数规划。默认的类型是连续型，还有一个二进制选项。 - undefined1
这类简单问题也可以用一种叫做约束编程的技术来解决。你可以在对应的维基百科条目中找到更多关于这种技术以及可用于解决这些问题的免费和商业求解器的详细信息。
如果涉及整数变量的问题比你所提到的更复杂，最好考虑使用通用的线性规划/整数规划求解器（如GLPK）。有很多选择，其中一些名称包括：LPSOLVE（免费）、IBM ILOG CPLEX（商业）。
- Samik R
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接