Re: Slow performance on "Select minimum" task

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 <[email protected]>:

> Hi,
>
> > On 23 May 2018, at 19:24, Jan van Rijn <[email protected]> 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
>
>

_______________________________________________
Help-glpk mailing list
[email protected]
https://lists.gnu.org/mailman/listinfo/help-glpk