r - 如何在 LPSolve 中实现完全不同的约束？

Question

我有一个问题，其解决方案必须在每个变量中包含一个唯一值。例如，24 名战斗机飞行员必须在一天的不同时间起飞。所以解决方案必须包含整数 1:24，以某种顺序，根据顺序上的一些限制。

我曾尝试在 LPSolve 中使用特殊有序集来执行此操作，但我不明白如何使用它。无论如何，我的试验都花了很长时间来执行，我不敢相信我设置正确。我可以使用蛮力在 1/1000 的时间内解决它。

使用 LPSolve/整数规划来优化一组唯一的相邻整数是否可行？如果是这样，添加约束以在 R(或 Python)中表达 x1 != x2 != x3 != xN 的最佳方法是什么？如果不是，我应该研究哪种算法来进行这种优化？

这是我目前的代码:

library('lpSolveAPI')

people <- c('Joe', 'Bob', 'Dave', 'Mike')
number_of_people = length(people)

model <- make.lp(0, number_of_people)
set.type(model, 1:number_of_people, 'integer')
set.bounds(model, lower=rep(1, number_of_people), 
      upper=rep(number_of_people, number_of_people))

constraint_names <- c('Bob < Mike')
add.constraint(model, c(0, 1, 0, -1), '<=', -0.1)
constraint_names <- append(constraint_names, 'Mike > Joe')
add.constraint(model, c(-1, 0, 0, 1), '>=', 0.1)
dimnames(model) <- list(constraint_names, people)

#not sure about this
#add.SOS(model, 'different positions', type=2, 
#priority=1,columns=1:number_of_people, weights=rep(1, number_of_people))

set.objfn(model, rep(1, length(people)))
lp.control(model, sense='min')
write.lp(model,'model.lp',type='lp')

solve(model)
get.variables(model)

Answer 1

不是求解 x1, x2, ..., xN，而是求解 bool 方阵 Y[i, j] 其中 Y[ i, j] == 1 表示 xi 在位置 j。

您需要将每个 xi 分配给恰好一个 j:

sum(Y[i, j]) == 1           # sum over j, for each i

您将每个 xi 分配给不同的 j 的约束如下:

sum(Y[i, j]) == 1           # sum over i, for each j

在将每个 xi 定义为虚拟整数后，您的原始约束和目标仍然可以用 x1, x2, ..., xN 表示(如果需要)变量:

xi = sum(j * Y[i,j])  # sum over j, for each i