Abstract
The duality for group problems developed in [3] is restricted top-nary group problems. Results for ternary group problems are obtained similar to those obtained by Fulkerson and Lehman for the binary case. A complete facet description of the group polyhedron is available for a group problem having the Fulkerson property. A group problem has the Fulkerson property if its vertices are the facets of the blocking group problem and if its facets are the vertices of the blocking group problem. The Fulkerson property is a generalization of the max-flow min-cut theorem of Ford and Fulkerson which is interpreted as a statement about the pair of row modules arising from a group problem. We show that a group problem has the Fulkerson property if the corresponding row module is regular.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
R.E. Bixby, “On Reids characterization of the ternary matroids,”Journal of Combinatorial Theory Series B 26 (1979) 174–204.
S. Chopra, “Dual row modules and polyhedra of blocking group problems,” Ph.D. Dissertation, SUNY Stony Brook, August 1986.
S. Chopra and E.L. Johnson, “Dual row modules and polyhedra of blocking group problems,”Mathematical Programming 38 (1987) 229–270.
E.W. Dijkstra, “A note on two problems in connection with graphs,”Numerische Mathematik 1 (1959) 269–271.
J. Edmonds, “Matroids and the greedy algorithm,”Mathematical Programming 1 (1971) 127–136.
D.R. Fulkerson, “Blocking Polyhedra,” in: B. Harris, ed.,Graph Theory and Its Applications (Academic Press, NY, 1970) 93–112.
D.R. Fulkerson, “Networks, Frames, Blocking Systems,” in: G.B. Dantzig and A.F. Veinott, Jr., eds.,Mathematics of the Decision Sciences, Part 1 (American Mathematical Society, 1968) pp. 303–334.
G. Gastou, “On facets of integer programming polyhedra,” Ph.D. thesis, Yale University (1982).
G. Gastou and E.L. Johnson, “Binary group and Chinese postman polyhedra,”Mathematical Programming 34 (1986) 1–33.
R.E. Gomory, “An algorithm for integer solutions to linear programs,” in: R.L. Graves and P. Wolfe, eds.,Recent Advances in Mathematical Programming (McGraw-Hill, 1963) pp. 269–302.
R.E. Gomory, “On the relation between integer and noninteger solutions to linear programs,”Proceedings of N.A.S. 53 (1965) 260–265.
R.E. Gomory, “Some polyhedra related to combinatorial problems,”Linear Algebra and Its Applications 2(4) (October 1969) 451–558.
M. Hall,The Theory of Groups, second edition (Chelsea Publishing Co., New York, 1976).
B. Hartley and T.O. Hawkes,Rings, Modules and Linear Algebra (Chapman and Hall Ltd., London).
E.L. Johnson, “On cut-set integer Polyhedra,”Cahiers du Centre d'Etudes de Recherche Operationelle 17 (1975) 235–251.
E.L. Johnson, “On the generality of the subadditive characterization of facets,”Mathematics of Operations Research 6 (1981) 101–112.
E.L. Johnson, “On binary group problems having the Fulkerson property,” Lecture notes from CIME Summer School, Como (1986), to be published by Springer-Verlag.
E.L. Johnson, “Support functions, Blocking pairs, and Anti-Blocking pairs,”Mathematical Programming Study 8 (1978) 167–196.
E.L. Johnson, “Integer Programming: facets, subadditivity and duality for group and semi-group problems,” CBMS-NSF Regional Conference Series in Applied Mathematics 32, SIAM, Philadelphia (1980).
A. Lehman, “A solution to the Shannon switching game,”SIAM Journal on Applied Mathematics 12 (1964) 687–725.
A. Lehman, “On the length-width inequality,”Mathematical Programming 17 (1979) 403–417.
S. MacLane and G. Birkhoff,Algebra (The MacMillan Co., New York, 1967).
P.D. Seymour, “The forbidden minors of binary clutters,”Journal London Mathematical Society (2) 12 (1976) 356–360.
P.D. Seymour, “A note on the production of matroid minors,”Journal of Combinatorial Theory (B) 22 (1977) 289–295.
P.D. Seymour, “Matroids with the max-flow min-cut property,”Journal of Combinatorial Theory (B) 23 (1977) 189–222.
P.D. Seymour, “Matroids and multicommodity flows,”European Journal Combinatorics 2 (1981) 257–290.
P.D. Seymour, “Matroid Representation over GF(3),”Journal of Combinatorial Theory (B) 26 (1979) 159–173.
W.T. Tutte, “Lectures on matroids,”Journal of Research National Bureau of Standards 69 B (1965) 1–47.
W.T. Tutte,Introduction to the Theory of Matroids (American Elsevier Publishing Co., New York, 1971).
D.J.A. Welsh,Matroid Theory (Associated Press, London, 1976).
H. Whitney, “On the abstract properties of linear dependence,”American Journal of Mathematics 57 (1935) 507–533.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Chopra, S., Jensen, D.L. & Johnson, E.L. Polyhedra of regularp-nary group problems. Mathematical Programming 43, 1–29 (1989). https://doi.org/10.1007/BF01582275
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01582275