New Valid Inequalities for the Optimal Communication Spanning Tree Problem

Yogesh Kumar Agarwal () and Prahalad Venkateshan ()
Additional contact information
Yogesh Kumar Agarwal: Decision Sciences, Indian Institute of Management, Prabandh Nagar, Lucknow 226013, India
Prahalad Venkateshan: Indian Institute of Management, Vastrapur, Ahmedabad 380015, India

INFORMS Journal on Computing, 2019, vol. 31, issue 2, 268-284

Abstract: The problem of designing a spanning tree on an underlying graph to minimize the flow costs of a given set of traffic demands is considered. Several new classes of valid inequalities are developed for the problem. Tests on 10-node problem instances show that the addition of these inequalities results in integer solutions for a significant majority of the instances without requiring any branching. In the remaining cases, root gaps of less than 1% from the optimal solutions are realized. For 30-node problem instances, the inequalities substantially reduce the number of nodes explored in the branch-and-bound tree, resulting in significantly reduced computational times. Optimal solutions are reported for problems with 30 nodes, 60 edges, fully dense traffic matrices, and Euclidean distance-based flow costs. Problems with such flow costs are well-known to be a very difficult class of problems to solve. Using the inequalities substantially improves the performance of a variable-fixing heuristic. Some polyhedral issues relating to the strength of these inequalities are also discussed.

Keywords: networks; optimization; integer programming; valid inequalities (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/ijoc.2018.0827 (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:31:y:2019:i:2:p:268-284

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 ().