A simplex procedure for linear programs with some 0–1 integer constraints

For the problem “maximize cx, subject to Ax?b, x?0 and a single 0–1 integer constraint dy?β, β?0, y_i = 1 when x_i > 0 and zero otherwise”, it is shown that only the feasible extreme points of Ax?b, x?0 need be searched. An adjacent vertex cut technique is developed to exclude, one at a time, the extreme points which are infeasible with respect to dy?β. In the concluding section, we also discuss the simple extension of the procedure to the case of multiple 0–1 constraints.