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

Consider the zero-one integer programming problem P₁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₁, …, c_n), x′ = (x₁, …, x_n), and b is an m × 1 vector with b′ = (b₁, …, b_m). Assume the elements of A, b, c are all rational. This paper characterizes the feasible solutions of P₁, shows that P₁ 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.