2026-05-14

Conjecture: For any feasible basis $B$ of the OHCP/flat norm LP, either $|\det B|=1$ or the Smith normal form is of the form

$$SNF(B)=\left[\begin{array}{cc}{I}_{m-t}& \\ & k{I}_t\end{array}\right]$$

where $k\in {\mathbb{Z}}_{+}$ and $0<t<m$.

Lemma: Let $B$ be a feasible basis with $|\det B|>1$. Assuming the above conjecture holds true, there are unimodular matrices $U$ and $V$ such that

$$UBV=S=\left[\begin{array}{cc}{I}_{m-t}& \\ & k{I}_t\end{array}\right].$$

Let $G$ be the last $t$ rows of $U$. Then $x_B=B^{-1}b$ is integral if $Gb\equiv 0\mathrm{mod}k$.

Proof. Notice that

$$x_B=B^{-1}b=(U^{-1}S{V}^{-1}{)}^{-1}b=V{S}^{-1}Ub.$$

Split $U$ into

$$U=\left[\begin{array}{c}F\\ G\end{array}\right].$$

Then it follows that

$$x_B=V\left[\begin{array}{c}Fb\\ \frac{1}{k}Gb\end{array}\right].$$

Note that $V$ is unimodular, so $x_B\in {\mathbb{Z}}^m$ if and only if $\frac{1}{k}Gb\in {\mathbb{Z}}^m$, i.e., $Gb\equiv 0\mathrm{mod}k$. $■$

Based on the above result, integrality appears to be property of the combination of $A$ and $b$. Numerical experiments have shown that for some instances $G\not\equiv 0\mathrm{mod}k$ and $G[\partial ]\not\equiv 0\mathrm{mod}k$, where $[\partial ]$ is the boundary matrix.

---

Below is a trace of a minimal non-TU instance ($10$ triangles):

Iteration 1-20: Phase 1 searching for initial basis

Iteration 21:

$$\begin{array}{rl}z& =6\\ x& =[1,4]+[0,1]+[2,3]+[4,5]-[0,3]-[2,5]\\ y& =0\end{array}$$

Iteration 22:

$$\begin{array}{rl}z& =5\\ x& =[2,3]+[4,5]-[0,4]-[0,3]-[2,5]\\ y& =-[0,1,4]\end{array}$$

Iteration 23:

$$\begin{array}{rl}z& =4\\ x& =[3,4]+[2,3]+[4,5]+-[2,5]\\ y& =[0,3,4]-[0,1,4]\end{array}$$

The remaining 11 iterations are the same solution $(z,x,y)$, but the simplex method is attempting other “equivalent” bases by swapping out degenerate variables.

Below is the final basis equation:

And the resulting SNF:

$$\left[\begin{array}{cc}0& I_{17}\\ 1& G^{\prime }\end{array}\right]BV=\left[\begin{array}{cc}{I}_{17}& \\ & 2\end{array}\right].$$

where

$$G^{\prime }=\left[\begin{array}{ccccccccccccccccc}0& -1& 0& 0& 0& 0& 0& 0& 0& 0& 0& -1& -1& 0& 0& 0& 0\end{array}\right]$$

We get an integer solution because

$$\left[\begin{array}{cc}1& G^{\prime }\end{array}\right]b\equiv 0\mathrm{mod}2.$$