# When is there at least an integral point in a polyhedron?

This problem comes from a problem of economics. Let $$x\in [0,1]^n$$. $$\{x_1,x_2,\ldots,x_n\}$$ is partitioned into $${S_1, S_2,\ldots,S_k}$$ such that $$\sum_{x_i\in S_j}x_i\leq 1$$ for each $$1\leq j\leq k$$. This constraint can be restated as $$Bx\leq 1$$ componentwise, where matrix $$B \in \mathbb \{0,1\}^{k \times n}$$ and its component $$b_{ij}=1$$ if $$x_j\in S_i$$. For instance, suppose $$x=(x_1,x_2,x_3)$$ and the partition is $$\{x_1\}$$ and $$\{x_2,x_3\}$$, this constraint can be written as $$\begin{gather*} \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 1 \end{bmatrix}\quad \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix}\quad \leq \begin{bmatrix} 1 \\ 1 \end{bmatrix} \end{gather*}$$

Let matrix $$A \in \mathbb \{0,\pm 1\}^{m \times n}$$ and $$P = \{x\in[0,1]^n: Bx\leq 1 \text{componentwise}, Ax=c\}$$ where $$c\in \mathbb{Z}^m$$ with each $$c_i\leq 1$$ (possibly negative). $$P$$ is known to be nonempty. What condition on $$A$$ would guarantee the existence of an integral vertex on $$P$$? From some examples I studied, my conjecture is that when $$A$$ is unimodular (not necessarily totally unimodular), $$P$$ has at least an integral vertex.

• Somewhat related to the question: How to solve the feasibility problem in 0-1 integer programs? – dhasson Sep 19 '20 at 16:24
• Can you please add some more information, for what reason you need to know this. There are no general characterizations i know of, the problem is in general NP-complete. If the matrix is totally unimodular and $b$ is integral, then each vertex of $P$ is integral, but the problem could still be infeasible. – user3680510 Sep 20 '20 at 12:44
• @user3680510 Thank you! Some additional details are: the matrix A is composed of 0,1 and -1; x belongs to the unit cube; the polyhedron P is known to be nonempty. From your comment, I know that the totally unimodularity of A is sufficient for my question, given that P is nonempty. I want to know whether there are other conditions that guarantee the existence of an integral point in P, possibly not on the vertex. – Surpass2019 Sep 20 '20 at 13:32
• @user3680510 Sorry. I mean some condition that only guarantees the existence of an integral point in $P$ (which is of course a vertex of $P$ since $x$ belongs to the unit cube), while $P$ is not necessarily integral. – Surpass2019 Sep 20 '20 at 13:49
• Well since you have the intersection with the unit cube, there cannot be any integer point which is not a vertex of $P$. What do you know about $b$, if $b \geq 0$ componentwise then 0-vector is always feasible. en.wikipedia.org/wiki/Total_dual_integrality is another concept which can help you. – user3680510 Sep 20 '20 at 17:29