In my research, I stumbled upon a problem, that I thought should have an easy solution, but I really cannot figure it out by myself. The setup is the following. Let $A \in \mathbb{N}^{m \times n}$ and $b \in \mathbb{N}^m$. This way we get a system of linear equations $Ax=b$. For my purposes $0 \in \mathbb{N}$ but we will assume that $A$ does not contain any zero-columns and there does actually exist a solution $x \in \mathbb{N}^n$ to the system of equations. Now let $a_j$ be the $j$-th column of $A$. The goal is to find a $\mu \in \mathbb{R}^n$ such that
- $\mu \cdot a_j > 0$ for all $j \in [n]$
- As many columns of $A$ as possible have the same dot product with $\mu$
The bigger the subset of columns with the same dot-product the better my algorithm can get to solve ILPs. It would suffice to find a polynomal time algorithm to determine the biggest subset. So far, I didn't get much further than just trying all possible subsets if there exists such a $\mu$, which is obviously in exponential time.
A bit of context if you are interested
It essentially boils down to minimizing a certain function:
$$k(\mu) = \max_{j \in [m]}\left\{\frac{\mu\cdot b}{\mu\cdot a_j}\right\} =: \max_{j\in[n]}\{k_j(\mu)\}$$
$k$ is only defined on $U = \{\mu \in \mathbb{R}^n\mid \forall a_j\colon \mu \cdot a_j > 0\}$. So $k$ is actually continous.
I found out that $k_j(\mu)$ is either strictly monotone or constant. So $k$ is the upper envelope of monotone functions. Also the boundary of the domain cannot contain the minimum as there $k$ explodes to infinity. So the only interesting regions, where the minimum can be located, are the boundaries between regions where different $k_j$ produce the value of $k$ (meaning its value is larger than all others). In other words, the only interesting regions are those where at lest 2 $k_j$'s have the same value (so $a_{j_1} \cdot \mu = a_{j_2} \cdot \mu$).
But I also found out that $k$ restricted to these boundaries is also either strictly monotone or constant. This fact doesn't change, no matter how many dot products should match.
Thus I concluded, that the only interesting regions are those, where as many dot products as possible match up.
Note: I know, this is definitely not a prove but I am just sharing my intuition for the problem. I would be gladful for some comments on that.