NEW PROCEDURES FOR PREPROCESSING 0-1 MODELS WITH KNAPSACK-LIKE CONSTRAINTS AND CONJUNCTIVE AND OR DISJUNCTIVE VARIABLE UPPER-BOUNDS

We present some preprocessing techniques for 0-1 models by taking advantage of the special structure provided by conjunctive and disjunctive variable upper bounds, which are often used to express logical constraints. These new procedures include variable fixing, generation of clique and cover-induced inequalities, and coefficient reduction and related constraint generation procedures. By considering the information provided by the variable upper bound constraints, the procedures can be applied when the conditions required by the standard methods are not satisfied. Although some of our procedures require the solution of 0-1 problems arising from the original model, the subproblems (mainly, subset sum and set covering models) are usually small. In any case, our methodology can also be applied by using easily computed upper bounds on the optimal values of the subproblems.