An optimization problem arising in the design of multiring systems

An optimization problem arising in the design of multiring systems

0.00 Avg rating0 Votes
Article ID: iaor20011484
Country: Netherlands
Volume: 124
Issue: 1
Start Page Number: 63
End Page Number: 76
Publication Date: Jul 2000
Journal: European Journal of Operational Research
Authors: ,
Keywords: programming: integer
Abstract:

We address a design problem that arises when a circular architecture is adopted to move resources in a system. In many of such architectures the demand directed from one node to another affects all the intermediate nodes, involving costs which increase both with the number of nodes and with the demand volume. We consider an application to network design and propose a model for designing a minimum cost hierarchical ring network. The problem is formalized as that of partitioning a set of nodes into p parts to be connected by rings, with the aim of minimizing the total capacity costs. We prove that the problem is NP-complete for p ≥ 2 and propose a guaranteed approximation algorithm for the case p = 2. We then propose a hybrid approach employing the approximation algorithm in combination with {0,1} LP. Experiments indicate the effectiveness of this approach in terms of computational resources and solution quality.

Reviews

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