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

[Jan van Rijn]

Dear Kevin,

Thanks for your quick answer!

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?

Thanks,

Jan

2018-05-28 5:02 GMT-04:00 Kevin Martin <address@hidden>:

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