# Are there specific examples of integral polyhedra that are neither Totally Unimodular nor Total Dual Integral?

It is well known that if a constraint matrix $A$ is total dual integral or totally unimodular, then this is a sufficient condition of integrality of the polyhedron defined by the system $Ax \leq \beta$ (provided that $\beta$ has integer entries). But it is not a necessary condition.

Thus my question is

Are there natural examples (from combinatorial optimization) of integral polyhedra such that their underlying constraint matrix is neither TUM nor TDI?

• By "underlying constraint matrix" do you mean the natural matrix defined by the facets of the polyhedron? Or are you just asking for a matrix $A$ that is not totally unimodular nor total dual integral but such that, for some $b$ (or do you want it to hold for all $b$?) $\{x : Ax \leq b\}$ is an integral polytope? – Joshua Grochow Apr 11 '17 at 16:03
• Also, I don't think TUM and TDI are standard enough abbreviations that it is good to use them in your title... – Joshua Grochow Apr 11 '17 at 16:05
• @JoshuaGrochow As for your first question, I actually ask for both: an example of an integral polyhedron where we cannot formulate it as a TUM/TDI matrix A for any vector b. As for the abbreviations, I will change them. – PsySp Apr 11 '17 at 16:16
• I don't think such a thing exists. I believe Giles and Pulleyblank showed that any integral polytope can be written as $\{x : Ax \leq b\}$ for some total dual integral A and integer vector b. – Joshua Grochow Apr 11 '17 at 18:21
• I still don't think it's a question of "which are those polytopes", since TDI isn't a property of polytopes. Every integral polytope can be written as the solution set of some TDI system. I bet it's not hard to show that every integral polytope can also be written as the solution set of some non-TDI system: you can probably do this by taking an arbitrary linear system that defines $P$ and if it is TDI then just scale it by a random rational number; see the proof of Thm 3.2 in Giles-Pulleyblank. – Joshua Grochow Apr 12 '17 at 4:49

I'm only going to talk about the constraint matrix part of the problem, I don't know much about the linear system (TDI) part.

Call a matrix $A$ good if $\{x|Ax\leq b,x\geq 0\}$ is a integral polytope for all integral $b$. TUM is precisely the set of good integral matrices. This is a result by Hoffman and Kruskal. see this for how the theorem comes about and the original paper.

If we relax the requirement that $A$ is integral, then we get a larger class of matrices. Call a good matrix $A$ trivial, if it is a scaling of a TUM matrix (i.e. $A=\frac{1}{k}B$ for some TUM matrix $B$ and integer $k$).

Sadly, I don't know of any natural non-trivial good matrices.

But there is a characterization of good matrices. A matrix $A$ is $1$-regular if for all non-singular square submatrix $R$, $R^{-1}$ is integral. We have the following by Appa and Kotnyek.

A rational matrix $A$ is good iff $A$ is $1$-regular.

Here is an example of a non-trivial good matrix.

$$\left( \begin{array}{cc} \frac{1}{2} & -\frac{1}{2} \\ -\frac{1}{2} & -\frac{1}{2} \\ \end{array} \right)$$

• Τhank you for the answer and the references that I was not aware of! This, together with @JoshuaGrochow comment about TDI, answer my question. – PsySp Apr 12 '17 at 8:17