Accelerating the Branch-and-Price Algorithm Using Machine Learning

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F18%3A00322959" target="_blank" >RIV/68407700:21230/18:00322959 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/68407700:21730/18:00322959

Výsledek na webu

<a href="http://dx.doi.org/10.1016/j.ejor.2018.05.046" target="_blank" >http://dx.doi.org/10.1016/j.ejor.2018.05.046</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.ejor.2018.05.046" target="_blank" >10.1016/j.ejor.2018.05.046</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Accelerating the Branch-and-Price Algorithm Using Machine Learning

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Accelerating the Branch-and-Price Algorithm Using Machine Learning

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2018

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

European Journal of Operational Research

ISSN

0377-2217

e-ISSN

1872-6860

Svazek periodika

271

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

15

Strana od-do

1055-1069

Kód UT WoS článku

000442060500020

EID výsledku v databázi Scopus

2-s2.0-85049119432