This thesis deals with the Travelling salesman problem with time windows. The problem is that the travelling salesman must pass through each defined location exactly once and finally return to the original place for the lowest possible price. The time windows in this problem are that each place can only be visited in a given time range, or it can happen that in a certain period of time there will be no path between some places. The thesis deals with an overview of this problem and problems similar to it. It also deals with the description of various methods by which this problem can be solved. As part of this thesis, an application in the Python programming language was also created, which is used to test selected methods for finding solutions. Finally, the given experiments are evaluated and the effectiveness of the given strategies is compared.

Cette thèse est consacrée à une étude approfondie du Rank Pricing Problem (RPP) et de deux généralisations. Le RPP est un problème d'optimisation combinatoire qui vise à fixer le prix des produits d'une entreprise afin de maximiser son profit. Elle concerne les clients à la demande, c'est-à-dire les clients qui sont intéressés par plusieurs produits de l'entreprise, mais qui n'ont l'intention d'en acheter qu'un. Les clients disposent d'un budget fixe et classent les produits qui les intéressent du "meilleur" au "pire". Lorsque l'entreprise fixe les prix, chaque client achètera son produit préféré parmi ceux qu'il peut se permettre. Dans le RPP, nous supposons que les produits sont offerts en quantité illimitée, ce qui convient si l'on considère que l'entreprise a suffisamment de produits pour satisfaire la demande, ou lorsque les produits peuvent être fabriqués rapidement avec un coût négligeable (par exemple, les biens numériques).Cette thèse se compose de quatre chapitres. Le premier est un chapitre d'introduction au problème et aux concepts mathématiques présents dans la thèse, tandis que les trois chapitres suivants se concentrent sur chacun des problèmes étudiés :le RPP et deux généralisations. Ainsi, le troisième chapitre est consacré à l'étude du Rank Pricing Problem with Ties (RPPT). Dans cette extension du problème, nous supposons que les clients peuvent exprimer leur indifférence entre les produits qui les intéressent au moyen de liens dans leur liste de préférences. Enfin, le dernier chapitre de la thèse comprend l'étude du Capacitated Rank Pricing Problem (CRPP) avec envie. Dans cette extension, nous avons supposé des prix de réserve pour les clients qui reflètent ce qu'ils sont prêts à payer pour chaque produit, plutôt qu'un budget unique par consommateur. Cependant, la principale différence est que dans le cas du CRPP, l'entreprise dispose d'un nombre limité de produits et peut ne pas être en mesure de satisfaire la demande de tous les clients. L'objectif de la thèse est d'obtenir des formulations linéaires en nombres entiers mixtes pour les trois problèmes étudiés, et de les comparer sur le plan théorique et/ou computationnel. À cette fin, la méthodologie utilisée est basée sur la proposition de variables de décision et de contraintes appropriées qui modélisent le problème. L'objectif suivant est l'amélioration de ces formulations au moyen d'inégalités valides qui réduisent l’ensemble admissible de la relaxation du problème et permettent d'obtenir une meilleure borne de la relaxation linéaire. Et enfin, un troisième objectif est la proposition d'algorithmes de résolution pour chacun de ces modèles, et leur comparaison ultérieure au moyen d'études computationnelles et de résolution au moyen de logiciels d'optimisation commerciaux. / This doctorate is entirely devoted to an in-depth study of the Rank Pricing Problem (RPP) and two generalizations. The RPP is a combinatorial optimization problem which aims at setting the prices of a series of products of a company to maximize its revenue. This problem is specified by a set of unit-demand customers, that is, customers interested in a subset of the products offered by the company which intend to buy at most one of them. To do so, they count on a fixed budget, and they rank the products of their interest from the “best” to the “worst”. Once the prices are established by the company, they will purchase their highest-ranked product among the ones they can afford. In the RPP, it is assumed an unlimited supply of products, which is consistent with a company having enough copies of a product to satisfy the demand, or with a setting where the products can be produced quickly at negligible cost (e.g. digital goods). This dissertation consists of four chapters. The first chapter introduces the RPP problem and the mathematical concepts present in the work, whereas each of the next three chapters tackles the resolution of each of the problems of study: the RPP and two generalizations. Thus, Chapter 3 is dedicated to the Rank Pricing Problem with Ties (RPPT), an extension of the RPP where we consider that customers can express indifference among products in their preference list. And the last chapter of the thesis is devoted to a generalization of the problem that we have named the Capacitated Rank Pricing Problem (CRPP) with envy. For this generalization, we have considered reservation prices of customers for the different products that reflect their willingness to pay, instead of a single budget per customer. However, the main difference is that, in the CRPP, the company has a limited supply of products and might not be able to satisfy all the customers’ requests. This is a realistic assumption that we can find in many companies.The aim of this thesis is the proposal of mixed-integer linear formulations for the three problems of study, and their theoretical and/or computational comparison. The methodology used is based on the introduction of decision variables and adequate restrictions to model the problems. Another objective consists in strengthening the formulations by means of valid inequalities that reduce the feasible region of the relaxed problem and allow us to obtain better linear relaxation bounds. Finally, a third goal is to derive resolution algorithms for each of these models and compare them computationally, using commercial solvers. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Cette thèse traite de la détection et de la ré-identification de personnes dans un environnement instrumenté par un réseau de caméras à champ disjoint. Elle est à la confluence des communautés Recherche Opérationnelle et Vision car elle s'appuie sur des techniques d'optimisation combinatoire pour formaliser de nouvelles modalités de vision par ordinateur. Dans ce contexte, un détecteur visuel de personnes, basé sur la programmation linéaire en nombres entiers, est tout d'abord proposé. Son originalité est de prendre en compte le coût de traitement et non uniquement les performances de détection. Ce détecteur est évalué et comparé aux détecteurs de la littérature les plus performants. Ces expérimentations menées sur deux bases de données publiques mettent clairement en évidence l'intérêt de notre détecteur en terme de coût de traitement avec garantie de performance de détection. La seconde partie de la thèse porte sur la modalité de ré-identification de personnes. L'originalité de notre approche, dénommée D-NCR (pour Directed Network Consistent Re-identification), est de prendre explicitement en compte les temps minimum de transit des personnes dans le réseau de caméras et sa topologie pour améliorer la performance de la ré-identification. On montre que ce problème s'apparente à une recherche de chemins disjoints particuliers à profit maximum dans un graphe orienté. Un programme linéaire en nombres entiers est proposé pour sa modélisation et résolution. Les évaluations réalisées sur une base publique d'images sont prometteuses et montrent le potentiel de cette approche. / This thesis deals with people detection and re-identification in an environment instrumented by a network of disjoint-field cameras. It stands at the confluence of the Operational Research and Computer Vision communities as combinatorial optimization techniques are used to formalize new computer vision methods. In this context, a people visual detector, based on mixed-integer programming, is first propose that simultaneously take computation time and detection performances into account. This detector is evaluated and compared to the best detectors of the literature. These experiments, conducted on two public databases, clearly demonstrate the interest of our detector in terms of processing time with detection performance guarantee. The second part of the thesis deals with people re-identification. Our novel approach, called D-NCR (Directed Network Consistent Re-identification), explicitly takes minimum transit times in the camera network into account, as well as the network topology, in order to improve the re-identification performance. This problem is similar to the determination of particular maximum-profitable independent paths in an oriented graph. A mixed-integer program is proposed to model and solve this problem. The experiments made on a public dataset sound promising and tend to prove the potential of the approach.

