정수 계획법으로 살펴보는 칵테일 최적화
작성자가 직접 개발한 커스텀 분기 한정(Branch-and-Bound) 알고리즘과 구글 OR-Tools, glpk.js 등 상용 수학적 최적화 솔버의 성능을 칵테일 제조 문제에 빗대어 비교한 글입니다. 개발자가 수십 시간 공들여 만든 알고리즘이 수십 년의 연구가 집약된 범용 솔버의 압도적인 속도(밀리초 단위의 계산)에 미치지 못한다는 사실을 체감하게 되는 기술적 인사이트를 제공합니다. 복잡한 최적화 문제를 다루는 실무자들에게 이미 검증된 오픈소스 솔버의 강력함을 일깨워주는 중요한 사례입니다.
정수 계획법 문제로서의 칵테일 최적화
2026년 6월 18일
나는 오랫동안 정수 계획법(Integer Programming) 문제에 관심을 가지고 있었습니다 (이 문제들은 중복 제거(dedupe) 분야에서 가장 흥미로운 문제들입니다). 과거에는 직접 커스텀 분기 한정(Branch-and-Bound) 알고리즘을 작성하는 방식으로 접근했습니다. 최근 들어 차량 경로 문제(Vehicle Routing)를 다량으로 포함하는 프로젝트에 구글 OR Tools를 사용하고 있는데, 이 과정에서 과거에 내가 정성껏 만든 알고리즘들이 이런 혼합 정수 선형 계획법(Mixed Integer Linear Programming) 솔버들과 대결하면 어느 정도 성능이 나올지 궁금해졌습니다.
결과는 그야말로 압도적이었습니다. 이 솔버들은 수천 시간의 연구와 엔지니어링 노하우가 결집된 기술적 경이로움 그 자체였습니다. 당연히 내가 짠 코드가 이들과 경쟁하기는 어려웠습니다.
몇 년 전, 나에게 주어진 특정 수의 재료만으로 칵테일 트레이 위에서 만들 수 있는 칵테일의 종류를 최대화하는 분기 한정(Branch-and-Bound) 솔버를 작성한 적이 있었습니다. 나름 뿌듯하게 생각했던 이 알고리즘도, 재료 예산을 30개로 설정하면 최적의 해결책을 찾는 데 몇 분씩 걸렸으며, 더 나은 해결책을 찾기 위해 끊임없이 검색하느라 사실상 종료되지 않았습니다.
하지만 아래에서 볼 수 있듯, glpk.js를 사용하면 최적의 결과를 찾는 데 단 몇 밀리초밖에 걸리지 않습니다. 30개의 재료를 가지고 있을 때, 당신은 29가지의 칵테일을 만들 수 있습니다.
0 10 20 30 40 50 60 70 80 90 100 ↑ 만들 수 있는 칵테일 수 20 40 60 80 100 120 트레이 위의 재료 수 → 29가지 칵테일과 재료
다음은 구매 목록입니다: 재료: 포함되는 칵테일 수