# Does this $0-1$ integer program have any speciallity?

Given matrix $$A \in \{0,1\}^{m \times n}$$ and vector $$b \in (\mathbb{Z^+})^m$$, where $$\mathbb{Z^+}$$ is the set of positive integers,

$$\begin{array}{ll} \text{maximize} & c^T x\\ \text{subject to} & Ax \leq b\\ & x \geq 0\\ & x \in \{0,1\}^n\end{array}$$

Notice the biggest difference from normal $$0-1$$ integer programming is that $$A \in \{0,1\}^{m \times n}$$ and $$b \in (\mathbb{Z^+})^m$$. Is there anything special about such integer programs? Is there an algorithm to solve them in polynomial time?

• The way you have written the formulation, it looks like $A$ and $b$ are variables, but I think you meant them to be constants. – RobPratt Oct 7 '19 at 18:56
• @RobPratt Yes, and they are constant interges, and A are all zero or one integers – worldterminator Oct 9 '19 at 8:13
• @RodrigodeAzevedo agree. – worldterminator Oct 9 '19 at 8:13
• Now posted also at or.stackexchange.com/q/2770/8 – Rodrigo de Azevedo Oct 9 '19 at 20:01
• Interesting how much more warmly the question was received at OR SE. – Rodrigo de Azevedo Oct 10 '19 at 6:18