A machine learning approach to rank pricing problems in branch-and-price

Pavlína Koutecká, Přemysl Šůcha, Jan Hůla and Broos Maenhout

European Journal of Operational Research, 2025, vol. 320, issue 2, 328-342

Abstract: This paper presents a novel approach exploiting machine learning to enhance the efficiency of the branch-and-price algorithm. The focus is, specifically, on problems characterized by multiple pricing problems. Pricing problems often constitute a substantial portion of CPU time due to their repetitive nature. The primary contribution of this work includes the introduction of a machine learning-based ranker that strategically guides the search for new columns in the column generation process. The master problem solution is analyzed by the ranker, which then suggests an order for solving the pricing problems to prioritize those with the potential to improve the master problem the most. This prioritization mechanism is essential in speeding up the column generation since, by identifying new columns early in the process, we can terminate the search procedure sooner. Furthermore, our technique exhibits applicability across all nodes of the branching tree, making it a valuable tool for solving a wide range of optimization problems. We demonstrate the usefulness of this approach in the challenging domain of operating room scheduling, an area that has seen limited exploration in the context of machine learning. Extensive experimental evaluations underline the effectiveness of the developed algorithm, consistently outperforming traditional search strategies in terms of time, number of solved pricing problems, searched nodes in the branching tree, and performed column generation iterations.

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

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722172400585X
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:320:y:2025:i:2:p:328-342

DOI: 10.1016/j.ejor.2024.07.029

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 ().