ON CHARACTERIZING MAXIMAL COVERS.

Resumen

ABSTRACT
In this paper we introduce the concept of maximal covers and provide some characterizations that make the identification of the maximal covers from the set of covers implied by a 0-1 knapsack constraint easier. By construction, these maximal covers induce non-dominated valid inequalities for the set of feasible solutions for the Knapsack constraint. So, their identification can help to tightening 0-1 models. We also show some situations where a procedure taken from the literature for identifying non-dominated inequalities from certain types of covers only obtains a small subset of maximal covers.

Key words: maximal covers, tighter formulations, knapsack constraints, dominated inequalities.

RESUMEN
En este trabajo se introduce el concepto de cubrimiento maximal y se proporcionan algunas caracterizaciones que facilitan la identificación de los cubrimientos maximales respecto del conjunto de cubrimientos implicados por una restricción de tipo mochila con variables 0-1. Por construcción, estos cubrimientos maximales inducen desigualdades no dominadas que son válidas para el conjunto de soluciones factibles para la restricción de tipo mochila. Así pues, su identificación puede contribuir al reforzamiento de modelos 0-1. Asimismo, se muestran algunas situaciones en las que un procedimiento descrito en la literatura que identifica desigualdades no dominadas a partir de ciertos tipos de cubrimientos únicamente obtiene un pequeño subconjunto de cubrimientos maximales.

Palabras clave: tapas máximas, formulaciones más firmes, constreñimiento de la mochila, desigualdades dominadas,