Search

Network Alignment (NA) is a hard optimization problem with important applications such as, for example, the identification of orthologous relationships between different proteins and of phylogenetic relationships between species. Given two (or more) networks, the goal is to find an alignment between them, that is, a mapping between their respective nodes such that the topological and functional structure is well preserved. Although the problem has received great interest in recent years, there is still a need to unify the different trends that have emerged from diverse research areas. In this paper, we introduce AntNetAlign, an Ant Colony Optimization (ACO) approach for solving the problem. The proposed approach makes use of similarity information extracted from the input networks to guide the construction process. Combined with an improvement measure that depends on the current construction state, it is able to optimize any of the three main topological quality measures. We provide an extensive experimental evaluation using real-world Protein-Protein Interaction (PPI) networks. Results show that our method outperforms other state-of-the-art approaches in two out of three of the tested scores within a reasonable amount of time, specially in the important S3score. Moreover, it is able to obtain near-optimal results when aligning networks with themselves., Christian Blum and Guillem Rodríguez Corominas were funded by project CI-SUSTAIN of the Spanish Ministry of Science and Innovation (PID2019-104156GB-I00). Maria J. Blesa acknowledges support from AEI under grant PID-2020-112581GB-C21 (MOTION) and the Catalan Agency for Management of University and Research Grants (AGAUR) under grant 2017-SGR-786 (ALBCOM).

The Network Alignment problem is a hard Combinatorial Optimization problem with a wide range of applications, especially in computational biology. Given two (or more) networks, the goal is to find a mapping between their respective nodes that preserves the topological and functional structure of the networks. In this work we extend a novel ant colony optimization approach for network alignment by adding a recently proposed Negative Learning mechanism. In particular, information for Negative Learning is obtained by solving sub-instances of the tackled problem instances at each iteration by means of an Integer Linear Programming solver. The results show that the proposed algorithm not only outperforms the standard ant colony optimization approach but also current state-of-the-art methods from the literature.

The time between an accident happening and an ambulance reaching the accident place is a very delicate and crucial time. The time elapsed between those two events could be the determining factor of whether the injured person gets to live or die. Therefore, that response time of the ambulance assisting in the accident should be as small as possible. The latter reduces a person’s recovery time and makes the difference between the patients having a temporary or long-term disability. The Sistema d’Emergències Mèdiques (SEM) and the Universitat Politècnica de Catalunya (UPC) are working in close collaboration to help SEM come up with a good and efficient system to always locate and well manage their ambulances. This will help SEM in always assigning the ambulance that arrives sooner to a given accident, thus reducing the risks associated with a long response time (such as long-term disabilities, or death). In the Regió Sanitària of Terres de L’Ebre in Catalonia, there are four ambulances and four bases. Currently, each ambulance occupies one base. In this master thesis, we explore the possibilities of stationing the ambulances following a different configuration (e.g., all the ambulance in one base and zero ambulances in the remaining bases, etc.) and check the average response time for each of those configurations in comparison to the current one. The aim of this study is to pick the configuration with the smallest average response time and thus, help with the overall goal of this collaboration between SEM and UPC.

Metaheuristic algorithms are employed to solve complex and large-scale optimization problems in many different fields, from transportation and smart cities to finance. This paper discusses how metaheuristic algorithms are being applied to solve different optimization problems in the area of bioinformatics. While the text provides references to many optimization problems in the area, it focuses on those that have attracted more interest from the optimization community. Among the problems analyzed, the paper discusses in more detail the molecular docking problem, the protein structure prediction, phylogenetic inference, and different string problems. In addition, references to other relevant optimization problems are also given, including those related to medical imaging or gene selection for classification. From the previous analysis, the paper generates insights on research opportunities for the Operations Research and Computer Science communities in the field of bioinformatics.

L’objecte del present treball consisteix en l’estudi i implementació de programari per a la resolució de problemes d’encaminament de vehicles i altres activitats logístiques. El problema d’encaminament de vehicles VRP Vehicle Routing Problem és un problema d’optimització combinatòria que va néixer al 1959. Existeixen diferents problemes d’encaminament de vehicles els quals donen resposta a les diferents casuístiques que es puguin donar com poden ser problemes amb límit de capacitat, amb múltiples dipòsits, amb limitació per finestres de temps, amb recollida i entrega, amb entregues i devolucions, estocàstics, amb partició i entrega, amb entregues periòdiques o amb una flota mixta. Per altra banda i en aquesta mateixa línia, existeixen diferents mètodes de resolució d’aquests problemes depenent de la volumetria i la necessitat de l’exactitud de la solució. Aquests a grosso modo es divideixen entre els mètodes exactes, les heurístiques, les meta-heurístiques i els algoritmes híbrids. Aquestes conjunt de mesures serveixen per respondre a la pregunta de quin és el conjunt òptim de rutes per una flota de vehicles que ha de satisfer les demandes d’un conjunt donat de clients amb el mínim cost possible. Aquesta estudi es pretén aplicat a l’empresa ILENCAT. Aquesta és una empresa que es dedica a la fabricació de lents oftàlmiques. Disposa del servei de transport subcontractat amb diferents empreses logístiques. Així doncs, el que es pretén és efectuar una anàlisi comparativa entre el cost actual del servei de transport extern de l’empresa i el cost si aquest servei es realitzés de manera interna, limitat a la província de Barcelona. Aquest objectiu neix arran de que es vol ser pionera en servir comandes de caràcter urgent (lliurament abans de les 11 hores del matí). S’escollirà tant el model del problema com el mètode de resolució. Aquest estudi s’ha realitzat amb la modelització del model matemàtic més adient a les característiques del problema mitjançant el llenguatge Python, la llibreria docplex del programari CPLEX de IBM mitjançant l’entorn de desenvolupament integrat Visual Studio Code (Microsoft). Com a conclusió es pot veure que surt a compte realitzar de manera interna el servei de transport de les mercaderies de l’empresa ILENCAT tant de caràcter econòmic com de caràcter pioner

