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/2022
Entry Accepted: 04/05/2022
Entry Last Modified: 04/05/2022

Modify/Update this entry