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
outputs:
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