Column Generation Algorithms for Nonlinear Optimization II: Numerical Investigations

García et al. present a class of column generation (CG) algorithms for nonlinear programs. Its main motivation from a theoretical viewpoint is that under some circumstances, finite convergence can be achieved, in much the same way as for the classic simplicial decomposition method; the main practical motivation is that within the class there are certain nonlinear column generation problems that can accelerate the convergence of a solution approach which generates a sequence of feasible points. This algorithm can, for example, accelerate simplicial decomposition schemes by making the subproblems nonlinear. This paper complements the theoretical study on the asymptotic and finite convergence of these methods given in [1] with an experimental study focused on their computational efficiency. Three types of numerical experiments are conducted. The first group of test problems has been designed to study the parameters involved in these methods. The second group has been designed to investigate the role and the computation of the prolongation of the generated columns to the relative boundary. The last one has been designed to carry out a more complete investigation of the difference in computational efficiency between linear and nonlinear column generation approaches. In order to carry out this investigation, we consider two types of test problems: the first one is the nonlinear, capacitated single-commodity network flow problem of which several large-scale instances with varied degrees of nonlinearity and total capacity are constructed and investigated, and the second one is a combined traffic assignment model

PSO and neural networks: Optimal combination to solve non linear complex problems

Swarm colonies reproduce social habits. Working together in a group to reach a predefined goal is a social behaviour occurring in nature. Linear optimization problems have been approached by different techniques based on natural models. In particular, Particles Swarm optimization is a meta-heuristic search technique that has proven to be effective when dealing with complex optimization problems. This paper presents and develops a new method based on different penalties strategies to solve complex problems. It focuses on the training process of the neural networks, the constraints and the election of the parameters to ensure successful results and to avoid the most common obstacles when searching optimal solutions.

Thermal food processing optimization: Algorithms and software

