Técnicas de optimización / Albert Corominas, coordinador, Carles Batlle Arnau, Ernest Benedito Benet, y...[otros siete]

Incluye índice al inicio del texto.

Incluye referencias bibliográficas al final de cada capítulo.

1. VECTORES ÓPTIMOS EN ESPACIOS REALES (Ernest Benedito).
1.1. INTRODUCCIÓN.
1.2. OPTIMIZACIÓN UNIDIMENSIONAL.
1.2.1. Condiciones necesarias y condiciones suficientes de óptimo.
1.2.2. Métodos para hallar mínimos locales en programas unidimensionales.
1.3. OPTIMIZACIÓN MULTIDIMENSIONAL SIN RESTRICCIONES.
1.3.1. Condiciones necesarias y condiciones suficientes de óptimo.
1.3.2. Métodos para hallar mínimos locales en programas multidimensionales sin restricciones.
1.4. OPTIMIZACIÓN MULTIDIMENSIONAL CON RESTRICCIONES DE IGUALDAD.
1.4.1. Condiciones necesarias y condiciones suficientes de óptimo.
1.4.2. Métodos para hallar mínimos locales en programas multidimensionales con restricciones de igualdad.
1.5. OPTIMIZACIÓN CON RESTRICCIONES DE CUALQUIER TIPΟ.
1.5.1. Condiciones necesarias y condiciones suficientes de óptimo.
1.5.2. Métodos para hallar el óptimo de un programa lineal.
1.5.3. Métodos para hallar el óptimo de un programa cuadrático.
1.5.4. Métodos para hallar el óptimo de un programa con restricciones lineales.
1.5.5. Métodos para hallar el óptimo de un programa con restricciones de cualquier tipo.
BIBLIOGRAFÍA.
ANEXO: DEFINICIONES Y PROPIEDADES.

2. EXPLORACIÓN ARBORESCENTE (Rafael Pastor).
2.1. INTRODUCCIÓN.
2.2. EXPLORACIÓN ARBORESCENTE.
2.3. INTRODUCCIÓN A LA PROPAGACIÓN DE RESTRICCIONES.
2.3.1. El problema de satisfacción de restricciones y las técnicas de consistencia.
2.3.2. La propagación de restricciones.
2.3.3. Resolución de problemas de optimización mediante propagación de restricciones.
2.4. LOS PROCEDIMIENTOS DE RAMIFICACIÓN Y ACOTACIÓN.
2.4.1. El branch and bound.
2.4.2. Otros procedimientos de exploración arborescente basados en la poda de vértices mediante cotas.
2.5. BRANCH AND WIN: METALGORITMO DE OPTIMIZACIÓN COMBINATORIA MEDIANTE LA EXPLORACIÓN DE GRAFOS.
2.5.1. Definiciones previas.
2.5.2. Una formalización de branch and win.
2.5.3. Detalle de los procedimientos utilizados en branch and win.
2.5.4. Branch and win: un metalgoritmo general.
2.6. LA EXPLORACIÓN ARBORESCENTE EN LA RESOLUCIÓN DE PROGRAMAS MATEMÁTICOS CON VARIABLES ENTERAS.
BIBLIOGRAFÍA.

3. MODELIZACIÓN DE PROBLEMAS DE OPTIMIZACIÓN (Amaia Lusa y Bruno Domenech).
3.1. INTRODUCCIÓN.
3.1.1. Ejemplos introductorios.
3.1.2. Pasos a seguir para modelizar un problema de optimización.
3.1.3. Organización del resto del capítulo.
3.2. TÉCNICAS DE MODELIZACIÓN CON VARIABLES CONTINUAS.
3.2.1. Minimax y maximin.
3.2.2. Minimizar el valor absoluto de una expresión.
3.2.3. Cota superior del valor absoluto de una expresión.
3.2.4. Programación separable convexa.
3.3. TÉCNICAS DE MODELIZACIÓN CON VARIABLES ENTERAS Y BINARIAS.
3.3.1. Por qué aparecen las variables enteras y binarias.
3.3.2. Ejemplos introductorios.
3.3.3. Redondear al entero inferior, al entero superior o al entero más próximo.
3.3.4. Expresiones que deben pertenecer a un conjunto de valores.
3.3.5. Conjunción, disyunción y exclusión: significado y notación.
3.3.6. Disyunción.
3.3.7. Exclusión (disyunción exclusiva).
3.3.8. Implicación.
3.3.9. Doble implicación (variables indicadoras): caso general y casos particulares (monomios binarios).
3.3.10. Relaciones lógicas entre condiciones: forma normal.
conjuntiva (FNC) y forma normal disyuntiva (FND).
3.3.11. Funciones separables no lineales y no convexas.
3.3.12. Producto de funciones lineales.
3.4. RELACIÓN ENTRE LA MODELIZACIÓN Y LA EFICIENCIA COMPUTACIONAL.
3.4.1. Técnicas elementales.
3.4.2. Técnicas avanzadas: restricciones válidas (planos de corte).
3.5. OPTIMIZACIÓN BAJO INCERTIDUMBRE.
3.5.1. Causas de incertidumbre.
3.5.2. Optimización mediante lógica difusa (fuzzy).
3.5.3. Optimización estocástica por escenarios
3.6. OPTIMIZACIÓN MULTIOBJETIVO.
3.6.1. Contexto multiobjetivo.
3.6.2. Conceptos básicos.
3.6.3. Optimización jerárquica.
3.6.4. Programación por metas (Goal Programming).
BIBLIOGRAFÍA.

