Network Design with Service Requirements: Scaling-up the Size of Solvable Problems

Naga V. C. Gudapati (), Enrico Malaguti () and Michele Monaci ()
Additional contact information
Naga V. C. Gudapati: Dipartimento di Ingegneria dell’Energia Elettrica e dell’Informazione “Guglielmo Marconi”, Università di Bologna, 40136 Bologna, Italy
Enrico Malaguti: Dipartimento di Ingegneria dell’Energia Elettrica e dell’Informazione “Guglielmo Marconi”, Università di Bologna, 40136 Bologna, Italy
Michele Monaci: Dipartimento di Ingegneria dell’Energia Elettrica e dell’Informazione “Guglielmo Marconi”, Università di Bologna, 40136 Bologna, Italy

INFORMS Journal on Computing, 2022, vol. 34, issue 5, 2571-2582

Abstract: Network design, a cornerstone of mathematical optimization, is about defining the main characteristics of a network satisfying requirements on connectivity, capacity, and level-of-service. It finds applications in logistics and transportation, telecommunications, data sharing, energy distribution, and distributed computing. In multicommodity network design, one is required to design a network minimizing the installation cost of its arcs and the operational cost to serve a set of point-to-point connections. The definition of this prototypical problem was recently enriched by additional constraints imposing that each origin-destination of a connection is served by a single path satisfying one or more level-of-service requirements, thus defining the Network Design with Service Requirements . These constraints are crucial, for example, in telecommunications and computer networks to ensure reliable and low-latency communication. In this paper we provide a new formulation for the problem, where variables are associated with paths satisfying the end-to-end service requirements. We present a fast algorithm for enumerating all the exponentially many feasible paths, and when this is not viable, we provide a column generation scheme that is embedded into a branch-and-cut-and-price algorithm. Extensive computational experiments on a large set of instances show that our approach can move a step further in the solution of the network design with service requirements compared with the current state-of-the-art.

Keywords: network design; multicommodity flow; service requirements; branch-and-cut-and-price algorithm; budget-constrained shortest path; labeling algorithm (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.1200 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:34:y:2022:i:5:p:2571-2582

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().