A cutting plane algorithm for the Capacitated Connected Facility Location Problem

A cutting plane algorithm for the Capacitated Connected Facility Location Problem

0.00 Avg rating0 Votes
Article ID: iaor20133981
Volume: 55
Issue: 3
Start Page Number: 647
End Page Number: 674
Publication Date: Jul 2013
Journal: Computational Optimization and Applications
Authors: , ,
Keywords: location, networks, design
Abstract:

We consider a network design problem that arises in the cost‐optimal design of last mile telecommunication networks. It extends the Connected Facility Location problem by introducing capacities on the facilities and links of the networks. It combines aspects of the capacitated network design problem and the single‐source capacitated facility location problem. We refer to it as the Capacitated Connected Facility Location Problem. We develop a basic integer programming model based on single‐commodity flows. Based on valid inequalities for the capacitated network design problem and the single‐source capacitated facility location problem we derive several (new) classes of valid inequalities for the Capacitated Connected Facility Location Problem including cut set inequalities, cover inequalities and combinations thereof. We use them in a branch‐and‐cut framework and show their applicability and efficacy on a set of real‐world instances.

Reviews

Required fields are marked *. Your email address will not be published.