본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

A Branch and Bound Algorithm for Solving a Capacitated Subtree of Tree Problem in Local Access Telecommunication Networks

Cho, Geon    (School of Business Administration, Chonnam National University   ); Kim, Seong-Lyun    (Electronics and Telecommunication Research Institute  );
  • 초록

    Given a rooted tree T with profits and node demands, the capacitated subtree of a tree problem (GSTP) consists of finding a rooted subtree of maximum profit, subject to having total demand no larger than the given capacity H. We first define the so-called critical item for CSTP and find an upper bound on the optimal value of CSTP in O(n $^{2}$ ) time, where n is the number of nodes in T. We then present our branch and bound algorithm for solving CSTP and illustrate the algiruthm by using an example. Finally, we implement our branch-and-bound algorithm and compare the computational results with those for both CPLEX and a dynamic programming algorithm. The comparison shows that our branch-and-bound algorithm performs much better than both CPLEX and the dynamic programming algorithm, where n and H are the range of [50, 500] and [5000, 10000], respectively.


  • 참고문헌 (15)

    1. Optimizing Constrained Subtrees of Trees , Aghezzaf, E.H.;T.L. Magnanti;L.A. Wolsey , Technical Report, Center for Operations Research & Econometrics / v.,pp.,
    2. A Decomposition Algorithm for Expanding Local Access Telecommunications Networks , Balakrishnan, A.;T.L. Magnanti;R.T. Wong , Operations Research / v.43,pp.43-57,
    3. An Algorithmic Approach to Network Location Problems Ⅱ : The p-medians , Kariv, O.;S.L. Hakimi , SIAM J. on Applied Mathematics / v.37,pp.539-555,
    4. Algorithms for Knapsack Problems , Martello, S.;P. Toth , Annals of Discrete Mathematics / v.31,pp.213-258,
    5. On Knapsacks, Partitions, and A New Dynamic Programming Technique for Trees , Johnson, D.S.;K.A. Niemi , Mathematics of Operations Research / v.8,pp.1-14,
    6. A Depth-First Dynamic Programming Algorithm for The Tree Knapsack Problem , Cho, G.;D.X. Shaw , Technical Report, School of Industrial Engineering / v.,pp.,
    7. Mirchandani, P.B.;R.L. Francis , Discrete Location Theory / v.,pp.,
    8. Chapter 9. Optimal Trees , Magnanti, T.L.;L.A. Wolsey , Handbooks in OR and MS / v.7,pp.,
    9. Limited Column Generation Technique for Several Telecommunications Network Design Problems , D.X. Shaw , Technical Report, School of Industrial Engineering / v.,pp.,
    10. Fast Approximation Algorithms for Knapsack Problems , Lawler, E.L. , Mathematics of Operations Research / v.4,pp.339-356,
    11. Computing Partitions with Applications to The Knapsack Problem , Horowitz, E.;S. Sahni , J. of the ACM / v.21,pp.277-292,
    12. An Algorithm for Large Zero-One Knapsack Problem , Balas, E.;E. Zemel , Operations Research / v.28,pp.1130-1154,
    13. Martello, S.;P. Toth , Knapsack Problems / v.,pp.,
    14. Approximation Algorithms for Certain Scheduling Problems , Ibarra, O.H.;C.E. Kim , Mathematics of Operations Research / v.3,pp.197-204,
    15. Nemhauser, G.L.;L.A. Wolsey , Integer and Combinatorial Optimization / v.,pp.,

 저자의 다른 논문

  • 조건 (9)

    1. 1996 "A Pseudopolynomial-time Algorithm for Solving a Capacitated Subtree of a Tree Problem in a Telecommunication System" 대한산업공학회지 = Journal of Korean institute of industrial engineers 22 (3): 485~498    
    2. 1998 "A Decomposition Algorithm for a Local Access Telecommunication Network Design Problem" 한국경영과학회지 = Journal of the Korean Operations Research and Management Science Society 23 (2): 29~46    
    3. 1998 "IVOD와 NVOD 혼합 서비스를 위한 다계층 VOD망의 자원 최적화" 산업공학 = IE Interfaces 11 (2): 39~48    
    4. 2001 "나무구조를 갖는 네트워크상에서의 제한용량이 있는 입지설정문제에 관한 연구" 대한산업공학회지 = Journal of Korean institute of industrial engineers 27 (3): 250~259    
    5. 2002 "집합 피복 공식화를 이용한 명제논리의 만족도 문제에 대한 계산실험 연구" 한국경영과학회지 = Journal of the Korean Operations Research and Management Science Society 27 (4): 87~109    
    6. 2004 "트리 네트워크 상에서의 p-미디안 문제에 대한 효율적인 알고리즘 개발에 관한 연구" 한국경영과학회지 = Journal of the Korean Operations Research and Management Science Society 29 (1): 57~70    
    7. 2006 "공급사슬 파트너십 하에서 공급자-구매자 이익공유와 가격결정 정책에 대한 계량 모형" 한국경영과학회지 = Journal of the Korean Operations Research and Management Science Society 31 (1): 73~82    
    8. 2006 "공급사슬관리에서 생산입지선정 문제와 안전재고 최적화 문제의 통합모형 개발에 관한 연구" 한국경영과학회지 = Journal of the Korean Operations Research and Management Science Society 31 (1): 91~103    

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
  • 한국경영과학회 : 저널
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기