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

[Kevin Martin]

> 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