Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming

References

• Amaldi E, Coniglio S, Gualandi S (2010) Improving cutting plane generation with 0-1 inequalities by bi-criteria separation. Festa P, ed. Proc. 9th Internat. Sympos. Experiment. Algorithms (Springer, Berlin), 266–275.Google Scholar
• Amaldi E, Coniglio S, Gualandi S (2014) Coordinated cutting plane generation via multi-objective separation. Math. Programming 143(1–2):87–110.Crossref, Google Scholar
• Balasundaram B, Butenko S, Hicks I (2011) Clique relaxations in social network analysis: The maximum k-plex problem. Oper. Res. 59(1):133–142.Link, Google Scholar
• Benson SJ, Ye Y, Zhang X (2000) Solving large-scale sparse semidefinite programs for combinatorial optimization. SIAM J. Optim. 10(2):443–461.Crossref, Google Scholar
• Bolusani S, Coniglio S, Ralphs TK, Tahernejad S (2020) A unified framework for multistage and multilevel mixed integer linear optimization. Dempe S, Zemkoho A, eds., Bilevel Optimization: Advances and Next Challenges (Springer, Cham, Switzerland), 513–560.Crossref, Google Scholar
• Bourjolly JM, Laporte G, Mercure H (1997) A combinatorial column generation algorithm for the maximum stable set problem. Oper. Res. Lett. 20(1):21–29.Crossref, Google Scholar
• Butenko S, Wilhelm W (2006) Clique-detection models in computational biochemistry and genomics. Eur. J. Oper. Res. 173(1):1–17.Crossref, Google Scholar
• Campêlo M, Cornuéjols G (2009) Stable sets, corner polyhedra and the Chvátal closure. Oper. Res. Lett. 37(6):375–378.Crossref, Google Scholar
• Cheng E, Cunningham W (1997) Wheel inequalities for stable set polytopes. Math. Programming 77(2):389–421.Crossref, Google Scholar
• Cheng E, de Vries S (2002) Antiweb-wheel inequalities and their separation problems over the stable set polytopes. Math. Programming 92(1):153–175.Crossref, Google Scholar
• Chvátal V (1970) The smallest triangle-free 4-chromatic 4-regular graph. J. Combin. Theory 9(1):93–94.Crossref, Google Scholar
• Chvátal V (1975) On certain polytopes associated with graphs. J. Combin. Theory Ser. B. 18(2):138–154.Crossref, Google Scholar
• Coniglio S, Gualandi S (2017) On the separation of topology-free rank inequalities for the max stable set problem. Iliopoulos CS, Pissis SP, Puglisi SJ, Raman R, eds. Proc. 16th Internat. Sympos. Experiment. Algorithms (Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany), 29:1–29:13.Google Scholar
• Coniglio S, Tieves M (2015) On the generation of cutting planes which maximize the bound improvement. Bampis E, ed. Proc. 14th Internat. Sympos. Experiment. Algorithms (Springer, Berlin), 97–109.Google Scholar
• Coniglio S, Furini F, San Segundo P (2021) A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts. Eur. J. Oper. Res. 289(2):435–455.Crossref, Google Scholar
• Corrêa R, Donne DD, Koch I, Marenco J (2018) General cut-generating procedures for the stable set polytope. Discrete Appl. Math. 245:28–41.Crossref, Google Scholar
• Dukanovic I, Rendl F (2007) Semidefinite programming relaxations for graph coloring and maximal clique problems. Math. Programming 109(2–3):345–365.Crossref, Google Scholar
• Furini F, Ljubic I, Martin S, San Segundo P (2019) The maximum clique interdiction game. Eur. J. Oper. Res. 277(1):112–127.Crossref, Google Scholar
• Giandomenico M, Rossi F, Smriglio S (2013) Strong lift and project cutting planes for the stable set problem. Math. Programming 141(1–2):165–192.Crossref, Google Scholar
• Giandomenico M, Letchford A, Rossi F, Smriglio S (2015) Ellipsoidal relaxations of the stable set problem: Theory and algorithms. SIAM J. Optim. 25(3):1944–1963.Crossref, Google Scholar
• Gouveia L, Martins P (2015) Solving the maximum edge-weight clique problem in sparse graphs with compact formulations. EURO J. Comput. Optim. 3(1):1–30.Crossref, Google Scholar
• Grötschel M, Lovász L, Schrijver A (1981) The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2):169–197.Crossref, Google Scholar
• Grötschel M, Lovász L, Schrijver A (1988) Geometric Algorithms and Combinatorial Optimization (Springer, Berlin).Google Scholar
• Gruber G, Rendl F (2003) Computational experience with stable set relaxations. SIAM J. Optim. 13(4):1014–1028.Crossref, Google Scholar
• Hastad J (1999) Clique is hard to approximate within n1−ε. Acta Math. 182:105–142.Crossref, Google Scholar
• Held S, Cook W, Sewell E (2012) Maximum-weight stable sets and safe lower bounds for graph coloring. Math. Programming Comput. 4(4):363–381.Crossref, Google Scholar
• Hoffman KL, Padberg M (1993) Solving airline crew scheduling problems by branch-and-cut. Management Sci. 39(6):657–682.Link, Google Scholar
• Hosseinian S, Fontes D, Butenko S (2018) A nonconvex quadratic optimization approach to the maximum edge weight clique problem. J. Global Optim. 72(2):219–240.Crossref, Google Scholar
• Hosseinian S, Fontes D, Butenko S, Buongiorno MN, Fornari M, Curtarolo S (2017) The maximum edge weight clique problem: Formulations and solution approaches. Butenko S, Pardalos PM, Shylo V, eds. Optimization Methods and Applications (Springer, Cham, Switzerland), 217–237.Crossref, Google Scholar
• Johnson D, Trick M, eds. (1996) Cliques, Coloring, and Satisfiability: The Second DIMACS Challenge (American Mathematical Society, Providence, RI).Crossref, Google Scholar
• Karp R (1972) Reducibility among combinatorial problems. Miller RE, Thatcher JW, Bohlinger JD, eds., Proc. Sympos. Complexity Comput. Computations (Springer, Boston).Google Scholar
• Letchford A, Rossi F, Smriglio S (2020) The stable set problem: Clique and nodal inequalities revisited. Comput. Oper. Res. 123:105024.Crossref, Google Scholar
• Lodi A, Ralphs T, Woeginger G (2014) Bilevel programming and the separation problem. Math. Programming 146(1–2):437–458.Crossref, Google Scholar
• Lovász L (1979) On the Shannon capacity of a graph. IEEE Trans. Inform. Theory 25(1):1–7.Crossref, Google Scholar
• Mannino C, Sassano A (1996) Edge projection and the maximum cardinality stable set problem. Johnson DS, Trick MA, eds. Cliques, Coloring, and Satisfiability (American Mathematical Society, Providence, RI), 205–219.Crossref, Google Scholar
• Marzi F, Rossi F, Smriglio S (2019) Computational study of separation algorithms for clique inequalities. Soft Comput. 23(9):3013–3027.Crossref, Google Scholar
• Maslov E, Batsyn M, Pardalos P (2014) Speeding up branch and bound algorithms for solving the maximum clique problem. J. Global Optim. 59(1):1–21.Crossref, Google Scholar
• Nemhauser G, Sigismondi G (1992) A strong cutting plane/branch-and-bound algorithm for node packing. J. Oper. Res. Soc. 43(5):443–457.Crossref, Google Scholar
• Östergård P (2002) A fast algorithm for the maximum clique problem. Discrete Appl. Math. 120(1):197–207.Crossref, Google Scholar
• Padberg M (1973) On the facial structure of set packing polyhedra. Math. Programming 5(1):199–215.Crossref, Google Scholar
• Pardalos P, Xue J (1994) The maximum clique problem. J. Global Optim. 4(3):301–328.Crossref, Google Scholar
• Prosser P (2012) Exact algorithms for maximum clique: A computational study. Algorithms 5(4):545–587.Crossref, Google Scholar
• Rebennack S, Reinelt G, Pardalos P (2012) A tutorial on branch and cut algorithms for the maximum stable set problem. Internat. Trans. Oper. Res. 19(1–2):161–199.Crossref, Google Scholar
• Rebennack S, Oswald M, Theis D, Seitz H, Reinelt G, Pardalos P (2011) A branch and cut solver for the maximum stable set problem. J. Combin. Optim. 21(4):434–457.Crossref, Google Scholar
• Rossi F, Smriglio S (2001) A branch and cut algorithm for the maximum cardinality stable set problem. Oper. Res. Lett. 28(2):63–74.Crossref, Google Scholar
• Rutenburg V (1994) Propositional truth maintenance systems: Classification and complexity analysis. Ann. Math. Artificial Intelligence 10(3):207–231.Crossref, Google Scholar
• San Segundo P, Artieda J (2015) A novel clique formulation for the visual feature matching problem. Appl. Intelligence 43(2):325–342.Crossref, Google Scholar
• San Segundo P, Lopez A, Pardalos P (2016) A new exact maximum clique algorithm for large and massive sparse graphs. Comput. Oper. Res. 66:81–94.Crossref, Google Scholar
• San Segundo P, Rodríguez-Losada D, Jiménez A (2011) An exact bit-parallel algorithm for the maximum clique problem. Comput. Oper. Res. 38(2):571–581.Crossref, Google Scholar
• San Segundo P, Coniglio S, Furini F, Ljubić I (2019) A new branch-and-bound algorithm for the maximum edge-weighted clique problem. Eur. J. Oper. Res. 278(1):76–90.Crossref, Google Scholar
• Sewell EC (1998) A branch and bound algorithm for the stability number of a sparse graph. INFORMS J. Comput. 10(4):438–447.Link, Google Scholar
• Shimizu S, Yamaguchi K, Masuda S (2019) A branch-and-bound based exact algorithm for the maximum edge-weight clique problem. Lee R, ed. Comput. Sci./Intelligence Appl. Inform.: CSII2018 (Springer, Cham, Switzerland), 27–47.Google Scholar
• Tomita E, Kameda T (2007) An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments. J. Global Optim. 37(1):95–111.Crossref, Google Scholar
• Trotter LJ (1975) A class of facet producing graphs for vertex packing polyhedra. Discrete Math. 12(4):373–388.Crossref, Google Scholar
• Wu Q, Hao JK (2015) A review on algorithms for maximum clique problems. Eur. J. Oper. Res. 242(3):693–709.Crossref, Google Scholar
• Wu Q, Hao JK (2016) A clique-based exact method for optimal winner determination in combinatorial auctions. Inform. Sci. 334:103–121.Crossref, Google Scholar
• Zuckerman D (2006) Linear degree extractors and the inapproximability of max clique and chromatic number. Proc. 38th Annual ACM Sympos. Theory Comput. (ACM, New York), 681–690.Google Scholar