Una generalización de las desigualdades de knapsack cover
Loading...
Date
2018
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
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.
Description
Tesis (Magíster en Ciencias de la Ingeniería)--Pontificia Universidad Católica de Chile, 2018