A branch and cut algorithm for minimum spanning trees under conflict constraints. (English) Zbl 1308.90033
Summary: We study approaches for the exact solution of the \(\mathsf{NP}\)-hard minimum spanning tree problem under conflict constraints. Given a graph \(G(V,E)\) and a set \(C \subset E \times E\) of conflicting edge pairs, the problem consists of finding a conflict-free minimum spanning tree, i.e. feasible solutions are allowed to include at most one of the edges from each pair in \(C\). The problem was introduced recently in the literature, with several results on its complexity and approximability. Some formulations and both exact and heuristic algorithms were also discussed, but computational results indicate considerably large duality gaps and a lack of optimality certificates for benchmark instances. In this paper, we build on the representation of conflict constraints using an auxiliary conflict graph \(\hat{G}(E,C)\), where stable sets correspond to conflict-free subsets of \(E\). We introduce a general preprocessing method and a branch and cut algorithm using an IP formulation with exponentially sized classes of valid inequalities for both the spanning tree and the stable set polytopes. Encouraging computational results indicate that the dual bounds of our approach are significantly stronger than those previously available, already in the initial LP relaxation, and we are able to provide new feasibility and optimality certificates.
MSC:
| 90B18 | Communication networks in operations research |
Software:
LEMONReferences:
| [1] | Achterberg, T.: Conflict analysis in mixed integer programming. Discret. Optim. 4(1), 4-20 (2007). doi:10.1016/j.disopt.2006.10.006 · Zbl 1169.90414 · doi:10.1016/j.disopt.2006.10.006 |
| [2] | Atamtürk, A., Nemhauser, G.L., Savelsbergh, M.W.: Conflict graphs in solving integer programming problems. Eur. J. Oper. Res. 121(1), 40-55 (2000). doi:10.1016/S0377-2217(99)00015-6 · Zbl 0959.90034 · doi:10.1016/S0377-2217(99)00015-6 |
| [3] | Balas, E.: Disjunctive programming. In: 50 Years of Integer Programming 1958-2008, pp. 283-340. Springer, Berlin Heidelberg (2010) · Zbl 1187.90005 |
| [4] | Balas, E., Yu, C.: Finding a maximum clique in an arbitrary graph. SIAM J. Comput. 15(4), 1054-1068 (1986). doi:10.1137/0215075 · Zbl 0604.05024 · doi:10.1137/0215075 |
| [5] | Darmann, A., Pferschy, U., Schauer, J.: Determining a minimum spanning tree with disjunctive constraints. In: Rossi, F., Tsoukias, A. (eds) Algorithmic Decision Theory, Lecture Notes in Computer Science, vol. 5783. Springer, Berlin Heidelberg, pp. 414-423 (2009). doi:10.1007/978-3-642-04428-1_36. · Zbl 1260.68171 |
| [6] | Darmann, A., Pferschy, U., Schauer, J., Woeginger, G.J.: Paths, trees and matchings under disjunctive constraints. Discret. Appl. Math. 159(16), 1726-1735 (2011). doi:10.1016/j.dam.2010.12.016 · Zbl 1228.05186 · doi:10.1016/j.dam.2010.12.016 |
| [7] | Dezső, B., Jüttner, A., Kovács, P.: LEMON—an open source C++ graph template library. Electron. Notes Theor. Comput. Sci. 264(5), 23-45 (2011). doi:10.1016/j.entcs.2011.06.003 · doi:10.1016/j.entcs.2011.06.003 |
| [8] | Edmonds, J.: Matroids and the greedy algorithm. Math. Program. 1, 127-136 (1971). doi:10.1007/BF01584082 · Zbl 0253.90027 · doi:10.1007/BF01584082 |
| [9] | Gerards, A., Schrijver, A.: Matrices with the Edmonds-Johnson property. Combinatorica 6(4), 365-379 (1986). doi:10.1007/BF02579262 · Zbl 0641.05039 |
| [10] | Goldberg, A.V., Tarjan, R.E.: A new approach to the maximum-flow problem. J. ACM 35(4), 921-940 (1988). doi:10.1145/48014.61051 · Zbl 0661.90031 · doi:10.1145/48014.61051 |
| [11] | Grötschel, M., Lovász, L., Schrijver, A.: Geometric algorithms and combinatorial optimization. Springer, Berlin Heidelberg (1988) · Zbl 0634.05001 · doi:10.1007/978-3-642-97881-4 |
| [12] | Magnanti, T.L., Wolsey, L.A.: Chapter 9 Optimal trees. In: Ball, M.O., Magnanti, T.L., Monma, C.L., Nemhauser, G.L. (eds) Network Models, Handbooks in Operations Research and Management Science, vol. 7. Elsevier, Amsterdam, pp. 503-615 (1995) · Zbl 0839.90135 |
| [13] | Öncan, T., Zhang, R., Punnen, A.P.: The minimum cost perfect matching problem with conflict pair constraints. Comput. Oper. Res. 40(4), 920-930 (2013). doi:10.1016/j.cor.2012.10.022 · Zbl 1349.90822 · doi:10.1016/j.cor.2012.10.022 |
| [14] | Padberg, M.: On the facial structure of set packing polyhedra. Math. Program. 5(1), 199-215 (1973). doi:10.1007/BF01580121 · Zbl 0272.90041 · doi:10.1007/BF01580121 |
| [15] | Padberg, M.W.: Covering, packing and knapsack problems. In: Hammer, P.L., Johnson, E.L., Korte, B.H. (eds.) Annals of Discrete Mathematics, vol. 4. Elsevier, Amsterdam, pp 265-287 (1979) · Zbl 0407.90056 |
| [16] | Pferschy, U., Schauer, J.: The knapsack problem with conflict graphs. J. Graph Algortihms Appl. 13(2), 233-249 (2009). doi:10.7155/jgaa.00186 · Zbl 1194.68175 · doi:10.7155/jgaa.00186 |
| [17] | Pferschy, U., Schauer, J.: The maximum flow problem with disjunctive constraints. J. Comb. Optim. 26, 109-119 (2011). doi:10.1007/s10878-011-9438-7 · Zbl 1275.90120 |
| [18] | Punnen, A.P., Zhang, R.: Quadratic bottleneck problems. Naval Res. Logist. (NRL) 58(2), 153-164 (2011). doi:10.1002/nav.20446 · Zbl 1216.90074 · doi:10.1002/nav.20446 |
| [19] | Rebennack, S., Reinelt, G., Pardalos, P.M.: A tutorial on branch and cut algorithms for the maximum stable set problem. Int. Trans. Oper. Res. 19(1-2), 161-199 (2012). doi:10.1111/j.1475-3995.2011.00805.x · Zbl 1270.90092 · doi:10.1111/j.1475-3995.2011.00805.x |
| [20] | Rossi, F., Smriglio, S.: A branch-and-cut algorithm for the maximum cardinality stable set problem. Oper. Res. Lett. 28(2), 63-74 (2001). doi:10.1016/S0167-6377(00)00060-2 · Zbl 1054.90098 · doi:10.1016/S0167-6377(00)00060-2 |
| [21] | Sadykov, R., Vanderbeck, F.: Bin packing with conflicts: a generic branch-and-price algorithm. INFORMS J. Comput. (2012). doi:10.1287/ijoc.1120.0499 · Zbl 1270.90092 |
| [22] | Tomita, E., Tanaka, A., Takahashi, H.: The worst-case time complexity for generating all maximal cliques and computational experiments. Theor. Comput. Sci. 363(1), 28-42 (2006). doi:10.1016/j.tcs.2006.06.015 · Zbl 1153.68398 · doi:10.1016/j.tcs.2006.06.015 |
| [23] | Zhang, R., Kabadi, S.N., Punnen, A.P.: The minimum spanning tree problem with conflict constraints and its variations. Discret. Optim. 8(2), 191-205 (2011). doi:10.1016/j.disopt.2010.08.001 · Zbl 1241.90167 · doi:10.1016/j.disopt.2010.08.001 |
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.
