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

Question

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

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

Возможно ли использовать LPSolve/ целочисленное программирование для оптимизации набора уникальных смежных целых чисел? Если это так, каков наилучший способ добавить ограничение для выражения 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