Looks for a Constraint Satisfaction Algorithm in R

Question

I have what I believe is a fairly simple constraint satisfaction problem but can not find the proper package for implementing an algorithm.

I wish to subset a data set of some points. Each point comes with list of other data points it must excluded from the subset if it were to be included. For example:

  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            

I want to maximize the amount of points I can put in my subset without breaking any rules. My data contains 1000s of points. What are the names of algorithms set up for this type of problem? Are they any packages in R that I should look at? Should I look to other programing languages?

Answer 1

Solve as an Integer Linear Programming (ILP) problem with eight binary variables, each representing one of the data points from A to H, for example with the help of package 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

That is, one solution is (B, E, F, H); of course, there may be other combinations of the same size, for instance (A, D, F, G). You can get more solutions by setting option num.bin.solns to some value > 1.