Please use this identifier to cite or link to this item: http://hdl.handle.net/11718/23878
Full metadata record
DC FieldValueLanguage
dc.contributor.authorAgarwal, Y.
dc.contributor.authorVenkateshan, Prahalad
dc.date.accessioned2021-05-24T06:50:13Z
dc.date.available2021-05-24T06:50:13Z
dc.date.issued2019
dc.identifier.citationAgarwal, Y., & Venkateshan, P. (2019). A new valid inequalities for optional communication spanning tree problem. Informs Journal on Computing, 31(2), 268-284. doi:https://doi.org/10.1287/ijoc.2018.0827en_US
dc.identifier.issn10919856 (Print) 15265528 (Online)
dc.identifier.urihttp://hdl.handle.net/11718/23878
dc.description.abstractThe 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.en_US
dc.language.isoenen_US
dc.publisherInforms Journal on Computingen_US
dc.subjectNetworksen_US
dc.subjectOptimizationen_US
dc.subjectInteger programmingen_US
dc.subjectValid inequalitiesen_US
dc.titleA new valid inequalities for optional communication spanning tree problemen_US
dc.typeArticleen_US
Appears in Collections:Journal Articles

Files in This Item:
There are no files associated with this item.


Items in IIMA Institutional Repository are protected by copyright, with all rights reserved, unless otherwise indicated.