3

我有一个问题，其解决方案必须在每个变量中包含一个唯一值。例如，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)
4

1 回答 1

3

不是求解，而是求解均值所在的x1, x2, ..., xN布尔方阵。Y[i, j]Y[i, j] == 1xij

您需要将每个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

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

xi = sum(j * Y[i,j])  # sum over j, for each i
于 2013-04-16T23:37:52.620 回答