Accelerating the Branch-and-Price Algorithm Using Machine Learning

Roman Václavík

doi:10.1016/j.ejor.2018.05.046

2018-12-01

PRE

DOI：10.1016/j.ejor.2018.05.046

原文链接

原文求助

摘要

En 中文

This study presents a widely applicable approach to accelerate the computation time of the Branch-andPrice (BaP) algorithm, which is a very powerful exact method used for solving complex combinatorial problems. Existing studies indicate that the most computationally demanding element of the BaP algorithm is the pricing problem. The case-studies presented in this paper show that more than 90% of the total Central Processing Unit (CPU) processing time is consumed by solving the pricing problem. The pricing problem is repetitive in nature and it solves the same problem from scratch differing only in the input dual prices. In this study, we demonstrate how to utilize the knowledge gained from previous executions of the pricing problem to reduce the solution space of pricing problems solved in future iterations. The solution is based on an online machine learning method that is not tailor-made for a specific problem (but needs a proper problem-dependent feature selection) and uses a very fast regression model that generates negligible overhead compared to the total CPU processing time of the BaP algorithm. The method predicts a tight upper bound for the current iteration of the pricing problem while preserving the exactness of the BaP algorithm. The efficiency of the proposed approach is demonstrated by two distinct case-studies: the nurse rostering problem and the scheduling of time-division multiplexing for multi-core platforms. The experiments carried out for both case-studies using benchmark instances from the literature show a 40% and 22% average CPU time reduction for the entire BaP algorithm. (C) 2018 Elsevier B.V. All rights reserved.

Keyword:

Scheduling

Branch-and-price

Pricing problem

Machine learning

Wpper bound