Re: Slow performance on "Select minimum" task

Dear Michael,

Thanks a lot, this seems like a very elegant formulation -- the performance
seems much better than my initial performance.

I need to add two things:
- It is my conjecture that there should be an additional constraint, i.e.,
y[r,c] > 0 (Otherwise non-selected rows could participate towards a lower
score)
- M[r,c] should contain positive values (which guarantees that y[r,c] == 1
iff x[r] - SUM x[s] == 1)

Thanks again. This really helped a lot :)

Best regards,
Jan



2018-06-05 11:05 GMT-04:00 Michael Hennebry <[email protected]>
:

> 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 <[email protected]>:
>>
>
> 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   [email protected]
> "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
>

_______________________________________________
Help-glpk mailing list
[email protected]
https://lists.gnu.org/mailman/listinfo/help-glpk