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:
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:
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