On Connections Between Zero-One Integer Programming and Concave Programming Under Linear Constraints

Consider the zero-one integer programming problem P 1 i:minimize Z = c′x subject to Ax ≦ b, 0 ≦ x i ≦ 1, x j = 0 or 1, j = 1, 2, …, n, where A is an m × n matrix, c′ = (c 1 , …, c n ), x′ = (x 1 , …, x n ), and b is an m × 1 vector with b′ = (b 1 , …, b m ). Assume the elements of A, b, c are all rational. This paper characterizes the feasible solutions of P 1 , shows that P 1 is equivalent to a problem of minimizing a concave quadratic objective function over a convex set, and applies a method developed by Tul to solve such a problem to yield a procedure for the zero-one integer programming problem.