Hello Andrew, > It is difficult to say how this or that heuristic used to choose > branching variable affects the solution process. I only would like to > draw an attention that reformulation of mip may essentially reduce the > solution time (though this is well known).
My understanding is, to solve this problem fast: 1) Symmetries should be removed. 2) The usage of trucks should be modeled as binaries. 3) Branching should be on trucks first. 4) Redundant constraints may help. I have added symmetry removal and result output to the following file: http://www.nabble.com/file/p26070245/trick3.mod trick3.mod I guess the problem is interesting enough to be added to the GLPK examples. Best regards Xypron Andrew Makhorin wrote: > >> When I removed >> redundant_constraint: >> sum{i in TRUCKS} capacity[i] * y[i] >= sum{j in PACKAGES} size[j]; >> [...] >> Is it this 40 % saving you are refering to? >> Interestingly when MIR cuts are enabled AND the redundant constraint is >> removed >> GLPK gets really slow. >> [...] >> With --first specified the solution was even faster. > > It is difficult to say how this or that heuristic used to choose > branching variable affects the solution process. I only would like to > draw an attention that reformulation of mip may essentially reduce the > solution time (though this is well known). > > If you try to solve the initial formulation, you can see that the > model is very hard for glpk. Cuts and different branching heuristics > do not help. I also tried pseudo-cost branching, it also does not help. > > Just another example. Look at the article "Rapid Mathematical > Programming or How to Solve Sudoku Puzzles in a few Seconds" by > Thorsten Koch at www.zib.de/Publications/Reports/ZR-05-51.pdf . > There are two formulations of the Sudoku puzzle: the first one (p. 5) > uses integer variables and all-different constraints; it cannot be > solved with cplex for more than six hours and one million branching > nodes; the second one (p. 6) uses binary variables and is similar to > sudoku.mod in glpk examples; glpsol can solve it either on the > preprocessing stage or, in hard cases, after performing 3-5 branches. > > > > _______________________________________________ > Help-glpk mailing list > [email protected] > http://lists.gnu.org/mailman/listinfo/help-glpk > > -- View this message in context: http://www.nabble.com/mip-formulations-and-reformulations-tp26060305p26070245.html Sent from the Gnu - GLPK - Help mailing list archive at Nabble.com. _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
