DIM_CMM_2003

Universidad de Chile
Facultad de Ciencias F´ısicas y Matem´aticas
Departamento de Ingenier´ıa Matem´atica

Desarrollo e Implementaci´on de Algoritmos
de Ramificaci´on y Acotamiento para
Resoluci´on de Problemas Enteros
Cuadr´aticos

´
Alvaro
Mois´es Valdebenito Bustamante
Abril 2003

Universidad de Chile
Facultad de Ciencias F´ısicas y Matem´
aticas
Departamento de Ingenier´ıa Matem´
aticaDesarrollo e Implementaci´
on de Algoritmos de
Ramificaci´
on y Acotamiento para Resoluci´
on de
Problemas Enteros Cuadr´
aticos
´
´ VALDEBENITO BUSTAMANTE
ALVARO
MOISES
Comisi´
on Examinadora
Nota(no )

CALIFICACIONES
(Letras)

Firma

Profesor Gu´ıa
Sr. Rafael Correa
Profesor Co-Gu´ıa
Sr. Oscar Barrientos

Profesores Integrantes
´
Sr. Felipe Alvarez

Sr. Roberto Cominetti

Nota Final
Examen deT´ıtulo

MEMORIA PARA OPTAR AL T´ITULO DE
´
INGENIERO CIVIL MATEMATICO
SANTIAGO DE CHILE
Abril 2003

RESUMEN DEL INFORME FINAL
PARA OPTAR AL T´ITULO DE
´
INGENIERO CIVIL MATEMATICO
´
POR: ALVARO
VALDEBENITO B.
PROF. GU´IA: SR. RAFAEL CORREA F.

Desarrollo e Implementaci´
on de Algoritmos de Ramificaci´
on
y Acotamiento para Resoluci´
on de Problemas Enteros
Cuadr´
aticos
El problema entero c´oncavoseparable, y en particular el problema de
asignaci´on cuadr´atica, cuentan con una amplia gama de aplicaciones, entre
estas se cuentan el problema del m´aximo clique, el de partici´on de un grafo,
problemas en computaci´on paralela y distribuida, y en an´alisis estad´ıstico.
Este trabajo consta principalmente de dos partes m´as las conclusiones.
La primera, est´a orientada al estudio y resoluci´on dedos problemas, el problema entero c´oncavo separable, que brinda la formulaci´on necesaria para
el desarrollo te´orico general, y el problema entero bilineal con restricciones
bilineales, sobre el cual se hace una primera implementaci´on computacional.
La segunda parte est´a dedicada al problema de asignaci´on cuadr´atica, para
el cual se implementa una segunda experiencia computacional, tendientea
aprovechar la estructura del problema que no es tomada en cuenta por su
formulaci´on como problema entero bilineal con restricciones bilineales.
El m´etodo utilizado para la resoluci´on de cada uno de estos problemas,
es un algoritmo de ramificaci´on y acotamiento, dicho algoritmo se basa dos
resultados expuestos en la primera parte de este trabajo, el primero es que
el dual de un problemacontinuo c´oncavo separable sobre una regi´on rectangular resulta ser lineal, el segundo es un excelente candidato a punto factible
junto a una condici´on suficiente de optimalidad local.
En cuanto a las experiencias num´ericas, teniendo en cuenta la complejidad de los problemas estudiados (ambos NP-duros), los resultados para el
problema entero bilineal con restricciones bilineales, dada sugeneralidad,
resultan satisfactorios; mostrando as´ı la versatilidad de la t´ecnica empleda.
Mientras que para el problema de asignaci´on cuadr´atica, pese a estar bien
encaminado, la t´ecnica utilizada todav´ıa no logra explotar toda la estructura
del problema.

AGRADECIMIENTOS
Dentro de lo posible, quisiera agradecer a quienes me ayudaron y apoyaron durante el desarrollo de este trabajo:
A Rafael Correay Oscar Barrientos, sin su gu´ıa este trabajo no existir´ıa.
´
A Roberto Cominetti y Felipe Alvarez,
por formar parte de la comisi´on
examinadora. Oscar Barrientos, merece adem´as mi agradecimiento por su
paciencia y dedicaci´on. Al Departamento de Ingenier´ıa Matem´atica, Centro
de Modelamiento Matem´atico y sus integrantes, por proveer de un excelente
ambiente de trabajo y estudio, y porpermitirme ser parte de ´el.
A mis amigos Nelson Morales y Luis Rademacher, por su omnipresente
apoyo t´ecnico. En particular quiero agradecer a Patricio Reyes, mi gran
amigo y compa˜
nero desde siempre, y a P´ıa Villarroel (Moima), por su apoyo
y compa˜
n´ıa en la elaboraci´on y revisi´on de este trabajo, a quienes espero
nunca terminar de agradecer.
Finalmente, quiero agradecer a mis abuelos, a mi...