O(n) Procedures for identifying maximal cliques and non-dominated extensions of consecutive minimal covers and alternates

Abstract

In this paper, we describe computationally efficient procedures for identifying all maximal cliques and non-dominated selected subsets of extensions of minimal covers and alternates that are implied by single 0-1 knapsack constraints. The induced inequalities are satisfied by and 0-1 feasible solution to the knapsack constraint, but are tipically violated by fractional solutions. In addition, the procedures described here are used in conjunction with other constraints to further tighten LP relaxations of 0-1 programs. The complexity of the procedures is O(n). © 1994 SEIO.