Bibliografie tematiche / Robust Combinatorial Optimization

Letteratura scientifica selezionata sul tema "Robust Combinatorial Optimization"

Autore: Grafiati

Pubblicato: 15 giugno 2024

Cita una fonte nei formati APA, MLA, Chicago, Harvard e in molti altri stili

Scegli il tipo di fonte:

Consulta la lista di attuali articoli, libri, tesi, atti di convegni e altre fonti scientifiche attinenti al tema "Robust Combinatorial Optimization".

Accanto a ogni fonte nell'elenco di riferimenti c'è un pulsante "Aggiungi alla bibliografia". Premilo e genereremo automaticamente la citazione bibliografica dell'opera scelta nello stile citazionale di cui hai bisogno: APA, MLA, Harvard, Chicago, Vancouver ecc.

Puoi anche scaricare il testo completo della pubblicazione scientifica nel formato .pdf e leggere online l'abstract (il sommario) dell'opera se è presente nei metadati.

Articoli di riviste sul tema "Robust Combinatorial Optimization":

Adjiashvili, David, Sebastian Stiller e Rico Zenklusen. "Bulk-Robust combinatorial optimization". Mathematical Programming 149, n. 1-2 (13 febbraio 2014): 361–90. http://dx.doi.org/10.1007/s10107-014-0760-6.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Kawase, Yasushi, e Hanna Sumita. "Randomized Strategies for Robust Combinatorial Optimization". Proceedings of the AAAI Conference on Artificial Intelligence 33 (17 luglio 2019): 7876–83. http://dx.doi.org/10.1609/aaai.v33i01.33017876.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

In this paper, we study the following robust optimization problem. Given an independence system and candidate objective functions, we choose an independent set, and then an adversary chooses one objective function, knowing our choice. The goal is to find a randomized strategy (i.e., a probability distribution over the independent sets) that maximizes the expected objective value in the worst case. This problem is fundamental in wide areas such as artificial intelligence, machine learning, game theory and optimization. To solve the problem, we propose two types of schemes for designing approximation algorithms. One scheme is for the case when objective functions are linear. It first finds an approximately optimal aggregated strategy and then retrieves a desired solution with little loss of the objective value. The approximation ratio depends on a relaxation of an independence system polytope. As applications, we provide approximation algorithms for a knapsack constraint or a matroid intersection by developing appropriate relaxations and retrievals. The other scheme is based on the multiplicative weights update (MWU) method. The direct application of the MWU method does not yield a strict multiplicative approximation algorithm but yield one with an additional additive error term. A key technique to overcome the issue is to introduce a new concept called (η,γ)-reductions for objective functions with parameters η and γ. We show that our scheme outputs a nearly α-approximate solution if there exists an α-approximation algorithm for a subproblem defined by (η,γ)-reductions. This improves approximation ratios in previous results. Using our result, we provide approximation algorithms when the objective functions are submodular or correspond to the cardinality robustness for the knapsack problem.

Buchheim, Christoph, e Jannis Kurtz. "Min–max–min robust combinatorial optimization". Mathematical Programming 163, n. 1-2 (14 luglio 2016): 1–23. http://dx.doi.org/10.1007/s10107-016-1053-z.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Poss, Michael. "Robust combinatorial optimization with knapsack uncertainty". Discrete Optimization 27 (febbraio 2018): 88–102. http://dx.doi.org/10.1016/j.disopt.2017.09.004.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Koster, Arie M. C. A., e Michael Poss. "Special issue on: robust combinatorial optimization". EURO Journal on Computational Optimization 6, n. 3 (settembre 2018): 207–9. http://dx.doi.org/10.1007/s13675-018-0102-1.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Goerigk, Marc, e Stefan Lendl. "Robust Combinatorial Optimization with Locally Budgeted Uncertainty". Open Journal of Mathematical Optimization 2 (18 maggio 2021): 1–18. http://dx.doi.org/10.5802/ojmo.5.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Goerigk, Marc, e Stephen J. Maher. "Generating hard instances for robust combinatorial optimization". European Journal of Operational Research 280, n. 1 (gennaio 2020): 34–45. http://dx.doi.org/10.1016/j.ejor.2019.07.036.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Poss, Michael. "Robust combinatorial optimization with variable cost uncertainty". European Journal of Operational Research 237, n. 3 (settembre 2014): 836–45. http://dx.doi.org/10.1016/j.ejor.2014.02.060.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Dokka, Trivikram, Marc Goerigk e Rahul Roy. "Mixed uncertainty sets for robust combinatorial optimization". Optimization Letters 14, n. 6 (24 luglio 2019): 1323–37. http://dx.doi.org/10.1007/s11590-019-01456-3.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Kurtz, Jannis. "Robust combinatorial optimization under budgeted–ellipsoidal uncertainty". EURO Journal on Computational Optimization 6, n. 4 (8 maggio 2018): 315–37. http://dx.doi.org/10.1007/s13675-018-0097-7.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Più fonti

