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