The capacitated facility location problem with single-sourcing constraints is a well-studied problem. Here we consider robust version of the problem with uncertainty in customers’ demands. Dantzig-Wolfe decomposition is used to isolate the robustness of a solution from the whole problem. Robustness is dealt in subproblems independently of the master problem. We propose a branch and price algorithm, in which a new column can be obtained by solving some ordinary binary knapsack problems. Computational experiments show that our proposed algorithm performs better than the solution of the direct reformulation of the problem as a mixed integer program. We also evaluate the robustness of the obtained solutions using simulation.
용량 제약과 단일 할당 조건이 있는 설비 입지 선정 문제는 최적화 분야의 여러 논문에서 다루어진 문제이다. 이 논문에서는 고객의 수요가 불확실하다는 조건 하의 문제를 강건 최적화 방법으로 해결하고자 한다. 분지한계법에 열 생성 기법을 적용한 분지평가법은 Dantzig-Wolfe 분해로 유도한 강화된 문제를 해결하는 방법이다. Dantzig-Wolfe 분해를 적용함으로서 원래의 모델에서 수요 불확실성 조건식을 부 문제로 분리하였으며, 이것은 이진 배낭 문제를 여러 번 풂으로써 해결할 수 있다. 우리는 직접적인 방법으로 설계한 혼합 정수계획법 모델의 풀이 시간과 분지평가법으로 푼 새로운 모델의 풀이 시간을 비교하였다. 또한, 문제의 해가 적은 비용으로 유효 해의 비율을 높이는지도 확인하였다.
