In July 2012, a paper by Gutfraind et al. introduced the neighbor-aided network installation problem, which asks for "a minimal cost ordering of the vertices of a graph, where the cost of visiting a node is a function of the number of neighbors that have already been visited." Additionally, in a 2018 paper by Cummings et al., two greedy heuristics were implemented to estimate solutions to the NANIP-Blackstart problem. This paper will evaluate the performance of the greedy heuristics introduced by Cummings et al., and compare their performance to a new heuristic. In addition to comparing heuristics, we will also look at varying the blackstart node and cost function. This analysis will be conducted by testing the heuristics on power networks from the SuiteSparse Matrix Collection and NIST Matrix Market. The goal of this body of work is to better understand the variables at play in the NANIP-Blackstart problem in order to work towards better estimated solutions.

We develop a class of models to represent the dynamics of a virus spreading in a cellphone network, employing a taxonomy that includes five key characteristics. Based on the resulting dynamics governing the spread, we present optimization models to rapidly detect the virus, subject to resource limitations. We consider two goals, maximizing the probability of detecting a virus by a time threshold and minimizing the expected time to detection, which can be applied to all spread models we consider. We establish a submodularity result for these two objective functions that ensures that a greedy heuristic yields a well-known constant-factor (63%) approximation. We relate the latter optimization problem, under a specific virus-spread mechanism from our class of models, to a classic facility-location model. Using data from a large carrier, we build several base cellphone contact networks of different scale. We then rescale these base networks using the so-called c-core decomposition that removes vertices of low degree in a recursive way. We further show that this down-sampling strategy preserves, in general, the topological properties of the base networks, based on testing several measures. For the objective that maximizes the probability that we detect a virus by a time threshold, we provide a sample-average optimization model that yields an asymptotically-optimal design for locating the detection devices, as the number of samples grows large. To choose a relevant time threshold, we perform a simulation for some spread models. We then test the performance of our proposed solution methods by solving the presented optimization models for some spread dynamics using some of the contact networks built after the c-core decomposition. The computational results show that the greedy algorithm is an efficient way to solve the corresponding sample-average approximation model, and the greedy solutions outperform some other simple solution approaches. / text

No description available.

A key challenge for manufacturing companies is to store parts in an efficient way atthe lowest cost possible. As the demand of differentiated products increases, togetherwith the fact that old products are not phased out at the same pace, the need of usingstorage space as dynamically as possible becomes vital.Scania’s engine assembly manufactures engines for various automotive vehicles andmarine & industry applications. The variation in engine range in Scania’s offeringleads to the need of holding a vast, and increasing, assortment of parts in the produc-tion. As a consequence, this puts more pressure on the logistics and furnishing withinthe engine assembly.This master thesis aims to facilitate the process of assigning parts’ storage locationsin the most profitable manner through an optimization model, the Location Model, inExcel VBA. Together with the model, suggestions of work methods are presented.By implementing the Location Model at Scania’s engine assembly, 4,98 % of all keptparts are recommended location changes, while resulting in cost savings, for the chosen30-day period. These location changes result in a cost saving of 6,73 % of the totallogistic costs for the same time period.

No description available.

Cette thèse se déroule au sein du projet ToDo (Time versus Optimality in discrete Optimization ANR 09-EMER-010) financé par l'Agence Nationale de la Recherche. Nous nous intéressons à la résolution exacte et approchée de deux problèmes de graphes. Dans un souci de compromis entre la durée d'exécution et la qualité des solutions, nous proposons une nouvelle approche par partition en cliques qui a pour but (1) de résoudre de manière rapide des problèmes exacts et (2) de garantir la qualité des résultats trouvés par des algorithmes d'approximation. Nous avons combiné notre approche avec des techniques de filtrage et une heuristique de liste. Afin de compléter ces travaux théoriques, nous avons implémenté et comparé nos algorithmes avec ceux existant dans la littérature. Dans un premier temps, nous avons traité le problème de l'indépendant dominant de taille minimum. Nous résolvons de manière exacte ce problème et démontrons qu'il existe des graphes particuliers dans lesquels le problème est 2-approximable. Dans un second temps nous résolvons par un algorithme exact et un algorithme d'approximation le problème du vertex cover et du vertex cover connexe. Puis à la fin de cette thèse, nous avons étendu nos travaux aux problèmes proches, dans des graphes comprenant des conflits entre les sommets. / This thesis takes place in the project ToDo 2 funded by the french National Research Agency. We deal with the resolution of two graph problems, by exact and approximation methods. For the sake of compromise between runtime and quality of the solutions, we propose a new approach by partitioning the vertices of the graph into cliques, which aims (1) to solve problems quickly with exact algortihms and (2) to ensure the quality if results with approximation algorithms. We combine our approach with filtering techniques and heuristic list. To complete this theoretical work, we implement our algorithms and compared with those existing in the literature. At the first step, we discuss the problem of independent dominating of minimum size. We solve this problem accurately and prove that there are special graphs where the problem is 2-approximable. In the second step, we solve by an exact algorithm and an approximation algorithm, the vertex cover problem and the connected vertex cover problem. Then at the end of this thesis, we extend our work to the problems in graphs including conflicts between vertices.

