혼합정수계획법 (Mixed-Integer Programming)
쉽게 풀면
공장을 "지을지 말지"는 0 또는 1의 정수로, 그 공장에서 "얼마나 생산할지"는 소수점이 있는 연속값으로 표현하고 싶을 때가 많습니다. 혼합정수계획법은 이렇게 정수 변수와 연속 변수를 한 모형 안에 함께 담을 수 있게 해줍니다. 모든 변수를 정수로 강제하지 않아도 되기 때문에 현실 문제를 더 유연하게 표현할 수 있습니다. 그만큼 다양한 산업 문제에 널리 쓰입니다.
왜 중요한가
공급망 설계, 생산 계획, 스케줄링 등 대부분의 실제 산업공학 문제는 예/아니오 결정과 양적 결정이 동시에 얽혀 있습니다. 혼합정수계획법은 이런 복합적인 구조를 하나의 최적화 모형으로 통합할 수 있어 실무 적용성이 높다고 평가받습니다. 생산 계획에서 설비 가동 여부나 배송 경로에서 차량 운행 여부처럼 실제 의사결정 변수 상당수가 연속값이 아닌 이산적 선택이기 때문에, 혼합정수계획법은 현실의 생산·물류 문제를 다루는 데 필수적인 수리적 도구로 쓰입니다.
논문에서는 이렇게 쓰입니다
설비를 지을지 말지는 정수 변수로, 실제 생산량은 연속 변수로 표현해 함께 최적화한다는 뜻입니다.
혼합정수계획 문제를 풀기 위해 널리 쓰이는 전용 최적화 소프트웨어를 사용했다는 의미입니다.
조금 더 깊게 보면
혼합정수계획법은 목적함수와 제약이 선형이면 혼합정수선형계획법(MILP), 비선형 요소가 포함되면 혼합정수비선형계획법(MINLP)으로 구분됩니다. 대표적인 풀이 방법은 분기한정법을 절단평면법 등과 결합한 분기절단법이며, 상용 솔버들이 이를 구현해 널리 활용됩니다. 혼합정수계획법은 일부 변수는 정수로, 나머지 변수는 연속값으로 두어 현실 문제를 더 정교하게 표현할 수 있게 해주는 기법으로, 순수정수계획법보다 표현력이 넓어 생산계획이나 물류 네트워크 설계에서 폭넓게 쓰입니다. 혼합정수계획법은 변수 일부만 정수로 제한한다는 점에서 모든 변수가 정수여야 하는 순수정수계획법과 구분되며, 분지한계법이나 절단평면법 같은 알고리즘으로 정수 제약을 만족하는 최적해를 탐색합니다.
주의할 점
정수 변수의 수가 많아지면 풀이 시간이 급격히 늘어날 수 있으므로, 문제 규모에 따라 모형 단순화나 근사 기법이 함께 고려되는 경우가 많습니다.
변수 수와 정수 제약이 늘어날수록 탐색해야 할 경우의 수가 기하급수적으로 증가하는 조합적 폭발이 발생할 수 있어, 대규모 문제에서는 정확한 최적해 대신 근사해를 구하는 전략이 흔히 사용됩니다. 변수와 제약식이 늘어날수록 탐색해야 할 조합의 수가 기하급수적으로 증가해 계산 시간이 급격히 길어지므로, 대규모 문제에서는 정확한 최적해 대신 근사해를 구하는 발견적 기법이 함께 활용됩니다.