Abstract
Box-totally dual integral (box-TDI) polyhedra are polyhedra described by systems which yield strong min-max relations. We characterize them in several ways, involving the notions of principal box-integer polyhedra and equimodular matrices. A polyhedron is box-integer if its intersection with any integer box \(\{\ell \le x \le u\}\) is integer. We define principally box-integer polyhedra to be the polyhedra P such that \( kP \) is box-integer whenever \( kP \) is integer. A rational \(r\times n\) matrix is equimodular if it has full row rank and its nonzero \(r\times r\) determinants all have the same absolute value. A face-defining matrix is a full row rank matrix describing the affine hull of a face of the polyhedron. Our main result is that the following statements are equivalent.
-
The polyhedron P is box-TDI.
-
The polyhedron P is principally box-integer.
-
Every face-defining matrix of P is equimodular.
-
Every face of P has an equimodular face-defining matrix.
-
Every face of P has a totally unimodular face-defining matrix.
-
For every face F of P, \(\mathrm{lin}(F)\) has a totally unimodular basis.
Along our proof, we show that a polyhedral cone is box-TDI if and only if it is box-integer, and that these properties are carried over to its polar. We illustrate these charaterizations by reviewing well known results about box-TDI polyhedra. We also provide several applications. The first one is a new perspective on the equivalence between two results about binary clutters. Secondly, we refute a conjecture of Ding, Zang, and Zhao about box-perfect graphs. Thirdly, we discuss connections with an abstract class of polyhedra having the Integer Carathéodory Property. Finally, we characterize the box-TDIness of the cone of conservative functions of a graph and provide a corresponding box-TDI system.
Similar content being viewed by others
Notes
In the standard definition, the emptyset is a face. It is not the case in this paper in order to lighten the statements.
When we write that a face F has a face-defining matrix M, we mean that M is face-defining for the face F, which is more restrictive than being a face-defining matrix of the polyhedron F.
Between the submission and the publication of this paper, the question was answered in [4].
References
Alspach, B., Goddyn, M., Zhang, C.-Q.: Graphs with the circuit cover property. Trans. Am. Math. Soc. 344, 131–154 (1994)
Appa, G.: k-integrality, an extension of total unimodularity. Oper. Res. Lett. 13, 159–163 (1993)
Appa, G., Kotnyek, B.: Rational and integral k-regular matrices. Discrete Math. 275(1), 1–15 (2004)
Barbato, M., Grappe, R., Lacroix, M., Lancini, E., Calvo, R.W.: The Schrijver system of the flow cone in series–parallel graphs. Discrete Appl. Math. https://doi.org/10.1016/j.dam.2020.03.054 (2020)
Barnett, S.: Matrices in Control Theory, 2nd edn. Robert E. Krieger Publishing Co., Inc., Melbourne, FL (1984)
Benchetrit, Y.: Integer round-up property for the chromatic number of some h-perfect graphs. Math. Program. 164(1), 245–262 (2017)
Bevis, J.H., Hall, F.J.: Some classes of integral matrices. Linear Algebra Appl. 48, 473–483 (1982)
Cameron, K.: Polyhedral and Algorithmic Ramifications of Antichains. Ph.D. Thesis, University of Waterloo (1982)
Cameron, K.: A min-max relation for the partial q-colourings of a graph. Part ii: Box perfection. Discrete Math. 74(1), 15–27 (1989)
Camion, P.: Characterization of totally unimodular matrices. Proc. Am. Math. Soc. 16(5), 1068–1073 (1965)
Chen, X., Chen, Z., Zang, W.: A unified approach to box-Mengerian hypergraphs. Math. Oper. Res. 35(3), 655–668 (2010)
Chen, X., Ding, G., Zang, W.: A characterization of box-Mengerian matroid ports. Math. Oper. Res. 33(2), 497–512 (2008)
Chen, X., Ding, G., Zang, W.: The box-TDI system associated with 2-edge connected spanning subgraphs. Discrete Appl. Math. 157(1), 118–125 (2009)
Cook, W.: On box totally dual integral polyhedra. Math. Program. 34(1), 48–61 (1986)
Cornaz, D., Grappe, R., Lacroix, M.: Trader multiflow and box-TDI systems in series–parallel graphs. Discrete Optim. 31, 103–114 (2019)
Ding, G., Feng, L., Zang, W.: The complexity of recognizing linear systems with certain integrality properties. Math. Program. 114(2), 321–334 (2008)
Ding, G., Tan, L., Zang, W.: When is the matching polytope box-totally dual integral? Math. Oper. Res. 43(1), 64–99 (2018)
Ding, G., Zang, W.: Packing cycles in graphs. J. Comb. Theory Ser. B 86(2), 381–407 (2002)
Ding, G., Zang, W., Zhao, Q.: On box-perfect graphs. J. Comb. Theory Ser. B 128, 17–46 (2018)
Duffin, R.: Topology of series–parallel networks. J. Math. Anal. Appl. 10(2), 303–318 (1965)
Edmonds, J.: Submodular Functions, Matroids, and Certain Polyhedra, pp. 11–26. Springer, Berlin (2003)
Edmonds, J., Giles, R.: Total dual integrality of linear inequality systems. In: Pulleyblank, W.R. (ed.) Progress in Combinatorial Optimization (Jubilee Conference, University of Waterloo, Waterloo, Ontario, 1982), pp. 117–129 (1984)
Ford, L.R., Fulkerson, D.R.: Maximal flow through a network. Can. J. Math. 8, 399–404 (1956)
Gerards, A., Laurent, M.: A characterization of box \(\frac{1}{d}\)-integral binary clutters. J. Comb. Theory Ser. B 65(2), 186–207 (1995)
Ghouila-Houri, A.: Caractérisation des matrices totalement unimodulaires. Comptes Rendus Hebdomadaires des Séances de l’Académie des Sciences (Paris) 254, 1192–1194 (1962)
Gijswijt, D.: Integer decomposition for polyhedra defined by nearly totally unimodular matrices. SIAM J. Discrete Math. 19(3), 798–806 (2005)
Gijswijt, D., Regts, G.: Polyhedra with the integer Carathéodory property. J. Comb. Theory Ser. B 102(1), 62–70 (2012)
Heller, I.: On linear systems with integral valued solutions. Pac. J. Math. 7(3), 1351–1364 (1957)
Heller, I., Tompkins, C.B.: An extension of a theorem of Dantzig’s. In: Linear Inequalities and Related Systems, AM-38, pp. 247–254. Princeton University Press, Princeton (1956)
Hoffman, A., Oppenheim, R.: Local unimodularity in the matching polytope. In: Alspach, B., Hell, P., Miller, D. (eds.) Algorithmic Aspects of Combinatorics, volume 2 of Annals of Discrete Mathematics, pp. 201–209. Elsevier, Amsterdam (1978)
Hoffman, A.J., Kruskal, J.B.: Integral boundary points of convex polyhedra. In: Linear Inequalities and Related Systems, AM-38, pp. 223–246. Princeton University Press, Princeton (1956)
Kotnyek, B.: A Generalization of Totally Unimodular and Network Matrices. Ph.D. Thesis, London School of Economics (2002)
Lee, J.: Subspaces with well-scaled frames. Linear Algebra Appl. 114, 21–56 (1989)
Lovász, L.: Normal hypergraphs and the perfect graph conjecture. Discrete Math. 306(10–11), 867–875 (2006)
Oda, T.: Problems on Minkowski sums of convex lattice polytopes. ar**v:0812.1418 (2008)
Pap, J.: Recognizing conic TDI systems is hard. Math. Program. 128(1–2), 43–48 (2011)
Papadimitriou, C.H., Yannakakis, M.: On recognizing integer polyhedra. Combinatorica 10(1), 107–109 (1990)
Schrijver, A.: Theory of Linear and Integer Programming. Wiley-Interscience series in discrete mathematics and optimization. Wiley, New York (1999)
Schrijver, A.: Combinatorial optimization: polyhedra and efficiency. In: Algorithms and Combinatorics. Springer, Berlin (2003)
Sebő, A.: Path partitions, cycle covers and integer decomposition. In: Lipshteyn, M., Levit, V.E., McConnell, R.M. (eds.) Graph Theory. Computational Intelligence and Thought: Essays Dedicated to Martin Charles Golumbic on the Occasion of His 60th Birthday, pp. 183–199. Springer, Berlin (2009)
Seymour, P.: The matroids with the max-flow min-cut property. J. Comb. Theory Ser. B 23(2), 189–222 (1977)
Seymour, P.: Sums of circuits. In: Graph Theory and Related Topics (Proceedings Conference, Waterloo, Ontario, 1977; J.A. Bondy, U.S.R. Murty), vol. 1, pp. 341–355 (1979)
Smith, H.J.S.: On systems of linear indeterminate equations and congruences. Philos. Trans. R. Soc. Lond. 151, 293–326 (1861)
Truemper, K., Chandrasekaran, R.: Local unimodularity of matrix-vector pairs. Linear Algebra Appl. 22, 65–78 (1978)
Veinott, A.F.J., Dantzig, G.B.: Integral extreme points. SIAM Rev. 10(3), 371–372 (1968)
Zambelli, G.: Colorings of k-balanced matrices and integer decomposition property of related polyhedra. Oper. Res. Lett. 35(3), 353–356 (2007)
Acknowledgements
We are grateful to András Sebő for his invaluable comments and suggestions. We also thank the referees for their very careful reading and useful suggestions.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Louis-Hadrien Robert: Supported by the NCCR SwissMAP, funded by the Swiss National Science Foundation.
Rights and permissions
About this article
Cite this article
Chervet, P., Grappe, R. & Robert, LH. Box-total dual integrality, box-integrality, and equimodular matrices. Math. Program. 188, 319–349 (2021). https://doi.org/10.1007/s10107-020-01514-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-020-01514-0