Penalty for zero–one integer equivalent problem

The equivalence of zero–one integer programming and a concave quadratic penalty function problem has been shown by Raghavachari, for a sufficiently large value of the penalty. A lower bound for this penalty is obtained here, which in specific cases cannot be reduced.This research was supported in part by the Computer Science Section of the National Science Foundation under Research Grant MCS 8101214.