Tesi sul tema "Robust Combinatorial Optimization":

Udwani, Rajan. "Vignettes on robust combinatorial optimization". Thesis, Massachusetts Institute of Technology, 2018. http://hdl.handle.net/1721.1/120192.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Thesis: Ph. D., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2018.
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, Adèle. "Anchored solutions in robust combinatorial optimization". Electronic Thesis or Diss., Sorbonne université, 2021. http://www.theses.fr/2021SORUS177.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Si les données d'un problème d'optimisation combinatoire changent, une solution initiale peut devenir sous-optimale ou infaisable. Il est alors nécessaire de calculer une nouvelle solution, mais aussi souhaitable de maintenir les décisions prises dans la solution initiale. Dans cette thèse nous proposons le critère d'ancrage pour favoriser les décisions inchangées entre solutions. En réoptimisation, il s'agit de trouver une solution conservant un nombre maximal de décisions d'une solution initiale. En optimisation robuste à deux étapes, nous proposons l'approche robuste-ancrée, qui consiste à calculer en avance une solution baseline et un sous-ensemble de décisions dites ancrées. Pour toute réalisation des données dans l'ensemble d'incertitude considéré, on peut réparer la solution baseline en une nouvelle solution sans changer les décisions ancrées. Cette approche permet un compromis entre le coût de la solution et les garanties sur les décisions. Les problèmes d'ancrage sont formalisés et déclinés sur deux classes de problèmes. La première est celle des programmes linéaires en variables binaires, et notamment des problèmes polynomiaux classiques comme l'arbre couvrant. La deuxième est celle des problèmes d'ordonnancement de projet, où des tâches doivent être ordonnancées sous des contraintes de précédences ou de ressources. La complexité algorithmique des problèmes d'ancrage est analysée. Les propriétés combinatoires des solutions ancrées sont étudiées, et permettent la conception d'approches algorithmiques et polyédrales dédiées. Des techniques de programmation linéaire en nombres entiers sont mises en œuvre, démontrant l'implémentabilité des problèmes d'ancrage
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.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

In this thesis, we study robust combinatorial problems with interval data. We introduce several new measures of robustness in response to the drawbacks of existing measures of robustness. The idea of these new measures is to ensure that the solutions are satisfactory for the decision maker in all scenarios, including the worst case scenario. Therefore, we have introduced a threshold over the worst case costs, in which above this threshold, solutions are no longer satisfactory for the decision maker. It is, however, important to consider other criteria than just the worst case.

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.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

