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 <henne...@web.cs.ndsu.nodak.edu> : > 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 <ke...@khn.org.uk>: >> > > 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 henne...@web.cs.ndsu.nodak.edu > "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 Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk