Accelerating the Branch-and-Price Algorithm Using Machine Learning

Roman Václavík, Antonín Novák, Přemysl Šůcha and Zdeněk Hanzálek

European Journal of Operational Research, 2018, vol. 271, issue 3, 1055-1069

Abstract: This study presents a widely applicable approach to accelerate the computation time of the Branch-and-Price (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.

Keywords: Scheduling; Branch-and-price; Pricing problem; Machine learning; Wpper bound (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221718304570
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:271:y:2018:i:3:p:1055-1069

DOI: 10.1016/j.ejor.2018.05.046

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().