Box-total dual integrality, box-integrality, and equimodular matrices

• 成果类型: Article
• 署名作者: Chervet, Patrick; Grappe, Roland; Robert, Louis-Hadrien
• 署名单位: Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I); University of Geneva
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-020-01514-0
• 发表日期: 2021
• 页码: 319-349
• 关键词: integer decomposition; tdi systems; colorings; polyhedra; PROPERTY; graph

摘要

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 {l <= x <= 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 x n matrix is equimodular if it has full row rank and its nonzero r x 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, 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 Caratheodory Property. Finally, we characterize the box-TDIness of the cone of conservative functions of a graph and provide a corresponding box-TDI system.