최적화란 무엇인가?

수리적으로 최적화는 주어진 제약 조건을 만족하는 가능해 중에서 특정 목적함수를 최대화 하는 것이다. 현실적으로 최적화는 인간의 이성적 활동의 총칭임을 알 수 있다. 사기업과 공공 부문을 포함하여 인류의 다양한 목적에 봉사하는 현대 시스템의 크고 작은 문제들은 최적화 문제로 모델링 된다. 특히 산업공학에서 진행되는 다양한 연구분야들과 최적화는 근본적인 연관성을 가지고 있다. 예를 들어, 산업공학에서 널리 진행되는 연구분야인 “Economics and Finance”, “Technology and Entrepreneurship “, “Pricing and revenue management” 등에서 자주 접하게 되는 금융 논문들의 이론적 이해를 위해서는 최적화의 쌍대성이 필수적이다. 또한 기본 최적화 모형인 2차 모형 (quadratic program)은 통계 방법 구현의 근본 요소가 됨을 알 수 있다. 특히 “Decision Analysis and Risk Analysis”, “Machine learning and its interface with optimization” 등 데이터 과학의 엔진이 되는 분류기(classifier) 혹은 인공신경망(neural network)의 학습 등은 모두 최적화 문제로 귀결되며, 해당 문제를 얼마나 엄밀하게 접근할 수 있는가 하는 것이 도출된 분석의 신뢰성을 결정한다.

방법론으로서 최적화의 키워드 중에 하나는 모형(modelling)이다. 앞에서 언급한 최적화의 범용성의 관점에서 볼 때, 인간의 의사결정과 문제 해결을 위한 분석의 성패는 자신의 문제를 가장 적절한 의사 결정문제로 모델링 할 수 있는가에 달려 있다. 예를 들어 자신의 문제가 중립적인 환경에서 이익을 극대화 하는 시스템 최적화 문제인지, 다양한 이해 관계를 가진 복수의 게임 플레이어의 최선을 다해서 얻은 균형에 관한 문제인지를 이해하는 것은 문제를 접근하는 방법뿐 아니라, 시스템을 통해 수집된 데이터의 해석을 근본적으로 차이점을 갖게 한다. 또한 이러한 모형을 풀거나 분석하는 방법의 정당성을 명시적으로 확보하는 노력을 하는 것은 의사결정과 분석 결과의 질을 제고하는 필수적인 사항이다.

본 연구실은 학문 선전(propaganda)이라는 기현상 속에서 간과하기 쉬운 방법론의 정당성과 엄밀함의 중요성에 대한 인식을 제고 하고, 광범위한 학문의 기본이 되는 최적화 모형의 이론과 해법연구에 그 초점을 둔다. 이와 동시에 연구한 이론과 해법을 실제 현실 문제에 적용하고 검증하는 작업을 병행함으로써, 최적화 이론과 응용의 균형을 맞춘다. 즉, 실제 현장과의 지속적인 의사소통을 통해 자칫 탁상 공론이 될 수 있는 최적화 모형을 벗어나 현장에서 직접 사용 가능한 모형을 개발하는 것 또한 연구실의 주요 과제가 된다. 또한 사기업 및 공공 부문에서 제공되는 실시간 빅데이터에서 모형에 필요한 정보들을 추출하는 것은 제안한 최적화 모형의 품질을 높이는 부가적인 요소가 될 수 있다. 이를 위해, 최적화 모형에서 사용되는 파라미터들-수요/공급 분포, 선호 분포 등-을 계산하기 위한 새로운 방법론을 개발하거나, 기존 널리 사용되는 데이터 마이닝 방법론들-분류기, 기계학습 등-의 질을 근본적으로 향상시키는 것 또한 연구 목표 중의 하나가 될 것이다.

본 연구실은 다음과 같은 목적으로 연구생들을 양성한다. 석사 과정은 학생의 출신 전공과 ‘career goal’에 맞는 분야와 수준의 최적화 이론과 해법을 습득하게 하여, 추후 기업, 연구소나 해당 분야 중심 대학의 박사 과정에서 수학, 연구할 수 있는 자질을 함양하게 한다. 박사 과정은 연구실 고유(original) 주제를 발굴하고 이에 대한 심화된 연구를 수행하여 분야의 의미 있는 저널에 게재할 수 있는 연구 능력을 확보하게 양성한다. 또한 금요세미나와 방학 중의 스터디는 교과목에서 얻을 수 없는 세분화 된 주제에 대한 연구와 학습을 위한 연구실의 전통 중에 하나로 발표라는 중요한 communication skill을 배양하는 장이기도 한다.

2018년 생산된 본 연구실 학위 논문과 그 개요

