3
$\begingroup$

Let $\mathcal{F}$ be a family of pairs of the form $(A,b)$, where $A$ is an integer matrix and $b$ is an integer vector with the same number of rows. For every integer $k$, define $L(\mathcal{F}, k)$ to be the following family of decision problems.

INPUT: a pair $(A,b)\in \mathcal{F}$.

OUTPUT: "True" if there exists a real vector $x \geq 0$ satisfying $A x \leq b$, where for every $i > k$, $x_i$ must be an integer (for $i\leq k$, $x_i$ can be any real number).

If $k=0$, then these are simply integer programming problems, and $L(\mathcal{F}, k)$ is NP-hard in general. But it is in P for some subclasses of matrices and vectors, for example, when for all $(A,b)\in \mathcal{F}$, the matrix $A$ is of totally unimodular.

I am interested in the effect of $k$ on the complexity of $L(\mathcal{F}, k)$. In particular, if $L(\mathcal{F}, k)$ is in P for some $k$, does it imply that $L(\mathcal{F}, k+1)$ is in P too?

Stated informally: if we take a single discrete variable and allow it to be continuous, does the problem remain tractable?

EDIT: Here is an example showing that the opposite is possible: if we start from an NP-hard problem, and convert a single discrete variable to continuous, the problem may become tractable. Consider the following family of linear programs: $$ a_1 x_1 + \cdots + a_n x_n = (a_1+ \cdots +a_n)/2 \\ 0 \leq x_i \leq 1 ~~~ \forall i\in\{1,\ldots,n\} \\ x_i \in \mathbb{Z} ~~~ \forall i\in\{1,\ldots,n\} $$ where the input is the integer vector $a_1,\ldots,a_n$ and the output is "true" if there is a vector $x_1,\ldots,x_n$ satisfying the constraint. This LP represents the NP-hard partition problem.

Suppose w.l.o.g. that the input arrives in descending order ($a_1\geq \cdots \geq a_n$). Then, if we allow a single variable $x_1$ to be continuous (we remove the constraint $x_1\in \mathbb{Z}$), then the problem becomes tractable: if the largest item can be split, then the answer is always "yes". So, $L(\mathcal{F}, 1)$ is in $P$ while $L(\mathcal{F}, 0)$ is NP-hard.

Is there an $\mathcal{F}$ for which the opposite holds --- $L(\mathcal{F}, 1)$ is in $P$ while $L(\mathcal{F}, 0)$ is NP-hard?

EDIT 2: Note that, without the restriction to linear problems, even making all variables continuous might make a problem harder. See this answer.

$\endgroup$
2
  • $\begingroup$ In some cases, yes! For example, when number of integer variables are bounded by some constant. $\endgroup$ Commented Apr 21, 2023 at 14:41
  • $\begingroup$ I do not understand. Can you elaborate? $\endgroup$ Commented Apr 22, 2023 at 20:13

1 Answer 1

1
$\begingroup$

If a linear program has some integer and continuous variables, then the problem is known as Mixed-Integer Linear Program. Moreover, if the number of integer variables are constant, then the problem can be solved in polynomial time (see Proposition 8.1 from here).

Therefore, if any $L(\mathcal{A}, \mathcal{B}, k)$ is in $\mathsf{P}$ for some $k$, and suppose that $n-k = O(1)$ where $n$ is the number of elements in $x$. Then, it trivially implies that $L(\mathcal{A}, \mathcal{B}, k+1)$ is in $\mathsf{P}$ too, since $L(\mathcal{A}, \mathcal{B}, k+1)$ can be solved in polynomial time (there are at most $n-k-1 = O(1)$ integer variables in $L(\mathcal{A}, \mathcal{B}, k+1)$).

$\endgroup$
2
  • $\begingroup$ This assumes that $n-k= O(1)$. What if this is not the case? $\endgroup$ Commented Apr 25, 2023 at 13:25
  • $\begingroup$ @ErelSegal-Halevi Yes! I will think/search on it. $\endgroup$ Commented Apr 25, 2023 at 14:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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