경영과학, 혹은 최적화란, 제약조건을 만족하는 대안 중에서 의사결정권자의 목적함수를 최적화하는 것을 찾는 이론 일체를 말한다. 본 연구실은 이론적이고 수리적인 연구에 초점을 두고 있다. 관련 과목으로는 경영과학, 선형 및 비선형 계획, 정수계획 및 네트워크 최적화, 조합최적화, 최적화 근사해법 등이 있다. 기존 수리계획 연구실과 상호 보완적이며, 실제 모든 세미나, 논문지도, 그리고 기타 행사들을 협동으로 진행하고 있다.

관련과목

최적화 분야에서의 연구를 수행하기 위해서 필요한 기존 이론 및 최신 동향들은 다음의 과목들을 통해 배울 수 있다.

- 경영과학: 경영과학은 현실 의사결정문제를 수리모형화하고, 그 해법을 개발하며, 마지막으로 해법이 제공한 해를 의사결정에 적용하는 일체의 과정이다. 강의에서는 선형계획, 네트워크 최적화, 정수 및 조합최적화, 비선형계획, 게임이론을 다룬다.

- 선형계획: 선형제약식으로 정의되는 가능해 집합이 가지는 특수한 구조와 쌍대성, 그리고 이에 기반한 해법인 simplex method에 대한 강의가 진행된다.

- 비선형계획: 목적함수 및 제약식이 비선형(nonlinear) 형태인 문제들은 선형계획과는 달리 풀기가 어렵다. 강의에서는 여러 유형의 비선형 최적화 문제에서 최적해가 만족해야 될 조건들과, 이에 기반한 다양한 해법들을 다룬다.

- 정수계획: 선형계획 문제에서 부가적으로 해에 대한 정수조건이 추가된 문제를 정수계획이라고 한다. 정수계획은 많은 현실문제를 표현할 수 있는 반면 최적해를 구하는 것이 어렵다. 강의에서는 정수계획 문제에서 좋은 가능해를 찾기 위한 이론 및 방법론들을 다룬다.

- 볼록계획: 비선형계획 문제 중에서 제약식과 목적식의 볼록성(convexity)이 보장되는 경우에는 최적해를 찾는 효율적인 해법이 존재한다. 강의에서는 집합과 함수의 볼록성의 정의 및 성질을 다루며, 볼록성을 갖는 최적화 문제의 특징 및 이를 풀기 위한 해법을 다룬다.

- 조합최적화: 선형계획을 포함한 볼록계획 문제를 제외한 대부분의 최적화 문제들은 효율적인 해법이 알려져 있는 어려운 문제들이 많다. 이론적으로 문제의 어려움을 규명하는 방법으로는 문제가 NP-complete (또는 NP-hard) 문제에 속한다는 것을 보이는 것이다. 강의에서는 이러한 계산 복잡도에 관련한 이론과 NP-complete 증명 기법 등을 다룬다.

- 최적화 근사해법: NP-complete에 속하는 문제로 알려진 어려운 최적화 문제에 대표적인 접근 방법 중 하나는 해품질을 일부 포기하는 대신에 효율적으로 가능해를 구하는 것이다. 근사해법은 효율적으로 가능해를 구하면서, 가능해의 품질이 최적해에 비해 나쁘지 않음을 보장해 줄 수 있는 해법을 말한다. 강의에서는 대표적인 NP-complete 문제에 대한 근사해법과 이를 개발하기 위한 기법들을 다룬다.

이론분야 연구

1. 조합최적화 근사해법 : 많은 최적화 문제들은 이른바 NP-hard 문제로 구분되어, 정확한 최적해를 구하기 위해서는 너무 많은 비용이 드는 문제들이다. 또한 상대적으로 빠른 시간 내에 최적해를 찾는 해법이 존재하는 최적화 문제의 경우에도, 최적해를 찾는 시간이 현실 문제에 적용하기에는 만족스럽지 못한 경우가 있다. 예를 들어, 실시간 이미지 처리에 경우, 최적해를 찾아주는 기존 해법으로는 짧은 시간 내에 해결할 수 없다. 따라서 이런 경우, 계산 자원의 사용을 허용할 수 있는 범위로 제한하면서 최적해에 가까운 해를 구하는 근사해법은 중요한 대안적인 접근법이다. 본 연구실에서는 여러 가지 응용성을 가진 조합 최적화 문제들의 근사해법에 관한 연구를 수행하고 있다.

2. SDP, 다항최적화문제 : 현재 최적화는 선형계획과 같은 전통적인 수리모형뿐 아니라, SDP 같은 새로운 수리모형으로 그 영역이 확대되고 있다. 본 연구실에서는 이러한 수리모형을 조합최적화 문제의 근사해법에 응용하는 연구를 추구하고 있다.

응용분야 연구

경영과학 및 최적화는 현실의 문제를 풀기 위해 시작된 학문이다. 이 순간에도 각 산업 분야의 내면에서 그 산업 활동의 목적을 극대화하는 해를 제공하고 있다. 본 연구실에서는 지금까지 SCM, 수송 문제, 철도 경합, KTX 차량 할당, 포트폴리오 구성 문제와 같은 여러 응용 문제들에 대해 연구를 수행했다.

한편, 여러 명의 의사결정자들의 이해관계가 서로 상충되는 상황에서의 문제는 게임이론을 통해 접근할 수 있다. 다수의 의사결정자들이 때로는 상충되는 이해관계 속에서, 혹은 때로는 협력관계 속에서 서로의 목적을 위해 합리적인 의사결정을 해야 하는 경우는 다양하기 때문에 그 응용분야는 매우 넓다. 국제 관계에서 나타나는 상충 관계, 시장에서의 기업 간 이해 관계 등에서 나타나는 의사결정 문제는 게임이론의 한 응용분야이고, 사용자들의 대중 교통망에서의 이동경로 선택도