加權頂點覆蓋（如線性規劃）與ROI包

Question

我試圖解決用R表示功課加權頂點覆蓋問題的實例，我似乎無法得到它的權利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("...")安裝的軟件包。

謝謝！

Answer 1

好了，解決了這個問題。問題是我沒有將byrows = TRUE添加到矩陣定義中。此外，我改變了ncol = 9到nrow = ...。顯然matrix()函數沒有按預期工作。