2026-07-02

TL;DR: In the flat norm LP, it is possible to have a fractional feasible solution but still have an integral optimal solution.

---

Upon further exploring the instance from 2026-06-29, I have found an instance which had intermediate BFS’ with fractional solution, but the optimal solution was integral. Recall that we started with the input

$$b=[0,6]+[6,7]+[7,8]-[0,8]\text{ where }\lambda =0.5$$

which had an intermediate BFS with basis matrix $B$ where $\det B=2$. Upon finding the Smith normal form for $B$, we found that

$$SNF(B)=\left[\begin{array}{cc}{I}_{26}& 0\\ 0& 2\end{array}\right]$$

with left-transform $U$ having a final row of

$$G=\left[\begin{array}{ccccccccccccccccccccccccccc}0& 0& 0& 0& -1& 1& 1& 1& 0& 0& 0& 1& 1& 1& 0& 0& 0& 1& 0& 0& 1& 1& 1& 0& 0& 0& 0\end{array}\right].$$

In order for the BFS to have an integral solution, one needs $Gb\equiv 0\mathrm{mod}2$ (see 2026-05-14). Thus, we consider the following ILP:

$$\begin{array}{rlr}& \underset{\mathbf{b},k}{\mathrm{maximize}}& 0\\ & \text{subject to}& B^{-1}\mathbf{b}\ge 0\\ & & G\mathbf{b}=2k+1\\ & & \mathbf{b}\in {\mathbb{Z}}^n\end{array}$$

Running this problem through Google’s OR-Tools gives the following feasible solution:

$$\begin{array}{rl}\mathbf{b}& =[3,6]-[0,4]+[0,3]+[0,1]+[6,7]-[2,7]+[2,4]+[1,2]\\ & +[5,7]+[2,5]+[7,8]-[2,8]+[3,8]+[2,3]-[0,8].\end{array}$$

Running this through my solver gives three iterations which had fractional feasible solutions:

108: [Feasible][P2][det(B)=2][z=6.25][E=[0,1];L=[0,6]]
	 x = 0.5*[3,6] + 0.5*[0,1] + 0.5*[6,7] + 0.5*[1,2] + 0.5*[7,8] + 0.5*[2,3] + -0.5*[0,8]; y = 0.5*[0,4,6] + -0.5*[0,3,6] + -0.5*[0,1,4] + -0.5*[4,6,7] + -0.5*[2,4,7] + -0.5*[1,2,4] + -1*[2,5,7] + -0.5*[2,7,8] + -0.5*[2,3,8] + -0.5*[0,3,8]
109: [Feasible][P2][det(B)=2][z=6.25][E=[3,4];L=[0,4]]
	 x = 0.5*[3,6] + 0.5*[0,1] + 0.5*[6,7] + 0.5*[1,2] + 0.5*[7,8] + 0.5*[2,3] + -0.5*[0,8]; y = 0.5*[0,4,6] + -0.5*[0,3,6] + -0.5*[0,1,4] + -0.5*[4,6,7] + -0.5*[2,4,7] + -0.5*[1,2,4] + -1*[2,5,7] + -0.5*[2,7,8] + -0.5*[2,3,8] + -0.5*[0,3,8]
110: [Feasible][P2][det(B)=2][z=6.25][E=[3,6,8];L=[6,8]]
	 x = 0.5*[3,6] + 0.5*[0,1] + 0.5*[6,7] + 0.5*[1,2] + 0.5*[7,8] + 0.5*[2,3] + -0.5*[0,8]; y = 0.5*[0,4,6] + -0.5*[0,3,6] + -0.5*[0,1,4] + -0.5*[4,6,7] + -0.5*[2,4,7] + -0.5*[1,2,4] + -1*[2,5,7] + -0.5*[2,7,8] + -0.5*[2,3,8] + -0.5*[0,3,8]
...
112: [Optimal][P2][det(B)=1][z=6][E=;L=[3,6]]
	 x = 1*[6,7] + 1*[7,8] + -1*[6,8]; y = -1*[0,1,4] + -1*[1,2,4] + -1*[2,5,7] + -1*[2,3,8] + -1*[0,3,8] + -1*[3,6,8]

However, the final solution w as integral. I tried making the basis the optimal basis with the following ILP:

$$\begin{array}{rlr}& \underset{{\mathbf{b}}^{+},{\mathbf{b}}^{-},k}{\mathrm{minimize}}& \sum _{i=1}^n(b_i^{+}+b_i^{-})\\ & \text{subject to}& B^{-1}({\mathbf{b}}^{+}-{\mathbf{b}}^{-})\ge 0\\ & & G({\mathbf{b}}^{+}-{\mathbf{b}}^{-})=2k+1\\ & & {\mathbf{b}}^{+},{\mathbf{b}}^{-}\in {\mathbb{Z}}_{\ge 0}^n\end{array}$$

