제약 만족 최적화 문제의 해결을 위한 지역 탐색과 제약 프로그래밍의 결합

황준하(Jun-Ha Hwang) 한국컴퓨터정보학회 2010 韓國컴퓨터情報學會論文誌 Vol.15 No.5

제약 만족 최적화 문제는 복잡한 제약 조건을 포함하는 동시에 비용을 최소화하는 최적화 문제로 정의된다. 지역 탐색과 제약 프로그래밍은 각각 이와 같은 문제의 해결을 위한 도구로서 활용되어 왔다. 본 논문에서는 탐색 성능 향상을 위해 지역 탐색과 제약 프로그래밍을 결합하는 방안을 제시하고 있다. 기본적으로 대상 문제의 해결을 위해 지역 탐색을 사용한다. 그러나 지역 탐색만을 사용할 경우 제약 조건을 모두 만족하는 실행 가능한 이웃해를 생성하는 것이 매우 힘들어진다. 따라서 본 논문에서는 이웃해 생성을 위한 도구로 제약 프로그래밍을 도입하였다. 가중치가 부여된 N-Queens 문제를 대상으로 한 실험 결과, 본 논문에서 제시한 방법을 통해 탐색 성능을 획기적으로 향상시킬 수 있음을 확인할 수 있었다. Constraint satisfaction optimization problem is a kind of optimization problem involving cost minimization as well as complex constraints. Local search and constraint programming respectively have been used for solving such problems. In this paper, I propose a method to integrate local search and constraint programming to improve search performance. Basically, local search is used to solve the given problem. However, it is very difficult to find a feasible neighbor satisfying all the constraints when we use only local search. Therefore, I introduced constraint programming as a tool for neighbor generation. Through the experimental results using weighted N-Queens problems, I confirmed that the proposed method can significantly improve search performance.

V2G 시스템에서 배터리의 DOD를 고려한 OPEX 최적화 기법

황준하(Jun-Ha Hwang),김도윤(Do-Yun Kim),신민호(Min-Ho Shin),고안열(An-Yeol Ko),원일권(Il-Kuen Won),원충연(Chung-Yuen Won) 한국조명·전기설비학회 2014 한국조명·전기설비학회 학술대회논문집 Vol.2014 No.5

가스터빈 벽면 조건에 따른 막냉각 효율 비교

황준하(Jun Ha Hwang),박준수(Jun Su Park) 한국유체기계학회 2022 유체기계 연구개발 발표회 논문집 Vol.2022 No.11

도시 전이공간으로서의 이면가로에 관한 연구

황준하(Hwang, Jun-Ha),김승회(Kim, Seung-Hoy) 대한건축학회 2013 대한건축학회 학술발표대회 논문집 Vol.33 No.2

예측전류제어가 적용된 IPMSM 구동 시스템의 제어기 성능 분석

황준하(Jun-Ha Hwang),원일권(Il-Kuen Won),김도윤(Do-Yun Kim),김영렬(Young-Real Kim),원충연(Chung-Yuen Won) 전력전자학회 2015 전력전자학술대회 논문집 Vol.2015 No.07

예측제어를 이용한 EV구동용 IPMSM의 최적전류제어

황준하(Jun-Ha Hwang),원일권(Il-Kuen Won),고안열(An-Yeol Ko),김도윤(Do-Yun Kim),원충연(Chung-Yuen Won) 한국조명·전기설비학회 2015 한국조명·전기설비학회 학술대회논문집 Vol.2015 No.5

집합 커버링 문제를 위한 정수계획법 기반 지역 탐색

황준하(Jun-Ha Hwang) 한국컴퓨터정보학회 2014 韓國컴퓨터情報學會論文誌 Vol.19 No.10

집합 커버링 문제는 대표적인 조합 최적화 문제들 중 하나로서 n개의 열로부터 일부를 선택하여 m개의 행을 커버하되 비용을 최소화하는 문제로 정의된다. 본 논문에서는 집합 커버링 문제를 해결하기 위한 정수 계획법 기반 지역 탐색의 적용 방안을 제시하고 있다. 정수계획법 기반 지역 탐색은 이웃해를 탐색하여 현재해를 반복적으로 개선하는 지역 탐색 기법의 일종으로서 이웃해를 생성하기 위한 알고리즘으로 정수계획법을 사용한다. 본 논문에서 제시한 기법의 효과를 검증하기 위해 OR-Library의 테스트 데이터를 대상으로 실험을 수행하였다. 실험 결과, 모든 테스트 데이터에 있어서 정수계획법 기반 지역 탐색을 통해 지금까지 알려진 가장 좋은 해를 탐색할 수 있었다. 특히 4개의 테스트 데이터에 대해서는 지금까지 알려진 가장 좋은 해보다 더 좋은 해를 도출할 수 있음을 확인할 수 있었다. The set covering problem (SCP) is one of representative combinatorial optimization problems, which is defined as the problem of covering the m-rows by a subset of the n-columns at minimal cost. This paper proposes a method utilizing Integer Programming-based Local Search (IPbLS) to solve the set covering problem. IPbLS is a kind of local search technique in which the current solution is improved by searching neighborhood solutions. Integer programming is used to generate neighborhood solution in IPbLS. The effectiveness of the proposed algorithm has been tested on OR-Library test instances. The experimental results showed that IPbLS could search for the best known solutions in all the test instances. Especially, I confirmed that IPbLS could search for better solutions than the best known solutions in four test instances.

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

황준하(Jun-Ha Hwang) 한국컴퓨터정보학회 2009 韓國컴퓨터情報學會論文誌 Vol.14 No.2