The algorithms and graphic user interface software package ?OPT-PROx? are developed to meet food engineering needs related to canned food thermal processing simulation and optimization. The adaptive random search algorithm and its modification coupled with penalty function?s approach, and the finite difference methods with cubic spline approximation are utilized by ?OPT-PROx? package (http://tomakechoice. com/optprox/index.html). The diversity of thermal food processing optimization problems with different objectives and required constraints are solvable by developed software. The geometries supported by the ?OPT-PROx? are the following: (1) cylinder, (2) rectangle, (3) sphere. The mean square error minimization principle is utilized in order to estimate the heat transfer coefficient of food to be heated under optimal condition. The developed user friendly dialogue and used numerical procedures makes the ?OPT-PROx? software useful to food scientists in research and education, as well as to engineers involved in optimization of thermal food processing.

Distributed Estimation of Distribution Algorithms for continuous optimization: how does the exchanged information influence their behavior?

One of the most promising areas in which probabilistic graphical models have shown an incipient activity is the field of heuristic optimization and, in particular, in Estimation of Distribution Algorithms. Due to their inherent parallelism, different research lines have been studied trying to improve Estimation of Distribution Algorithms from the point of view of execution time and/or accuracy. Among these proposals, we focus on the so-called distributed or island-based models. This approach defines several islands (algorithms instances) running independently and exchanging information with a given frequency. The information sent by the islands can be either a set of individuals or a probabilistic model. This paper presents a comparative study for a distributed univariate Estimation of Distribution Algorithm and a multivariate version, paying special attention to the comparison of two alternative methods for exchanging information, over a wide set of parameters and problems ? the standard benchmark developed for the IEEE Workshop on Evolutionary Algorithms and other Metaheuristics for Continuous Optimization Problems of the ISDA 2009 Conference. Several analyses from different points of view have been conducted to analyze both the influence of the parameters and the relationships between them including a characterization of the configurations according to their behavior on the proposed benchmark.

NURBS-Based Geometry Parameterization for Aerodynamic Shape Optimization

La motivación de esta tesis es el desarrollo de una herramienta de optimización automática para la mejora del rendimiento de formas aerodinámicas enfocado en la industria aeronáutica. Este trabajo cubre varios aspectos esenciales, desde el empleo de Non-Uniform Rational B-Splines (NURBS), al cálculo de gradientes utilizando la metodología del adjunto continuo, el uso de b-splines volumétricas como parámetros de diseño, el tratamiento de la malla en las intersecciones, y no menos importante, la adaptación de los algoritmos de la dinámica de fluidos computacional (CFD) en arquitecturas hardware de alto paralelismo, como las tarjetas gráficas, para acelerar el proceso de optimización. La metodología adjunta ha posibilitado que los métodos de optimización basados en gradientes sean una alternativa prometedora para la mejora de la eficiencia aerodinámica de los aviones. La formulación del adjunto permite calcular los gradientes de una función de coste, como la resistencia aerodinámica o la sustentación, independientemente del número de variables de diseño, a un coste computacional equivalente a una simulación CFD. Sin embargo, existen problemas prácticos que han imposibilitado su aplicación en la industria, que se pueden resumir en: integrabilidad, rendimiento computacional y robustez de la solución adjunta. Este trabajo aborda estas contrariedades y las analiza en casos prácticos. Como resumen, las contribuciones de esta tesis son: • El uso de NURBS como variables de diseño en un bucle de automático de optimización, aplicado a la mejora del rendimiento aerodinámico de alas en régimen transónico. • El desarrollo de algoritmos de inversión de punto, para calcular las coordenadas paramétricas de las coordenadas espaciales, para ligar los vértices de malla a las NURBS. • El uso y validación de la formulación adjunta para el calculo de los gradientes, a partir de las sensibilidades de la solución adjunta, comparado con diferencias finitas. • Se ofrece una estrategia para utilizar la geometría CAD, en forma de parches NURBS, para tratar las intersecciones, como el ala-fuselaje. • No existen muchas alternativas de librerías NURBS viables. En este trabajo se ha desarrollado una librería, DOMINO NURBS, y se ofrece a la comunidad como código libre y abierto. • También se ha implementado un código CFD en tarjeta gráfica, para realizar una valoración de cómo se puede adaptar un código sobre malla no estructurada a arquitecturas paralelas. • Finalmente, se propone una metodología, basada en la función de Green, como una forma eficiente de paralelizar simulaciones numéricas. Esta tesis ha sido apoyada por las actividades realizadas por el Área de Dinámica da Fluidos del Instituto Nacional de Técnica Aeroespacial (INTA), a través de numerosos proyectos de financiación nacional: DOMINO, SIMUMAT, y CORESFMULAERO. También ha estado en consonancia con las actividades realizadas por el departamento de Métodos y Herramientas de Airbus España y con el grupo Investigación y Tecnología Aeronáutica Europeo (GARTEUR), AG/52. ABSTRACT The motivation of this work is the development of an automatic optimization strategy for large scale shape optimization problems that arise in the aeronautics industry to improve the aerodynamic performance; covering several aspects from the use of Non-Uniform Rational B-Splines (NURBS), the calculation of the gradients with the continuous adjoint formulation, the development of volumetric b-splines parameterization, mesh adaptation and intersection handling, to the adaptation of Computational Fluid Dynamics (CFD) algorithms to take advantage of highly parallel architectures in order to speed up the optimization process. With the development of the adjoint formulation, gradient-based methods for aerodynamic optimization become a promising approach to improve the aerodynamic performance of aircraft designs. The adjoint methodology allows the evaluation the gradients to all design variables of a cost function, such as drag or lift, at the equivalent cost of more or less one CFD simulation. However, some practical problems have been delaying its full implementation to the industry, which can be summarized as: integrability, computer performance, and adjoint robustness. This work tackles some of these issues and analyse them in well-known test cases. As summary, the contributions comprises: • The employment of NURBS as design variables in an automatic optimization loop for the improvement of the aerodynamic performance of aircraft wings in transonic regimen. • The development of point inversion algorithms to calculate the NURBS parametric coordinates from the space coordinates, to link with the computational grid vertex. • The use and validation of the adjoint formulation to calculate the gradients from the surface sensitivities in an automatic optimization loop and evaluate its reliability, compared with finite differences. • This work proposes some algorithms that take advantage of the underlying CAD geometry description, in the form of NURBS patches, to handle intersections and mesh adaptations. • There are not many usable libraries for NURBS available. In this work an open source library DOMINO NURBS has been developed and is offered to the community as free, open source code. • The implementation of a transonic CFD solver from scratch in a graphic card, for an assessment of the implementability of conventional CFD solvers for unstructured grids to highly parallel architectures. • Finally, this research proposes the use of the Green's function as an efficient paralellization scheme of numerical solvers. The presented work has been supported by the activities carried out at the Fluid Dynamics branch of the National Institute for Aerospace Technology (INTA) through national founding research projects: DOMINO, SIMUMAT, and CORESIMULAERO; in line with the activities carried out by the Methods and Tools and Flight Physics department at Airbus and the Group for Aeronautical Research and Technology in Europe (GARTEUR) action group AG/52.

A review of estimation of distribution algorithms in bioinformatics

Evolutionary search algorithms have become an essential asset in the algorithmic toolbox for solving high-dimensional optimization problems in across a broad range of bioinformatics problems. Genetic algorithms, the most well-known and representative evolutionary search technique, have been the subject of the major part of such applications. Estimation of distribution algorithms (EDAs) offer a novel evolutionary paradigm that constitutes a natural and attractive alternative to genetic algorithms. They make use of a probabilistic model, learnt from the promising solutions, to guide the search process. In this paper, we set out a basic taxonomy of EDA techniques, underlining the nature and complexity of the probabilistic model of each EDA variant. We review a set of innovative works that make use of EDA techniques to solve challenging bioinformatics problems, emphasizing the EDA paradigm's potential for further research in this domain.

OSIA: Out-of-order scheduling for in-order arriving in concurrent multi-path transfer.

One major problem of concurrent multi-path transfer (CMT) scheme in multi-homed mobile networks is that the utilization of different paths with diverse delays may cause packet reordering among packets of the same ?ow. In the case of TCP-like, the reordering exacerbates the problem by bringing more timeouts and unnecessary retransmissions, which eventually degrades the throughput of connections considerably. To address this issue, we ?rst propose an Out-of-order Scheduling for In-order Arriving (OSIA), which exploits the sending time discrepancy to preserve the in-order packet arrival. Then, we formulate the optimal traf?c scheduling as a constrained optimization problem and derive its closedform solution by our proposed progressive water-?lling solution. We also present an implementation to enforce the optimal scheduling scheme using cascaded leaky buckets with multiple faucets, which provides simple guidelines on maximizing the utilization of aggregate bandwidth while decreasing the probability of triggering 3 dupACKs. Compared with previous work, the proposed scheme has lower computation complexity and can also provide the possibility for dynamic network adaptability and ?ner-grain load balancing. Simulation results show that our scheme signi?cantly alleviates reordering and enhances transmission performance.

Robustness and Recoverability in Transport Logistics

Abstract Transport is the foundation of any economy: it boosts economic growth, creates wealth, enhances trade, geographical accessibility and the mobility of people. Transport is also a key ingredient for a high quality of life, making places accessible and bringing people together. The future prosperity of our world will depend on the ability of all of its regions to remain fully and competitively integrated in the world economy. Efficient transport is vital in making this happen. Operations research can help in efficiently planning the design and operating transport systems. Planning and operational processes are fields that are rich in combinatorial optimization problems. These problems can be analyzed and solved through the application of mathematical models and optimization techniques, which may lead to an improvement in the performance of the transport system, as well as to a reduction in the time required for solving these problems. The latter aspect is important, because it increases the flexibility of the system: the system can adapt in a faster way to changes in the environment (i.e.: weather conditions, crew illness, failures, etc.). These disturbing changes (called disruptions) often enforce the schedule to be adapted. The direct consequences are delays and cancellations, implying many schedule adjustments and huge costs. Consequently, robust schedules and recovery plans must be developed in order to fight against disruptions. This dissertation makes contributions to two different fields: rail and air applications. Robust planning and recovery methods are presented. In the field of railway transport we develop several mathematical models which answer to RENFE’s (the major railway operator in Spain) needs: 1. We study the rolling stock assignment problem: here, we introduce some robust aspects in order to ameliorate some operations which are likely to fail. Once the rolling stock assignment is known, we propose a robust routing model which aims at identifying the train units’ sequences while minimizing the expected delays and human resources needed to perform the sequences. 2. It is widely accepted that the sequential solving approach produces solutions that are not global optima. Therefore, we develop an integrated and robust model to determine the train schedule and rolling stock assignment. We also propose an integrated model to study the rolling stock circulations. Circulations are determined by the rolling stock assignment and routing of the train units. 3. Although our aim is to develop robust plans, disruptions will be likely to occur and recovery methods will be needed. Therefore, we propose a recovery method which aims to recover the train schedule and rolling stock assignment in an integrated fashion all while considering the passenger demand. In the field of air transport we develop several mathematical models which answer to IBERIA’s (the major airline in Spain) needs: 1. We look at the airline-scheduling problem and develop an integrated approach that optimizes schedule design, fleet assignment and passenger use so as to reduce costs and create fewer incompatibilities between decisions. Robust itineraries are created to ameliorate misconnected passengers. 2. Air transport operators are continuously facing competition from other air operators and different modes of transport (e.g., High Speed Rail). Consequently, airline profitability is critically influenced by the airline’s ability to estimate passenger demands and construct profitable flight schedules. We consider multi-modal competition including airline and rail, and develop a new approach that estimates the demand associated with a given schedule; and generates airline schedules and fleet assignments using an integrated schedule design and fleet assignment optimization model that captures the impacts of schedule decisions on passenger demand.

Design equations for reinforced concrete members strengthened in shear with external FRP reinforcement formulated in an evolutionary multi-objective framework

Methods for predicting the shear capacity of FRP shear strengthened RC beams assume the traditional approach of superimposing the contribution of the FRP reinforcing to the contributions from the reinforcing steel and the concrete. These methods become the basis for most guides for the design of externally bonded FRP systems for strengthening concrete structures. The variations among them come from the way they account for the effect of basic shear design parameters on shear capacity. This paper presents a simple method for defining improved equations to calculate the shear capacity of reinforced concrete beams externally shear strengthened with FRP. For the first time, the equations are obtained in a multiobjective optimization framework solved by using genetic algorithms, resulting from considering simultaneously the experimental results of beams with and without FRP external reinforcement. The performance of the new proposed equations is compared to the predictions with some of the current shear design guidelines for strengthening concrete structures using FRPs. The proposed procedure is also reformulated as a constrained optimization problem to provide more conservative shear predictions.

Approximate Relational Reasoning for Probabilistic Programs

La seguridad verificada es una metodología para demostrar propiedades de seguridad de los sistemas informáticos que se destaca por las altas garantías de corrección que provee. Los sistemas informáticos se modelan como programas probabilísticos y para probar que verifican una determinada propiedad de seguridad se utilizan técnicas rigurosas basadas en modelos matemáticos de los programas. En particular, la seguridad verificada promueve el uso de demostradores de teoremas interactivos o automáticos para construir demostraciones completamente formales cuya corrección es certificada mecánicamente (por ordenador). La seguridad verificada demostró ser una técnica muy efectiva para razonar sobre diversas nociones de seguridad en el área de criptografía. Sin embargo, no ha podido cubrir un importante conjunto de nociones de seguridad “aproximada”. La característica distintiva de estas nociones de seguridad es que se expresan como una condición de “similitud” entre las distribuciones de salida de dos programas probabilísticos y esta similitud se cuantifica usando alguna noción de distancia entre distribuciones de probabilidad. Este conjunto incluye destacadas nociones de seguridad de diversas áreas como la minería de datos privados, el análisis de flujo de información y la criptografía. Ejemplos representativos de estas nociones de seguridad son la indiferenciabilidad, que permite reemplazar un componente idealizado de un sistema por una implementación concreta (sin alterar significativamente sus propiedades de seguridad), o la privacidad diferencial, una noción de privacidad que ha recibido mucha atención en los últimos años y tiene como objetivo evitar la publicación datos confidenciales en la minería de datos. La falta de técnicas rigurosas que permitan verificar formalmente este tipo de propiedades constituye un notable problema abierto que tiene que ser abordado. En esta tesis introducimos varias lógicas de programa quantitativas para razonar sobre esta clase de propiedades de seguridad. Nuestra principal contribución teórica es una versión quantitativa de una lógica de Hoare relacional para programas probabilísticos. Las pruebas de correción de estas lógicas son completamente formalizadas en el asistente de pruebas Coq. Desarrollamos, además, una herramienta para razonar sobre propiedades de programas a través de estas lógicas extendiendo CertiCrypt, un framework para verificar pruebas de criptografía en Coq. Confirmamos la efectividad y aplicabilidad de nuestra metodología construyendo pruebas certificadas por ordendor de varios sistemas cuyo análisis estaba fuera del alcance de la seguridad verificada. Esto incluye, entre otros, una meta-construcción para diseñar funciones de hash “seguras” sobre curvas elípticas y algoritmos diferencialmente privados para varios problemas de optimización combinatoria de la literatura reciente. ABSTRACT The verified security methodology is an emerging approach to build high assurance proofs about security properties of computer systems. Computer systems are modeled as probabilistic programs and one relies on rigorous program semantics techniques to prove that they comply with a given security goal. In particular, it advocates the use of interactive theorem provers or automated provers to build fully formal machine-checked versions of these security proofs. The verified security methodology has proved successful in modeling and reasoning about several standard security notions in the area of cryptography. However, it has fallen short of covering an important class of approximate, quantitative security notions. The distinguishing characteristic of this class of security notions is that they are stated as a “similarity” condition between the output distributions of two probabilistic programs, and this similarity is quantified using some notion of distance between probability distributions. This class comprises prominent security notions from multiple areas such as private data analysis, information flow analysis and cryptography. These include, for instance, indifferentiability, which enables securely replacing an idealized component of system with a concrete implementation, and differential privacy, a notion of privacy-preserving data mining that has received a great deal of attention in the last few years. The lack of rigorous techniques for verifying these properties is thus an important problem that needs to be addressed. In this dissertation we introduce several quantitative program logics to reason about this class of security notions. Our main theoretical contribution is, in particular, a quantitative variant of a full-fledged relational Hoare logic for probabilistic programs. The soundness of these logics is fully formalized in the Coq proof-assistant and tool support is also available through an extension of CertiCrypt, a framework to verify cryptographic proofs in Coq. We validate the applicability of our approach by building fully machine-checked proofs for several systems that were out of the reach of the verified security methodology. These comprise, among others, a construction to build “safe” hash functions into elliptic curves and differentially private algorithms for several combinatorial optimization problems from the recent literature.

Aerodinámica experimental de elementos de parques energéticos

La creciente demanda de energía eléctrica y la necesidad de implementar energías no contaminantes hace que las llamadas tecnologías verdes sean cada día más solicitadas. Entre estas tecnologías encontramos la energía solar y la energía eólica; ambas tienen una trayectoria de uso e investigación bastante amplia, sin embargo aún presentan problemas de fondo que impiden dar mayor impulso a su uso. El objetivo de la presente tesis es presentar soluciones a problemas de optimización en campos conversores de energía. Para ello se analizan y resuelven dos problemas por medio de técnicas de aerodinámica experimental: el primero sobre campos de colectores solares y el segundo sobre campos eólicos. Las técnicas de medición utilizadas en aerodinámica, y en el presente trabajo, son: medición de cargas, anemometría de hilo caliente, velocimetría por imagen de partículas y escaneo de presiones; además de un análisis estadístico de los datos. En el primer caso se ensayan experimentalmente colectores solares parabólicos en donde, por cuestiones de seguridad o por protección contra el viento, se utilizan cercas. Éstas modifican el comportamiento del flujo corriente abajo y se ha encontrado que la distancia a la cual se colocan, así como el tipo de cercas (sólida o permeable), modifican las cargas estructurales a las que los colectores están expuestos. Los resultados demuestran que existe una distancia crítica en la cual la presencia de la cerca aumenta la carga en lugar de disminuirla, por lo cual la selección adecuada del parapeto y la distancia a la cual se coloca son de suma importancia para la optimización de la estructura. En el segundo caso se ensaya experimentalmente y simula numéricamente la estela de turbinas eólicas por medio de discos porosos. En donde un disco permeable simula el rotor de una turbina. El disco es capaz de semejar la estela y los efectos que ésta puede causar corriente abajo. Los resultados muestran que seleccionando adecuadamente la porosidad, es posible simular coeficientes de empuje similares a los desarrollados por los aerogeneradores, además la estela y sus efectos son semejantes a los medidos en campo. ABSTRACT The called green energy technologies are increasingly required because of the growing demand for electricity and the need to implement nonpolluting energy. Among the green energy technologies it is found the solar and the wind energy, both have a history of use and fairly extensive research; however they still have problems which limit to give them further impetus to its use. The aim of this thesis is to present solutions to optimization problems in energy harvesting. To this end it is analysed, and solved, two problems by means of techniques in experimental aerodynamics: the first issue with regard to parabolic troughs and the second about wind farms. The measurement techniques commonly used in aerodynamics, and used in this research work, are: measurement of loads, hot wire anemometry, particle image velocimetry and scanning of pressures; where data are collected and then an statistical analysis is done. In the first case it is tested parabolic troughs where, either for security reasons or protection against the wind actions, fences are used. These fences modify the behaviour of flow downstream and it was found that the distance at which they are placed, and the type of fences (solid or permeable) modify the structural loads to which the parabolic troughs are exposed. The results show that there is a critical distance at which the presence of the fence increases the load instead of protecting the parabolic trough, hence making the proper selection of the parapet and the distance at which it stands are paramount for the optimization of the structure. In the second case it is tested, experimentally and numerically, the wake of wind turbines by means of porous disks; where the permeable disc simulates a turbine rotor. The disc is able to mimic the wake and the effects that it can cause downstream. The results show that by properly selecting the porosity, it is possible to simulate drag coefficients similar to those developed by wind turbines; moreover the porous disk wake and its effects are similar to those measured on field.

Arquitectura de supercomputación en la nube para la resolución de problemas de optimización combinatoria

La tesis está focalizada en la resolución de problemas de optimización combinatoria, haciendo uso de las opciones tecnológicas actuales que ofrecen las tecnologías de la información y las comunicaciones, y la investigación operativa. Los problemas de optimización combinatoria se resuelven en general mediante programación lineal y metaheurísticas. La aplicación de las técnicas de resolución de los problemas de optimización combinatoria requiere de una elevada carga computacional, y los algoritmos deben diseñarse, por un lado pensando en la efectividad para encontrar buenas soluciones del problema, y por otro lado, pensando en un uso adecuado de los recursos informáticos disponibles. La programación lineal y las metaheurísticas son técnicas de resolución genéricas, que se pueden aplicar a diferentes problemas, partiendo de una base común que se particulariza para cada problema concreto. En el campo del desarrollo de software, los frameworks cumplen esa función de comenzar un proyecto con el trabajo general ya disponible, con la opción de cambiar o extender ese comportamiento base o genérico, para construir el sistema concreto, lo que permite reducir el tiempo de desarrollo, y amplía las posibilidades de éxito del proyecto. En esta tesis se han desarrollado dos frameworks de desarrollo. El framework ILP permite modelar y resolver problemas de programación lineal, de forma independiente al software de resolución de programación lineal que se utilice. El framework LME permite resolver problemas de optimización combinatoria mediante metaheurísticas. Tradicionalmente, las aplicaciones de resolución de problemas de optimización combinatoria son aplicaciones de escritorio que permiten gestionar toda la información de entrada del problema y resuelven el problema en local, con los recursos hardware disponibles. Recientemente ha aparecido un nuevo paradigma de despliegue y uso de aplicaciones que permite compartir recursos informáticos especializados por Internet. Esta nueva forma de uso de recursos informáticos es la computación en la nube, que presenta el modelo de software como servicio (SaaS). En esta tesis se ha construido una plataforma SaaS, para la resolución de problemas de optimización combinatoria, que se despliega sobre arquitecturas compuestas por procesadores multi-núcleo y tarjetas gráficas, y dispone de algoritmos de resolución basados en frameworks de programación lineal y metaheurísticas. Toda la infraestructura es independiente del problema de optimización combinatoria a resolver, y se han desarrollado tres problemas que están totalmente integrados en la plataforma SaaS. Estos problemas se han seleccionado por su importancia práctica. Uno de los problemas tratados en la tesis, es el problema de rutas de vehículos (VRP), que consiste en calcular las rutas de menor coste de una flota de vehículos, que reparte mercancías a todos los clientes. Se ha partido de la versión más clásica del problema y se han hecho estudios en dos direcciones. Por un lado se ha cuantificado el aumento en la velocidad de ejecución de la resolución del problema en tarjetas gráficas. Por otro lado, se ha estudiado el impacto en la velocidad de ejecución y en la calidad de soluciones, en la resolución por la metaheurística de colonias de hormigas (ACO), cuando se introduce la programación lineal para optimizar las rutas individuales de cada vehículo. Este problema se ha desarrollado con los frameworks ILP y LME, y está disponible en la plataforma SaaS. Otro de los problemas tratados en la tesis, es el problema de asignación de flotas (FAP), que consiste en crear las rutas de menor coste para la flota de vehículos de una empresa de transporte de viajeros. Se ha definido un nuevo modelo de problema, que engloba características de problemas presentados en la literatura, y añade nuevas características, lo que permite modelar los requerimientos de las empresas de transporte de viajeros actuales. Este nuevo modelo resuelve de forma integrada el problema de definir los horarios de los trayectos, el problema de asignación del tipo de vehículo, y el problema de crear las rotaciones de los vehículos. Se ha creado un modelo de programación lineal para el problema, y se ha resuelto por programación lineal y por colonias de hormigas (ACO). Este problema se ha desarrollado con los frameworks ILP y LME, y está disponible en la plataforma SaaS. El último problema tratado en la tesis es el problema de planificación táctica de personal (TWFP), que consiste en definir la configuración de una plantilla de trabajadores de menor coste, para cubrir una demanda de carga de trabajo variable. Se ha definido un modelo de problema muy flexible en la definición de contratos, que permite el uso del modelo en diversos sectores productivos. Se ha definido un modelo matemático de programación lineal para representar el problema. Se han definido una serie de casos de uso, que muestran la versatilidad del modelo de problema, y permiten simular el proceso de toma de decisiones de la configuración de una plantilla de trabajadores, cuantificando económicamente cada decisión que se toma. Este problema se ha desarrollado con el framework ILP, y está disponible en la plataforma SaaS. ABSTRACT The thesis is focused on solving combinatorial optimization problems, using current technology options offered by information technology and communications, and operations research. Combinatorial optimization problems are solved in general by linear programming and metaheuristics. The application of these techniques for solving combinatorial optimization problems requires a high computational load, and algorithms are designed, on the one hand thinking to find good solutions to the problem, and on the other hand, thinking about proper use of the available computing resources. Linear programming and metaheuristic are generic resolution techniques, which can be applied to different problems, beginning with a common base that is particularized for each specific problem. In the field of software development, frameworks fulfill this function that allows you to start a project with the overall work already available, with the option to change or extend the behavior or generic basis, to build the concrete system, thus reducing the time development, and expanding the possibilities of success of the project. In this thesis, two development frameworks have been designed and developed. The ILP framework allows to modeling and solving linear programming problems, regardless of the linear programming solver used. The LME framework is designed for solving combinatorial optimization problems using metaheuristics. Traditionally, applications for solving combinatorial optimization problems are desktop applications that allow the user to manage all the information input of the problem and solve the problem locally, using the available hardware resources. Recently, a new deployment paradigm has appeared, that lets to share hardware and software resources by the Internet. This new use of computer resources is cloud computing, which presents the model of software as a service (SaaS). In this thesis, a SaaS platform has been built for solving combinatorial optimization problems, which is deployed on architectures, composed of multi-core processors and graphics cards, and has algorithms based on metaheuristics and linear programming frameworks. The SaaS infrastructure is independent of the combinatorial optimization problem to solve, and three problems are fully integrated into the SaaS platform. These problems have been selected for their practical importance. One of the problems discussed in the thesis, is the vehicle routing problem (VRP), which goal is to calculate the least cost of a fleet of vehicles, which distributes goods to all customers. The VRP has been studied in two directions. On one hand, it has been quantified the increase in execution speed when the problem is solved on graphics cards. On the other hand, it has been studied the impact on execution speed and quality of solutions, when the problem is solved by ant colony optimization (ACO) metaheuristic, and linear programming is introduced to optimize the individual routes of each vehicle. This problem has been developed with the ILP and LME frameworks, and is available in the SaaS platform. Another problem addressed in the thesis, is the fleet assignment problem (FAP), which goal is to create lower cost routes for a fleet of a passenger transport company. It has been defined a new model of problem, which includes features of problems presented in the literature, and adds new features, allowing modeling the business requirements of today's transport companies. This new integrated model solves the problem of defining the flights timetable, the problem of assigning the type of vehicle, and the problem of creating aircraft rotations. The problem has been solved by linear programming and ACO. This problem has been developed with the ILP and LME frameworks, and is available in the SaaS platform. The last problem discussed in the thesis is the tactical planning staff problem (TWFP), which is to define the staff of lower cost, to cover a given work load. It has been defined a very rich problem model in the definition of contracts, allowing the use of the model in various productive sectors. It has been defined a linear programming mathematical model to represent the problem. Some use cases has been defined, to show the versatility of the model problem, and to simulate the decision making process of setting up a staff, economically quantifying every decision that is made. This problem has been developed with the ILP framework, and is available in the SaaS platform.

Automated wordlength optimization framework for multi-source statistical interval-based analysis of nonlinear systems with control-flow structures

El uso de aritmética de punto fijo es una opción de diseño muy extendida en sistemas con fuertes restricciones de área, consumo o rendimiento. Para producir implementaciones donde los costes se minimicen sin impactar negativamente en la precisión de los resultados debemos llevar a cabo una asignación cuidadosa de anchuras de palabra. Encontrar la combinación óptima de anchuras de palabra en coma fija para un sistema dado es un problema combinatorio NP-hard al que los diseñadores dedican entre el 25 y el 50 % del ciclo de diseño. Las plataformas hardware reconfigurables, como son las FPGAs, también se benefician de las ventajas que ofrece la aritmética de coma fija, ya que éstas compensan las frecuencias de reloj más bajas y el uso más ineficiente del hardware que hacen estas plataformas respecto a los ASICs. A medida que las FPGAs se popularizan para su uso en computación científica los diseños aumentan de tamaño y complejidad hasta llegar al punto en que no pueden ser manejados eficientemente por las técnicas actuales de modelado de señal y ruido de cuantificación y de optimización de anchura de palabra. En esta Tesis Doctoral exploramos distintos aspectos del problema de la cuantificación y presentamos nuevas metodologías para cada uno de ellos: Las técnicas basadas en extensiones de intervalos han permitido obtener modelos de propagación de señal y ruido de cuantificación muy precisos en sistemas con operaciones no lineales. Nosotros llevamos esta aproximación un paso más allá introduciendo elementos de Multi-Element Generalized Polynomial Chaos (ME-gPC) y combinándolos con una técnica moderna basada en Modified Affine Arithmetic (MAA) estadístico para así modelar sistemas que contienen estructuras de control de flujo. Nuestra metodología genera los distintos caminos de ejecución automáticamente, determina las regiones del dominio de entrada que ejercitarán cada uno de ellos y extrae los momentos estadísticos del sistema a partir de dichas soluciones parciales. Utilizamos esta técnica para estimar tanto el rango dinámico como el ruido de redondeo en sistemas con las ya mencionadas estructuras de control de flujo y mostramos la precisión de nuestra aproximación, que en determinados casos de uso con operadores no lineales llega a tener tan solo una desviación del 0.04% con respecto a los valores de referencia obtenidos mediante simulación. Un inconveniente conocido de las técnicas basadas en extensiones de intervalos es la explosión combinacional de términos a medida que el tamaño de los sistemas a estudiar crece, lo cual conlleva problemas de escalabilidad. Para afrontar este problema presen tamos una técnica de inyección de ruidos agrupados que hace grupos con las señales del sistema, introduce las fuentes de ruido para cada uno de los grupos por separado y finalmente combina los resultados de cada uno de ellos. De esta forma, el número de fuentes de ruido queda controlado en cada momento y, debido a ello, la explosión combinatoria se minimiza. También presentamos un algoritmo de particionado multi-vía destinado a minimizar la desviación de los resultados a causa de la pérdida de correlación entre términos de ruido con el objetivo de mantener los resultados tan precisos como sea posible. La presente Tesis Doctoral también aborda el desarrollo de metodologías de optimización de anchura de palabra basadas en simulaciones de Monte-Cario que se ejecuten en tiempos razonables. Para ello presentamos dos nuevas técnicas que exploran la reducción del tiempo de ejecución desde distintos ángulos: En primer lugar, el método interpolativo aplica un interpolador sencillo pero preciso para estimar la sensibilidad de cada señal, y que es usado después durante la etapa de optimización. En segundo lugar, el método incremental gira en torno al hecho de que, aunque es estrictamente necesario mantener un intervalo de confianza dado para los resultados finales de nuestra búsqueda, podemos emplear niveles de confianza más relajados, lo cual deriva en un menor número de pruebas por simulación, en las etapas iniciales de la búsqueda, cuando todavía estamos lejos de las soluciones optimizadas. Mediante estas dos aproximaciones demostramos que podemos acelerar el tiempo de ejecución de los algoritmos clásicos de búsqueda voraz en factores de hasta x240 para problemas de tamaño pequeño/mediano. Finalmente, este libro presenta HOPLITE, una infraestructura de cuantificación automatizada, flexible y modular que incluye la implementación de las técnicas anteriores y se proporciona de forma pública. Su objetivo es ofrecer a desabolladores e investigadores un entorno común para prototipar y verificar nuevas metodologías de cuantificación de forma sencilla. Describimos el flujo de trabajo, justificamos las decisiones de diseño tomadas, explicamos su API pública y hacemos una demostración paso a paso de su funcionamiento. Además mostramos, a través de un ejemplo sencillo, la forma en que conectar nuevas extensiones a la herramienta con las interfaces ya existentes para poder así expandir y mejorar las capacidades de HOPLITE. ABSTRACT Using fixed-point arithmetic is one of the most common design choices for systems where area, power or throughput are heavily constrained. In order to produce implementations where the cost is minimized without negatively impacting the accuracy of the results, a careful assignment of word-lengths is required. The problem of finding the optimal combination of fixed-point word-lengths for a given system is a combinatorial NP-hard problem to which developers devote between 25 and 50% of the design-cycle time. Reconfigurable hardware platforms such as FPGAs also benefit of the advantages of fixed-point arithmetic, as it compensates for the slower clock frequencies and less efficient area utilization of the hardware platform with respect to ASICs. As FPGAs become commonly used for scientific computation, designs constantly grow larger and more complex, up to the point where they cannot be handled efficiently by current signal and quantization noise modelling and word-length optimization methodologies. In this Ph.D. Thesis we explore different aspects of the quantization problem and we present new methodologies for each of them: The techniques based on extensions of intervals have allowed to obtain accurate models of the signal and quantization noise propagation in systems with non-linear operations. We take this approach a step further by introducing elements of MultiElement Generalized Polynomial Chaos (ME-gPC) and combining them with an stateof- the-art Statistical Modified Affine Arithmetic (MAA) based methodology in order to model systems that contain control-flow structures. Our methodology produces the different execution paths automatically, determines the regions of the input domain that will exercise them, and extracts the system statistical moments from the partial results. We use this technique to estimate both the dynamic range and the round-off noise in systems with the aforementioned control-flow structures. We show the good accuracy of our approach, which in some case studies with non-linear operators shows a 0.04 % deviation respect to the simulation-based reference values. A known drawback of the techniques based on extensions of intervals is the combinatorial explosion of terms as the size of the targeted systems grows, which leads to scalability problems. To address this issue we present a clustered noise injection technique that groups the signals in the system, introduces the noise terms in each group independently and then combines the results at the end. In this way, the number of noise sources in the system at a given time is controlled and, because of this, the combinato rial explosion is minimized. We also present a multi-way partitioning algorithm aimed at minimizing the deviation of the results due to the loss of correlation between noise terms, in order to keep the results as accurate as possible. This Ph.D. Thesis also covers the development of methodologies for word-length optimization based on Monte-Carlo simulations in reasonable times. We do so by presenting two novel techniques that explore the reduction of the execution times approaching the problem in two different ways: First, the interpolative method applies a simple but precise interpolator to estimate the sensitivity of each signal, which is later used to guide the optimization effort. Second, the incremental method revolves on the fact that, although we strictly need to guarantee a certain confidence level in the simulations for the final results of the optimization process, we can do it with more relaxed levels, which in turn implies using a considerably smaller amount of samples, in the initial stages of the process, when we are still far from the optimized solution. Through these two approaches we demonstrate that the execution time of classical greedy techniques can be accelerated by factors of up to ×240 for small/medium sized problems. Finally, this book introduces HOPLITE, an automated, flexible and modular framework for quantization that includes the implementation of the previous techniques and is provided for public access. The aim is to offer a common ground for developers and researches for prototyping and verifying new techniques for system modelling and word-length optimization easily. We describe its work flow, justifying the taken design decisions, explain its public API and we do a step-by-step demonstration of its execution. We also show, through an example, the way new extensions to the flow should be connected to the existing interfaces in order to expand and improve the capabilities of HOPLITE.

Localization and Tracking in Energy-Constrained Networks with Dynamic Connectivity

Systems used for target localization, such as goods, individuals, or animals, commonly rely on operational means to meet the final application demands. However, what would happen if some means were powered up randomly by harvesting systems? And what if those devices not randomly powered had their duty cycles restricted? Under what conditions would such an operation be tolerable in localization services? What if the references provided by nodes in a tracking problem were distorted? Moreover, there is an underlying topic common to the previous questions regarding the transfer of conceptual models to reality in field tests: what challenges are faced upon deploying a localization network that integrates energy harvesting modules? The application scenario of the system studied is a traditional herding environment of semi domesticated reindeer (Rangifer tarandus tarandus) in northern Scandinavia. In these conditions, information on approximate locations of reindeer is as important as environmental preservation. Herders also need cost-effective devices capable of operating unattended in, sometimes, extreme weather conditions. The analyses developed are worthy not only for the specific application environment presented, but also because they may serve as an approach to performance of navigation systems in absence of reasonably accurate references like the ones of the Global Positioning System (GPS). A number of energy-harvesting solutions, like thermal and radio-frequency harvesting, do not commonly provide power beyond one milliwatt. When they do, battery buffers may be needed (as it happens with solar energy) which may raise costs and make systems more dependent on environmental temperatures. In general, given our problem, a harvesting system is needed that be capable of providing energy bursts of, at least, some milliwatts. Many works on localization problems assume that devices have certain capabilities to determine unknown locations based on range-based techniques or fingerprinting which cannot be assumed in the approach considered herein. The system presented is akin to range-free techniques, but goes to the extent of considering very low node densities: most range-free techniques are, therefore, not applicable. Animal localization, in particular, uses to be supported by accurate devices such as GPS collars which deplete batteries in, maximum, a few days. Such short-life solutions are not particularly desirable in the framework considered. In tracking, the challenge may times addressed aims at attaining high precision levels from complex reliable hardware and thorough processing techniques. One of the challenges in this Thesis is the use of equipment with just part of its facilities in permanent operation, which may yield high input noise levels in the form of distorted reference points. The solution presented integrates a kinetic harvesting module in some nodes which are expected to be a majority in the network. These modules are capable of providing power bursts of some milliwatts which suffice to meet node energy demands. The usage of harvesting modules in the aforementioned conditions makes the system less dependent on environmental temperatures as no batteries are used in nodes with harvesters--it may be also an advantage in economic terms. There is a second kind of nodes. They are battery powered (without kinetic energy harvesters), and are, therefore, dependent on temperature and battery replacements. In addition, their operation is constrained by duty cycles in order to extend node lifetime and, consequently, their autonomy. There is, in turn, a third type of nodes (hotspots) which can be static or mobile. They are also battery-powered, and are used to retrieve information from the network so that it is presented to users. The system operational chain starts at the kinetic-powered nodes broadcasting their own identifier. If an identifier is received at a battery-powered node, the latter stores it for its records. Later, as the recording node meets a hotspot, its full record of detections is transferred to the hotspot. Every detection registry comprises, at least, a node identifier and the position read from its GPS module by the battery-operated node previously to detection. The characteristics of the system presented make the aforementioned operation own certain particularities which are also studied. First, identifier transmissions are random as they depend on movements at kinetic modules--reindeer movements in our application. Not every movement suffices since it must overcome a certain energy threshold. Second, identifier transmissions may not be heard unless there is a battery-powered node in the surroundings. Third, battery-powered nodes do not poll continuously their GPS module, hence localization errors rise even more. Let's recall at this point that such behavior is tight to the aforementioned power saving policies to extend node lifetime. Last, some time is elapsed between the instant an identifier random transmission is detected and the moment the user is aware of such a detection: it takes some time to find a hotspot. Tracking is posed as a problem of a single kinetically-powered target and a population of battery-operated nodes with higher densities than before in localization. Since the latter provide their approximate positions as reference locations, the study is again focused on assessing the impact of such distorted references on performance. Unlike in localization, distance-estimation capabilities based on signal parameters are assumed in this problem. Three variants of the Kalman filter family are applied in this context: the regular Kalman filter, the alpha-beta filter, and the unscented Kalman filter. The study enclosed hereafter comprises both field tests and simulations. Field tests were used mainly to assess the challenges related to power supply and operation in extreme conditions as well as to model nodes and some aspects of their operation in the application scenario. These models are the basics of the simulations developed later. The overall system performance is analyzed according to three metrics: number of detections per kinetic node, accuracy, and latency. The links between these metrics and the operational conditions are also discussed and characterized statistically. Subsequently, such statistical characterization is used to forecast performance figures given specific operational parameters. In tracking, also studied via simulations, nonlinear relationships are found between accuracy and duty cycles and cluster sizes of battery-operated nodes. The solution presented may be more complex in terms of network structure than existing solutions based on GPS collars. However, its main gain lies on taking advantage of users' error tolerance to reduce costs and become more environmentally friendly by diminishing the potential amount of batteries that can be lost. Whether it is applicable or not depends ultimately on the conditions and requirements imposed by users' needs and operational environments, which is, as it has been explained, one of the topics of this Thesis.

Automatic design of Ant Colony Optimization for permutation problems

In this study, we present a framework based on ant colony optimization (ACO) for tackling combinatorial problems. ACO algorithms have been applied to many diferent problems, focusing on algorithmic variants that obtain high-quality solutions. Usually, the implementations are re-done for various problem even if they maintain the same details of the ACO algorithm. However, our goal is to generate a sustainable framework for applications on permutation problems. We concentrate on understanding the behavior of pheromone trails and specific methods that can be combined. Eventually, we will propose an automatic offline configuration tool to build an efective algorithm. ---RESUMEN---En este trabajo vamos a presentar un framework basado en la familia de algoritmos ant colony optimization (ACO), los cuales están dise~nados para enfrentarse a problemas combinacionales. Los algoritmos ACO han sido aplicados a diversos problemas, centrándose los investigadores en diversas variantes que obtienen buenas soluciones. Normalmente, las implementaciones se tienen que rehacer, inclusos si se mantienen los mismos detalles para los algoritmos ACO. Sin embargo, nuestro objetivo es generar un framework sostenible para aplicaciones sobre problemas de permutaciones. Nos centraremos en comprender el comportamiento de la sendas de feromonas y ciertos métodos con los que pueden ser combinados. Finalmente, propondremos una herramienta para la configuraron automática offline para construir algoritmos eficientes.