정보과학회논문지 (Journal of KIISE)
Current Result Document :
| 한글제목(Korean Title) |
용량 제약이 있는 설비 배치 문제에 대한 휴리스틱 및 선형계획법 완화의 계산적 분석 |
| 영문제목(English Title) |
Computational Analysis of Heuristics and Linear Programming Relaxations for Capacitated Facility Location |
| 저자(Author) |
이승민
안형찬
Seungmin Lee
Hyung-Chan An
|
| 원문수록처(Citation) |
VOL 48 NO. 04 PP. 0377 ~ 0390 (2021. 04) |
한글내용
(Korean Abstract) |
본 논문에서는 용량 제약이 있는 설비 배치 문제(CFL)에 대한 근사 알고리즘을 실용적으로 변형한 새로운 휴리스틱과 이것이 이용하는 선형계획법 완화를 실험적으로 평가·분석한다. CFL은 컴퓨터 과학 및 운용과학 분야에서 널리 연구되어온 문제이나, 선형계획법에 기반한 상수 인자 근사 알고리즘은 최근에야 발견되었다. 그러나, 기존의 느슨한 분석으로는 해당 선형계획법 완화의 정수격차(integrality gap)를 288로 상한할 수 있을 뿐이었다. 본 논문은 실제 데이터셋에서의 근사율과 정수격차를 측정함으로써, 휴리스틱 및 여기에 사용된 선형계획의 실질적인 성능을 평가함과 동시에 이론적인 추측을 위한 근거를 마련하고자 한다. 기존의 근사 알고리즘은 이론적인 것이어서 실제로 구현하기에는 지나치게 느린 수행 시간을 갖는다. 본 논문에서는 수치적 안정성을 해치지 않으면서도 수행시간을 개선할 수 있는 휴리스틱들을 제안하고 알고리즘의 파라미터를 실험적으로 최적화하여 고속의 구현을 얻는다.
|
영문내용
(English Abstract) |
In this paper, we experimentally evaluate new practical heuristics based on approximation algorithms for capacitated facility location (CFL) and the linear programming (LP) relaxations used by them. Although CFL has been extensively studied in the fields of computer science and operations research, an LP-based constant-factor approximation algorithm was only discovered recently. However, the existing analysis only gives a loose upper bound of 288 on the integrality gap of the LP relaxation. By measuring the approximation ratio and the integrality gap in a concrete dataset, this paper aims at measuring the practical performance of the heuristics and the relaxation, which would also provide evidence for further theoretical exploration. Due to the highly theoretical nature of the existing approximation algorithm, its naive implementation is practically inefficient. In this paper, we propose heuristics that improve the running time without affecting the numerical stability and experimentally optimize the algorithms’ parameters, thus obtaining an efficient implementation.
|
| 키워드(Keyword) |
용량 제약이 있는 설비 배치 문제
조합 최적화 알고리즘
선형계획법
휴리스틱
capacitated facility location
combinatorial optimization algorithms
linear programming
heuristics
|
| 파일첨부 |
PDF 다운로드
|
