On characterizing tighter formulations for 0–1 programs

We present two approaches for 0–1 program model tightening. They are based on increasing and reducing knapsack constraint coefficients, respectively. Both approaches make use of information from cover structures implied by the original constraint system. The formulations that they provide are 0–1 equivalent and as tight as the original model. We also present some characterizations for the new formulations to be tighter than the original model.