2026-08-17

Our current goal is: given a fractional solution to the flat norm LP, determine the integral solution to the ILP in polynomial time. On 2026-07-21 I gave a so called “tangent-descent” method which walked through the parameter space in order to find an integral solution. While it happened to work in this particular instance, I don’t think it will work in general. Mainly, I do not think the approach is sound and it assumes that every fractional solution has a corresponding integral solution with the same objective, which I do not believe to be true.

Notice that two basic solutions $u_1$ and $u_2$ are simultaneously optimal for parameters $\theta =(\mathbf{v},\lambda \mathbf{v})$ if $⟨\theta ,g(u_1)-g(u_2)⟩=0$ where $g(u)=(\mathbf{x},\mathbf{y})$. Thus, given fractional, optimal $u_1$ we seek $u_2$ such that $⟨\theta ,g(u_1)-g(u_2)⟩=0$. Thus, instead of changing $\theta$, we should find $u_2\in {\mathbb{Z}}^N$ such that $g(u_1)-g(u_2)$ is orthogonal to $\theta$. This leads to the following ILP:

$$\begin{array}{rlr}& \text{minimize}& \Vert g(u_2){\Vert }_1\\ & \text{subject to}& ⟨\theta ,g(u_1)-g(u_2)⟩=0\\ & & \mathbf{x}-[\partial ]\mathbf{y}=\mathbf{c}\\ & & u_2=(\mathbf{x},\mathbf{y})\ge 0\end{array}$$

which is just as hard as solving it as an ILP from the start.

Borrowing from 2026-07-21, let $u^{\prime }=u+\Delta u$ where $\Delta u=({ϵ}^{+},{ϵ}^{-},{\delta }^{+},{\delta }^{-})$. Then it follows that

$$⟨\theta ,g(u^{\prime })-g(u)⟩=⟨\theta ,g(u)+g(\Delta )-g(u))⟩=⟨\theta ,g(\Delta u)⟩$$

as $g$ is linear. Then we can rewrite our ILP as follows:

$$\begin{array}{rlr}& \text{minimize}& \Vert \Delta u{\Vert }_1\\ & \text{subject to}& ⟨\theta ,g(\Delta u)⟩=0\\ & & (\mathbf{x}+ϵ)-B(\mathbf{y}+\delta )=\mathbf{c}\\ & & u+\Delta u\in {\mathbb{Z}}^N\\ & & \Delta u=({ϵ}^{+},{ϵ}^{-},{\delta }^{+},{\delta }^{-})\ge 0\end{array}$$

But this still has our unfriendly integer constraint $u+\Delta u\in {\mathbb{Z}}^N$.

Consider the homology constraints:

$$\begin{array}{rlrl}& & ({\mathbf{x}}^{+}+{ϵ}^{+}-{\mathbf{x}}^{-}-{ϵ}^{-})-B({\mathbf{y}}^{+}+{\delta }^{+}-{\mathbf{y}}^{-}-{\delta }^{-})-\mathbf{c}& =0\\ -& & ({\mathbf{x}}^{+}-{\mathbf{x}}^{-})-B({\mathbf{y}}^{+}-{\mathbf{y}}^{-})-\mathbf{c}& =0\\ & & ({ϵ}^{+}-{ϵ}^{-})-B({\delta }^{+}-{\delta }^{-})& =0\end{array}$$

implying that the set of $\Delta u$ which preserve the homology must satisfy the equation

$$\left[\begin{array}{cccc}I& -I& -B& B\end{array}\right]\left[\begin{array}{c}{ϵ}^{+}\\ {ϵ}^{-}\\ {\delta }^{+}\\ {\delta }^{-}\end{array}\right]=0,$$

i.e., belong to the kernel of $\left[\begin{array}{cccc}I& -I& -B& -B\end{array}\right]$. Define $r={ϵ}^{-}$, $q={\delta }^{-}$, $z={\delta }^{+}-{\delta }^{-}$, then it follows that

$$\text{ker}A=\left\{\left[\begin{array}{c}r+Bz\\ r\\ q+z\\ q\end{array}\right]:r\in {\mathbb{R}}^m,q,z\in {\mathbb{R}}^n\right\}$$

which implies that $\text{nullity}A=m+2n$. Indeed, I claim the basis for $A$ is given by

$$\Gamma =\left[\begin{array}{ccc}{I}_m& 0& B\\ I_m& 0& 0\\ 0& I_n& I_n\\ 0& I_n& 0\end{array}\right].$$

Notice that

$$\begin{array}{rl}A\Gamma & =\left[\begin{array}{cccc}{I}_m& -I_m& -B& B\end{array}\right]\left[\begin{array}{ccc}{I}_m& 0& B\\ I_m& 0& 0\\ 0& I_n& I_n\\ 0& I_n& 0\end{array}\right]\\ & =\left[\begin{array}{c}{I}_m-I_m\\ -B+B\\ B-B\end{array}\right]\\ & =0.\end{array}$$

Thus, any homology preserving perturbation is of the form

$$\Delta u=\left[\begin{array}{ccc}{I}_m& 0& B\\ I_m& 0& 0\\ 0& I_n& I_n\\ 0& I_n& 0\end{array}\right]\left[\begin{array}{c}r\\ q\\ z\end{array}\right]=\left[\begin{array}{c}r+Bz\\ r\\ q+z\\ q\end{array}\right].$$

Looking at the integrality constraint, we get that

