DETECTING INFEASIBILITY AND FIXING VARIABLES IN 0-1 LINEAR PROGRAMMING PROBLEMS

Abstract

In this paper we present a procedure for obtaining lower bounds on a linear function by means of certain families of packings, coverings and special ordered sets. We also present new methods for detecting infeasibility and fixing variables in 0-1 linear programming problems based on these bounds that allow consideration of several constraints jointly. Furthermore, we show some situations which are detected by these new methods, but not by the traditional methods, which consider the constraints individually