---
id: wiki-2026-0508-combinatorial-optimization
title: Combinatorial Optimization
category: 10_Wiki/Topics
status: verified
canonical_id: self
aliases: [Discrete Optimization, CO, Integer Programming]
duplicate_of: none
source_trust_level: A
confidence_score: 0.9
verification_status: applied
tags: [algorithms, optimization, np-hard, operations-research, ml]
raw_sources: []
last_reinforced: 2026-05-10
github_commit: pending
tech_stack:
  language: Python/C++
  framework: OR-Tools / Gurobi / SCIP / cvxpy
---

# Combinatorial Optimization

## 매 한 줄
> **"매 finite discrete set 위 의 best-element 찾기"**. TSP/Knapsack/Scheduling 의 OR core — 매 1947 Dantzig simplex 부터 매 2026 Gurobi 12 + neural CO hybrid. 매 production 의 매 routing/scheduling/matching 의 ubiquitous — 매 Amazon delivery/Uber matching/airline crew scheduling.

## 매 핵심

### 매 Canonical 문제
- **TSP** (Traveling Salesman): 매 NP-hard, 매 Concorde solver 의 84,000 cities 의 optimal.
- **Knapsack**: 매 NP-hard, 매 weakly — 매 pseudo-polynomial DP O(nW).
- **Set Cover / Vertex Cover**: 매 NP-hard, 매 LP rounding O(log n).
- **Min-cost Flow / Bipartite Matching**: 매 P 의 polynomial.
- **Job-Shop Scheduling**: 매 NP-hard, 매 CP-SAT 의 modern winner.

### 매 Solution 기법
- **Exact**: branch-and-bound, branch-and-cut, dynamic programming.
- **Approximation**: PTAS/FPTAS, LP relaxation + rounding, primal-dual.
- **Heuristic**: greedy, local search, simulated annealing, genetic algorithms.
- **Metaheuristic**: tabu search, ALNS, large-neighborhood search.
- **Modern**: CP-SAT (Google OR-Tools), MIP solvers, neural CO (Pointer Net, GFlowNet).

### 매 Complexity classes
- **P**: 매 Bipartite Matching (Hungarian O(n³)), Min Cut.
- **NP-hard**: 매 TSP, ILP, Vertex Cover, Set Cover.
- **APX-hard**: 매 Set Cover (no PTAS unless P=NP).
- **APX**: 매 Vertex Cover (2-approx trivial).

### 매 응용
1. **Vehicle routing (VRP)**: 매 Amazon Last Mile, UPS ORION.
2. **Workforce scheduling**: 매 airline crew, hospital nurse rostering.
3. **Bin packing**: 매 datacenter VM placement.
4. **Matching markets**: 매 Uber rider-driver, kidney exchange.
5. **Compiler register allocation**: 매 graph coloring.

## 💻 패턴

### Knapsack DP
```python
def knapsack_01(weights, values, capacity):
    n = len(weights)
    dp = [0] * (capacity + 1)
    for i in range(n):
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[capacity]
```

### Branch-and-Bound TSP
```python
import heapq, math

def tsp_bnb(dist):
    n = len(dist)
    best = math.inf
    heap = [(0, [0])]  # (lower_bound, path)
    while heap:
        lb, path = heapq.heappop(heap)
        if lb >= best: continue
        if len(path) == n:
            cost = sum(dist[path[i]][path[i+1]] for i in range(n-1)) + dist[path[-1]][0]
            best = min(best, cost); continue
        for v in range(n):
            if v not in path:
                new_path = path + [v]
                cur = sum(dist[new_path[i]][new_path[i+1]] for i in range(len(new_path)-1))
                # 매 simple LB — 매 MST 의 better
                heapq.heappush(heap, (cur, new_path))
    return best
```

### OR-Tools VRP (production scale)
```python
from ortools.constraint_solver import pywrapcp, routing_enums_pb2

def solve_vrp(distance_matrix, num_vehicles, depot=0):
    mgr = pywrapcp.RoutingIndexManager(len(distance_matrix), num_vehicles, depot)
    routing = pywrapcp.RoutingModel(mgr)

    def dist_cb(i, j): return distance_matrix[mgr.IndexToNode(i)][mgr.IndexToNode(j)]
    transit_idx = routing.RegisterTransitCallback(dist_cb)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_idx)

    params = pywrapcp.DefaultRoutingSearchParameters()
    params.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    params.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
    params.time_limit.seconds = 10
    return routing.SolveWithParameters(params)
```

