How can I implement an all different constraint in LPSolve?

Question

I have a problem whose solution must contain a unique value in each variable. E.g., 24 fighter pilots must depart in different hours of one day. So the solution must contain the integerse 1:24, in some order, according to a few constraints on the order.

I've tried using a Special Ordered Set to do that in LPSolve, but I can't understand how to use it. In any case, my trials have all been taking so long to execute, I cannot believe I am setting this up correctly. I could use brute force to solve it in 1/1000th of the time.

Is it feasible to use LPSolve/integer programming to optimize an set of unique adjacent integers? If so, what is the best way to add a constraint to express x1 != x2 != x3 != xN in R (or Python)? If not, which algorithm(s) should I be looking into for this kind of optimization?

Here is the code I have so far:

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)

flodel · Accepted Answer · 2013-04-16 23:58:22Z

4

Instead of solving for x1, x2, ..., xN, solve for a square matrix of booleans Y[i, j] where Y[i, j] == 1 means xi is in position j.

You need that each xi be assigned to exactly one j:

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

Your constraint that each xi be assigned to a distinct j writes:

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

Your original constraints and objective can still be expressed (if needed) in terms of x1, x2, ..., xN after defining each xi as a dummy integer variable:

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

edited Apr 16, 2013 at 23:58

answered Apr 16, 2013 at 23:37

flodel

89.3k21 gold badges190 silver badges225 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

How can I implement an all different constraint in LPSolve?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related