×

zbMATH — the first resource for mathematics

Orbital branching. (English) Zbl 1206.90101
Summary: We introduce orbital branching, an effective branching method for integer programs containing a great deal of symmetry. The method is based on computing groups of variables that are equivalent with respect to the symmetry remaining in the problem after branching, including symmetry that is not present at the root node. These groups of equivalent variables, called orbits, are used to create a valid partitioning of the feasible region that significantly reduces the effects of symmetry while still allowing a flexible branching rule. We also show how to exploit the symmetries present in the problem to fix variables throughout the branch-and-bound tree. Orbital branching can easily be incorporated into standard integer programming software. Through an empirical study on a test suite of symmetric integer programs, the question as to the most effective orbit on which to base the branching decision is investigated. The resulting method is shown to be quite competitive with a similar method known as isomorphism pruning and significantly better than a state-of-the-art commercial solver on symmetric integer programs.

MSC:
90C10 Integer programming
Software:
MINTO; nauty
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Achterberg T., Koch T., Martin A.: Branching rules revisited. Oper. Res. Lett. 33, 42–54 (2004) · Zbl 1076.90037 · doi:10.1016/j.orl.2004.04.002
[2] Barnhart C., Johnson E.L., Nemhauser G.L., Savelsbergh M.W.P., Vance P.H.: Branch and price: column generation for solving huge integer programs. Oper. Res. 46, 316–329 (1998) · Zbl 0979.90092 · doi:10.1287/opre.46.3.316
[3] Cameron P.J.: Permutation Groups. London Mathematical Society, London (1999) · Zbl 0922.20003
[4] Dolan E., Moré J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201–213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263
[5] Foggia, P., Sansone, C., Vento, M.: A preformance comparison of five algorithms for graph isomorphism. In: Proc. 3rd IAPR-TC15 Workshop Graph-Based Representations in Pattern Recognition, pp. 188–199 (2001)
[6] Fulkerson D.R., Nemhauser G.L., Trotter L.E.: Two computationally difficult set covering problems that arise in computing the 1-width of incidence matrices of Steiner triples. Math. Program. Study 2, 72–81 (1973) · Zbl 0353.90060
[7] Grove L.C., Benson C.T.: Finite Reflection Groups. Springer, Heidelberg (1985) · Zbl 0579.20045
[8] Hamalainen H., Honkala I., Litsyn S., Östergård P.: Football pools–a game for mathematicians. Am. Math. Monthly 102, 579–588 (1995) · Zbl 0841.90147 · doi:10.2307/2974552
[9] Holm S., Sørensen M.: The optimal graph partitioning problem: solution method based on reducing symmetric nature and combinatorial cuts. OR Spectrum 15, 1–8 (1993) · Zbl 0784.90096
[10] Kaibel, V., Peinhardt, M., Pfetsch, M.E.: Orbitopal fixing. In: IPCO 2007: The Twelfth Conference on Integer Programming and Combinatorial Optimization, pp. 74–88. Springer, Heidelberg (2007) · Zbl 1136.90407
[11] Kaibel V., Pfetsch M.E.: Packing and partitioning orbitopes. Math. Program. 114, 1–36 (2008) · Zbl 1171.90004 · doi:10.1007/s10107-006-0081-5
[12] Linderoth J.T., Savelsbergh M.W.P.: A computational study of search strategies in mixed integer programming. INFORMS J. Comput. 11, 173–187 (1999) · Zbl 1040.90535 · doi:10.1287/ijoc.11.2.173
[13] Litsyn S.: An updated table of the best binary codes known. In: Pless, V.S., Huffman, W.C. (eds) Handbook of Coding Theory volume 1, pp. 463–498. Elsevier, Amsterdam (1998) · Zbl 0968.94019
[14] Macambira, E.M., Maculan, N., de Souza, C.C.: Reducing symmetry of the SONET ring assignment problem using hierarchical inequalities. Technical Report ES-636/04, Programa de Engenharia de Sistemas e Computação, Universidade Federal do Rio de Janeiro (2004)
[15] Margot F.: Pruning by isomorphism in branch-and-cut. Math. Program. 94, 71–90 (2002) · Zbl 1023.90088 · doi:10.1007/s10107-002-0358-2
[16] Margot F.: Exploiting orbits in symmetric ILP. Math. Program. Ser. B 98, 3–21 (2003) · Zbl 1082.90070 · doi:10.1007/s10107-003-0394-6
[17] Margot F.: Small covering designs by branch-and-cut. Math. Program. 94, 207–220 (2003) · Zbl 1030.90144 · doi:10.1007/s10107-002-0316-z
[18] McKay B.D.: Nauty User’s Guide (Version 1.5). Australian National University, Canberra (2002)
[19] Méndez-Díaz I., Zabala P.: A branch-and-cut algorithm for graph coloring. Discrete Appl. Math. 154(5), 826–847 (2006) · Zbl 1120.90034 · doi:10.1016/j.dam.2005.05.022
[20] Mills, W.H., Mullin, R.C.: Coverings and packings. In: Contemporary Design Theory: A Collection of Surveys, pp. 371–399. Wiley, New York (1992) · Zbl 0783.05038
[21] Nemhauser G.L., Savelsbergh M.W.P., Sigismondi G.C.: MINTO, a Mixed INTeger Optimizer. Oper. Res. Lett. 15, 47–58 (1994) · Zbl 0806.90095 · doi:10.1016/0167-6377(94)90013-2
[22] Ostrowski, J., Linderoth, J., Rossi, F., Smriglio, S.: Orbital branching. In: IPCO 2007: The Twelfth Conference on Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, vol. 4517, pp. 104–118. Springer, Heidelberg (2007) · Zbl 1136.90411
[23] Ostrowski, J., Linderoth, J., Rossi, F., Smriglio, S.: Constraint orbital branching. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds.) IPCO 2008: The Thirteenth Conference on Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, vol. 5035, pp. 225–239 (2008) · Zbl 1143.90361
[24] Rotman J.J.: An Introduction to the Theory of Groups, 4th edn. Springer, Heidelberg (1994)
[25] Sewell E.C.: A branch-and-bound algorithm for the stability number of a sparse graph. INFORMS J. Comput. 10, 438–447 (1998) · doi:10.1287/ijoc.10.4.438
[26] Sherali H.D., Smith J.C.: Improving zero-one model representations via symmetry considerations. Manage. Sci. 47(10), 1396–1407 (2001) · Zbl 1232.90309 · doi:10.1287/mnsc.47.10.1396.10265
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.