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

[Kevin Martin]

Hi,

> On 23 May 2018, at 19:24, Jan van Rijn <address@hidden> wrote:
> 
>  However, even for small problem instances (D=1, R=25, D=256) the MIP solver 
> already takes 14 seconds; setting the parameters higher results in incredibly 
> high runtimes. 
> 

I don’t understand Python, but it looks from your code as if you are 
introducing a binary variable and constraint per element in your matrix. If I 
have understood your problem correctly, there is a much smaller formulation. If 
you’ve not tried it yet, it might be worth a go.

1. Let x_j be a binary variable which is 1 if we include row j.
2. Let y_i be a non-negative variable which is the minimum value in column i 
under the row selection.

3. Minimise \sum_i y_i
4. Subject to \sum_j x_j = D
5. Subject to \forall i y_i >= 1-\sum_{j:M(j,i)=1} x_j

Some notes:

- The y_i variables do not have to declared integer as they will be 
automatically integer if the x_j are. You may get better branching if they are 
integer though.
- The constraint (5) forces the min in the column to be 1 if we include NO rows 
that have 0s. We do not have to specifically force it to 0 if there are 0s in 
the column as the objective will do this for us.
  
> Is there something that should be taken into consideration? Could this be a 
> problem with the GLPK solver?

Solving (by this I mean proving optimality) an arbitrary integer program is an 
NP problem, and therefore currently behaves exponentially. Solvers use very 
clever tricks and heuristics to make large problems tractable, but this makes 
them very sensitive to things like the problem formulation. You can represent 
the exact same problem different ways and get very different performances.

Also, when measuring time, beware of the time spent building the problem. I 
doubt it has much effect in this case, but you can get a better measure of it 
by writing mps files from Python, and then solving these files wth the solver 
command line, you should then be able to get the actual solve time. I am very 
wary of this as recently we scaled two dimensions in a problem we are solving 
at work, one by 4x, the other by 5x. We saw a rise in the time from 15 mins to 
5.5 hours. However, we have since discovered that 4 of those 5.5 hours are 
spent calculating derivatives in our code that builds the objective function 
and constraint matrix, rather than the solver itself.
  
> 
> Best,
> Jan

Thanks,
Kev