3

ソリューションの各変数に一意の値を含める必要がある問題があります。たとえば、24 人の戦闘機パイロットは、1 日の異なる時間帯に出発する必要があります。したがって、ソリューションには、順序に関するいくつかの制約に従って、ある順序で整数の 1:24 が含まれている必要があります。

LPSolve でそれを行うために Special Ordered Set を使用しようとしましたが、その使用方法がわかりません。いずれにせよ、私の試行はすべて実行に時間がかかりすぎており、これを正しく設定しているとは信じられません. 力ずくで1000分の1の時間で解くことができました。

一意の隣接する整数のセットを最適化するために 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それぞれを正確に 1 つに割り当てる必要があります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 に答える