Strong formulations for network design problems with connectivity requirements. (English) Zbl 1067.68104
Summary: The network design problem with connectivity requirements (NDC) includes as special cases a wide variety of celebrated combinatorial optimization problems including the minimum spanning tree, Steiner tree, and survivable network design problems. We develop strong formulations for two versions of the edge-connectivity NDC problem: unitary problems requiring connected network designs, and nonunitary problems permitting nonconnected networks as solutions. We (1) present a new directed formulation for the unitary NDC problem that is stronger than a natural undirected formulation; (2) project out two classes of valid inequalities – partition inequalities, and combinatorial design inequalities – that generalize known classes of valid inequalities for the Steiner tree problem to the unitary NDC problem; and (3) show how to strengthen and direct nonunitary problems. Our results provide a unifying framework for strengthening formulations for NDC problems, and demonstrate the power of flow-based formulations for network design problems with connectivity requirements.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68M10 | Network design and communication in computer systems |
Keywords:
strong formulations; survivability; Steiner forest problem; directed formulations; valid inequalities; projectionReferences:
| [1] | Baïou, SIAM J Discrete Math 10 pp 505– (1997) |
| [2] | Balakrishnan, Networks 43 pp 10– (2004) |
| [3] | Balas, Networks 13 pp 495– (1983) |
| [4] | Benders, Numer Math 4 pp 238– (1962) |
| [5] | Dida Biha, Oper Res Lett 19 pp 71– (1996) |
| [6] | Boyd, SIAM J Discrete Math 6 pp 612– (1993) |
| [7] | Cardwell, IEEE J Selected Areas Commun 7 pp 1188– (1989) |
| [8] | Chopra, Oper Res Lett 8 pp 25– (1989) |
| [9] | Chopra, SIAM J Discrete Math 5 pp 321– (1992) |
| [10] | Chopra, Math Program 64 pp 209– (1994) |
| [11] | Chopra, Math Program 64 pp 231– (1994) |
| [12] | ? Connectivity augmentation problems in network design,? Mathematical Programming: State of the Art 1994, and (Editors), The University of Michigan, East Lansing, MI, 1994. |
| [13] | Fredman, J ACM 34 pp 596– (1987) |
| [14] | Analysis of linear programming relaxations for a class of connectivity problems, PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, 1990 (also Working paper OR 233-90, Operations Research Center, M.I.T.). |
| [15] | Goemans, Math Program 63 pp 157– (1994) |
| [16] | Goemans, Math Program 69 pp 335– (1995) |
| [17] | Goemans, Networks 23 pp 19– (1993) |
| [18] | Gomory, SIAM J Appl Math 9 pp 551– (1961) |
| [19] | Grötschel, SIAM J Discrete Math 3 pp 502– (1990) |
| [20] | Grötschel, Oper Res 40 pp 309– (1992) |
| [21] | Grötschel, SIAM J Optimizat 2 pp 474– (1992) |
| [22] | and ? Design of survivable networks,? Handbooks in Operations Research and Management Science, and (Editors), North-Holland, Amsterdam, 1995, pp. 617-672. |
| [23] | Grötschel, Oper Res 43 pp 1012– (1995) |
| [24] | Jain, Combinatorica 21 pp 39– (2001) |
| [25] | and A dual-ascent algorithm for low-connectivity network design, Technical report, Robert H. Smith School of Business, University of Maryland, College Park, MD, 2004. |
| [26] | and Optimal trees, Handbooks in Operations Research and Management Science, and (Editors), North-Holland, Amsterdam, 1995, pp. 503-615. |
| [27] | Mahjoub, Math Program 64 pp 199– (1994) |
| [28] | Menger, Fundam Math 10 pp 96– (1927) |
| [29] | Nash-Williams, Can J Math 12 pp 555– (1960) · Zbl 0096.38002 · doi:10.4153/CJM-1960-049-6 |
| [30] | Formulations and algorithms for network design problems with connectivity requirements, PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, 1995. |
| [31] | and ? Network connectivity,? Annotated Bibliographies in Combinatorial Optimization, and (Editors), John Wiley & Sons, New York, 1997, pp. 335-354. |
| [32] | ? Design of survivable networks,? Lecture Notes in Mathematics, Springer-Verlag, Berlin, 1992. · Zbl 0766.90063 |
| [33] | Winter, J Algorithms 7 pp 549– (1986) |
| [34] | Winter, Networks 17 pp 129– (1987) |
| [35] | Wong, Math Program 28 pp 271– (1984) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