Étant donné G = (V, E) un graphe non orienté connexe et un entier positif β (n), où n est le nombrede sommets de G, le problème du séparateur (VSP) consiste à trouver une partition de V en troisclasses A, B et C de sorte qu'il n'y a pas d'arêtes entre A et B, max {| A |, | B |} est inférieur ou égal àβ (n) et | C | est minimum. Dans cette thèse, nous considérons une modélisation du problème sous laforme d'un programme linéaire en nombres entiers. Nous décrivons certaines inégalités valides et etdéveloppons des algorithmes basés sur un schéma de voisinage.Nous étudions également le problème du st-séparateur connexe. Soient s et t deux sommets de Vnon adjacents. Un st-séparateur connexe dans le graphe G est un sous-ensemble S de V \ {s, t} quiinduit un sous-graphe connexe et dont la suppression déconnecte s de t. Il s'agit de déterminer un stséparateur de cardinalité minimum. Nous proposons trois formulations pour ce problème et donnonsdes inégalités valides du polyèdre associé à ce problème. Nous présentons aussi une heuristiqueefficace pour résoudre ce problème. / Given G=(V,E) a connected undirected graph and a positive integer β(n), where n is number ofvertices, the vertex separator problem (VSP) is to find a partition of V into three classes A,B and Csuch that there is no edge between A and B, max{|A|,|B|}less than or equal β(n), and |C| isminimum. In this thesis, we consider aninteger programming formulation for this problem. Wedescribe some valid inequalties and using these results to develop algorithms based onneighborhood scheme.We also study st-connected vertex separator problem. Let s and tbe two disjoint vertices of V, notadjacent. A st-connected separator in the graph G is a subset S of V\{s,t} such that there are no morepaths between sand tin G[G\S] and the graph G[S] is connected . The st-connected vertex speratorproblem consists in finding such subset with minimum cardinality. We propose three formulationsfor this problem and give some valid inequalities for the polyhedron associated with this problem.We develop also an efficient heuristic to solve this problem.