The vector $\mathbf{b}={\mathbf{b}}^{+}-{\mathbf{b}}^{-}$ again had an intermediate BFS with a fractional solution, but the optimal BFS had an integral solution. However this approach is flawed, we want to minimize $\Vert {\mathbf{x}}_B\Vert =\Vert B^{-1}\mathbf{b}\Vert$. Thus, we consider the following MILP (which does not capture $\lambda$):

$$\begin{array}{rlrlr}& \underset{\mathbf{b},\mathbf{x},k}{\mathrm{minimize}}& \sum _{i=1}^n{x}_i& & \\ & \text{subject to}& B^{-1}\mathbf{b}\ge 0& & \\ & & G\mathbf{b}=2k+1& & \\ & & x_i\ge (B^{-1}\mathbf{b}{)}_i& & \forall i\\ & & \mathbf{b}\in {\mathbb{Z}}^n,k\in \mathbb{Z},\mathbf{x}\in {\mathbb{R}}_{\ge 0}^n& & \end{array}$$

This results in the following solution:

$$\begin{array}{rl}\mathbf{b}& =[3,6]-[0,4]+[0,3]+[0,1]+[6,7]+[2,4]+[1,2]+[7,8]-[2,8]+[3,8]+[2,3]-[0,8].\end{array}$$

Again it made an intermediate BFS have a fractional solution, but it failed to make $B$ the optimal basis:

 92: [Feasible][P2][det(B)=2][z=5.75][E=[0,1];L=[0,6]]
	 x = 0.5*[3,6] + 0.5*[0,1] + 0.5*[6,7] + 0.5*[1,2] + 0.5*[7,8] + 0.5*[2,3] + -0.5*[0,8]; y = 0.5*[3,4,6] + -0.5*[0,3,4] + -0.5*[0,1,4] + -0.5*[4,6,7] + -0.5*[2,4,7] + -0.5*[1,2,4] + -0.5*[2,7,8] + -0.5*[2,3,8] + -0.5*[0,3,8]
 93: [Feasible][P2][det(B)=2][z=5.75][E=[3,4];L=[0,4]] 
	 x = 0.5*[3,6] + 0.5*[0,1] + 0.5*[6,7] + 0.5*[1,2] + 0.5*[7,8] + 0.5*[2,3] + -0.5*[0,8]; y = 0.5*[3,4,6] + -0.5*[0,3,4] + -0.5*[0,1,4] + -0.5*[4,6,7] + -0.5*[2,4,7] + -0.5*[1,2,4] + -0.5*[2,7,8] + -0.5*[2,3,8] + -0.5*[0,3,8]
 94: [Feasible][P2][det(B)=2][z=5.75][E=[3,6,8];L=[6,8]]
	 x = 0.5*[3,6] + 0.5*[0,1] + 0.5*[6,7] + 0.5*[1,2] + 0.5*[7,8] + 0.5*[2,3] + -0.5*[0,8]; y = 0.5*[3,4,6] + -0.5*[0,3,4] + -0.5*[0,1,4] + -0.5*[4,6,7] + -0.5*[2,4,7] + -0.5*[1,2,4] + -0.5*[2,7,8] + -0.5*[2,3,8] + -0.5*[0,3,8]
...
 96: [Optimal][P2][det(B)=1][z=5.5][E=;L=[3,6]] 
	 x = 1*[6,7] + 1*[7,8] + -1*[6,8]; y = -1*[0,1,4] + -1*[1,2,4] + -1*[2,3,8] + -1*[0,3,8] + -1*[3,6,8]

Given that $B$ was originally found by setting $\lambda =0.5$, we either need to find a way to incorporate $\lambda$ in the above MILP, or find a non-unimodular basis with $\lambda =1$. We can capture $\lambda$ by noting which columns of $B$ correspond to triangles. Let

$$\mathcal{T}=\{1,2,4,5,6,7,8,10,12,13,15,17,19,21,22,25\}$$

be the indices of basic variables corresponding to triangles. Then we can capture $\lambda$ in our MILP by modifying the objective:

$$\begin{array}{rlrlr}& \underset{\mathbf{b},\mathbf{x},k}{\mathrm{minimize}}& \sum _{i\notin \mathcal{T}}{x}_i+\lambda \sum _{i\in \mathcal{T}}{x}_i& & \\ & \text{subject to}& B^{-1}\mathbf{b}\ge 0& & \\ & & G\mathbf{b}=2k+1& & \\ & & x_i\ge (B^{-1}\mathbf{b}{)}_i& & \forall i\\ & & \mathbf{b}\in {\mathbb{Z}}^n,k\in \mathbb{Z},\mathbf{x}\in {\mathbb{R}}_{\ge 0}^n& & \end{array}$$

However, this resulted in the same solution as before. We can conclude that $B$ is not the optimal basis for any fractional solution.