Symmetry in Integer Linear Programming

François Margot ()
Additional contact information
François Margot: Tepper School of Business, Carnegie Mellon University

Chapter Chapter 17 in 50 Years of Integer Programming 1958-2008, 2010, pp 647-686 from Springer

Abstract: Abstract An integer linear program (ILP) is symmetric if its variables can be permuted without changing the structure of the problem. Areas where symmetric ILPs arise range from applied settings (scheduling on identical machines), to combinatorics (code construction), and to statistics (statistical designs construction). Relatively small symmetric ILPs are extremely difficult to solve using branch-and-cut codes oblivious to the symmetry in the problem. This paper reviews techniques developed to take advantage of the symmetry in an ILP during its solution. It also surveys related topics, such as symmetry detection, polyhedral studies of symmetric ILPs, and enumeration of all non isomorphic optimal solutions.

Keywords: Symmetry Breaking; Symmetry Group; Travel Salesman Problem; Permutation Group; Enumeration Tree (search for similar items in EconPapers)
Date: 2010
References: Add references at CitEc
Citations: View citations in EconPapers (1)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-540-68279-0_17

Ordering information: This item can be ordered from
http://www.springer.com/9783540682790

DOI: 10.1007/978-3-540-68279-0_17

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().