정수계획법은 조합 최적화 문제의 최적해를 매우 효과적으로 탐색할 수 있는 기법인 반면에 대상 문제가 선형적으로 표현되어야만 적용이 가능하다는 단점이 있다. 본 논문에서는 정수계획 법의 뛰어난 탐색 능력과 이웃해 탐색 기법의 유연성을 결합함으로써 비선형 최적화 문제를 효과적으로 해결하는 방안을 제시하고 있다. 먼저 1단계에서는 주어진 문제로부터 선형적으로 표현 가능한 부문제만을 대상으로 정수계획 법을 적용한다. 2단계에서는 전체 문제를 대상으로 이웃해 탐색 기법을 적용하되 1단계의 결과를 초기해로 설정한 후 탐색을 수행한다. 비선형 최대 커버링 문제를 대상으로 한 실험 결과, 이와 같은 간단한 결합만으로도 이웃해 탐색 기법만을 적용했을 때보다 훨씬 좋은 해를 도출할 수 있음을 확인하였다. 이는 기본적으로 정수계획법의 탁월한 성능에 기인한 것으로 판단된다. 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.

선형 제약 만족 최적화 문제를 위한 정수계획법 기반 지역 탐색 기법

황준하(Jun-Ha Hwang),김성영(Sung-Young Kim) 한국컴퓨터정보학회 2010 韓國컴퓨터情報學會論文誌 Vol.15 No.9

선형 제약 만족 최적화 문제는 선형식으로 표현 가능한 목적함수 및 복잡한 제약조건을 포함하는 조합 최적화 문제를 의미한다. 정수계획법은 이와 같은 문제를 해결하는 데 매우 효과적인 기법으로 알려져 있지만 문제의 규모가 커질 경우 준최적해를 도출하기까지 매우 많은 시간과 메모리를 요구한다. 본 논문에서는 지역 탐색과 정수계획법을 결합하여 탐색 성능을 향상할 수 있는 방안을 제시한다. 기본적으로 대상 문제의 해결을 위해 지역 탐색의 가장 단순한 형태인 단순 언덕오르기 탐색을 사용하되 이웃해 생성 시 정수계획법을 적용한다. 또한 부가적으로 초기해 생성을 위해 제약 프로그래밍을 활용한다. N-Queens 최대화 문제를 대상으로 한 실험 결과, 본 논문에서 제시한 기법을 통해 다른 탐색 기법들보다 훨씬 더 좋은 해를 도출할 수 있음을 확인할 수 있었다. Linear constraint satisfaction optimization problem is a kind of combinatorial optimization problem involving linearly expressed objective function and complex constraints. Integer programming is known as a very effective technique for such problem but require very much time and memory until finding a suboptimal solution. In this paper, we propose a method to improve the search performance by integrating local search and integer programming. Basically, simple hill-climbing search, which is the simplest form of local search, is used to solve the given problem and integer programming is applied to generate a neighbor solution. In addition, constraint programming is used to generate an initial solution. Through the experimental results using N-Queens maximization problems, we confirmed that the proposed method can produce far better solutions than any other search methods.

다차원 배낭 문제를 위한 정수계획법 기반 지역 탐색 기법

황준하(Jun-Ha Hwang) 한국컴퓨터정보학회 2012 韓國컴퓨터情報學會論文誌 Vol.17 No.6

정수계획법 기반 지역 탐색은 단순 언덕오르기 탐색을 기반으로 하는 지역 탐색의 일종으로서 기존의 지역 탐색과는 달리 이웃해 생성 시 정수계획법을 활용한다. 기존 연구 [1]에 의하면 정수계획법 기반 지역 탐색은 경영과학 및 인공지능 분야에서 많은 관심을 받아 온 다차원 배낭 문제를 해결하는 데 매우 효과적인 것으로 알려져 있다. 그러나 해당 연구에서는 OR-Library에 있는 다차원 배낭 문제들 중 규모가 가장 큰 문제들만을 대상으로 하여 정수계획법 기반 지역 탐색의 우수성을 검증하였다는 단점이 있다. 본 논문에서는 그 외의 문제들을 대상으로 정수계획법 기반 지역 탐색을 적용함으로써 보다 객관적으로 정수계획법 기반 지역 탐색의 우수성을 검증한다. 아울러 본 논문에서는 기존의 정수계획법 기반 지역 탐색이 단순 언덕오르기 탐색과 정수계획법을 결합한 것과는 달리 언덕오르기 탐색, 타부 탐색, 시뮬레이티드 어닐링과 같은 다른 지역 탐색 기법과 정수계획법을 결합하는 방안을 제시한다. 실험 결과, 정수계획법 기반 지역 탐색은 중소 규모의 다차원 배낭 문제들에 있어서도 기존의 가장 좋은 휴리스틱 탐색 기법에 비해 유사하거나 더 우수한 성능을 발휘함을 확인하였다. 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 knapsack problem(MKP) which has received wide attention in operations research and artificial intelligence area. However, the existing research has a shortcoming that it verified the superiority of IPbLS targeting only largest-scale problems among MKP test problems in the OR-Library. In this paper, I verify the superiority of IPbLS more objectively by applying it to other problems. In addition, unlike the existing IPbLS that combines simple hill-climbing search and integer programming, I propose methods combining other local search algorithms like hill-climbing search, tabu search, simulated annealing with integer programming. Through the experimental results, I confirmed that IPbLS shows comparable or better performance than the best known heuristic search also for mid or small-scale MKP test problems.