1. 상한과 하한
친구 몸무게를 맞혀야 한다. 정확한 숫자는 모르지만 이렇게 말할 수 있다.
"음… 최소 60kg은 넘겠지(하한), 아무리 많아도 80kg은 안 넘겠지(상한)."
정확한 답을 몰라도 "이 범위 안에 있다"는 건 확신할 수 있다. 그리고 범위가 좁아질수록("68~70kg 사이!") 답에 가까워진다.
최적화도 똑같다. 진짜 정답(가장 좋은 답)을 단번에 찾기 어려우니까,
- 아래로는 여기보다 좋을 순 없다는 선(하한)을 긋고
- 위로는 적어도 이 정도는 된다는 선(상한)을 긋는다.
두 선의 간격이 0에 가까워지면 → "정답 찾았다"고 증명되는 것이다. 이 간격을 gap(갭)이라 부른다.
💡 왜 중요하냐면, 컴퓨터가 "완벽한 정답"을 다 못 찾아도 "지금 답이 최선에서 2% 이내"라고 보장해줄 수 있기 때문이다.
- 하한: LP 완화에서 얻는다.
- 상한: 실제로 실행 가능한(휴리스틱)에서 얻는다.
- 최적성 척도:
2. min-max
택배 기사 3명에게 배달 구역을 나눠준다. 두 가지 방법이 있다.
- 방법 A: 한 명에게 60km, 나머지에게 20km·10km → 총 90km
- 방법 B: 35km·30km·25km → 총 90km
총 거리는 둘 다 90km로 똑같다. 그런데 딱 봐도 B가 낫다. A는 한 명만 죽어나고, B는 모두 비슷하게 일하고 다 같이 일찍 퇴근한다.
여기서 핵심은 "제일 오래 일하는 사람"이다.
- A는 제일 힘든 사람이 60km
- B는 제일 힘든 사람이 35km
이렇게 "가장 나쁜 값(제일 힘든 사람)을 최대한 줄이자"는 목표가 바로 min-max다. 부하를 골고루 나누고 싶을 때, 다 같이 빨리 끝내고 싶을 때 쓴다.
💡 그냥 "총 거리 줄이기"만 하면 A와 B를 구분 못 한다. "제일 힘든 사람을 보라"는 관점이 있어야 B를 고를 수 있다.
3. master와 subproblem
사장님이 회사 전체 계획을 세운다. 근데 혼자 모든 걸 다 정할 순 없다. 그래서 이렇게 한다.
- 사장(master): 큰 그림만 정한다. "이 방향으로 가자."
- 현장 직원(subproblem): 그 방향이 현실적으로 되는지, 더 좋은 방법은 없는지 확인해서 보고한다.
사장이 큰 결정 → 직원이 피드백 → 사장이 수정 → 다시 직원이 피드백… 이 왕복을 반복하면, 혼자 전부 계산하는 것보다 훨씬 빠르게 좋은 답에 도달한다.
큰 문제를 "큰 결정 담당(master)"과 "세부 확인 담당(subproblem)"으로 나눠 주고받는 것 — 이게 분해(decomposition)의 핵심이다.
직원이 사장에게 보내는 피드백 종류에 따라 두 갈래로 나뉜다.
- "이건 안 돼요 / 이렇게 하면 더 좋아요" 하고 조건을 보내면 → Benders
- "이런 새 방법(경로)이 있어요" 하고 선택지를 보내면 → 열 생성
4. LP relaxation
"반 대표를 몇 명 뽑을까?" 계산기를 두드렸더니 2.5명이라고 나왔다. 현실에 2.5명은 없다. 하지만 이 답도 쓸모가 있다. "진짜 답은 2명 아니면 3명 근처겠구나"라는 감을 주니까.
원래 문제는 "사람은 딱 떨어지는 정수여야 한다"는 빡빡한 규칙이 있어서 풀기 어렵다. 그래서 "잠깐 2.5명도 허용하자"고 규칙을 느슨하게 푼다. 이렇게 하면 문제가 훨씬 쉽게 풀리고, 진짜 답의 범위(1번에서 배운 하한!)를 싸게 알아낼 수 있다.
이게 LP 완화(relaxation)다. "정수여야 한다"는 조건을 잠깐 풀어주는 것.
5. Dual
공장에서 원재료가 딱 100kg까지만 있다. 사장이 묻는다. "재료를 1kg 더 구하면 이익이 얼마나 늘어?" 답이 "3만 원"이라면 → 그 재료 1kg의 숨은 가치는 3만 원이다.
이렇게 "제한을 아주 조금 풀면 결과가 얼마나 좋아지는가"를 나타내는 값을 그림자 가격(dual)이라 한다. 겉으로 안 보이지만 각 조건마다 붙어 있는 "숨은 시세표" 같은 것.
배달 문제에서는 이렇게 쓴다. "고객 A를 한 번 방문하는 것의 숨은 가치 = 5천 원." 이 시세표가 있어야 다음 단계에서 "새 배달 경로가 이득인지 아닌지"를 판단할 수 있다.
6. column generation
여행사가 여행 코스를 짠다. 가능한 코스 조합은 수만 가지라 전부 종이에 적을 수 없다. 그래서 이렇게 한다.
- 일단 코스 몇 개만 놓고 시작한다.
- 기획자에게 묻는다. "지금 가진 것보다 더 이득인 새 코스 있어?"
- 있으면 받아서 추가하고, 없으면 끝.
전부 나열하지 않고 이득 되는 선택지만 그때그때 만들어 붙이는 것 — 이게 열 생성(column generation)이다.
배달 문제에서 "새 경로가 이득인지"는 5번의 그림자 가격으로 판단한다.
"이 경로의 실제 비용"이 "그 경로가 들르는 고객들의 숨은 가치 합"보다 싸면 → 이득! 추가한다.
지금 손에 든 코스 몇 개만 놓고 푸는 이 축소판 문제를 RMP(제한된 마스터)라 부른다. "냉장고 재료를 다 꺼내지 않고, 지금 쓸 것만 도마에 올리고 부족하면 그때 가져온다"는 느낌.
7. Branch
한 장면. 열 생성으로 문제를 풀었더니 답이 "이 경로를 0.5번, 저 경로를 0.5번 써라"라고 나왔다. 경로를 반만 쓸 순 없다.
그래서 갈래를 친다. "이 경로를 쓴다 vs 안 쓴다" 두 경우로 나눠서 각각 다시 풀어본다. 이렇게 어중간한 답이 나올 때마다 갈라 가며 정수(딱 떨어지는 답)로 몰아가는 게 분기(branch)다.
열 생성 + 분기를 합친 게 Branch-and-Price. 갈라진 각 경우에서 또 열 생성을 돌린다.
