Orbital Conflict: Cutting Planes for Symmetric Integer Programs

References

• Achterberg T, Wunderling R (2013) Mixed Integer Programming: Analyzing 12 Years of Progress. Facets of Combinatorial Optimization (Springer, Berlin, Heidelberg), 449–482.Google Scholar
• Achterberg T, Bixby R, Gu Z, Rothberg E, Weninger D (2020) Presolve reductions in mixed integer programming. INFORMS J. Comput. 32(2).Google Scholar
• Atamtürk A, Nemhauser G, Savelsbergh M (2000) Conflict graphs in solving integer programming problems. Eur. J. Oper. Res. 121(1):40–55.Google Scholar
• Correa RC, Donne DD, Koch I, Marenco J (2018) General cut-generating procedures for the stable set polytope. Discrete Appl. Math. 245:28–41.Google Scholar
• Debroni J, Eblen JD, Langston MA, Myrvold W, Shor P, Weerapurage D (2011) A complete resolution of the Keller maximum clique problem. Proc. 22nd Annual ACM-SIAM Symp. Discrete Algorithms (SODA) (Society for Industrial and Applied Mathematics, Philadelphia), 129–135.Google Scholar
• Dezső B, Jüttner A, Kovács P (2011) LEMON – An open source C++ graph template library. Electronic Notes Theoret. Comput. Sci. 264(5):23–45.Google Scholar
• Feo T, Resende M (1989) A probabilistic heuristic for a computationally difficult set covering problem. Oper. Res. Lett. 8(2):67–71.Google Scholar
• Fulkerson D, Nemhauser G, Trotter L (1974) Two computationally difficult set covering problems that arise in computing the 1-width of incidence matrices of Steiner triple systems. Balinski ML, ed. Approaches to Integer Programming (Springer, Berlin, Heidelberg), 72–81.Google Scholar
• Giandomenico M, Rossi F, Smriglio S (2013) Strong lift-and-project cutting planes for the stable set problem. Math. Programming 141:165–192.Google Scholar
• Graham R, Sloane N (1985) On the covering radius of codes. IEEE Trans. Inform. Theory 31(3):385–401.Google Scholar
• Grötschel M, Lovász L, Schrijver A (1988) Stable sets in graphs. Geometric Algorithms and Combinatorial Optimization (Springer, Berlin, Heidelberg), 272–303.Google Scholar
• Johnson DJ, Trick M (1996) Cliques, Coloring and Satisfiability: Second DIMACS Implementation Challenge, October 11–13, 1993 (American Mathematical Society, Providence, RI).Google Scholar
• Karmarkar N, Resende M, Ramakrishnan K (1991) An interior point algorithm to solve computationally difficult set covering problems. Math. Programming 52(1–3):597–618.Google Scholar
• Letchford A, Rossi F, Smriglio S (2020) The stable set problem: Clique and nodal inequalities revisited. Comput. Oper. Res. 123:105024.Google Scholar
• Linderoth J, Margot F, Thain G (2009) Improving bounds on the football pool problem via symmetry reduction and high-throughput computing. INFORMS J. Comput. 21:445–457.Link, Google Scholar
• Margot F (2002) Pruning by isomorphism in branch-and-cut. Math. Programming 94(1):71–90.Google Scholar
• Margot F (2003) Exploiting orbits in symmetric ILP. Math. Programming 98(1):3–21.Google Scholar
• Margot F (2007) Symmetric ILP: Coloring and small integers. Mixed integer programming. Discrete Optim. 4(1):40–62.Google Scholar
• Margot F (2009) Symmetry in integer linear programming. Jünger M, Liebling T, Naddef D, Nemhauser GL, Pulleyblank WR, Reinelt G, Rinaldi G, Wolsey LA, eds. 50 Years of Integer Programming 1958–2008 (Springer, Berlin, Heidelberg), 647–686.Google Scholar
• Marzi F, Rossi F, Smriglio S (2019) Computational study of separation algorithms for clique inequalities. Soft Comput. 23(9):3013–3027.Google Scholar
• McKay B, Piperno A (2014) Practical graph isomorphism, II. J. Symbolic Comput. 60:94–112.Google Scholar
• Nemhauser G, Savelsbergh M, Sigismondi G (1994) MINTO, a mixed INTeger optimizer. Oper. Res. Lett. 15(1):47–58.Google Scholar
• Núñez-Ares J, Goos P (2019) Enumeration and multicriteria selection of orthogonal minimally aliased response surface designs. Technometrics 62(1):21–32.Google Scholar
• Ostrowski J (2009) Symmetry in integer programming. Unpublished PhD thesis, Lehigh University.Google Scholar
• Ostrowski J, Linderoth J, Rossi F, Smriglio S (2008) Constraint orbital branching. Lodi A, Panconesi A, Rinaldi G, eds. Proc. 13th Conf. Integer Programming Combin. Optim. (IPCO) (Springer, Berlin, Heidelberg), 225–239.Google Scholar
• Ostrowski J, Linderoth J, Rossi F, Smriglio S (2011a) Orbital branching. Math. Programming 126(1):147–178.Google Scholar
• Ostrowski J, Linderoth J, Rossi F, Smriglio S (2011b) Solving large Steiner triple covering problems. Oper. Res. Lett. 39(2):127–131.Google Scholar
• Padberg M (1973) On the facial structure of set packing polyhedra. Math. Programming 5(1):199–215.Google Scholar
• Pfetsch ME, Rehn T (2019) A computational comparison of symmetry handling methods for mixed integer programs. Math. Programming Comput. 11(1):37–93.Google Scholar
• Puget JF (2005) Automatic detection of variable and value symmetries. Beek P, ed. Lecture Notes in Computer Science, Principles and Practice of Constraint Programming, vol. 3709 (Springer, Berlin, Heidelberg), 475–489.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.Google Scholar
• Rehn T, Schürmann A (2010) C++ tools for exploiting polyhedral symmetries. Fukuda K, Hoeven J van der, Joswig M, Takayama N, eds. Proc. 3rd Internat. Congress Math. Software (Springer, Berlin, Heidelberg), 295–298.Google Scholar
• Rotman J (1994) An Introduction to the Theory of Groups, 4th ed. (Springer, New York).Google Scholar
• Salvagnin D (2005) A dominance procedure for integer programming. Unpublished master’s thesis, University of Padova, Padova, Italy.Google Scholar
• Schönheim J (1964) On coverings. Pacific J. Math. 14(4):1405–1411.Google Scholar
• Thain D, Tannenbaum T, Livny M (2005) Distributed computing in practice: The Condor experience. Concurrency Comput. 17(2–4):323–356.Google Scholar