Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

EDIT: I realized that while writing this question, I was reasoning about orthogonal projections. Thus, I forgot to transpose when forming the projection on to the space orthogonal to the image of $P$. For clarity, it was intended that the L.H.S. is perpendicular to the R.H.S. I have changed the question to reflect this.

Let $P\in\mathbb{Z}^{n \times n}$ with $P^2=P$ and $0<\text{rank}(P)=r<n$. For an arbitrary constant vector $\mathbf{b}\in\mathbb{Z}^n$, consider the polytope defined by:

$$ P\mathbf{x}\geq (I-P^T)\mathbf{b} $$

Under what conditions does this posses an integer solution for $x$?

First of all, we can assume without loss of generality that $(I-P^T)\mathbf{b}\neq 0$, and that it has at least one strictly positive and at least one strictly negative coordinate; otherwise the question of feasibility is trivial.

Does anyone know anything about the other cases? This question seems intuitively (perhaps naively) easier than the general integer programming problem, but I can't seem to find an Ansatz.

share|improve this question

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.