La construction de modèles qui protègent contre les incertitudes dans les données, telles que la variabilité de l'information et l'imprécision est une des principales préoccupations en optimisation sous incertitude. L'incertitude peut affecter différentes domaines, comme le transport, les télécommunications, la finance, etc. ainsi que les différentes parts d'un problème d'optimisation, comme les coefficients de la fonction objectif et /ou les contraintes. De plus, l'ensemble des données incertaines peut être modélisé de différentes façons, comme sous ensembles compactes et convexes de l´espace réel de dimension n, polytopes, produits Cartésiens des intervalles, ellipsoïdes, etc.

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.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Subset selection is fundamental in combinatorial optimization with applications in biology, operations research, and computer science, especially machine learning and computer vision. However, subset selection has turned out to be NP-hard and polynomial-time solutions are usually not available. Therefore, it is of great importance to develop approximate algorithms with theoretical guarantee for subset selection in constrained settings. To select a diverse subset with an asymmetric objective function, we develop an asymmetric subset selection method, which is computationally efficient and has a solid lower bound on approximation ratio. Experimental results on cascade object detection demonstrate the effectiveness of the proposed method. To select a diverse subset with bandit feedbacks, we develop a new bandit framework, which we refer to it as per-round knapsack constrained linear submodular bandits. With the proposed bandit framework, we propose two algorithms with solid regret bounds. Experimental results on personalized recommendation demonstrate the effectiveness of the proposed method. To correct bias in subset selection, we develop a new regularization criterion to minimize the distribution shift between selected subset and the set of all elements. Experimental results on image retrieval demonstrate the effectiveness of the proposed method. To explore diversity in anchor templates, we devise a pyramid of diversity-driven anchor templates to generate high quality proposals. Experimental results on cascade face detection demonstrate the effectiveness of the proposed method. In this thesis, we focus on developing robust diversity-driven subset selection methods in constrained settings as well as their applications in machine learning and computer vision.

Hamaz, Idir. "Méthodes d'optimisation robuste pour les problèmes d'ordonnancement cyclique". Thesis, Toulouse 3, 2018. http://www.theses.fr/2018TOU30205/document.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Plusieurs problèmes d'ordonnancement cyclique ont été étudiés dans la littérature. Cependant, la plupart de ces travaux considèrent que les paramètres sont connus avec certitude et ne prennent pas en compte les différents aléas qui peuvent survenir. Par ailleurs, un ordonnancement optimal pour un problème déterministe peut très vite devenir le pire ordonnancement en présence d'incertitude. Parmi les incertitudes que nous pouvons rencontrer dans les problèmes d'ordonnancement, la variation des durées des tâches par rapport au valeurs estimées, pannes des machines, incorporation de nouvelles tâches qui ne sont pas considérées au départ, etc. Dans cette thèse, nous étudions des problèmes d'ordonnancement cyclique où les durées des tâches sont affectées par des incertitudes. Ces dernières sont décrites par un ensemble d'incertitude où les durées des tâches sont supposées appartenir à des intervalles et le nombre de déviations par rapport aux valeurs nominales est contrôlé par un paramètre appelé budget d'incertitude. Nous étudions deux problèmes en particulier. Le premier est le problème d'ordonnancement cyclique de base (BCSP). Nous formulons celui-ci comme un problème d'optimisation robuste bi-niveau et, à partir des propriétés de cette formulation, nous proposons différents algorithmes pour le résoudre. Le deuxième problème considéré est le problème du jobshop cyclique. De manière similaire au BSCP, nous proposons une formulation en termes de problème d'optimisation bi-niveau et, en exploitant les algorithmes développés pour le problème d'ordonnancement cyclique de base, nous développons un algorithme de Branch-and-Bound pour le résoudre. Afin d'évaluer l'efficacité de notre méthode nous l'avons comparé à des méthodes de décomposition qui existent dans la littérature pour ce type de problèmes. Enfin, nous avons étudié une version du problème du jobshop cyclique où les durées des tâches prennent des valeurs dans des intervalles d'une manière uniforme et dont l'objectif est de minimiser la valeur moyenne du temps de cycle. Pour résoudre ce problème nous avons adopté un algorithme de Branch-and-Bound où chaque sous-problème de l'arbre de recherche consiste à calculer le volume d'un polytope. Enfin, pour montrer l'efficacité de chacune de ses méthodes, des résultats numériques sont présentés
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 e 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.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Hommelsheim, Felix [Verfasser], Christoph [Akademischer Betreuer] Buchheim e 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.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Solano, Charris Elyn Lizeth. "Optimization methods for the robust vehicle routing problem". Thesis, Troyes, 2015. http://www.theses.fr/2015TROY0026/document.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Cette thèse aborde le problème de tournées de véhicules (VRP) adressant des incertitudes via l'optimisation robuste, en donnant le VRP Robuste (RVRP). D'abord, les incertitudes sont intégrées sur les temps de trajet. Ensuite, une version bi-objectif du RVRP (bi-RVRP) est considérée en prenant en compte les incertitudes sur les temps de trajet et les demandes. Pour résoudre le RVRP et le bi-RVRP, différentes méthodes sont proposées pour déterminer des solutions robustes en minimisant le pire cas. Un Programme Linéaire à Variables Mixtes Entières (MILP), six heuristiques constructives, un algorithme génétique (GA), une procédure de recherche locale et quatre stratégies itératives à démarrage multiple sont proposées : une procédure de recherche constructive adaptive randomisée (GRASP), une recherche locale itérée (ILS), une ILS à démarrage multiple (MS-ILS), et une MS-ILS basée sur des tours géants (MS-ILS-GT) convertis en tournées réalisables grâce à un découpage lexicographique. Concernant le bi-RVRP, le coût total des arcs traversés et la demande totale non satisfaite sont minimisés sur tous les scénarios. Pour résoudre le problème, différentes versions de métaheuristiques évolutives multi-objectif sont proposées et couplées à une recherche locale : l'algorithme évolutionnaire multi-objectif (MOEA) et l'algorithme génétique avec tri par non-domination version 2 (NSGAII). Différentes métriques sont utilisées pour mesurer l’efficience, la convergence, ainsi que la diversité des solutions pour tous ces algorithmes
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 /". Zürich : ETH, 2007. http://e-collection.ethbib.ethz.ch/show?type=diss&nr=17452.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Più fonti

