In my ILP problem I need permutations of \(\{1, 2, ..., n\}\). Below is what I have come up with, the issue is: it uses \(O(n^2)\) binary variables. Is it possible to express the alldifferent constraint with \(O(n)\) variables (integer allowed) and constraints, neglecting poor relaxation? If yes, how? (The goal is to use the students version of AMPL :) ) If not, what reasonable formulations are there? I am particularly interested in formulations using \(O(n)\) variables: many of the constraints might be eliminated by the presolve, based on other constraints in my ILP problem. Finally, a fragment of my attempt in AMPL:
Solution: I turned the ILP into a CSP and now I am using IBM ILOG CP Optimizer which is free for academic users. asked 22 Aug '12, 07:25 Ali 
You can use n(n1)/2 binary
You can also use the excellent review of how to represent absolute value by @Paul Rubin. Then state
In general, this will introduce auxiliary binary variables or SOS, unfortunately. Many thanks! AFAIK, we don't have indicator variables in AMPL and I am trying to use the students' version of it, hence the question. I could model the indicator variables with binary ones but I would end up with O(n^2) many of them...
(22 Aug '12, 08:14)
Ali
Upvoted as I can do it now :) In the meantime, I applied for CPLEX at IBM Academic Initiative. Perhaps its better than AMPL in my case.
(22 Aug '12, 08:29)
Ali
1
With CPLEX you'll also get CP optimizer, a constraint programming solver. In it you can directly state a all different constraint on integer variables. I don't know if CP Optimizer would be a good fit for the rest of your model though.
(22 Aug '12, 08:54)
jfpuget
I can turn my problem into a CSP and it is fairly natural too in that form. The IBM ILOG OPL Scripting seems like a viable alternative to AMPL. Thank you for pointing it out!
(22 Aug '12, 09:14)
Ali
2
See also: H.P.Williams, Hong Yan, "Representations of the alldifferent Predicate of Constraint Satisfaction in Integer Programming," INFORMS Journal on Computing, Vol. 13 (2001) 96103
(22 Aug '12, 10:48)
erwin
showing 5 of 6
show 1 more comments

Actually, AMPL does support indictor constraints (INFORMS06.pdf, slide 33) when used with CPLEX. It also supports lazy constraints (slide 32); so while you cannot avoid \(O(n^2)\) clutter to model alldifferent, you could try making the extra constraints lazy and see if that helped with solution time. (Don't know that it will, but it's worth a try.) answered 22 Aug '12, 08:32 Paul Rubin ♦♦ fbahr ♦ Voted up as I stole your material ;)
(22 Aug '12, 08:36)
jfpuget

You can formulate this as a constraint programming problem in AMPL using the
AMPL already supports two constraint programming solvers, IBM/ILOG CP Optimizer and Gecode. See "LOGIC" AND CONSTRAINT PROGRAMMING EXTENSIONS for more details. answered 18 Apr '13, 13:12 vitaut 