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?

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

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.