Nuevos métodos para la reducción del intervalo de integridad en programación con variables 0-1

Abstract

EN MUCHOS PROBLEMAS PRACTICOS, DENTRO DE LOS MODELOS DE PROGRAMACION ENTERA, SE RESTRINGE EL VALOR DE LAS VARIABLES ENTERAS A LOS VALORES 0-1, EL OBJETIVO DEL ESTUDIO, HA SIDO PROFUNDIZAR EN LA TEORIA SOBRE LA REFORMULACION AUTOMATICA, TRATANDO DE OBTENER UNA RELAJACION LINEAL FUERTE DEL PROBLEMA, Y REDUCIENDO ASI EL DENOMINADO INTERVALO DE INTEGRIDAD. NUESTRA METODOLOGIA PARA LA REFORMULACION DE UN PROBLEMA ENTERO 0-1 UTILIZA CONSTANTEMENTE LA ESTRUCTURA ESPECIAL, TANTO DE LAS DESIGUALDADES LINEALES QUE DESCRIBEN LA REGION FACTIBLE, COMO DE LAS CONDICIONES AUXILIARES, TALES COMO CICLOS, CUBRIMIENTOS, CONDICIONES DE LIMITE SUPERIOR, ETC. EN EL PROCESO DE REFORMULACION SE PUEDEN DISTINGUIR DOS ETAPAS, LA DE PREPROCESO Y LA DE GENERACION DE CORTES CON EL FIN DE REDUCIR LA REGION FACTIBLE LINEAL. LOS PROCEDIMIENTOS PROPUESTOS, GENERAN CONDICIONES EQUIVALENTES 0-1 Y MAS FUERTES QUE LAS INICIALES. LA EFECTIVIDAD HA SIDO PROBADA TANTO MEDIANTE DEMOSTRACIONES TEORICAS COMO A TRAVES DE SU APLICACION A EJEMPLOS ALGUNO DE ELLOS CLASICOS.