User Tools

Site Tools


Modeling permutations

Q: How can I model a vector of integer variables x(i) that can assume values 1,2,…,card(i), and each x(i) should be different, i.e. x(i) <> x(j) for all i <> j ?

This looks like we need the help of a permutation matrix P=p(i,j), where there is exactly one 1 in each row and column, and the other elements are zero. The identity matrix is a trivial example of a permutation matrix. Other ones just have some rows and columns of the identity matrix interchanged. To model this in a MIP use binary variables P and add the constraints:

   alias (i,j);
   binary variables p(i,j);
   equations rowsum(i) colsum(j) ;
   rowsum(i).. sum(j, p(i,j)) =e= 1;
   colsum(j).. sum(i, p(i,j)) =e= 1;

The different values for our vector x can now be calculated as:

   x(i) =e= sum(j, ord(j)*p(i,j));

Because x is automatically integer if p is integer, we can declare x as a normal continuous variable.

IMPRESSUM / LEGAL NOTICEPRIVACY POLICY gams/model_permutations.txt · Last modified: 2020/05/20 12:02 by Frederik Fiand