Hi Andrew, I have been preparing some patches to improve the performance when solving integer problems. Instead of spamming the list, I have created a git repository on github where I maintain them: https://github.com/cmatraki/GLPK/tree/work
The main patches can be split in the following 6 groups (giving the short commit id and description for each patch): 1) faster pseudocost calculation and product score: 9dc0a6e reuse glp_prob for faster pcost initialisation a5816c7 add bfd copy operation cdffc12 use bfd_copy in pcost to avoid identical factorizations e96cd73 add --pcostmul product score option I have already sent these patches to the list some time ago: https://lists.gnu.org/archive/html/help-glpk/2017-01/msg00022.html https://lists.gnu.org/archive/html/help-glpk/2017-01/msg00090.html 2) objective step f233ccf find objective step and exploit it in search This patch finds cases where the objective value has discrete steps and uses this information to avoid some calculations 3) node preprocessor speed cdcd235 improve node preprocessor execution speed This patch avoids some copying and memory allocations inside the node preprocessor, which surprisingly was evident in some profiles. 4) Keep factorisation valid as much as possible 789e4c6 decouple root restoration from freezing 2d6bcfa avoid root restoration when restoring a child subproblem 947b7b9 avoid root restoration when restoring the sibling subproblem 45576b8 small ios_delete_node() cleanup Currently, when backtracking the solver restores the root node and then recreates the node to be restored. This set avoids this as much as possible and introduces the concept of sibling nodes (having the same parent) that can be similarly restored without invalidating the factorisation. 5) Use more information for pseudocost update 49dff33 update pcosts using reduced cost of nonbasic variables This is based on a presentation from SAS called "More Ways to Use Dual Information in MILP". 6) Improve active list search speed in the common case be47768 keep active list sorted in local bound order 8f5f9df fix comment to reflect new active list order 129bdd8 Make active list a true priority queue using the existing avl tree routines... ae86fdf Make active node count correct (including current node) When the active list becomes very large, traversing it becomes very time consuming (probably processor cache invalidation). This set makes the active list into a priority queue that is always in local bound order, with the exception of the current node that is not on the list to avoid unnecessary moves while its bound is updated. This is a small API change. These patches collectively can solve 36 problems from miplib 2010 within a time limit of two hours per problem. Do let me know if you have any comments, suggestions or questions. Best Regards, Chris Matrakidis
_______________________________________________ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
