0
$\begingroup$

Please consider the following question: Given an integer m by n matrix A and an integer m-vector b, the 0-1 integer programming problem asks whether there exists an integer n-vector x with elements in the set ${ 0, 1 }$ such that $Ax \leq b$. Prove that 0-1 integer programming is NP-complete.

Am I correct that $Ax$ is a vector, $b$ is a vector and $Ax \leq b$ is true iff every element of $Ax$ is less than or equal to its corresponding element of $b$?

Thanks, Bob

$\endgroup$
1
$\begingroup$

Yes, element-wise comparison is the usual convention for these constraint problems.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.