최소 단어 이상 선택하여야 합니다.
최대 10 단어까지만 선택 가능합니다.
다음과 같은 기능을 한번의 로그인으로 사용 할 수 있습니다.
NTIS 바로가기한국경영과학회지 = Journal of the Korean Operations Research and Management Science Society, v.39 no.1, 2014년, pp.13 - 27
유준상 (고려대학교 산업경영공학부) , 이영호 (고려대학교 산업경영공학부) , 박기경 (고려대학교 산업경영공학부)
In this paper, we deal with a Steiner Ring Star (SRS) problem arising from the design of survivable telecommunication networks. We develop two mixed integer programming formulations for the SRS problem by implementing Miller-Tucker-Zemlin (MTZ) and Sarin-Sherali-Bhootra (SSB) subtour elimination con...
핵심어 | 질문 | 논문에서 추출한 답변 |
---|---|---|
SRS 문제를 생존성 망 설계 기술에 응용하면 어떤 이점이 생기는가? | SRS 문제는 생존성 망 설계(Survivable Network Design) 기술에 응용된다. 트리(Tree) 구조나 버스(Bus) 구조 망에서 에지 장애가 발생하는 경우 통신이 모두 두절된다. 반면에 링-스타 구조를 이용한 망 구조는 링을 구성하는 에지에 장애가 발생하여도 반대 방향으로 경로를 선회하여 통신을 유지한다. | |
SRS 문제는 무엇인가? | 이 논문은 슈타이너-링-스타(Steiner Ring Star, SRS) 문제를 다룬다. SRS 문제는 주어진 그래프에서 링-스타 토폴로지 구성 비용을 최소화하는 문제이다. 그래프 G= (V, E )에서 노드(Node) 집합, V= M∪N, M∩N= Φ이며 M은 Target 노드(Target Node) 집합, N은 Steiner 노드(Steiner Node) 집합을 나타낸다. | |
RSP는 SRS문제와 비교해 어떤 특징을 갖는 문제인가? | 이 논문에서 다루는 SRS 문제와 유사한 문제로 링-스타 문제(Ring Star Problem, RSP)가 있다. RSP는 SRS 문제와 달리 Steiner 노드와 Target 노드 구분이 없으며, 노드를 연결하는 단일 링 구조를 형성하고 링에 포함되지 않은 모든 노드를 링 구조를 형성한 노드에 연결하는 그래프 구성 비용을 최소화하는 문제이다. RSP를 다룬 기존 연구로는 Labbé et al. |
Labbe, M., G. Laporte, I.R. Martin, and J.J.S. Gonzalez, "The Ring Star Problem : Polyhedral Analysis and Exact Algorithm," Networks, Vol.43(2004), pp.177-189.
Lee, Y., S.Y. Chiu, and J. Ryan, "A Branch and Cut Algorithm for a Steiner Tree-Star Problem," INFORMS Journal on Computing, Vol.8(1996), pp.194-201.
Lee, Y., S.Y. Chiu, and J. Sanchez, "A Branch and Cut Algorithm for the Steiner Ring Star Problem," International Journal of Management Science, Vol.4(1998), pp.21-34.
Sarin, S.C., H.D. Sherali, and A. Bhootra, "New Tighter Polynomial Length Formulations for the Asymmetric Traveling Salesman Problem with and without Precedence Constraints," Operations Research Letters, Vol.33, No.1(2005), pp.62-70.
Sherali, H.D., W.P. Adams, and P.J. Driscroll, "Exploiting Special Structures in Constructing a Hierarchy of Relaxations for 0-1 Mixed Integer Problem," Operations Research, Vol.46(1998), pp.396-405.
Sherali, H.D. and P.J. Driscroll, "On Tightening the Relaxations of Miller-Tucker-Zemlin Formulations for Asymmetric Traveling Salesman Problems," Operations Research, Vol.50, No.4(2002), pp.656-669.
Sherali, H.D., S.C. Sarin, and P.-F. Tsai, "A Class of Lifted Path and Flow-Based Formulations for the Asymmetric Traveling Salesman Problem with and without Precedence Constraints," Discrete Optimization, Vol.6(2006), pp.20-32.
Simonetti, L., Y. Frota, and C.C. de Souza, "The Ring-Star Problem : A New Integer Programming Formulation and a Branchand-Cut Algorithm," Discrete Applied Mathematics, Vol.159, No.16(2011), pp.1901-1914.
*원문 PDF 파일 및 링크정보가 존재하지 않을 경우 KISTI DDS 시스템에서 제공하는 원문복사서비스를 사용할 수 있습니다.
Free Access. 출판사/학술단체 등이 허락한 무료 공개 사이트를 통해 자유로운 이용이 가능한 논문
※ AI-Helper는 부적절한 답변을 할 수 있습니다.