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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]