Estudio del rango disyuntivo de las desigualdades validas

Abstract

Este trabajo está dirigido a estudiar el algoritmo de planos de corte para problemas de programación lineal entera mixta 0-1, ’’Lift and Project”, realizado por Balas, Ceria y Cornuéjols. En este contexto se han completado las justificaciones de resultados enunciados en el trabajo, provenientes de la Teoría de Optimización y de la Teoría Poliedral. Siguiendo lo sugerido por los autores para estimar la eficacia del algoritmo, se estudia el rango disyuntivo de las desigualdades válidas de la cápsula convexa de las soluciones de algunos problemas enteros mixtos 0-1. Este nos permite, en forma teórica , estimar la rapidez con que el algoritmo puede alcanzar un poliedro para el cual dicha desigualdad esté contenida entre sus facetas.