Libri sul tema "Robust Combinatorial Optimization":

Ahuja, Ravindra K. Robust and Online Large-Scale Optimization: Models and Techniques for Transportation Systems. Berlin, Heidelberg: Springer-Verlag Berlin Heidelberg, 2009.

Cerca il testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Davidor, Yuval. Genetic algorithms and robotics: A heuristic strategy for optimization. Singapore: World Scientific, 1991.

Cerca il testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Capitoli di libri sul tema "Robust Combinatorial Optimization":

Gabrel, Virginie, e Cécile Murat. "Robust Shortest Path Problems". In Paradigms of Combinatorial Optimization, 615–39. Hoboken, NJ, USA: John Wiley & Sons, Inc., 2013. http://dx.doi.org/10.1002/9781118600207.ch19.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Gabrel, Virginie, e Cécile Murat. "Robust Shortest Path Problems". In Paradigms of Combinatorial Optimization, 615–39. Hoboken, NJ, USA: John Wiley & Sons, Inc., 2014. http://dx.doi.org/10.1002/9781119005353.ch19.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Eberle, Franziska, Ruben Hoeksma, Nicole Megow, Lukas Nölke, Kevin Schewior e Bertrand Simon. "Speed-Robust Scheduling". In Integer Programming and Combinatorial Optimization, 283–96. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-73879-2_20.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

