在 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

我想在不违反任何规则的情况下最大化我可以放入我的子集中的点数。我的数据包含 1000 个点。为此类问题设置的算法名称是什么？它们是我应该查看的 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.

在 R 中寻找约束满足算法

Looks for a Constraint Satisfaction Algorithm in R

r

algorithm

optimization

combinatorics

discrete-optimization