Journal of the Korean Operations Research and Management Science Society (한국경영과학회지)

The Korean Operations Research and Management Science Society (한국경영과학회)
권호 표지

Lower and Upper Bounding Strategies for the Network Disconnection Problem

네트워크 단절문제에 대한 상한과 하한을 구하는 해법

  • 김현준 (울산대학교 경영학부) ;
  • 명영수 (단국대학교(천안) 경영학과) ;
  • 박성수 (한국과학기술원 산업공학과) ;
  • 오상민 (한국과학기술원 산업공학과)
  • Published : 2004.03.01
Download PDF
⟨ Previous Next ⟩

Abstract

The network disconnection problem ms to find a set of edges such that the total cost of removing the edges is no more than a given budget and the weight of nodes disconnected from a designated source by removing edges is maximized. Martel et at. have shown that the problem with unit capacity and unit demand Is NP-hard and Myung and kim present an integer programming formulation and develop an algorithm that Includes a preprocessing procedure and lower and upper bounding strateagies. in this paper, we present new findings on the properties of the optimal solution and an alternative integer programming formulation, based on which new lower and upper bounding strategies are developed. Computational results for evaluating the performance of the proposed algorithm are also presented.

Keywords

References

  1. Interfaces v.25 SONET toolkit : A decision support system for designing robust and cost-effective fiber-optic networks Cosares,S.;Deutec,N.D.;Saniee,I.;Wasem,O.J. https://doi.org/10.1287/inte.25.1.20
  2. Journal of the ACM v.32 Optimal attack and reinforcement of network Cunningham,W.H. https://doi.org/10.1145/3828.3829
  3. Comput. Operations Res. v.5 Future Paths for Integer Programming and Links to Artificial Intellingence Glover,F.
  4. ORSA J. Computing v.1 Tabu Search-Part I Glover,F. https://doi.org/10.1287/ijoc.1.3.190
  5. ORSA J. Computing v.2 Tabu Search-Part II Glover,F. https://doi.org/10.1287/ijoc.2.1.4
  6. Network Models Design of survivable networks Grotschel,M.;Monma,C.L.;Stoer,M.;M.O.Ball(et al.)(eds.)
  7. SIAM Journal on Computing v.20 Computing the strength of a graph Gusfield,D. https://doi.org/10.1137/0220040
  8. Meta Heuristic Kim,Y-K.;Yun,B-S.;Lee,S-B.
  9. Working paper Computing the disconnectivity of graph Martel,C.;Nuckolls,G.;Sniegowski,D.
  10. To appear in European Journal of Operational Research A Cutting Plane Algorithm for Computing k-edge Survivability of a Network Myung,Y.S.;Kim,H.J.
  11. Working paper An algorithm for the graph disconnection problem Myung,Y.S.;Kim,H.J.
  12. Proceeding of KIIE/KORMS Spring Conerence An improved algorithm for the graph disconnection problem Myung,Y.S.;Kim,H.J.
  13. Management Science v.45 Design of communication networks with survivability constraints Myung,Y.S.;Kim,H.J.;Tcha,D.W. https://doi.org/10.1287/mnsc.45.2.238
  14. Master Dissertation, Korea Advanced Institute of Science and Technology Mathematical Models and a Heuristic Algorithm for the Graph Disconnection Problem Oh,S-M.
  15. Fiber network survivability Wu,T.