D’Angelo, Gianlorenzo, Gabriele Di Stefano, Alfredo Navarra e Cristina M. Pinotti. "Recoverable Robust Timetables on Trees". In Combinatorial Optimization and Applications, 451–62. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-642-02026-1_43.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Kasperski, Adam, Adam Kurpisz e Paweł Zieliński. "Recoverable Robust Combinatorial Optimization Problems". In Operations Research Proceedings, 147–53. Cham: Springer International Publishing, 2013. http://dx.doi.org/10.1007/978-3-319-00795-3_22.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Genc, Begum, Mohamed Siala, Gilles Simonin e Barry O’Sullivan. "On the Complexity of Robust Stable Marriage". In Combinatorial Optimization and Applications, 441–48. Cham: Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-71147-8_30.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Orlin, James B., Andreas S. Schulz e Rajan Udwani. "Robust Monotone Submodular Function Maximization". In Integer Programming and Combinatorial Optimization, 312–24. Cham: Springer International Publishing, 2016. http://dx.doi.org/10.1007/978-3-319-33461-5_26.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Cicerone, Serafino, Gianlorenzo D’Angelo, Gabriele Di Stefano, Daniele Frigioni e Alfredo Navarra. "Delay Management Problem: Complexity Results and Robust Algorithms". In Combinatorial Optimization and Applications, 458–68. Berlin, Heidelberg: Springer Berlin Heidelberg, 2008. http://dx.doi.org/10.1007/978-3-540-85097-7_43.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Gupta, Anupam, Viswanath Nagarajan e Vijay V. Vazirani. "Thrifty Algorithms for Multistage Robust Optimization". In Integer Programming and Combinatorial Optimization, 217–28. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013. http://dx.doi.org/10.1007/978-3-642-36694-9_19.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Ganapathy, Murali K. "Robust Mixing". In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 351–62. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006. http://dx.doi.org/10.1007/11830924_33.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Atti di convegni sul tema "Robust Combinatorial Optimization":

Shao, Zhihui, Jianyi Yang, Cong Shen e Shaolei Ren. "Learning for Robust Combinatorial Optimization: Algorithm and Application". In IEEE INFOCOM 2022 - IEEE Conference on Computer Communications. IEEE, 2022. http://dx.doi.org/10.1109/infocom48880.2022.9796715.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Zhang, Xin, Yilin Fang e Quan Liu. "Finding Robust Pareto-Optimal Solutions Over Time for Dynamic Disassembly Sequence Planning". In ASME 2022 17th International Manufacturing Science and Engineering Conference. American Society of Mechanical Engineers, 2022. http://dx.doi.org/10.1115/msec2022-85358.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Abstract Disassembly sequence planning plays a crucial role in the reuse and remanufacturing of end-of-life products, which is a combinatorial optimization problem and has been studied by many researchers. However, it is challenging to obtain optimal disassembly sequences due to great uncertainty owing to various unpredictable factors. We note that some of the uncertainties accompanying the products disassembly process are characterized by dynamic changes and can actually be regarded as dynamic disassembly sequence planning problem. Robust Pareto-optimal over time (RPOT) is a good approach to aovid the inconvenience of tracking optimization by finding solutions that remain acceptable over an extended period. Since there are few studies on applying RPOT to combinatorial optimization, the autoregressive prediction model in RPOT is more suitable for continuous search space problems than combinatorial optimization. In this paper, we develop a dynamic disassembly sequence planning problem considering the uncertainty caused by dynamically changing product states. Finding robust Pareto-optimal solutions over time for dynamci disassembly sequence planning to avoid the consumption of frequent switching solutions. To better apply RPOT to combinatorial optimization, online prediction model is proposed to replace the autoregressive prediction model. Experiment is executed in the three scale problems and compared with tracking optimization. The results indicate that online predictors can effectively improve the accuracy of prediction and improve the performance of the algorithm, and RPOT with new predictor is a more practical and time-saving method of addressing dynamic disaseembly sequence planning problem than tracking optimization.

Zhang, J., W. Wu e M. Yagiura. "Worst case scenario lemma for Γ-robust combinatorial optimization problems under max-min criterion". In 2017 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM). IEEE, 2017. http://dx.doi.org/10.1109/ieem.2017.8289850.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Martin, Hugo, e Patrice Perny. "BiOWA for Preference Aggregation with Bipolar Scales: Application to Fair Optimization in Combinatorial Domains". In Twenty-Eighth International Joint Conference on Artificial Intelligence {IJCAI-19}. California: International Joint Conferences on Artificial Intelligence Organization, 2019. http://dx.doi.org/10.24963/ijcai.2019/252.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

