O(n log n) procedures for tightening cover inequalities

We present two procedures for tightening cover induced inequalities in 0–1 programs by using knapsack constraints plus some other information from the program. The tightening is obtained by solving successive knapsack problems with all 0–1 objective function coefficients, and using dominance criteria to avoid the explicit solving of some knapsack problems. The new constraints are 0–1 equivalent to and LP tighter than the original ones. Both procedures have O(n log n) complexity, where n is the number of variables with nonzero coefficients in the knapsack constraint; however, one of them can strongly reduce the computational effort. Some computational experience is reported.