solución de problemas de programación lineal en enteros
TRANSCRIPT
TRABAJO DE DIPLOMA
Solución de Problemas deProgramación Lineal en Enteros
usando varias técnicas de Optimización.
Autor: Rubén Pérez Armas.
Tutor: MSc. Gonzalo J. Palencia Fernández.
2008
“Año 50 de la Revolución”
FACULTAD
MATEMATICA – FISICA - COMPUTACION
Hago constar que el presente trabajo fue realizado en la Universidad Central “Marta Abreu”de Las Villas como parte de la culminación de los estudios de la especialidad de Licenciaturaen Matemáticas, autorizando a que el mismo sea utilizado por la institución , para los finesque estime conveniente, tanto de forma parcial como total y que además no podrá serpresentado en eventos ni publicado sin la autorización de la Universidad.
_____________________Firma del autor
Los abajo firmantes, certificamos que el presente trabajo ha sido realizado según acuerdos dela dirección de nuestro centro y el mismo cumple con los requisitos que debe tener un trabajode esta envergadura referido a la temática señalada.
________________ _________________________ Firma del tutor Firma del jefe del Seminario
i
Pensamiento
“Educar es depositar en cada hombre toda la obra humana que le ha
antecedido: es hacer a cada hombre re sumen del mundo viviente, hasta
el día en que vive: es ponerlo a nivel de su tiempo, para que flote en él,
y no dejarlo debajo de su tiempo, con lo que no podrá salir a flote; es
preparar al hombre para la vida.
José Martí Pérez
Nueva York, noviembre 1883.
ii
Dedicatoria
Dedico mi tesis a mis padres y familia.
Y a esta gran obra por la que cada día debemos ser mejores, “La Revolución”.
iii
Agradecimientos
Me gustaría expresar mi mayor agradecimiento por haber llegado a este momento tan especial
como es la culminación de mi tesis, a mis padres Rubén Pérez Ayo y Jenny Armas Margado por
darme su apoyo minuto a minuto y compartir conmigo comprendiendo y analizando cada
dificultad y cada problema con amor y dedicación y haciendo hasta lo imposible por ver mis
sueños hecho realidad, siempre con la fe puesta en m í de terminar con éxitos, junto a ustedes
incluyo también a mi hermana. Y por todo esto que aunque es poco lo que yo pueda expresar les
doy de todo corazón las gracias.
A mi novia, Grey Izquierdo Moreno, que a lo largo de estos años de estudio compartió conmigo
los momentos buenos y difíciles, logrando en mi el placer de admirarla.
Agradecer: palabra que encierra gratitud, reconocimiento, satisfacción, gusto, plac er es esto y
quizás más el merecido significado que deseo expresar para definir el trabajo realizado por
Gonzalo J. Palencia.
Por haber aceptado incondicionalmente mi solicitud para la tutoría de mi tesis de graduación
Por haber empleado el tan preciado tiempo del que dispone.
Por los días de incertidumbre y llegar hasta el desvelo.
Por su paciencia y comprensión.
Por la confianza depositada en m í desde el primer momento para realizar mi proyecto con gran
profundidad.
Por llegar al final con el espíritu de haber realizado un trabajo de grandes.
Y le digo con el mayor respeto, sinceridad y admiración: ha ganado usted un amigo.
Por todo esto y de corazón le doy las gracias...
A los profesores de Estadística, por ayudarme en los momentos en que fui con ellos, a pedir
aclaraciones de dudas que me fueron surgiendo a lo largo de la elaboración y análisis estadísticos
en mi proyecto.
Agradecimientos
iv
Agradezco y con especial reconocimiento también a Marisela profesora que me impartió por
primera vez la asignatura de op timización y me motivó a interesarme con profundidad en esta
rama de las Matemáticas.
A Yoandy Castillo Sánchez.
A Rangel Roque Fundora.
A Miguel Angel Estela Rodriguez.
A. Dayron Hernández Pérez .
Y a todos mis amigos, que mi mayor deseo es poderlos men cionar a todos, pero no terminaría
ni alcanzaría esta hoja. Para mí, la amistad y la unión en la que pude disfrutar en estos años, me
ha servido de gran impulso y estímulo para llegar al final.
Y por todo lo dejado escrito les doy las gracias por ha ber dejado compartir mi vida con todos
ustedes y esperando que este trabajo pueda servirle a muchos en un futuro.
v
Resumen
Éste documento investiga una de las técnicas novedosas en la programación en enteros, el método
de Ramificación y Acotación comb inado con los cortes de Gomory y Chvatal -Gomory
(Ramificación y Corte). A través del programa Programación Lineal en Enteros v.1.0 y del
programa SPSS v.11.0 se lleva a cabo la implementación y comparación de las distintas
alternativas empleadas en el m étodo de Ramificación y Corte para problemas con pequeña
dimensión (máximo 8 variables y 5 restricciones), utilizando los cortes anteriormente
mencionados y aplicados cada 1, 2, 0 -1, 1-0 niveles del árbol. El principio básico del Método de
Ramificación y Corte es igual al del método de Ramificación y Acotación, se utilizan las mejores
estrategias para la selección de la variable y los nodos a ramificar. Se incluyen además los
Métodos de los Planos Cortantes de Gomory y el de los Planos Cortantes de Chvata l-Gomory.
Además se hace una comparación co n el software Mathematica v.6.0 para validar los resultados
obtenidos. Un total de 12 estrategias fueron analizadas para la resolución de problemas de
programación lineal en enteros.
vi
Abstract
This document investigates one of the novel techniques in the integer programming, the Method
of Branch and Bound combined with the cuts of Gomory and Chvatal -Gomory (Branch and Cut).
Through the program Programaci ón Lineal en Enteros v.1.0 and of the program SPSS v.11.0 is
carried out the implementation and comparison of the different alternatives employees in the
method of Branch and Cut for problems with small dimension (maximum 8 variables and 5
restrictions), using the previously mentioned and applied cuts each 1, 2, 0-1, 1-0 levels of the tree.
The basic principle of the Method of Branch and Cut is similar to that of the method of Branch
and Bound, the best strategies are used for the selection of the variable and the nodes to ramify.
They are also included the Method s of the Sharp Planes of Gomory and that of the Sharp Planes
of Chvatal-Gomory. A comparison is also made with the software Mathematica v.6.0 to validate
the obtained results. A total of 12 strategies were analyzed for the resolution of problems of
integer lineal programming.
vii
Índice
PENSAMIENTO ................................ ................................ ................................ ................................ ........................... I
DEDICATORIA ................................ ................................ ................................ ................................ .......................... II
AGRADECIMIENTOS ................................ ................................ ................................ ................................ .............III
RESUMEN ................................ ................................ ................................ ................................ ................................ ... V
ABSTRACT ................................ ................................ ................................ ................................ ................................ VI
ÍNDICE ................................ ................................ ................................ ................................ ................................ ..... VII
1. INTRODUCCIÓN ................................ ................................ ................................ ................................ .................... 2
2. MÉTODOS DE PROGRAMACIÓN LINEAL EN ENTEROS ................................ ................................ ........... 6
2.1 NOTACIONES Y DEFINICIONES ................................ ................................ ................................ .............................. 62.2 RAMIFICACIÓN ................................ ................................ ................................ ................................ ..................... 82.3 MÉTODO DE RAMIFICACIÓN Y ACOTACIÓN ................................ ................................ ................................ .......... 9
2.3.1 Selección de las variables a ramificar ................................ ................................ ................................ ....... 112.3.2 Selección de los nodos a ramificar ................................ ................................ ................................ ............ 122.3.3 Búsqueda de una soluc ión inicial factible................................ ................................ ................................ .. 142.3.4 Aspectos del Algoritmo ................................ ................................ ................................ .............................. 152.3.5 Algoritmo general de Ramificación y Acotación ................................ ................................ ....................... 15
2.4 MÉTODO DE PLANOS CORTANTES DE GOMORY ................................ ................................ ................................ .. 162.4.1 Algoritmo de Planos Cortantes de Gomory ................................ ................................ ............................... 18
2.5 CORTES DE CHVATAL - GOMORY ................................ ................................ ................................ ....................... 192.5.1 Separación de un problema para F CG ................................ ................................ ................................ ........ 202.5.2 Algoritmo de Cortes de Chvatal -Gomory ................................ ................................ ................................ .. 21
2.6 RAMIFICACIÓN Y CORTES ................................ ................................ ................................ ................................ ... 212.6.1 Esquema General del Algoritmo de Ramificación y Corte ................................ ................................ ........ 23
3. PRUEBAS NUMÉRICAS Y ANÁLISIS DE RESULTADOS ................................ ................................ ............ 25
3.1 ESTRATEGIAS UTILIZADAS ................................ ................................ ................................ ................................ . 253.2 DESCRIPCIÓN DE LOS PROBLEMAS DE PRUEBA ................................ ................................ ................................ ... 263.3 DETALLES DE LA IMPLEMENTACIÓN ................................ ................................ ................................ ................... 273.4 EJEMPLO DESDE EL MATHEMATICA ................................ ................................ ................................ .................... 313.5 ANÁLISIS ESTADÍSTICO................................ ................................ ................................ ................................ ....... 34
3.5.1 Descriptivo ................................ ................................ ................................ ................................ ................. 343.5.2 Exploratorio ................................ ................................ ................................ ................................ ............... 373.5.3 No Paramétrico ................................ ................................ ................................ ................................ .......... 39
3.6 CONCLUSIONES................................ ................................ ................................ ................................ ................... 41
CONCLUSIONES ................................ ................................ ................................ ................................ ...................... 42
RECOMENDACIONES ................................ ................................ ................................ ................................ ............ 43
BIBLIOGRAFÍA ................................ ................................ ................................ ................................ ........................ 44
APÉNDICE A. TABLAS ................................ ................................ ................................ ................................ ........... 48
A.1 PROBLEMAS DE PRUEBA ................................ ................................ ................................ ................................ .... 49A.2 ANÁLISIS ESTADÍSTICO. ................................ ................................ ................................ ................................ .... 62A.3 NOTACIÓN ................................ ................................ ................................ ................................ ........................ 65
1
1. Introducción
oy en día, la optimización se ha convertido en práctica habitual en las ciencias, las
ingenierías y los servicios. En Estadística son comunes los términos “máxima
probabilidad o mínimos cuadrados”; en el c ampo de los negocios es frecuente
encontrar términos como “máximo beneficio, mínimo costo o aprovechamiento máximo de los
recursos”. Aunque muchos de los aspectos básicos de la Optimización se desarrollaron en los
siglos XVIII y XIX con los trabajos de Lag range o Euler el verdadero desarrollo de la
Programación Matemática (PM) comienza con los trabajos de Kantorovich y Dantzig en los años
40. Sin embargo, no es hasta la revolución informática de los años 70, cuando apoyados en el
poder de cálculo de los ordenadores, la PM comienza a ser una herramienta ampliamente
utilizada en muchas aplicaciones. Los problemas de Optimización se pueden clasif icar en
problemas que involucran variables continuas solamente o en problemas con variables continuas
y discretas (o solamente discretas). En muchos problemas prácticos, las variables de decisión
sólo tienen un sentido real si su valor es entero. Por ejemplo, con frecuencia es necesario asignar
personas, máquinas, vehículos a las actividades , en cantidades enteras. El hecho de exigir valores
enteros es la única diferencia respecto a un problema de Programación L ineal (PL), entonces se
trata de un problema de Programación en Enteros (PE). El Modelo Matemático para PE es
sencillamente el modelo de PL con la restricción adicional de que las variables deben tener
valores enteros.
Un Problema de Programación Lineal en Enteros (PLE) está dado por:
mmxnnnT ZbZAbAxZxSsaZcxcxf ,,:,, (1.1)
Capítulo
1H
Capítulo 1. Introducción
2
En una forma más Standard un PLE se escribe:
n
T
Zxx
bAx
xc
,0
min
(1.2)
En forma de sumatoria un PLE se escribe:
Zxx
mibxa
xc
jj
ijij
n
j
jj
n
i
,0
,...,1,
min
1
1
(1.3)
Igual que en el caso de los PL las restricciones pueden aparecer con signo de , o de y en
forma similar, usando variables de holgura o superplus, se pueden llevar a la forma Standard.
Una generalización de los PLE son los Pro blemas Lineales Mixtos (PLM), donde solamente
algunas de las variables, deben satisfacer la restricción de ser enteras. Estos problemas pueden
escribirse:
0,
min
21
21
vZx
bvAxA
vcxc
n
(1.4)
Puede parecer que los problemas de PE son relativamente fáciles de resolver. Después de todo,
los problemas de PL se pueden resolver de una manera bastante eficiente, y la única diferencia es
que la PE tiene muchas menos solucione s que considerar. De hecho, está garantizado que los
problemas de PE pura con una región factible acotada tienen sólo un número finito de soluciones
Capítulo 1. Introducción
3
factibles, pero éste número suele ser lo suficientemente grande (en un problema binario con n
variables el número de soluciones factibles a estudiar es 2 n) como para que resulte imposible su
comparación. Entonces, cada vez que n aumenta en 1, el número de soluciones se duplica. Este
patrón se llama el crecimiento exponencial de la dificultad del problema. Con 10n , se tienen
más de 1000 soluciones (1024); con 20n , son más de un 106; con 30n resultan más de mil
millones, y así sucesivamente; por eso, hasta las computadoras más eficie ntes son incapaces de
realizar una enumeración exhaustiva (que verifique la factibilidad de cada solución y si es
posible, que calcule el valor de la función objetivo) para Problemas Enteros Binarios (PEB) con
unas cuantas docenas de variables, sin mencion ar los problemas de PE en general con el mismo
número de variables enteras.
Los métodos más populares para resolver (1.1) fundamentalmente están basados en los métodos
de Ramificación y Acotamiento (B & B del inglés Branch and Bound ) y sus variantes, donde cada
subproblema lineal se resuelve utilizando cualquier método de PL (Simplex, Simplex -Revisado,
Método de Punto Interior, etc...). Este método consiste en una enumeración del árbol en el cual el
espacio de variables enteras se divide de forma sucesiva dando a lugar a subproblemas lineales
que se resuelven en cada nodo del árbol . Para la elección del nodo a ramificar se utilizan reglas
heurísticas (búsqueda en profundidad, búsqueda en anchura, etc…) que serán expuestas en el
Capítulo 2. Otra variante que existe para resolver (1.1) es el Método de los Planos Cortantes de
Gomory [Gomory, ´59], que se basa en la introducción de nuevas restricciones al problema
Relajado, hasta lograr que la solución óptima del nuevo problema sea entera. El mismo tiene una
desventaja: podemos realizar hasta 1000 iteraciones y no llegar al óptimo, es por eso que
acudimos a la aplicación de otros métodos de la PE.
El desarrollo de dos técnicas importantes ha contribuido a mitigar el crecimiento exponencial en
la solución de problemas de PLE Mixtos. El desarrollo de técnicas de pre -procesamiento y la
introducción de Planos Cortantes. El pre -procesamiento se basa en la utilización de eliminación
automática de variables y restricciones, reformulación de restricciones, fijar a pri ori algunas
variables enteras. Los Planos Cortantes son restricciones extra añadidas al problema, bien en el
nodo inicial o dentro de la enumeración, que tiene el efecto de reducir la región factible del
problema. Dos artículos reportan la aparición del al goritmo de Ramificación y Corte [Grötschel,
Holland, ’91], [Padberg, Rinaldi, ’91]. Los últimos desarrollos en la PE Mixta incluyen los
métodos de Ramificación y Precio (Branch and Price ) [Liberti, ´06] y Ramificación y Corte
Capítulo 1. Introducción
4
(Branch and Cut, [Balas´93]); [Rinaldi, ´91]; [Jünger, ’95]; [Caprara and Fischetti, ’97];
[Fischetti, Lodi, ’05]; [Grossmann, Caballero, ’07]; etc... Se reporta en la bibliografía actualizada
que la aplicación de Métodos híbridos, o sea, Ramificación y Acotación combinado con los
Planos Cortantes de Gomory (Branch and Cut) proporciona mejoras de pre -procesado y aumento
en la velocidad de los ordenadores. Esta demostrado por Eisenbrand, F . que la separación de un
problema aplicando el corte Chvatal-Gomory es NP-Hard [Eisenbrand, ‘99]. En los últimos años
ha despertado un gran interés la aplicación de métodos híbridos en la Optimización para acelerar
su convergencia, es por eso que en nuestro trabajo centraremos nuestra atención en la resolución
de problemas de PLE aplicando el Método de Ramificación y Corte.
Los objetivos de nuestro trabajo son:
Objetivo General:
1. Implementar diferentes algoritmos que permiten resolver PLE usando el lenguaje del
paquete Mathematica.
Objetivos Específicos:
1. Implementar el algoritmo de Ramificación y Aco tación, Planos Cortantes de Gomory,
Planos Cortantes de Chvatal -Gomory y diferentes variantes de Ramificación y Corte en
lenguaje del paquete Matemática.
2. Realizar experimentos numéricos para verificar la efectividad de la implementación.
3. Realizar un análisis estadístico de las pruebas numéricas realizadas.
El presente trabajo consta de tres Capítulos:
Capítulo 1: En la Introducción se ofrece un estado de arte hasta la actualidad de los diferentes
métodos que existen para resolver problemas de PLE.
Capítulo 2: Se introducen las diferentes notaciones y definiciones que se utilizan en nuestro
trabajo. También se expone una idea básica de los fundamentos teóricos de diferentes algoritmos
Capítulo 1. Introducción
5
que permiten resolver PLE (Ramificación y Acotación, Planos Cortan tes de Gomory, Planos
Cortantes de Chvatal-Gomory y el de Ramificación y Corte).
Capítulo 3: Se proponen 11 estrategias que involucran los métodos descritos en el capítulo
anterior, se suman a estas el método implementado en el paquete Mathematica ; realizándose las
corridas a los problemas de prueba y llevándose a cabo un análisis estadístico.
6
2. Métodos de Programación Lineal en Enteros
n este capítulo centraremos nuestra atención en exponer la idea básica de diferentes
algoritmos que permiten resolver problemas de PLE y algunos aspectos teóricos
relacionados con los algoritmos. Específicamente, uno de los primeros métodos que
surgió para resolver los problemas de PLE es el Método de Planos Cortantes de Gomory
[Gomory, ’63], después apareció el Método de Ramificación y Acotación, más conocido por su
nombre en inglés Branch and Bound , recibe su nombre precisamente por las dos técnicas en las
que basa su desarrollo, que son la Ramificación y la Acotación, y por último, la combinación de
los dos métodos anteriores, que se inscribió en la literatura como el Método de Ramificación y
Corte (Branch and Cut). Se introducirán las diferentes Notaciones y Definiciones que serán
utilizadas en el transcurso de nuestro trabajo.
2.1 Notaciones y Definiciones
Consideremos el siguiente problema de PLE, lo denotemos por (P)
n
T
Zxx
bAx
xc
,0
:sa
min
(P),
Donde nm c,b),,( nmMA y la relajación del problema (P ) lo denotemos por (RP)
que tiene la siguiente forma:
Capítulo
2E
Capítulo 2. Métodos de Programación Lineal en Enteros
7
0
:sa
min
x
bAx
xcT
(RP)
Denotemos por : nRP
nP SbAxZxS al conjunto formado por todas las
soluciones factibles de (P) que tienen coordenadas en entero y a bAxxS nRP : al
conjunto formado por todas las soluciones factibles de (RP).
Consideremos los dos problemas de Optimización siguientes:
P1:
nTx
:sa
)(min xcxz TRP
P2:
Sx
:sa
)(min xcxz TP
, donde S T
Definición 1 (Relajación de un Problema)
El problema de PL que se obtiene al eliminar en un PLE las condiciones de integridad , es
conocido como la relajación del PLE. En general el problema, se dice que P1 es una Relajación
para P2.
Definición 2 (Inecuación Válida (del inglés “Valid Inequalities”))
Dado un conjunto nX , una “Inecuación” o “restricción” 0 xt con n , 0 es
válida paranX , si y 0
t xXxxX , o sea, si se satisface en todos los
puntos factibles (enteros).
Lema. (Caracterización de las “ Inecuaciones Válidas”)
Consideremos el siguiente problema
X x:
)(min
sa
xf, donde by Z1 yX .
Entonces la “Inecuación” by es válida para X .
Definición 3 (Separación de un problema)
Capítulo 2. Métodos de Programación Lineal en Enteros
8
Dado cualquier punto RPSx * y F una familia de inecuaciones válidas para PS , Separación de
un problema es buscar una inecuación válida de F que se viole en *x ( x 0*t ) o
demostrar que no existe.
Definición 4 (Nivel de un vértice).
Sea G un árbol binario y v, w vértices del árbol.
El nivel del vértice v es la longitud del camino simple de la raíz de G a v.
Notas:
1. Un árbol binario es aquel cuyo vértice tiene a lo más 2 hijos.
2. Un camino simple es el camino de v a w sin vértices repetidos.
Haremos mención a algunos términos que se utilizan en el á rbol de enumeración, o sea, éste
árbol nos permite describir el proceso de cálculo aplicando el Método de Ramificación y
Acotación y sus variantes para la resolución de un PLE.
2.2 Ramificación
Vértice cancelado: cuando no tiene sentido hacer una separac ión a partir de él (no más
exploración).
Vértice vivo: no es cancelado y todavía no se ha hecho una separación a partir de el
(puede seguirse explorando)
Ramificar: significa seleccionar un vértice vivo para cancelarlo o separarlo.
Vértices vivos y cancelados son las hojas del árbol.
Expondremos a continuación los fundamentos teóricos en los cuales se basan los diferentes
métodos que permiten resolver problemas de PLE. Los métodos m ás usados parten de la
Relajación del problema.
Idea: sustituir el problema entero original por un problema más sencillo, que pueda ser resuelto
más fácilmente, por tanto; que pueda ser utilizado para obtener cotas.
Capítulo 2. Métodos de Programación Lineal en Enteros
9
Las más usada es la Relajación Lineal que consiste en eliminar la condición de que las variables
tomen valores enteros (condiciones de integridad) . Si los puntos extremos del problema tuvieran
coordenadas en enteros, pues no hubiera problema, entonces ¿por qué no obtener una envoltura
convexa? Es demasiado costoso. Por eso acudimos a otras herramientas matemáticas que nos
permiten resolver PLE, en el cual Ralph Gomory es el Díos en la PLE.
2.3 Método de Ramificación y Acotación
El método de Ramificación y Acotación ha evolucionado gracias a la contribución de muchos
investigadores, entre ellos los primeros que incursionaron éste tema fueron Land and Doig [Land
and Doig, ´60]. Este consiste en una búsqueda sistemática de soluciones continuas en las cuales
las variables enteras están forzadas a tomar valores enteros [Gupta, Ravindran, ´85], la estructura
lógica del conjunto solución son los árboles.
Inicialmente se resuelve el problema de PL relajado. Si todas las variables enteras toman valores
enteros, entonces se ha llegado a una solución entera factible para el problema (1 .1) ó (P).
Usualmente variables enteras toman valores no enteros, entonces se selecciona n una de estas
variables ix con valores ix~ y se ramifica [Gupta, Ravindran, ´85]. La ramificación genera dos
nuevos subproblemas de PL y las siguientes cotas para cada uno, o sea, a partir de RPS los dos
nuevos subproblemas se generan de la siguiente manera:
x~ x: x jj1 SS
1x~ x: x jj2 SS
Uno de estos dos nuevos subproblemas es escogido para ser resuelto. Si alguna de las variab les
enteras toma valores no enteros se vuelve a repetir el proceso anterior hasta encontrar una
solución factible entera. Si una de las siguientes reglas se satisface, entonces no se requiere
ramificación, el nodo correspondiente a sido explorado al máximo (tanteado) y puede ser
abandonado [Leyffer, ’98].
Capítulo 2. Métodos de Programación Lineal en Enteros
10
R1) Si un nodo no factible es detectado, el subárbol completo que comienza con este nodo es no
factible y el nodo es tanteado.
R2) Un nodo entero factible es detectado. Esto provee una cota superior, la ramificación no es
posible y el nodo será tanteado.
R3) La solución del nodo es mayor o igual que la cota superior actual, en este caso el nodo es
podado y una vez que esto ocurre el algoritmo hace Backtracking a otro nodo el cual no haya sido
explorado, hasta que todos los nodos se exploren o se haya llegado al umbral especificado.
Una vez que un nodo sea explorado el algoritmo hace un Backtracking hacia otro nodo que no
haya sido explorado. La estrategia de búsqueda que se usa es primero en profundidad para elegir
los subproblemas, hasta que una solución entera es encontrada. La búsqueda puede detenerse
cuando el árbol sea completamente explorado o hasta un Umbral especificado para no tener que
explorar el árbol completo, lo cual mejora considerablemen te la eficiencia del algoritmo, ya que
para problemas de grandes dimensiones sería muy costoso tener que explorar el árbol completo,
mientras que con un Umbral la búsqueda se hace mucho más eficiente.
En adición a los datos del problema y al árbol que des cribe el proceso de Ramificación y
Acotación, el algoritmo utiliza la variable:
Ub: Cota superior. Este es el valor de la función objetivo para la mejor solución entera
conocida. Es inicializada Ub = para un problema de minimización.
La eficiencia del método de Ramificación y Acotación frecuentemente depende de las
reglas usadas para seleccionar las variables a ramificar y los nodos a ramificar.
Un nodo generalmente almacena la cota superior y el correspondiente valor de la
función objetivo.
El procedimiento de ramificar y resolver una secuencia de problemas continuos se
procede hasta que una solución entera de uno de dichos problemas es encontrada.
Capítulo 2. Métodos de Programación Lineal en Enteros
11
Cuando obtenemos una de estas soluciones factibles enteras, el correspondiente v alor
de la función objetivo se convierte en una cota superior. Esto posibilita que en futuras
consideraciones podamos podar todos los nodos cuyos valores de la función objetivo
son mayores que la cota superior.
Cuando se encuentra una solución factible entera, y el valor de la función objetivo es
menor que la cota superior, este se convierte en la nueva cota superior.
2.3.1 Selección de las variables a ramificar
Existen diversos criterios para escoger la variable que se va a ramificar, a continuación h aremos
alusión a tres de ellos que son los más utilizados.
1. Menor índice primero: Cada variable entera es organizada en orden de importancia, la
más importante se comienza primero a procesar. Esto se puede lograr indexando las
variables con una prioridad en orden decreciente y seleccionando la variable con menor
índice primero.
2. Variables enteras más fraccionarias : Esta estrategia selecciona la variable que esté
más lejos de su valor entero más cercano.
3. Uso de Pseudos-Costos: Los Pseudos-Costos son usados como una medida cuantitativa
de la importancia de la variable entera, lo cual permite que se le asigne cierta prioridad
a las variables. Para cada variable entera jx se definen las siguientes cantidades: jpcl
llamado lower pseudos-cost y jpcu llamado upper pseudos-cost, estos valores son
computados durante la búsqueda de la siguiente forma:
jpcl =( Lf - Kf ) /*jx
Suponiendo que en el nodo K la variable jx es seleccionada para ser ramificada:
*jx : Denota la parte fraccionaria del valor de la variable jx .
Capítulo 2. Métodos de Programación Lineal en Enteros
12
Kf : Denota el valor de la función objetivo en el nodo K.
Lf : Denota el valor de la función objetivo cuando el problema continuo es
resuelto con la restricción adicional jx [ jx ].
jpcu = ( Uf - Kf ) / (1-*jx )
Uf : Denota el valor de la función objetivo cuando el problema continuo es
resuelto con la restricción adicional jx [ jx ]+1.
Estos pseudos-costos pueden ser interpretados como el deterioro del valor funcional por unidad
de cambio de la variable jx , donde jpcl corresponde al decrecimiento de jx y jpcu
corresponde al incremento de la variable jx .
Esta estrategia es invocada de la siguiente manera:
1. Calcular jpcl y jpcu para todas las variables enteras siempre que sea posible.
2. Calcular jV = [ jpcl*jx , jpcu (1-
*jx )].
3. Seleccionar la variable jx para la cual jV es máximo.
2.3.2 Selección de los nodos a ramificar
Para la selección de los nodos a ramificar existen diversos criterios, haremos alusión a tres de
ellos:
Ramificar por el nodo con menor cota : El nodo que tiene la menor cota es seleccionado a
ramificar por el. Lawler and Wood (1966) argumentaron que para cualquier problema dado el
conjunto de nuevos problemas acotados es únicamente determinado, entonces esta estrategia
tiene la ventaja que la cantidad total de cálculos es minimizada, en el sentido de que cualquier
Capítulo 2. Métodos de Programación Lineal en Enteros
13
operación de ramificación ejecutada bajo esta estrategia, también puede ser ejecutada bajo
cualquier otra estrategia. Estrategia conocida como búsqueda de anchura.
Ramificar por el nodo más nuevo: A los nodos correspondientes al nuevo problema le son
asignadas preferencia sobre el resto de los nodos seleccionados para ramificar. Esta estrategia
también es conocida como depth (profundidad), back -track (volver atrás) o last -in-first-out
(último en entrar primero en salir). Esta estrategia tiene la ventaja que economiza memoria y es
relativamente fácil de implementar.
Uso de estimación: Esta estrategia considera solo el valor de la función objetivo y no tiene en
cuenta lo “cualitativo” de las so luciones óptimas continuas. Para ilustrar el concepto de
“cualitativo” consideremos el siguiente ejemplo de tres variables:
)1(x = (1.3, 2.4, 5.1) , 1z =10.5
)2(x = (1.0, 3.0, 5.1) , 2z =10.6
Acorde con el esquema de selección de la cota inferior, se preferiría mejor el nodo 1 y no el
nodo 2. Sin embargo tal selección no parece ser la más apropiada ya que la solución 2 está más
cercana a una solución entera. Si selecc ionamos el nodo 2 este podrá ser explorado en la
próxima iteración, mientras que si seleccionamos el nodo 1 requeriremos un gran número de
iteraciones antes de que este pueda ser explorado.
Para evitar esto es que se utiliza este nuevo concepto llamado estimación, que utiliza pseudos-
costos. Dado un nodo K, la cantidad llamada estimación del nodo K y denotada por kE se
calcula de la siguiente manera:
kE = Kf +
m
jjV
1
kE es en cierto sentido un estimado del valor de la función objetivo, de la mejor solución
entera, que puede ser esperado para el descendiente del nodo K.
Capítulo 2. Métodos de Programación Lineal en Enteros
14
Esta estrategia debe ser invocada de la siguiente manera:
1. Computar la estimación de todos los nodos no explorados.
2. Seleccionar el nodo con menor valor de la estimación.
2.3.3 Búsqueda de una solución inicial factible
Para la búsqueda de esta solución inicial se han propuesto diversas heurísticas, aquí haremos
referencia a una de ellas.
Heurística A:
Tenemos que nxxxx ,...,, 21 es la solución de un nodo no explorado y p representa el
número de variables enteras que asumen valores no enteros en esta solución.
En esta heurística se llevan a cabo los siguient es pasos:
1. Seleccionar el nodo para el cual el orden de no factibilidad es mínimo. Seleccionar la
variable jx , para ramificar acorde a las reglas especificadas. Para este nodo, el número
de variables enteras ya deben tener valores enter os. Estas variables están fijas a sus
correspondientes valores enteros mientras se ramifica. Así, no tienen permitido cambiar
sus valores en ninguno de los dos subproblemas. La idea es decrementar el número de
variables enteras con valores no enteros y a sí se arriba a soluciones con un bajo orden
de no factibilidad.
2. Si el subproblema de cota superior con restricción jx [ jx ] es “continuo factible” , se
fija la variable jx a [ jx ] en todas las subsecuencias descendientes del nodo.
Similarmente si el subproblema con la restricción de cota inferior jx [ jx ]+1 es
“continuo factible”, se fija la variable jx a [ jx ]+1 en todas las subsecuencias
descendientes del nodo.
Capítulo 2. Métodos de Programación Lineal en Enteros
15
Si después de resolver los dos subproblemas una solución entera factible es obtenida, nos
detenemos, de otra forma se retorna al paso 1.
Heurística B:
Esta Heurística se aplica a problemas de Programación no lineal en Enteros y por tanto no es de
nuestro interés.
2.3.4 Aspectos del Algoritmo
Después de haber abordado brevemente la teoría de Ramificación y Acotación, vamos a
formalizar qué criterios seguiremos para implementar nuestro algoritmo que resuelve problemas
de PLE.
En los artículos consultados, para realizar esta tesis, se prueba mediante experimentos numéricos,
en los cuales se hacía una comparación con respecto a la optimalidad y rendimiento del algo ritmo
de Ramificación y Acotación usando las distintas estrategias expuestas anteriormente, que los
mejores resultados se obtuvieron con las siguientes heurísticas:
Para la ramificación de los nodos el criterio con el cual se obtuvieron los mejores
resultados y el cual nosotros elegimos para realizar la implementación del algoritmo de
Ramificación y Acotación es: Ramificar por el nodo con menor cota , y para la
ramificación de las variables elegimos el criterio: Variables enteras más fraccionarias .
Con respecto a la elección del umbral consideramos que debía ser 50 nodos a generar ya que en
los experimentos numéricos los resultados arrojaron que el promedio de nodos generados es de 6,
además de los requerimientos de memoria y procesamiento se harían críti cos con un umbral muy
grande.
2.3.5 Algoritmo general de Ramificación y Acotación
Capítulo 2. Métodos de Programación Lineal en Enteros
16
Sea PLE un problema de Programación Lineal Entera de minimización y PL su relajación lineal.
Los pasos del algoritmo de Ramificación y Acotación ( Branch and Bound) para resolver el PLE
son los siguientes:
Paso 1. Cota Superior: z . Subproblemas pendientes: L = {PL}.
Paso 2. Mientras L :
a) Tomar PL i de L y resolverlo.
b) Sí PL i es no factible, eliminarlo.
c) Sí PL i es factible, y su solución óptima es entera:
Actualizar z , *x y eliminar PL i.
d) Sí PL i es factible y su solución óptima no es entera:
Sí su valor óptimo es superior a z , eliminar PL i.
Si no,
Escoger una variable con valor no entero y ramificar
(Añadir a L los subproblemas correspondientes.)
Paso 3. Sí z , el problema es no factible; en caso contrario, *x es la solución óptima.
2.4 Método de Planos Cortantes de Gomory
Capítulo 2. Métodos de Programación Lineal en Enteros
17
Expondremos la idea general de este método y consideremos el problema (P) y
particionemos la matriz del sistema de restricciones de la forma siguiente:
][ DBA y las variables de decisión
D
B
x
xx , donde la matriz es de dimensión
B ),( mmM y se le llama matriz básica y a la matriz D ),( mnmM se le denomina
matriz no básica. Análogamente tenemos los vectores básicos mBx y a los vectores
mnDx se le denominan vectores no básicos. Sustituyendo estas notaciones en el
problema mencionado y expresando las variables básicas en función de las no básicas (por
coordenadas) obtenemos:
j
n
mjijiB xyyx
i1
0 (2.1)
Donde la matriz ),(*}{ 1 mnmMDByY ij y 0iy son los términos
independientes, mi ,...,1 . Precisamente la técnica de Gomory parte (2 .1). También
podemos reescribir (2.1) en forma vectorial de la manera siguiente:
RjjjB xYYx 0 , donde básicasno variablesdeíndicejjR
Tomando la u-ésima fila de (2.1) tendríamos:
RjjUjUBU xYYx 0 (2.2)
Para que el valor de la variable BUx se convierta en entero, es necesario que al menos una de las
variables no básicas asuma un valor positivo y para lograr esto es necesario ampliar el rango de la
matriz con la inclusión de nuevas restricciones a partir de ( 2.2).
Descompongamos (2.2) de la forma siguiente:
RjfY UjUjUj , y RjfY UUU ,000 (2.3)
Capítulo 2. Métodos de Programación Lineal en Enteros
18
Donde:
0U es el mayor entero menor que 0UY
0Uf es la mantisa que resulta de la diferencia de 0UY y 0U ., 10 0 Uf
Uj es el mayor entero menor o igual que UjY
Ujf es la mantisa que resulta de la diferencia de UjY y Uj ., 10 Ujf
Sustituyendo (2.3) en (2.2) y para cualquier solución entera de ( 2.2), realizando transformaciones
algebraicas obtenemos finalmente la ecuación del Plano Cortante de Gomory [Garfinkel, ´72] que
tiene la forma siguiente:
RjUjUj fxf )()( 0 (2.4)
La ecuación (2.4) es la que se añade al conjunto de restricciones ya modificadas por las
transformaciones elementales realizadas en la iteración óptima y es la que va forzando la solución
a que sea totalmente en enteros.
Utilizando la definición 2, denotemos por
Rj
UjUjG fxfF )()( 0 , le llamaremos corte
de Gomory y es una familia de inecuaciones o restricciones válidas para PS .
2.4.1 Algoritmo de Planos Cortantes de Gomory
Paso 1. (Inicialización). Se resuelve el problema Relajado. Si la solución actual no est á acotada o
es no factible, se detiene el proceso. En caso contrario ir al Paso 2.
Paso 2. (Chequeo de la Solución). Si la solución obtenida cumple con las condiciones de
integridad, se detiene el algoritmo, la solución actual es óptima. En caso contrario, ir al Paso 3.
Capítulo 2. Métodos de Programación Lineal en Enteros
19
Paso 3. (Generación de un corte). Se construye la ecuación de Planos Cortantes respecto a la
variable que requiere ser entera, añadiendo esta nueva restricción o inecuación válida para PS y
se regresa al Paso 1.
2.5 Cortes de Chvatal - Gomory
Expondremos los pasos a seguir para obtener el Corte de Chvatal -Gomory (del inglés Chvatal –
Gomory Cuts) [Pisinger, ‘07].
Supongamos que estamos en presencia del problema (P) , o sea,
njx
bxabxa
sa
xc
j
m
n
jjmj
n
jjj
n
j
t
,...,1,
,...,
:
max
11
11
1
Paso 1. Tomando una combinación lineal de las restricciones
m
iiij
n
j
m
iiji buxau
11 1 (2.5)
Escribiendo la ecuación (2.5) en forma compacta, obtenemos
bxa j
n
j
1
(2.6)
Paso 2. Como 001
j
n
j
xaax
Expandiendo la ecuación anterior y tomando en cuenta ( 2.5) obtenemos
Capítulo 2. Métodos de Programación Lineal en Enteros
20
bxa j
n
j
1
Paso 3. Como jjj xax , se cumple entonces que
bxa j
n
j
1
, esta inecuación puede escribirse
n
j
Tj
T buxAu1
y precisamente esta última expresión es la ecuación de Corte Chvatal - Gomory.
Denotemos por
n
j
Tj
TCG buxAuF
1
la ecuación de Corte de Chvatal -Gomory y es una
familia de inecuaciones o restricciones válidas para PS .
2.5.1 Separación de un problema para F CG
Sobre la aplicación de este tipo de corte se h an dedicado muchos trabajos, el modelo que
presentamos fue una variante aplicada en [Fischetti, Lodi ,’ 05].
Haciendo buyAu TT 0 , debe cumplirse que 00* xT , es por eso que en el
modelo se maximiza la expresión 0* xT , y de la literatura se reporta que una de las mejores
variantes es tomando 01.0 .
Capítulo 2. Métodos de Programación Lineal en Enteros
21
0:,...,1)(
}0{)(,
,...,1,10
}0{)(,10
)(,.
max
**
*
*
00
*
0)(
*
*
j
j
i
j
T
jjT
j
xJjjj
xnjxJdonde
xJjparaentero
miparau
xJjparaf
buf
xJjparaAufas
x
(2.7)
A partir del problema (2.7) podemos decir que existe la separación del problema en el intervalo
especificado o que no existe.
2.5.2 Algoritmo de Cortes de Chvatal -Gomory
Paso1. (Iniciación). Se resuelve el problema original s in restricciones de integridad . Si la solución
no esta acotada o el problema es no factible mensaje indicando la mala formulación, se detiene el
proceso.
Paso2. (Control de la Solución). Si la solución obtenida cumple con las condiciones de
integridad, se detiene dado que esta solución es la óptima. En caso contrario, ir al Paso 3.
Paso3. (Generación de un corte). Se utiliza el modelo (2.7) propuesto anteriormente para lograr
la separación del problema.
Paso 4. (Resolución). Se añade el corte de Chvatal -Gomory obtenido al problema previamente
resuelto, se resuelve el problema res ultante y se continúa con el Paso 2.
2.6 Ramificación y Cortes
En la búsqueda por mejorar las técnicas para resolver un PLE nos encontramos con uno de los
métodos avanzados para la resolución de este tipo de problemas, el método de Ramificación y
Corte.
Capítulo 2. Métodos de Programación Lineal en Enteros
22
Este método se obtiene como resultado de la combinación del método de Ramificación y
Acotación y el método de los Planos Cortantes. La base de estos métodos es la misma utilizada en
el método de Ramificación y Acotación con la diferencia de que en un nivel determinado del
árbol de exploración se aplica un corte válido que reduce el conjunto de solución del problema
relajado que se este analizando en ese momento, y este proceso se repite de manera alternada
hasta encontrar el óptimo. No se ha determinado cad a cuántos niveles, ni que posible corte
introducir, siendo este uno de los principales objetivos de este trabajo. La convergencia es
asegurada por Ramificación y Acotación [Pisinger, ‘07 ].
A continuación se describirán de manera ilustrativa la introducción de un corte cualquiera cada
cierto nivel del árbol o cada cierta combinación de estos (niveles analizados en este trabajo).
Niveles del árbol ,...3,2,1
Nota: Solo se ilustraran los primeros pasos.
Corte añadido cada 1 nivel del árbol.
Nivel donde se añade el corte ,...7,5,3,1
Corte añadido cada 0-1 nivel del árbol.
Capítulo 2. Métodos de Programación Lineal en Enteros
23
Nivel donde se añade el corte ,...9,8,6,5,3,2,0
Corte añadido cada 1-0 nivel del árbol.
Nivel donde se añade el corte ,...8,7,5,4,2,1
Corte añadido cada 2 niveles del árbol.
Nivel donde se añade el corte ,...8,6,4,2
2.6.1 Esquema General del Algoritmo de Ramificación y Corte
Paso 1. (Comenzar). Resolver el problema como si fuera un problema ordinario de PL
(Relajación de enteros). La solución obtenida se toma como cota máxima y base para el
procedimiento de búsqueda de una solución factible.
Paso 2. (Ramificar). A partir de la solución de PL designar una variable como entera y
seleccionar, a partir de los posibles valores e nteros que pueda tomar, una rama para investigarla.
Capítulo 2. Métodos de Programación Lineal en Enteros
24
Paso 3. (Limitar). Encontrar un límite para el problema definido por la rama seleccionada. El
límite esta dado por el valor de la mejor solución factible de enteros encontrada hasta el
momento, y domina a todos los otros posibles resultados de otra rama.
Paso 4. (Comparar). Comparar la solución obtenida en la rama con el l ímite de referencia vigente.
Si el valor de la solución es menor que el límite vigente, se elimina de consideración toda
la nueva rama. Se continúa con las ramas que no hayan sido evaluadas aún.
Si el valor de la solución es mejor que el límite vigente y si la solución es entera
(factible), entonces se convierte en el nuevo límite de referencia. Se examinan las ramas
que aún no se han considerado en relación al nuevo límite.
Si el valor de la solución es mayor que el límite vigente, pero la solución no es entera
(factible) deben explorarse las ramificaciones de nivel inferior en la misma rama.
Paso 5. (Terminar). Quedarse con la mejor solución factible obtenida una vez examinadas todas
las ramificaciones.
25
3. Pruebas Numéricas y Análisis de Resultados
a estadística es una de las herramientas más potentes para muchos trabajos de
investigación. Cuando nos referimos a un pr oblema donde nos encontramos con datos
experimentales y queremos conocer las causas de é ste comportamiento, predecir el
comportamiento o hacer diversas comparaciones, etc… , la estadística juega un papel importante
para poder resolver dichos enigmas.
En la sección 3.1 detallamos las estrategias utilizadas en nuestro trabajo, describiendo de é sta
forma los problemas de prueba en la sección 3.2. Las distintas tácticas fueron implementadas en
el programa: Programación Lineal en Enteros v.1.0, los detalles de la implementación del
mismo, así como la sintaxis de las p rincipales funciones, se abordarán en la sesión 3.3. Para
comprender el funcionamiento del programa se describirá un ejemplo en la sesión 3.4. En la
sección 3.5 se llevarán a cabo las pruebas estad ísticas necesarias para poder afirmar cuáles de las
estrategias resultan ser las mejores ante la población de problemas pequeños. Para finalizar en la
sección 3.6 se enunciarán las conclusiones de éste capítulo.
3.1 Estrategias Utilizadas
Para obtener respuesta a nuestro trabajo de investigación hemos considerado dos de los más
famosos cortes, como son el corte de Gomory y el corte de Chvatal -Gomory; hemos aplicado los
mismos cada 1, 2, 0-1, 1-0 niveles del árbol, además de compararlos con el método de
Ramificación y Acotación, el método de los Planos Cortantes de Gomory, el método de los
Planos Cortantes de Chvatal -Gomory y con el método implementado por el software mathematica
v.6.0 (Ramificación y Acotación en su función LinearProgramming [Wolfram, ´07]).
Capítulo
3L
Capítulo 3.Pruebas Numéricas y Análisis de Resultados
26
Estas diferentes alternativas para resolver PLE forman un total de 12 estrategias que son
enumeradas de la manera siguiente:
ESTRATEGIAS UTILIZADAS
No. Método Corte Nivel
1 Ramificación y Acotación (math) Ninguno Ninguno
2 Ramificación y Acotación (propio) Ninguno Ninguno
3 Planos Cortantes de Gomory Gomory 0
4 Planos Cortantes de Chvatal -Gomory Chvatal-Gomory 0
5 Ramificación y Cortes Gomory 1
6 Ramificación y Cortes Chvatal-Gomory 1
7 Ramificación y Cortes Gomory 0-1
8 Ramificación y Cortes Chvatal-Gomory 0-1
9 Ramificación y Cortes Gomory 1-0
10 Ramificación y Cortes Chvatal-Gomory 1-0
11 Ramificación y Cortes Gomory 2
12 Ramificación y Cortes Chvatal-Gomory 2
Estructura del análisis:
1. Hacer una comparación de las estrategias implementadas en el software Programación
Lineal en Enteros v.1.0, con el objetivo de determinar cuál o cuáles son las mejores.
2. Hacer una comparación de las mejores con la estrategia número1.
El costo significativo por ejecutar un PLE es el tiempo de solución de computadora. Por
consiguiente decidimos utilizar tiempo de la solución (Tiempo CPU) como el indicador de la
actuación de las estrategias. Además hemos considerado los nodos evaluados como un pa rámetro
de la rapidez con que los métodos se acercan a la solución.
3.2 Descripción de los problemas de Prueba
Capítulo 3.Pruebas Numéricas y Análisis de Resultados
27
Es de vital importancia para cualquier estudio computacional examinar una amplia gama de
problemas de prueba.
Entre los problemas de prueba disponibles nosotros consideramos problemas pequeños
[Zaychenko, ´84], donde todas las variables son enteras. No tiene ningún propósito considerar
aquellos que no tienen ningún punto entero en su región factible o donde las variables asumen
valores grandes.
Un total de 40 problemas de prueba fueron seleccionados (Tabla 1, Apéndice A.1), entre ellos:
31 de 2 variables, entre los cuales 18, 11 y 2 constan con 2, 3 y 4 restricciones
respectivamente.
5 de 3 variables, entre los cuales 2 y 3 constan con 2 y 4 restricciones respectivamente.
3 de 3 variables con 4 restricciones.
1 de 8 variables y 5 restricciones.
En las Tablas 2...13 del Apéndice A.1 se muestran las 12 estrategias aplicadas a lo s problemas
analizados.
3.3 Detalles de la implementación
En el programa: Programación Lineal en Enteros v.1.0 se utilizaron las distintas alternativas
descritas anteriormente. El mismo se implementó en el paquete Mathematica v.6.0.
Capítulo 3.Pruebas Numéricas y Análisis de Resultados
28
Los cortes probados en un gran número de problemas fueron: el corte de Gomory y los de
Chvatal-Gomory. El diseño de la función ProgramacionLinealPart1 y ProgramacionLinealPart2
tienen la ventaja de tener implementados los cuatro métodos analizados en este trabajo
(Ramificación y Acotación, Planos Cortantes de Gomory, Planos Cortantes de Chvatal -Gomory,
y Ramificación y Cortes), solo basta con cambiar l as opciones en dependencia del método que se
desee utilizar. El trabajo con los niveles del árbol para aplicar los cortes fue implementado de
manera general dándole la posibilidad al usuario de aplicar los cortes cada un cierto número n de
niveles, así como una combinación de ellos. Los problemas intermedios fueron resueltos por los
métodos Simplex Revisado y Simplex Dual [Castillo, ´02]. La estrategia para la selección de la
variable a ramificar fue Variables enteras más fraccionarias y para la selección del nodo a
ramificar fue Ramificar por el nodo más nuevo .
El programa fue dividido en 2 partes debido a que en la parte 1 se utiliz ó la técnica de la
reoptimización (adicionar el corte a la última tabla simplex) en relación a los cor tes de Gomory,
este análisis no se realizó para el corte de Chvatal -Gomory.
Capítulo 3.Pruebas Numéricas y Análisis de Resultados
29
Las funciones implementadas en el programa capa ces de resolver cualquier problema en enteros
fueron la función ProgramacionLinealPart1 y ProgramacionLinealPart2.
Sintaxis # 1: )0()0()0()0(0 ,,,,,1Pr UvwuvnbvbLinealPartogramacion
Dado un problema de PLE (problema de minimización) en función de variables básicas y no
básicas la función ProgramacionLinealPart1 resuelve el mismo utilizando el método de
Ramificación y Acotación.
Ejemplo: (Parámetros de la función ProgramacionLinealPart1)
2,1,,0
15301
1742.
4max
21
21
21
ienterox
xx
xxas
xx
i
(3.1)
Cualquier problema de PL es equivalente a un Problema de PL en función de variables básicas y
no básicas, solo basta con hacer un grupo de transformaciones [Castillo, ´02].
El problema (3.1) se puede escribir:
4,3,2,1,,0
30115
4217.
4min
214
213
21
ienterox
xxx
xxxas
xx
i
(3.2)
Donde:
43 , xxvb y 21 , xxvnb
0)0(0 u y 4,1)0( w
15,17)0( v y 3,10,4,2)0( U .
Capítulo 3.Pruebas Numéricas y Análisis de Resultados
30
Sintaxis # 2: OpcionesUvwuvnbvbLinealPartogramacion ,,,,,,1Pr )0()0()0()0(0
Sintaxis # 3: OpcionesUvwuvnbvbLinealPartogramacion ,,,,,,2Pr )0()0()0()0(0
Opciones de ambas funciones:
Cut: Especifica el tipo de corte empleado.
Level: Especifica cada cuántos niveles o combinación de niveles debe aplicarse dicho
corte.
WorkingPrecision: Especifica cuantos dígitos de precisión deben mantenerse en los
cálculos interiores ( significa que se trabaja con fracciones).
Iteración: Cantidad máxima de iteraciones que se pueden llevar a cabo (en el programa se
implementó un mensaje que nos avisa cuando se llega a esta iteraci ón sin alcanzar el
punto óptimo).
M: Los problemas intermedios son resueltos por e l método Simplex o Simplex-Dual. En el
caso del método Simplex se comienza el proceso iterativo a partir de una solución
básica factible, con este objetivo se utiliza el método de la M Grande [Castillo, ´02],
para lograr que dicha solución sea factible (en caso que no lo sea). El valor de la M
debe ser lo suficientemente grande para que cuando se obtenga la solución factible
inicial el valor de min)1(0 u . En caso que esto no ocurra , el problema no daría la
solución óptima (se implementó un mensaje que nos avisa cuando esto ocurre), solo
basta con aumentar el valor de la M .
Opciones por defecto para ambas funciones:
CutNone
LevelNone
WorkingPrecision
Iteracion100
Capítulo 3.Pruebas Numéricas y Análisis de Resultados
31
M20
Llamada a los distintos métodos:
1. Método de Ramificación y Acotación.
)0()0()0()0(0 ,,,,,1Pr UvwuvnbvbLinealPartogramacion , utiliza técnica de reoptimización.
)0()0()0()0(0 ,,,,,2Pr UvwuvnbvbLinealPartogramacion , no utiliza técnica de reoptimización.
2. Método de Planos Cortantes de Gomory.
0,"",,,,,,1Pr )0()0()0()0(0 LevelGomoryCutUvwuvnbvbLinealPartogramacion
3. Método de Planos Cortantes de Chvatal -Gomory.
0,"",,,,,,2Pr )0()0()0()0(0 LeveloryChvatalGomCutUvwuvnbvbLinealPartogramacion
4. Método de Ramificación y Cortes.
nLevelGomoryCutUvwuvnbvbLinealPartogramacion ,"",,,,,,1Pr )0()0()0()0(0
,...,"",,,,,,1Pr 1)0()0()0()0(
0 nLevelGomoryCutUvwuvnbvbLinealPartogramacion
Nota: Utiliza cortes de Gomory.
nLevelGomoryCutUvwuvnbvbLinealPartogramacion ,"",,,,,,2Pr )0()0()0()0(0
,...,"",,,,,,2Pr 1)0()0()0()0(
0 nLevelGomoryCutUvwuvnbvbLinealPartogramacion
Nota: Utiliza cortes de Chvatal-Gomory.
3.4 Ejemplo desde el Mathematica
Sea el siguiente Problema de PLE
Capítulo 3.Pruebas Numéricas y Análisis de Resultados
32
2,1,,0
15301
1742.
4max
21
21
21
ienterox
xx
xxas
xx
i
Nota: La llamada de los problemas se hizo desde un fichero texto.
Ejemplo: (Método de Ramificación y Corte , cada 0-1 niveles de árbol, utilizando el corte de
Gomory).
Paso 1. Escribir en un fichero texto el problema equivalente en función de las variables básicas y
no básicas.
Fichero.txt
0 -1 -4
17 -2 -4
15 -10 -3
Paso 2. Ejecutar el programa: Programación Lineal en Enteros.
Paso 3. Ejecutar la celda donde aparece implementado el código del programa.
Paso 4. Ejecutar
SetDirectory ["Dirección_Fichero"];
Data = ReadList ["Nombre_Fichero.txt", Number, R ecordListsTrue];
Problem =US [Data]
Donde:
Capítulo 3.Pruebas Numéricas y Análisis de Resultados
33
Dirección_Fichero: Especifica la dirección donde se encuentra el fichero con el problema
que se desea resolver, ejemplo: "C:\\Documents and Settings\\usuario\\Escritorio"
Nombre_Fichero: Especifica el nombre del fichero, ejemplo: Fichero.txt
Aclaración de las 3 funciones utilizadas :
SetDirectory: Crea un directorio nuevo (directorio en el cual se encuentre el fichero
con el problema).
ReadList: Lee los datos del fichero entrado por el usuar io en la dirección creada por el
mismo (salida de los datos en forma de lista)
US: Función implementada en el programa que organiza los datos de forma tal que
estén listos para ser usados en las funciones ProgramacionLinelPart1 y
ProgramacioLinealPart2.
Se tiene entonces:
Problem = {{x3, x4}, {x1, x2}, 0, {-1,-4}, {17,15}, {{-2,-4}, {-10,-3}}}
Paso 5. Ejecutar la función ProgramacionLinealPart1 de la siguiente forma:
1,0,"",Pr1Pr LevelGomoryCutoblemLinealPartogramacion
Salida:
Method: Branch & Cut
Cuts Type: Gomory
Level: {0, 1}
Information of the problem:
Optimo Iteraciones Nodos Evaluados Tiempo CPU (m/s)
{-16,{0,4}} 3 4 0.0150
Capítulo 3.Pruebas Numéricas y Análisis de Resultados
34
3.5 Análisis Estadístico
El tiempo de solución muchas veces depende de lo siguiente:
1. El particular sistema utilizado para el estudio.
2. El particular programa usado para resolver los problemas.
En nuestro estudio:
1. Los problemas fueron corridos en un Intel Celeron CPU 2.67 GHz, 247 RAM.
2. Se usó el programa Programación Lineal en Enteros v.1.0 implementado en el paquete
Mathematica v.6.0.
Las diferentes pruebas estadísticas fueron ejecutadas en el paquete SPSS v.11.0
Observación: Debido a que observamos que hay problemas donde el tiempo es casi insignificante
(0.×10-5), se reemplazará dicho valor por 0 (tratamiento a los datos perdidos)
3.5.1 Descriptivo
Breve Introducción:
Al analizar datos, lo primero que tenemos que hacer con una variable es, formarse una idea lo
más exacta posible acerca de sus características. Esto se consigue prestando atención a tres
aspectos básicos: tendencia central, dispers ión y forma de la distribución. Ahora bien, las medidas
de tendencia central y de dispersión, los índices y gráficos sobre la forma de la distribución,
resultan más o menos útiles dependiendo del tipo de variable que se intente caracterizar. Con
variables categóricas, por ejemplo, las medidas de tendencia central y de dispersión , carecen de
importancia comparadas con la utilidad de una distribución de frecuencias o un gráfico sobre la
forma de la distribución. Por e l contrario, con variables continuas una distribución de frecuencias
pierde importancia comparada con la capacidad informativa de las medidas de tendencia central y
de dispersión. Por otro lado, los diagramas que informan sobre la forma de una distribución son
diferentes dependiendo de que la vari able estudiada sea categórica o continua.
Capítulo 3.Pruebas Numéricas y Análisis de Resultados
35
Emplearemos el procedimiento descriptivo ubicado en el menú analizar/estadísticos
descriptivos/descriptivos del SPSS.
Se analizarán un grupo de estadísticos como la media, la asimetría, la curtosis y sus respect ivos
errores tipificados, la varianza, la desviación típica, el menor valor, el mayor valor y los valores
tipificados asociados a cada observación [Bouza, Sistachs , ´04]
Análisis de la Tabla 14 (Apéndice A.2)
Destacar que en la estrategia 7 el mayor tiempo de solución de los problemas fue 0.0470 seg.
Resaltar la rapidez en el tiempo cómputo de las estrategias 7 y 9 con valores promedios por
debajo de 0.03 segundos. Además de la rapidez del grupo formado por las estrategias 5, 11, 3
y 2 que aunque el promedio no supera al anterior es muy bueno con promedios entre 0.03 y
0.04. El error típico de la media nos lleva a concluir que no hay una diferencia significativa
entre las observaciones de cada estrategia, destacando el menor valor en la estrategia 7.
La desviación típica de las estrategias 7, 9, 5, 11, 3 y 2 son muy pequeñas, por debajo del
valor promedio, lo que nos indica que los valores del tiempo para las estrategias anteriormente
mencionadas están muy cercanos a la media.
La varianza de las estrategias 7, 9, 5, 11, 3 y 2 es muy pequeña, ofreciéndonos una idea de
que las estrategias resolvieron todos los problemas en un período de tiempo similar.
Mediante el análisis de los principales estadísticos de distribución (asimetría y curtosis)
llegamos a la conclusión de que la única variable posible a distribuirse normalmente es la
estrategia 7, debido a que el cociente entre el índic e de asimetría y su error típico , y el
cociente entre el índice de curtosis y su error típico son menores en valor absol uto que 1.96,
mientras que las demás estrategias presentan una distribución asimétrica positiva y una
distribución leptocúrtica.
Capítulo 3.Pruebas Numéricas y Análisis de Resultados
36
Se hizo un análisis de los valores tipificados de cada observación con respecto a las
estrategias y nos llevó a la conclusión de que los datos no seguían ninguna distribución
normal.
Análisis de la Tabla 15 (Apéndice A.2)
Destacar en las estrategias 4, 8, 10, 6 y 7 la mayor cantidad de nodos evaluados, por debajo de
11.
Despuntar el valor promedio de nodos evaluados en las est rategias 4, 8, 10, 6, 7 y 9 por
debajo de 5. El error típico de la media nos lleva a concluir que no hay una diferencia
significativa entre las observaciones de todas las estrategias.
La desviación típica de las estrategias son muy pequeñas, por debajo d el valor promedio, lo
que nos indica que los nodos evaluados para estas estrategias están muy cercanos a la media.
Las menores varianzas las encontramos en las estrategias 4, 8, 10, 6 y 7, podemos decir que la
variabilidad de los nodos evaluados para las estrategias anteriormente mencionadas no varían
significativamente.
Mediante el análisis de los principales estadísticos de distribución (asimetría y curtosis)
llegamos a la conclusión de que la única variable posible a distribuirse normalmente es la
estrategia 7, debido a que el cociente entre el índice de asimetría y su error típico, además del
cociente entre el índice de curtosis y su error típico son menores en valor absoluto que 1.96,
mientras que algunas estrategias presentan una distribución asimét rica positiva y otras una
distribución asimétrica negativa. Además algunas presentan una distribución leptocúrtica y
otras una distribución platicúrtica.
Se hizo un análisis de los valores tipificados de cada observación con respecto a las
estrategias, afirmando que los datos no siguen una distribución normal.
Conclusiones: Análisis Descriptivo
Capítulo 3.Pruebas Numéricas y Análisis de Resultados
37
De acuerdo al análisis descriptivo desarrollado concluimos esta primera etapa de la manera
siguiente:
Ranking para las estrategias analizadas:
Tiempo CPU Nodos Evaluados
Estrategias Ranking Estrategias Ranking7 1 4 19 2 8 25 3 10 3
11 4 6 43 5 7 52 6 9 66 7 3 7
10 8 5 88 9 12 9
12 10 11 104 11 2 11
De acuerdo al indicador de tiempo analizado para elegir la mejor , podemos separar las que
utilizan el corte de Gomory como mejores .
De acuerdo al indicador de nodos evaluados podemos concluir que todas las estrategias
poseen promedios casi iguales, resaltando la 4 con el menor promedio.
Prestar una atención especial a la estrategia 7 y 9 con datos que demuestran ser las
mejores para los problemas analizados.
No se puede afirmar nada acerca de qué distribuciones siguen las distintas estrategias .
La única posible a distribuirse normal es la 7.
3.5.2 Exploratorio
Breve Introducción:
Independientemente de la complejidad de los datos disponibles y del procedimiento estadístico
que se tenga intención de utilizar, una exploración minuciosa de los dat os previa al inicio de
cualquier análisis posee importantes ventajas que un analista de datos no puede pasar por alto.
Una exploración minuciosa de los datos permite identificar, entre otras cosas: posibles errores
(datos mal introducidos, respuestas mal c odificadas, etc…), valores extremos (valores que se
Capítulo 3.Pruebas Numéricas y Análisis de Resultados
38
alejan en gran medida del resto), pautas extrañas en los datos (valores que se repiten mucho o
que no aparecen nunca, etc.), variabilidad no esperada (demasiados casos en una de las dos colas
de la distribución, demasiada concentración en torno a determinado valor), etc …
Emplearemos el procedimiento E xplorar, ubicado en el menú analizar/estadísticos
descriptivos/explorar del SPSS.
Analizaremos un grupo de estadísticos como la media truncada (media ari tmética calculada
eliminando el 5 % de los casos con valores más pequeños y el 5 % de los casos con valores más
grandes, con el objetivo de obtener una media menos sensible a la presencia de valores extremos),
la mediana y los percentiles 10, 20, 30,…, 90.
Se aplicará la prueba de Shapiro-Wilk [Shapiro, Wilk, ´65] y el método grafico para comprobar
el supuesto de normalidad.
Análisis de la Tabla 16 (Apéndice A.2)
Al igual que la media (descrita anteriormente), la media recortada nos indica que las
estrategias 7, 9, 5, 11, 2 y 3 poseen un menor promedio de tiempo cómputo .
Análisis de la Tabla 17 (Apéndice A.2)
La media recortada nos indica que las estrategias 4, 7 y 9 po seen un menor promedio de
nodos.
Se analizaron los percentiles anteriormente me ncionados, sin destacar nada nuevo.
Pruebas de Normalidad.
Se analizaron los gráficos Q-Q normal y los gráficos Q-Q normal sin tendencia para todas las
estrategias en cuanto al tiempo y al nivel de nodos evaluados , obteniendo como resultado una
distribución no normal. Se analizó la prueba de Shapiro-Wilk, obteniendo los mismos resultados
que con el análisis gráfico, debido a que en todos los casos el nivel de significación se encuentra
por debajo de 0.05, véase las Tablas 18 y 19, Apéndice A.2.
Capítulo 3.Pruebas Numéricas y Análisis de Resultados
39
Conclusiones del Análisis Exploratorio:
Los resultados son muy similares a los anteriores (sección 3.5.1). Podemos decir que las
estrategias aplicadas no tienen una distribución normal.
3.5.3 No Paramétrico
Breve Introducción:
Existen contrastes que permiten pone r a prueba hipótesis no referidas a parámetros poblacionales;
otros que no necesitan establecer supuestos exigentes sobre las poblaciones de donde se extraen
las muestras; y por último, los que no necesitan trabajar datos obtenidos con una escala de medida
de intervalo o razón. Esta otra familia se conoce con el nombre de Contrastes no p aramétricos o
Pruebas no paramétricas.
Algunos autores utilizan el término “no paramétricos” para referirse únicamente a los
contrastes que no plantean hipótesis sobre parám etros y que se limitan a analizar las
propiedades nominales u ordinales de los datos , además añaden el término de distribución
libre para referirse a los que no necesitan establecer supuestos (o establecen supuestos
poco exigentes, como simetría o continui dad) sobre las poblaciones originales de l as que
se extraen las muestras; pero lo cierto es que el incumplimiento de cualquiera de las tres
características señaladas al principio puede ser considerada suficiente para caracterizar a
un contraste como no paramétrico.
Emplearemos algunos de los procedimientos ubicados en el menú analizar/pruebas no
paramétricas del SPSS para llevar a cabo las distintas pruebas no paramétricas.
Prueba de Kolmogorov-Smirnov:
Se analizó la prueba de Kolmogorov-Smirnov [Kolmogorov, ´33], se comprobaron otros
supuestos de distribución (uniforme y exponencial). Después de obtener los resultados de las
pruebas podemos decir que las distintas estrategias no se ajustan a ninguna de las distribuciones
básicas (normal, uniforme y exponencial).
Capítulo 3.Pruebas Numéricas y Análisis de Resultados
40
Debido a que nuestros datos no se ajustan a la distribución normal no se puede llevar a cabo un
análisis de varianza (ANOVA de un factor), emplearemos entonces la prueba de Friedman
[Friedman, `37] ubicada en el menú analizar/pruebas no parametr icas/k muestras relacionadas.
Los resultados obtenidos nos llevan a concluir que las medias poblacionales de las estrategias
para ambos indicadores difieren debido a que el nivel de significación se obtuvo por debajo de
0.05 (véase las Tablas 20 y 21 de la prueba de Friedman en el apéndice A.2).
Prueba de Wilcoxon:
Pasaremos a comparar las estrategias 2 a 2, para saber con exactitud c uáles difieren y cuáles no,
para éste análisis emplearemos la prueba de Wilcoxon [Wilcoxon, ´45] ubicada en el menú
analizar/pruebas no parametricas/2 muestras relacionadas. Estas se llevarán a cabo en el orden del
ranking de las estrategias , planteado en análisis anteriores y utilizando la corrección de
Bonferroni (con el objetivo de controlar el error de tipo I) que nos llev ará a basar nuestras
decisiones en un nivel de significación de 0.05/11. Un total de 55 pruebas para el tiempo de
CPU y un total de 55 pruebas para los nodos evaluados supuestas a analizar (se van ejecutando y
cuando se obtenga la igualdad de las estrat egias que se estén analizando en ese momento, no se
continúa, puesto que las restantes combinaciones darían el mismo resultado).
Conclusiones de las pruebas de Wilcoxon :
1. Tiempo CPU.
Podemos afirmar que las estrategias 7, 2, 3 5 8 9 y 11 no difieren en cua nto a promedios
poblacionales puesto que la significación de todas las pruebas de Wilcoxon donde se
involucraban dichas estrategias es menor que 0.05/11. De la misma forma concluimos con
las estrategias 6, 4, 8, 10 y 12.
2. Nodos Evaluados.
Podemos afirmar que las estrategias 4, 6, 7, 8, 10 y 12 no difieren en cuanto a promedios
poblacionales puesto que la signif icación de todas las pruebas de Wilcoxon donde se
involucraban dichas estrategias es menor que 0.05/11. De la misma forma concluimos con
las estrategias 9, 2, 3, 5, 12, 11 y 2.
Capítulo 3.Pruebas Numéricas y Análisis de Resultados
41
Comparación con el Mathematica:
Por ser el grupo de estrategias 7, 9, 5, 11, 3 y 2 mejores en cuanto al tiempo que el grupo formado
por 6, 4, 8, 10 y 12, emplearemos la prueba de Friedman para comparar el mejor grupo con la
alternativa 1.
Los resultados obtenidos nos revelan que existe una significación en cuanto a las medias
poblacionales de las estrategias 7, 9, 5, 11 , 3 y 2 con respecto a la estrategia 1, siendo éstas las
mejores.
3.6 Conclusiones
Durante las secciones 3.5.1 y 3.5.2 podemos extraer como mejor estrategia a la 7, pero esto nada
nos dice de la actuación sobre la población de todos los problemas con características semejantes
(dimensión). Tras la culminación de las distintas pruebas no paramé tricas ejecutadas en el
software SPSS v.11.0 apreciamos que no existe una diferencia de medias poblacionales entre las
estrategias 7, 9, 5, 11, 3 y 2 (que fueron las que mejores resultados reportaron, con respecto al
tiempo cómputo), sin embargo el indicador de la cantid ad de nodos evaluados nos llevó a
determinar la eficiencia del Método de Ramificación y Acotación combinado con el Método de
Planos Cortantes de Gomory aplicados cada ,...7,6,4,3,1,0 niveles del árbol.
42
Conclusiones
Como resultado de este trabajo hemos arribado a las siguientes concluciones :
Se logró implementar y poner “puesta a punto” los diferentes algoritmos que permiten
resolver problemas lineales en enteros incluyendo diferentes tipos de corte combinado con
el método de Ramificación y Acotación.
En total fueron probados 40 problemas de PLE. Los resultados num éricos arrojaron que
las soluciones coinciden con el paquete M athematica v.6.0 al 100 %.
La mejor estrategia para resolver problemas pequeños es la aplicación del Método de
Ramificación y Corte, utilizando los cortes de Gomory aplicados cada 0 -1 niveles del
árbol.
La cantidad de nodos evaluados en el Método de Planos Cortantes de Chavatal -Gomory
superan al resto de las estrategias implementadas .
Todas las estrategias de Ramificación y Corte, utilizando el corte de Gomory superan al
método implementado por el paquete Mathematica v.6.0 en su función
LinearProgramming.
43
Recomendaciones
Aplicar el Método de Punto Interior combinado en el algoritmo de Ramificación y Corte,
en la resolución de problemas de Programación Cuadrática Convexa Discreta, para
problemas a grandes escalas.
Implementar la estrategia Uso de estimación en la selección del nodo a ramificar.
44
Bibliografía
[Balas E, Fischetti M., ´93] E. Balas, M. Fischetti. (1993). A lifting procedure for the Asymmetric
Traveling Salesman Polytope and a large new class of facet, Mathematical Programming 58, 325 -
352.
[Bouza C., Sistachs V., ´04] Carlos N. Bouza Herrera, Vivian Sistachs Vega. (2004). Estadística
Teoría Básica y Ejercicios, Primera Edición, Félix Valera.
[Caprara and Fischetti M., ´97] Caprara and M. Fischetti. (1997). Branch and cut algorithms. In
M. Dell`Amico, F. Maffioli, and S. Martello, editors, Annotated Bibliographies in Combinatorial
Optimizations, chapter 4. John Wiley.
[Castillo E., Autores, ´02] Enrique Castillo, Antonio J. Conejo, Pablo Pedregal, Ricardo García,
Natalia Alguacil. (2002). Formulación y Resolución de Modelos de Programación Matemática en
Ingeniería y Ciencia.
[Fischetti M, Lodi A., ´05] M. Fischetti, A. Lodi. (2005). Optimizing over the first Chvátal
closure, in M. Jünger and V. Kailbel (ed.s), Integer Programming and Combinatorial
Optimization - IPCO 2005, LNCS 3509, Springer- Verlag, Berlin Heidelberg, 12-22.
[Friedman M., ´37] Friedman, M. (1937). The use of ranks to avoid the assumption of normality
implicit in the analysis of variance. Journal of the American Statistical Association , 61, 1081-
1096.
[Garfinkel, ´72] Garfinkel. (1972). Integer Programming.
[Gomory R., ´63] R. E. Gomory. (1963). An algorithm for integer solutions to linear programs. In
R. L. Graves and P. Wolfe, editors, Recent Advances in Mathematical Programming , pages 269-
302. McGraw-Hill, New York.
Bibliografía
45
[Grossmann, Caballero J., ´07] Grossmann I. E; Caballero J. A. (2007). ”Una Revisión del Estado
de Arte en Optimización”. Revista Iberoamericana de Automática e Informática Industrial, ISSN:
1697-7912. Vol.4, Num. 1, Enero 2007, pp. 5 -23.
[Grötschel M, Holland O., ’91] M. Gr ötschel, O. Holland. (1991). Solution of large-scale
travelling salesman problems. Mathematical Programming , 51(2):141-202.
[Gupta O. K, Ravindran A., ´85] Omprakash K. Gupta, A. Ravindran. (1985) . “Branch and Bound
experiments in nonlinear integer programming”. Management Science. 31(12) ,1533-1546.
[Johnsonbaugh R., ´04] Richard Johnsonbaugh. (2004). Matemáticas Discretas Tomo II, Cuarta
Edición, Félix Valera.
[Jünger M., Reinelt G., Thienel S., ’95] M. J ünger, G. Reinelt , S. Thienel .(1995). Practical
problem solving with cutting plane algori thms in combinatorial optimization. In Combinatorial
Optimization: DIMACS, Series in Discrete Mathematic and Teoretical Computer Science ,
Volumen 20, 111-152, AMS.
[Kolmogorov, ´33] Kolmogorov. (19 33). A. Sulla determinazione empirica di una legge di
distribuzione. Giornale dell’ Intituto Italiano degli Attuari , 4, 83-91.
[Krume S., ´04] Seven O. Krume. (2004). Integer Programming.
[Land A., Doig A., ´60] A. Land, A. Doig . (1960). An automatic Method of Solving Discrete
Programming Problems, Econometrik a 28, no.3, 497-520.
[Leyffer S., ’98] Sven Leyffer. (1998). Integrating SQP and Brand -and-bound for Mixed Integer
Nonlinear Programming. SIAM Journal Optimization.
[Liberti L., ´06] Leo Liberti. (2006). Integer Programming, LIX, Ecole Polytechnique, F-91128
Palaiseau, France.
Bibliografía
46
[Lieberman, Autores, ´97] Lieberman y Colectivo de Autores. (1997). Investigación de
Operaciones Tomo I y Tomo II. VI edición.
[Mitchell-1 J., ´98] John E. Mitchell. (1998). Cutting Plane Algorithms for Integer, Cutting plane
algorithms.
[Mitchell-2 J., ´98] John E. Mitchell. (1998). Branch and Cut Algorithms for Integer, Branch -and-
Cut.
[Mitchell J., ´99] John E. Mitchell. (1999). Branch and Cut Algorithms for Combinatorial
Optimizations Problems, Mathematica Sciences, Rensselaer Polytechnic Institute Troy, NY, USA ,
September 7.
[Pisinger D., ‘07] David Pisinger. (2007). Introduction to Optimization, DIKU.
[Rinaldi G., Padberg M., ´91] M. Padberg and G. Rinaldi. (1991). A branch -and-cut algorithm for
the resolution of large-scale symmetric traveling salesman problems. SIAM Review, 33(1):60-
100.
[Shapiro S., Wilk, ´65] Shapiro, S. S. y Wilk, M. B. (1965). An analysis of variance test for
normality (complete samples). Biometrika, 52, 591-611.
[Wilcoxon F., ´45] Wilcoxon, F. ( 1945). Individual comparisons by ranking methods. Biometrics,
1, 80-83.
[Wilder M., ´04] Manuel A., Ramón V., Wilder M. (2004). Programación Matemática I.
[Wolfram, ´07] Wolfram Mathematica. (2007). Constrained Optimization Overview.
Bibliografía
47
[Zaychenko Y., Shumilova C., ´84] Zaychenko Yu. P y Shumilova C. A. (1984). Investigación de
Operaciones. Manual de Ejercicios. Escuela Superior Kiev.
48
Apéndice A. Tablas
En éste apéndice representaremos las principales tablas consideradas en el Capítulo 3.
Sección A.1: podemos encontrar la tabla con la descripción detallada de los problemas de
prueba, así como los distintos resultados obtenidos al aplicarle las distintas estrategias.
Sección A.2: podemos encontrar las principales tablas estadísticas.
Sección A.3 mostraremos las notaciones empleadas en las tablas de la sección A.2.
Apéndice
A
Apéndice A. Tablas
49
A.1 Problemas de Prueba
Tabla # 1: Descripción de los Problemas.
ID Variables Restricciones1 2 22 2 23 2 24 2 25 2 26 2 27 2 28 2 29 3 2
10 2 211 4 312 4 313 2 214 2 215 2 316 2 317 4 318 2 319 2 420 2 221 2 322 2 323 3 424 3 425 2 326 2 327 2 428 2 229 3 230 2 331 8 532 2 333 2 234 2 335 2 236 2 237 2 238 3 439 2 3
40 2 2
Apéndice A. Tablas
50
Tabla # 2: Ramificación y Acotación en Mathematica 6.0.
ID IteracionesNodos
EvaluadosTiempo
CPU1 - - 0.0632 - - 0.0473 - - 0.0474 - - 0.0785 - - 0.0796 - - 0.0637 - - 0.0638 - - 0.119 - - 0.078
10 - - 0.06211 - - 0.06212 - - 0.07813 - - 0.07914 - - 0.07815 - - 0.07816 - - 0.04717 - - 0.07818 - - 0.07819 - - 0.09320 - - 0.047
ID IteracionesNodos
EvaluadosTiempo
CPU21 - - 0.07822 - - 0.04723 - - 0.07924 - - 0.09425 - - 0.07826 - - 0.09427 - - 0.07828 - - 0.07829 - - 0.07830 - - 0.03231 - - 0.03132 - - 0.07833 - - 0.06334 - - 0.07835 - - 0.06236 - - 0.06237 - - 0.07838 - - 0.09439 - - 0.06240 - - 0.078
Apéndice A. Tablas
51
Tabla # 3: Ramificación y Acotación (propio).
ID IteracionesNodos
EvaluadosTiempo
CPU1 3 4 0.01602 3 4 0.01503 3 5 0.01604 3 4 0.01505 3 3 0.01606 6 8 0.03107 9 12 0.07808 4 5 0.01609 6 10 0.0470
10 4 5 0.016011 4 6 0.031012 4 4 0.031013 3 4 0.015014 3 5 0.016015 4 5 0.032016 5 6 0.031017 6 8 0.047018 9 12 0.063019 8 11 0.093020 3 5 0.0160
ID IteracionesNodos
EvaluadosTiempo
CPU21 4 5 0.031022 4 4 0.015023 4 5 0.×10-5
24 6 8 0.047025 6 8 0.031026 3 4 0.016027 4 5 0.047028 4 5 0.031029 4 7 0.031030 5 8 0.031031 6 10 0.062032 3 3 0.016033 4 6 0.032034 4 5 0.047035 3 5 0.016036 5 8 0.047037 3 4 0.015038 8 11 0.062039 5 6 0.032040 6 9 0.0790
Apéndice A. Tablas
52
Tabla # 4: Ramificación y Corte.Corte: GomoryNivel: 0
ID IteracionesNodos
EvaluadosTiempo
CPU1 3 3 0.01602 2 2 0.01603 13 13 0.07904 6 6 0.03105 3 3 0.01606 9 9 0.04607 5 5 0.03108 6 6 0.03209 4 4 0.0150
10 3 3 0.015011 4 4 0.031012 5 5 0.015013 2 2 0.015014 8 8 0.047015 6 6 0.031016 9 9 0.046017 3 3 0.016018 2 2 0.016019 3 3 0.016020 2 2 0.0150
ID IteracionesNodos
EvaluadosTiempo
CPU21 8 8 0.046022 4 4 0.015023 3 3 0.016024 17 17 0.109025 5 5 0.031026 2 2 0.016027 7 7 0.047028 4 4 0.015029 2 2 0.015030 7 7 0.046031 5 5 0.031032 3 3 0.015033 3 3 0.016034 2 2 0.016035 9 9 0.047036 4 4 0.016037 3 3 0.015038 25 25 0.219039 6 6 0.031040 2 2 0.0150
Apéndice A. Tablas
53
Tabla # 5: Ramificación y Corte.Corte: Chvatal-GomoryNivel: 0
ID IteracionesNodos
EvaluadosTiempo
CPU1 2 2 0.01502 2 2 0.01603 4 4 0.10904 4 4 0.09405 3 3 0.06206 4 4 0.07907 2 2 0.01608 3 3 0.07809 3 3 0.0310
10 3 3 0.062011 2 2 0.188012 4 4 0.187013 2 2 0.031014 3 3 0.110015 4 4 0.109016 5 5 0.110017 4 4 0.093018 3 3 0.063019 4 4 0.187020 2 2 0.0150
ID IteracionesNodos
EvaluadosTiempo
CPU21 6 6 0.578022 2 2 0.031023 3 3 0.078024 10 10 1.859025 5 5 0.109026 2 2 0.031027 4 4 0.062028 2 2 0.047029 2 2 0.016030 2 2 0.140031 3 3 1.359032 3 3 0.031033 4 4 0.125034 3 3 0.031035 5 5 0.250036 2 2 0.047037 2 2 0.031038 8 8 0.703039 3 3 0.047040 2 2 0.0310
Apéndice A. Tablas
54
Tabla # 6: Ramificación y Corte.Corte: GomoryNivel: 1
ID IteracionesNodos
EvaluadosTiempo
CPU1 3 3 0.01602 3 3 0.01603 3 4 0.01504 4 6 0.03105 3 3 0.01506 6 8 0.04707 4 5 0.03208 6 8 0.04709 6 9 0.0470
10 3 3 0.016011 5 7 0.016012 7 8 0.062013 3 3 0.016014 5 7 0.047015 3 3 0.015016 4 5 0.016017 5 6 0.031018 2 2 0.016019 3 3 0.032020 3 4 0.0160
ID IteracionesNodos
EvaluadosTiempo
CPU21 5 6 0.031022 4 4 0.016023 3 3 0.015024 8 9 0.078025 6 7 0.047026 3 4 0.016027 3 3 0.015028 3 4 0.015029 4 5 0.016030 6 8 0.047031 4 5 0.031032 3 3 0.016033 4 5 0.016034 3 3 0.015035 15 22 0.125036 3 4 0.032037 3 3 0.015038 10 13 0.078039 5 6 0.031040 3 4 0.0150
Apéndice A. Tablas
55
Tabla # 7: Ramificación y Corte.Corte: Chvatal-GomoryNivel: 1
ID IteracionesNodos
EvaluadosTiempo
CPU1 3 3 0.01602 3 3 0.04703 4 5 0.03104 3 4 0.03205 3 3 0.04706 4 5 0.07807 5 6 0.07808 4 5 0.07809 6 8 0.1090
10 3 3 0.031011 4 5 0.375012 5 6 0.219013 3 3 0.016014 3 4 0.062015 3 3 0.063016 4 5 0.093017 6 7 0.141018 2 2 0.031019 3 3 0.063020 3 4 0.0470
ID IteracionesNodos
EvaluadosTiempo
CPU21 3 3 0.062022 4 4 0.062023 5 5 0.140024 5 5 0.282025 4 4 0.063026 3 4 0.094027 3 3 0.046028 3 4 0.031029 4 5 0.063030 5 6 0.125031 6 8 1.594032 3 3 0.031033 3 3 0.032034 3 3 0.047035 4 5 0.062036 3 4 0.016037 3 3 0.046038 8 10 0.297039 4 4 0.046040 3 4 0.0460
Apéndice A. Tablas
56
Tabla # 8: Ramificación y Corte.Corte: GomoryNivel: 0-1
ID IteracionesNodos
EvaluadosTiempo
CPU1 3 4 0.03102 2 2 0.01603 4 5 0.01504 5 6 0.03205 3 3 0.01506 6 7 0.03207 5 6 0.03108 6 7 0.03109 4 5 0.0310
10 5 6 0.031011 5 6 0.031012 5 5 0.031013 2 2 0.×10-5
14 5 6 0.032015 4 4 0.016016 5 6 0.031017 4 5 0.031018 2 2 0.×10-5
19 2 2 0.016020 2 2 0.0150
ID IteracionesNodos
EvaluadosTiempo
CPU21 5 5 0.031022 4 4 0.015023 4 4 0.016024 6 7 0.031025 5 6 0.031026 2 2 0.016027 4 4 0.015028 4 5 0.016029 2 2 0.×10-5
30 7 8 0.047031 4 5 0.032032 3 3 0.016033 4 4 0.031034 2 2 0.×10-5
35 4 5 0.032036 4 5 0.031037 3 4 0.016038 7 9 0.047039 5 5 0.032040 2 2 0.0160
Apéndice A. Tablas
57
Tabla # 9: Ramificación y Corte.Corte: Chvatal-GomoryNivel: 0-1
ID IteracionesNodos
EvaluadosTiempo
CPU1 2 2 0.×10-5
2 2 2 0.01503 4 4 0.09404 4 4 0.07805 3 3 0.03106 3 3 0.06307 2 2 0.04708 3 3 0.03109 3 4 0.0310
10 3 4 0.047011 2 2 0.203012 5 5 0.328013 2 2 0.031014 3 4 0.078015 5 6 0.109016 4 5 0.047017 5 5 0.109018 3 4 0.047019 4 4 0.172020 2 2 0.0320
ID IteracionesNodos
EvaluadosTiempo
CPU21 4 4 0.266022 2 2 0.047023 4 5 0.078024 6 8 0.875025 3 3 0.047026 2 2 0.047027 4 4 0.093028 2 2 0.047029 2 2 0.047030 2 2 0.172031 4 5 1.312032 3 3 0.031033 5 5 0.141034 4 5 0.063035 4 5 0.125036 2 2 0.047037 2 2 0.031038 5 6 0.156039 3 3 0.031040 2 2 0.0320
Apéndice A. Tablas
58
Tabla # 10: Ramificación y Corte.Corte: GomoryNivel: 1-0
ID IteracionesNodos
EvaluadosTiempo
CPU1 3 3 0.×10-5
2 3 3 0.01603 3 4 0.01604 4 5 0.04705 3 3 0.01506 5 6 0.01607 4 5 0.03108 5 6 0.01609 6 7 0.0310
10 3 3 0.×10-5
11 5 6 0.031012 6 7 0.047013 3 3 0.×10-5
14 4 5 0.015015 3 3 0.015016 4 5 0.016017 4 4 0.016018 2 2 0.×10-5
19 3 3 0.016020 3 4 0.0150
ID IteracionesNodos
EvaluadosTiempo
CPU21 4 4 0.016022 4 4 0.016023 3 3 0.015024 8 9 0.078025 6 7 0.046026 3 4 0.015027 3 3 0.031028 3 4 0.016029 4 5 0.031030 6 7 0.031031 4 5 0.047032 3 3 0.015033 4 5 0.031034 3 3 0.016035 8 11 0.047036 3 4 0.015037 3 3 0.016038 12 15 0.093039 4 4 0.031040 3 4 0.0150
Apéndice A. Tablas
59
Tabla # 11: Ramificación y Corte .Corte: Chvatal-GomoryNivel: 1-0
ID IteracionesNodos
EvaluadosTiempo
CPU1 3 3 0.03102 3 3 0.04603 4 4 0.07804 3 4 0.04605 3 3 0.04606 4 5 0.04707 5 6 0.09408 4 5 0.06309 5 6 0.1090
10 3 3 0.031011 4 5 0.359012 6 7 0.234013 3 3 0.031014 3 4 0.047015 3 3 0.047016 4 5 0.063017 6 7 0.156018 2 2 0.031019 3 3 0.063020 3 4 0.0470
ID IteracionesNodos
EvaluadosTiempo
CPU21 3 3 0.063022 4 4 0.047023 4 4 0.094024 6 6 0.453025 5 5 0.110026 3 4 0.062027 3 3 0.047028 3 4 0.047029 4 5 0.063030 5 6 0.156031 5 6 1.406032 3 3 0.047033 3 3 0.063034 3 3 0.031035 4 4 0.094036 3 4 0.047037 3 3 0.047038 9 11 0.375039 4 4 0.109040 3 4 0.0470
Apéndice A. Tablas
60
Tabla # 12: Ramificación y Corte.Corte: GomoryNivel: 2
ID IteracionesNodos
EvaluadosTiempo
CPU1 3 4 0.01502 3 4 0.01503 3 5 0.01604 3 4 0.03105 3 3 0.01606 5 6 0.04607 6 8 0.04608 4 5 0.01609 8 13 0.0630
10 4 5 0.016011 4 6 0.031012 4 4 0.031013 3 4 0.015014 3 5 0.016015 4 5 0.031016 5 6 0.031017 5 6 0.031018 2 2 0.×10-5
19 7 9 0.047020 3 5 0.0160
ID IteracionesNodos
EvaluadosTiempo
CPU21 4 4 0.032022 4 4 0.016023 4 4 0.032024 7 9 0.062025 5 6 0.031026 3 4 0.015027 4 5 0.032028 4 5 0.031029 4 7 0.031030 5 7 0.047031 6 9 0.063032 3 3 0.016033 4 6 0.032034 4 5 0.031035 5 6 0.016036 4 6 0.032037 3 4 0.031038 10 13 0.094039 4 5 0.031040 4 5 0.0310
Apéndice A. Tablas
61
Tabla # 13: Ramificación y Corte.Corte: Chvatal-GomoryNivel: 2
ID IteracionesNodos
EvaluadosTiempo
CPU1 3 4 0.03202 3 4 0.03103 4 5 0.06204 3 4 0.01605 3 3 0.03106 5 6 0.09407 9 12 0.17208 4 5 0.04709 6 9 0.1410
10 4 5 0.062011 4 6 0.078012 4 4 0.094013 3 4 0.032014 3 5 0.031015 4 5 0.078016 5 6 0.110017 5 6 0.1090418 2 2 0.016019 7 9 0.141020 3 5 0.0160
ID IteracionesNodos
EvaluadosTiempo
CPU21 4 5 0.109022 4 4 0.063023 4 4 0.094024 5 5 0.156025 5 6 0.094026 3 4 0.031027 4 5 0.047028 4 5 0.063029 4 7 0.047030 5 6 0.141031 6 9 2.437032 3 3 0.032033 3 3 0.016034 4 5 0.063035 3 4 0.046036 5 8 0.063037 3 4 0.031038 9 12 0.297039 5 6 0.110040 6 8 0.1090
Apéndice A. Tablas
62
A.2 Análisis Estadístico.
Tabla # 14: Estadísticos Descriptivos para la variable Tiempo CPU.
E Min Max Media ETM DT V A ETA C ETC7 .0000 .0470 .023475 .001861 .0117691 .000 -.378 .374 -.193 .7339 .0000 .0930 .024500 .003045 .0192554 .000 1.733 .374 3.943 .7335 .0150 .1250 .030475 .003667 .0231893 .001 2.262 .374 6.328 .733
11 .0000 .0940 .030875 .002768 .0175078 .000 1.450 .374 3.373 .7333 .0150 .2190 .033050 .005691 .0359928 .001 3.972 .374 18.775 .7332 .0000 .0930 .033225 .003314 .0209609 .000 1.087 .374 .814 .7336 .0160 1.5940 .121050 .039791 .2516575 .063 5.434 .374 31.907 .733
10 .0310 1.4060 .126925 .036181 .2288289 .052 4.826 .374 26.161 .7338 .0000 1.3120 .132025 .037782 .2389524 .057 4.041 .374 17.370 .733
12 .0160 2.4370 .136051 .059641 .3772001 .142 6.118 .374 38.172 .7334 .0150 1.8590 .181525 .057416 .3631338 .132 3.656 .374 13.867 .733
Tabla # 15: Estadísticos Descriptivos para la variable Nodos Evaluados.
E Min Max Media ETM DT V A ETA C ETC4 2 10 3.40 .27 1.692 2.862 2.105 .374 5.761 .7338 2 8 3.55 .23 1.484 2.203 .740 .374 .338 .733
10 2 11 4.35 .26 1.642 2.695 1.891 .374 5.676 .7336 2 10 4.42 .26 1.662 2.763 1.425 .374 2.412 .7337 2 9 4.55 .29 1.839 3.382 .164 .374 -.458 .7339 2 15 4.85 .39 2.466 6.079 2.321 .374 6.986 .7333 2 25 5.48 .71 4.501 20.256 2.689 .374 9.020 .7335 2 22 5.53 .56 3.544 12.563 2.898 .374 11.521 .733
12 2 12 5.55 .35 2.230 4.972 1.362 .374 1.967 .73311 2 13 5.65 .37 2.327 5.413 1.696 .374 3.496 .7332 3 12 6.30 .40 2.514 6.318 .906 .374 -.203 .733
Apéndice A. Tablas
63
Tabla # 16: Estadísticos Descriptivos para la variable Tiempo CPU.
E MR Me2 .031722 .0310003 .026778 .0160004 .111472 .0705005 .027389 .0160006 .078917 .0620007 .023472 .0310008 .085528 .0470009 .022472 .016000
10 .087667 .06250011 .029528 .03100012 .074334 .063000
Tabla # 17: Estadísticos Descriptivos para la variable Nodos evaluados.
E MR Me2 6.17 5.003 4.81 4.004 3.17 3.005 5.03 4.506 4.28 4.007 4.47 5.008 3.44 3.509 4.53 4.00
10 4.19 4.0011 5.42 5.0012 5.36 5.00
Apéndice A. Tablas
64
Tabla # 18: Prueba de Normalidad para la variable Tiempo CPU.
Shapiro-WilkE Estadístico gl Sig2 .906 40 .0033 .868 40 .0004 .518 40 .0005 .459 40 .0006 .696 40 .0007 .355 40 .0008 .852 40 .0009 .455 40 .000
10 .793 40 .00011 .404 40 .00012 .838 40 .000
Tabla # 19: Prueba de Normalidad para la variable Nodos Evaluados.
Shapiro-WilkE Estadístico gl Sig2 .875 40 .0003 .707 40 .0004 .758 40 .0005 .708 40 .0006 .850 40 .0007 .927 40 .0138 .869 40 .0009 .759 40 .000
10 .815 40 .00011 .825 40 .00012 .862 40 .000
Apéndice A. Tablas
65
Tabla # 20: Prueba de Friedman para la variable Tiempo CPU.
Chi-cuadrado 216.801gl 10
Sig. asintót. .000
Tabla # 21: Prueba de Friedman para la variable Nodos Evaluad os.
Chi-cuadrado 109.235gl 10
Sig. asintót. .000
A.3 Notación
Análisis Estadístico
Notación DescripciónE Estrategias.
Min Valor más pequeño.Max Valor más grande.
Media Media muestral.ETM Error típico de la media muestral.DT Desviación típica.V Varianza muestral.A Asimetría.
ETA Error típico de la asimetría.C Curtosis.
ETC Error típico de la curtosis.MR Media recortada al 5 %.Me Mediana.