[SLSCM] 26년 09월

About this offer

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