Algorithm for solving a mixed integer programming problem in polynomial time? I have the following mixed integer programming (MIP) problem:
$$
\begin{array}{rll}
\text{Maximize } &amp; z=k \\
\text{subject to }
&amp; a_ik - m_i \geq 0 &amp; (i=1,\dots,n) \\
&amp; b_ik - m_i \leq 1 &amp; (i=1,\dots,n) \\
\text{where}
&amp; k \in \mathbb{R}_{\geq 0}, m_i \in \mathbb{N}_0 &amp; (i=1,\dots,n),
\end{array}
$$
where $a_i,b_i$ are non-negative real numbers such that $0 \leq a_1 &lt; b_1 &lt; a_2 &lt; b_2 &lt; \dots &lt; a_n &lt; b_n$ (defining $n$ &quot;forbidden intervals&quot; $(a_i,b_i)$), $k$ is an unknown repetition frequency, and $m_1,\dots,m_n$ are unknown integers (telling how many repetitions will occur before the different intervals).
(Alternatively, the MIP-problem can be rephrased as &quot;Find the minimal $x \in \mathbb{R}_{&gt;0}$ such that $mx\not\in(a_i,b_i)\ \forall\ m\in\mathbb{N},i\in\{1,\dots,n\}$&quot;. It is by defining $k=1/x$, and $m_i$ as the largest non-negative integer for which $m_i x \leq a_i$, that the MIP formulation can be obtained.)
I need to either come up with an algorithm to solve this problem in polynomial time, or prove that the problem is NP-hard (or NP-intermediate if not NP-hard, I guess). I have tried to come up with a poly-time algorithm but not been successful, but I don't really know how to prove NP-hardness either.
How can I prove that this problem is NP-hard, or alternatively, is there some algorithm with a polynomial (in terms of the input size, i.e., the size required to store the input in memory) worst-case time complexity that can solve it?
In general, how do one prove NP-hardness? What I understand, for a given problem H, if every problem in NP problem can be reduced H in polynomial time, then H is NP-hard. But how do I prove that this is the case? There has to be close to infinitely many problems in NP, so is it enough to show for one of the problems that are NP-complete that it can be reduced to H in polynomial time? Is there some list of NP-complete problems that I can look at to try to prove that this MIP problem is NP-hard?
Finding an upper limit for k is trivial. Let d be the minimum of $b_i - a_i$ over all i, then k ≤ floor (1 / d).
And for each k up to the upper limit, it is trivial to check that floor ($a_i \cdot k$) = floor ($b_i \cdot k$).