2026-07-21

I spent some time exploring the parameter space for the example given in 2026-07-09. More specifically, I modified the weights of triangles as follows:

$$v_i=\{\begin{array}{ll}{\theta }_1& \text{ if yi is not a Mobius triangle}\\ {\theta }_2& \text{ if yi is a Mobius triangle.}\end{array}$$

I then did an exhaustive computation of $({\theta }_1,{\theta }_2)\in [0.1,3]\times [0.1,3]$ with a step size of $\Delta {\theta }_i=0.01$. For each set of weights, I solved the flat norm LP and stored the objective value $z^{\ast }$, and whether ${\mathbf{y}}^{\ast }$ is integral. In other words, I looked at the following map:

$$f({\theta }_1,{\theta }_2)=\{\begin{array}{ll}(z^{\ast },1)& \text{if }{\mathbf{y}}^{\ast }\in {\mathbb{Z}}^n\\ (z^{\ast },0)& \text{if }{\mathbf{y}}^{\ast }\notin {\mathbb{Z}}^n.\end{array}$$

I then plotted this map using a contour plot:

We find the following interesting facts:

• Every fractional solution $(z^{\ast },{\mathbf{x}}^{\ast },{\mathbf{y}}^{\ast })$ has a corresponding integral solution with the same objective $z^{\ast }$.
• For each objective value $z^{\ast }$, its corresponding parameter space is divided into two parts: fractional vertices and integral vertices.

My idea is as follows:

1. Compute the flat norm LP
2. If the solution is fractional, tweak the weights so that we get an equivalent integral solution.

This strategy requires us to have a strong understanding of the parameter space. That is, fix $K$ and $c$ and look at the space $\theta =(\mathbf{w},\lambda \mathbf{v})$. Assume that the LP gave $z=3.00009$ as in our example. For any vertex of the LP $u=(\mathbf{x},\mathbf{y})$, consider $g(u)=({\mathbf{x}}^{+}+{\mathbf{x}}^{-},{\mathbf{y}}^{+}+{\mathbf{y}}^{-})$. Then our objective is given by

$$z(\theta ,u)=⟨\theta ,g(u)⟩.$$

We want to look at the following hypersurface in ${\mathbb{R}}_{\ge 0}^{2N-1}$ where $N=m+n$:

$$\begin{array}{rl}{\mathcal{S}}_{z^{\ast }}& =\{\theta \ge 0,u\ge 0:z(\theta ,u)=z^{\ast }\}\\ & =\{\theta \ge 0,u\ge 0:\sum _{i=1}^N{\theta }_i(g(u){)}_i=z^{\ast }\}.\end{array}$$

Notice that the map $z:{\mathbb{R}}^{2N}\to \mathbb{R}$ is smooth and ${\nabla }_{\theta }z=g(u)$ on $\mathcal{S}$. One approach to this is as follows:

1. Set ${\theta }_0$ by the given parameters.
2. Solve the flat norm LP to find $u_0$, record the objective value $z^{\ast }$.
3. At step $k$, do the following:
   1. If $u_k\in {\mathbb{Z}}^N$, stop.
   2. Otherwise, set ${\theta }_{k+1}={\theta }_k+{\rho }_{k}g(u_k)$
   3. Find $u_{k+1}$ such that $({\theta }_{k+1},u_{k+1})\in {\mathcal{S}}_{z^{\ast }}$.

The difficult step is projecting back into ${\mathcal{S}}_{z^{\ast }}$. Let $u_{k+1}=\mu u_k$. Notice that

$$\begin{array}{rl}{z}^{\ast }& =z({\theta }_{k+1},u_{k+1})\\ & =⟨{\theta }_{k+1},\mu u_k⟩\\ & =\mu ⟨{\theta }_{k+1},u_k⟩\end{array}$$

implies that

$$\mu =\frac{z^{\ast }}{⟨{\theta }_{k+1},u_k⟩}.$$

So, we get back to ${\mathcal{S}}_{\ast }$ by setting

$$u_{k+1}=\frac{z^{\ast }}{⟨{\theta }_{k+1},u_k⟩}{u}_k.$$

However, this doesn’t respect the homology constraints. Notice that

$$\begin{array}{rl}\mu ({\mathbf{x}}^{+}-{\mathbf{x}}^{-})-\mu B({\mathbf{y}}^{+}-{\mathbf{y}}^{-})& =\mu \mathbf{c}\ne \mathbf{c}.\end{array}$$

Adding a vector to $u_k$ might work. Notice that

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

I’m not sure what to set $ϵ$ to. We need

$$⟨{\theta }_{k+1},ϵ⟩=z^{\ast }-⟨{\theta }_{k+1},u_k⟩.$$

What we need to do, is solve the following LP:

$$\begin{array}{rlr}& \text{maximize}& \Vert ϵ\Vert \\ & \text{subject to}& ⟨{\theta }_{k+1},ϵ⟩=z^{\ast }-⟨{\theta }_{k+1},u_k⟩\\ & & ϵ\in {\mathbb{R}}^N\end{array}$$

Call this problem $\mathcal{P}2$ and the flat norm $\mathcal{P}1$. Then our algorithm is as follows:

1. Set ${\theta }_0$ by the given parameters.
2. Solve $\mathcal{P}1$ to find $u_0$, record the objective value $z^{\ast }$.
3. At step $k$, do the following:
   1. If $u_k\in {\mathbb{Z}}^N$, stop.
   2. Otherwise, set ${\theta }_{k+1}={\theta }_k+{\rho }_{k}g(u_k)$
   3. Find $u_{k+1}$ by solving $\mathcal{P}2$.

However, I don’t know if this will converge and if it does, converge in a linear number of steps. Maybe there is a fast way to solve $\mathcal{P}2$?