(A) branch and price algorithm for the robust capacitated facility location problem with single sourcing

Abstract

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.