Ищет алгоритм удовлетворения ограничений в R

Question

У меня есть, на мой взгляд, довольно простая проблема удовлетворения ограничений, но я не могу найти подходящий пакет для реализации алгоритма.

Я хочу подгруппировать набор данных некоторых точек.Каждая точка поставляется со списком других точек данных, которые она должна исключить из подмножества, если она должна быть включена.Например:

  points Must_Exclude
1      A            B,E
2      B            
3      C            F,G,H
4      D            
5      E            D
6      F            
7      G            H
8      H            

Я хочу максимизировать количество баллов, которое я могу положить в мое подмножество, не нарушая никаких правил.Мои данные содержат тысячи баллов.Как называются алгоритмы, предназначенные для этого типа проблемы?Это какие-нибудь пакеты в R, на которые мне стоит взглянуть?Стоит ли искать другие языки программирования?

Answer 1

Решить как задачу целочисленного линейного программирования (ILP) с восемью двоичными переменными, каждая из которых представляет одну из точек данных от A до H, например, с помощью пакета lpSolve .

## Define inputs
obj <- rep(1, 8)                # 8 binary variables for A..H
A <- matrix(rbind(              # constraints:
    c(1,1,0,0,0,0,0,0),         # A <> B
    c(1,0,0,0,1,0,0,0),         # A <> E
    c(0,0,1,0,0,1,0,0),         # C <> F
    c(0,0,1,0,0,0,1,0),         # C <> G
    c(0,0,1,0,0,0,0,1),         # C <> H
    c(0,0,0,1,1,0,0,0),         # D <> E
    c(0,0,0,0,0,0,1,1)), 7, 8)  # G <> H
dir <- rep("<=", 7)             # all constraints '<='
rhs <- rep(1, 7)                # all right hand sides = 1
## maximise solution
sol <- lpSolve::lp("max", obj, A, dir, rhs,
                   all.bin = TRUE, num.bin.solns = 1)
sol$solution
## [1] 0 1 0 0 1 1 0 1

То есть, одним из решений является (B, E, F, H);конечно, могут быть другие комбинации того же размера, например (A, D, F, G).Вы можете получить больше решений, установив для параметра num.bin.solns значение> 1.