如何在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，求解布爾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