User Tools

Site Tools


gams:model_permutations

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

gams:model_permutations [2007/08/10 11:04] (current)
Line 1: Line 1:
 +====== Modeling permutations ======
 +
 +
 +How can I model in GAMS the following restriction?​ A vector of integer variables x(i) 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=pij,
 +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: 2007/08/10 11:04 (external edit)