### CP-SAT Job-Shop Scheduling
```python
from ortools.sat.python import cp_model

def job_shop(jobs):  # jobs[j] = [(machine, duration), ...]
    model = cp_model.CpModel()
    horizon = sum(d for j in jobs for _, d in j)
    tasks = {}
    for j_id, job in enumerate(jobs):
        for t_id, (m, d) in enumerate(job):
            start = model.NewIntVar(0, horizon, f"s_{j_id}_{t_id}")
            end = model.NewIntVar(0, horizon, f"e_{j_id}_{t_id}")
            interval = model.NewIntervalVar(start, d, end, f"i_{j_id}_{t_id}")
            tasks[(j_id, t_id)] = (start, end, interval, m)

    machines = {}
    for (j, t), (s, e, i, m) in tasks.items(): machines.setdefault(m, []).append(i)
    for m, ivs in machines.items(): model.AddNoOverlap(ivs)

    for j_id, job in enumerate(jobs):
        for t in range(len(job) - 1):
            model.Add(tasks[(j_id, t+1)][0] >= tasks[(j_id, t)][1])

    makespan = model.NewIntVar(0, horizon, "makespan")
    model.AddMaxEquality(makespan, [tasks[(j, len(jobs[j])-1)][1] for j in range(len(jobs))])
    model.Minimize(makespan)
    solver = cp_model.CpSolver()
    solver.parameters.max_time_in_seconds = 30
    return solver.Solve(model)
```

### Simulated Annealing TSP
```python
import random, math

def sa_tsp(dist, iters=100000, T0=10.0, alpha=0.9999):
    n = len(dist)
    cur = list(range(n)); random.shuffle(cur)
    def cost(p): return sum(dist[p[i]][p[(i+1)%n]] for i in range(n))
    cc = cost(cur); best, bc = cur[:], cc; T = T0
    for _ in range(iters):
        i, j = sorted(random.sample(range(n), 2))
        new = cur[:i] + cur[i:j+1][::-1] + cur[j+1:]
        nc = cost(new)
        if nc < cc or random.random() < math.exp((cc - nc) / T):
            cur, cc = new, nc
            if cc < bc: best, bc = cur[:], cc
        T *= alpha
    return best, bc
```

### LP Relaxation + Rounding (Set Cover)
```python
import cvxpy as cp
import numpy as np

def set_cover_lp(sets, universe):
    n, m = len(sets), len(universe)
    x = cp.Variable(n, nonneg=True)
    constraints = []
    for u in universe:
        constraints.append(sum(x[i] for i, s in enumerate(sets) if u in s) >= 1)
    cp.Problem(cp.Minimize(sum(x)), constraints).solve()
    # 매 randomized rounding — 매 O(log n) approximation
    return [i for i in range(n) if np.random.random() < min(1, x.value[i] * np.log(m))]
```

## 매 결정 기준
| 문제 size | Approach |
|---|---|
| n < 20 (TSP) | Brute force / DP held-karp O(n²·2ⁿ) |
| n < 100 (TSP) | Branch-and-cut + MTZ formulation |
| n > 1000 (TSP) | LKH heuristic / Concorde |
| Scheduling | CP-SAT (OR-Tools) — 매 modern winner |
| Real-time matching | Hungarian / auction algorithm |
| ILP general | Gurobi/CPLEX > SCIP > CBC |

**기본값**: 매 OR-Tools (CP-SAT) 의 free + production-grade.

## 🔗 Graph
- 부모: [[Optimization]] · [[Operations Research]]
- 변형: [[Linear Programming]] · [[Integer Programming]]

## 🤖 LLM 활용
**언제**: 매 problem-to-formulation translation, 매 OR-Tools/Gurobi code scaffold, 매 constraint reformulation 의 brainstorm.
**언제 X**: 매 large-scale numerical solving (의 dedicated solver 영역), 매 verified optimal proof.

## ❌ 안티패턴
- **Hand-rolled greedy 의 production**: 매 OR-Tools 의 90% 의 better 의 거의 모든 case.
- **ILP everywhere**: 매 LP relaxation feasible 의 fast solve 의 missing.
- **No warm-start**: 매 incremental re-solve 의 1000x speedup 의 missing.
- **Ignoring problem structure**: 매 specialized algorithm (Hungarian, Held-Karp) 의 generic ILP 의 better.
- **Exact 의 over-pursuit**: 매 NP-hard 의 1% gap 의 충분 의 99% case.

## 🧪 검증 / 중복
- Verified (Cook _In Pursuit of TSP_, Schrijver _Combinatorial Optimization_, Wolsey _Integer Programming_).
- 신뢰도 A.

## 🕓 Changelog
| 날짜 | 변경 |
|---|---|
| 2026-05-08 | Phase 1 |
| 2026-05-10 | Manual cleanup — DP/B&B/CP-SAT/SA/LP-rounding patterns |
