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 programs. A given constraint is tightened by using its own structure as well as information from the other constraints. Our approach exploits special structures that are frequently encountered in practical problems, namely knapsack constraints, cliques, covers, variables covers and variable upper bounds. We consider 0–1 knapsack and subset-sum problems with clique and cover induced constraints. The tightening (reduction and increasing) of constraint coefficients benefits from implication results due to probing analysis. Some computational experience is reported on well-known real-life problems as well as on a new set of large-scale problems from the investment planning sector.