help-glpk
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Help-glpk] Slow performance on "Select minimum" task


From: Michael Hennebry
Subject: Re: [Help-glpk] Slow performance on "Select minimum" task
Date: Tue, 5 Jun 2018 10:05:59 -0500 (CDT)
User-agent: Alpine 2.20 (DEB 67 2015-01-07)

On Tue, 29 May 2018, Jan van Rijn wrote:

Yes, it is indeed a matrix of floats.

2018-05-29 15:45 GMT-04:00 Kevin Martin <address@hidden>:

I have re-read your problem and I may have misinterpreted it. I thought
your matrix was binary, as in each element was in {0,1}, the sum condition
was supposed to be i:M(j,i)=0, which would be the sum of all the row
inclusion (x_j) variables where the Matrix element for the column was 0.
The idea being that if none of the rows corresponding to a are 0 selected,
the minimum of the column must be 1.

As I re-read your original email, I now think that each element may be
fractional somewhere in the closed interval [0,1]. If this is the case, I
think the problem may be quite hard, for general M, I can?t think of an
obvious way to formulate it better.

A similar mechanism still works:

y[r,c] >= x[r] - SUM x[s]
                 s in Q[r,c]

x is binary
y need not be specified binary
Q[r,c] = { s : M[s,c]< M[r,c] }
The objective is SUM y[r,c]*M[r,c]
                 r,c

The definition of Q assumes no ties.
Ties may be broken arbitrarily, but must be consistent.
You may turn M[s,c]< M[r,c] into a lexigraphic comparison
of (M[s,c], s) and (M[r,c], r) .

--
Michael   address@hidden
"Sorry but your password must contain an uppercase letter, a number,
a haiku, a gang sign, a heiroglyph, and the blood of a virgin."
                                                             --  someeecards



reply via email to

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