article

Routing Through Virtual Paths in Layered Telecommunication Networks

Authors:

Geir Dahl,

Alexander Martin,

Mechthild StoerAuthors Info & Claims

Operations Research, Volume 47, Issue 5

Pages 693 - 702

https://doi.org/10.1287/opre.47.5.693

Published: 01 May 1999 Publication History

Abstract

We study a network configuration problem in telecommunications where one wants to set up paths in a capacitated network to accommodate given point-to-point traffic demand. The problem is formulated as an integer linear programming model where 0-1 variables represent different paths. An associated integral polytope is studied, and different classes of facets are described. These results are used in a cutting plane algorithm. Computational results for some realistic problems are reported.

Cited By

View all

Benhamiche AMahjoub APerrot NUchoa E(2016)Unsplittable non-additive capacitated network design using set functions polyhedraComputers and Operations Research10.1016/j.cor.2015.08.00966:C(105-115)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1016/j.cor.2015.08.009
(2015)Formulations for the nonbifurcated hop-constrained multicommodity capacitated fixed-charge network design problemComputers and Operations Research10.1016/j.cor.2014.07.01353:C(1-8)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.1016/j.cor.2014.07.013
Mattia S(2012)Solving survivable two-layer network design problems by metric inequalitiesComputational Optimization and Applications10.1007/s10589-010-9364-051:2(809-834)Online publication date: 1-Mar-2012
https://dl.acm.org/doi/10.1007/s10589-010-9364-0
Show More Cited By

Routing Through Virtual Paths in Layered Telecommunication Networks
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
  2. Mathematical analysis
    1. Mathematical optimization
      1. Continuous optimization
      2. Mixed discrete-continuous optimization
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
    2. Mathematical optimization
      1. Mixed discrete-continuous optimization

Recommendations

The Circlet Inequalities: A New, Circulant-Based, Facet-Defining Inequality for the TSP
Facet-defining inequalities of the symmetric traveling salesman problem (TSP) polytope play a prominent role in both polyhedral TSP research and state-of-the-art TSP solvers. In this paper, we introduce a new class of facet-defining inequalities, the ...
A note on critical-set and lifted surrogate inequalities for cardinality-constrained linear programs

Generalize critical-set cuts for cardinality-constrained LP (CCLP) sets.Show how to derive lifted surrogate cuts for the CCLP polytope on-the-fly.Test the use of both cuts within branch-and-cut to solve CCLP.Analyze the results of the computational ...
On the cut polytope

The cut polytopePC(G) of a graphG=(V, E) is the convex hull of the incidence vectors of all edge sets of cuts ofG. We show some classes of facet-defining inequalities ofPC(G). We describe three methods with which new facet-defining inequalities ofPC(G) ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Operations Research Volume 47, Issue 5

May 1999

141 pages

ISSN:0030-364X

Issue’s Table of Contents

Publisher

INFORMS

Linthicum, MD, United States

Publication History

Published: 01 May 1999

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Benhamiche AMahjoub APerrot NUchoa E(2016)Unsplittable non-additive capacitated network design using set functions polyhedraComputers and Operations Research10.1016/j.cor.2015.08.00966:C(105-115)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1016/j.cor.2015.08.009
(2015)Formulations for the nonbifurcated hop-constrained multicommodity capacitated fixed-charge network design problemComputers and Operations Research10.1016/j.cor.2014.07.01353:C(1-8)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.1016/j.cor.2014.07.013
Mattia S(2012)Solving survivable two-layer network design problems by metric inequalitiesComputational Optimization and Applications10.1007/s10589-010-9364-051:2(809-834)Online publication date: 1-Mar-2012
https://dl.acm.org/doi/10.1007/s10589-010-9364-0
Borne SGabrel VMahjoub RTaktak R(2011)Multilayer survivable optical network designProceedings of the 5th international conference on Network optimization10.5555/2040817.2040840(170-175)Online publication date: 13-Jun-2011
https://dl.acm.org/doi/10.5555/2040817.2040840
Mattia S(2011)The two layer network design problemProceedings of the 5th international conference on Network optimization10.5555/2040817.2040836(145-149)Online publication date: 13-Jun-2011
https://dl.acm.org/doi/10.5555/2040817.2040836
Benhamiche AMahjoub RPerrot N(2011)On the design of optical OFDM-based networksProceedings of the 5th international conference on Network optimization10.5555/2040817.2040819(1-6)Online publication date: 13-Jun-2011
https://dl.acm.org/doi/10.5555/2040817.2040819
Marchand HMartin AWeismantel RWolsey L(2002)Cutting planes in integer and mixed integer programmingDiscrete Applied Mathematics10.1016/S0166-218X(01)00348-1123:1-3(397-446)Online publication date: 15-Nov-2002
https://dl.acm.org/doi/10.1016/S0166-218X%2801%2900348-1

Abstract

Cited By

Recommendations

The Circlet Inequalities: A New, Circulant-Based, Facet-Defining Inequality for the TSP

A note on critical-set and lifted surrogate inequalities for cardinality-constrained linear programs

On the cut polytope

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations