EFFICIENT REFORMULATION FOR 0-1 PROGRAMS - METHODS AND COMPUTATIONAL RESULTS

We introduce two general methods for 0-1 program reformulation. Our fi rst method generalizes coefficient reduction, our second method genera lizes lifting. Together they provide a unifying interpretation of many previously described automatic reformulation methods. The particular model structures that we consider are individual knapsack constraints, pairs of knapsack constraints, clique and cover induced inequalities, variable upper bounding constraints and capacity expansion constraint s. We describe several easy applications of our reformulation procedur es. Some computational experience is reported, including the currently best known results on a well-known 147 x 2655 benchmark problem.