Взвешенное покрытие вершин (в виде линейного программирования) в R с пакетом ROI - PullRequest
Новая
       13

Взвешенное покрытие вершин (в виде линейного программирования) в R с пакетом ROI

0 голосов
/ 05 января 2012

Я пытаюсь решить проблему взвешенного покрытия вершин, используя 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("...").

Спасибо!

1 Ответ

0 голосов
/ 06 января 2012

Хорошо, решил.Проблема заключалась в том, что я не добавил byrows = TRUE к определению матрицы.Кроме того, я изменил ncol = 9 на nrow = ....Очевидно, функция matrix() не сработала, как я ожидал.

...