gams:model_permutations

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

— |
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 NOTICE
PRIVACY POLICY
gams/model_permutations.txt ยท Last modified: 2007/08/10 11:04 (external edit)