Dual row modules and polyhedra of blocking group problems.(English)Zbl 0636.90064
Summary: Corresponding to every group problem is a row module. Duality for group problems is developed using the duality or orthogonality of the corresponding row modules. The row module corresponding to a group problem is shown to include Gomory’s fractional cuts for the group polyhedron and all the vertices of the polyhedron of the blocking group problem. The polyhedron corresponding to a pair of blocking group problems are shown to have a blocking nature i.e. the vertices of one include some of the facets of the other and mutatis mutandis. The entire development is constructive. The notions of contraction, deletion, expansion and extension are defined constructively and related to homomorphic liftings and subproblems in a dual setting. Roughly speaking a homomorphic lifting is dual to forming a subproblem. A proof of the Gastou-Johnson generalization of Gomory’s homomorphic lifting theorem is given, and dual constructions are discussed. A generalization of Gomory’s subadditive characterization to subproblems is given. In the binary case, it is closely related to the work of Seymour on cones arising from binary matroids.
Cite
Full Text:DOI
References:
| [1] | J. Araoz and E.L. Johnson, ”Morphic liftings between pairs of integer polyhedra” IBM Research Report, in preparation. |
| [2] | S. Chopra, ”Dual row modules and polyhedra of blocking group problems,” Ph.D. Dissertation, SUNY (Stony Brook, 1986). ·Zbl 0636.90064 |
| [3] | S. Chopra, D.L. Jensen and E.L. Johnson, ”Polyhedra of regularp-nary group problems,” submitted toMathematical Programming. ·Zbl 0673.90068 |
| [4] | D.R. Fulkerson, ”Blocking polyhedra,” in: B. Harris, ed.,Graph theory and its applications (Academic Press, NY, 1970) pp. 93–112. ·Zbl 0217.18505 |
| [5] | D.R. Fulkerson, ”Networks, frames, blocking systems,” in: G.B. Dantzig and A.F. Veinott Jr., eds.Mathematics of the decision sciences, Part 1 (AMS, 1968) pp. 303–334. ·Zbl 0182.53402 |
| [6] | G. Gastou, ”On Facets of integer programming polyhdra,” Ph.D. thesis, Yale University, 1982. |
| [7] | G. Gastou and E.L. Johnson, ”Binary group and Chinese postman polyhedra,”Mathematical Programming 34 (1986) 1–33. ·Zbl 0589.52004 ·doi:10.1007/BF01582160 |
| [8] | R.E. Gomory, ”An algorithm for integer solutions to linear programs,” R.L. Graves and P. Wolfe, eds.,Recent advances in mathematical programming, (McGraw Hill, New York, 1963), pp. 269–302. ·Zbl 0235.90038 |
| [9] | R.E. Gomory, ”On the relation between integer and noninteger solutions to linear programs,”Proceedings of National Academy of Science 53 (1965) 260–265. ·Zbl 0132.13702 ·doi:10.1073/pnas.53.2.260 |
| [10] | R.E. Gomory, ”Some polyhedra related to combinatorial problems,”Linear Algebra and its Applications 2 (1969) 451–558. ·Zbl 0184.23103 ·doi:10.1016/0024-3795(69)90017-2 |
| [11] | M. Hall,The theory of groups (Chelsea publishing Co., NY, 1976). ·Zbl 0354.20001 |
| [12] | B. Hartley and T.O. Hawkes, Rings, modules and linear algebra (Chapman and Hall Ltd., London). ·Zbl 0206.01603 |
| [13] | T.C. Hu,Integer programming and network flows (Addison-Wesley, 1970). |
| [14] | E.L. Johnson, ”On the generality of the subadditive characterization of facets,”Mathematics of Operations Research 6 (1981) 101–112. ·Zbl 0513.90059 ·doi:10.1287/moor.6.1.101 |
| [15] | E.L. Johnson, ”On binary group problems having the Fulkerson property,” IBM RC 10641 (Yorktown Heights, NY, 1984). |
| [16] | E.L. Johnson, ”Support functions, blocking pairs, and anti-blocking pairs,”Mathematical Programming Study 8 (1978) 167–196. ·Zbl 0457.90075 |
| [17] | E.L. Johnson, ”Integer Programming: facets, subadditivity and duality for group and semi-group problems,” IBM RC 7450 (Yorktown Heights, NY, 1978). |
| [18] | S. MacLane and G. Birkhoff,Algebra (The MacMillan Co., NY, 1967). |
| [19] | P.D. Seymour, ”Matroids with the max-flow min-cut property,”Journal of Combinatorial Theory series B 23 (1977) 189–222. ·Zbl 0375.05022 ·doi:10.1016/0095-8956(77)90031-4 |
| [20] | P.D. Seymour, ”Matroids and multicommodity flows,”European Journal of Combinatorics 2 (1981) 257–290. ·Zbl 0479.05023 |
| [21] | W.T. Tutte, ”Lectures on matroids,”Journal of Research of the National Bureau of Standards Section B 69 (1965) 1–47. ·Zbl 0151.33801 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
