- Two Benders-type Branch-and-Cut Algorithms for Capacitated Facility Location with Single-Sourcing Dieter Weninger(dieter.weningerfau.de) Laurence A. Wolsey(laurence.wolseyuclouvain.be) Abstract: 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. Keywords: Integer programming, Benders' algorithm, Branch-and-cut, Mixed integer subproblems, Facilities planning and design Category 1: Integer Programming ((Mixed) Integer Linear Programming ) Category 2: Combinatorial Optimization (Branch and Cut Algorithms ) Category 3: Applications -- Science and Engineering (Facility Planning and Design ) Citation: Friedrich-Alexander Universität Erlangen-Nürnberg, 04/2022 Download: [PDF]Entry Submitted: 04/05/2022Entry Accepted: 04/05/2022Entry Last Modified: 04/05/2022Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.