The Path Restoration Version of the Spare Capacity Allocation Problem with Modularity Restrictions: Models, Algorithms, and an Empirical Analysis

This investigation presents a strategy to construct a compact mathematical model of the path-restoration version of the spare capacity allocation problem. The strategy uses a node-arc formulation and combines constraints whenever multiple working paths affected by an edge failure have identical orig...

Full description

Saved in:
Bibliographic Details
Published in:INFORMS journal on computing 2001-06, Vol.13 (3), p.181-190
Main Authors: Kennington, Jeffery L, Lewis, Mark W
Format: Article
Language:English
Subjects:
Algorithms
Applications
Communications
Communications networks
Integer
Linear programming
Mathematical models
Modularity
Networks-Graphs
Optimization
Programming
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This investigation presents a strategy to construct a compact mathematical model of the path-restoration version of the spare capacity allocation problem. The strategy uses a node-arc formulation and combines constraints whenever multiple working paths affected by an edge failure have identical origins or destinations. Another unique feature of this model is the inclusion of modularity restrictions corresponding to the discrete capacities of the equipment used in telecommunication networks. The new model can be solved using a classical branch-and-bound algorithm with a linear-programming relaxation. A preprocessing module is developed, which generates a set of cuts that strengthens this linear programming relaxation. The overhead associated with the cuts is offset by the improved bounds produced. A new branch-and-bound algorithm is developed that exploits the modularity restrictions. In an extensive empirical analysis, a software implementation of this algorithm was found to be substantially faster than CPLEX 6.5.3. For a test suite of 50 problems, each having 50 nodes and 200 demands from a uniform distribution with a small variance, our new software obtained solutions guaranteed to be within 4% of optimality in five minutes of CPU time on a DEC AlphaStation.
ISSN:1091-9856
1526-5528
1091-9856
DOI:10.1287/ijoc.13.3.181.12629