4
$\begingroup$

I have the following mixed integer programming (MIP) problem:

$$ \begin{array}{rll} \text{Maximize } & z=k \\ \text{subject to } & a_ik - m_i \geq 0 & (i=1,\dots,n) \\ & b_ik - m_i \leq 1 & (i=1,\dots,n) \\ \text{where} & k \in \mathbb{R}_{\geq 0}, m_i \in \mathbb{N}_0 & (i=1,\dots,n), \end{array} $$

where $a_i,b_i$ are non-negative real numbers such that $0 \leq a_1 < b_1 < a_2 < b_2 < \dots < a_n < b_n$ (defining $n$ "forbidden intervals" $(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 "Find the minimal $x \in \mathbb{R}_{>0}$ such that $mx\not\in(a_i,b_i)\ \forall\ m\in\mathbb{N},i\in\{1,\dots,n\}$". 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?

$\endgroup$
4
  • $\begingroup$ Are you sure the rephrasing is right? Shouldn't it be something like $m_i$ instead of $m$? And something like $m_i x \le a_i$ and $(m_i+1) x \ge b_i$, rather than what you have? Where does the $\forall m \in \mathbb{N}$ come from? $\endgroup$
    – D.W.
    Feb 3 at 1:13
  • $\begingroup$ @D.W. "$\forall\ m\in\mathbb{N}, i\in\{1,\dots,n\}$" means that the expression $mx\not\in(a_i,b_i)$ must hold for all such $m$ and $i$, i.e., that for no such $m$ and $i$ is $mx$ in the given interval. An alternative way to express this would be $\not\exists\ m\in\mathbb{N}, i\in\{1,\dots,n\}\text{ s.t. }mx\in(a_i,b_i)$. Since the expression holds for any combination of $m$ and $i$, if you substitute $m_i$ for $m$, the problem would remain equivalent. $\endgroup$ Feb 3 at 3:35
  • $\begingroup$ Because of transitivity, it is indeed enough to demonstrate a polytime reduction from a single NP-hard problem to your target problem. $\endgroup$
    – Juho
    Feb 3 at 7:21
  • $\begingroup$ "In general, how do one prove NP-hardness? " -> pick any NP-hard problem, and reduce it to the one you want to prove. "reduce" means to find a polynomial algorithm to convert any input parameters and output results of the known problem into equivalent input/output parameters of the new problem (with equivalent input-output relation of course). In other words, if you can prove that an algo which solves the new problem would also solve a known hard problem, you have proven that the new problem is hard. $\endgroup$
    – AnoE
    Jul 16 at 6:55
0
$\begingroup$

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$).

$\endgroup$
2
  • 3
    $\begingroup$ Yup. Unfortunately, this takes exponential time: the running time is exponential in the size of the input (which is proportional to the log of the values), so this doesn't answer whether the task can be solved in polynomial time or not. Also, your answer solves the case where $k$ is required to be integer, but the question seems to allow $k$ to be any real number. $\endgroup$
    – D.W.
    Feb 3 at 1:02
  • $\begingroup$ As D.W. said, $k$ doesn't have to be an integer (I have clarified this in my question), so $k\leq 1/d$, and there are infinitely many $k$ between 0 and this limit. If $k$ would have to be an integer, as you have noted, the algorithm could run in $O(nd)$ time; however, this counts as pseudo-polynomial time. "The input size" refers to the size required to represent the input in memory, which is roughly the number of input elements times the number of bits required to store one input element. $\endgroup$ Feb 3 at 4:03
0
$\begingroup$

Here is a simple algorithm based on the alternative formulation ("Find the minimal $x \in \mathbb{R}_{>0}$..."), for which I have not been able to bound the running time by a polynomial. Briefly, we start at a lower bound and keep increasing $x$ by the minimum "useful" amount (meaning: all smaller increases are known to fail) until we get a feasible solution:

  1. Begin by setting $x = \max_i (b_i-a_i)$. (This is a lower bound, since any smaller choice of $x$ would necessarily cause the longest interval to be hit at least once.) If this choice of $x$ avoids all intervals, we are done; otherwise continue.
  2. Set $x':=x$. We maintain the invariant that all solutions smaller than $x'$ are known to be infeasible.
  3. For each interval $i$:
    1. Determine whether the $i$-th interval is hit by computing $c_i=\lfloor a_i/x\rfloor + 1$ and testing whether $c_ix < b_i$.
    2. If so, set $x_i$ to $x+(b_i-c_ix)/c_i$ and update $x'$ to $\max \{x', x_i\}$. Note that $x_i$ is certainly feasible for the $i$-th interval, because there is at most 1 hit within this interval with the current $x$ (by our initial choice of $x$, and the fact that we only ever increase it), and $x_i$ is the result of increasing $x$ by the smallest amount necessary to slide the hit location to the right endpoint of the interval, which is not enough to introduce a new hit on this interval from the left-hand side.
  4. If any intervals were hit in the previous step, set $x := x'$ and go to 3, otherwise $x$ is the optimal solution.

