비선형 최적화 문제의 해결을 위한 정수계획법과 이웃해 탐색 기법의 결합

다국어 초록 (Multilingual Abstract)

Integer programming is a very effective technique for searching optimal solution of combinatorial optimization problems. However, its applicability is limited to linear models. In this paper, I propose an effective method for solving a nonlinear optimization problem by integrating the powerful search performance of integer programming and the flexibility of neighborhood search algorithms. In the first phase, integer programming is executed with subproblem which can be represented as a linear form from the given problem. In the second phase, a neighborhood search algorithm is executed with the whole problem by taking the result of the first phase as the initial solution. Through the experimental results using a nonlinear maximal covering problem, I confirmed that such a simple integration method can produce far better solutions than a neighborhood search algorithm alone. It is estimated that the success is primarily due to the powerful performance of integer programming.

참고문헌 (Reference)

1 황준하, "정수계획법과 휴리스틱 탐색기법의 결합에 의한 승무일정계획의 최적화" 한국정보과학회 8 (8): 195-205, 2002

2 황준하, "이웃해 탐색 기법을 이용한 Maximal Covering 문제의 해결" 한국컴퓨터정보학회 11 (11): 129-138, 2006

3 강명주, "시뮬레이티디 어닐링 알고리즘을 이용한 클러스터 기반의 멀티캐스트 라우팅 문제 해법" 한국컴퓨터정보학회 9 (9): 189-194, 2004

4 황준하, "승무일정계획의 최적화를 위한 이웃해탐색 기법과 정수계획법의 결합" 한국정보과학회 31 (31): 829-839, 2004

5 박태진, "대규모 Maximal Covering 문제 해결을위한 유전 알고리즘" 한국정보과학회 31 (31): 570-576, 2004

6 R.L.Church, "The Maximal Covering Location Problem" 32 (32): 101-118, 1974

7 F. Glover, "Tabu Search" Kluwer Academic Publishers 1-122, 1997

8 R. J. Vanderbei, "Linear Programming: Foundations and Extentions" Kluwer Academic Publishers 13-24, 1997

9 L.A. Wolsey, "Integer programming" Wiley 91-107, 1998

10 "ILOG CPLEX 10.2 Documentation, ILOG"

11 E. Tsang, "Foundations of Constraint Satisfaction" Academic Press Limited 17-27, 1996

12 T. Achterberg, "Constraint Integer Programming: A New Approach to Integrate CP and MIP" LNCS 6-20, 2008

13 M. Mitchell, "An Introduction to Genetic Algorithms" MIT Press 1-31, 1997

14 B.T. Downs, "An Exact Algorithm for the Maximal Covering Problem" 43 (43): 435-461, 1996

15 U. Junker, "A framework for constraint programming based column generation" LNCS 261-274, 1999