Towards a parallel implementation of CPLEX using a pseudo-cost repository

Pseudo-cost based branching is a popular branching strategy used by Mixed Integer Programming (MIP) solvers. This strategy relies on pseudo-cost updates from various parts of the search tree for making accurate branching decisions. Since such updates are not instantly available during a distributed computation, parallel MIP solver implementations that use pseudo-cost branching may not perform well when the underlying cluster is scaled horizontally. To address this issue, we propose integrating a repository of pre-calculated pseudo-costs into a parallel implementation of CPLEX. Although all the facilities needed for such an implementation are currently not available, experiments with hard-to-solve instances indicate that the proposed implementation can help limit the number of nodes explored during the distributed computation.