5
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • $\begingroup$ Somewhat related to the question: How to solve the feasibility problem in 0-1 integer programs? $\endgroup$ – dhasson Sep 19 '20 at 16:24
  • $\begingroup$ 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. $\endgroup$ – user3680510 Sep 20 '20 at 12:44
  • $\begingroup$ @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. $\endgroup$ – Surpass2019 Sep 20 '20 at 13:32
  • $\begingroup$ @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. $\endgroup$ – Surpass2019 Sep 20 '20 at 13:49
  • $\begingroup$ 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. $\endgroup$ – user3680510 Sep 20 '20 at 17:29

Your Answer

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

Browse other questions tagged or ask your own question.