11
$\begingroup$

Given $P = \{x\in\mathbb R^n: Ax \leq b\}$, I want to decide if $(\mathbb Z^\ell \times \mathbb R^{n-\ell}) \cap \operatorname{relint}(P)$ is non-empty.

Is this problem in NP?


One idea is to check if $P_\varepsilon \cap (\mathbb Z^\ell \times \mathbb R^{n-\ell})$ is non-empty by solving a MILP, where $P_\varepsilon = \{x\in\mathbb R^n: Ax \leq b - \varepsilon e\}$ and $e$ is a vector of ones.

But then how do I choose a $\varepsilon$ whose representation is polynomially large in the description of $A$ and $b$, so I don't end up cutting away some integer point?

We can assume $A$ and $b$ to have integer entries only.

I think, if I have $\ell = n$ and $P$ full-dimensional, we can choose $\varepsilon = 1$. But what if $\ell < n$ strictly?

Note that if $P$ is not full-dimensional, we can do some transformations to get around it.

$\endgroup$
  • $\begingroup$ For $A=(\begin{smallmatrix}1\\-1\end{smallmatrix})$, $x\in\mathbb{R}$, $b=(\begin{smallmatrix}1.5\\-0.5\end{smallmatrix})$ polyhedron $P$ is full-dimensional and contains $x=1$, but for $\ell=n=1$, $P_1$ is empty. $\endgroup$ – Marcus Ritt Jun 26 at 20:42
  • $\begingroup$ No. $A$, $b$ have integer entries only. $\endgroup$ – Sriram Sankaranarayanan Jun 26 at 20:53
  • $\begingroup$ I see. I misread the "can assume". $\endgroup$ – Marcus Ritt Jun 26 at 22:20
  • 1
    $\begingroup$ 'can assume' was in the sense that if $A$ and $b$ were just rational matrices, then $\varepsilon$ can be chosen as the reciprocal of the LCM of the denominators of the entries in $A$ and $b$ and it is just simpler to work with integer matrices. $\endgroup$ – Sriram Sankaranarayanan Jun 26 at 22:25
  • $\begingroup$ No, I have an intuition that it is NP hard. In the mixed-integer case, I want to be sure about the existence of a viable polynomial-sized certificate (which exists in the pure integer as well as the continuous case). $\endgroup$ – Sriram Sankaranarayanan Jun 27 at 18:41
6
$\begingroup$

In the full-dimensional case, I think you can consider $\varepsilon\geq 0$ as an extra continuous variable in order to get your poly-size certificate. Let $$Q=\{(x,\varepsilon)\,:\,Ax+e\varepsilon\leq b, 0\leq\varepsilon\leq1\}.$$

If there is a mixed-integer point in the interior of $P$ then there exists a mixed-integer point of poly-size in $Q$ with $\varepsilon>0$ (for instance a mixed-integer optimal solution of maximizing $\varepsilon$ over $Q$). More precisely, since $P$ contains a mixed-integer point in its interior then: $$\varepsilon^*=\max\{\varepsilon \,:\, (x,\varepsilon) \in Q\cap(\mathbb{Z}^l\times\mathbb{R}^{n-l+1})\}$$ must be positive. Then, since the polyhedron $Q$ is rational there exists a mixed-integer optimal solution $(x^*,\varepsilon^*)$ of poly-size. This point $x^*$ is the certificate.

The non-fulldimensional case can be reduced to the full-dimensional case by applying an unimodular transformation to $P$ that makes $\text{aff}(P)$ to be equal to $\mathbb{R}^p\times\{0\}$ (for instance by using the Hermite Normal form of $A$).

$\endgroup$
  • $\begingroup$ This is more clear, thanks. But I still do not see why $Q$ will necessarily allow you to find a point in the interior if it is nonempty. We will indeed have $\epsilon>0$ if you maximize it, but it seems that it can still happen that $x^*$ lies on the border, $\epsilon$ is too big and the optimal solution corresponding to $(x^*,\epsilon^*)$ will be a point on another border of $P$ than $x^*$. Of course, there are only 2 different borders if $\mathrm{relint}(P)\neq \emptyset$, but the intersection with the integral parts can still be empty, and I don't see how to detect this easily. $\endgroup$ – Discrete lizard Aug 30 at 15:21
  • $\begingroup$ If $(x^*,\epsilon^*)$ is the optimal solution with $\epsilon^*>0$, then by definition of $Q$, $$Ax^*\leq b-e\epsilon^*< b.$$ Thus, the point $x^*\in P$ satisfies all constraints strictly and belongs to the interior of $P$. This exact reasoning only works for $P$ full-dimensional, but can be adapted to work in the non-fulldimensional case as well. $\endgroup$ – Diego Morán Aug 30 at 18:14
  • $\begingroup$ Ah, what I say can't happen, because the epsilon movement is for all inequalities simultaneously. Ok, I get it now, thanks. $\endgroup$ – Discrete lizard Aug 31 at 11:58
3
$\begingroup$

This problem is NP-complete, and equivalent to solving a MILP problem.

We can see the complexity equivalence by considering that, if there are no integer feasible points in the polyhedron, we need to prove that there are none - this is equivalent to solving the MILP.

This is typically solved by relaxing the MILP and using branch and bound. In some cases, Benders decomposition, or outer approximation may also be used.

If we don't need a guarantee, but just a feasible point, we can use MIP heuristics, e.g. a feasibility pump.

$\endgroup$
  • $\begingroup$ I know that the problem is NP hard. But the question is whether this is in NP! is there a polynomial sized certificate for ALL instances with decision 'yes'? $\endgroup$ – Sriram Sankaranarayanan Aug 29 at 13:32
  • $\begingroup$ An NP-complete problem is, by definition, the intersection between NP-hard and NP so yes, the problem is NP. $\endgroup$ – nikaza Aug 29 at 18:02
  • $\begingroup$ I don't believe it is NP-complete. Your MILP can be feasible, but this problem infeasible. $\endgroup$ – Sriram Sankaranarayanan Aug 29 at 18:40
  • $\begingroup$ What you described is a linear Integer Programming problem, which is NP-complete. $\endgroup$ – nikaza Aug 29 at 18:43
  • $\begingroup$ It is NP complete to decide if there are integer points in a polyhedron. Except for the answer by Diego above, I have not seen a direct reference where it says it is in NP (or it is NP complete) to decide if there are integer points in the relative interior of a polyhedron. $\endgroup$ – Sriram Sankaranarayanan Aug 29 at 21:25

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.