[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## Re: [Help-glpk] 2D Matrix, One value per column constraint

**From**: |
Andrew Makhorin |

**Subject**: |
Re: [Help-glpk] 2D Matrix, One value per column constraint |

**Date**: |
Thu, 21 Feb 2008 11:46:09 +0300 |

>* I have a var w[i,j] which is a matrix with i rows and j column*
>* representing the values I'm looking for. I have been able to model*
>* most of my constraints linearly, but I'm stuck at one of the*
>* constraints. The constraint is that there can only be one value per*
>* column and the rest of the values have to be zero. I'm not sure how I*
>* can model this linearly.*
>* I tried introducing a second var x[i,j] which would be a binary value*
>* indicating if the value w[i,j] was zero or another value and then*
>* putting constraints on the x[i,j] values. I tried this in two ways:*
>* 1. Making the x[i,j] dependent on the w[i,j] values like so:*
>* s.t. set_x1{i in I, j in J}: if(w[i,j] > 0) then x[i,j] = 1;*
>* This is an invalid statement.*
This essentialy depends on values which w[i,j] may take on.
In a most general case you can model your condition as follows:
s.t. foo{j in J}: sum{i in I} x[i,j] <= 1;
s.t. bar{i in I, j in J} w[i,j] <= w_max[i,j] * x[i,j];
The first constraint requires auxiliary (0,1)-matrix x[i,j] to have
at most one 1 in each column; it is assumed that x[i,j] is binary.
In the second constraint w_max[i,j] is a parameter which is an upper
bound of w[i,j]; it is assumed that all w[i,j] >= 0.