In this thesis we study some storage loading problems motivated from several practical contexts, under different types of uncertainty on the items’ data. To have robust stacking solutions against the data uncertainty, we apply the concepts of strict and adjustable robustness. We first give complexity results for various storage loading problems with stacking constraints, and point out some interesting settings in which the adjustable robust problems can be solved more efficiently than the strict ones. Then we propose different solution algorithms for the robust storage loading problems, and figure out which algorithm performs best for which data setting. We also propose a robust optimization framework dealing with storage loading problems under stochastic uncertainty. In this framework, we offer several rule-based ways of scenario generation to derive different uncertainty sets, and analyze the trade-off between cost and robustness of the robust stacking solutions. Additionally, we introduce a novel approach in dealing with stability issues of stacking configurations. Our key idea is to impose a limited payload on each item depending on its weight. We then study a storage loading problem with the interaction of stacking and payload constraints, as well as uncertainty on the weights of items, and propose different solution approaches for the robust problems.

Cette thèse s'inscrit dans le domaine de l'optimisation combinatoire. Elle utilise l'approche polyèdrale pour résoudre des problèmes combinatoires qui se posent dans le contexte des réseaux de télécommunications. Nous introduisons et étudions le problème de synthèse de réseaux à composantes connexes unicycliques. Après avoir rappelé que le problème est facile à résoudre en absence d'autres contraintes, nous étudions de nouvelles variantes en intégrant de nouvelles contraintes techniques. Nous commençons par une contrainte portant sur la taille des cycles. Nous souhaitons interdire tous les cycles contenant au plus $p$ sommets. Le problème est alors NP-Difficile. Des inégalités valides sont alors proposées pour ce problème. On montre sous des conditions bien précises que ces inégalités peuvent être des facettes. Plusieurs algorithmes polynomiaux ont été proposés pour la séparation des inégalités valides. Ces algorithme sont mis en oeuvre et des résultats numériques sont donnés. Nous nous focalisons par la suite sur un nouveau problème dit de Steiner consistant à partitionner un réseau en composantes unicycliques tout en imposant que certains sommets soient sur les cycles. On montre alors que ce problème est facile au sens de la complexité algorithmique en proposant un algorithme polynomial et une formulation étendue du problème. On présente également une description partielle de l'enveloppe convexe des vecteurs d'incidence de ces réseaux. La séparation des inégalités est également étudiée. Nous proposons notamment une généralisation de l'algorithme de Padberg-Rao pour séparer les inégalités Blossom. D'autres contraintes techniques sont prises en compte : contraintes de degrés, contrainte sur le nombre de composantes connexes, appartenance de certains sommets à une même composante connexe et enfin la séparation de certains sommets qui doivent être sur des composantes différentes. Enfin, nous faisons une étude spectrale de deux classes spécifiques de graphes unicycliques. / In this thesis, we use the polyhedral approach to solve combinatorial problems in telecommunications context. First, we introduce the problem of network design with unicyclic connected components. We recall that without other constraints, our problem is easy to solve, and we propose a study with new technical constraints. We start our study by adding constraints on the size of cycles. We aim to obtain unicyclic components such that the size of each cycle is not lower than a certain p. This problem is NP-Hard. We describe some valid inequalities for the design of unicyclic graphs with girth constraints. The faces induced by these valid inequalities are also studied. Some of them can be separated in polynomial time. A cutting plane algorithm based on these inequalities is implemented to solve the problem. Furthermore, we focus on a Steiner type problem, which consists in partitioning the graph to unicyclic components, such that some given vertices belong to a cycle. We prove then that our problem is easy to solve, and we propose an exact extended formulation and a partial description of the convex hull of the incidence vectors of our Steiner network problem. Polynomial time separation algorithms are described. One of them is a generalization of the Padberg&Rao algorithm to separate blossom inequalities. Other technical constraints are proposed such as degree constraints, a bound of the number of unicyclic components, constraints related to whether some given pairs of vertices belong to the same component or to different components. Finally, we study the spectra of two specified classes of unicyclic graphs.

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.

京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第18621号 / 情博第545号 / 新制||情||96(附属図書館) / 31521 / 京都大学大学院情報学研究科数理工学専攻 / (主査)教授 永持 仁, 教授 太田 快人, 教授 髙橋 豊 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

