How to express the "not equals" relation in linear programming?

Question

I want to solve a LP problem in Python with the library Pulpe (or any other).

I want to express a constraint stating that all my variables must have different values, (their domain is {0, 1, 2, 3... N} for a given integer N.) that is x_1 != x_2 != x_3 ... != x_N.

The solver gives me a solution when I do not add any constraint related to what I mentionned above but when I do, it tells me that the system is not feasible even though it has one solution.

In order to add the "all different" constraint, I did the following:

for x_i in variables:
    for x_j in variables:
        if the following constraint has not been already added and x_i != x_j:
            my_problem += x_i - x_j >= 1, "unique name for the constraint"

The previous code does not work. When I want to add the constraint x_i != x_j, it just doesn't work. So, as I am working with a bounded set of integers, I can (I think) rewrite the "not equals" as x_i - x_j > 0. Pulpe tells me that it does not handle the ">" operator between int and LpAffineExpression so I wrote x_i - x_j >= 1. However, it runs but it seems that it does not work and I can't figure out why.

Answer 1

There are a few ways of doing this, depending on the exact situation.

You seem to have n variables x[i]. They can assume values {0,...,n} and must be all different.

As an aside: your notation x[1] ≠ x[2] ≠ x[3].. is not completely correct. E.g. x[1]=1, x[2]=2, x[3]=1 would satisfy x[1] ≠ x[2] ≠ x[3].

The all-different constraint can be written pairwise as x[i] ≠ x[j] for all i < j (we don't want to check i and j twice). This inequality can be restated as: x[i] ≤ x[j]-1 OR x[i] ≥ x[j]+1. The OR condition can be implemented in a MIP model as:

 x[i] ≤ x[j]-1 + M δ[i,j]        ∀ i < j
 x[i] ≥ x[j]+1 - M (1-δ[i,j])    ∀ i < j
 δ[i,j] ∈ {0,1}

where M=n+1. We added extra binary variables δ[i,j].

This is the most direct formulation of a "not-equal" construct. It also has relatively few binary variables: about n^2/2. Other formulations are also possible. For more information see link.

Note that constraint programming solvers often have built-in facilities for the all-different constraint, so it may be easier to use a CP solver (they can also be more efficient for models with all-different constraints).