  


Two Benderstype BranchandCut Algorithms for Capacitated Facility Location with SingleSourcing
Dieter Weninger(dieter.weningerfau.de) Abstract: We consider mixed 01 integer programs of the form $\min\{cx+hy: Ax+By \geq b, x \in \{0,1\}^n,y \in \{0,1\}^p \times \R^{Np}_+\}$ in which the subproblem arising when $x$ is fixed has special structure. One such example is the capacitated facility location problem with singlesourcing 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 singlesourcing variables taking fractional values is typically small. We present two branchandcut 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, Branchandcut, 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: FriedrichAlexander Universität ErlangenNürnberg, 04/2022 Download: [PDF] Entry Submitted: 04/05/2022 Modify/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  