24-01 Definition

이 절에서는 Mixed integer program 방식을 통해서 Optimization problem 을 풀기 위한 기본 개념들에 대해 설명하고자 한다.

Problem definition

Optimization model 중 일부 변수(variables)가 정수(integer)라는 제한조건이 있을 때, 이를 integer program 이라 부른다.

\(\begin{align} &\min_{x} && f(x) \\\\ &\text{subject to } && x \in C \\\\ &&&x_{j} \in \mathbb{Z}, j \in J \end{align}\) \(\begin{align} \text{where } f: \mathbb{R}^{n} \rightarrow \mathbb{R}, \quad C \subseteq \mathbb{R}^{n} \quad and \quad J \subseteq {1, \dotsc, n}. \end{align}\)

앞선 식에서 \(J\)가 다음을 만족 한다면, pure integer program 이라고 부른다.

\(J =\) { \(1, \dotsc, n\) }

이 절에서 논의되는 \(f\) 와 \(C\) 는 모두 convex라고 가정하도록 하자.

Binary variables

Integer program을 대표하는 몇몇 사례를 살펴보면 yes/no 결정 문제 또는 논리값등을 들 수 있다. 이때 이진변수(binary variable)를 사용해서 문제를 정의하면서 조건에 대한 0 혹은 1의 값을 구해 문제를 풀게 된다.

다음으로 소개할 Combinatorial optimization은 integer program과 직접적으로 연관되어 있다. binary variable을 활용함으로써, 기존 문제를 재변형하여 새로운 문제로 바꿔 풀 수 있기 때문이다.

Combinatorial optimization problem은 triple \((N, \mathcal{F}, c)\) 표현을 활용하여 정의된다.

• \(\quad N\) 은 유한한 ground set 이다
  
• \(\quad \mathcal{F} \subseteq 2^{N}\) 는 feasible solution들의 집합이다
  
• \(\quad c \in \mathbb{R}^{N}\) 은 cost function 이다
  

triple \((N, \mathcal{F}, c)\) 를 통해서 다음 수식을 푸는 것이 최종 목표이다.

\[\begin{align} \quad \min_{S \in \mathcal{F}} & \sum_{i \in S} c_{i} \\ \end{align}\]

많은 결합 최적화(combinatorial optimization) 문제는 binary integer program들로 쓰여질 수있다.