On connections between zero-one integer programming and concave programming under linear constraints

Abstract

Consider the zero-one integer programming problem Pi:minimize Z=c'x subject to Axrb, O<xj<1, xi=O or 1, j=l, 2, **., n, where A is an mXn matrix, c'= (ci, * * *, ca), x'= (xi, *-* *, x), and b is an mXl vector with b'= (bi, **, bin). Assume the elements of A, b, c are all rational. This paper characterizes the feasible solutions of P1, shows that P1 is equivalent to a problem of minimizing a concave quadratic objective function over a convex set, and applies a method developed by TuT to solve such a problem to yield a procedure for the zero-one integer programming problem.