Exploiting symmetries in mathematical programming via orbital independence. (English) Zbl 1467.90051

Dias, Gustavo; Liberti, Leo

Ann. Oper. Res. 298, No. 1-2, 149-182 (2021).

Summary: The presence of symmetries in the solution set of mathematical programs requires the exploration of symmetric subtrees during the execution of Branch-and-Bound type algorithms and yields increases in computation times. When some of the solution symmetries are evident in the formulation, it is possible to deal with them as a preprocessing step. In this sense, implementation-wise, one of the simplest approaches is to break symmetries by adjoining Symmetry-Breaking Constraints (SBCs) to the formulation. Designed to remove some of the symmetric global optima, these constraints are generated from each orbit of the action of the symmetries on the variable index set. Incompatible SBCs, however, might make all of the global optima infeasible. In this paper we introduce and test a new concept of Orbital Independence designed to address this issue. We provide necessary conditions for characterizing independent sets of orbits and also prove that such sets embed sufficient conditions to exploit symmetries from two or more distinct orbits concurrently. The theory developed is used to devise an algorithm that identifies the largest independent set of orbits of any mathematical program. Extensive numerical experiments are provided to validate the theoretical results.

MSC:

90C27	Combinatorial optimization
90C20	Quadratic programming

Keywords:

combinatorial optimization; symmetry breaking; group theory; quadratic programming

Software:

SCIP; nauty; CPLEX; Traces; AMPL; GAP

References:

[1]	Achterberg, T., SCIP: Solving constraint integer programs, Mathematical Programming Computation, 1, 1, 1-41 (2009) · Zbl 1171.90476
[2]	Berstel, J.; Boasson, L.; van Leeuwen, J., Context-free languages, Handbook of theoretical computer science, 59-102 (1990), Cambridge, MA, USA: MIT Press, Cambridge, MA, USA · Zbl 0900.68286
[3]	Bomze, I.; Budinich, M.; Pardalos, P.; Pelillo, M.; Du, DZ; Pardalos, P., The maximum clique problem, Handbook of combinatorial optimization: Supplement, 1-74 (1998), US, Boston, MA: Springer, US, Boston, MA · Zbl 1253.90188
[4]	Costa, A., Hansen, P., & Liberti, L. (2010). Formulation symmetries in circle packing. In R. Mahjoub (Ed.), ISCO 2010 proceedings, ENDM (Vol. 36, pp. 1303-1310). Amsterdam, Netherlands: Elsevier. · Zbl 1274.90500
[5]	Dias, G., & Liberti, L. (2015). Orbital independence in symmetric mathematical programs. In Z. Lu et al. (Eds.), COCOA 2015 proceedings, LNCS (Vol. 9486, pp. 467-480). Springer. · Zbl 1478.90096
[6]	Faenza, Y.; Kaibel, V., Extended formulations for packing and partitioning orbitopes, Mathematics of Operations Research, 34, 3, 686-697 (2009) · Zbl 1218.90124
[7]	Fischetti, M., & Liberti, L. (2012). Orbital shrinking. In R. Mahjoub, V. Markakis, I. Milis, & V. Paschos (Eds.), ISCO 2012 proceedings, LNCS (Vol. 7422, pp. 48-58). Berlin, Heidelberg: Springer. · Zbl 1370.90209
[8]	Fischetti, M.; Liberti, L.; Salvagnin, D.; Walsh, T., Orbital shrinking: Theory and applications, Discrete Applied Mathematics, 222, 109-123 (2017) · Zbl 1406.90081
[9]	Fourer, R.; Gay, D.; Kernighan, B., The AMPL book (2002), California, USA: Cengage Learning, California, USA
[10]	Friedman, E. (2007). Fundamental domains for integer programs with symmetries. In A. Dress, Y. Xu, B. Zhu (Eds.), COCOA 2007 proceedings, LNCS (Vol. 4616, pp. 146-153). Springer. · Zbl 1175.90296
[11]	Galli, S. (2004). Parsing AMPL internal format for linear and non-linear expressions. B.Sc. dissertation, DEI, Politecnico di Milano, Italy.
[12]	Gallo, G.; Hammer, P.; Simeone, B., Quadratic knapsack problems, 132-149 (1980), Berlin, Heidelberg: Springer, Berlin, Heidelberg · Zbl 0462.90068
[13]	IBM. (2014). ILOG CPLEX 12.6—user’s manual.
[14]	Kaibel, V.; Pfetsch, M., Packing and partitioning orbitopes, Mathematical Programming, 114, 1, 1-36 (2008) · Zbl 1171.90004
[15]	Liberti, L., Reformulations in mathematical programming: Definitions and systematics, RAIRO-RO, 43, 1, 55-86 (2009) · Zbl 1158.90390
[16]	Liberti, L., Reformulations in mathematical programming: Automatic symmetry detection and exploitation, Mathematical Programming A, 131, 273-304 (2012) · Zbl 1235.90103
[17]	Liberti, L.; Leyffer, S.; Lee, J., Symmetry in mathematical programming, Mixed integer nonlinear programming, IMA Series, 263-286 (2012), New York: Springer, New York · Zbl 1242.90236
[18]	Liberti, L., Cafieri, S., & Savourey, D. (2010). Reformulation optimization software engine. In K. Fukuda et al. (Eds.), Mathematical software, LNCS (Vol. 6327, pp. 303-314). Springer. · Zbl 1294.68160
[19]	Liberti, L.; Ostrowski, J., Stabilizer-based symmetry breaking constraints for mathematical programs, Journal of Global Optimization, 60, 183-194 (2014) · Zbl 1312.90077
[20]	Margot, F., Pruning by isomorphism in branch-and-cut, Mathematical Programming, 94, 71-90 (2002) · Zbl 1023.90088
[21]	Margot, F., Exploiting orbits in symmetric ILP, Mathematical Programming B, 98, 3-21 (2003) · Zbl 1082.90070
[22]	Margot, F.; Jünger, M., Symmetry in integer linear programming, 50 years of integer programming, 647-681 (2010), Berlin: Springer, Berlin
[23]	McKay, B., Practical graph isomorphism, Congressus Numerantium, 30, 45-87 (1981)
[24]	McKay, B.; Piperno, A., Practical graph isomorphism, II, Journal of Symbolic Computation, 60, 94-112 (2014) · Zbl 1394.05079
[25]	Ostrowski, J.; Linderoth, J.; Rossi, F.; Smriglio, S., Orbital branching, Mathematical Programming, 126, 1, 147-178 (2011) · Zbl 1206.90101
[26]	Pfetsch, M., & Rehn, T. (2015). A computational comparison of symmetry handling methods for mixed integer programs. Technical report 5209, optimization online. · Zbl 1411.90233
[27]	The GAP Group. (2014). GAP - Groups. Algorithms and programming. Version 4.7.4.