초록 ▼

연구개요
본 연구는 분포-강건 이산 최적화 문제에 대한 알고리즘을 개발하여 데이터 불확실성 하의 문제를 효율적으로 해결하고자 한다. 현실의 최적화 문제에서는 측정 오차나 시점/상황의 변화 가능성으로 인해 목적 함수나 제약 조건의 계수가 불확실한 상황에 놓일 수 있다. 이를 극복하기 위한 최근의 방법론인 분포-강건 최적화는 불확실한 계수의 확률 분포에 대한 평균, 표준편차와 같은 부분적인 정보를 바탕으로 해당 정보에 부합하는 모든 확률 분포에 대해 목표 함숫값이 최적에서 멀어지거나 제약 조건을 위반하게 되는 위험을 최소화하는 해

연구개요
본 연구는 분포-강건 이산 최적화 문제에 대한 알고리즘을 개발하여 데이터 불확실성 하의 문제를 효율적으로 해결하고자 한다. 현실의 최적화 문제에서는 측정 오차나 시점/상황의 변화 가능성으로 인해 목적 함수나 제약 조건의 계수가 불확실한 상황에 놓일 수 있다. 이를 극복하기 위한 최근의 방법론인 분포-강건 최적화는 불확실한 계수의 확률 분포에 대한 평균, 표준편차와 같은 부분적인 정보를 바탕으로 해당 정보에 부합하는 모든 확률 분포에 대해 목표 함숫값이 최적에서 멀어지거나 제약 조건을 위반하게 되는 위험을 최소화하는 해법을 찾는다. 이는 불확실한 계수의 확률 분포를 단정하지 않으면서 최적해의 강건성을 확률적으로 보증한다. 최근 결정변수가 실수인 연속 최적화 문제에 대해 분포-강건 방법론을 적용하는 연구가 많이 진행되었지만, 결정 변수가 정수인 이산 최적화 문제에 대해서 분포-강건 방법론을 적용한 연구는 상대적으로 부족하며 결과 또한 좋지 않다. 따라서 본 연구에서는 데이터 불확실성 하의 이산 최적화 문제에 분포-강건 최적화의 방법론을 적용하고 이를 효율적으로 해결할 수 있는 알고리즘을 개발하고자 한다.

연구 목표대비 연구결과
본 연구에서는 목적 함수나 제약 조건의 계수에 대한 정확한 확률 분포를 알 수 없으며, 평균, 분산과 같은 몇몇 정보만이 확률 분포의 모호성 집합 형태로 주어진 분포-강건 이산 최적화 문제를 해결할 수 있는 알고리즘을 개발하고자 하였다. 또한, 알고리즘의 효율성을 시간 복잡도 분석을 통하여 이론적으로 증명하는 한편, 실험을 통해 이를 분포-강건 이산 최적화 문제 해결에 적용 가능함을 보였다. 마지막으로 연구에서 제시하는 해결 방법이 최단 경로 문제 등 현실의 최적화 문제에 적용 가능한지를 확인하였다. 연구는 3년에 걸쳐 각 아이템의 무게가 불확실한 분포-강건 이진 배낭 문제, 목적 함수의 계수가 불확실한 분포-강건 조합최적화 문제, 제약 조건의 계수가 불확실한 분포-강건 정수계획법 문제에 대하여 각각 진행되었다. 문제에 대한 접근은 확률 변수로 이루어진 비선형 목적 함수나 제약 조건을 이차 원뿔체 공식으로 근사하여 접근하고 최종적으로 문제의 최적해를 구할 수 있는 알고리즘을 개발하는 식으로 이루어졌다. 연구 결과, 배낭 문제, 최단 경로 문제, 차량 경로 문제, 용량 제약 하의 입지 선정 문제 등 데이터 불확실성이 있는 다양한 이산 최적화 문제에 대하여 우리의 방법론을 적용할 수 있었다.

연구개발성과의 활용 계획 및 기대효과 (연구개발결과의 중요성)
본 연구에서 제안하는 알고리즘은 넓은 범위의 분포-강건 이산 최적화 문제를 효율적으로 해결하는데 사용될 수 있다. 또한, 본 연구는 데이터 불확실성 하의 최적화 문제의 해법에 대한 새로운 연구 방향을 제시하며 파생되는 다양한 후속 연구가 이어질 것으로 기대된다. 특히, 본 연구의 결과는 연구 과정에서 다룬 문제들 외에도 통신, 물류, 운송, 제조 등 이산 최적화 방법론을 사용하는 다양한 분야로 확장 가능하다.

(출처 : 요약문 2p)

목차 Contents

• 표지 ... 1
• 연구결과 요약문 ... 2
• 목차 ... 3
• 1. 연구개발과제의 개요 ... 4
• 2. 연구개발과제의 수행 과정 및 수행 내용 ... 6
• 1) 1차년도 ... 6
• 2) 2차년도 ... 8
• 3) 3차년도 ... 10
• 3. 연구개발과제의 수행 결과 및 목표 달성 수준 ... 13
• 1) 정성적 연구개발성과(연구개발결과) ... 13
• 2) 세부 정량적 연구개발성과 ... 13
• 3) 목표 달성 수준 ... 13
• 4) 목표 미달 시 원인 분석 ... 13
• 4. 연구개발성과의 관련 분야에 대한 기여 정도(연구개발결과의 중요성) ... 14
• 5. 연구개발성과의 관리 및 활용 계획 ... 14
• 6. 참고문헌 ... 14
• [붙임1] 세부 정량적 연구개발성과 ... 16
• [붙임2] 연구책임자 대표적 연구실적 및 증빙(요약문 및 사본) ... 17
• 끝페이지 ... 19