We study the biOWA model for preference aggregation and multicriteria decision making from bipolar rating scales. A biOWA is an ordered doubly weighted averaging extending standard ordered weighted averaging (OWA) and allowing a finer control of the importance attached to positive and negative evaluations in the aggregation. After establishing some useful properties of biOWA to generate balanced Pareto-optimal solutions, we address fair biOWA-optimization problems in combinatorial domains. We first consider the use of biOWA in multi-winner elections for aggregating graded approval and disapproval judgements. Then we consider the use of biOWA for solving robust path problems with costs expressing gains and losses. A linearization of biOWA is proposed, allowing both problems to be solved by MIP. A path-ranking algorithm for biOWA optimization is also proposed. Numerical tests are provided to show the practical efficiency of our models.

Tiwari, Santosh, Joshua Summers e Georges Fadel. "A Genetic Algorithm Based Procedure for Extracting Optimal Solutions From a Morphological Chart". In ASME 2007 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. ASMEDC, 2007. http://dx.doi.org/10.1115/detc2007-35497.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

A novel approach using a genetic algorithm is presented for extracting globally satisfycing (Pareto optimal) solutions from a morphological chart where the evaluation and combination of “means to sub-functions” is modeled as a combinatorial multi-objective optimization problem. A fast and robust genetic algorithm is developed to solve the resulting optimization problem. Customized crossover and mutation operators specifically tailored to solve the combinatorial optimization problem are discussed. A proof-of-concept simulation on a practical design problem is presented. The described genetic algorithm incorporates features to prevent redundant evaluation of identical solutions and a method for handling of the compatibility matrix (feasible/infeasible combinations) and addressing desirable/undesirable combinations. The proposed approach is limited by its reliance on the quantifiable metrics for evaluating the objectives and the existence of a mathematical representation of the combined solutions. The optimization framework is designed to be a scalable and flexible procedure which can be easily modified to accommodate a wide variety of design methods that are based on the morphological chart.

Jacobs, Tobias, Francesco Alesiani e Gulcin Ermis. "Reinforcement Learning for Route Optimization with Robustness Guarantees". In Thirtieth International Joint Conference on Artificial Intelligence {IJCAI-21}. California: International Joint Conferences on Artificial Intelligence Organization, 2021. http://dx.doi.org/10.24963/ijcai.2021/357.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Application of deep learning to NP-hard combinatorial optimization problems is an emerging research trend, and a number of interesting approaches have been published over the last few years. In this work we address robust optimization, which is a more complex variant where a max-min problem is to be solved. We obtain robust solutions by solving the inner minimization problem exactly and apply Reinforcement Learning to learn a heuristic for the outer problem. The minimization term in the inner objective represents an obstacle to existing RL-based approaches, as its value depends on the full solution in a non-linear manner and cannot be evaluated for partial solutions constructed by the agent over the course of each episode. We overcome this obstacle by defining the reward in terms of the one-step advantage over a baseline policy whose role can be played by any fast heuristic for the given problem. The agent is trained to maximize the total advantage, which, as we show, is equivalent to the original objective. We validate our approach by solving min-max versions of standard benchmarks for the Capacitated Vehicle Routing and the Traveling Salesperson Problem, where our agents obtain near-optimal solutions and improve upon the baselines.

