Friday, January 30, 2009

All-different

> Hi I am trying to solve a certain linear integer problem with lp_solve.
> I know that the solution set (24 variables) is (1,2...,24) and I am trying to figure out a way to input to lp_solve this array in order to get a feasible solution.

> In other words is it possible to put have a (or a set) of constraints saying that x1 ,x2,....,x24 belong to (1 ,2,...24) set but they are distinct (for instance x1=24, x2=3,x3=21 etc...).


This is called the ALL-DIFFERENT constraint. See here for an example.

One way of modeling this as a MIP is:

binary variable p(i,j) (i,j=1..24)
sum(i, p(i,j)) = 1;  for all j
sum(j, p(i,j)) = 1;  for all i
a(i) = i     (constant)
x(i) = sum(j, p(i,j)*a(j))

A tighter formulation would be:

sum(i, x(i)) = 0.5*n*(n+1), where n=24
sum(j in J, x(j)) ≥ 0.5*card(J)*(card(J)+1) where J is an element of the power set of {1,..,24} with card(J) < 24.
See this presentation.