This thesis deals with the no-depot minmax Multiple Traveling Salesmen Problem (MTSP), which can be formulated as follows. Given a set of n cities and k salesmen,find k disjoint tours (one for each salesmen) such that each city belongs to exactly one tour and the length of the longest of k tours is minimized. The no-depot assumption means that the salesmen do not start from and return to one fixed depot. The no-depot model can be applied in designing patrolling routes, as well as in business situations, especially where salesmen work from home or the company has no central office. This model can be also applied to the job scheduling problem with n jobs and k identical machines. Despite its potential applicability to a number of important situations, the research literature on the no-depot minmax k-TSP has been limited, with no reports on computational experiments. The previously published results included the proof of NP-hardness of the problem of interest, which motivates using heuristics for its solution. This thesis proposes several construction heuristic algorithms, including greedy algorithms, cluster first and route second algorithms, and route first and cluster second algorithms. As a local search method for a single tour, 2-opt search and Lin-Kernighan were used, and for a local search method between multiple tours, relocation and exchange (edge heuristics) were used. Furthermore, to prevent the drawback of trapping in the local minima, the simulated annealing method is used. Extensive computational experiments were carried out using TSPLIB instances. Among construction algorithms, route first and cluster second algorithms including removing two edges method performed best. In terms of running time, clustering first and routing second algorithms took shorter time on large-scale instances. The simulated annealing could produce better solutions than the descent method, but did not always perform well in terms of average solution. To evaluate the performance of the proposed heuristic methods, their solutions were compared with the optimal solutions obtained using a mixed-integer programming formulation of the problem. For small-scale problems, heuristic solutions were equal to the optimal solution output by CPLEX.

La commande H∞ est de nos jours utilisée pour la régulation de nombreux systèmes. Cette technique de contrôle permet de synthétiser des lois de commande robustes, dans le sens où le comportement du système régulé est peu sensible aux perturbations externes. De plus, la commande H∞ permet de prendre en compte des incertitudes liés au modèle décrivant le système à réguler. Par conséquence, cette technique de contrôle est robuste vis-à-vis des perturbations et des incertitudes de modèle. Afin de synthétiser une loi de commande robuste, les spécifications des performances du système en boucle fermée sont traduites en critères H∞ à partir desquels est formulé un problème d'optimisation. La loi de commande est une solution de ce problème, qui est non convexe dans le cas général. Les deux principales approches pour la résolution de ce problème sont basées sur la reformulation convexe et les méthodes d'optimisations locales, mais ne garantissent pas l'optimalité de la loi de commande vis-à-vis des critères H∞. Cette thèse propose une approche de la commande H∞ par des méthodes d'optimisation globales, rarement considérées jusqu'à présent. Contrairement aux approches classiques, bien qu'au prix d'une complexité algorithmique supérieure, la convergence vers la loi de commande optimale est garantie par les méthodes globales. De plus, les incertitude de modèle sont prises en compte de manière garantie, ce qui n'est pas nécessairement le cas avec les approches convexes et locales. / H∞ control is nowadays used in many applications. This control technique enables to synthesize control laws which are robust with respect to external disturbances. Moreover, it allows to take model uncertainty into account in the synthesis process. As a consequence, H∞ control laws are robust with respect to both external disturbances and model uncertainty. A robust control law is a solution to an optimization problem, formulated from H∞ criteria. These criteria are the mathematical translations of the desired closed loop performance specifications. The two classical approaches to the optimization problem rely on the convex reformulation and local optimization methods. However, such approaches are unable to guarantee the optimality, with respect to the H∞ criteria, of the control law. This thesis proposes to investigate a global optimization approach to H∞ control. Contrary to convex and local approaches, global optimization methods enable to guarantee the optimality of the control, and also to take into account model uncertainty in a reliable way.

Dans cette thèse, nous étudions les solutions des équations Hamilton-Jacobi. Plus précisément, nous comparons la solution de viscosité, obtenue comme limite de solutions de l'équation perturbée par un petit terme de diffusion, et la solution minmax, définie géométriquement à partir d'une fonction génératrice quadratique à l'infini. Dans la littérature, il y a des cas bien connus où les deux coïncident, par exemple lorsque le hamiltonien est convexe ou concave, le minmax pouvant alors être réduit à un min ou un max. Mais les solutions minmax et de viscosité diffèrent en général. Nous construisons des "minmax itérés" en répétant pas à pas la procédure de minmax et démontrons que, quand la taille du pas tend vers zéro, les minmax itérés tendent vers la solution de viscosité. Dans une deuxième partie, nous étudions les lois de conservation en dimension un d'espace par le méthode de "front tracking". Nous montrons que dans le cas où la donnée initiale est convexe, la solution de viscosité et le minmax sont égaux. Et comme application, nous décrivons sur des exemples la manière dont sont construites les singularités de la solution de viscosité. Pour finir, nous montrons que la notion de minmax n'est pas aussi évidente qu'il y paraît.

<p>Whist is one of the most played card games of the world. Though there have been many studies made in the field of game theory, whist is still somewhat of an unchartered territory. In this thesis some methods to obtain an optimal strategy for whist are discussed. </p><p>Whist belongs to a group of games called logical games. For this group there exists algorithms which result in an optimal strategy. Two algorithms where examined. The minmax algorithm and the alphbeta algorithm. these algorithms could be adapted to whist </p><p>It is possible that there are methods that use the properties of the cards better the the former algorithms to get an optimal result. A few such methods will also be discussed. </p><p>The practical result of the theoretical investigation was a game where the adapted algorithms were implemented. </p>

Whist is one of the most played card games of the world. Though there have been many studies made in the field of game theory, whist is still somewhat of an unchartered territory. In this thesis some methods to obtain an optimal strategy for whist are discussed. Whist belongs to a group of games called logical games. For this group there exists algorithms which result in an optimal strategy. Two algorithms where examined. The minmax algorithm and the alphbeta algorithm. these algorithms could be adapted to whist It is possible that there are methods that use the properties of the cards better the the former algorithms to get an optimal result. A few such methods will also be discussed. The practical result of the theoretical investigation was a game where the adapted algorithms were implemented.

Growing attention is being paid to the problem of efficiently designing and operating reverse supply chain systems to handle the return flows of production wastes, packaging, and end-of-life products. Because uncertainty plays a significant role in all fields of decision-making, solution methodologies for determining the strategic infrastructure of reverse production systems under uncertainty are required. This dissertation presents innovative optimization algorithms for designing a robust network infrastructure when uncertainty affects the outcomes of the decisions. In our context, robustness is defined as minimizing the maximum regret under all realization of the uncertain parameters. These new algorithms can be effectively used in designing supply chain network infrastructure when the joint probability distributions of key parameters are unknown. These algorithms only require the information on potential ranges and possible discrete values of uncertain parameters, which often are available in practice. These algorithms extend the state of the art in robust optimization, both in the structure of the problems they address and the size of the formulations. An algorithm for dealing with the problem with correlated uncertain parameters is also presented. Case studies in reverse production system infrastructure design are presented. The approach is generalizable to the robust design of network supply chain systems with reverse production systems as one of their subsystems.

No description available.

