Spelling suggestions: "subject:"polyhedral approach"" "subject:"polyhedrals approach""
1 |
Optimización lineal entera mixta aplicada a problemas de planificación estratégica en electricidadAngulo Cárdenas, Alejandro Alberto January 2015 (has links)
Doctor en Sistemas de Ingeniería / En esta tesis se presentan los resultados del trabajo desarrollado por el autor durante el
periodo en que fue estudiante de doctorado en el Departamento de Industrias de la Universidad
de Chile. El trabajo se centra en la aplicación de técnicas de optimización entera-mixtas
a problemas de planificación estratégica del sector eléctrico, donde el problema de corto plazo
correspondiente al predespacho de unidades de generación en sistemas térmicos es el tema
central en estudio.
En lo relativo al modelamiento del problema de predespacho de unidades, se considera
el análisis de las distintas formulaciones entera-mixtas disponibles en la literatura junto con
una nueva basada en un formulaciones extendidas tipo red. Se investiga su desempeño sobre
un conjunto de instancias reales desde el punto de vista de su eficiencia computacional al
ser resueltas con softwares comerciales. Lo anterior incluye análisis de tiempos de solución,
nodos utilizados e iteraciones de simplex realizadas para distintas tolerancias requeridas. Los
experimentos muestran la calidad de la aproximación propuesta, siendo esta completamente
competitiva respecto a las ya documentadas. Este resultado era esperable, dada la estructura
totalmente unimodular de gran parte de la formulación propuesta, pero para nada justificable
debido al tamaño de la misma. Lo anterior muestra que el efecto del preproceso de los
softwares comerciales puede ser fundamental en algunas formulaciones.
Por otro lado, respecto a la función objetivo del problema de predespacho de unidades, que
por lo general se representa como una función cuadrática de la generación, se presenta una
nueva manera de linealizar su comportamiento de modo que su inclusión en una formulación
entera-mixta lineal tradicional sea eficiente. Esto último debe entenderse a partir de la necesidad
que el tamaño de la aproximación no crezca de manera desmedida si el error requerido
para la misma decrece. Si bien ya existía la posibilidad de hacer esto mediante la aplicación
de la aproximación desarrollada por Ben-Tal y Nemirovsky para conos de segundo orden [2],
acá se presenta un método alternativo, con mejores propiedades numéricas, un orden de magnitud
mejor en calidad de aproximación, y cuya aplicación a problemas reales de predespacho
de unidades genera mejores resultados respecto de las aproximaciones tradicionales.
Por último, con el fin de mejorar el desempeño de la formulación entera-mixta presentada,
se realiza el análisis poliedral de una de sus subestructuras esperando identificar desigualdades
válidas que permitan mejorar su cota dual. Esta subestructura corresponde al knapsack semicontinuo
con restricciones adicionales del tipo generalized upper bound. Se demuestra que bajo
supuestos simples es posible identificar facetas tipo generalized flow cover en espacios restringidos
de dimensión inferior. Luego se llevan estas desigualdades al espacio original utilizando
procedimientos de lifting multidimensional independiente de la secuencia [38, 27, 16, 17] y se
iii
prueba que con supuestos adicionales también son facetas allí. Experimentos computacionales
en instancias derivadas de problemas de UC muestran su eficiencia, donde más de un 50%
del gap integral del nodo raíz se reduce aplicando en promedio solo tres de estos cortes.
Además, en este contexto, también se ha implementado un solver ad-hoc para la solución
eficiente de las relajaciones lineales de la formulación tipo red, con un speed-up del orden de
4x a 8x respecto a CPLEX barrier optimizer, pero que aún no está documentado.
|
2 |
K-Separator problem / Problème de k-SéparateurMohamed Sidi, Mohamed Ahmed 04 December 2014 (has links)
Considérons un graphe G = (V,E,w) non orienté dont les sommets sont pondérés et un entier k. Le problème à étudier consiste à la construction des algorithmes afin de déterminer le nombre minimum de nœuds qu’il faut enlever au graphe G pour que toutes les composantes connexes restantes contiennent chacune au plus k-sommets. Ce problème nous l’appelons problème de k-Séparateur et on désigne par k-séparateur le sous-ensemble recherché. Il est une généralisation du Vertex Cover qui correspond au cas k = 1 (nombre minimum de sommets intersectant toutes les arêtes du graphe) / Let G be a vertex-weighted undirected graph. We aim to compute a minimum weight subset of vertices whose removal leads to a graph where the size of each connected component is less than or equal to a given positive number k. If k = 1 we get the classical vertex cover problem. Many formulations are proposed for the problem. The linear relaxations of these formulations are theoretically compared. A polyhedral study is proposed (valid inequalities, facets, separation algorithms). It is shown that the problem can be solved in polynomial time for many special cases including the path, the cycle and the tree cases and also for graphs not containing some special induced sub-graphs. Some (k + 1)-approximation algorithms are also exhibited. Most of the algorithms are implemented and compared. The k-separator problem has many applications. If vertex weights are equal to 1, the size of a minimum k-separator can be used to evaluate the robustness of a graph or a network. Another application consists in partitioning a graph/network into different sub-graphs with respect to different criteria. For example, in the context of social networks, many approaches are proposed to detect communities. By solving a minimum k-separator problem, we get different connected components that may represent communities. The k-separator vertices represent persons making connections between communities. The k-separator problem can then be seen as a special partitioning/clustering graph problem
|
Page generated in 0.065 seconds