Integer Programming

all or nothing problem에서 사용
ex) knapsack problem → 아이템을 0.8개 넣을 수 없다

Requirements on selecting variables

1. At Least

   at least one of variables among items 1, 3, 4:

   \(x_1 + x_3 + x_4 ≥ 1\)

2. At Most

   at most two of variables among items 1, 3, 4:

   \(x_1 + x_3 + x_4 ≤ 2\)

3. Or

   select variable 1 or 2:

   \(x_1 + x_2 ≥ 1\)

   select 2 otherwise item 3 and 4 together:

   \(2x_2 + x_3 + x_4 ≥ 2\)

4. If-else

   if variable 1 is selected, then variable 2 is also selected:

   \(x_1 ≤ x_2\)

   if variable 1 is selected, do not select item 3 and 4:

   \(2(1 - x_1) ≥ x_3 + x_4\)

At least/most some constraints

constraints를 유연하게 선택하는 방법

\(g_1(x) ≤ b_1\)과 \(g_2(x) ≥ b_2\)를 둘 다 만족하는 경우를 표현하려면 union으로 표현할 수 있다.

이는 linear program에 적합하지 않기 때문에 variable로 표현한다.

\[z = \begin{cases} 0 & \text{if } g_1(x) ≤ b_1 \\ 1 & \text{if } g_2(x) ≤ b_2 \end{cases}\]

이는 아래의 수식으로 표현할 수 있다

\[\begin{align} &g_1(x) - b_1 ≤ M_1z \\ &g_2(x) - b_2 ≤ M_2(1 - z) \end{align}\]

이때\(M_1\)과 \(M_2\)는 충분히 큰 상수이다.

일반적인 예시

Facility location problem

1. where to open convenience stores?
2. where to build warehouses or distribution centers?
3. where to build factories?
4. where to build power stations, fire stations, or police stations?

→ where to locate scarce resource?

demoand nodes potential locations

1. set covering problem
2. maximum covering problem
3. fixed charge location problem

machine scheduling problem

production mode

1. single machine serial production
2. multiple parallel machines
3. flow shop scheduling: all jobs must follow the same sequence
4. job shop scheduling: each job has its own sequence

job splitting

• preemptive problem: 특정 작업을 중단하고 시급한 다른 작업을 수행한 후, 다시 돌아올 수 있음
• non-preemptive problem

performance measurement

• Makespan: 모든 작업이 끝나는 시간
• total completion time
• number of delayed jobs
• total lateness: completion time이 due time보다 앞서는 경우 negative lateness
• total tardiness: completion time이 due time보다 뒤에 있는 경우에만 completion time - due time, 그 외 0