Efficient reformulation for 0-1 programs: methods and computational results

摘要: Abstract We introduce two general methods for 0–1 program reformulation. Our first method generalizes coefficient reduction, our second 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 clique and cover induced inequalities, variable upper bounding constraints capacity expansion constraints. describe several easy applications procedures. Some computational experience is reported, including the currently best known results on well-known 147 × 2655 benchmark problem.