정수계획법 (Integer Programming)
한 줄 정의: 결정변수가 반드시 정수 값만 가져야 하는 제약 아래 목적함수를 최적화하는 수리계획 문제입니다.
쉽게 풀면
공장을 몇 개 지을지, 트럭을 몇 대 운행할지처럼 "반쪽짜리"가 있을 수 없는 문제를 풀 때 정수계획법을 씁니다. 일반적인 최적화 기법은 답을 3.7대처럼 소수로 내놓을 수 있지만, 현실에서는 트럭 3.7대를 운행할 수 없습니다. 정수계획법은 이런 답을 처음부터 정수로만 나오도록 강제하는 방법입니다. 그래서 계산이 훨씬 까다롭고 시간이 오래 걸리는 경우가 많습니다.
왜 중요한가
생산 설비 투자, 시설 입지 선정, 인력 배치, 일정 편성 등 산업공학의 많은 의사결정 문제는 본질적으로 개수·순서·선택 같은 이산적인 성격을 가지고 있습니다. 정수계획법은 이러한 현실적 제약을 정확히 반영할 수 있어 이론과 실무 양쪽에서 폭넓게 연구되고 응용됩니다.
논문에서는 이렇게 쓰입니다
"본 연구에서는 물류센터 입지 선정 문제를 정수계획법(Integer Programming) 모형으로 정식화하였다."
어느 위치에 물류센터를 지을지를 0 또는 1의 정수 변수로 표현해 최적의 조합을 찾는다는 의미입니다.
"제안된 정수계획법 모형은 분기한정법(Branch and Bound)을 이용하여 최적해를 도출하였다."
정수 해를 구하기 위해 흔히 쓰이는 탐색 알고리즘을 적용해 문제를 풀었다는 뜻입니다.
조금 더 깊게 보면
정수계획법은 모든 변수가 정수인 순수정수계획법과, 일부만 정수인 혼합정수계획법으로 나뉩니다. 대표적인 풀이법으로는 분기한정법, 절단평면법 등이 있으며, 변수와 제약이 많아질수록 계산 복잡도가 급격히 커지는 NP-hard 특성을 가지는 경우가 일반적입니다. 그래서 대규모 문제에서는 완전한 최적해 대신 근사해를 구하는 휴리스틱 기법이 함께 활용되기도 합니다.
주의할 점
정수 제약을 추가하면 연속 변수만 사용하는 선형계획법보다 풀이 시간이 크게 늘어날 수 있어, 문제 규모에 따라 적절한 알고리즘 선택이 중요합니다.