[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.