Mixed Integer Problem(MIP)에서 조건을 완화 하여 문제를 해결하기 위해 Lagrangian Relaxation을 사용한다.
예제는 “Facility Location Problem”중 “p-Median Problem”의 예이다.
고객들의 위치와 고객이 요구하는 서비스 수요량과 그 서비스를 제공하기 위한 시설을 도입 또는 건설하기 위한 후보 위치와 후보 위치에서 고객에게 서비스를 하기 위한 운송비용이 주어 졌을 때 운송비용을 최소화하는 장소에 시설을 건설하기 위한 최적의 장소를 찾는 문제이다.
JuMP와 MIP solver를 사용한 결과와 Lagrangian Relaxation을 사용한 결과를 비교 한다.
상세 내용은 아래 링크를 클릭하여 볼 수 있으며 필요한 데이터도 링크를 걸어 둔다.