×

zbMATH — the first resource for mathematics

Reformulations in mathematical programming: automatic symmetry detection and exploitation. (English) Zbl 1235.90103
Summary: If a mathematical program has many symmetric optima, solving it via branch-and-bound techniques often yields search trees of disproportionate sizes; thus, finding and exploiting symmetries is an important task. We propose a method for automatically finding the formulation group of any given mixed-integer nonlinear program, and for reformulating the problem by means of static symmetry breaking constraints. The reformulated problem – which is likely to have fewer symmetric optima – can then be solved via standard branch-and-bound codes such as CPLEX (for linear programs) and Couenne (for nonlinear programs). Our computational results include formulation group tables for the MIPLib3, MIPLib2003, GlobalLib and MINLPLib instance libraries and solution tables for some instances in the aforementioned libraries.

MSC:
90C11 Mixed integer programming
90C26 Nonconvex programming, global optimization
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Al-Khayyal F.A., Sherali H.D.: On finitely terminating branch-and-bound algorithms for some global optimization problems. SIAM J. Optim. 10(4), 1049–1057 (2000) · Zbl 0994.65068
[2] Babai L.: Automorphism groups, isomorphism, reconstruction. In: Graham, R., Grötschel, M., Lovász, L. (eds) Handbook of Combinatorics, vol. 2, pp. 1447–1540. MIT Press, Cambridge (1996)
[3] Bauer C., Frink A., Kreckel R.: Introduction to the GiNaC framework for symbolic computation within the C++ programming language. J. Symb. Comput. 33(1), 1–12 (2002) · Zbl 1017.68163
[4] Belotti P., Lee J., Liberti L., Margot F., Wächter A.: Branching and bounds tightening techniques for non-convex MINLP. Optim. Methods Softw. 24(4), 597–634 (2009) · Zbl 1179.90237
[5] Berthold, T., Pfetsch, M.: Detecting orbitopal symmetries. In: Fleischmann, B., Borgwardt, K.-H., Klein, R., Tuma, A. (eds.) Operations Research Proceedings 2008, pp. 433–438. Springer, Berlin (2009) · Zbl 1209.90260
[6] Bixby, R., Ceria, S., McZeal, C., Savelsbergh, M.: An updated mixed integer programming library: Miplib 3. Technical Report TR98-03, Rice University (1998)
[7] Booth, K., Colbourn, C.: Problems polynomially equivalent to graph isomorphism. Technical Report CS-77-04, University of Waterloo (1979)
[8] Boulle M.: Compact mathematical formulation for graph partitioning. Optim. Eng. 5, 315–333 (2004) · Zbl 1151.90522
[9] Bruglieri M., Liberti L.: Optimal running and planning of a biomass-based energy production process. Energy Policy 36, 2430–2438 (2008)
[10] Bussieck, M.: Globallib–a collection of nonlinear programming problems. http://www.gamsworld.org/global/globallib.htm (2004)
[11] Bussieck, M., Drud, A., Meeraus, A.: MINLPLib–A collection of test models for mixed-integer nonlinear programming. Inf. J. Comput. 15(1) (2003) · Zbl 1238.90104
[12] Butler, G.: Fundamental Algorithms for Permutation Groups, LNCS, vol. 559. Springer (1991) · Zbl 0785.20001
[13] Cohen, D., Jeavons, P., Jefferson, C., Petrie, K., Smith, B.: Symmetry definitions for constraint satisfaction problems. In: van Beek, P. (ed.) CP, LNCS, vol. 3709. Springer (2005) · Zbl 1153.68454
[14] Cohen J.S.: Computer Algebra and Symbolic Computation: Mathematical Methods. AK Peters, Natick, MA (2000)
[15] Cohen J.S.: Computer Algebra and Symbolic Computation: Elementary Algorithms. AK Peters, Natick, MA (2002) · Zbl 1011.68180
[16] Faenza Y., Kaibel V.: Extended formulations for packing and partitioning orbitopes. Math. Oper. Res. 34(3), 686–697 (2009) · Zbl 1218.90124
[17] Fischetti, M., Salvagnin, D.: A local dominance procedure for mixed-integer linear programming. Technical report, ARRIVAL project (2007)
[18] Fourer R., Gay D.: The AMPL Book. Duxbury Press, Pacific Grove (2002)
[19] Friedman, E.J.: Fundamental domains for integer programs with symmetries. In: Dress, A., Xu, Y., Zhu, B. (eds.) COCOA Proceedings, LNCS, vol. 4616, pp. 146–153. Springer (2007) · Zbl 1175.90296
[20] The GAP Group: GAP–Groups, Algorithms, and Programming, Version 4.4.10 (2007)
[21] Hall M.: Theory of Groups. 2nd edn. Chelsea Publishing Company, New York (1976) · Zbl 0354.20001
[22] ILOG (2008) ILOG CPLEX 11.0 User’s Manual. ILOG S.A., Gentilly, France
[23] Kaibel V., Pfetsch M.: Packing and partitioning orbitopes. Math. Program. 114(1), 1–36 (2008) · Zbl 1171.90004
[24] Laundy R., Perregaard M., Tavares G., Tipi H., Vazacopoulos A.: Solving hard mixed-integer programming problems with Xpress-MP: a MIPLIB 2003 case study. Inf. J. Comput. 21(2), 304–313 (2009) · Zbl 1243.90149
[25] Lee J., Margot F.: On a binary-encoded ILP coloring formulation. Inf. J. Comput. 19(3), 406–415 (2007) · Zbl 1241.90087
[26] Leyffer, S.: MacMINLP–AMPL collection of mixed integer nonlinear programs. http://www.mcs.anl.gov/\(\sim\)leyffer/macminlp/ (2000)
[27] Liberti, L.: Framework for symbolic computation in C++ using n-ary trees. Technical report, CPSE, Imperial College London (2001)
[28] Liberti L.: Writing global optimization software. In: Liberti, L., Maculan, N. (eds) Global Opti- mization: from Theory to Implementation, pp. 211–262. Springer, Berlin (2006) · Zbl 1100.90004
[29] Liberti L.: Automatic generation of symmetry-breaking constraints. In: Yang, B., Du, D.-Z., Wang, C.A. (eds) COCOA Proceedings, LNCS, vol. 5165, pp. 328–338. Springer, Berlin (2008) · Zbl 1168.90566
[30] Liberti, L.: Reformulations in mathematical programming: symmetry. Technical Report 2165, Optimization Online (2008) · Zbl 1235.90103
[31] Liberti L.: Reformulations in mathematical programming: definitions and systematics. RAIRO-RO 43(1), 55–86 (2009) · Zbl 1158.90390
[32] Liberti L., Cafieri S., Tarissan F.: Reformulations in mathematical programming: a computational approach. In: Abraham, A., Hassanien, A.-E., Siarry, P., Engelbrecht, A. (eds) Foundations of Computational Intelligence, vol. 3, number 203 in Studies in Computational Intelligence, pp. 153–234. Springer, Berlin (2009)
[33] Liberti L., Mladenović N., Nannicini G.: A good recipe for solving MINLPs. In: Maniezzo, V., Stützle, T., Voß, S. (eds) Hybridizing Metaheuristics and Mathematical Programming, volume 10 of Annals of Information Systems, pp. 231–244. Springer, New York (2009)
[34] Margot F.: Pruning by isomorphism in branch-and-cut. Math. Program. 94, 71–90 (2002) · Zbl 1023.90088
[35] Margot F.: Exploiting orbits in symmetric ILP. Math. Program. B 98, 3–21 (2003) · Zbl 1082.90070
[36] Margot F.: Small covering designs by branch-and-cut. Math. Program. B 94, 207–220 (2003) · Zbl 1030.90144
[37] Margot F.: Symmetric ILP: coloring and small integers. Discret. Optim. 4, 40–62 (2007) · Zbl 1169.90411
[38] Margot F.: Symmetry in integer linear programming. In: Jünger, M., Liebling, T., Naddef, D., Nemhauser, G., Pulleyblank, W., Reinelt, G., Rinaldi, G., Wolsey, L. (eds) 50 Years of Integer Programming, pp. 647–681. Springer, Berlin (2010)
[39] Martin, A., Achterberg, T., Koch, T.: Miplib 2003. Technical Report 05-28, ZIB (2005)
[40] McKay B.: Practical graph isomorphism. Congr. Numerantium 30, 45–87 (1981) · Zbl 0521.05061
[41] McKay B.: Nauty User’s Guide (Version 2.4). Computer Science Department, Australian National University, Canberra (2007)
[42] Neumaier A.: Complete search in continuous global optimization and constraint satisfaction. Acta Numer. 13, 271–369 (2004) · Zbl 1113.90124
[43] Ostrowski, J., Linderoth, J., Rossi, F., Smriglio, S.: Orbital branching. In: Fischetti, M., Williamson, D.P. (eds.) IPCO, LNCS, vol. 4513, pp. 104–118. Springer (2007) · Zbl 1136.90411
[44] Ostrowski, J., Linderoth, J., Rossi, F., Smriglio, S.: Constraint orbital branching. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds.) IPCO, LNCS, vol. 5035, pp. 225–239. Springer (2008) · Zbl 1143.90361
[45] Ramani A., Markov I.: Automatically exploiting symmetries in constraint programming. In: Faltings, B., Petcu, A., Fages, F., Rossi, F. (eds) Constraint Solving and Constraint Logic Programming, LNAI, vol. 3419, pp. 98–112. Springer, Berlin (2005) · Zbl 1078.68760
[46] Rosen, K.H. (eds): Handbook of Discrete and Combinatorial Mathematics. CRC Press, New York (2000) · Zbl 1044.00002
[47] Sahinidis, N.V., Tawarmalani, M.: BARON 7.2.5: Global Optimization of Mixed-Integer Nonlinear Programs, User’s Manual (2005) · Zbl 1099.90047
[48] Schichl H., Neumaier A.: Interval analysis on directed acyclic graphs for global optimization. J. Glob. Optim. 33(4), 541–562 (2005) · Zbl 1094.65061
[49] Seress A.: Permutation Group Algorithms. Cambridge University Press, Cambridge (2003) · Zbl 1028.20002
[50] Sherali H., Smith C.: Improving discrete model representations via symmetry considerations. Manag. Sci. 47(10), 1396–1407 (2001) · Zbl 1232.90309
[51] Uehara R., Toda S., Nagoya T.: Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs. Discret. Appl. Math. 145, 479–482 (2005) · Zbl 1056.05099
[52] Vallentin, F.: Symmetry in semidefinite programs. Technical Report 1702, Optimization Online (2007) · Zbl 1165.90017
[53] Wielandt H.: Finite Permutation Groups. Academic Press, New York (1964) · Zbl 0138.02501
[54] Wolsey L.A.: Integer Programming. Wiley, New York (1998)
[55] Zhu W.: Unsolvability of some optimization problems. Appl. Math. Comput. 174, 921–926 (2006) · Zbl 1098.65071
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.