라그랑지완화법 (Lagrangian Relaxation)
쉽게 풀면
복잡한 제약조건 때문에 풀기 어려운 문제가 있을 때, 그 제약을 아예 없애버리는 대신 "이 제약을 어기면 벌금을 낸다"는 식으로 목적함수에 벌점을 넣어 문제를 단순화하는 방법이라고 생각하면 됩니다. 제약조건 자체를 없앴기 때문에 문제는 훨씬 풀기 쉬워지지만, 대신 벌금의 크기를 얼마로 정하느냐에 따라 얻어지는 결과가 달라집니다. 라그랑지완화법은 이 벌금 값을 잘 조정해가면서, 원래 어려운 문제의 답에 최대한 가까운 근사해와 함께 원래 문제의 답이 가질 수 있는 한계값을 함께 얻어내는 방법입니다.
왜 중요한가
대규모 최적화 문제 중에는 특정 제약조건 하나만 없으면 문제가 훨씬 단순한 구조로 쪼개지는 경우가 많습니다. 라그랑지완화법은 이런 구조적 특성을 활용해 문제를 다루기 쉬운 형태로 바꾸고, 동시에 최적해의 품질을 가늠할 수 있는 한계값을 제공하기 때문에 분지한정법과 결합해 대규모 정수계획법 문제를 푸는 데도 널리 쓰입니다.
논문에서는 이렇게 쓰입니다
여러 부서나 공정을 연결하는 까다로운 제약을 완화함으로써, 문제를 나누어 각각 따로 풀 수 있게 만들었다는 의미입니다.
완화된 문제에서 구한 한계값을 이용해 가능성 없는 탐색 경로를 더 빨리 걸러낼 수 있었다는 뜻입니다.
조금 더 깊게 보면
라그랑지완화법에서 얻어지는 해는 원래 문제의 최적해에 대한 하한 또는 상한을 제공하며, 이 한계값과 실제 최적값 사이의 차이를 라그랑지간극이라 부릅니다. 승수 값을 반복적으로 갱신하며 이 간극을 최대한 줄이는 과정을 라그랑지쌍대문제라 하고, 이때 서브그래디언트 기법과 같은 반복적 갱신 방법이 흔히 활용됩니다.
주의할 점
정수계획법과 같이 볼록성이 없는 문제에서는 라그랑지완화를 통해 얻은 해가 원래 문제에서 실행 가능하지 않을 수 있어, 별도의 복원 절차나 다른 기법과의 결합이 필요한 경우가 많습니다.