integer programming formulation of the alldifferent constraint

 7 1 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: param n_row; param n_col; set ROWS := {1 .. n_row}; set COLS := {1 .. n_col}; var row{ROWS,COLS} binary; var P{i in ROWS} = sum {k in COLS} row[i,k]*k; s.t. row_r{i in ROWS}: sum{j in COLS} row[i,j] = 1; row_c{j in COLS}: sum{i in ROWS} row[i,j] = 1;  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 73●3●7 accept rate: 0%

 6 You can use n(n-1)/2 binary diff constraints. If x and y are integer variables, and iv an indicator variable in CPLEX you can state that x and y are different as follows.  iv = 1 <-> x - y = 0 iv = 0  You can also use the excellent review of how to represent absolute value by @Paul Rubin. Then state  |x - y| >= 1  In general, this will introduce auxiliary binary variables or SOS, unfortunately. answered 22 Aug '12, 08:03 jfpuget 2.5k●3●10 accept rate: 8% fbahr ♦ 4.6k●7●16 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 1 O(n^2) but less binaries still, n(n-1)/2 instead of n^2 (22 Aug '12, 08:26) jfpuget 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 all-different Predicate of Constraint Satisfaction in Integer Programming," INFORMS Journal on Computing, Vol. 13 (2001) 96-103 (22 Aug '12, 10:48) erwin showing 5 of 6 show 1 more comments
 5 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 ♦♦ 14.6k●5●13 accept rate: 19% fbahr ♦ 4.6k●7●16 Voted up as I stole your material ;) (22 Aug '12, 08:36) jfpuget
 3 You can formulate this as a constraint programming problem in AMPL using the alldiff constraint: param n; var P{i in 1..n} integer >= 1 <= n; s.t. alldiff_P: alldiff{i in 1..n} P[i];  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 327●1●8 accept rate: 20%
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags: