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.

Reparing the ILP

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}{ϵ}^{+}+{ϵ}^{-}\\ {\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^{+}+B(y^{-}-y^{+}+k_1)\}=x^{+}+\max \{0,B(y^{-}-y^{+}+k_1\}\\ k_3& \ge \max \{y^{+},y^{-}+k_1\}\end{array}$$

where 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^{+}-B(y^{-}-y^{+}+k_1))+\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 \max \{x_i^{+},x_i^{+}+B(y^{-}-y^{+}+k_1)\}\rceil -2x_i^{+}-B(y^{-}-y^{+}+k_1))\\ & +\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).$$

We can reexpress $F$ as a regression. Using the fact that $\lceil \max \{a,b\}\rceil =\max \{\lceil a\rceil ,\lceil b\rceil \}$, $\max \{a,b\}=(a+b)/2+|a-b|/2$ and $(B{k}_1{)}_i\in \mathbb{Z}$, we get (setting $z=y^{-}-y^{+}+k_1$)

$$\begin{array}{rl}{F}_1(k_1)& =2\max \{\lceil x_i^{+}\rceil ,\lceil x_i^{+}+(Bz{)}_i\rceil \}-2x_i^{+}-(Bz{)}_i\\ & =\left(\lceil x_i^{+}\rceil +\lceil x_i^{+}+(Bz{)}_i\rceil \right)+\left|\lceil x_i^{+}+(Bz{)}_i\rceil -\lceil x_i^{+}\rceil \right|\\ & -2x_i^{+}-(Bz{)}_i\\ & =\left(\lceil x_i^{+}\rceil +\lceil x_i^{+}+(B(y^{-}-y^{+}){)}_i+(B{k}_1{)}_i\rceil \right)\\ & +\left|\lceil x_i^{+}+(B(y^{-}-y^{+}){)}_i+(B{k}_1{)}_i\rceil -\lceil x_i^{+}\rceil \right|\\ & -2x_i^{+}-(B(y^{-}-y^{+}){)}_i-(B{k}_1{)}_i\\ & =\left((B(k_1){)}_i+\lceil x_i^{+}\rceil +\lceil x_i^{+}+(B(y^{-}-y^{+}){)}_i\rceil \right)\\ & +\left|(B{k}_1{)}_i+\lceil x_i^{+}+(B(y^{-}-y^{+}){)}_i\rceil -\lceil x_i^{+}\rceil \right|\\ & -2x_i^{+}-(B(y^{-}-y^{+}){)}_i-(B{k}_1{)}_i\\ & =C_1+\left|(B{k}_1{)}_i-(\lceil x_i^{+}\rceil -\lceil x_i^{+}-(B(y^{+}-y^{-}){)}_i)\right|\end{array}$$

for some constant $C_1$. Using the same tricks on the right-hand sum, we get

$$\begin{array}{rl}{F}_2(k_1)& =2\max \{\lceil y_j^{+}\rceil ,\lceil y_j^{-}+k_{1,j}\rceil \}-y_j^{+}-y_j^{-}-k_{1,j}\\ & =(\lceil y_j^{+}\rceil +\lceil y_j^{-}+k_{1,j}\rceil )+\left|\lceil y_j^{-}+k_{1,j}\rceil -\lceil y_j^{+}\rceil \right|\\ & -y_j^{+}-y_j^{-}-k_{1,j}\\ & =C_2+\left|k_{1.j}-\left(\lceil y_j^{+}\rceil -\lceil y_j^{-}\rceil \right)\right|.\end{array}$$

Thus, defining ${\alpha }_i=\lceil x_i^{+}\rceil -\lceil x_i^{+}-B(y^{+}+-y^{-})\rceil$ and ${\beta }_i=\lceil y_j^{+}\rceil -\lceil y_j^{-}\rceil$,

$$F(k_1)=C+\Vert \mathbf{w}\odot (B{k}_1-\alpha ){\Vert }_1+\lambda \Vert \mathbf{v}\odot (k_1-\beta ){\Vert }_1$$

where $C=C_1+C_2$ is some constant and $\odot$ is the Hadamard product.

We clean clean this up by a change of variables $d=k_1-\beta$: defining $r=\alpha -B\beta$ to get

$$\underset{k_1\in {\mathbb{Z}}^n}{\min }F(k_1)=C+\underset{d\in {\mathbb{Z}}^n}{\min }\left(\Vert \mathbf{w}\odot (Bd-r){\Vert }_1+\lambda \Vert \mathbf{v}\odot d{\Vert }_1\right).$$

Using the homology condition, one gets that

$$r=\lceil x^{+}\rceil -\lceil x^{-}\rceil -B(\lceil y^{+}\rceil -\lceil y^{-}\rceil )-c,$$

i.e., $r$ measures how non-homologous the rounded solution is to $c$.

Finding the Minimum Pertubation

Let $d^{\ast }$ be the optimal integer vector for the problem. Then it follows that for the trivial point $0\in {\mathbb{Z}}^n$:

$$\Vert \mathbf{w}\odot (B{d}^{\ast }-r){\Vert }_1+\lambda \Vert \mathbf{v}\odot d^{\ast }{\Vert }_1\le \Vert \mathbf{w}\odot (B0-r){\Vert }_1+\lambda \Vert \mathbf{v}\odot 0{\Vert }_1=\Vert \mathbf{w}\odot r{\Vert }_1.$$

Thus, for all other cases, one needs to search the set

$$\mathcal{L}=\left\{d\in {\mathbb{Z}}^n:\Vert \mathbf{w}\odot (Bd-r){\Vert }_1+\lambda \Vert \mathbf{v}\odot d{\Vert }_1\le \Vert \mathbf{w}\odot r{\Vert }_1\right\}.$$

Lemma 1: If $u=(x^{+},x^{-},y^{+},y^{-})$ is integral, then $\Delta u=0$.

Proof. Notice that

$$r=\lceil x^{+}\rceil -\lceil x^{-}\rceil -B(\lceil y^{+}\rceil -\lceil y^{-}\rceil )-c=x^{+}-x^{-}-B(y^{+}-y^{-})-c=0.$$

From above it follows that $d=0$, i.e., $k_1=\lceil y^{+}\rceil -\lceil y^{-}\rceil =y^{+}-y^{-}$. Thus, we get that

$$k_2=\max \{x^{+},x^{+}+B(y^{-}-y^{+}+k_1)\}=\max \{x^{+},x^{+}\}=x^{+}$$

and

$$k_3=\max \{y^{+},y^{-}+k_1\}=\max \{y^{+},y^{+}\}=y^{+}.$$

Therefore, it follows that

$$\Delta u=\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}{x}^{+}-x^{+}\\ x^{+}-x^{+}-B0\\ y^{+}-y^{+}\\ y^{+}-y^{-}-(y^{+}-y^{-})\end{array}\right]=0.\square$$

Theorem 2: If $d^{\ast }=0$, then we can repair our LP by rounding.

Proof. Assume that $d^{\ast }=0$ which implies that $k_1=\lceil y^{+}\rceil -\lceil y^{-}\rceil$. Denote the residuals ${ϵ}^{\pm }=\lceil x^{\pm }\rceil -x^{\pm }$ and ${\delta }^{\pm }=\lceil y^{\pm }\rceil -y^{\pm }$. Then we get that

$$\begin{array}{rl}{k}_2& =\lceil \max \{x^{+},x^{+}+B(y^{-}-y^{+}+k_1)\}\rceil \end{array}$$

and

$$k_3=\lceil \max \{y^{+},y^{-}+\lceil y^{+}\rceil -\lceil y^{-}\rceil \}\rceil =\lceil y^{+}\rceil .$$

Hence,

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

Therefore, we can obtain the integral solution by setting $y^{+}=\lceil y^{+}\rceil$, $y^{-}=\lceil y^{-}\rceil$ and computing

$$x=c+B(\lceil y^{+}\rceil -\lceil y^{-}\rceil ).\square$$

Future Directions: At this point it would likely be best to pursue which instances correspond to $d^{\ast }=0$. One approach is determining which $r$ vectors result in $\mathcal{L}=\{0\}$ and relating it back to $B$.

---

Update 8/20:

Theorem 3: If $\Vert r{\Vert }_{\infty }\le \frac{1}{2}$, then $d^{\ast }=0$.

Proof. Define $f(d)=\Vert \mathbf{w}\odot (Bd-r){\Vert }_1+\lambda \Vert \mathbf{v}\odot d{\Vert }_1$. Notice that $d\in \mathcal{L}$ if and only if $f(d)-f(0)\le 0$ and

$$f(d)-f(0)=\lambda \Vert v\odot d{\Vert }_1-\sum _{i=1}^n{w}_i{h}_i((Bd{)}_i)$$

where $h_i(a)=|r_i|-|a-r_i|$. We consider two cases:

• Case 1 ($(Bd{)}_i=0$): then it follows that $h_i(a)=0$
• Case 2 ($(Bd{)}_i\ne 0$): Notice that $B_{ij}\in \{-1,0,1\}$ so $|a|\ge 1$. Using the reverse triangle inequality, we get that

