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

[Jan van Rijn]

Dear Kevin,

Yes, it is indeed a matrix of floats.

Thanks for the quick replies and your help though :)

Best,

Jan

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

> On 29 May 2018, at 16:32, Jan van Rijn <address@hidden> wrote:
>
> It is true that I introduced a binary variable per matrix element, and it would be great if we could get rid of it.
> From your formulation, I struggle to understand the last statement:
> What exactly does M(j, i) represent?

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.

I guess the best approach depends on your requirements. If you are just after something ok and quick that scales, I would start with a convex approximation of the column minimum, formulate a convex problem based on this, and use something like Ipopt to solve it, round the result. If instead, you want something within known bounds of optimal you can try adjusting the glpk termination criteria (I think by default it tries to prove optimality) or maybe provide some heuristics to help prune the search space, see GLP_IHEUR in the glpk manual.

Thanks,
Kev