Single-commodity robust network design problem: Complexity, instances and heuristic solutions.

Álvarez-Miranda, Eduardo and Cacchiani, Valentina and Lodi, Andrea and Parriani, Tiziano and Schmidt, Daniel R. (2014) Single-commodity robust network design problem: Complexity, instances and heuristic solutions.
Published in: European Journal of Operational Research Vol. 238 (3). pp. 711-723. ISSN 0377-2217

Abstract

We study a single-commodity Robust Network Design problem (RND) in which an undirected graph with edge costs is given together with a discrete set of balance matrices, representing different supply/demand scenarios. In each scenario, a subset of the nodes is exchanging flow. The goal is to determine the minimum cost installation of capacities on the edges such that the flow exchange is feasible for every scenario. Previously conducted computational investigations on the problem motivated the study of the complexity of some special cases and we present complexity results on them, including hypercubes. In turn, these results lead to the definition of new instances (random graphs with {-1,0,1} balances) that are computationally hard for the natural flow formulation. These instances are then solved by means of a new heuristic algorithm for RND, which consists of three phases. In the first phase the graph representing the network is reduced by heuristically deleting a subset of the arcs, and a feasible solution is built. The second phase consists of a neighborhood search on the reduced graph based on a Mixed-Integer (Linear) Programming (MIP) flow model. Finally, the third phase applies a proximity search approach to further improve the solution, taking into account the original graph. The heuristic is tested on the new instances, and the comparison with the solutions obtained by Cplex on a natural flow formulation shows the effectiveness of the proposed method.


Actions:
Download: [img] PDF - Preprinted Version
Download (289kB) | Preview
Export as: [error in script]
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Article
Citations: [error in script] [error in script]
Subjects:
  • 90-XX Operations research, mathematical programming > 90Bxx Operations research and management science > 90B10 Network models, deterministic

  • 90-XX Operations research, mathematical programming > 90Bxx Operations research and management science > 90B18 Communication networks

  • 90-XX Operations research, mathematical programming > 90Bxx Operations research and management science > 90B25 Reliability, availability, maintenance, inspection

  • 90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C08 Special problems of linear programming (transportation, multi-index, etc.)

  • 90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C35 Programming involving graphs or networks

  • 90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C59 Approximation methods and heuristics

  • Additional Information: Also appeared as technical report OR-13-14 at the University of Bologna.
    Subjects: 90-XX Operations research, mathematical programming > 90Bxx Operations research and management science > 90B10 Network models, deterministic
    90-XX Operations research, mathematical programming > 90Bxx Operations research and management science > 90B18 Communication networks
    90-XX Operations research, mathematical programming > 90Bxx Operations research and management science > 90B25 Reliability, availability, maintenance, inspection
    90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C08 Special problems of linear programming (transportation, multi-index, etc.)
    90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C35 Programming involving graphs or networks
    90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C59 Approximation methods and heuristics
    Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger
    Depositing User: Daniel R. Schmidt
    Date Deposited: 03 Apr 2014 09:55
    Last Modified: 24 Nov 2015 09:59
    Deposit Information:
    ZAIK Number: [error in script]
    Depositing User: Daniel R. Schmidt
    Date Deposited: 03 Apr 2014 09:55
    Last Modified: 24 Nov 2015 09:59
    URI: http://e-archive.informatik.uni-koeln.de/id/eprint/772