The aim of this thesis is to develop a tractable method for approximating the steady-state behavior of continuous-review base-stock controlled assembly systems with Poisson demand arrivals and manufacturing and assembly facilities modeled as Jackson networks. One class of systems studied is to produce a single type of finished product assembling a number of components and another class is to produce two types of finished products allowing component commonality. The performance measures evaluated are the expected backorders, fill rate and the stockout probability for finished product(s). A partially aggregated but exact model is approximated assuming that the state-dependent transition rates arising as a result of the partial aggregation are constant. This approximation leads to the derivation of a closed-form steady-state probability distribution, which is of product-form. Adequacy of the proposed model in approximating the steady-state performance measures is tested against simulation experiments over a large range of parameters and the approximation turns out to be quite accurate with absolute errors of 10% at most for fill rate and stockout probability, and of less than 1.37 (&amp / #8776 / 2) requests for expected backorders. A greedy heuristic which is proposed to be employed using approximate steady-state probabilities is devised to optimize base-stock levels while aiming at an overall service level for finished product(s).

This paper concerns a specific pursuit-evasion problem with a node-located evader which we call the monk problem. First, we propose a way of verifying a strategy using a new kind of recursive systems, called EL-systems. We show how an EL-system representing a graph-instance of the problem can be represented using matrices, and we give an example of how this can be used to efficiently implement a verifier. In the later parts we propose heuristics to construct a strategy, based on a greedy algorithm. Our main focus is to minimise the number of pursuers needed, called the search number. The heuristics rely on properties of minimal stable components. We show that the minimal stable components are equivalent to the strongly connected components of a graph, and prove that the search number is equal to the maximum search number of its strongly connected components. We also establish lower and upper bounds for the search number to narrow the search space. / Denna rapport avhandlar ett specifikt pursuit-evasion problem med en hörnplacerad flykting, som vi kallar för munkproblemet. Först föreslår vi ett sätt att verifiera en strategi med en ny typ av rekursivt system, kallat EL-system. Vi visar hur ett EL-system som representerar en grafinstans av munkproblemet kan representeras med matriser, och vi ger ett exempel på hur detta kan användas för att effektivt implementera en verifikator. I de senare delarna föreslår vi heuristiker för att konstruera en strategi, baserad på giriga algoritmer. Vårt huvudfokus är att minimera antalet förföljare som krävs för att dekontaminera grafen, det så kallade söktalet. Vår heuristik förlitar sig på egenskaper för minimala stabila komponenter. Vi visar att minimala stabila komponenter är ekvivalenta med de starka komponenterna i en graf, och härleder att söktalet är lika med det maximala söktalet för grafens starka komponenter. Vi etablerar också undre och övre gränser för söktalet i syfte att minska sökintervallet.

The elimination of distribution inefficiencies, occurring due to the timing of customers' orders is an important reason for companies to introduce vendor managed inventory programs. By managing their customers' inventories, suppliers may be able to reduce demand variability and therefore distribution costs. We develop technology to measure the effectiveness of distribution strategies. We develop a methodology that allows the computation of tight lower bounds on the total mileage required to satisfy customer demand over a period of time. As a result, companies will be able to gain insight into the effectiveness of their distribution strategy. This technology can also be used to suggest desirable delivery patterns and to analyze tactical and strategic decisions. Secondly, we study the inventory routing problem with continuous moves (IRP-CM). The typical inventory routing problem deals with the repeated distribution of a single product, from a single facility, with an unlimited supply, to a set of customers that can all be reached with out-and-back trips. Unfortunately, this is not always the reality. We introduce the IRP-CM to study two important real-life complexities: limited product availabilities at facilities and customers that cannot be served using out-and-back tours. We need to design delivery tours spanning several days, covering huge geographic areas, and involving product pickups at different facilities. We develop a heuristic and an optimization algorithm to construct distribution plans. The heuristic is an innovative randomized greedy algorithm, which includes linear programming based postprocessing technology. To solve the IRP-CM to optimality, we give a time-discretized integer programming model and develop a branch-and-cut algorithm. As instances of time-discretized models tend to be large we discuss several possibilities for reducing the problem size. We introduce a set of valid inequalities, called delivery cover inequalities, in order to tighten the bounds given by the LP relaxation of the time-discretized model. We also introduce branching schemes exploiting the underlying structure of the IRP-CM. An extensive computational study demonstrates the effectiveness of the optimization algorithm. Finally, we present an integrated approach using heuristics and optimization algorithms providing effective and efficient technology for solving inventory problems with continuous moves.

No description available.