An Approach to Zero-One Integer Programming

Abstract

By starting with an all-integer zero-one linear programming problem, it is possible to develop a modified, possibly linear, programming problem that provides a characterization of the basis corresponding to a feasible zero-one solution to the integer problem. This characterization is based on the number of variables equal to one in the feasible solution. This paper develops an approach to zero-one programming based on this characterization. The method uses the criterion function of the original problem as a constraint, and then generates a sequence of feasible zero-one solutions, each with a greater value of the objective function. The solution technique is terminated when no more feasible solutions can be found, indicating that the last feasible solution determined is the optimum.