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.

Improve this question
$\endgroup$
7
  • $\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, 2019 at 20:42
  • $\begingroup$ No. $A$, $b$ have integer entries only. $\endgroup$
    – Sriram Sankaranarayanan
    Jun 26, 2019 at 20:53
  • $\begingroup$ I see. I misread the "can assume". $\endgroup$
    – Marcus Ritt
    Jun 26, 2019 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, 2019 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, 2019 at 18:41

2 Answers 2

Reset to default
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$).

Improve this answer
$\endgroup$
3
  • $\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, 2019 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, 2019 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, 2019 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.

Improve this answer
$\endgroup$
5
  • $\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, 2019 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$
    – Nikos Kazazakis
    Aug 29, 2019 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, 2019 at 18:40
  • $\begingroup$ What you described is a linear Integer Programming problem, which is NP-complete. $\endgroup$
    – Nikos Kazazakis
    Aug 29, 2019 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, 2019 at 21:25

Your Answer

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

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