Casting Light on the Hidden Bilevel Combinatorial Structure of the Capacitated Vertex Separator Problem

References

• Albert R, Jeong H, Barabási AL (2000) Error and attack tolerance of complex networks. Nature 406(6794):378–382.Crossref, Google Scholar
• Baggio A, Carvalho M, Lodi A, Tramontani A (2021) Multilevel approaches for the critical node problem. Oper. Res. 69(2):1–23.Link, Google Scholar
• Baïou M, Barahona F (2016) Stackelberg bipartite vertex cover and the preflow algorithm. Algorithmica 74(3):1174–1183.Crossref, Google Scholar
• Bastubbe M, Lübbecke M (2020) A branch-and-price algorithm for capacitated hypergraph vertex separation. Math. Programming Comput. 12(1):39–68.Crossref, Google Scholar
• Bergner M, Caprara A, Ceselli A, Furini F, Lübbecke M, Malaguti E, Traversi E (2015) Automatic Dantzig–Wolfe reformulation of mixed integer programs. Math. Programming 149(1):391–424.Crossref, Google Scholar
• Borndörfer R, Ferreira C, Martin A (1998) Decomposing matrices into blocks. SIAM J. Optim. 9(1):236–269.Crossref, Google Scholar
• Borrero JS, Prokopyev OA, Sauré D (2019) Sequential interdiction with incomplete information and learning. Oper. Res. 67(1):72–89.Link, Google Scholar
• Brotcorne L, Labbé M, Marcotte P, Savard G (2008) Joint design and pricing on a network. Oper. Res. 56(5):1104–1115.Link, Google Scholar
• Brown G, Carlyle M, Salmerón J, Wood K (2006) Defending critical infrastructure. INFORMS J. Appl. Anal. 36(6):530–544.Link, Google Scholar
• Bui TN, Jones C (1992) Finding good approximate vertex and edge partitions is np-hard. Inform. Process. Lett. 42(3):153–159.Crossref, Google Scholar
• Casorrán C, Fortz B, Labbé M, Ordóñez F (2019) A study of general and security Stackelberg game formulations. Eur. J. Oper. Res. 278(3):855–868.Crossref, Google Scholar
• Cormican KJ, Morton DP, Wood RK (1998) Stochastic network interdiction. Oper. Res. 46(2):184–197.Link, Google Scholar
• Cornaz D, Furini F, Lacroix M, Malaguti E, Mahjoub AR, Martin S (2019) The vertex k-cut problem. Discrete Optim. 31:8–28.Crossref, Google Scholar
• de Souza C, Balas E (2005a) The vertex separator problem: a polyhedral investigation. Math. Programming 103(3):583–608.Crossref, Google Scholar
• de Souza C, Balas E (2005b) The vertex separator problem: algorithms and computations. Math. Programming 103(3):609–631.Crossref, Google Scholar
• Delorme M, Iori M, Martello S (2016) Bin packing and cutting stock problems: Mathematical models and exact algorithms. Eur. J. Oper. Res. 255(1):1–20.Crossref, Google Scholar
• Dempe S, Zemkoho AB (2013) The bilevel programming problem: reformulations, constraint qualifications and optimality conditions. Math. Programming 138(1-2):447–473.Crossref, Google Scholar
• Djidjev HN (2000) Partitioning planar graphs with vertex costs: Algorithms and applications. Algorithmica 28(1):51–75.Crossref, Google Scholar
• Dolan ED, Moré JJ (2002) Benchmarking optimization software with performance profiles. Math. Programming 91(2):201–213.Crossref, Google Scholar
• Fischetti M, Ljubić I, Monaci M, Sinnl M (2017) A new general-purpose algorithm for mixed-integer bilevel linear programs. Oper. Res. 65(60):1615–1637.Link, Google Scholar
• Fischetti M, Ljubić I, Monaci M, Sinnl M (2019) Interdiction games under monotonicity. INFORMS J. Comput. 31(2):390–410.Link, Google Scholar
• Fischetti M, Leitner M, Ljubić I, Luipersbeck M, Monaci M, Resch M, Salvagnin D, Sinnl M (2017) Thinning out Steiner trees: a node-based model for uniform edge costs. Math. Programming Comput. 9:203–229.Crossref, Google Scholar
• Fukuyama J (2006) NP-completeness of the planar separator problems. J. Graph Algorithms Appl. 10(2):317–328.Crossref, Google Scholar
• Furini F, Ljubić I, Malaguti E, Paronuzzi P (2019) On integer and bilevel formulations for the k-vertex cut problem. Math. Programming Comput. 12:133–164.Crossref, Google Scholar
• Garg N, Saran H, Vazirani V (1999) Finding separator cuts in planar graphs within twice the optimal. SIAM J. Comput. 29(1):159–179.Crossref, Google Scholar
• Gay DM (1985) Electronic mail distribution of linear programming test problems. Math. Programming Soc. COAL Newsletter 13:10–12.Google Scholar
• Heath M, Ng E, Peyton B (1991) Parallel algorithms for sparse linear systems. SIAM Rev. 33(3):420–460.Crossref, Google Scholar
• Hopcroft J, Tarjan R (1973) Algorithm 447: efficient algorithms for graph manipulation. Comm. ACM 16(6):372–378.Crossref, Google Scholar
• Johnson DS, Trick MA (1996) Cliques, coloring, and satisfiability. Second DIMACS Implementation Challenge, October 11-13, 1993, vol. 26, American Mathematical Socety (Rutgers University, Piscataway, NJ).Google Scholar
• Kleinert T, Labbé M, Plein F, Schmidt M (2020) Technical note–There’s no free lunch: On the hardness of choosing a correct Big-M in bilevel optimization. Oper. Res. 68(6):1716–1721.Link, Google Scholar
• Koch T, Achterberg T, Andersen E, Bastert O, Berthold T, Bixby RE, Danna E, et al.. (2011) Miplib 2010. Math. Programming Comput. 3(2):103–163.Crossref, Google Scholar
• Leitner M, Ljubić I, Luipersbeck M, Sinnl M (2018) A dual ascent-based branch-and-bound framework for the prize-collecting steiner tree and related problems. INFORMS J. Comput. 30(2):402–420.Link, Google Scholar
• Lipton R, Tarjan R (1979) A separator theorem for planar graphs. SIAM J. Appl. Math. 36(2):177–189.Crossref, Google Scholar
• Lipton RJ, Tarjan RE (1977) Applications of a planar separator theorem. 18th Annual Sympos. Foundations Comput. Sci. (SFCS 1977 Providence, RI), 162–170.Google Scholar
• Lozano L, Smith J (2017) A value-function-based exact approach for the bilevel mixed integer programming problem. Oper. Res. 65(3):768–786.Link, Google Scholar
• Shen S, Smith JC (2012) Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs. Networks 60(2):103–119.Crossref, Google Scholar
• Shen S, Smith JC, Goli R (2012) Exact interdiction models and algorithms for disconnecting networks via node deletions. Discrete Optim. 9(3):172–188.Crossref, Google Scholar
• Tahernejad S, Ralphs T, DeNegre S (2020) A Branch-and-Cut Algorithm for Mixed Integer Bilevel Linear Optimization Problems and Its Implementation. Math. Program. Comput. 12:529–568.Google Scholar
• Tao Z, Zhongqian F, Binghong W (2006) Epidemic dynamics on complex networks. Progress Natl. Sci. 16(5):452–457.Crossref, Google Scholar
• Watts DJ, Strogatz SH (1998) Collective dynamics of “small-world” networks. Nature 393(6684):440–442.Crossref, Google Scholar
• Wood RK (2011) Bilevel network interdiction models: Formulations and solutions. Cochran JJ, Cox LA, Keskinocak P, Kharoufeh JP, Smith JC, eds. Wiley Encyclopedia of Operations Research and Management Science.Google Scholar
• Zachary WW (1977) An information flow model for conflict and fission in small groups. J. Anthropol. Res. 33(4):452–473.Crossref, Google Scholar