Improved branch-and-price algorithm fork the efficient 2-terminal reliability problem

Roman A. Rudakov

N.N. Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Ekaterinburg

Abstract: The Efficient 2-Terminal Reliability Problem is a nonlinear optimization problem aimed at designing a minimal-cost network within the reliability guaranties. Recent research has provided Branch-and-Price (BnP) solution based on probability relaxation, the Dantzig–Wolfe decomposition, followed by the column generation technique, and Branch-and-Bound scheme. Unfortunately, the performance of this algorithm deteriorates in cases of high-density graphs and stringent unreliability thresholds. By extending our recent approach, we introduce an improved BnP algorithm supplemented with novel valid inequalities, more efficient nonlinear integer pricing problem solver, primal heuristics, and branching strategies. Evaluation results on benchmarking instances demonstrate significant performance advantage of the proposed method.

Keywords: 2-Terminal Reliable Problem, Dantzig–Wolfe decomposition, Branch-and-price

Language: English

DOI: 10.15826/umj.2025.2.014

Bibliographic databases:

•