Steiner Ring Star 문제를 해결하기 위한 새로운 Mixed-Integer Programming Modeling
A New Mixed-Integer Programming Modeling for the Steiner Ring Star Problem
유준상(고려대학교); 이영호(고려대학교); 박기경(고려대학교)
39권 1호, 13~27쪽
초록
In this paper, we deal with a Steiner Ring Star (SRS) problem arising from the design of survivable telecommunicationnetworks. We develop two mixed integer programming formulations for the SRS problem by implementing Miller-Tucker-Zemlin (MTZ) and Sarin-Sherali-Bhootra (SSB) subtour elimination constraints, and then apply the reformulationlinearizationtechnique (RLT) to enhance the lower bound obtained by the LP relaxation. By exploiting the ring-starstructure of underlying network, we devise some valid inequalities that tighten the LP relaxation. Computational resultsdemonstrate the effectiveness of the proposed solution procedure.
Abstract
In this paper, we deal with a Steiner Ring Star (SRS) problem arising from the design of survivable telecommunicationnetworks. We develop two mixed integer programming formulations for the SRS problem by implementing Miller-Tucker-Zemlin (MTZ) and Sarin-Sherali-Bhootra (SSB) subtour elimination constraints, and then apply the reformulationlinearizationtechnique (RLT) to enhance the lower bound obtained by the LP relaxation. By exploiting the ring-starstructure of underlying network, we devise some valid inequalities that tighten the LP relaxation. Computational resultsdemonstrate the effectiveness of the proposed solution procedure.
- 발행기관:
- 한국경영과학회
- 분류:
- 경영학