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 \geq b, x \in \{0,1\}^n,y \in \{0,1\}^p \times \R^{N-p}_+\}$ in which the subproblem arising when $x$ is fixed 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,\eta)$-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.

Citation

Friedrich-Alexander Universität Erlangen-Nürnberg, 04/2022

Article

Download

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