Dissertations / Theses on the topic 'Robust Combinatorial Optimization'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 31 dissertations / theses for your research on the topic 'Robust Combinatorial Optimization.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
Udwani, Rajan. "Vignettes on robust combinatorial optimization." Thesis, Massachusetts Institute of Technology, 2018. http://hdl.handle.net/1721.1/120192.
This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
Cataloged from student-submitted PDF version of thesis.
Includes bibliographical references (pages 137-142).
In this thesis, we design and analyze algorithms for robust combinatorial optimization in various settings. First, we consider the problem of simultaneously maximizing multiple objectives, all monotone submodular, subject to a cardinality constraint. We focus on the case where the number of objectives is super-constant yet much smaller than the cardinality of the chosen set. We propose several algorithms (including one with the best achievable asymptotic guarantee for the problem). Experiments on synthetic data show that a heuristic based on our more practical and fast algorithm outperforms current practical algorithms in all cases considered. Next, we study the problem of robust maximization of a single monotone submodular function in scenarios where after choosing a feasible set of elements, some elements from the chosen set are adversarially removed. Under some restriction on the number of elements that can be removed, we give the first constant factor approximation algorithms as well as the best possible asymptotic approximation in certain cases. We also give a black box result for the much more general setting of deletion-robust maximization subject to an independence system. Lastly, we consider a robust appointment scheduling problem where the goal is to design simple appointment systems that try to achieve both high server utilization as well as short waiting times, under uncertainty in job processing times. When the order of jobs is fixed and one seeks to find optimal appointment duration for jobs, we give a simple heuristic that achieves the first constant factor (2) approximation. We also give closed form optimal solutions in various special cases that supersede previous work. For the setting where order of jobs is also flexible and under-utilization costs are homogeneous, it was previously shown that an EPTAS exists. We instead focus on simple and practical heuristics, and find a ratio based ordering which is 1.0604 approximate, improving on previous results for similarly practical heuristics.
by Rajan Udwani.
Ph. D.
Pass-Lanneau, Adèle. "Anchored solutions in robust combinatorial optimization." Electronic Thesis or Diss., Sorbonne université, 2021. http://www.theses.fr/2021SORUS177.
If the instance of an optimization problem changes, an initial solution may become suboptimal or infeasible. It is then necessary to compute a new solution, but it is also desirable to keep some decisions from the initial solution unchanged. In this thesis we propose the anchoring criterion to favor unchanged decisions between solutions. In a reoptimization setting, the goal is to find a new solution while keeping a maximum number of decisions from the initial solution. In a robust 2-stage optimization setting, we propose the anchor-robust approach to compute in advance a baseline solution, along with a subset of so-called anchored decisions. For any realization in the considered uncertainty set, it is possible to repair the baseline solution into a new solution without changing anchored decisions. The anchor-robust approach allows for a trade-off between the cost of a solution and guaranteed decisions. Anchoring problems are formally defined and studied on two problem classes. The first one is the class of integer programs in binary variables, including classical polynomial problems such as spanning trees. The second one is project scheduling, where jobs must be scheduled under precedence only, or precedence and resource constraints. The complexity of anchoring problems is analyzed. Combinatorial properties of anchored solutions are exhibited, and dedicated algorithmic and polyhedral approaches are devised. Mixed-integer programming techniques are investigated, that highlight the practical implementability of anchoring problems
Hites, Romina. "Robustness and preferences in combinatorial optimization." Doctoral thesis, Universite Libre de Bruxelles, 2005. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/210905.
Therefore, in each of these new measures, a second criteria is used to evaluate the performance of the solution in other scenarios such as the best case one.
We also study the robust deviation p-elements problem. In fact, we study when this solution is equal to the optimal solution in the scenario where the cost of each element is the midpoint of its corresponding interval.
Then, we finally formulate the robust combinatorial problem with interval data as a bicriteria problem. We also integrate the decision maker's preferences over certain types of solutions into the model. We propose a method that uses these preferences to find the set of solutions that are never preferred by any other solution. We call this set the final set.
We study the properties of the final sets from a coherence point of view and from a robust point of view. From a coherence point of view, we study necessary and sufficient conditions for the final set to be monotonic, for the corresponding preferences to be without cycles, and for the set to be stable.
Those that do not satisfy these properties are eliminated since we believe these properties to be essential. We also study other properties such as the transitivity of the preference and indifference relations and more. We note that many of our final sets are included in one another and some are even intersections of other final sets. From a robust point of view, we compare our final sets with different measures of robustness and with the first- and second-degree stochastic dominance. We show which sets contain all of these solutions and which only contain these types of solutions. Therefore, when the decision maker chooses his preferences to find the final set, he knows what types of solutions may or may not be in the set.
Lastly, we implement this method and apply it to the Robust Shortest Path Problem. We look at how this method performs using different types of randomly generated instances.
Doctorat en sciences, Orientation recherche opérationnelle
info:eu-repo/semantics/nonPublished
Salazar-Neumann, Martha. "Advances in robust combinatorial optimization and linear programming." Doctoral thesis, Universite Libre de Bruxelles, 2010. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/210192.
Une des approches possibles pour résoudre des tels problèmes est de considérer les versions minimax regret, pour lesquelles résoudre un problème sous incertitude revient à trouver une solution qui s'écarte le moins possible de la valeur solution optimale dans tout les cas.
Dans le cas des incertitudes définies par intervalles, les versions minimax regret de nombreux problèmes combinatoires polynomiaux sont NP-difficiles, d'ou l'importance d'essayer de réduire l'espace des solutions. Dans ce contexte, savoir quand un élément du problème, représenté par une variable, fait toujours ou jamais partie d'une solution optimal pour toute réalisation des données (variables 1-persistentes et 0-persistentes respectivement), constitue une manière de réduire la taille du problème. Un des principaux objectifs de cette thèse est d'étudier ces questions pour quelques problèmes d'optimisation combinatoire sous incertitude.
Nous étudions les versions minimax regret du problème du choix de p éléments parmi m, de l'arbre couvrant minimum et des deux problèmes de plus court chemin. Pour de tels problèmes, dans le cas des incertitudes définis par intervalles, nous étudions le problème de trouver les variables 1- et 0-persistentes. Nous présentons une procédure de pre-traitement du problème, lequel réduit grandement la taille des formulations des versions de minimax regret.
Nous nous intéressons aussi à la version minimax regret du problème de programmation linéaire dans le cas où les coefficients de la fonction objectif sont incertains et l'ensemble des données incertaines est polyédral. Dans le cas où l'ensemble des incertitudes est défini par des intervalles, le problème de trouver le regret maximum est NP-difficile. Nous présentons des cas spéciaux ou les problèmes de maximum regret et de minimax regret sont polynomiaux. Dans le cas où l´ensemble des incertitudes est défini par un polytope, nous présentons un algorithme pour trouver une solution exacte au problème de minimax regret et nous discutons les résultats numériques obtenus dans un grand nombre d´instances générées aléatoirement.
Nous étudions les relations entre le problème de 1-centre continu et la version minimax regret du problème de programmation linéaire dans le cas où les coefficients de la fonction objectif sont évalués à l´aide des intervalles. En particulier, nous décrivons la géométrie de ce dernier problème, nous généralisons quelques résultats en théorie de localisation et nous donnons des conditions sous lesquelles certaines variables peuvet être éliminées du problème. Finalement, nous testons ces conditions dans un nombre d´instances générées aléatoirement et nous donnons les conclusions.
Doctorat en sciences, Orientation recherche opérationnelle
info:eu-repo/semantics/nonPublished
Yu, Baosheng. "Robust Diversity-Driven Subset Selection in Combinatorial Optimization." Thesis, The University of Sydney, 2019. http://hdl.handle.net/2123/19834.
Hamaz, Idir. "Méthodes d'optimisation robuste pour les problèmes d'ordonnancement cyclique." Thesis, Toulouse 3, 2018. http://www.theses.fr/2018TOU30205/document.
Several studies on cyclic scheduling problems have been presented in the literature. However, most of them consider that the problem parameters are deterministic and do not consider possible uncertainties on these parameters. However, the best solution for a deterministic problem can quickly become the worst one in the presence of uncertainties, involving bad schedules or infeasibilities. Many sources of uncertainty can be encountered in scheduling problems, for example, activity durations can decrease or increase, machines can break down, new activities can be incorporated, etc. In this PhD thesis, we focus on scheduling problems that are cyclic and where activity durations are affected by uncertainties. More precisely, we consider an uncertainty set where each task duration belongs to an interval, and the number of parameters that can deviate from their nominal values is bounded by a parameter called budget of uncertainty. This parameter allows us to control the degree of conservatism of the resulting schedule. In particular, we study two cyclic scheduling problems. The first one is the basic cyclic scheduling problem (BCSP). We formulate the problem as a two-stage robust optimization problem and, using the properties of this formulation, we propose three algorithms to solve it. The second considered problem is the cyclic jobshop problem (CJSP). As for the BCSP, we formulate the problem as two-stage robust optimization problem and by exploiting the algorithms proposed for the robust BCSP we propose a Branch-and-Bound algorithm to solve it. In order to evaluate the efficiency of our method, we compared it with classical decomposition methods for two-stage robust optimization problems that exist in the literature. We also studied a version of the CJSP where each task duration takes uniformly values within an interval and where the objective is to minimize the mean value of the cycle time. In order to solve the problem, we adapted the Branch-and-Bound algorithm where in each node of the search tree, the problem to be solved is the computation of a volume of a polytope. Numerical experiments assess the efficiency of the proposed methods
Kurtz, Jannis [Verfasser], Christoph [Akademischer Betreuer] Buchheim, and Anita [Gutachter] Schöbel. "Min-max-min robust combinatorial optimization / Jannis Kurtz ; Gutachter: Anita Schöbel ; Betreuer: Christoph Buchheim." Dortmund : Universitätsbibliothek Dortmund, 2016. http://d-nb.info/1118847598/34.
Hommelsheim, Felix [Verfasser], Christoph [Akademischer Betreuer] Buchheim, and Sebastian [Gutachter] Stiller. "Complexity of bulk-robust combinatorial optimization problems / Felix Hommelsheim ; Gutachter: Sebastian Stiller ; Betreuer: Christoph Buchheim." Dortmund : Universitätsbibliothek Dortmund, 2020. http://d-nb.info/122008073X/34.
Solano, Charris Elyn Lizeth. "Optimization methods for the robust vehicle routing problem." Thesis, Troyes, 2015. http://www.theses.fr/2015TROY0026/document.
This work extends the Vehicle Routing Problem (VRP) for addressing uncertainties via robust optimization, giving the Robust VRP (RVRP). First, uncertainties are handled on travel times/costs. Then, a bi-objective version (bi-RVRP) is introduced to handle uncertainty in both, travel times and demands. For solving the RVRP and the bi-RVRP different models and methods are proposed to determine robust solutions minimizing the worst case. A Mixed Integer Linear Program (MILP), several greedy heuristics, a Genetic Algorithm (GA), a local search procedure and four local search based algorithms are proposed: a Greedy Randomized Adaptive Search Procedure (GRASP), an Iterated Local Search (ILS), a Multi-Start ILS (MS-ILS), and a MS-ILS based on Giant Tours (MS-ILS-GT) converted into feasible routes via a lexicographic splitting procedure. Concerning the bi-RVRP, the total cost of traversed arcs and the total unmet demand are minimized over all scenarios. To solve the problem, different variations of multiobjective evolutionary metaheuristics are proposed and coupled with a local search procedure: the Multiobjective Evolutionary Algorithm (MOEA) and the Non-dominated Sorting Genetic Algorithm version 2 (NSGAII). Different metrics are used to measure the efficiency, the convergence as well as the diversity of solutions for all these algorithms
Gatto, Michael Joseph. "On the impact of uncertainty on some optimization problems : combinatorial aspects of delay management and robust online scheduling /." Zürich : ETH, 2007. http://e-collection.ethbib.ethz.ch/show?type=diss&nr=17452.
Thom, Lisa [Verfasser], Anita [Akademischer Betreuer] Schöbel, Anita [Gutachter] Schöbel, and Marie [Gutachter] Schmidt. "Solution Methods for Multi-Objective Robust Combinatorial Optimization / Lisa Thom ; Gutachter: Anita Schöbel, Marie Schmidt ; Betreuer: Anita Schöbel." Göttingen : Niedersächsische Staats- und Universitätsbibliothek Göttingen, 2018. http://d-nb.info/115709466X/34.
Almeida, Coco Amadeu. "Robust covering problems : formulations, algorithms and an application." Thesis, Troyes, 2017. http://www.theses.fr/2017TROY0026/document.
Two robust optimization NP-Hard problems are studied in this thesis: the min-max regret Weighted Set Covering Problem (min-max regret WSCP) and the min-max regret Maximal Coverage Location Problem (min-max regret MCLP). The min-max regret WSCP and min-max regret MCLP are, respectively, the robust optimization counterparts of the Set Covering Problem and of the Maximal Coverage Location Problem. The uncertain data in these problems is modeled by intervals and only the minimum and maximum values for each interval are known. However, while the min-max regret WSCP is mainly studied theoretically, the min-max regret MCLP has an application in disaster logistics which is also investigated in this thesis. Two other robust optimization criteria were derived for the MCLP: the max-max MCLP and the min-max MCLP. In terms of methods, mathematical formulations, exact algorithms and heuristics were developed and applied to both problems. Computational experiments showed that the exact algorithms efficiently solved 14 out of 75 instances generated to the min-max regret WSCP and all realistic instances created to the min-max regret MCLP. For the simulated instances that was not solved to optimally in both problems, the heuristics developed in this thesis found solutions, as good as, or better than the exact algorithms in almost all instances. Concerning the application in disaster logistics, the robust models found similar solutions for realistic scenarios of the earthquakes that hit Kathmandu, Nepal in 2015. This indicates that we have got a robust solution, according to all optimization models
Diaz, Leiva Juan Esteban. "Simulation-based optimization for production planning : integrating meta-heuristics, simulation and exact techniques to address the uncertainty and complexity of manufacturing systems." Thesis, University of Manchester, 2016. https://www.research.manchester.ac.uk/portal/en/theses/simulationbased-optimization-for-production-planning-integrating-metaheuristics-simulation-and-exact-techniques-to-address-the-uncertainty-and-complexity-of-manufacturing-systems(9ef8cb33-99ba-4eb7-aa06-67c9271a50d0).html.
Aprahamian, Hrayer Yaznek Berg. "Optimal Risk-based Pooled Testing in Public Health Screening, with Equity and Robustness Considerations." Diss., Virginia Tech, 2018. http://hdl.handle.net/10919/95169.
PHD
Tozoni, Davi Colli 1988. "Solving the art gallery problem = a practical and robust method for optimal point guard positioning = Resolução do problema da galeria de arte: um método prático e robusto para o posicionamento ótimo de guardas-ponto." [s.n.], 2014. http://repositorio.unicamp.br/jspui/handle/REPOSIP/275523.
Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação
Made available in DSpace on 2018-08-25T16:57:43Z (GMT). No. of bitstreams: 1 Tozoni_DaviColli_M.pdf: 4212278 bytes, checksum: afb91e202a72e28729ff14334901884f (MD5) Previous issue date: 2014
Resumo: Nesta dissertação, apresentamos nossa pesquisa sobre o Problema da Galeria de Arte (AGP), um dos problemas mais estudados em Geometria Computacional. O AGP, que é um problema NP-difícil, consiste em encontrar o número mínimo de guardas suficiente para garantir a cobertura visual de uma galeria de arte representada por um polígono. Na versão do problema tratada neste trabalho, usualmente chamada de Problema da Galeria de Arte com Guardas-Ponto, os guardas podem ser posicionados em qualquer lugar do polígono e o objetivo é cobrir toda a região, que pode ou não conter buracos. Nós estudamos como aplicar conceitos e algoritmos de Geometria Computacional, bem como Técnicas de Programação Inteira, com a finalidade de resolver o AGP de forma exata. Este trabalho culminou na criação de um novo algoritmo para o AGP, cuja ideia é gerar, de forma iterativa, limitantes superiores e inferiores para o problema através da resolução de versões discretizadas do AGP, que são reduzidas a instâncias do Problema de Cobertura de Conjuntos. O algoritmo foi implementado e testado em mais de 2800 instâncias, de diferentes tamanhos e classes. A técnica foi capaz de resolver, em minutos, mais de 90% de todas as instâncias consideradas, incluindo polígonos com milhares de vértices, e ampliou em muito o conjunto de casos para os quais são conhecidas soluções exatas. Até onde sabemos, apesar do extensivo estudo do AGP nas últimas quatro décadas, nenhum outro algoritmo demonstrou a capacidade de resolver o AGP de forma tão eficaz como a técnica aqui descrita
Abstract: In this dissertation, we present our research on the Art Gallery Problem (AGP), one of the most investigated problems in Computational Geometry. The AGP, which is a known NP-hard problem, consists in finding the minimum number of guards sufficient to ensure the visibility coverage of an art gallery represented as a polygon. In the version of the problem treated in this work, usually called Art Gallery Problem with Point Guards, the guards can be placed anywhere in the polygon and the objective is to cover the whole region, which may or not have holes. We studied how to apply Computational Geometry concepts and algorithms as well as Integer Programming techniques in order to solve the AGP to optimality. This work culminated in the creation of a new algorithm for the AGP, whose idea is to iteratively generate upper and lower bounds for the problem through the resolution of discretized versions of the AGP, which are reduced to instances of the Set Cover Problem. The algorithm was implemented and tested on more than 2800 instances of different sizes and classes of polygons. The technique was able to solve in minutes more than 90% of all instances considered, including polygons with thousands of vertices, greatly increasing the set of instances for which exact solutions are known. To the best of our knowledge, in spite of the extensive study of the AGP in the last four decades, no other algorithm has shown the ability to solve the AGP as effectively as the one described here
Mestrado
Ciência da Computação
Mestre em Ciência da Computação
An, Na. "Resource Modeling and Allocation in Competitive Systems." Diss., Georgia Institute of Technology, 2005. http://hdl.handle.net/1853/6997.
Ridremont, Thomas. "Design of robust networks : application to the design of wind farm cabling networks." Thesis, Paris, CNAM, 2019. http://www.theses.fr/2019CNAM1228/document.
Nowadays, the design of networks has become a decisive problematic which appears in many fields such as transport or energy. In particular, it has become necessary and important to optimize the way in which networks used to produce, collect or transport energy are designed. We focus in this thesis on electricity produced through wind farms. The production of energy by wind turbines appears more than ever like a good alternative to the electrical production of thermal or nuclear power plants.We focus in this thesis on the design of the cabling network which allows to collect and route the energy from the wind turbines to a sub-station, linking the wind farm to the electrical network. In this problem, we know the location of each wind turbine of the farm and the one of the sub-station. We also know the location of possible inter-connection nodes which allow to connect different cables between them. Each wind turbine produces a known quantity of energy and with each cable are associated a cost and a capacity (the maximum amount of energy that can be routed through this cable). The optimizationproblem that we consider is to select a set of cables of minimum cost such that the energy produced from the wind turbines can be routed to the sub-station in the network induced by this set of cables, without exceeding the capacity of each cable. We focus on cabling networks resilient to breakdowns
Ridremont, Thomas. "Design of robust networks : application to the design of wind farm cabling networks." Electronic Thesis or Diss., Paris, CNAM, 2019. http://www.theses.fr/2019CNAM1228.
Nowadays, the design of networks has become a decisive problematic which appears in many fields such as transport or energy. In particular, it has become necessary and important to optimize the way in which networks used to produce, collect or transport energy are designed. We focus in this thesis on electricity produced through wind farms. The production of energy by wind turbines appears more than ever like a good alternative to the electrical production of thermal or nuclear power plants.We focus in this thesis on the design of the cabling network which allows to collect and route the energy from the wind turbines to a sub-station, linking the wind farm to the electrical network. In this problem, we know the location of each wind turbine of the farm and the one of the sub-station. We also know the location of possible inter-connection nodes which allow to connect different cables between them. Each wind turbine produces a known quantity of energy and with each cable are associated a cost and a capacity (the maximum amount of energy that can be routed through this cable). The optimizationproblem that we consider is to select a set of cables of minimum cost such that the energy produced from the wind turbines can be routed to the sub-station in the network induced by this set of cables, without exceeding the capacity of each cable. We focus on cabling networks resilient to breakdowns
Griset, Rodolphe. "Méthodes pour la résolution efficace de très grands problèmes combinatoires stochastiques : application à un problème industriel d'EDF." Thesis, Bordeaux, 2018. http://www.theses.fr/2018BORD0219/document.
The purpose of this Ph.D. thesis is to study optimization techniques for large-scale stochastic combinatorial problems. We apply those techniques to the problem of scheduling EDF nuclear power plant maintenance outages, which is of significant importance due to the major part of the nuclear energy in the French electricity system. We build on a two-stages extended formulation, the first level of which fixes nuclear outage dates and production profiles for nuclear plants, while the second evaluates the cost to meet the demand. This formulation enables the solving of deterministic industrial instances to optimality, by using a MIP solver. However, the computational time increases significantly with the number of scenarios. Hence, we resort to a procedure combining column generation of a Dantzig-Wolfe decomposition with Benders’ cut generation, to account for the linear relaxation of stochastic instances. We then obtain integer solutions of good quality via a heuristic, up to fifty scenarios. We further assume that outage durations are uncertain and that unexpected shutdowns of plants may occur. We investigate robust optimization methods in this context while ignoring possible recourse on power plants outage dates. We report on several approaches, which use bi-objective or probabilistic methods, to ensure the satisfaction of constraints which might be relaxed in the operating process. For other constraints, we apply a budget uncertainty-based approach to limit future re-organizations of the scheduling. Adding probabilistic information leads to better control of the price of the robustness
Durán, Mateluna Cristian. "Exact solution methods for large-scale discrete p-facility location problems." Electronic Thesis or Diss., Institut polytechnique de Paris, 2024. http://www.theses.fr/2024IPPAE001.
This thesis focuses on the exact solution of the NP-hard problems p-median and p-center, combinatorial optimization problems that quickly become difficult to solve as the instance size increases. These discrete location problems involve opening a defined number p of facilities and then allocating to them a set of clients according to an objective function to be minimized.First, we study the p-median problem, which seeks to minimize the sum of distances between clients and the open facilities to which they are allocated. We develop an algorithm based on Benders decomposition that outperforms state-of-the-art exact methods. The algorithm considers a two-stage approach and an efficient algorithm for separating Benders cuts. The method has been evaluated on over 230 benchmark instances with up to 238025 clients and sites. Many instances are solved to optimality for the first time or have their best known solution improved.Secondly, we explore the p-center problem, which seeks to minimize the largest distance between a client and its nearest open facility. We first compare the five main MILP formulations in the literature. We study the Benders decomposition and also propose an exact algorithm based on a client clustering procedure based on the structure of the problem. All the proposed methods are compared with the state-of-the-art on benchmark instances. The results obtained are analyzed, highlighting the advantages and disadvantages of each method.Finally, we study a robust two-stage p-center problem with uncertainty on node demands and distances. We introduce the robust reformulation of the problem based on the five main deterministic MILP formulations in the literature. We prove that only a finite subset of scenarios from the infinite uncertainty set can be considered without losing optimality. We also propose a column and constraint generation algorithm and a branch-and-cut algorithm to efficiently solve this problem. We show how these algorithms can also be adapted to solve the robust single-stage problem. The different proposed formulations are tested on randomly generated instances and on a case study drawn from the literature
Poirion, Pierre-Louis. "Programmation linéaire mixte robuste; Application au dimensionnement d'un système hybride de production d'électricité." Thesis, Paris, CNAM, 2013. http://www.theses.fr/2015CNAM0948/document.
Robust optimization is a recent approach to study problems with uncertain datathat does not rely on a prerequisite precise probability model but on mild assumptionson the uncertainties involved in the problem.We studied a linear two-stage robustproblem with mixed-integer first-stage variables and continuous second stagevariables. We considered column wise uncertainty and focused on the case whenthe problem doesn’t satisfy a "full recourse property" which cannot be always satisfied for real problems. We also studied the complexity of the robust problemwhich is NP-hard and proved that it is actually polynomial solvable when a parameterof the problem is fixed.We then applied this approach to study a stand-alonehybrid system composed of wind turbines, solar photovoltaic panels and batteries.The aim was to determine the optimal number of photovoltaic panels, wind turbinesand batteries in order to serve a given demand while minimizing the total cost of investment and use. We also studied some properties of the second stage problem, in particular that the second stage problem can be solvable in polynomial time using dynamic programming
Poirion, Pierre-Louis. "Programmation linéaire mixte robuste; Application au dimensionnement d'un système hybride de production d'électricité." Electronic Thesis or Diss., Paris, CNAM, 2013. http://www.theses.fr/2013CNAM0948.
Robust optimization is a recent approach to study problems with uncertain datathat does not rely on a prerequisite precise probability model but on mild assumptionson the uncertainties involved in the problem.We studied a linear two-stage robustproblem with mixed-integer first-stage variables and continuous second stagevariables. We considered column wise uncertainty and focused on the case whenthe problem doesn’t satisfy a "full recourse property" which cannot be always satisfied for real problems. We also studied the complexity of the robust problemwhich is NP-hard and proved that it is actually polynomial solvable when a parameterof the problem is fixed.We then applied this approach to study a stand-alonehybrid system composed of wind turbines, solar photovoltaic panels and batteries.The aim was to determine the optimal number of photovoltaic panels, wind turbinesand batteries in order to serve a given demand while minimizing the total cost of investment and use. We also studied some properties of the second stage problem, in particular that the second stage problem can be solvable in polynomial time using dynamic programming
Chopra, Smriti. "Spatio-temporal multi-robot routing." Diss., Georgia Institute of Technology, 2015. http://hdl.handle.net/1853/53383.
Haddad, Marcel Adonis. "Nouveaux modèles robustes et probabilistes pour la localisation d'abris dans un contexte de feux de forêt." Electronic Thesis or Diss., Université Paris sciences et lettres, 2020. http://www.theses.fr/2020UPSLD021.
The location of shelters in different areas threatened by wildfires is one of the possible ways to reduce fatalities in acontext of an increasing number of catastrophic and severe forest fires. The problem is basically to locate p sheltersminimizing the maximum distance people will have to cover to reach the closest accessible shelter in case of fire. Thelandscape is divided in zones and is modeled as an edge-weighted graph with vertices corresponding to zones andedges corresponding to direct connections between two adjacent zones. Each scenario corresponds to a fire outbreak ona single zone (i.e., on a vertex) with the main consequence of modifying evacuation paths in two ways. First, an evacuationpath cannot pass through the vertex on fire. Second, the fact that someone close to the fire may have limited choice, ormay not take rational decisions, when selecting a direction to escape is modeled using a new kind of evacuation strategy.This evacuation strategy, called Under Pressure, induces particular evacuation distances which render our model specific.We propose two problems with this model: the Robust p-Center Under Pressure problem and the Probabilistic p-CenterUnder Pressure problem. First we prove hardness results for both problems on relevant classes of graphs for our context.In addition, we propose polynomial exact algorithms on simple classes of graphs and we develop mathematical algorithmsbased on integer linear programming
Rehbinder, Henrik. "State Estimation and Limited Communication Control for Nonlinear Robotic Systems." Doctoral thesis, KTH, Mathematics, 2001. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-3250.
Touzani, Hicham. "Planification Multi-Robot du Problème de Répartition de Tâches avec Évitement Automatique de Collisions et Optimisation du Temps de Cycle : Application à la Chaîne de Production Automobile." Electronic Thesis or Diss., université Paris-Saclay, 2022. http://www.theses.fr/2022UPAST079.
In the automotive industry, several robots are required to simultaneously carry out welding sequences on the same vehicle. Assigning and coordinating welding tasks between robots is a manual and challenging phase that must be optimized using automatic tools. The cycle time of the cell strongly depends on different robotic factors such as the task allocation among the robots, the configuration solutions, and obstacle avoidance. Moreover, a key aspect, often neglected in the state-ofthe- art, is to define a strategy to solve the robotic task sequencing with an effective robot-robot collision avoidance integration. This thesis is motivated by solving this industrial problem and seeks to raise different research challenges. It begins by presenting the current state-of-the-art solutions regarding robotic planning. An in-depth investigation is carried out on the related existing academic/industrial solutions to solve the robotic task sequencing problem, particularly for multi-robot systems. This investigation helps identify the challenges when integrating several robotic factors into the optimization process. An efficient iterative algorithm that generates a high-quality solution for the Multi-Robotic Task Sequencing Problem is presented. This algorithm manages not only the mentioned robotic factors but also aspects related to accessibility constraints and mutual collision avoidance. In addition, a home-developed planner (RoboTSPlanner) handling six-axis robots has been validated in a real case scenario. In order to ensure the completeness of the proposed methodology, we perform optimization in the task, configuration, and coordination space in a synergistic way. Compared to the existing approaches, both simulation and real experiments reveal positive results in terms of cycle time and show the ability of this method to be interfaced with both industrial simulation software and ROS-I tools
Thom, Lisa. "Solution Methods for Multi-Objective Robust Combinatorial Optimization." Doctoral thesis, 2018. http://hdl.handle.net/11858/00-1735-0000-002E-E3D4-D.
Le, Xuan Thanh. "Robust solutions to storage loading problems under uncertainty." Doctoral thesis, 2017. https://repositorium.ub.uni-osnabrueck.de/handle/urn:nbn:de:gbv:700-2017021715554.
Karimi, Mehdi. "A Quick-and-Dirty Approach to Robustness in Linear Optimization." Thesis, 2012. http://hdl.handle.net/10012/7178.
Gupta, Shubham. "Building Networks in the Face of Uncertainty." Thesis, 2011. http://hdl.handle.net/10012/6140.
PINTO, DIEGO MARIA. "Mathematical optimization and learning models to address uncertainties and sustainability of supply chain management." Doctoral thesis, 2023. https://hdl.handle.net/11573/1666725.