4. HEURÍSTICAS (Albert Corominas).
4.1. INTRODUCCIÓN.
4.1.1. A qué problemas se refiere este capítulo.
4.1.2. Heurísticas.
4.1.3. Organización del resto del capítulo.
4.2. ESTRUCTURA GENERAL DE LOS PROCEDIMIENTOS HEURÍSTICOS.
4.3. EJEMPLOS DE PROBLEMAS, HEURÍSTICAS Y COTAS.
4.3.1. El problema de la mochila (knapsack problem, KP).
4.3.2. Bin packing, SALBP-1, Pm ||Cmax.
4.3.3. El traveling salesperson problem (TSP).
4.3.4. El problema del cubrimiento de cardinalidad mínima (minimum cardinality cover problem).
4.3.5. Conjunto interiormente estable de peso máximo (maximum weight independent set problem).
4.3.6. Fm prmu | Cmax.
4.3.7. El problema de transporte.
4.3.8. Programación de proyectos con restricciones disyuntivas y de precedencia.
4.4. PRE-PROCESAMIENTO.
4.5. HEURÍSTICAS VORACES.
4.5.1. Introducción.
4.5.2. Orientaciones para el diseño de heurísticas voraces.
4.5.3. Familias de heurísticas voraces: EAGH.
4.5.4. Cócteles de heurísticas.
4.6. CÁLCULO DE COTAS.
4.7. PROCEDIMIENTOS DE MEJORA: OPTIMIZACIÓN LOCAL
4.7.1. Conceptos generales.
4.7.2. Vecindarios
4.7.3. Algoritmos de optimización local.
4.8. SÍNTESIS Y CONCLUSIONES
BIBLIOGRAFÍA

5. METAHEURÍSTICAS, HIPERHEURÍSTICAS Y MATHEURÍSTICAS (Alberto García-Villoria).
5.1. INTRODUCCIÓN.
5.1.1. Origen, motivación y concepto.
5.1.2. Organización del resto del capítulo.
5.2. METAHEURÍSTICAS.
5.2.1. Introducción.
5.2.2. Búsqueda Local Iterativa (Iterated Local Search, ILS).
5.2.3. Recocido Simulado (Simulated Annealing, SA).
5.2.4. Búsqueda Tabú (Tabu Search, TS).
5.2.5. Procedimiento de Búsqueda Voraz Adaptativo Probabilista (Greedy Randomized Adaptive Search Procedure, GRASP).
5.2.6. Búsqueda de Vecindario Variable (Variable Neighborhood Search, VNS).
5.2.7. Algoritmo Genético (Genetic Algorithm, GA).
5.2.8. Algoritmo de la Colonia de Hormigas (Ant Colony Optimization, ACO).
5.2.9. Optimización por Nube de Partículas (Particle Swarm Optimization, PSO).
5.2.10. Hibridación de metaheurísticas.
5.2.11. Abuso de metaheurísticas nuevas.
5.3. HIPERHEURÍSTICAS.
5.3.1. Introducción.
5.3.2. Hiper Heurísticas constructivas.
5.3.3. Hiperheuristicas de mejoramiento.
5.4. MATHEURÍSTICAS.
5.4.1. Introducción.
5.4.2. Local Branching.
5.4.3. Corridor Method.
5.4.4. Relax and Fix.
5.5. EJEMPLO DE APLICACIÓN: BIN PACKING EN UNA DIMENSIÓN.
5.5.1. Problema y representación de la solución.
5.5.2. Solución inicial, vecindario y procedimiento de optimización local.
5.5.3. Búsqueda Local Iterativa (ILS).
5.5.4. Recocido Simulado (SA).
5.5.5. Búsqueda Tabú (TS).
5.5.6. Procedimiento de Búsqueda Voraz Adaptativo Probabilista (GRASP).
5.5.7. Búsqueda de Vecindario Variable (VNS).
5.5.8. Algoritmo Genético (GA).
5.5.9. Algoritmo de la Colonia de Hormigas (ACO).
5.5.10. Optimización por Nube de Partículas (PSO).
5.5.11. Hiperheurísticas.
5.5.12. Matheurísticas.
5.6. EJEMPLO DE APLICACIÓN: CARGAS EN UN ANDAMIO.
5.6.1. Problema, representación de la solución y enfoque de resolución.
5.6.2. Matheurística basada en Búsqueda Local Iterativa (ILS).
5.6.3. Matheuristica basada en Algoritmo Genético (GA).
5.6.4. Matheurística basada en Optimización por Nube de Partículas (PSO).
5.7. SÍNTESIS Y CONCLUSIONES.
BIBLIOGRAFÍA.

