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