$$\begin{array}{rl}{u}^{\prime }\in {\mathbb{Z}}^{2N}& ⟺u+\Delta u\in {\mathbb{Z}}^{2N}\\ & ⟺\Delta u\equiv -u\mathrm{mod}\mathbb{Z}\\ & ⟺\left[\begin{array}{c}r+Bz\\ r\\ q+z\\ q\end{array}\right]\equiv -\left[\begin{array}{c}{x}^{+}\\ x^{-}\\ y^{+}\\ y^{-}\end{array}\right]\mathrm{mod}\mathbb{Z}.\end{array}$$

Combining equations, we get that

$$\left[\begin{array}{c}Bz\\ z\end{array}\right]\equiv \left[\begin{array}{c}{x}^{-}-x^{+}\\ y^{-}-y^{+}\end{array}\right]\mathrm{mod}\mathbb{Z}.$$

The second equation is easily satisfiable by saying that

$$z=y^{-}-y^{+}+k_1$$

for some $k_1\in {\mathbb{Z}}^n$. Solving for $r$ gives us that

$$\begin{array}{rl}r& =-Bz-x^{+}+k_2\\ & =-B(y^{-}-y^{+}+k_1)-x^{+}+k_2\end{array}$$

for some $k_2\in {\mathbb{Z}}^m$. Solving for $q$ gives us that

$$\begin{array}{rl}q& =-z-y^{+}+k_3\\ & =(y^{+}-y^{-}-k_1)-y^{+}+k_3\\ & =-y^{-}-k_1+k_3\end{array}$$

for $k_3\in {\mathbb{Z}}^n$. Thus, our search space is restricted to

$$\Omega =\left\{\left[\begin{array}{c}-B(y^{-}-y^{+}+k_1)-x^{+}+k_2\\ -y^{-}-k_1+k_3\\ y^{-}-y^{+}+k_1\end{array}\right]:k_2\in {\mathbb{Z}}^m,k_1,k_3\in {\mathbb{Z}}^n\right\}$$

which can be reexpressed by $\Omega ={\alpha }_0+K{\mathbb{Z}}^{m+2n}$ where

$${\alpha }_0=\left[\begin{array}{c}-B(y^{-}-y^{+}+k_1)-x^{+}+k_2\\ -y^{-}-k_1+k_3\\ y^{-}-y^{+}+k_1\end{array}\right]\text{ and }K=\left[\begin{array}{ccc}-B& I_m& 0\\ -I_n& 0& I_n\\ I_n& 0& 0\end{array}\right].$$

Therefore, our new repair ILP is given by

$$\begin{array}{rlr}& \text{minimize}& \Vert d+Mk{\Vert }_1\\ & \text{subject to}& ⟨\theta ,g(d+Mk)⟩=0\\ & & d+Mk\ge 0\\ & & k\in {\mathbb{Z}}^{m+2n}\end{array}$$

where $d=\Gamma {\alpha }_0$ and $M=\Gamma K$. Unfortunately, this problem appears to still be NP-hard.

This also assumes that each fractional solution has an equivalent integral solution. We forgo this assumption by a slight tweak:

$$\begin{array}{rlr}& \text{minimize}& ⟨\theta ,g(d+Mk)⟩\\ & \text{subject to}& d+Mk\ge 0\\ & & k\in {\mathbb{Z}}^{m+2n}\end{array}$$

Note that

$$\Delta u=d+Mk=\left[\begin{array}{c}{k}_2-x^{+}\\ k_2-x^{+}-B(y^{-}-y^{+}+k_1)\\ k_3-y^{+}\\ k_3-y^{-}-k_1\end{array}\right]=\left[\begin{array}{c}{ϵ}^{+}\\ {ϵ}^{-}\\ {\delta }^{+}\\ {\delta }^{-}\end{array}\right].$$

Thus, it follows that

$$\begin{array}{rl}g(d+Mk)& =\left[\begin{array}{c}{e}^{+}+e^{-}\\ {\delta }^{+}+{\delta }^{-}\end{array}\right]=\left[\begin{array}{c}2k_2-2x^{+}-B(y^{-}-y^{+}+k_1)\\ 2k_3-y^{+}-y^{-}-k_1\end{array}\right],\end{array}$$

i.e.,

$$⟨\theta ,g(d+Mk)⟩={\mathbf{w}}^{\top }\left(2k_2-2x^{+}-B(y^{-}-y^{+}+k_1)\right)+\lambda {\mathbf{v}}^{\top }\left(2k_3-y^{+}-y^{-}-k_1\right).$$

We can also use the constraint $d+Mk\ge 0$ and the convexity of our objective to eliminate $k_2$ and $k_3$. That is, $k_2$ and $k_3$ are the smallest integers such that

$$\begin{array}{rl}{k}_2& \ge \max \{x^{+},x^{+}+Bz\}\\ k_3& \ge \max \{y^{+},y^{-}+k_1\}\end{array}$$

where $z=y^{-}-y^{+}+k_1$ and max is taken elementwise. Thus, we may view $k_2$ and $k_3$ as functions of $k_1$ and all other terms are constants; so our objective can be expressed by

$$F(k_1)={\mathbf{w}}^{\top }(2k_2(k_1)-2x^{+}-Bz)+\lambda {\mathbf{v}}^{\top }(2k_3(k_1)-y^{+}-y^{-}-k_1).$$

Which written as a sum is given by

$$\begin{array}{rl}F(k_1)& =\sum _{i=1}^m{w}_i(2\lceil x_i^{+}+\max \{0,(Bz{)}_i\}\rceil -2x_i^{+}-(Bz{)}_i)\\ & +\lambda \sum _{j=1}^n{v}_j(2\lceil \max \{y_j^{+},y_j^{-}+k_{1,j}\}\rceil -y_j^{+}-y_j^{-}-k_{1,j}).\end{array}$$

Leaving the following integer nonlinear program:

$$\underset{k_1\in {\mathbb{Z}}^n}{\min }F(k_1).$$