ON TIGHTENING 0-1-PROGRAMS BASED ON EXTENSIONS OF PURE 0-1-KNAPSACK AND SUBSET-SUM PROBLEMS

We present a framework for automatic tightening of general 0-1 program s. A given constraint is tightened by using its own structure as well as information from the other constraints. Our approach exploits speci al structures that are frequently encountered in practical problems, n amely knapsack constraints, cliques, covers, variable covers and varia ble upper bounds. We consider 0-1 knapsack and subset-sum problems wit h clique and cover induced constraints. The tightening (reduction and increasing) of constraint coefficients benefits from implication resul ts due to probing analysis. Some computational experience is reported on well-known real-life problems as well as on a new set of large-scal e problems from the investment planning sector.