L'optimització amb colònies de formigues (ACO) és una metaheurística que s'inspira en la naturalesa. ACO explota la capacitat que tenen les formigues per a trobar rutes curtes, entre el formiguer i la font d'aliments, utilitzant dos mecanismes: la construcció de solucions i l'actualització de feromones. Igual que les formigues trien la ruta en funció de la concentració de feromones, l'algorisme ACO fa servir valors de feromones, a més d'informació greedy, per a construir diverses solucions en cada iteració. Posteriorment, l'algorisme fa servir algunes de les millors solucions construïdes per a actualitzar el seu model de feromones com una manera d'emular la dinàmica dels rastres de feromones de les formigues durant la cerca d'aliments. Aquest model de feromones condueix la cerca cap a àrees pròximes a la solució utilitzada per a l'actualització. Per tant, podem dir que aquest algorisme d'optimització utilitza un mecanisme d'\emph{aprenentatge positiu}, com ho fan la majoria de metaheurísticas. Se sap per experiència que l'aprenentatge negatiu, juntament amb el mecanisme d'aprenentatge positiu, juga un paper vital en el comportament dels eixams d'animals i en l'evolució dins de les espècies i entre espècies, així com en la història humana. Diversos treballs han intentat millorar els algorismes ACO existents integrant mecanismes d'aprenentatge negatiu. No obstant això, la majoria d'aquestes implementacions no han produït cap millora significativa sobre l'algorisme ACO estàndard. La nostra proposta d'aprenentatge negatiu per a ACO empra diverses característiques no contemplades en implementacions anteriors. El nostre aprenentatge negatiu ACO identifica solucions dolentes (o components d'una solució dolenta) comparant les solucions generades en una iteració ACO amb la solució generada per un component algorítmic addicional. Qualsevol component d'una solució que es trobi en una iteració de ACO però que no sigui present en la solució generada pel component algorítmic addicional es considera un component de solució de baixa qualitat i el seu valor de feromona negatiu s'incrementa. Per tant, és menys probable que aquest component se seleccioni en les iteracions successives. Una altra característica nova és que l'algorisme baseline ACO genera una subinstància que consta dels components comuns trobats en totes les iteracions. Posteriorment, l'algorisme de base passa aquesta subinstància al component algorítmic addicional. Per tant, el component algorítmic considera una instància més petita formada per components que, presumiblement, són d'alta qualitat. En aquesta tesi, utilitzem amb èxit diversos algorismes d'optimització com a opcions per al component algorítmic addicional en les nostres implementacions ACO amb aprenentatge negatiu i resolem diversos problemes d'optimització (el problema de la motxilla multidimensional, el problema del conjunt dominant mínim, el problema de la màxima satisfactibilitat, el problema del conjunt dominant mínim amb capacitats i el problema del conjunt dominant mínim amb influència positiva). Els resultats experimentals mostren que les nostres variants ACO amb aprenentatge negatiu són millors que l'algorisme ACO de base i els altres algorismes d'optimització utilitzats internament en les nostres variants ACO amb aprenentatge negatiu. Clarament, aquesta és una fita que cap altra implementació d'aprenentatge negatiu ACO ha assolit anteriorment. D'altra banda, comparem les nostres variants amb quatre propostes ACO amb aprenentatge negatiu, representatives de la literatura, per al problema de la motxilla multidimensional i el problema del conjunt dominant mínim. La comparació mostra que, globalment, les nostres variants ACO amb aprenentatge negatiu funcionen significativament millor que aquests competidors. A més, trobem que ACOnegplus---la nostra millor variant ACO amb aprenentatge negatiu en general---sempre és competitiva amb els millors algorismes per a cadascun dels problemes d'optimització considerats. De fet, ACOnegplus és actualment l'algorisme més competitiu per al problema del conjunt dominant mínim amb influència positiva. D'aquesta manera, hem demostrat l'aplicabilitat general i l'efectivitat de la nostra proposta ACO amb aprenentatge negatiu. La Optimización con colonias de hormigas (ACO) es una metaheurística inspirada en la naturaleza. ACO explota la capacidad que tienen las hormigas para encontrar rutas cortas, entre el hormiguero y la fuente de alimentos, utilizando dos mecanismos: la construcción de soluciones y la actualización de feromonas. Al igual que las hormigas eligen la ruta en función de la concentración de feromonas, el algoritmo ACO utiliza valores de feromonas, además de información greedy, para construir varias soluciones en cada iteración. Posteriormente, el algoritmo usa algunas de las mejores soluciones construidas para actualizar su modelo de feromonas como una forma de emular la dinámica de los rastros de feromonas de las hormigas durante la búsqueda de alimentos. Este modelo de feromonas conduce la búsqueda hacia áreas cercanas a la solución utilizada para la actualización. Por lo tanto, podemos decir que este algoritmo de optimización utiliza un mecanismo de aprendizaje positivo, como lo hacen la mayoría de metaheurísticas. Se sabe que el aprendizaje negativo, junto con el mecanismo de aprendizaje positivo, juega un papel vital en el comportamiento de los enjambres de animales y en la evolución dentro de las especies y entre especies, así como en la historia humana. Varios trabajos han intentado mejorar los algoritmos ACO existentes integrando mecanismos de aprendizaje negativo. Sin embargo, la mayoría de estas implementaciones no han producido ninguna mejora significativa sobre el algoritmo ACO estándar. Nuestra propuesta de aprendizaje negativo para ACO emplea varias características no contempladas en implementaciones anteriores. Nuestro aprendizaje negativo ACO identifica soluciones malas (o componentes de una solución mala) comparando las soluciones generadas en una iteración ACO con la solución generada por un componente algorítmico adicional. Cualquier componente de una solución que se encuentre en una iteración de ACO pero que no esté presente en la solución generada por el componente algorítmico adicional se considera un componente de solución de baja calidad y su valor de feromona negativo se incrementa. Por tanto, es menos probable que este componente se seleccione en las iteraciones sucesivas. Otra característica novedosa es que el algoritmo baseline ACO genera una subinstancia que consta de los componentes comunes encontrados en todas las iteraciones. Posteriormente, el algoritmo de base pasa esta subinstancia al componente algorítmico adicional. Por lo tanto, el componente algorítmico considera una instancia más pequeña formada por componentes que, presumiblemente, son de alta calidad. En esta tesis, utilizamos con éxito varios algoritmos de optimización como opciones para el componente algorítmico adicional en nuestras implementaciones ACO con aprendizaje negativo y resolvemos varios problemas de optimización (problema de la mochila multidimensional, problema del conjunto dominante mínimo, problema de la máxima satisfactibilidad, problema del conjunto dominante mínimo con capacidades, problema del conjunto dominante mínimo con influencia positiva). Los resultados experimentales muestran que nuestras variantes ACO con aprendizaje negativo son mejores que el algoritmo ACO de base y los otros algoritmos de optimización utilizados internamente en nuestras variantes algorítmicas. Claramente, este es un logro que ninguna otra implementación de aprendizaje negativo ACO ha obtenido anteriormente. Por otro lado, comparamos nuestras variantes con cuatro propuestas ACO con aprendizaje negativo, representativas de la literatura, para el problema de la mochila multidimensional y el problema del conjunto dominante mínimo. La comparación muestra que, globalmente, nuestras variantes ACO con aprendizaje negativo funcionan significativamente mejor que estos competidores. Además, encontramos que ACOnegplus---nuestra mejor variante algorítmica---siempre es competitiva con los mejores algoritmos para cada uno de los problemas considerados. De hecho, ACOnegplus es actualmente el algoritmo más competitivo para el problema del conjunto dominante mínimo con influencia positiva. De esta manera, hemos demostrado la aplicabilidad general y la efectividad de nuestra propuesta algorítmica. Ant Colony Optimization (ACO) is a metaheuristic that took its inspiration from nature. This algorithm imitates the ants' capability in finding short routes between their nest and food sources by using two mechanisms: solution construction and pheromone update. Similar to the real ants that choose their route based on its pheromone concentration, the ACO algorithm makes use of pheromone values, in addition to greedy information, to construct several solutions at each iteration. Subsequently, the algorithm uses some of the good ones of the constructed solutions to update its pheromone model as a way to emulate the dynamics of the pheromone trails during the ants' foraging activities. This pheromone model will bias the search towards areas in the proximity of the solutions used for updating. Hence, we can say that this optimization algorithm uses a positive learning mechanism, as most metaheuristics do. Observations showed that negative learning, in addition to the positive learning mechanism, also plays a vital role in animal swarm behavior, the species and inter-species evolution, as well as the human history. Several works tried to improve existing ACO algorithms by integrating negative learning mechanisms. However, most of these implementations did not produce any consistent improvement over the standard ACO algorithm. Our negative learning ACO proposal employs several features not considered in previous implementations. Unlike the previous approaches that identify the negative learning information by a function that searches for worse solutions or simply by choosing the worst solution in an iteration for updating the pheromone values, our negative learning ACO identifies bad solutions (or bad solution components) by comparing the solutions produced in an ACO iteration to the solution generated by an additional algorithmic component. Any solution component found in an ACO iteration but not present in the solution generated by the additional algorithmic component is considered a bad solution component. As a consequence, its negative pheromone value is increased. Consequently, this component will be less likely to be selected in the next iterations. We developed another novel feature to support this negative information identification mechanism. The baseline ACO algorithm generates a sub-instance that consists of solution components found in each of its iterations. Subsequently, the baseline algorithm feeds the sub-instance to the additional algorithmic component. Hence, the algorithmic component works on a problem instance that is smaller in size and consists of presumably high-quality solution components. We successfully used several optimization algorithms (CPLEX, MAX-MIN Ant System, and the MaxSAT solvers SATlike and SlsMcs) as options for the additional algorithmic component in our negative learning ACO applications to several optimization problems (Multi Dimensional Knapsack Problem, Minimum Dominating Set problem, Maximum Satisfiability problem, Capacitated Minimum Dominating Set problem, and Minimum Positive Influence Dominating Set problem). The results show that our negative learning ACO variants improve consistently over the baseline ACO algorithm and over the other optimization algorithms used internally in our negative learning ACO variants. Clearly, this is an achievement that no other negative learning ACO proposal obtained in their implementations. We also compared them to four representative negative learning ACO proposals from the literature in our application to the Multi Dimensional Knapsack Problem and Minimum Dominating Set problem. The comparison shows that, globally, our negative learning ACO variants perform significantly better than these competitors. Moreover, we found that ACOnegplus---our overall-best negative learning ACO variant---always performs competitively with the state-of-the-art algorithms in each considered optimization problem. In fact, ACOnegplus is currently the state-of-the-art algorithm for the Minimum Positive Influence Dominating Set problem. This way, we proved the general applicability and the effectiveness of our negative learning ACO proposal.

Many rail terminals have loading areas that are properly equipped to move containers between trains. With the growing throughput of these terminals all the trains involved in a sequence of such movements may not ¿t in the loading area simultaneously, and storage areas are needed to place containers waiting for their destination train, although this storage increases the cost of the transshipment. This increases the complexity of the planning decisions concerning these activities, since now trains need to be packed in groups that ¿t in the loading area, in such a way that the number of containers moved to the storage area is minimized. Additionally, each train is only allowed to enter the loading area once. Similarly to previous authors, we model this situation as an acyclic graph partitioning problem for which we present a new formulation, and several valid inequalities based on its theoretical properties. Our computational experiments show that the new formulation outperforms the previously existing ones, providing results that improve even on the best exact algorithm designed so far for this problem.

Purpose: This paper aims to propose a new model called the stochastic green capacitated p-median problem with a simulation-based optimisation approach. An integer linear programming mathematical model is built considering the total emission produced by vehicles and the uncertain parameters including the travel cost for a vehicle to travel from a particular facility to a customer and the amount of CO2 emissions produced. We also develop a simulation-based optimisation algorithm for solving the problem.Design/methodology/approach: The authors proposed new algorithms to solve the problem. The proposed algorithm is a hybridisation of Monte Carlo simulation and a Variable Neighbourhood Search matheuristic. The proposed model and method are evaluated using instances that are available in the literature.Findings: Based on the results produced by the computational experiments, the developed approach can obtain interesting results. The obtained results display that the proposed method can solve the problems within a short computational time and the solutions produced have good quality (small deviations).Originality/value: To the best of our knowledge, there is no paper in the previous literature investigating the simulation-based optimisation for the stochastic green capacitated p-median problem. There are two main contributions in this paper. First, to build a new model for the capacitated p-median problem taking into account the environmental impact. Second, to design a simulation-based optimisation approach to solve the stochastic green capacitated p-median problem incorporating VNS-based matheuristic and Monte Carlo simulation.

The Network Alignment problem is an NP-complete Combinatorial Optimization problem in graphs. The goal is to find an alignment between the input networks, i.e., a mapping between their respective nodes, such that the topological and functional structure is well preserved. During the last decades, many methods have been proposed for solving the problem. However, many of them are designed only for specific areas and applications. In this thesis, we propose AntNetAlign, a new Ant Colony Optimization Algorithm for solving the Network Alignment problem with an integrative view. The key novelties of this approach are the following. First, it can incorporate any pairwise node similarity information to guide the construction process. This similarity is not restricted to any specific kind, allowing for high versatility while applying our method in different contexts. Second, it combines this similarity metric with an improvement measure that depends on the current state of the construction, thus providing both a global and local view of the undergoing construction process. Third, it is able to optimize any of the three considered topological quality measures. And fourth, it is complemented with three different selection strategies. The experimental results obtained over a real-world set of Protein-Protein Interaction networks show that out algorithm is able to outperform other state-of-the-art algorithms from the literature in two out of three of the tested scores. More specifically, our method obtains significantly better results in the superior S3 score in a reasonable amount of time. Moreover, AntNetAlign obtains nearly-optimal solutions when aligning networks with themselves. Additional experimental results show that the good performance of our algorithm may be justified by its high resistance to noise.

This paper discusses the use of probabilistic or randomized algorithms for solving combinatorial optimization problems. Our approach employs non-uniform probability distributions to add a biased random behavior to classical heuristics so a large set of alternative good solutions can be quickly obtained in a natural way and without complex conguration processes. This procedure is especially useful in problems where properties such as non-smoothness or non-convexity lead to a highly irregular solution space, for which the traditional optimization methods, both of exact and approximate nature, may fail to reach their full potential. The results obtained are promising enough to suggest that randomizing classical heuristics is a powerful method that can be successfully applied in a variety of cases

This chapter describes the fundamental characteristics of Complementary Metal-Oxide-Semiconductor (CMOS) technology, and how it can be assessed for system reliability studies. After some definitions, the dominating manufacturing technologies are described together with its advantages and disadvantages. Then, the core memory circuits present in today's computing systems are presented. Finally, the chapter provides an evaluation of these memory circuits when considering reliability across technology nodes.

Finding the longest common subsequence of a given set of input strings is a relevant problem arising in various practical settings. One of these problems is the so-called longest arc-preserving common subsequence problem. This NP-hard combinatorial optimization problem was introduced for the comparison of arc-annotated ribonucleic acid (RNA) sequences. In this work we present an integer linear programming (ILP) formulation of the problem. As even in the context of rather small problem instances the application of a general purpose ILP solver is not viable due to the size of the model, we study alternative ways based on model reduction in order to take profit from this ILP model. First, we present a heuristic way for reducing the model, with the subsequent application of an ILP solver. Second, we propose the application of an iterative hybrid algorithm that makes use of an ILP solver for generating high quality solutions at each iteration. Experimental results concerning artificial and real problem instances show that the proposed techniques outperform an available technique from the literature., This work was partially funded by project SGR 2014-1034 ( AGAUR, Generalitat de Catalunya ). Our experiments have been executed in the High Performance Computing environment managed by the rd lab at the Technical University of Barcelona ( http://rdlab.cs.upc.edu ) and we would like to thank them for their support.

This chapter describes the fundamental characteristics of Complementary Metal-Oxide-Semiconductor (CMOS) technology, and how it can be assessed for system reliability studies. After some definitions, the dominating manufacturing technologies are described together with its advantages and disadvantages. Then, the core memory circuits present in today's computing systems are presented. Finally, the chapter provides an evaluation of these memory circuits when considering reliability across technology nodes.

This paper addresses an assembly line balancing problem in which the length of the workpieces is larger than the width of the workstations. The problem differs from traditional variants of assembly line balancing in the sense that only a portion of the workpiece, or portions of two consecutive workpieces, can be reached from any workstation. Consequently, at any stationary stage of the cycle, each workstation can only process a portion of the tasks, namely, those which are inside the area of a workpiece that is reachable from the workstation. The objective is to find a (cyclic) movement scheme of the workpieces along the line and a task assignment to stationary stages of the production process, while minimizing the cycle time. We propose three hybrid approaches of metaheuristics and mathematical programming - one based on simulated annealing and the other two based on tabu search, relying on different neighborhood definitions. The two former approaches make use of a classical neighborhood, obtained by applying local changes to a current solution. The latter approach, in contrast, draws ideas from the corridor method to define a corridor around the current solution, via the imposition of exogenous constraints on the solution space of the problem. An extensive computational experiment is carried out to test the performance of the proposed approaches, improving the best results published to date.

El problema de la dominació independent ponderada és un problema NP-hard d'optimització combinatòria en grafs. Aquest problema només ha estat abordat a la literatura per enfocaments de programació lineal entera, heurístiques voraces i diferents versions d'algoritmes voraços iteratius basats en poblacions. En aquest projecte, primer apliquem una millora sobre les heurístiques voraces existents. Això ho fem implementant les versions rollout d'aquestes heurístiques i provant-les en un marc multistart on són aplicades de forma probabilística. En segon lloc, implementem tres versions d'un algorisme genètic esbiaixat de clau aleatòria. La diferència entre aquestes versions es troba en la forma en què els individus són descodificats en solucions viables del problema. Els resultats mostren que els algorismes desenvolupats poden competir amb els que són estat de l'art en el conjunt d'instàncies relativament petites. No obstant això, amb una mida creixent de les instàncies del problema, els nostres algorismes no poden arribar al nivell dels resultats obtinguts per l'algorisme més punter. Tot i això, els nostres algorismes poden ser millorats de moltes formes diferents, les quals expliquem en detall. Per tant, creiem que els nostres algorismes haurien de ser més estudiats en treballs futurs. The weighted independent domination problem is an NP-hard combinatorial optimization problem in graphs. This problem has only been tackled in the literature by integer linear programming approaches, by Greedy heuristics, and by different versions of a population-based iterated greedy algorithm. In this project, we first improve over the existing Greedy heuristics. This is done by implementing the rollout versions of these heuristics, and by testing them in a multistart framework in which they are applied in a probabilistic way. Second, we implement three versions of a biased random key genetic algorithm. The difference between these versions is found in the way in which individuals are decoded into feasible solutions to the problem. Moreover, we study the rollout versions of the corresponding decoders. Our results show that the developed algorithms can compete with the state of the art in the group of rather small-scale problem instances. However, with a growing size of the problem instances, our algorithms can not quite match the results of the current state-of-the-art algorithm. Nevertheless, our algorithms can potentially be improved in several different ways, which we explain in detail. Therefore, we believe that our algorithms should be further studied in future work.

The scheduling process on every production line is of principal importance as it directly affects the productivity of a company. For decades now, operational research has offered managers tools to automate their scheduling process and cope with the increase on product demand and variability. However, generally small and medium size companies do not have access to such solutions, widely incorporated on the workflow of more industrialized operations and other large companies. On this thesis, an automatic task scheduling service is developed, by implementing a GRASP algorithm with first descent local search to solve a combinatorial optimization problem known as the Job Shop Problem (JSP), along with one of its variants for considering job priorities and due dates based on total weighted tardiness (JSPTWT). This work reviews their mathematical formulation and several solution approaches and also performs a series of computational experiments to determined best set of parameters for the solver. Finally, a user interface powered by Shiny package in R is presented to offer the end users a friendly platform to support their scheduling processes, and a preliminary economic model for the first year of operation for this service is introduced.

Random peptide libraries that cover large search spaces are often used for the discovery of new binders, even when the target is unknown. To ensure an accurate population representation, there is a tendency to use large libraries. However, parameters such as the synthesis scale, the number of library members, the sequence deconvolution and peptide structure elucidation, are challenging when increasing the library size. To tackle these challenges, we propose an algorithm-supported approach to peptide library design based on molecular mass and amino acid diversity. The aim is to simplify the tedious permutation identification in complex mixtures, when mass spectrometry is used, by avoiding mass redundancy. For this purpose, we applied multi (two- and three-)-objective genetic algorithms to discriminate between library members based on defined parameters. The optimizations led to diverse random libraries by maximizing the number of amino acid permutations and minimizing the mass and/or sequence overlapping. The algorithm-suggested designs offer to the user a choice of appropriate compromise solutions depending on the experimental needs. This implies that diversity rather than library size is the key element when designing peptide libraries for the discovery of potential novel biologically active peptides. Electronic supplementary material The online version of this article (10.1186/s13321-019-0347-6) contains supplementary material, which is available to authorized users.

L’optimització combinatòria és un tipus específic d’optimització matemàtica on el domini de les variables és discret. Aquest tipus de problemes d’optimització tenen una gran aplicabilitat degut a la seva capacitat d’optimització sobre objectes unitaris i no divisibles. Més enllà dels algoritmes genèrics, la comunitat investigadora és molt activa proposant algorismes capaços d’abordar problemes d’optimització combinatòria per a problemes específics. L’objectiu d’aquesta tesi és investigar com ampliar l’aplicabilitat d’algorismes d’optimització combinatoria que exploten l’estructura dels problemes a resoldre. Ho fem des de la perspectiva del maquinari d’una computadora, perseguint l’explotació total dels recursos computacionals que ofereix el maquinari actual. Per assolir generalitat treballem amb tres problemes diferents. Primer abordem el problema de generació d’estructures de la coalició (CSGP). Trobem que l’algorisme d’última generació és IDP. Proposem un algoritme optimitzat i paral·lel capaç de resoldre el CSGP. Aconseguim això definint un nou mètode per dur a terme l’operació més crítica -Splitting-, així com definint un nou mètode per dividir l’operació de l’algoritme en els diferent subprocessos. A continuació, estudiem el problema de determinació del guanyador (WDP) per a les subhastes combinades (CA). Trobem que l’escalabilitat dels solucionadors d’avantguarda és limitada. Més concretament, mostrem com millorar la resolució de resultats de relaxació LP per al WDP en subhastes combinables de gran escala mitjançant l’aplicació de l’algoritme AD³. A continuació, contribuïm amb una versió optimitzada d’AD³ que també es pot executar en un escenari paral·lel de memòria compartida. Finalment, estudiem l’aplicació de AD³ per resoldre les relaxacions LP d’un problema més exigent de la computacionalment: El problema de la predició de cadenes laterals (SCP). Presentem una manera optimitzada de resoldre l’operació més crítica, la resol·lució d’un problema quadràtic per a un factor arbitrari. En tots els casos proposem algoritmes optimitzats que es poden escalar de forma paral·lela i que milloren notablement l’estat de la tècnica. Tres ordres de magnitud a IDP, i un ordre de magnitud a AD³. L’objectiu final d’aquest treball és demostrar com un disseny algorisme conscient de maquinari pot conduir a millores de rendiment significatives. Mostrem estratègies exportables a algorismes d’optimització combinatòria similars. Aquestes estratègies ajudaran al dissenyador d’algorismes a assolir més eficiència en les CPU modernes. La optimización combinatoria es un tipo específico de optimización donde el dominio de las variables es discreto. Este tipo de problemas de optimización tienen una gran aplicabilidad debido a su capacidad de optimización sobre objetos unitarios y no divisibles. Más allá de los algoritmos genéricos, la comunidad investigadora es muy activa proponiendo algoritmos capaces de abordar problemas de optimización combinatoria para problemas específicos. El objetivo de esta tesis es investigar cómo ampliar la aplicabilidad de algoritmos de optimización combinatoria que explotan la estructura de los problemas a resolver. Lo hacemos desde la perspectiva del hardware de una computadora, persiguiendo la explotación total de los recursos computacionales que ofrece el hardware actual. Para alcanzar generalidad trabajamos con tres problemas diferentes. Primero abordamos el problema de generación de estructuras de la coalición (CSGP). Encontramos que el algoritmo de última generación es IDP. Proponemos un algoritmo optimizado y paralelo capaz de resolver el CSGP. Conseguimos esto deniendo un nuevo metodo para llevar a cabo la operacion mas crtica -Splitting-, así como deniendo un nuevo método para dividir la operación del algoritmo en los diferente subprocesos. A continuación, estudiamos el problema de determinación del ganador (WDP) para las subastas combinatorias (CA). Encontramos que la escalabilidad de los solucionadores de vanguardia es limitada. Más concretamente, mostramos cómo mejorar la resolución de resultados de relajación LP para el WDP en subastas combinatorias de gran escala mediante la aplicación del algoritmo AD³. A continuación, contribuimos con una versión optimizada de AD³ que también se puede ejecutar en un escenario paralelo de memoria compartida. Finalmente, estudiamos la aplicación de AD³ para resolver las relajaciones LP de un problema más exigente de la computacionalmente: El problema de la predición de cadenas laterales (SCP). Presentamos una manera optimizada de resolver la operación más crítica, la resolución de un problema cuadrático para un factor arbitrario. En todos los casos proponemos algoritmos optimizados que se pueden escalar de forma paralela y que mejoran notablemente el estado de la técnica. Tres órdenes de magnitud en IDP, y un orden de magnitud en AD³. El objetivo nal de este trabajo es demostrar como un diseño algoritmo consciente de hardware puede conducir a mejoras de rendimiento signicativas. Mostramos estrategias exportables a algoritmos de optimización combinatoria similares. Estas estrategias ayudarán al diseñador de algoritmos lograr más eficiencia en las CPU modernas. Combinatorial Optimization is a specific type of mathematical optimization where variables' domain is discrete. This kind of optimization problems have an enormous applicability due to its ability to optimize over unitary and non-divisible objects. Beyond generic algorithms, the research community is very active proposing algorithms able to tackle specific combinatorial optimization problems. The goal of this thesis is to investigate how to widen the applicability of Combinatorial Optimization algorithms that exploit the structure of the problems to solve. We do so from a computer's hardware perspective, pursuing the full exploitation of computational resources offered by today's hardware. For the sake of generality we work on three different problems. First we tackle the Coalition Structure Generation Problem (CSGP). We find that the state-of-the-art algorithm is IDP. We propose an optimized and parallel algorithm able to solve the CSGP. We reach this by defining a novel method to perform the most critical operation --Splitting-- as well as by defining a novel method to divide the the algorithm's operation in threads. Then, we study the Winner Determination Problem (WDP) for Combinatorial Auctions (CA), which is very related to the CSGP. We find that state-of-the-art solvers' scalability is limited. More specifically we show how to improve results solving LP relaxations for the WDP in Large Scale Combinatorial Auctions by applying the AD³ algorithm. Then we contribute with an optimized version of AD³ which is also able to run in a shared-memory parallel scenario. Finally we study the application of AD³ to solve the LP relaxations of a more CPU demanding problem: The Side-Chain Prediction (SCP). We present an optimized way to solve the most critical operation which is solving a Quadratic Problem for an Arbitrary Factor. In all the cases we propose optimized algorithms that are scalable in parallel and that improve significantly the state-of-the-art. Three orders of magnitude speedup on IDP, one order of magnitude speedup in AD³. The ultimate purpose of this work is to demonstrate how a hardware-aware algorithmic design can lead to significant speedups. We show strategies that are exportable to similar Combinatorial Optimization algorithms. Such strategies will help the algorithm designer to achieve more efficiency in modern CPUs.

Modern heuristics or metaheuristics are optimization algorithms that have been increasingly used during the last decades to support complex decision-making in a number of fields, such as logistics and transportation, telecommunication networks, bioinformatics, finance, and the like. The continuous increase in computing power, together with advancements in metaheuristics frameworks and parallelization strategies, are empowering these types of algorithms as one of the best alternatives to solve rich and real-life combinatorial optimization problems that arise in a number of financial and banking activities. This article reviews some of the works related to the use of metaheuristics in solving both classical and emergent problems in the finance arena. A non-exhaustive list of examples includes rich portfolio optimization, index tracking, enhanced indexation, credit risk, stock investments, financial project scheduling, option pricing, feature selection, bankruptcy and financial distress prediction, and credit risk assessment. This article also discusses some open opportunities for researchers in the field, and forecast the evolution of metaheuristics to include real-life uncertainty conditions into the optimization problems being considered. This work has been partially supported by the Spanish Ministry of Economy and Competitiveness (TRA2013-48180-C3-P, TRA2015-71883-REDT), FEDER, and the Universitat Jaume I mobility program (E-2015-36).

The technical contents of this work fall within the field of statistical disclosure control (SDC), which concerns the postprocessing of the demographic portion of the statistical results of surveys containing sensitive personal information, in order to effectively safeguard the anonymity of the participating respondents. The concrete purpose of this study is to improve the efficiency of a widely used algorithm for k-anonymous micro¬aggregation, known as maximum distance to average vector (MDAV), in order to vastly accelerate its execution without affecting its excellent functional performance with respect to competing methods. The improvements tested in this project are quite diverse, encompassing algebraic modifications, divide-and-conquer algorithmic improvements, and last but not least, parallel computation both on CPU and graphics processing units (GPUs). We focused more on parallelization because it is the most scalable and powerful tool we could use, comparing CPU and massive GPU parallelization. Nonetheless, the algebraic and algorithmic improvement in the code are conceived bearing in mind the optimization of the parallelization of the algorithm. We also propose a computational change involving a drastically reduced execution time, occasionally at the price of a slightly higher distortion. Los contenidos técnicos de este trabajo recaen en el campo de la revelación estadística, que se refiere al procesamiento posterior de la parte demográfica de los resultados estadísticos de encuestas que contienen información personal, a fin de salvaguardar eficazmente la anonimidad de los encuestados que participan . El objetivo concreto de este estudio es mejorar la eficiencia de un algoritmo utilizado para la microagregació k-anónimo, conocido con el nombre de maximum distance to average vector (MDAV), para acelerar enormemente su ejecución sin afectar su excelente rendimiento funcional respecto a la de otros métodos. Las mejoras puestas a prueba en este proyecto son muy diversas, modificaciones algebraicas, algoritmos de "divide and conquer", y por último pero no menos importante, la computación paralela tanto en las unidades de CPU y de procesamiento gráfico (GPU). Nos centramos más en la paralelización, ya que es la herramienta más escalable y de gran alcance que podríamos utilizar, comparando la paralelización en CPU y la paralelización masiva en GPU. No obstante, las mejoras algebraicas y algorítmica que se han utilizado han tenido en cuenta la optimización de la paralelización del algoritmo. También proponemos un cambio computacional que implica una gran mejora en el tiempo, pero causando un pequeño aumento de la distorsión ocasionalmente. Els continguts tecnics d'aquest treball recauen en el camp de la revelació estadistica, que es refereix al processament posterior de la part demografica dels restultats estadistics d'enquestes que contenen informació personal, a fi de salvaguardar eficaçment l'anonimitat dels enquestats que hi participen. L'objectiu concret d'aquest estudi és millorar l'eficiencia d'un algoritme utilitzat per a la microagregació k-anonim, conegut amb el nom de maximum distance to average vector (MDAV), per tal d'accelerar enormement la seva execució sense afectar la seva excel·lent rendiment funcional respecte a la d'altres mètodes. Les millores possades a prova en aquest projecte són molt diverses, modificacions algebraiques, algorismes de "divide and conquer", i per últim però no menys important, la computació paral·lela tant en les unitats de CPU i de processament gràfic (GPU). Ens centrem més en la paral·lelització, ja que és l'eina més escalable i de gran abast que podríem utilitzar, comparant la paral·lelitzacio en CPU i la paral·lelització massiva en GPU. No obstant, les millores algebraiques i algorítmica que s'han utilitzat han tingut en compte la optimització de la paral·lelització del algoritme. També proposem un canvi computacional que implica una gran millora en el temps, però causant un petit augment de la distorsio ocasionalment.

Conjoint analysis has become the most used technique for measuring preferences for new products to be launched in the market. Experimental design models are key elements for its use in market research. Such models involve a matrix in which attributes and levels are combined, making product concepts that respondents then evaluate. Experimental design has emerged as a key element in conjoint analysis’ success because its application generates statistical and reliability implications for part-worth factor estimations and for the type of heuristics followed by respondents. This paper proposes a conceptualization of both statistical and cognitive efficiency criteria for experimental designs. A review of the most used statistical optimization criteria is presented, as well as a methodology for optimizing cognitive efficiency. Finally, we suggest a dynamic algorithm for optimizing the objective function in a sequential manner.

[EN] Since its appearance in the 1990s, horizontal collaboration (HC) practices have revealed themselves as catalyzers for optimizing the distribution of goods in freight transport logistics. After introducing the main concepts related to HC, this paper offers a literature review on the topic and provides a classification of best practices in HC. Then, the paper analyses the main benefits and optimization challenges associated with the use of HC at the strategic, tactical, and operational levels. Emerging trends such as the concept of ` green' or environmentally- friendly HC in freight transport logistics are also introduced. Finally, the paper discusses the need of using hybrid optimization methods, such as simheuristics and learnheuristics, in solving some of the previously identified challenges in real- life scenarios dominated by uncertainty and dynamic conditions., This work has been partially supported by the Spanish Ministry of Economy and Competitiveness & FEDER (TRA2013-48180-C3-P, TRA2015-71883-REDT), The Erasmus+ program (2016-1-ES01-KA108-023465), the Ibero American Program of Science and Technology for Development (CYTED2014-515RT-0489), the CAN Foundation (CAN2014-3758, CAN2015-70473), and the Spanish Ministry of Education (FPU-14/00024).

Un gran nombre de processos de presa de decisions en sectors estratègics com el transport i la producció representen problemes NP-difícils. Sovint, aquests processos es caracteritzen per alts nivells d'incertesa i dinamisme. Les metaheurístiques són mètodes populars per a resoldre problemes d'optimització difícils en temps de càlcul raonables. No obstant això, sovint assumeixen que els inputs, les funcions objectiu, i les restriccions són deterministes i conegudes. Aquests constitueixen supòsits forts que obliguen a treballar amb problemes simplificats. Com a conseqüència, les solucions poden conduir a resultats pobres. Les simheurístiques integren la simulació a les metaheurístiques per resoldre problemes estocàstics d'una manera natural. Anàlogament, les learnheurístiques combinen l'estadística amb les metaheurístiques per fer front a problemes en entorns dinàmics, en què els inputs poden dependre de l'estructura de la solució. En aquest context, les principals contribucions d'aquesta tesi són: el disseny de les learnheurístiques, una classificació dels treballs que combinen l'estadística / l'aprenentatge automàtic i les metaheurístiques, i diverses aplicacions en transport, producció, finances i computació. Un gran número de procesos de toma de decisiones en sectores estratégicos como el transporte y la producción representan problemas NP-difíciles. Frecuentemente, estos problemas se caracterizan por altos niveles de incertidumbre y dinamismo. Las metaheurísticas son métodos populares para resolver problemas difíciles de optimización de manera rápida. Sin embargo, suelen asumir que los inputs, las funciones objetivo y las restricciones son deterministas y se conocen de antemano. Estas fuertes suposiciones conducen a trabajar con problemas simplificados. Como consecuencia, las soluciones obtenidas pueden tener un pobre rendimiento. Las simheurísticas integran simulación en metaheurísticas para resolver problemas estocásticos de una manera natural. De manera similar, las learnheurísticas combinan aprendizaje estadístico y metaheurísticas para abordar problemas en entornos dinámicos, donde los inputs pueden depender de la estructura de la solución. En este contexto, las principales aportaciones de esta tesis son: el diseño de las learnheurísticas, una clasificación de trabajos que combinan estadística / aprendizaje automático y metaheurísticas, y varias aplicaciones en transporte, producción, finanzas y computación. A large number of decision-making processes in strategic sectors such as transport and production involve NP-hard problems, which are frequently characterized by high levels of uncertainty and dynamism. Metaheuristics have become the predominant method for solving challenging optimization problems in reasonable computing times. However, they frequently assume that inputs, objective functions and constraints are deterministic and known in advance. These strong assumptions lead to work on oversimplified problems, and the solutions may demonstrate poor performance when implemented. Simheuristics, in turn, integrate simulation into metaheuristics as a way to naturally solve stochastic problems, and, in a similar fashion, learnheuristics combine statistical learning and metaheuristics to tackle problems in dynamic environments, where inputs may depend on the structure of the solution. The main contributions of this thesis include (i) a design for learnheuristics; (ii) a classification of works that hybridize statistical and machine learning and metaheuristics; and (iii) several applications for the fields of transport, production, finance and computing.

Daily fantasy Sports are popular betting online multiplayer contests consisting in the confection of a virtual lineup of elite athletes observing specific restrictions. The scores are computed from the performance of the athletes in their respective matches. In this project two machine learning methods, linear regression and neural networks, are evaluated through the construction of the necessary models to predict expectations, variances and covariances of these scores. It is concluded that the method of choice depends on the available data and the parameter to predict. The existing betting strategies for the selection of an optimal set of athletes, consisting on the maximization with restrictions of a linear function, are also reviewed. One strategy is proposed consisting in the maximization with restrictions of a quadratic function in order to address certain caveats of these approaches. A practical and theoretical comparison between two methods, a genetic algorithm and an integer programming algorithm, is also performed as means to solve the combinatorial optimization problem posed by these maximizations. It is concluded that integer programming is the most efficient approach. Finally, a simulation on the performance of the strategies is run, hinting at the superiority of the proposed one. Los Daily Fantasy Sports son competiciones multijugador de apuestas en línea muy populares que consisten en hacer una selección virtual de deportistas de élite respetando unas normas específicas. Las puntuaciones obtenidas se computan a partir de la actuación de los deportistas en sus respectivos partidos. En este proyecto se evalúa teóricamente i prácticamente dos métodos de aprendizaje máquina supervisado, regresión lineal y redes neuronales, para construir, a partir de datos históricos, los modelos necesarios para anticipar esperanzas, varianzas i covarianzas de estas puntuaciones. Se concluye que el método preferido depende de los datos disponibles y de la característica a predecir. Se revisan también las estrategias de apuesta existentes que consisten en la maximización con restricciones de una función lineal para elegir un conjunto de deportistas óptimo. Se propone una estrategia consistente en la maximización de una función cuadrática con restricciones para solucionar algunos de sus inconvenientes. Se realiza igualmente una comparativa teórica y práctica de dos métodos, un algoritmo genético y un algoritmo de programación de enteros, para resolver el problema de optimización combinacional que representan estas maximizaciones. Se concluye que la programación de enteros es el método más eficiente. Finalmente se realiza una simulación de las diversas estrategias que apunta a la superioridad de la propuesta. Els Daily Fantasy Sports són competicions multijugador d'apostes en línia molt populars que consisteixen en fer una selecció virtual d'esportistes d'èlit respectant unes normes específiques. Les puntuacions obtingudes es computen a partir de l'actuació dels esportistes en els seus respectius partits. En aquest projecte s'avaluen teòricament i pràctica dos mètodes d'aprenentatge màquina supervisat, regressió lineal i xarxes neuronals, per construir, a partir de dades històriques, els models necessaris per anticipar esperances, variàncies i covariàncies d'aquestes puntuacions. Es conclou que el mètode preferit depèn de les dades disponibles i la característica a predir. Es revisen també les estratègies d'aposta existents que consisteixen en la maximització amb restriccions d'una funció lineal per tal d'escollir un conjunt d'esportistes òptim. Es proposa una estratègia consistent en la maximització d'una funció quadràtica amb restriccions per solucionar-ne certs inconvenients. Es realitza igualment una comparativa teòrica i pràctica de dos mètodes, un algoritme genètic i un algoritme de programació d'enters, per resoldre el problema d'optimització combinacional que representen aquestes maximitzacions. Es conclou que la programació d'enters és el mètode més eficient. Finalment es realitza una simulació de les diverses estratègies que apunta a la superioritat pràctica de la proposada.

In many situations, the resources in organizations are employed to satisfy some demand (or services) requirements, which are repeated with some periodicity. These recurrent services appear in a large variety of processes such as manufacturing, logistics and several other types of services. In this thesis, we focus on a particular family of problems involving the planning of recurrent services. In these problems resources are assigned to offer recurrent services over a planning horizon. Even if these problems can be classified as scheduling problems, this specific characteristic makes them differ from the typical scheduling problems studied in the literature. A very special characteristic of the problems that we study is that services are considered as single-period tasks. That is, the time needed to start and complete a service never exceeds one time period of the planning horizon. Furthermore, we focus on identifying the single periods when each service is repeated within the time horizon, instead of on the sequence according to which the different services are executed along the time horizon. We concentrate on modelling aspects for recurrent service problems with single-period duration,and on solution techniques for efficiently finding solutions. Particular emphasis is placed on the study of the strategy that is followed to offer the services over the planning horizon, that is, the policy for scheduling. Our aim is to analyze different options for such scheduling policies.The purpose is to provide enough support to decision makers to determine the convenience of using (or not) flexible policies as an alternative to regular strategies.For this, we study alternative models for two different scheduling policies. These models are addressed from a mathematical programming point of view and, therefore, we present several Mixed Integer Linear Programming (MILP) formulations. We develop two different types of formulations: the first type can be seen as a natural initial approach to the problem and produces sparse coefficients matrices whereas the second type is focused on determining the very first service period for each customer and gives dense matrices. For each type of formulation, we present two versions: an extensive and a compact one. In the first one decision variables are associated with individual demand customers whereas in the second one decision variables are associated with classes of customers with similar characteristics. For the regular policy we develop the both types of formulations whereas for the flexible policy we only study the extensive formulation. The formulations for each policy are compared trough extensive computational experience. Since the flexible policy results harder to solve than the regular one, we make use of combinatorial optimization techniques that permit alternative solution methods.In particular, we propose two different formulations suitable for column generation (CG).For each formulation we study the pricing subproblem that allows generating new columns, the initialization phase, as well as a procedure to tackle infeasibility issues. Additionally, we apply stabilization procedures in order to avoid the generation of an excessive of columns. Each CG algorithm is embedded within a branch-and-price (BP) framework, which combines different branching strategies. The BP was implemented for each CG formulation producing very interesting results that we present and analyze. Heuristics are alternative combinatorial optimization techniques that provide optimal and near optimal values within small computational times. In this thesis we also propose a heuristic algorithm suitable for both of scheduling policies.The heuristic produces good quality solutions for the studied problems, specially for the flexible policy. Finally, the structure of the solutions obtained with both scheduling policies are analyzed giving important insights on the trade-off between the regular and the flexible policies., En muchas situaciones los recursos en las organizaciones se usan para satisfacer requerimientos de demanda (o servicios) los cuales se repiten con cierta periodicidad. Estos servicios recurrentes aparecen en una gran variedad de procesos de manufactura, logística y varios otros tipos de servicios. Esta tesis aborda una familia de problemas en donde los recursos deben ser asignados para ofrecer servicios recurrentes sobre un horizonte de planeación. Estos problemas tienen ciertas características que los hacen distintos a los problemas típicos de calendarización encontrados en la literatura. Una de ellas es que los servicios son tareas de periodo unitario. Esto es, el tiempo necesario para comenzar y terminar un servicio nunca excede de un periodo de tiempo del horizonte de planeación. Además, en este tipo de problemas no enfocamos en determinar los periodos en los que cada servicio será repetido, en lugar de la secuenciación en que los diferentes servicios son ejecutados. En particular, nos concentramos en aspectos de modelización para los problemas de servicios recurrentes con duración de periodo simple así como en técnicas de resolución para encontrar soluciones eficientes. Hacemos particular énfasis en el estudio de la estrategia a seguir para ofrecer los servicios, esto es, la política de calendarización. Nuestro propósito es el análisis de distintas opciones para tales políticas. El objetivo es proveer soporte suficiente para los tomadores de decisiones en cuanto a la conveniencia de usar (o no) políticas flexibles como alternativa a estrategias regulares. Para ello estudiamos modelos alternativos para dos diferentes políticas de calendarización. Estos modelos se estudian desde una perspectiva de programación matemática y, por tanto, se presentan varias formulaciones de programación lineal mixta entera. En esta tesis desarrollamos dos tipos de formulaciones: el primer tipo puede verse como un acercamiento natural al problema y produce matrices con coeficientes dispersos mientras que el segundo tipo se enfoca en determinar el primer periodo de servicio para cada cliente y da como resultado matrices densas. Para cada tipo de formulación presentamos dos versiones: una extensa y una compacta. En la primera, las variables de decisión están asociadas a clientes individuales mientras que en la segunda, las variables de decisión se asocian con clases de clientes con características similares. Para la política regular desarrollamos formulaciones de las dos versiones mientras que para la política flexible únicamente estudiamos formulaciones extensas. Las formulaciones para cada política son comparadas por medio de una amplia experiencia computacional. Debido a que la política flexible resulta más difícil de resolver que la regular, usamos técnicas de optimización combinatoria que permiten métodos alternativos de solución. En particular, proponemos dos formulaciones distintas, ambas adecuadas para generación de columnas (GC). Para cada formulación estudiamos el subproblema de pricing para generar nuevas columnas, la fase de inicialización así como un procedimiento para atacar temas de infactibilidad. Además, aplicamos procedimientos de estabilización con el objetivo de evitar la generación de un número excesivo de columnas. Cada algoritmo de GC ha sido incrustado dentro de una estructura de branch-and-price (BP), el cual combina diferentes estrategias de ramificación. El BP ha sido implementado para cada formulación de GC produciendo resultados interesantes los cuales presentamos y analizamos. En este trabajo también proponemos un algoritmo heurístico adaptable para ambas políticas de calendarización. Las heurísticas producen soluciones de buena calidad para los problemas estudiados, especialmente para la política flexible. Finalmente, la estructura de las soluciones obtenidas con ambas políticas se analizan, obteniendo ideas importantes en cuanto a la compensación entre las políticas regulares y las flexibles.