Learning-based Selection process for Branch and Bound Algorithms

Karima Rihane, Adel Dabah, Abdelhakim Aitzai

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Branch and Bound (B&B) algorithms represent a well-known tool for optimally solving combinatorial optimization problems in general and scheduling problems in particular. They have been widely used as a reference for classical scheduling problems such-as job shop scheduling. However, they rely on a deep knowledge of the problem to achieve fast convergence and low execution time. To deal efficiently with real-world problems where we do not have prior knowledge, we investigate the use of learning-based methods to accelerate the B&B tree exploration in this paper. We use the Blocking Job Shop Scheduling Problem (BJSSP) as a study case. Our approach aims to learn an efficient branching and selection process by training a model using small and medium BJSSP benchmarks. For each benchmark, two phases are used. First, we train the model using a small set of solutions provided by a metaheuristic to detect similar features among good solutions. Therefore, generating branching and selection roles. After that, we apply these roles to solve these instances optimally. The obtained results show the effectiveness of our proposed learning-based selection by achieving performance results near the best B&B implementation for BJSSP known to us.
Original languageEnglish (US)
Title of host publication2022 IEEE Congress on Evolutionary Computation (CEC)
PublisherIEEE
ISBN (Print)9781665467087
DOIs
StatePublished - Jul 18 2022

Fingerprint

Dive into the research topics of 'Learning-based Selection process for Branch and Bound Algorithms'. Together they form a unique fingerprint.

Cite this