6. CALIBRACIÓN Y EXPERIENCIAS COMPUTACIONALES (Alberto García-Villoria y Ernest Benedito).
6.1. INTRODUCCIÓN.
6.1.1. Conceptos y motivación.
6.1.2. Organización del resto del capítulo.
6.2. CALIBRACIÓN DE LOS PARÁMETROS.
6.2.1. Introducción.
6.2.2. Ejemplares de entrenamiento.
6.2.3. Cómo calibrar.
6.3. EXPERIENCIA COMPUTACIONAL.
6.3.1. Introducción.
6.3.2. Ejemplares de testeo.
6.3.3. Métricas y diseño de la experiencia computacional.
6.3.4. Análisis de los resultados.
6.3.5. Replicabilidad, duplicabilidad y números pseudoaleatorios.
6.4. SÍNTESIS Y CONCLUSIONES.
BIBLIOGRAFÍA.

7. MODELIZACIÓN Y RESOLUCIÓN BASADAS EN LA TEORÍA DE GRAFOS (Ernest Benedito y Albert Corominas).
7.1. INTRODUCCIÓN.
7.2. TERMINOLOGÍA BÁSICA DE LA TEORÍA DE GRAFOS.
7.3. CAMINOS EXTREMOS EN UN GRAFO.
7.4. PROGRAMACIÓN DINÁMICA DETERMINISTA DISCRETA.
7.5. FLUJOS ÓPTIMOS.
7.5.1. El problema del flujo compatible de coste mínimo en una red de transporte.
7.5.2. El algoritmo de Ford-Fulkerson para el problema del flujo máximo.
7.6. ÁRBOLES DE DECISIÓN.
7.7. PROCESOS DE DECISIÓN EN CADENAS DE MÁRKOV.
7.7.1. Conceptos básicos sobre cadenas de Márkov.
7.7.2. Procesos markovianos de decisión.
7.7.3. Problemas de procesos markovianos de decisión con actualización de recompensas (PPMD-A).
7.7.4. Problemas de procesos markovianos de decisión con el promedio de las recompensas (PPMD-P).
BIBLIOGRAFÍA.

8. CONTROL ÓPTIMO (Carles Batlle y Enric Fossas).
8.1. INTRODUCCIÓN.
8.1.1. Sistemas de control. Tiempo discreto y tiempo continuo.
8.1.2. Control óptimo. Funcionales y cálculo de variaciones.
8.2. PROGRAMACIÓN DINÁMICA. PRINCIPIO DE OPTIMALIDAD.
8.3. LA ECUACIÓN DE HAMILTON-JACOBI-BELLMAN.
8.4. EJEMPLOS DE SOLUCIÓN DE LA ECUACIÓN DE HJB.
8.4.1. Ejemplo 1.
8.4.2. Ejemplo 2.
8.4.3. Ejemplo 3.
8.4.4. Ejemplo 4: el regulador lineal cuadrático.
8.5. ECUACIONES DE EULER-LAGRANGE.
8.6. EL PRINCIPIO DE PONTRYAGIN.
8.7. EJEMPLOS DE USO DEL PRINCIPIO DE PONTRYAGIN.
8.7.1. Ejemplo 1.
8.7.2. Ejemplo 2.
8.7.3. El regulador lineal cuadrático.
8.7.4. Estado final sobre una variedad.
8.7.5. Tiempo óptimo.
8.8. COMPARACIÓN DE LOS MÉTODOS BASADOS EN LA PROGRAMACIÓN DINÁMICA Y EN EL PRINCIPIO DE PONTRYAGIN.
8.9. MÉTODOS NUMÉRICOS.
8.9.1. Métodos numéricos para la ecuación de HJB. La ecuación diferencial de Riccati.
8.9.2. Métodos numéricos para la solución de problemas de frontera.
BIBLIOGRAFÍA.