Sunday, October 16, 2011

Sorting by MIP

Here is a toy model that illustrates that certain models are poorly suited for solving by MIP solvers.

Sorting data is a rather elementary operation. Surprisingly, GAMS has nothing built in for this. There is an external tool for sorting (gdxrank), but in some environments (e.g. NEOS) this is not allowed. There are some slower GAMS coding tricks that can help. Of course we can also write a simple MIP model that performs sorting:

$ontext

  
mip model for sorting

$offtext


set i /i1*i100/;

parameter p(i) "original data"
;
p(i) = uniform(0,1);


alias
(i,j);
binary variable x(i,j) "permutation matrix"
;
variable y(i) "sorted version of p"
;
variable
z;

equations

  dummy   
"dummy objective"
  assign1 
"assignment constraint"
  assign2 
"assignment constraint"
  ydef    
"y is permuted version of x"
  sort    
"require y to be sorted"
;

dummy.. z =e= 0;

assign1(i)..
sum(j, x(i,j)) =e= 1;
assign2(j)..
sum
(i, x(i,j)) =e= 1;
ydef(i)..    y(i) =e=
sum
(j, x(i,j)*p(j));
sort(i+1)..  y(i+1) =g= y(i);


model m /all/
;
solve
m minimizing z using mip;

display

 
"-----------------------------------------------------------------------",
 
"Results"
,
 
"-----------------------------------------------------------------------"
,
   p,y.l;


This is quite slow however. n=100 is no problem, but n>200 will require significant time (>1000 seconds). Constraints assign1 and assign2 form an assignment problem, which is easy to solve. The simple extension will cause relaxation based MIP solvers to slow down enormously. Obvious question: are there better formulations? I would guess constraint programming solvers would do better on this.

For some instances Gurobi is doing very good, probably because of its excellent heuristics. But this is not the case for all instances: in some cases it is just as slow as other solvers.

The above model contains two noteworthy modeling tricks:

  • a dummy objective so that we stop after the first integer solution is found
  • the equation sort is indexed over i+1 so that the last one is not generated: this equation has card(i)−1 members.