2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Joshua Grochow Apr 11 '17 at 16:03
  • $\begingroup$ Also, I don't think TUM and TDI are standard enough abbreviations that it is good to use them in your title... $\endgroup$ – Joshua Grochow Apr 11 '17 at 16:05
  • $\begingroup$ @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. $\endgroup$ – PsySp Apr 11 '17 at 16:16
  • 1
    $\begingroup$ 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. $\endgroup$ – Joshua Grochow Apr 11 '17 at 18:21
  • 1
    $\begingroup$ 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. $\endgroup$ – Joshua Grochow Apr 12 '17 at 4:49
3
$\begingroup$

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)$$

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.