Dublin Core
Title
Una generalización de las desigualdades de knapsack cover
Subject
510
Matemática física y química
Optimización matemática.
Programación dinámica.
Description
Tesis (Magíster en Ciencias de la Ingeniería)--Pontificia Universidad Católica de Chile, 2018
Los problemas de cubrimiento aparecen naturalmente en optimización discreta. En su versión más básica, debemos elegir un conjunto de artículos de costo mínimo que cubra una determinada demanda. Este es el clásico problema de la mochila en su versión de cubrimiento o Minimum Knapsack, que es NP-hard. A diferencia de la versión original, la relajación lineal natural de esta versión tiene un gap de integralidad no acotado. Carret al. (2000) idearon un conjunto de desigualdades, las knapsack-cover inequalities, para fortalecer esta relajación y reducir el gap a 2.En esta tesis, consideramos un contexto natural donde cada elemento se puede tomar de manera fraccionada, pero con costo no lineal, lo que es una generalización del problema anterior. Extendemos las knapsack-cover inequalities para el caso de funciones de costos lineales por partes, mostramos que su relajación y un algoritmo primal-dual mantienen el gap de integralidad en 2. Al aproximar funciones de costos generales no decrecientes y continua por la izquierda por funciones lineales por partes, podemos obtener un algoritmo primal-dual (2+")-aproximado para estas funciones generales. Finalmente, probamos nuestro algoritmo computacionalmente usando datos basados en el problema de generación de energía con demanda simple, donde se tiene una demanda eléctrica y un conjunto de centrales de producción con funciones de costo no lineales y discontinuas. Mostramos que nuestro algoritmo primal-dual alcanza errores promedio por debajo del 4% al compararse con la solución dual obtenida. Además, observamos que disminuye el error al aumentar la demanda. Una pregunta abierta es si nuestras desigualdades se pueden utilizar para problemas más generales, como el Unsplittable Flow-cover Problem on a path con costos no lineales que, en cierto sentido, agrega una dimensión temporal al problema. Esto abriría la posibilidad de considerar problemas de generación de energía dinámicos.
Creator
Morales Muñoz, Ignacio
Date
2018-08-08T13:31:09Z
2018-08-08T13:31:09Z
2018
Contributor
Verschae, José
Pontificia Universidad Católica de Chile. Escuela de Ingeniería
Rights
acceso abierto
Format
xi, 78 hojas
application/pdf
Language
es
Type
tesis de maestría
Identifier
10.7764/tesisUC/ING/21971
https://doi.org/10.7764/tesisUC/ING/21971
https://repositorio.uc.cl/handle/11534/21971