On box totally dual integral polyhedra.(English)Zbl 0589.52006
A rational linear system Ax\(\leq b\) is a totally dual integral system (TDI system) if for each integral vector for which the optima of \[ \min \{yb: yA=w, y\geq 0\}= \max \{wx: Ax\leq b\} \] exists, the minimum can be achieved by an integral vector. If, for every choice of rational vectors \(\ell\) and u, the linear system \((Ax\leq b)\wedge (\ell \leq x\leq u)\) is a TDI system, the system Ax\(\leq b\) is said to be a base totally dual integral system (base TDI system). The feasible set for such a system is a box TDI polyhedron.
A geometric characterization of these polyhedra is given. It is used to show that each TDI defining system for a box TDI polyhedron is in fact a box TDI system. The class of box TDI polyhedra is in co-NP and is closed under taking projections and dominants.
A geometric characterization of these polyhedra is given. It is used to show that each TDI defining system for a box TDI polyhedron is in fact a box TDI system. The class of box TDI polyhedra is in co-NP and is closed under taking projections and dominants.
Reviewer: R.Fourneau
MSC:
| 52A40 | Inequalities and extremum problems involving convexity in convex geometry |
| 52Bxx | Polytopes and polyhedra |
| 90C10 | Integer programming |
Cite
Full Text:DOI
References:
| [1] | A. Bachem and M. Grötschel, ”New aspects of polyhedral theory”, in: B. Korte, ed.,Modern applied mathematics – Optimization and operations research (North-Holland, Amsterdam, 1982) 51–106. ·Zbl 0481.90063 |
| [2] | E. Balas and W.R. Pulleyblank, ”The perfectly matchable subgraph polytope of a bipartite graph”,Networks 13 (1983) 495–516. ·Zbl 0525.90069 ·doi:10.1002/net.3230130405 |
| [3] | C. Berge,Graphs and hypergraphs (North-Holland, Amsterdam, 1973). ·Zbl 0254.05101 |
| [4] | C. Berge and V. Chvátal,Topics on perfect graphs (North-Holland, Amsterdam, 1984). ·Zbl 0546.00006 |
| [5] | K. Cameron, ”Polyhedral and algorithmic ramifications of antichains”, Ph.D. Thesis, University of Waterloo, 1982. |
| [6] | R. Chandrasekaran, ”Polynomial algorithms for totally dual integral systems and extensions”,Annals of Discrete Mathematics 11 (1981) 39–51. ·Zbl 0469.90060 |
| [7] | W. Cook, L. Lovász and A. Schrijver, ”A polynomial-time test for total dual integrality in fixed dimension”,Mathematical Programming Study 22 (1984) 64–69. ·Zbl 0557.90071 |
| [8] | W.H. Cunningham, ”An unbounded matroid intersection polyhedron”, Linear Algebra and its Appliications 16 (1977) 209–215. ·Zbl 0373.05024 ·doi:10.1016/0024-3795(77)90003-9 |
| [9] | W.H. Cunningham and J. Green-Krotki, to appear. |
| [10] | J. Edmonds, ”Submodular functions, matroids, and certain polyhedra”, in: R. Guy, H. Hanani, N. Sauer and J. Schonheim, eds.,Combinatorial structures and their applications (Gordon and Breach, New York, 1970) 69–87. ·Zbl 0268.05019 |
| [11] | J. Edmonds and R. Giles, ”A min-max relation for submodular functions on graphs”,Annals of Discrete Mathematics 1 (1977) 185–204. ·Zbl 0373.05040 ·doi:10.1016/S0167-5060(08)70734-9 |
| [12] | J. Edmonds and R. Giles, ”Box total dual integrality”, unpublished paper, 1980. ·Zbl 0555.90078 |
| [13] | J. Edmonds and R. Giles, ”Total dual integrality of linear inequality systems”, in: W.R. Pulleyblank, ed.,Progress in combinatorial optimization (Academic Press, Toronto, 1984) 117–129. ·Zbl 0555.90078 |
| [14] | A. Frank, ”Kernel systems of directed graphs”,Acta Scientiarum Mathematicarum (Szeged) 41 (1979) 63–76. ·Zbl 0425.05028 |
| [15] | A. Frank, ”Generalized polymatroids”, Report 81206-OR, Institut für Ökonometrie und Operations Research, Bonn, F.R. Germany, 1981. ·Zbl 0568.05018 |
| [16] | A. Frank and E. Tardos, ”Generalized polymatroids and submodular flows”, in preparation. ·Zbl 0665.90073 |
| [17] | D.R. Fulkerson, ”Blocking and anti-blocking pairs of polyhedra”,Mathematical Programming 1 (1971) 168–194. ·Zbl 0254.90054 ·doi:10.1007/BF01584085 |
| [18] | M.R. Garey and D.S. Johnson,Computers and intractability: A Guide to the theory of NP-completeness (W.H. Freeman and Company, San Francisco, 1979). ·Zbl 0411.68039 |
| [19] | J. von zur Gathen and M. Sieveking, ”A bound on solutions of linear integer equalities and inequalities”,Proceedings of the American Mathematical Society 72 (1978) 155–158. ·Zbl 0397.90071 ·doi:10.1090/S0002-9939-1978-0500555-0 |
| [20] | F.R. Giles and W.R. Pulleyblank, ”Total dual integrality and integer polyhedra”, Linear Algebra and its Applications 25 (1979) 191–196. ·Zbl 0413.90054 ·doi:10.1016/0024-3795(79)90018-1 |
| [21] | C. Greene and D. Kleitman, ”The structure of Spernerk-families”,Journal of Combinatorial Theory Series A 20 (1976) 41–68. ·Zbl 0363.05006 ·doi:10.1016/0097-3165(76)90077-7 |
| [22] | H. Gröflin and A.J. Hoffman, ”Lattice polyhedra II: Generalization, constructions and examples”,Annals of Discrete Mathematics 15 (1982) 189–203. ·Zbl 0507.90062 |
| [23] | M. Grötschel, L. Lovász and A. Schrijver, ”The ellipsoid method and its consequences in combinatorial optimization”,Combinatorica 1 (1981) 169–197. ·Zbl 0492.90056 ·doi:10.1007/BF02579273 |
| [24] | M. Grötschel, L. Lovász and A. Schrijver, ”Polynomial algorithms for perfect graphs”, in: C. Berge and V. Chvátal, eds.,Topics on perfect graphs (North-Holland, Amsterdam, 1984) 325–356. ·Zbl 0554.05041 |
| [25] | M. Grötschel, L. Lovász and A. Schrijver, ”Relaxations of vertex packing”, Report 84341-OR, Institut für Ökonometrie und Operations Research, Bonn, W. Germany, 1984. ·Zbl 0596.05052 |
| [26] | M. Grötschel, L. Lovász and A. Schrijver,The ellipsoid method and combinatorial optimization (Springer-Verlag), to appear. ·Zbl 0539.90078 |
| [27] | A.J. Hoffman, ”A generalization of max flow-min cut”,Mathematical Programming 6 (1974) 352–359. ·Zbl 0357.90068 ·doi:10.1007/BF01580250 |
| [28] | A.J. Hoffman and D.E. Schwartz, ”On lattice polyhedra”, in: A. Hajnal and V.T. Sós, eds.,Combinatorics (North-Holland, Amsterdam, 1978) 593–598. ·Zbl 0408.05011 |
| [29] | L.G. Khachiyan, ”A polynomial algorithm in linear programming”,Soviet Mathematics Doklady 20 (1979) 191–194. ·Zbl 0414.90086 |
| [30] | L. Lovász, ”Normal hypergraphs and the perfect graph conjecture”,Discrete Mathematics 2 (1972) 253–267. ·Zbl 0239.05111 ·doi:10.1016/0012-365X(72)90006-4 |
| [31] | L. Lovász, ”Perfect graphs”, in: L.W. Beineke and R.J. Wilson, eds.,Selected topics in graph theory 2 (Academic Press, London, 1983) 55–87. ·Zbl 0536.05055 |
| [32] | C. McDiarmid, ”Blocking, antiblocking, and pairs of matroids and polymatroids”,Journal of Combinatorial Theory Series B 25 (1978) 313–325. ·Zbl 0401.05032 ·doi:10.1016/0095-8956(78)90008-4 |
| [33] | W.R. Pulleyblank, ”Polyhedral combinatorics”, in: A. Bachem, M. Grötschel and B. Korte, eds.,Mathematical Programming–The state of the art (Springer-Verlag, Heidelberg, 1983) 312–345. ·Zbl 0566.90063 |
| [34] | R.T. Rockafeller,Convex analysis (Princeton University Press, Princeton, 1970). |
| [35] | A. Schrijver, ”On total dual integrality”,Linear Algebra and its Applications 38 (1981) 27–32. ·Zbl 0474.90065 ·doi:10.1016/0024-3795(81)90005-7 |
| [36] | A. Schrijver, ”Proving total dual integrality with cross-free families–a general framework”,Mathematical Programming 29 (1984) 15–27. ·Zbl 0531.90076 ·doi:10.1007/BF02591726 |
| [37] | A. Schrijver, ”Total dual integrality from directed graphs, crossing families, and sub- and supermodular functions”, in: W.R. Pulleyblank, ed.,Progress in combinatorial optimization (Academic Press, Toronto, 1984) 315–361. ·Zbl 0542.90068 |
| [38] | A. Schrijver,Theory of linear and integer programming (Wiley) to appear. |
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.
