선형계획법으로 말 가두기, 생각보다 쉽다

Integer programming easily encloses horse

 

⚡ 한 줄 요약: "조건을 부등식으로만 쓸 수 있으면" 길찾기·배치·스케줄링 같은 난제도 솔버가 대신 푼다 → 직접 알고리즘 짜기 전에 "이거 선형계획법으로 모델링되나?"부터 자문하라.

 

 

무슨 일인지

요즘 해커뉴스에서 화제가 된 글이 하나 있다.
제목부터 엉뚱한 "Integer programming easily encloses horse(정수계획법으로 말을 손쉽게 가둔다)".
들판에 흩어진 점들을 울타리로 둘러싸 '말'을 가두는 기하 퍼즐을, 직접 알고리즘을 짜는 대신 정수계획법(Integer Programming) 문제로 번역해 범용 솔버에 던졌더니 깔끔하게 풀리더라는 이야기다.

핵심 메시지는 퍼즐 자체가 아니다.
"의외로 많은 문제가 부등식 몇 개로 표현되고, 그러면 사람이 머리 싸맬 필요 없이 솔버가 푼다"는 점이다.
그 토대가 바로 검색 수요 높은 선형계획법(Linear Programming, LP)이다.

 

 

배경 — 선형계획법이 뭔데

선형계획법은 "1차식(선형)으로 된 목적함수를, 1차식 제약조건 아래에서 최대/최소로 만드는" 최적화 기법이다.
구성 요소는 딱 셋이다.

 

구성	의미	예시
변수	우리가 정할 값	제품 A를 몇 개 만들까
목적함수	최대/최소로 만들 대상	총이익 = 3A + 5B
제약조건	지켜야 할 부등식	재료 A + 2B ≤ 14

 

변수가 연속값(소수 허용)이면 순수 선형계획법이고, 단순법(Simplex)·내부점법 등으로 실무에서 매우 빠르게 풀린다.
그런데 "말 0.7마리"는 말이 안 된다.
변수에 정수 제약을 걸면 그게 정수계획법(IP), 일부만 정수면 혼합정수계획법(MILP)이다.
이론적으로 IP는 NP-난해라 일반적으로 어렵지만, 분기한정법(branch & bound) 기반 현대 솔버 덕에 현실 규모 문제는 놀랄 만큼 잘 풀린다.
말 가두기 글이 보여준 게 정확히 이 지점이다.

 

 

개발자에게 주는 의미

직접 코드를 짜는 사고방식과 결이 다르다.

• "어떻게 풀까"가 아니라 "무엇을 만족해야 하나"를 적는다. 알고리즘이 아니라 제약을 선언하면 끝이다(선언적 사고).
• 배치, 스케줄링, 경로·자원 할당, 포트폴리오, 출고 최적화처럼 "여러 제약 속 최적 조합" 문제는 대부분 LP/MILP로 모델링된다.
• 직접 짠 그리디·휴리스틱은 "그럭저럭 좋은 답"에 그치지만, 솔버는 최적해(또는 최적성 보장 구간)를 준다.

함정도 분명하다.
제약이나 목적이 비선형(곱셈·제곱·조건분기)이면 그대로는 안 된다.
다만 'A이거나 B' 같은 논리 조건은 이진변수 + Big-M 기법으로 선형화하는 정석 패턴이 있다.

 

 

실무 적용 — 10줄이면 모델링 끝

파이썬 PuLP로 간단한 생산 최적화를 보자.
핵심은 부등식만 쓰면 된다는 점이다.

import pulp

# 제품 A, B 생산으로 이익 최대화
prob = pulp.LpProblem("max_profit", pulp.LpMaximize)

# 연속 변수 → 선형계획법(LP)
a = pulp.LpVariable("A", lowBound=0)
b = pulp.LpVariable("B", lowBound=0)

prob += 3 * a + 5 * b        # 목적함수: 이익
prob += a + 2 * b <= 14      # 제약: 재료 한도
prob += 3 * a - b >= 0       # 제약: 생산 비율
prob += a <= 4               # 제약: 설비 용량

prob.solve()
print(pulp.value(a), pulp.value(b), pulp.value(prob.objective))

"말 0.7마리" 문제를 막으려면 변수 선언만 바꾸면 그대로 정수계획법이 된다.

a = pulp.LpVariable("A", lowBound=0, cat="Integer")  # 정수 제약

모델은 그대로 두고 cat="Integer" 한 줄로 LP → IP 전환.
"말은 정수 마리만" 같은 현실 제약이 이렇게 들어간다.
솔버는 PuLP 기본 동봉 CBC 외에 HiGHS, Google OR-Tools 등으로 교체 가능하다.

 

 

체크포인트 — 그래서 뭘 해보면 되나

• 새 문제를 만나면 먼저 자문하라: "변수·목적·제약을 1차식으로 적을 수 있나?" 가능하면 직접 알고리즘 짜지 말고 솔버에 맡겨라.
• 작게 시작하라: pip install pulp 후 위 10줄을 그대로 돌려보고, 제약을 하나씩 늘리며 감을 잡아라.
• 정수 여부를 의식하라: "0.5개"가 말이 되는지로 LP/IP를 가른다. 규모가 커져 느려지면 정수변수 개수부터 줄여라(완화·근사).
• 비선형·논리조건은 이진변수 + Big-M 선형화 패턴을 먼저 검색해보라. 의외로 정형화된 레시피가 많다.

 

 

참고

• dynomight — Integer programming easily encloses horse
• Hacker News — 관련 토론
• PuLP 공식 문서 — Optimization with PuLP
• Google OR-Tools — Linear & Integer Optimization 가이드
• HiGHS — 고성능 LP/MILP 오픈소스 솔버