수학적 최적화와 정수 계획법

최적화 문제란

최적화 문제는 지켜야 할 조건 안에서 어떤 값을 가장 크게(또는 작게) 만드는 변수 값을 찾는 문제다. 차량·회의실·작업자 배정, 근무표, 배송 경로, 적재처럼 무엇을 어디에 넣을지 고르는 문제가 대부분 여기에 속한다. 고를 수 있는 조합이 지수적으로 늘어나므로 모든 경우를 따져 볼 수는 없다.

푸는 세 가지 길

방법	방식	장점	단점
문제 전용 알고리즘	문제 구조에 맞춘 알고리즘을 직접 설계한다(그리디, DP, 그래프 알고리즘)	빠르고 최적을 증명할 수 있다	문제가 조금만 바뀌어도 다시 설계해야 한다. 설계 비용이 크다
휴리스틱·메타휴리스틱	유전 알고리즘, 담금질 기법, 지역 탐색으로 좋은 해를 빠르게 찾는다	구현이 비교적 쉽고 큰 문제에도 돈다	최적이라는 보장이 없고, 얼마나 나쁜지도 모른다
수리 모델 + 솔버	문제를 수식으로 적고 범용 솔버에 넘긴다	조건을 추가·변경하기 쉽다. 최적해 또는 최적과의 차이(gap)를 알려 준다	문제가 커지면 연산 시간이 급격히 는다

조건이 자주 바뀌는 업무 문제에서는 세 번째 길이 개발 비용을 크게 줄인다. 수식을 코드로 옮긴 모양이 그대로라서 읽고 고치기도 쉽다.

모델의 세 요소

요소	뜻	구간 배정 예
결정 변수	솔버가 정할 값	`x[r][c] ∈ {0, 1}`: 예약 r을 차량 c에 배정하면 1
제약 조건	해가 지켜야 할 조건	모든 예약은 차량 하나에만 배정된다: `Σ_c x[r][c] = 1`. 시간이 겹치는 두 예약은 같은 차량에 못 간다: `x[r1][c] + x[r2][c] ≤ 1`. 이미 확정된 배정은 고정한다
목적 함수	최대·최소화할 값	아래 「목적 함수 설계」

변수가 정수(특히 0/1)로 제한되면 정수 계획법(Integer Programming), 목적 함수와 제약이 모두 선형이면 정수 선형 계획법(ILP), 실수 변수가 섞이면 혼합 정수 계획법(MIP) 이다. "고르거나 고르지 않거나"인 조합 문제는 0/1 변수로 자연스럽게 표현된다. 제약을 모두 만족하는 변수 조합의 집합을 해 공간(feasible region) 이라 하고, 솔버는 그 안에서 목적 함수가 가장 좋은 점을 찾는다.

flowchart LR
  n1["문제를 말로 정의"] --> n2["결정 변수 정하기"] --> n3["제약을 식으로"] --> n4["목적 함수"] --> n5["솔버 실행"]
  n5 --> r1["최적해"]
  n5 --> r2["시간 제한 내 최선 해 + gap"]
  n5 --> r3["해 없음(infeasible)"]

목적 함수 설계

가장 어려운 부분은 "어떤 배정이 더 좋은가"를 숫자로 만드는 일이다.

비즈니스 목표를 그대로 옮기기 어려우면 대리 지표를 만든다. 구간 배정이라면 "앞으로 들어올 만한 예약"을 나타내는 가상 예약을 깔아 두고, 기존 예약을 배정한 뒤 가상 예약이 많이 들어갈수록 좋다고 정의할 수 있다. 빈 시간이 잘게 쪼개지지 않고 한 차량에 모이도록 유도하는 효과다.
좋은 지표는 모델도 가볍게 만든다. 예약 사이의 선후 관계를 변수로 일일이 두지 않아도 된다.
목표가 여럿이면 가중합으로 묶거나, 중요한 것부터 차례로 최적화하고 앞의 결과를 제약으로 고정한다.

솔버

솔버	특징
Google OR-Tools CP-SAT	오픈 소스. 정수·논리 제약이 많은 조합 문제(배정, 일정)에 강하다
HiGHS, SCIP	오픈 소스 LP·MIP 솔버
Gurobi, CPLEX	상용. 대규모 MIP에서 빠르다

모델링 라이브러리(OR-Tools, PuLP, Pyomo, JuMP)로 수식을 쓰면 솔버를 바꿔 끼우기 쉽다.

운영에서 주의할 것

계산량: 변수·제약 수가 늘면 시간이 급격히 는다. 독립적인 부분 문제로 쪼개고(지역·차종별), 확정된 부분은 고정하고, 시간 제한을 두고 그때까지의 최선 해를 쓴다.
실행 주기: 이벤트마다 다시 최적화하면 결과가 자주 바뀌어 사람이 따라가기 어렵다. 일정 간격으로 모아 배치로 돌리는 편이 운영에 맞는 경우가 많다.
개선 여지: 자원이 남아돌거나 거의 꽉 찬 상태에서는 배치를 바꿀 여지가 작다. 적당히 찬 상황에서 효과가 가장 크다.
해가 없을 때: 제약이 서로 충돌하면 infeasible이 나온다. 일부 제약을 벌점이 있는 소프트 제약으로 바꿔 항상 해가 나오게 한다.

정리

배정·일정 문제는 결정 변수·제약·목적 함수로 적으면 범용 솔버로 풀린다.
0/1 선택 문제는 정수 계획법으로 자연스럽게 표현된다.
가장 어려운 일은 목적 함수 설계다. 비즈니스 의미를 담은 대리 지표를 만든다.
문제 크기, 실행 주기, 해가 없을 때의 처리까지 운영 관점으로 함께 설계한다.

버그 제보