Nous étudions plusieurs problèmes de coloration dans les graphes, pour certains avec une composante ludique. La coloration à distance 2 d'un graphe est une coloration de ses sommets telle que deux sommets à distance au plus 2 ont des couleurs différentes. Le L(p; q)-étiquetage est une généralisation de ce problème ou les contraintes à distance 1 et 2 sont différentes. Nous donnons des résultats pour ces deux problèmes dans plusieurs classes de graphes peu denses (ayant un faible degré moyen maximum).Le jeu de coloration sur un graphe est un jeu ou deux joueurs, Alice et Bob, colorent tour à tour un des sommets non coloriés d'un graphe, construisant ainsi une coloration propre partielle de plus en plus étendue de ce graphe. Alice tente d'étendre la coloration à l'ensemble du graphe, et Bob tente de l'en empêcher. Nous travaillons sur un invariant de graphe, le degré minmax, dont l'étude permet de déduire des résultats pour le jeu de coloration via l'étude d'un problème structurel, la (1; k)-décomposition d'un graphe, c'est-à-dire la partition de ses arêtes en une forêt et un sous-graphe de degré inférieur ou égal à k.Nous travaillons enfin sur une variante du jeu de coloration nommée jeu de coloration d'incidences, ou Alice et Bob colorient les incidences d'un graphe, pour lequel nous donnons une stratégie efficace pour Alice.Enfin, tout au long de notre mémoire, nous étudions les liens entre la notion de coloration est celle de marquage. Un marquage est un ordre sur les sommets (ou arêtes, ou incidences...) d'un graphe possédant des caractéristiques utiles pour le colorer. Pour nos différents problèmes, nous questionnons l'utilité ou les limites de l'usage de cette notion. / We study several problems of graph coloring, some of them with a game component.A 2-distance coloring of a graph is a vertex coloring where two vertices at distanceat most two have different colors. A L(p; q)-labeling is a generalisation of the distance-2coloring where constraints are different at distance 1 and 2. We give results for thesetwo problems in several classes of sparse graphs (with a low maximal average degree).The coloring game on a graph is a game where two players, Alice and Bob, taketurns coloring an uncolored vertex of the graph, constructing together a proper partialcoloring of the graph extending as time moves on. Alice try to extend the coloringto the whole graph, and Bob try to prevent her to win. We study a graph invariant,the minmax degree, who has consequences on the coloring game through the notion of(1; k)-decomposition of a graph, which is the partition of its edge set into a forest and asubgraph of degree bounded by k.We finally study a variant of the coloring game named incidence coloring game, whereAlice and Bob are coloring the incidences of a graph, and for which we give an efficientstrategy for Alice.Finally, during our thesis, we study the connections between coloring and marking,which is an order on the vertices of a graph (or its edges, or its incidences) havingproperties usefull for its coloring. For our problems, we try to determine the utility andthe limits of a marking-based approach of coloring problems.

Práce se zabývá určením pravděpodobnostních rozdělení pro stochastické programování, při kterém jsou optimální hodnoty účelové funkce extrémní (minimální nebo maximální). Rozdělení se určuje pomocí heuristických metod, konkrétně pomocí genetických algoritmů, kde celá populace aproximuje hledané rozdělení. První kapitoly popisují obecně matematické a stochastické programování a dále jsou popsány různé heuristické metody a s důrazem na genetické algoritmy. Těžiště práce je v naprogramování daného algoritmu a otestování na úlohách lineárních a kvadratických stochastických modelů.

On étudie l'équation de Hamilton-Jacobi évolutive du premier ordre, couplée avec une donnée initiale lipschitzienne. Le but est de comparer les solutions de viscosité et les solutions variationnelles pour cette équation, deux notions de solutions faibles qui coïncident en dynamique hamiltonienne convexe. Pour travailler dans un cadre pertinent pour les deux types de solutions, on doit d’abord construire une solution variationnelle sans hypothèse de compacité sur la variété ou le hamiltonien étudiés. On retrace dans ce cas la construction historique des solutions variationnelles, en détaillant les propriétés de la famille génératrice obtenue par la méthode des géodésiques brisées. Il en découle des estimées permettant d’obtenir la solution de viscosité à partir de la solution variationnelle par un procédé d’itération. Après avoir vérifié que la solution variationnelle construite coïncide effectivement avec la solution de viscosité pour un Hamiltonien convexe, on caractérise les Hamiltoniens intégrables pour lesquels cette propriété persiste, en étudiant attentivement des exemples élémentaires en dimension 1 et 2. / We study the first order Hamilton-Jacobi equation associated with a Lipschitz initial condition. The purpose of this thesis is to compare two notions of weak solutions for this equation, namely the viscosity solution and the variational solution, that are known to coincide in convex Hamiltonian dynamics. In order to work in a relevant framework for both notions, we first need to build a variational solution without compactness assumption on the manifold or the Hamiltonian. To do so, we follow the historical construction, detailing properties of the generating family obtained via the broken geodesics method. Local estimates allow to prove that the viscosity solution can be obtained from the variational solution via an iterative process. We then check that this construction gives effectively the viscosity solution for a convex Hamiltonian, and characterize the integrable Hamiltonians for which this property persists by carefully studying elementary examples in dimension 1 and 2.