IMPROVED BRANCH-AND-PRICE ALGORITHM FOR THE EFFICIENT 2-TERMINAL RELIABILITY PROBLEM

Roman A. Rudakov     (Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, 16 S. Kovalevskaya Str., Ekaterinburg, 620108, Russian Federation)

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

Full Text:

PDF

References


  1. Achterberg T., Koch Th., Martin A. Branching rules revisited. Oper. Res. Lett., 2005. Vol. 33, No. 1. P. 42–54. DOI: 10.1016/j.orl.2004.04.002
  2. Arslan O., Laporte G. Network design with vulnerability constraints and probabilistic edge reliability. Networks, 2024. Vol. 84, No. 2. P. 181–199. DOI: 10.1002/net.22222
  3. Bouchery Y., Corbett C.J., Fransoo J.C., Tan T. (eds.) Sustainable Supply Chains: A Research-Based Textbook on Operations and Strategy. Springer Ser. Supply Chain Manag. Cham: Springer, 2024. 553 p. DOI: 10.1007/978-3-031-45565-0
  4. Casazza M., Ceselli A. Optimization algorithms for resilient path selection in networks. Comput. Oper. Res., 2021. Vol. 128. Art. no. 105191. DOI: 10.1016/j.cor.2020.105191
  5. Desrosiers J., Lübbecke M., Desaulniers G., Gauthier J.B. Branch-and-price. Montréal, Canada: Les Cahiers du GERAD, 2024. 657 p.
  6. Feng W., Guo H. An FPRAS for two terminal reliability in directed acyclic graphs. In: Leibniz Int. Proc. Informatics (LIPIcs), vol. 297: 51st Int. Colloquium on Automata, Languages, and Programming (ICALP 2024). Germany: Dagstuhl, 2024. P. 62:1–62:19. DOI: 10.4230/LIPIcs.ICALP.2024.62
  7. Gouveia L., Leitner M. Design of survivable networks with vulnerability constraints. European J. Oper. Res., 2017. Vol. 258, No. 1. P. 89–103. DOI: 10.1016/j.ejor.2016.09.003
  8. Gouveia L., Joyce-Moniz M., Leitne M. Branch-and-cut methods for the Network Design Problem with Vulnerability Constraints. Comput. Oper. Res., 2018. Vol. 91. P. 190–208. DOI: 10.1016/j.cor.2017.10.005
  9. Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, vers. 11.0. 2024. URL: https://www.gurobi.com
  10. Khachai D., Sadykov R., Battaïa O., Khachay M. Precedence constrained generalized traveling salesman problem: Polyhedral study, formulations, and branch-and-cut algorithm. European J. Oper. Res., 2023. Vol. 309, No. 2. P. 488–505. DOI: 10.1016/j.ejor.2023.01.039
  11. Khachai D., Battaïa O., Petunin A., Khachay M. Discrete cutting path problems: a general solution framework and industrial applications. Int. J. Production Res., 2025. Vol. 63, No. 3. P. 949–969. DOI: 10.1080/00207543.2024.2365360
  12. Moore E.F., Shannon C.E. Reliable circuits using less reliable relays. J. Franklin Inst., 1956. Vol. 262, No. 3. P. 191–208. DOI: 10.1016/0016-0032(56)90559-2
  13. Ogorodnikov Y., Rudakov R., Khachai D., Khachay M. A problem-specific branch-and-bound algorithm for the protected shortest simple path problem with must-pass nodes. IFAC-PapersOnLine, 2022. Vol. 55, No. 10. P. 572–577. DOI: 10.1016/j.ifacol.2022.09.455
  14. Ogorodnikov Yu.Yu., Rudakov R.A., Khachai D.M., Khachai. M.Yu. Fault-tolerant families of production plans: Mathematical model, computational complexity, and branch-and-bound algorithms. Comput. Math. Math. Phys., 2024. Vol. 64, No. 6. P. 1193–1210. DOI: 10.1134/S0965542524700441
  15. Rudakov R., Khachay D., Ogorodnikov Y., Khachay M. Reliable production process design problem: Compact MILP model and ALNS-based primal heuristic. Lect. Notes in Comput. Sci., vol. 14395: Optimization and Applications (OPTIMA 2023), N. Olenev et al. (eds). Cham: Springer, 2023. P. 174–188. DOI: 10.1007/978-3-031-47859-8_13
  16. Rudakov R.A., Khachay D.M., Ogorodnikov Y.Y., Khachay M.Y. Branch-and-price algorithm for the efficient 2-terminal reliability problem. Sib. Electron. Math. Rep., 2025. Vol. 22, No. 2. P. 68–84.
  17.  Satyanarayana A., Kevin Wood R. A linear-time algorithm for computing \(k\)-terminal reliability in series-parallel networks. SIAM J. Comput., 1985. Vol. 14, No. 4. P. 818–832. DOI: 10.1137/0214057
  18. Song Y., Luedtke J.R. Branch-and-cut approaches for chance-constrained formulations of reliable network design problems. Math. Program. Comput., 2013. Vol. 5, No. 4. P. 397–432. DOI: 10.1007/s12532-013-0058-3
  19. Uchoa E., Pessoa A., Moreno L. Optimizing with Column Generation: Advanced branch-cut-and-price algorithms (Part I). Technical Report L-2024-3. Niterói: Universidade Federal Fluminense, Engenharia de Produção. 2024.
  20. Valiant L.G. The complexity of enumeration and reliability problems. SIAM J. Comput., 1979. Vol. 8, No. 3. P. 410–421. DOI: 10.1137/0208032
  21. Zenklusen R., Laumanns M. High-confidence estimation of small \(s-t\) reliabilities in directed acyclic networks. Networks, 2011. Vol. 57, No. 4. P. 376–388. DOI: 10.1002/net.20412




DOI: http://dx.doi.org/10.15826/umj.2025.2.014

Article Metrics

Metrics Loading ...

Refbacks

  • There are currently no refbacks.