Multi-Armed Bandits (MAB) constitute the most fundamental model for sequential decision making problems with an exploration vs. exploitation trade-off. In such problems, the decision maker selects an arm in each round and observes a realization of the corresponding unknown reward distribution. Each decision is based on past decisions and observed rewards. The objective is to maximize the expected cumulative reward over some time horizon by balancing exploitation (arms with higher observed rewards should be selectedoften) and exploration (all arms should be explored to learn their average rewards). Equivalently, the performanceof a decision rule or algorithm can be measured through its expected regret, defined as the gap betweenthe expected reward achieved by the algorithm and that achieved by an oracle algorithm always selecting the bestarm. This thesis investigates stochastic and adversarial combinatorial MAB problems, where each arm is a collection of several basic actions taken from a set of $d$ elements, in a way that the set of arms has a certain combinatorial structure. Examples of such sets include the set of fixed-size subsets, matchings, spanning trees, paths, etc. These problems are specific forms of online linear optimization, where the decision space is a subset of $d$-dimensional hypercube.Due to the combinatorial nature, the number of arms generically grows exponentially with $d$. Hence, treating arms as independent and applying classical sequential arm selection policies would yield a prohibitive regret. It may then be crucial to exploit the combinatorial structure of the problem to design efficient arm selection algorithms.As the first contribution of this thesis, in Chapter 3 we investigate combinatorial MABs in the stochastic setting and with Bernoulli rewards. We derive asymptotic (i.e., when the time horizon grows large) lower bounds on the regret of any algorithm under bandit and semi-bandit feedback. The proposed lower bounds are problem-specific and tight in the sense that there exists an algorithm that achieves these regret bounds. Our derivation leverages some theoretical results in adaptive control of Markov chains. Under semi-bandit feedback, we further discuss the scaling of the proposed lower bound with the dimension of the underlying combinatorial structure. For the case of semi-bandit feedback, we propose ESCB, an algorithm that efficiently exploits the structure of the problem and provide a finite-time analysis of its regret. ESCB has better performance guarantees than existing algorithms, and significantly outperforms these algorithms in practice. In the fourth chapter, we consider stochastic combinatorial MAB problems where the underlying combinatorial structure is a matroid. Specializing the results of Chapter 3 to matroids, we provide explicit regret lower bounds for this class of problems. For the case of semi-bandit feedback, we propose KL-OSM, a computationally efficient greedy-based algorithm that exploits the matroid structure. Through a finite-time analysis, we prove that the regret upper bound of KL-OSM matches the proposed lower bound, thus making it the first asymptotically optimal algorithm for this class of problems. Numerical experiments validate that KL-OSM outperforms state-of-the-art algorithms in practice, as well.In the fifth chapter, we investigate the online shortest-path routing problem which is an instance of combinatorial MABs with geometric rewards. We consider and compare three different types of online routing policies, depending (i) on where routing decisions are taken (at the source or at each node), and (ii) on the received feedback (semi-bandit or bandit). For each case, we derive the asymptotic regret lower bound. These bounds help us to understand the performance improvements we can expect when (i) taking routing decisions at each hop rather than at the source only, and (ii) observing per-link delays rather than end-to-end path delays. In particular, we show that (i) is of no use while (ii) can have a spectacular impact.For source routing under semi-bandit feedback, we then propose two algorithms with a trade-off betweencomputational complexity and performance. The regret upper bounds of these algorithms improve over those ofthe existing algorithms, and they significantly outperform state-of-the-art algorithms in numerical experiments. Finally, we discuss combinatorial MABs in the adversarial setting and under bandit feedback. We concentrate on the case where arms have the same number of basic actions but are otherwise arbitrary. We propose CombEXP, an algorithm that has the same regret scaling as state-of-the-art algorithms. Furthermore, we show that CombEXP admits lower computational complexity for some combinatorial problems. / <p>QC 20160201</p>

Cut problems on graphs are a well-known and intensively studied class of optimization problems. In this thesis, we study the maximum cut problem, the maximum bond problem, and the minimum multicut problem through their associated polyhedra, i.e., the cut polytope, the bond polytope, and the multicut dominant, respectively. Continuing the research on the maximum cut problem and the cut polytope, we present a linear description for cut polytopes of K_{3,3}-minor-free graphs as well as an algorithm solving the maximum cut problem on these graphs in the same running time as planar maximum cut. Moreover, we give a complete characterization of simple and simplicial cut polytopes. Considering the maximum cut problem from an algorithmic point of view, we propose an FPT-algorithm for the maximum cut problem parameterized by the crossing number. We start the structural study of the bond polytope by investigating its basic properties and the effect of graph operations on the bond polytope and its facet-defining inequalities. After presenting a linear-time reduction of the maximum bond problem to the maximum bond problem on 3-connected graphs, we discuss valid and facet defining inequalities arising from edges and cycles. These inequalities yield a complete linear description for bond polytopes of 3-connected planar (K_5-e)-minor-free graphs. This polytopal result is mirrored algorithmically by proposing a linear-time algorithm for the maximum bond problem on (K_5-e)-minor-free graphs. Finally, we start the structural study of the multicut dominant. We investigate basic properties, which gives rise to lifting and projection results for the multicut dominant. Then, we study the effect of graph operations on the multicut dominant and its facet-defining inequalities. Moreover, we present facet-defining inequalities supported on stars, trees, and cycles as well as separation algorithms for the former two classes of inequalities.