[대규모 플레이어의 다양성을 고려한 게임 문제]
대규모 에이전트가 존재하는 게임에서 에이전트들의 다양성을 고려했을 때 에이전트들의 선택을 예측하는 모형에 대해서 연구한다. 먼저 에이전트들의 선택을 각 대안이 선택된 비율로써 나타내며, 이 때의 균형의 존재성에 대해 논의한다. 이렇게 균형을 정의할 경우, 실제 대규모 선택 데이터로부터 에이전트의 다양성을 나타내는 파라미터의 결합확률분포를 역최적화 기법을 통해 구할 수 있다. 무한 최적화 문제로 나타나는 역최적화 문제의 특징에 대해 연구하며, 이산화 했을 때 얻을 수 있는 ‘biquadratic program’을 풀기 위한 효과적인 해법 또한 제시한다. 실제 응용 예로써 하루 약 1000만명의 승객이 이용하는 지하철 경로 선택 모형에 적용한다. 이를 위해 먼저 교통카드 데이터로부터 승객들의 실제 경로 선택을 찾아내는 데이터 마이닝 방법론을 개발한다. 이렇게 얻은 대규모 실제 선택 데이터를 이용하여, 승객들의 이동시간, 환승, 혼잡, 위험선호에 대한 선호 파라미터들의 결합확률분포를 계산한다. 그리고 이를 이용하여 제안한 게임 모형의 예측력을 검증한다. 해당 연구는 실제 선택 데이터를 얻기 위한 big-data analysis, data mining, 선택 모형 개발을 위한 game theory, decision analysis, computational social science, 게임 모형 분석을 위한 functional analysis, 역최적화 문제를 풀기 위한 infinite-dimensional optimization, approximation algorithm 등 다양한 분야와 접목되어 있는 주제로 볼 수 있다. 또한 본 연구에서 개발된 모형 및 기법은 대규모 경쟁 상황에 있는 기업들 간의 facility location problem 혹은 학생들의 university choice problem 등의 문제에 또한 적용 가능할 것으로 생각된다.
[부보상 문제]
철도 노선계획 열생성 기법 부문제는 철도 네트워크 상의 한 노선에서 방문할 도시들을 결정하는 문제로 각 도시의 승객을 다른 도시에 운반하는 과정에서 발생하는 수익에서 승객의 총 이동시간에 비례해 발생하는 비용을 뺀 값을 최대화하는 것을 목표로 한다. 이는 조선시대 보따리 장수인 ‘부보상’이 가장 효율적인 무역을 위해 방문하는 도시를 정하고 재화들의 구매/판매 전략을 세우는 것과 같다. 해당 문제는 정수 계획 모형으로 표현할 수 있으며, 이 때의 해법으로 정수변수를 완화한 선형계획문제의 해집합의 크기를 줄이며 분지하는 방식의 해법인 분지절단법(branch-and-cut) 알고리듬을 활용한다. 그리고 알고리듬의 계산속도를 줄이기 위해 절단평면(cutting plane)을 찾고 해당하는 분리 알고리듬(separation algorithm)을 개발하는 연구를 진행하고 있다. 본 연구는 대규모 인구의 철도를 통한 이동이 발생할 때 열차를 효과적으로 배차하여 보다 많은 이동수요를 충족시키는 데 응용될 수 있으며 명절 등의 기간에 특히 큰 효과를 볼 수 있다.
[취약성을 최소화하는 시스템 구성품 배치 문제]
취약성은 생존성을 정량적으로 측정하기 위한 하나의 요소로써 시스템에 외부의 위협이 가해졌을 때 시스템이 기능을 상실할 확률을 의미한다. 이는 시스템의 구성품들이 배치되는 형태에 따라 변화한다. 하지만 현재 취약성 감소를 위한 구성품의 배치 문제는 주로 설계자의 경험이나 규칙기반 기법으로 이루어지며, 해당 방법은 시스템이 복잡하고 위협방향의 수가 클수록 최적 배치를 얻어내기 어려워진다. 본 연구에서는 먼저 결함수를 분석하여 구성품들을 일정하게 분류한다. 이 후 이를 이용하여 본 문제를 혼합정수계획법으로 모형화하고 문제의 특성을 이용한 해법의 개발을 통해 계산시간 및 해 품질을 개선한다. 결함수분석으로 도출된 최소단위 고장관리집합이, 인공적인 위협에 의해 고장이 발생할 사건을 정의할 수 있다면, 본 연구의 적용대상을 군사분야뿐만이 아닌 민간분야(자동차, 열차, 인공위성 등)로 확대시킬 수 있을 것이다.
[기계 학습을 이용한 실시간 열차 스케줄링]
열차 재스케줄링 문제는 열차 네트워크, 열차들의 기존 운행 계획, 열차 상태들을 입력으로 하여 경합이 발생했을 때 안전 제약을 만족시키면서 기존의 일정에서 크게 벗어나지 않는 스케줄을 복구하는 시스템 최적화 문제를 말한다. 열차 재스케줄링 문제에서 보편적으로 고려되던 일반 철도와 달리 도시 철도는 별도로 역간 이동 시간에 비해 정차 시간이 차지하는 비중이 크다는 특징을 가진다. 본 연구에서는 이러한 문제를 각자의 이해 관계를 가진 복수의 게임 플레이어가 자신의 효용을 고려하여 최선을 하는 마르코프 게임(Markov game)으로 모델링한다. 이러한 마르코프 게임 모형은 정차 시간이 stochastic한 문제의 특성을 잘 반영한다. 또한 본 연구는 유연하고 빠른 학습을 할 수 있는 새로운 기계 학습 알고리즘을 제시한다.

다음은 몇 top school의 연구 분야 분류이다.

Research Areas:
-Computational Social Science,
-Decision Analysis and Risk Analysis,
-Economics and Finance,
-Organization,
-Technology and Entrepreneurship,
-Probability and Stochastic systems,
-Operations Management,
-Strategy and Policy,
-Systems Modeling and Optimization
Recent Research Topics Include:
-Approximation algorithms,
-Discrete, continuous, convex, robust, stochastic optimization,
-Ground and air transportation,
-Health care,
-Health care analytics,
-Machine learning and its interface with optimization,
-Online algorithms,
-Personalized medicine,
-Pricing and revenue management,
-Social networks,
-Stochastic modeling,
-Supply chain management
이 분류를 보면 최적화가 다른 분야와 어떠한 근본적인 연관성을 가지고 있는지 알 수 있을 것이다.

서울대학교 산업공학과 경영과학/최적화 연구실, 서울시 관악구 신림동 56-2 39동 411호 우)151-742
Management Science/Optimization Lab., 39-411 Seoul National University, 56-2 Shilim-dong, Kwanak-gu, Seoul, Korea
Tel) 82-2-884-1164 E-mail) webadmin@polytope.snu.ac.kr