我正在尝试使用R作为家庭作业来解决加权顶点覆盖问题的一个实例,我似乎无法将其弄好。我正在使用ROI
包(也可以使用linprog
)。
实例看起来像这样:
Edges:
A-B, A-C, A-G,
B-C, B-D, B-E, B-G,
C-E, C-F,
D-F,
E-G,
F-H, F-I,
G-H
Weights:
A - 10,
B - 7,
C - 4,
D - 7,
E - 12,
F - 25,
G - 27,
H - 3,
I - 9
我的代码是:
# a b c d e f g h i
constraints <- L_constraint(matrix(c(1, 1, 0, 0, 0, 0, 0, 0, 0, # a b
1, 0, 1, 0, 0, 0, 0, 0, 0, # a c
1, 0, 0, 0, 0, 0, 1, 0, 0, # a g
0, 1, 1, 0, 0, 0, 0, 0, 0, # b c
0, 1, 0, 1, 0, 0, 0, 0, 0, # b d
0, 1, 0, 0, 1, 0, 0, 0, 0, # b e
0, 1, 0, 0, 0, 0, 1, 0, 0, # b g
0, 0, 1, 0, 1, 0, 0, 0, 0, # c e
0, 0, 1, 0, 0, 1, 0, 0, 0, # c f
0, 0, 0, 1, 0, 1, 0, 0, 0, # d f
0, 0, 0, 0, 1, 0, 1, 0, 0, # e g
0, 0, 0, 0, 0, 1, 0, 1, 0, # f h
0, 0, 0, 0, 0, 1, 0, 0, 1, # f i
0, 0, 0, 0, 0, 0, 1, 1, 0, # g h
# end of u + v >= 1
1, 0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 0, 0, 0, 0, 0, 0, 0,
0, 0, 1, 0, 0, 0, 0, 0, 0,
0, 0, 0, 1, 0, 0, 0, 0, 0,
0, 0, 0, 0, 1, 0, 0, 0, 0,
0, 0, 0, 0, 0, 1, 0, 0, 0,
0, 0, 0, 0, 0, 0, 1, 0, 0,
0, 0, 0, 0, 0, 0, 0, 1, 0,
0, 0, 0, 0, 0, 0, 0, 0, 1,
# end of u >= 0
1, 0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 0, 0, 0, 0, 0, 0, 0,
0, 0, 1, 0, 0, 0, 0, 0, 0,
0, 0, 0, 1, 0, 0, 0, 0, 0,
0, 0, 0, 0, 1, 0, 0, 0, 0,
0, 0, 0, 0, 0, 1, 0, 0, 0,
0, 0, 0, 0, 0, 0, 1, 0, 0,
0, 0, 0, 0, 0, 0, 0, 1, 0,
0, 0, 0, 0, 0, 0, 0, 0, 1),
# end of u <= 1
ncol = 9), # matrix
dir = c(rep(">=", 14+9), rep("<=", 9)),
rhs = c(rep(1, 14), rep(0, 9), rep(1, 9))) # L_constraint
objective <- L_objective(c(10, 7, 4, 7, 12, 25, 27, 3, 9))
problem <- OP(objective, constraints, rep("C", 9),
maximum = FALSE)
solution <- ROI_solve(problem, solver = "glpk")
结果是No solution found.
我不知道我做错了什么,但它也可能是明显的东西。无法理解它 - 解决方案应始终存在,即使它需要所有顶点(即所有变量都> = 0.5)。
如果重要的话,我在Arch Linux上运行R从存储库(版本2.14)并通过install.packages("...")
安装包。
谢谢!
好的,解决了。问题是我没有将byrows = TRUE
添加到矩阵定义中。此外,我将ncol = 9
改为nrow = ...
。显然matrix()
功能没有像我预期的那样工作。