1. Big-M

Big-M은 특정 조건에서만 제약식을 활성화하기 위해 사용하는 큰 값이다.

예를 들어,

x = 1일 때 제약 적용
x = 0일 때 제약 완화

와 같은 조건을 MILP에서 표현할 때 사용한다.

주의

Big-M을 너무 크게 설정하면

LP Relaxation 약화
→ Solver 성능 저하
→ MIP Gap 증가

가 발생할 수 있다.

따라서 가능한 범위에서 작고 타이트한 M 값을 사용하는 것이 중요하다.

---

2. Feasible Solution과 Optimal Solution

Feasible Solution

모든 제약조건을 만족하는 해.

Optimal Solution

Feasible Solution 중 목적함수가 가장 좋은 해.

Feasible
→ 조건을 만족하는 해

Optimal
→ 조건을 만족하면서 가장 좋은 해

Solver는 먼저 feasible solution을 찾고, 이후 더 좋은 해가 존재하는지 계속 탐색한다.

---

3. Incumbent, Best Bound, MIP Gap

Gurobi 로그에서 중요하게 확인한 개념이다.

Incumbent

현재까지 발견한 가장 좋은 feasible solution.

Best Bound

아직 탐색하지 않은 영역까지 고려했을 때 최적해가 가질 수 있는 이론적 경계값.

MIP Gap

Incumbent와 Best Bound 사이의 차이를 나타낸다.

Gap ↓
→ 현재 해가 최적해에 가까워짐

기억할 것

Gap이 크다
≠ Infeasible

예를 들어 Gap이 92%라는 것은 해가 없다는 의미가 아니라, 현재 해와 최적해의 경계 사이 차이가 아직 크다는 의미다.

---

4. Branch-and-Bound

MILP Solver가 최적해를 찾는 대표적인 방법이다.

문제를 작은 문제로 분할
→ 각 영역의 Bound 계산
→ 가능성 없는 영역 제거
→ 좋은 해가 존재할 영역 탐색

Gurobi 로그 주요 항목

Incumbent : 현재 가장 좋은 해
BestBd    : 최적해의 Bound
Gap       : Incumbent와 BestBd의 차이
Expl      : 탐색 완료한 Node
Unexpl    : 아직 탐색하지 않은 Node

Solver는 단순히 좋은 해를 찾는 것뿐 아니라 그 해보다 더 좋은 해가 존재하지 않는다는 것까지 증명해야 Optimal이 된다.

---

5. Exact Method와 Heuristic

Exact Method

최적해를 보장할 수 있는 방법.

예:

• MILP
• Branch-and-Bound

장점:

Optimality 보장 가능

단점:

문제 규모 증가
→ 계산시간 급증

Heuristic / Metaheuristic

최적해 보장보다는 제한시간 안에 좋은 해를 빠르게 찾는 방법.

예:

• GA
• ALNS
• SA
• 2-opt

---

6. Genetic Algorithm

GA는 생물의 진화 과정을 모방한 탐색 알고리즘이다.

초기해 생성
→ 선택
→ 교차
→ 돌연변이
→ 새로운 해 생성

한계

좋은 해를 빠르게 찾을 수 있지만 탐색이 특정 영역에 집중되면

Local Optimum

에 빠질 수 있다.

---

7. ALNS

Adaptive Large Neighborhood Search

현재 해의 일부를 크게 제거한 뒤 다시 복구하면서 새로운 해를 탐색한다.

현재 해
↓
Destroy
↓
일부 고객 제거
↓
Repair
↓
고객 재삽입
↓
새로운 해 평가

사용한 Destroy Operator

Worst Removal
Route Removal

Worst Removal
현재 해에서 비용에 큰 영향을 주는 고객을 제거한다.

Route Removal
특정 Route의 고객들을 제거해 경로 구조를 크게 변경한다.

---

8. Repair Operator

Greedy Insertion

고객을 삽입했을 때 비용 증가가 가장 작은 위치에 삽입한다.

Regret-2

고객의

두 번째로 좋은 삽입 비용
-
가장 좋은 삽입 비용

을 계산한다.

이 차이가 큰 고객을 먼저 삽입한다.

핵심

지금 삽입하지 않으면
나중에 비용이 크게 증가할 고객을 우선 처리

---

9. Simulated Annealing

ALNS에서 새로운 해를 받아들일지 결정할 때 사용할 수 있는 방법이다.

더 좋은 해
→ Accept

더 나쁜 해
→ 일정 확률로 Accept

이유

좋은 해만 계속 선택하면 Local Optimum에 빠질 수 있다.

나쁜 해를 일정 확률로 받아들여 현재 지역을 벗어나 더 넓은 영역을 탐색할 수 있다.

---

10. 2-opt

Route 내부의 두 연결을 끊고 경로 순서를 변경하여 더 짧은 경로를 찾는 Local Search 방법이다.

기존 경로
A-B-C-D

일부 연결 변경
A-C-B-D

차량 경로를 부분적으로 개선할 때 자주 사용하는 기본적인 Local Search 기법이다.

---

11. 최적화 문제의 크기

MILP에서는 변수 수와 제약식 수가 증가하면 계산량도 크게 증가한다.

특히 차량, 고객, Dock, Time Slot 등의 조합이 많아지면

문제 규모 증가
→ 변수 및 제약식 증가
→ 탐색 공간 증가
→ Solver 계산시간 증가

가 발생한다.

핵심

모델을 만들 때는

정확한 모델
+
계산 가능한 모델

을 함께 고려해야 한다.

---

12. Instance와 모델 검증

처음부터 큰 데이터를 사용하는 것보다 작은 Instance부터 모델을 검증하는 것이 중요하다.

소규모 Instance
→ 모델 동작 검증
→ Optimal Solution 확인
→ 데이터 규모 확대
→ 계산시간 및 Gap 확인
→ 필요 시 Heuristic 적용

중요한 점

코드가 실행된다
≠ 모델이 올바르다

결과가 실제로 의도한 제약과 운영 방식을 만족하는지 직접 확인해야 한다.

---

9월 최적화 공부 핵심 흐름

수리모델 구축
↓
소규모 Instance 검증
↓
Gurobi로 Exact Solution 탐색
↓
Incumbent / Best Bound / MIP Gap 확인
↓
문제 규모 증가
↓
계산시간 증가
↓
Heuristic / Metaheuristic 필요
↓
GA / ALNS / SA / Local Search 적용

핵심은 최적해를 찾는 것뿐 아니라, 문제 규모와 제한시간을 고려해 적절한 해결 방법을 선택하는 것이다.