Optimization Online


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

Dieter Weninger(dieter.weninger***at***fau.de)
Laurence A. Wolsey(laurence.wolsey***at***uclouvain.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society