[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Cyclic group blocking polyhedra

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

Abstract

Gomory (Linear Algebra Appl 2:451–558, 1969) gave a subadditive characterization of the facets of the group polyhedron. Although there are exponentially many facets (see Gomory and Johnson in Math Program 3:359–389, 1972, Example 4.6) and exponentially many vertices for the group polyhedron for the master cyclic group problem, Gomory’s characterization of the non-trivial facets has polynomially many subadditive inequalities, in fact of order |G|2 for a finite Abelian group G. We reduce this subadditive inequality system to its minimal representation by a triple system of the same order and show the dimensionality of the polytope of non-trivial facets. The system of all triples corresponds to all solution vectors of length three into which every solution vector can be decomposed. Our minimal representation leads to a characterization of the vertices of length three. Gomory et al. (Math Program 96:321–339, 2003) introduced a shooting experiment involving solving the shooting linear program repeatedly to find important facets. We develop a topological network flow model of the dual problem of the shooting linear program in a reverse procedure from the decomposition of solution vectors into triples. Hunsaker (2003) gave a knapsack shooting experiment, which we use to find a simple pattern for the most hit knapsack facets.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Aráoz, J.: Polyhedral Neopolarities. Ph.D. Dissertation, University of Waterloo, Department of Computer Science (1974)

  2. Aráoz J., Evans L., Gomory R., Johnson E.: Cyclic group and knapsack facets. Math. Program. 96, 377–408 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  3. Chopra S., Johnson E.L.: Dual row modules and polyhedra of blocking group problems. Math. Program. 38, 229–270 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  4. Even S., Goldreich O.: The minimal-length generating sequence problem is NP-hard. J. Algorithms 2, 311–313 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  5. Fulkerson D.R.: Blocking polyhedra. In: Harris, B. (ed) Graph Theory and Its Applications., pp. 93–112. Academic Press, New York (1970)

    Google Scholar 

  6. Gomory R.E.: Some polyhedra related to combinatorial problems. Linear Algebra Appl. 2, 451–558 (1969)

    Article  MathSciNet  MATH  Google Scholar 

  7. Gomory R.E., Johnson E.L.: Some continuous functions related to corner polyhedra, II. Math. Program. 3, 359–389 (1972)

    Article  MathSciNet  MATH  Google Scholar 

  8. Gomory R.E., Johnson E.L., Evans L.: Corner polyhedra and their connection with cutting planes. Math. Program. 96, 321–339 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  9. Gross J.L., Tucker T.W.: Topological Graph Theory. Wiley, New York (1987)

    MATH  Google Scholar 

  10. Heydemann M.-C.: Cayley graphs and interconnection networks. In: Hahn, G., Sabidussi, G. (eds) Graph Symmetry, pp. 167–224. Kluwer, The Netherlands (1997)

    Chapter  Google Scholar 

  11. Hunsaker, B.: Measuring Facets of Polyhedra to Predict Usefulness in Branch-and-Cut Algorithms. Ph.D. Thesis, Georgia Institute of Technology (2003)

  12. Jerrum M.: The complexity of finding minimal-length generating sequence. Theor. Comput. Sci. 36, 265–289 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  13. Shim, S.: Large Scale Group Network Optimization, Ph.D. Thesis, Georgia Institute of Technology (2009)

  14. Shim S., Johnson E.L., Cao W.: Primal-dual simplex method for shooting. Electronic Notes in Discrete Mathematics. 36, 719–726 (2010)

    Article  Google Scholar 

  15. Wong C.K., Coppersmith D.: A combinatorial problem related to multimodule memory organization. J. Assoc. Comput. Mach. 21, 392–402 (1974)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Industrial Engineering and Management Sciences, Northwestern University, 2145 Sheridan Road Room C210, Evanston, IL, 60208, USA

    Sangho Shim & Ellis L. Johnson

Authors
  1. Sangho Shim
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ellis L. Johnson
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Sangho Shim.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Shim, S., Johnson, E.L. Cyclic group blocking polyhedra. Math. Program. 138, 273–307 (2013). https://doi.org/10.1007/s10107-012-0536-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-012-0536-9

Mathematics Subject Classification

Search

Navigation