초록 ▼

연구수행을 통해 도출한 연구성과는 총 세가지로 구분할 수 있다. 첫째, 기존 연구에 대한 정리이다. 먼저 NP-hard 문제에 대해 제시된 근사해법을 개발한 방법론을 기준으로 분류하였다. 그리고 P 문제에 대해 제시된 근사해법 (최대짝짓기문제, 최소비용 걸침나무 문제, -쌍 최단경로문제, 곡선 단순화 문제)에 대해 조사,분석하였고, 추가적으로 최적해 탐색을 위한 계산 하한 결과를 정리하였다.
둘째, 다양한 문제들에 대한 근사해법 개발이다. 전체 연구 기간 중 연구 대상이 된 문제들은 1) 게임이론을 적용한 워게임 문제, 2)

연구수행을 통해 도출한 연구성과는 총 세가지로 구분할 수 있다. 첫째, 기존 연구에 대한 정리이다. 먼저 NP-hard 문제에 대해 제시된 근사해법을 개발한 방법론을 기준으로 분류하였다. 그리고 P 문제에 대해 제시된 근사해법 (최대짝짓기문제, 최소비용 걸침나무 문제, -쌍 최단경로문제, 곡선 단순화 문제)에 대해 조사,분석하였고, 추가적으로 최적해 탐색을 위한 계산 하한 결과를 정리하였다.
둘째, 다양한 문제들에 대한 근사해법 개발이다. 전체 연구 기간 중 연구 대상이 된 문제들은 1) 게임이론을 적용한 워게임 문제, 2) 구간 스케줄링(Interval scheduling problem) 문제, 3) 최대절단면(Maximum cut problem) 문제, 4) 최대안정집합(Stable set problem) 문제, 5) 관망 펌핑 일정 계획(Pumping scheduling problem of water supply network) 문제이다.
1) 교전상황을 수리 모형화하고, 게임이론의 관점에서 균형전략을 구하는 문제를 연구하였다. 특히, 피아의 기동을 예측할 수 있는 기습의 교전 상황에 대하여, 다중 기간에서의 화력 운영에 대한 의사결정 문제를 고려하였다. 란체스터 제곱 법칙으로 묘사되는 교전 상황에 대해 피아 모두 여러 종류의 무기체계를 지닌 교전 상황을 연속시간 워게임 모델로 수리 모형화하고, 몇 가지 가정을 바탕으로 이 모형을 이산시간 모형으로 근사하여 최소최대선형 다중계층 문제로 표현하였다. 하지만 이 문제의 특수한 형태인 최소최대선형 이중계층 문제의 NP-hardness가 이미 증명되었고, 다항시간 내 최적해를 보장하는 해법은 현재까지 존재하지 않는다. 본연구에서는 워게임 균형의 존재성을 증명하였고, ϵ-내쉬 균형을 탐색하는 휴리스틱 알고리즘을 제시하였다.
2) 구간 스케줄링 문제의 역문제를 연구하였다. 구간스케줄링 문제는 시작시간과 종료시간이 고정된 작업을 모두 처리하기 위해 필요한 최소의 기계 수(m')와 각 기계가 어떤 작업을 처리하는지 구하는 문제이다. 그런데 보유하고 있는 기계 수(m)가 m'보다 적은 경우 새로운 문제에 봉착하게 된다. 즉, 주어진 작업 중에서 어떤 작업을 m대의 기계에서 처리해야 이익을 최대화하는지 묻는 문제이다. 또한, 주어진 시작시간과 종료시간을 변경할 수 있으면 이익을 더 남길 수 있다. 이처럼 시작시간이나 종료시간을 변경할 수 있는 모형을 구간스케줄링문제의 역문제라고 부른다. 하지만 이 경우 작업의 처리시간이 원래 주어진 처리시간에서 연속적으로 달라질 수 있기 때문에 문제의 계산 복잡도가 아직 밝혀지지 않고 있다. 본 연구에서는 이 역문제에 대한 2-근사해법을 제시하고, 다양한 special case의 최적해를 탐색하는 알고리즘을 제시하였다. (이 논문은 SCI 저널에 submit한 상태이다.)
3), 4) NP-hard 문제 중에서 전통적인 조합최적화 문제인 최대안정집합과 최대절단면 문제를 연구하였다. Handelman Hierarchy를 통한 상한 분석을 진행하였는데, 이를 통해 각 문제에 대한 Handelman Hierarchy 의 rank를 증명하였다. (이 두 논문은 SCI 저널에 publish된 상태이다.) 이 결과는 추후 근사해법 개발에 큰 도움이 되리라 기대한다.
5) 관망 펌핑 일정 계획 문제를 연구하였다. 이 문제는, 취수원에서 수용가를 연결하는 상수도 네트워크에서, 요구하는 유량을 발생시키는 일일 펌프 일정 중 소모하는 전기에너지 비용을 최소화하는 일정을 구하는 문제이다. 이 문제는 NP-hard 임을 증명할 수 있는데, 그렇기 때문에 현장에 실시간으로 적용하기 위해서는 문제의 최적해를 탐색하기보다, 최적에 가까운 해를 빠른 시간 내에 출력하는 것이 현명한 접근일 것이다. 본 연구에서는 이 문제에 대한 정확한 수학적 모형을 제시하고, 이에 대해 실시간 해법을 제시하였다. 또한 이 해법의 해가 기존의 비용을 6%정도 감축시킴을 실험으로 확인하였다.
셋째, 선형계획 및 원추계획 문제에 대한 계산시간 단축 연구이다. 본 연구에서는 이를 위해 GPU 병렬 처리기법에 대한 기존 분석을 진행하였다.