Abstract
We define a fundamental domain of a linear programming relaxation of a combinatorial integer program which is symmetric under a group action. We then provide a construction for the polytope of a fundamental domain defined by the maximization of a linear function. The computation of this fundamental domain is at worst polynomial in the size of the group. However, for the special case of the symmetric group, whose size is exponential in the size of the integer program, we show how to compute a separating hyperplane in polynomial time in the size of the integer program.
Fundamental domains may provide a straightforward way to reduce the computation difficulties that often arise in integer programs with symmetries. Our construction is closely related to the constructions of orbitopes by Kaibel and Pfetch, but are simpler and more general, at a cost of creating new non-integral extreme points.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
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. Operations Research 46, 316–329 (1998)
Bazaraa, M.S., Kirca, O.: A branch-and-bound heuristic for solving the quadratic assignment problem. Naval Research Logistics Quarterly 30, 287–304 (1983)
Holm, S., Srensen, M.: The optimal graph partitioning problem: Solution method based on reducing symmetric nature and combinatorial cuts. OR Spectrum 15, 1–8 (1993)
Kaibel, V., Peinhardt, M., Pfetsch, M.: Orbitopal fixing. In: Proc. 12th Conference on Integer Programming and Combinatorial Optimization (IPCO). LNCS, Springer, Heidelberg (forthcoming, 2007)
Kaibel, V., Pfetsch, M.: Packing and partitioning orbitopes. Math. Program., Ser. A 2006 (in press), doi:10.1007/s10107-006-0081-5
Margot, F.: Pruning by isomorphism in branch-and-cut. Mathematical Programming 94(1), 71–90 (2002)
Margot, F.: Small covering designs by branch-and-cut. Mathematical Programming 94(2), 207–220 (2003)
Méndez-Díaz, I., Zabala, P.: A branch-and-cut algorithm for graph coloring. Discrete Applied Mathematics 154(5), 826–847 (2006)
Ostrowski, J., Linderoth, J., Rossi, F., Smriglio, S.: Orbital branching. In: Proc. 12th Conference on Integer Programming and Combinatorial Optimization (IPCO). LNCS, Springer, Heidelberg (forthcoming, 2007)
Serafini, P., Ukovich, W.: A mathematical model for periodic scheduling problems. SIAM J. Discrete Math 2(4), 550–581 (1989)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Friedman, E.J. (2007). Fundamental Domains for Integer Programs with Symmetries. In: Dress, A., Xu, Y., Zhu, B. (eds) Combinatorial Optimization and Applications. COCOA 2007. Lecture Notes in Computer Science, vol 4616. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73556-4_17
Download citation
DOI: https://doi.org/10.1007/978-3-540-73556-4_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-73555-7
Online ISBN: 978-3-540-73556-4
eBook Packages: Computer ScienceComputer Science (R0)