최소 단어 이상 선택하여야 합니다.
최대 10 단어까지만 선택 가능합니다.
다음과 같은 기능을 한번의 로그인으로 사용 할 수 있습니다.
NTIS 바로가기韓國컴퓨터情報學會論文誌 = Journal of the Korea Society of Computer and Information, v.17 no.6, 2012년, pp.13 - 27
Integer programming-based local search(IPbLS) is a kind of local search based on simple hill-climbing search and adopts integer programming for neighbor generation unlike general local search. According to an existing research [1], IPbLS is known as an effective method for the multidimensional knaps...
핵심어 | 질문 | 논문에서 추출한 답변 |
---|---|---|
정수계획법 기반 지역 탐색의 과정은? | 정수계획법 기반 지역 탐색은 지역 탐색을 기본으로 하는 탐색 알고리즘으로서 기존의 지역 탐색과 마찬가지로 현재해를 기반으로 임의의 변수들의 값을 변경하여 이웃해를 생성한 후 그 결과에 따라 이동하는 과정을 반복적으로 수행한다. 그러나 일반적인 지역 탐색이 임의의 변수들의 값을 무작위로 변경하여 이웃해를 생성하는 것과는 달리 정수계획법 기반 지역 탐색에서는 정수계획법을 사용하여 이웃해를 생성한다. | |
정수계획법 기반 지역 탐색에서는 무엇을 사용하여 이웃해를 생성하는가? | 정수계획법 기반 지역 탐색은 지역 탐색을 기본으로 하는 탐색 알고리즘으로서 기존의 지역 탐색과 마찬가지로 현재해를 기반으로 임의의 변수들의 값을 변경하여 이웃해를 생성한 후 그 결과에 따라 이동하는 과정을 반복적으로 수행한다. 그러나 일반적인 지역 탐색이 임의의 변수들의 값을 무작위로 변경하여 이웃해를 생성하는 것과는 달리 정수계획법 기반 지역 탐색에서는 정수계획법을 사용하여 이웃해를 생성한다. 기존 연구 [1]에서는 다차원 배낭 문제를 해결하기 위하여 정수계획법 기반 지역 탐색을 사용하였으며, 실험을 통해 지금까지 가장 좋은 결과를 보였던 탐색 기법보다 더 좋은 해를 도출할 수 있음을 확인하였다. | |
분지한계법은 어떤 장점이 있는가? | 정수계획법의 기본 탐색 알고리즘인 분지한계법(branch and bound)은 탐색 공간의 해들을 완전히 열거하는 방식을 사용하기 때문에 최적해의 도출이 보장된다. 더군다나 단순한 완전 열거 방식과는 달리 상한값과 하한값을 활용하여 최적해를 도출하는 데 불필요한 부분을 효과적으로 제거함으로써 중소 규모의 문제에 있어서 매우 빠르게 최적해를 도출할 수 있다는 장점이 있다[3]. 그러나 문제의 규모가 커질 경우 여전히 최적해를 도출하기까지 많은 시간을 요구하며, 특히 탐색 정보를 저장하기 위한 방대한 탐색 트리를 유지하는 데 과도한 메모리가 소요된다는 단점이 있다. |
J. Hwang, S. Park, and I. Y. Kong, "An Integer Programming-based Local Search for Large-scale Multidimensional Knapsack Problems," International Journal on Computer Science and Engineering, Vol. 3, No. 6, pp. 2257-2264, June 2011.
J. Hwang, and S. Kim, "An Integer Programming-based Local Search for Large-scale Maximal Covering Problems," International Journal on Computer Science and Engineering, Vol. 3, No. 2, pp. 837-843, Feb. 2011.
L. A. Wolsey, "Integer Programming," Wiley, pp. 91-111, 1998.
J. E. Beasley, "A Lagrangian Heuristic for Set Covering Problems," Naval Research Logistics, Vol. 37, No. 1, pp. 151-164, Feb. 1990.
N. Mladenovic, J. Brimberg, P. Hansen and J. A. Moreno Perez, "The p-median Problem: A Survey of Metaheuristic Approaches," European Journal of Operational Research, Vol. 179, No. 3, pp. 927-939, June 2007.
M. Diaby, "The Traveling Salesman Problem: A Linear Programming Formulation," WSEAS Transactions on Mathematics, Vol. 6, No. 6, pp. 745-754, May 2007.
J. Hwang, and K. R. Ryu, "A Hybrid of Neighborhood Search and Integer Programming for Crew Schedule Optimization," Journal of KISS : Software and Applications, Vol. 31, No. 6, pp. 829-839, June 2004.
S. Hasegawa, and Y. Kosugi, "Solving Nurse Scheduling Problem by Integer-programming-based Local Search," 2006 IEEE International Conference on Systems, Man and Cybernetics, pp. 1474-1480, Oct. 2006.
M. Hewitt, G. L. Nemhauser, and M. W. Savelsbergh, "Combining Exact and Heuristic Approaches for the Capacitated Fixed Charge Network Flow Problem," INFORMS Journal on Computing, Vol. 22, No. 2, pp. 314-325, Spring 2010.
J. Hwang, and S. Kim, "Integer Programming-based Local Search Technique for Linear Constraint Satisfaction Optimization Problem," Journal of The Korea Society of Computer and Information, Vol. 15, No. 9, pp. 47-55, Sep. 2010.
J. Puchinger, G. R. Raidl, and U. Pferschy, "The Multidimensional Knapsack problem: Structure and Algorithms," INFORMS Journal on Computing, Vol. 22, No. 2, pp. 250-265, Spring 2010.
J. E. Beasley, "OR-Library: Distributing Test Problems by Electronic Mail," The Journal of the Operational Research Society, Vol. 41, No. 11, pp. 1069-1072, 1990.
S. Boussier, M. Vasquez, Y. Vimont, S. Hanafi, and P. Michelon, "Solving the 0-1 Multidimensional Knapsack Problem with Resolution Search," VI ALIO/EURO Workshop on Applied Combinatorial Optimization, May 2009.
S. Boussier, M. Vasquez, Y. Vimont, S. Hanafi, and P. Michelon, "A Multi-level Search Strategy for the 0-1 Multidimensional Knapsack Problem," Discrete Applied Mathematics, Vol. 158, No. 2, pp. 97-109, Jan. 2010.
M. Vasquez, and Y. Vimont, "Improved Results on the 0-1 Multidimensional Knapsack Problem," European Journal of Operational Research, Vol. 165, No. 1, pp. 70-81, August 2005.
C. Wilbaut, and S. Hanafi, "New Convergent Heuristics for 0-1 Mixed Integer Programming," European Journal of Operational Research, Vol. 195, No. 1, pp. 62-74, May 2009.
F. Della Croce, and A. Grosso, "Improved Core Problem based Heuristics for the 0/1 Multidimensional Knapsack Problem," Computers & Operations Research, Vol. 39, No. 1, pp. 27-31, Jan. 2012.
F. Glover, and M. Laguna, "Tabu search," Kluwer Academic Publishers, pp. 1-57, 1997.
S. Russell, and P. Norvig, "Artificial Intelligence: A Modern Approach," Prentice Hall, pp. 115-116, 2005.
"IBM ILOG CPLEX V12.1: User's Manual for CPLEX," International Business Machines Corporation, 2009.
*원문 PDF 파일 및 링크정보가 존재하지 않을 경우 KISTI DDS 시스템에서 제공하는 원문복사서비스를 사용할 수 있습니다.
Free Access. 출판사/학술단체 등이 허락한 무료 공개 사이트를 통해 자유로운 이용이 가능한 논문
※ AI-Helper는 부적절한 답변을 할 수 있습니다.