CP debugging needs and tools

Conventional programming techniques are not well suited for solving many highly combinatorial industrial problems, like scheduling, decision making, resource allocation or planning. Constraint Programming (CP), an emerging software technology, offers an original approach allowing for efficient and flexible solving of complex problems, through combined implementation of various constraint solvers and expert heuristics. Its applications are increasingly elded in various industries.

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.

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.

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.

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.