Where this could be slow is if all intervals are very narrow, and far to the right. It seems plausible to me that some such problem instance could necessitate a long initial sequence of small rightward nudges, each of which produces an $x$ that alleviates the hit for one interval, but reintroduces a hit on some other interval.

$\endgroup$
0
$\begingroup$

Since the value of each $m_i$ doesn't matter (you can assign $m_i=\lfloor a_ik\rfloor$ as far as the $[b_ik-1, a_ik]$ contains an integer), your problem can be re-formulated as:

$$ \begin{align} \max~~& k\\ \text{s.t.}~~& b_ik-1\le \lfloor a_ik\rfloor & \forall i=1, ..., n\tag{1}\\ & k\in\Bbb R_{\ge 0}\\ \text{where}~~& a_i,b_i\in\Bbb R_{\ge0}, ~a_i\lt b_i & \forall i=1,..., n \end{align} $$

The restriction (1) generates a sequence of valid values for each interval $i$, defined by a sequence of disjunt ranges with gaps between them (I use range instead of interval to differentiate from the input):

$$ \def\int#1#2#3#4{\left[\frac{#1}{#2},~\frac{#3}{#4}\right]} %% k\in\mathcal I_i=\int{0}{a_i}{1}{b_i}\bigcup\int{1}{a_i}{2}{b_i}\bigcup\cdots\bigcup\int{q_i^*-1}{a_i}{q_i^*}{b_i}\bigcup\int{q_i^*}{a_i}{q_i^*+1}{b_i}\\ \\ ~\text{where}~q_i^*=\left\lfloor\frac{a_i}{b_i-a_i}\right\rfloor $$

and where the maximum $k_i^*$ for any $i$ is $$ k_i^* = \frac{q_i^*+1}{b_i} = \frac{\left\lfloor\frac{a_i}{b_i-a_i}\right\rfloor+1}{b_i} $$

Given any $\mathcal I_i$, the length of each range in its sequence decreases by $\frac{1}{a_i}-\frac{1}{b_i}$ respect to the previous one, while each gap increases by the same amount. The sequence ends when a next range would give an empty interval, and the size of the sequence is $q_i^* + 1$.

I haven't been able to find any NP-complete problem reducible to yours, but I would go for NP-complete problems related to congruences or algebra. There must be something related there.

Respect to a solution algorithm, just take

$$ k^+=\min_i\left\{k_i^*\right\}=\min_i\left\{\frac{\left\lfloor\frac{a_i}{b_i-a_i}\right\rfloor+1}{b_i}\right\} $$

as initial upper bound, and then, if for some $j$ the restriction (1) is not satisfied, assign

$$ k^+\leftarrow \frac{\left\lfloor\frac{k^+}{b_j}\right\rfloor}{b_j}\tag{2} $$

and repeat (that assignment will give the maximum feasible $k\lt k^+$ for the interval $j$).

This algorithm will run in $O(n\sum_i^n q_i^*)$ in the worst case, which is the size of the input multiplied by the total number of gaps, and thus exponential in the size of the input if codified in binary, or quadratic when codified in unary (each time the algorithm updates $k^+$ is because it falled in some gap, and to know it you have to do $O(n)$ checks; the worst case being when $k^+$ visited all gaps).

In practice, you could improve this algorithm a lot by sorting the intervals by $\frac{1}{a_i}-\frac{1}{b_i}$ in decreasing (non-increasing) order, so when checking the feasibility of $k^+$ you check intervals with bigger gaps first so that the jumps given by (2) are the biggest as possible the sooner as possible (if $a_1=0$ you can just remove the first interval, because the initial $k^+$ will already be $\le\frac{1}{b_1}$).

NOTE: The definition of $\mathcal I_i$ for each interval $i$ can be obtained by calculating the valid values of $k$ so that $\lfloor a_ik\rfloor=q$ and $b_ik-1\leq q$ for some natural number $q$, and $q_i^*$ is the maximum $q$ so that $\frac{q}{a_i}\le \frac{q+1}{b_i}$ holds. Respect to the first equation, consider that $\lfloor a_ik\rfloor=q$ implies $a_ik\le q\lt a_ik + 1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.