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

Abstract

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.