$$|a-r_i|\ge |a|-|r_i|\ge 1-|r_i|\ge 2|r_i|-|r_i|=|r_i|⟹h_i(a)\le 0.$$

Therefore, in either case, $h_i\le 0$ which implies that

$$\sum _{i=1}^n{w}_i{h}_i((Bd{)}_i)\le 0.$$

Assume that $d\ne 0$, i.e., $|d_j|\ge 1$ for some $j$. Then it follows that

$$f(d)-f(0)\ge \lambda \Vert v\odot d{\Vert }_1\ge \lambda \underset{i}{\max }{v}_i>0,$$

thus $d\notin \mathcal{L}$. $\square$

Question: What assumptions about the simplicial complex must be made in order for

$$\Vert r{\Vert }_{\infty }={\Vert \lceil x^{+}\rceil -\lceil x^{-}\rceil -B(\lceil y^{+}\rceil -\lceil y^{-}\rceil )-c\Vert }_{\infty }<\frac{1}{2}?$$

---

Let $b_i$ to be the $i$th row of $B$ written as a column vector and define $f:{\mathbb{R}}^n\to \mathbb{R}$ by

$$\begin{array}{rl}f(d)& =\Vert w\odot (Bd-r){\Vert }_1+\lambda \Vert v\odot d{\Vert }_1\\ & =\sum _{i=1}^m{w}_i|(Bd{)}_i-r_i|+\lambda \sum _{j=1}^n{v}_j|d_i|\\ & =\sum _{i=1}^m{w}_i|b_i^{\top }d-r_i|+\sum _{j=1}^n\lambda v_j|d_i|\\ & =\sum _{i=1}^m{\phi }_i(d)+\sum _{j=1}^n{\psi }_j(d).\end{array}$$

Recall that a subgradient of a convex function $f$ at $x_0\in {\mathbb{R}}^n$ is a vector $g\in {\mathbb{R}}^n$ such that

$$f(x)-f(x_0)\ge g^{\top }(x-x_0)\forall x.$$

Denote by $\partial f(x)$ the set of all subgradients of $f$ at $x$. For example, for $f(x)=\Vert x{\Vert }_1$ we get

$$g_i=\{\begin{array}{ll}\{1\}& x_i>0\\ [-1,1]& x_i=0\\ \{-1\}& x_i<0\end{array}$$

where $e_i$ is the $i$-th standard basis vector for ${\mathbb{R}}^n$. A crucial property is that $x_0$ is a global minimum if and only if $0\in \partial f(x_0)$. See Ryan Tibshirani’s notes for more details.

We note the following properties:

• $\partial (\alpha f)=\alpha \partial f$
• $\partial (f_1+f_2)=\partial f_1+\partial f_2$
• $\partial [f(Ax)+b]=A^{\top }\partial f(Ax+b)$

Lemma 4: $\partial [f(b_i^{\top }d-r_i)]=b_i\partial f(b_i^{\top }-r_i)$

Proof. TODO $\square$

Notice that

$$\begin{array}{r}\partial {\phi }_i(0)=w_i\partial |b_i^{\top }d-r_i|=\{\begin{array}{ll}\{-w_i{b}_i\}& r_i>0\\ \{t{w}_i{b}_i:t\in [-1,1]\}& r_i=0\\ \{w_i{b}_i\}& r_i<0\end{array}\end{array}$$

which implies that

$$\begin{array}{rl}\partial \left[\sum _{i=1}^m{\phi }_i(0)\right]& =-\sum _{i=1}^m{w}_i\text{sgn}(r_i)b_i+\sum _{i:r_i=0}{w}_i[-1,1]b_i\end{array}$$

Next

$$\partial {\phi }_j(0)=\lambda v_j\partial |d_i|=\{\lambda t{v}_j{e}_j:t\in [-1,1]\}$$

so

$$\partial \left[\sum _{j=1}^n{\psi }_j(0)\right]=\sum _{j=1}^n\lambda [-1,1]v_j{e}_j=\{g\in {\mathbb{R}}^n:|g_j|\le \lambda v_j\},$$

an axis-aligned box. Therefore, as a Minkowski sum we get

$$\partial f(0)=-B^{\top }(w\odot \text{sgn}(r))+K+\mathcal{B}$$

where (defining $Z=\{i:r_i=0\}$)

$$\begin{array}{rl}K& =\left\{\sum _{i\in Z}{t}_i{w}_i{b}_i:t\in [-1,1{]}^{|Z|}\right\}\\ \mathcal{B}& =\{g\in {\mathbb{R}}^n:|g_j|\le \lambda v_j\}.\end{array}$$

It is not clear as to what $r$ vectors correspond to $0\in \partial f(0)$.