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:nu…

Accepted Answer

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
```

How can I implement an all different constraint in LPSolve?

Solution

Problem