Valid Inequalities for the Telecommunications Network Design Problem

Yogesh K. Agarwal ()
Additional contact information
Yogesh K. Agarwal: Jaipuria Institute of Management

Chapter Chapter 5 in Optimization Essentials, 2024, pp 175-194 from Springer

Abstract: Abstract This chapter addresses the problem of designing a backbone telecommunications network using transmission facilities (e.g., optical fibers) of a fixed capacity. Given a set of nodes, traffic demands among the nodes, and the costs of installing the facilities between the nodes, we need to design a minimum-cost network that can carry all the traffic demands. The problem can be modeled as a mixed integer program using a multicommodity network flow formulation. The chapter briefly introduces the concept of valid inequalities and reviews integer rounding and Chvátal-Gomory methods generating valid inequalities. It then identified the p-partition-based substructures for p = 2, 3, and 4, from which valid inequalities can be generated by applying the Chvatál-Gomory method. Several families of such inequalities are derived, and the effect of adding these inequalities is demonstrated through simple examples. A simple but effective shrinking heuristic is developed to find the p-partitions which are likely to result in violated valid inequalities. Some computational results are presented to demonstrate the effectiveness of the proposed approach.

Date: 2024
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:spr:isochp:978-981-99-5491-9_5

Ordering information: This item can be ordered from
http://www.springer.com/9789819954919

DOI: 10.1007/978-981-99-5491-9_5

Access Statistics for this chapter

More chapters in International Series in Operations Research & Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().