Koch, Patrick N., Janet K. Allen, Farrokh Mistree e Dimitri Mavris. "The Problem of Size in Robust Design". In ASME 1997 Design Engineering Technical Conferences. American Society of Mechanical Engineers, 1997. http://dx.doi.org/10.1115/detc97/dac-3983.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Abstract To facilitate the effective solution of multidisciplinary, multiobjective complex design problems, a departure from the traditional parametric design analysis and single objective optimization approaches is necessary in the preliminary stages of design. A necessary tradeoff becomes one of efficiency vs. accuracy as approximate models are sought to allow fast analysis and effective exploration of a preliminary design space. In this paper we apply a general robust design approach for efficient and comprehensive preliminary design to a large complex system: a high speed civil transport (HSCT) aircraft. Specifically, we investigate the HSCT wing configuration design, incorporating life cycle economic uncertainties to identify economically robust solutions. The approach is built on the foundation of statistical experimentation and modeling techniques and robust design principles, and is specialized through incorporation of the compromise Decision Support Problem for multiobjective design. For large problems however, as in the HSCT example, this robust design approach developed for efficient and comprehensive design breaks down with the problem of size — combinatorial explosion in experimentation and model building with number of variables — and both efficiency and accuracy are sacrificed. Our focus in this paper is on identifying and discussing the implications and open issues associated with the problem of size for the preliminary design of large complex systems.

Lyons, Donald P., e Ken D. Kihm. "Tomographic Identification of Bubbles in Two-Phase Flows Using a Genetic Algorithm". In ASME 1997 International Mechanical Engineering Congress and Exposition. American Society of Mechanical Engineers, 1997. http://dx.doi.org/10.1115/imece1997-0788.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Abstract Genetic algorithm (GA)-based tomographic reconstruction algorithm is examined to use for nonintrusive optical or acoustic imaging of bubbles in two-phase flows. Individual bubble boundaries are described by elliptical basis functions whose major and minor axes specify the bubble shape and sizes. Genetic algorithm, a robust combinatorial non-linear optimization based on fittest survival principle, allows a regressive determination of the bubble center locations, shape and sizes simultaneously by maximizing the fidelity of guessed images compared with measured images. Preliminary results indicate a strong potential of GA-based tomography for accurate reconstruction of two-phase flow images.

Kotary, James, Vincenzo Di Vito e Ferdinando Fioretto. "Differentiable Model Selection for Ensemble Learning". In Thirty-Second International Joint Conference on Artificial Intelligence {IJCAI-23}. California: International Joint Conferences on Artificial Intelligence Organization, 2023. http://dx.doi.org/10.24963/ijcai.2023/217.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Model selection is a strategy aimed at creating accurate and robust models by identifying the optimal model for classifying any particular input sample. This paper proposes a novel framework for differentiable selection of groups of models by integrating machine learning and combinatorial optimization. The framework is tailored for ensemble learning with a strategy that learns to combine the predictions of appropriately selected pre-trained ensemble models. It does so by modeling the ensemble learning task as a differentiable selection program trained end-to-end over a pretrained ensemble to optimize task performance. The proposed framework demonstrates its versatility and effectiveness, outperforming conventional and advanced consensus rules across a variety of classification tasks.

Rao, Navin S., e Krishnan Balasubramaniam. "Analysis and Characterization of Ply Lay-Up in Fiber Reinforced Composites Using Ultrasonic Plate Wave Dispersion Curves". In ASME 1997 International Mechanical Engineering Congress and Exposition. American Society of Mechanical Engineers, 1997. http://dx.doi.org/10.1115/imece1997-1041.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Abstract In this paper, initial efforts on the characterization of the ultrasonic oblique incidence data to obtain the fiber orientation and ply Lay-up properties of orthotropic symmetry material systems, such as fiber reinforced composites, will be discussed. The acoustical data domain used was the plate wave dispersion curves. The influence of ply-Lay-up ordering in cross-ply symmetric graphite/epoxy laminates on leaky plate wave dispersion curves was studied. The Thomson-Haskell Method was implemented to model the reflection factor behavior of fluid-loaded laminated plates and compute the dispersion curves. Two different types of ply ordering — staggered and inverted — were examined. It was found that the all dispersion modes are sensitive to changes in lay-up sequence. Consequently, it was concluded that stacking sequence identification from leaky plate wave dispersion data is indeed possible, provided accurate experimental and robust combinatorial optimization techniques are used. It is further recommended that Genetic Algorithms can be used as the optimization tool for solving the inverse problem of nondestructively obtaining the ply-Lay-up from experimental oblique incidence ultrasonic data on composite materials.