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

Resumen

En este trabajo se presenta un procedimiento de obtención de cotas inferiores para una función lineal a partir de ciertas familias de empaquetamientos, cubrimientos y conjuntos ordenados especiales.
Asimismo, se presentan nuevos métodos de detección de infactibilidad y fijación de variables en problemas de programación lineal 0-1 basados en dichas cotas que permiten considerar conjuntamente varias restricciones. Además, se muestran algunas situaciones que son detectadas por estos métodos, pero no por los métodos tradicionales, los cuales consideran las restricciones individualmente.

Palabras clave: Infactibilidad, empaquetamientos, cubrimientos, conjuntos ordenados especiales, familias admisibles.

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.

Key words: Infeasibility, packings, coverings, special ordered sets, admissible families.