Как я могу реализовать все различные ограничения в LPSolve?

Question

У меня проблема, решение которой должно содержать уникальное значение в каждой переменной. Например, 24 пилота-истребителя должны уходить в разные часы одного дня. Таким образом, решение должно содержать целые числа 1:24, в некотором порядке, в соответствии с несколькими ограничениями на порядок.

Я пробовал использовать специальный заказ, чтобы сделать это в LPSolve, но я не могу понять, как его использовать. В любом случае, мои испытания все так долго выполнялись, я не могу поверить, что правильно настроил это. Я мог использовать грубую силу, чтобы решить ее в 1/1000-й раз.

Возможно ли использовать программирование LPSolve/integer для оптимизации набора уникальных смежных целых чисел? Если да, то каким образом можно добавить ограничение для выражения x1! = X2! = X3! = XN в R (или Python)? Если нет, то какой алгоритм (ы) я должен искать для такого рода оптимизации?

Вот код, который я до сих пор:

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 

Ваших оригинальных ограничения и цель может еще выражать (если необходимо) в терминах x1, x2, ..., xN после определения каждого xi в качестве целочисленной переменной:

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