Skip to main content
SpringerLink
Log in

Exploiting orbits in symmetric ILP

  • Published:
Mathematical Programming Submit manuscript

Abstract.

This paper describes components of a branch-and-cut algorithm for solving integer linear programs having a large symmetry group. It describes an isomorphism pruning algorithm and variable setting procedures using orbits of the symmetry group. Pruning and orbit computations are performed by backtracking procedures using a Schreier-Sims table for representing the symmetry group. Applications to hard set covering problems, generation of covering designs and error correcting codes are given.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Avis, D.: A Note on Some Computationally Difficult Set Covering Problems. Mathematical Programming 8, 138–145 (1980)

    Google Scholar 

  2. Butler, G.: Computing in Permutation and Matrix Groups II: Backtrack Algorithm. Mathematics of Computation 39, 671–680 (1982)

  3. Butler, G.: Fundamental Algorithms for Permutation Groups. Lecture Notes in Computer Science 559, Springer, 1991

  4. Butler, G., Cannon, J.J.: Computing in Permutation and Matrix Groups I: Normal Closure, Commutator Subgroups, Series. Mathematics of Computation 39, 663–670 (1982)

  5. Butler, G., Lam, W.H.: A General Backtrack Algorithm for the Isomorphism Problem of Combinatorial Objects. Journal of Symbolic Computation 1, 363–381 (1985)

    Google Scholar 

  6. Conway, J.H., Sloane, N.J.A.: Sphere Packings, Lattices and Groups. Springer, 1993

  7. Feo, T.A., Resende, G.C.: A Probabilistic Heuristic for a Computationally Difficult Set Covering Problem. Operations Research Letters 8, 67–71 (1989)

    Google Scholar 

  8. 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 Triple Systems. Mathematical Programming Study 2, 72–81 (1974)

    Google Scholar 

  9. Hall, M.: Combinatorial Theory. Wiley, 1986

  10. Jünger, M., Naddef, D., eds.: Computational Combinatorial Optimization. Lecture Notes in Computer Science 2241, Springer, 2001

  11. ILOG CPLEX 7.1 User's Manual, 2001

  12. Elf, M., Gutwenger, C., Jünger, M., Rinaldi, G.: Branch-and-Cut Algorithms for Combinatorial Optimization and their Implementation in ABACUS. In: [10], 155–222

  13. Etzion, T., Wei, V., Zhang, Z.: Bounds on the Sizes of Constant Weight Covering Codes. Designs, Codes and Cryptography 5, 217–239 (1995)

    Google Scholar 

  14. Hoffman, C.M.: Group-Theoretic Algorithms and Graph Isomorphism. Lecture Notes in Computer Science 136, Springer, 1982

  15. Jünger, M., Thienel, S.: Introduction to ABACUS – A Branch-And-Cut System. Operations Research Letters 22, 83–95 (1998)

  16. Kreher, D.L., Stinson, D.R.: Combinatorial Algorithms, Generation, Enumeration, and Search, CRC Press, 1999

  17. Leon, J.S.: On an Algorithm for Finding a Base and a Strong Generating Set for a Group Given by Generating Permutations. Mathematics of Computation 35, 941–974 (1980)

    Google Scholar 

  18. Leon, J.S.: Computing Automorphism Groups of Combinatorial Objects. In: Computational Group Theory, Atkinson M.D. (ed.), Academic Press 1984, pp. 321–335

  19. Luks, E.: Permutation Groups and Polynomial-Time Computation. In: DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 11 1993, Groups and Computation, L. Finkelsein, W. Kantor, eds., 139–175

  20. Mannino, C., Sassano, A.: Solving Hard Set Covering Problems. Operations Research Letters 18, 1–5 (1995)

  21. http://www.ms.uky.edu/∼fmargot/recpub.html

  22. Margot, F.: Small Covering Designs by Branch-and-Cut. Research report 2000-27, Department of Mathematics, University of Kentucky. To appear in Mathematical Programming.

  23. Margot, F.: Pruning by Isomorphism in Branch-and-Cut. Research report 2001-08, Department of Mathematics, University of Kentucky.

  24. Lytsin, S.: An Updated Table of the Best Binary Codes Known. In: Handbook of Coding Theory, V.S. Pless, W.C. Huffmann, eds., North-Holland, Elsevier, 1998

  25. Martin, A.: General Mixed Integer Programming: Computational Issues for Branch-and-Cut Algorithms. In: [10], 1–25

  26. McKay, B.D.: Nauty User's Guide (Version 1.5). Computer Science Department, Australian National University, Canberra

  27. Mills, W.H., Mullin, R.C.: Coverings and Packings. In: Contemporary Design Theory: A collection of Surveys. Dinitz J.H., Stinson D.R., eds., Wiley, 1992, 371–399

  28. Odijk, M.A., van Maaren, H.: Improved Solutions to the Steiner Triple Covering Problem. Information Processing Letters 65, 67–69 (1998)

    Google Scholar 

  29. http://www.oreas.de

  30. Padberg, M.W., Rinaldi, G.: A Branch-and-Cut Algorithm for the Resolution of Large Scale Symmetric Travelling Salesman Problems. SIAM Review 33, 60–100 (1991)

    Google Scholar 

  31. Sherali, H.D., Smith, J.C.: Improving Discrete Model Representations via Symmetry Considerations. Management Science 47, 1396–1407 (2001)

    Google Scholar 

  32. Thienel, S.: ABACUS - A Branch-And-CUt System. Ph.D. Thesis, Universität zu Köln, 1995

  33. Wolsey, L.A.: Integer Programming, Wiley 1998

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, University of Kentucky, Lexington, KY, 40506-0027

    François Margot

Authors
  1. François Margot
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to François Margot.

Additional information

Mathematics Subject Classification (2000): 90C10, 90C27, 90C57

Rights and permissions

Reprints and permissions

About this article

Cite this article

Margot, F. Exploiting orbits in symmetric ILP. Math. Program., Ser. B 98, 3–21 (2003). https://doi.org/10.1007/s10107-003-0394-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-003-0394-6

Keywords

Search

Navigation