> 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.
Hello Erwin,
ReplyDeleteyour second formulation is a relaxation only, as the PPT presentation suggests. How can you be sure that ALL-DIFFERENT holds when adding this relaxation to your linear program? Or did you mean that you need to include your first and the second, tighter formulation into the LP for maximum efficiency?
Thanks!
Yes I think you are correct, and I should say something more about this. See also: http://ww.lse.ac.uk/collections/operationalResearch/pdf/PWilliams_2001_IJOC.pdf.
ReplyDelete