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's gravatar image

Ali
7336
accept rate: 0%

edited 12 Dec '14, 07:45


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.

link

answered 22 Aug '12, 08:03

jfpuget's gravatar image

jfpuget
2.5k310
accept rate: 8%

edited 01 Feb '14, 15:19

fbahr's gravatar image

fbahr ♦
4.6k716

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

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.)

link

answered 22 Aug '12, 08:32

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

edited 22 Aug '12, 09:03

fbahr's gravatar image

fbahr ♦
4.6k716

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 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.

link

answered 18 Apr '13, 13:12

vitaut's gravatar image

vitaut
32718
accept rate: 20%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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:

×231
×101
×6

Asked: 22 Aug '12, 07:25

Seen: 3,802 times

Last updated: 12 Dec '14, 07:45

OR-Exchange! Your site for questions, answers, and announcements about operations research.