Two Benders-type Branch-and-Cut Algorithms for Capacitated Facility Location with Single-Sourcing

We consider mixed 0-1 integer programs of the form min { cx + hy : Ax + By ≥ b, x ∈ { 0 , 1 } n , y ∈ { 0 , 1 } p × R N − p + } in which the subproblem arising when x is ﬁxed has special structure. One such example is the capacitated facility location problem with single-sourcing in which the linear programming relaxation of the subproblem is a transportation problem and, although the number N of y -variables is large, the number of single-sourcing variables taking fractional values is typically small. We present two branch-and-cut algorithms that solve linear programs while maintaining a separation between a Benders’ Master problem in ( x, η ) variables and a subproblem in y -variables. One involves branching in ( x, y ) -space and the other requires branching in x -space plus valid inequalities in ( x, y ) -space lifted from cuts in the y -space.