2026-02-19

I believe I have gotten my LP solver working correctly now (and much faster). That being said, it has yet to successfully solve an OHCP instance due to numerical instability caused by making use of $B^{-1}$. However, based on my observations so far (about 23000 iterations) I have the following conjecture:

Conjecture: Assume we are solving an OHCP instance via revised simplex method. At each iteration, the following two statements hold:

1. The minimum-ratio test results in ${\theta }^{\ast }$ integral.
2. If $B^{-1}$ is not integral, then there is a basic variable $x_i$ such that $x_i=0$, i.e., ${\theta }^{\ast }=0$.

If the above conjecture holds true, then after each iteration the next bfs, $x^{\prime }=x+{\theta }^{\ast }d$ will be integral whenever the current bfs $x$ is integral. Indeed, recall that $d$ is given such that $d_{\mathcal{B}}=-B^{-1}{A}_j$ and $d_j=1$, where $d_{\mathcal{B}}$ is the subvector corresponding to the basis variables $\mathcal{B}$. If $B^{-1}$ is integral, than $d$ would be integral ($A$ is an integral matrix). If $B^{-1}$ is not integral, then by statement 2, $x^{\prime }=x+0d=x$.