Le problème du sac à dos à plusieurs contraintes est un problème classique de l'optimisation appartenant à la classe des problèmes NP-difficiles. On le retrouve notamment sous la forme de sous-problème de nombreux problèmes d'optimisation combinatoire. Les méthodes classiques de résolution exacte telles que la programmation dynamique ou le branch-and-bound ont été traitées abondamment dans la littérature. Elles présentent n'eanmoins des faiblesses si elles sont utilisées telles quelles, d'où l'idée de faire coopérer ces méthodes en tirant profit de leurs spécificités afin de proposer soit des méthodes heuristiques performantes, soit des méthodes exactes plus efficaces. Les approches heuristiques que nous proposons sont comparées à d'autres heuristiques de la littérature. Notre méthode coopérative est, quant à elle, comparée à un algorithme de branchand- bound. L'ensemble de ces tests numériques ont été menés pour diverses instances plus ou moins difficiles de la littérature ainsi que sur des instances engendrées aléatoirement. Enfin, nous proposons deux techniques pour engendrer des problèmes difficiles. Ces dernières sont basées sur des problèmes en contraintes égalités et sur l'analyse de la transformée en Z du sac à dos.

Le problème de la recherche d'un élément dans un ensemble donne est un des problèmes fondamentaux en informatique non numérique, lie, par exemple, aux bases de données, a la compilation, a l'optimisation combinatoire, etc... Dans cette thèse nous abordons le problème de la recherche dans des ensembles ordonnes et quelques problèmes qui lui sont lies. Une matrice est dite triée si elle possédé une relation d'ordre total sur chaque ligne et chaque colonne. Un cas particulier est l'ensemble des matrices définies par x+y, la somme cartésienne de deux vecteurs tries. Après un tour d'horizon des problèmes de la sélection, de la recherche et du tri sur des ensembles de la forme x=y, nous démontrons des bornes inférieures et introduisons des bornes supérieures pour les problèmes de la recherche et de la sélection. Nous proposons, en outre, plusieurs algorithmes parallèles pour la recherche dans x+y. Ensuite nous montrons comment appliquer ces résultats a la resolution en parallèle du problème de décision du sac-a-dos, ou, étant donnes plusieurs objets et un sac de capacité définie a remplir, on veut décider s'il existe une combinaison des objets qui remplit exactement le sac. Des algorithmes avec une accélération optimale sont introduits pour divers modèles de machines parallèles a mémoire partagée et distribuée. Pour ce problème les approches existantes se ramènent soit a la recherche dans x+y, soit a la traversée d'un espace combinatoire a l'aide de la technique du Branch & Bound. Cette dernière technique est aussi discutée dans ce travail, ou nous présentons un algorithme de Branch & Bound en vue de la resolution de problèmes d'optimisation combinatoire sur la connexion machine. Enfin, toujours dans le domaine de l'optimisation combinatoire, nous étudions le comportement de l'algorithme de recuit simule. Nous prouvons que, malgré la confiance qu'il inspire et sa grande utilisation pour des application

Les problèmes de découpe et de placement sont des problèmes combinatoires. Ils sont classes dans la catégorie des problèmes NP-Complets et admettent de nombreuses applications en industrie, en systèmes multiprocesseurs. Nous proposons dans cette thèse, plusieurs méthodes de résolution exactes et approchées, séquentielles et parallèles du problème de découpe et de placement à deux dimensions.

Ce travail porte sur la résolution exacte d'un problème d'optimisation combinatoire multi-objectif. Nous cherchons d'une part à confirmer l'efficacité de l'algorithme dit en deux phases, et d'autre part à poser une généralisation des procédures de séparation et évaluation, populaires dans le cadre mono-objectif mais presque absentes en multi-objectif. Notre étude s'appuie sur le problème multi-objectif de sac à dos unidimensionnel en variables binaires. Ce dernier est un classique de l'optimisation combinatoire, présent comme sous problème dans de nombreux problèmes d'optimisation. La première partie de nos travaux porte sur un pré-traitement permettant de réduire la taille d'instances de ce problème. Nous mettons en évidence plusieurs propriétés permettant de déterminer a priori une partie de la structure de toutes les solutions efficaces. Nous nous attachons ensuite à décrire une procédure performante de type deux phases pour ce problème, tout d'abord dans le cas bi-objectif. Nous étendons ensuite cette procédure pour des instances ayant trois objectifs ou plus. Les résultats obtenus sont comparés aux meilleurs algorithmes existants pour ce problème et confirment l'efficacité de l'approche en deux phases. La dernière partie de notre travail concerne la généralisation au cas multi-objectif d'une procédure de séparation et évaluation. Nous identifions plusieurs difficultés auxquelles nous répondons en proposant deux nouvelles procédures. Les expérimentations numériques indiquent que ces dernières permettent de résoudre des instances en des temps raisonnables, bien qu'elles n'atteignent pas les performances d'une procédure de type deux phases.

Le conflit entre la demande de services multimédia en multidiffusion à haut débit (MBMS) et les limites en ressources radio demandent une gestion efficace de l'allocation des ressources radio (RRM) dans les réseaux 3G UMTS. À l'opposé des travaux existant dans ce domaine, cette thèse se propose de résoudre le problème de RRM dans les MBMS par une approche d’optimisation combinatoire. Le travail commence par une modélisation formelle du problème cible, désigné comme Flexible Radio Resource Management Model (F2R2M). Une analyse de la complexité et du paysage de recherche est effectuée à partir de ce modèle. Tout d’abord on montre qu'en assouplissant les contraintes de code OVSF, le problème de RRM pour les MBMS peut s'apparenter à un problème de sac à dos à choix multiples (MCKP). Une telle constatation permet de calculer les limites théoriques de la solution en résolvant le MCKP similaire. En outre, l'analyse du paysage montre que les espaces de recherche sont accidentés et constellés d'optima locaux. Sur la base de cette analyse, des algorithmes métaheuristiques sont étudiés pour résoudre le problème. Nous montrons tout d'abord que un Greedy Local Search (GLS) et un recuit simulé (SA) peuvent trouver de meilleures solutions que les approches existantes implémentées dans le système UMTS, mais la multiplicité des optima locaux rend les algorithmes très instables. Un algorithme de recherche tabou (TS) incluant une recherche à voisinage variable (VNS) est aussi développé et comparé aux autres algorithmes (GLS et SA) et aux approches actuelles du système UMTS ; les résultats de la recherche tabou dépassent toutes les autres approches. Enfin les meilleures solutions trouvées par TS sont également comparées avec les solutions théoriques générées par le solveur MCKP. On constate que les meilleures solutions trouvées par TS sont égales ou très proches des solutions optimales théoriques. / The high throughputs supported by the multimedia multicast services (MBMS) and the limited radio resources result in strong requirement for efficient radio resource management (RRM) in UMTS 3G networks. This PhD thesis proposes to solve the MBMS RRM problem as a combinatorial optimization problem. The work starts with a formal modeling of the problem, named as the Flexible Radio Resource Management Model (F2R2M). An in-depth analysis of the problem complexity and the search landscape is done from the model. It is showed that, by relaxing the OVSF code constraints, the MBMS RRM problem can be approximated as a Multiple-Choice Knapsack Problem (MCKP). Such work allows us to compute the theoretical solution bounds by solving the approximated MCKP. Then the fitness landscape analysis shows that the search spaces are rough and reveal several local optimums. Based on the analysis, some metaheuristic algorithms are studied to solve the MBMS RRM problem. We first show that a Greedy Local Search (GLS) and a Simulated Annealing (SA) allow us to find better solutions than the existing approaches implemented in the UMTS system, however the results are instable due to the landscape roughness. Finally we have developed a Tabu Search (TS) mixed with a Variable Neighborhood Search (VNS) algorithm and we have compared it with GLS, SA and UMTS embedded algorithms. Not only the TS outperforms all the other approaches on several scenarios but also, by comparing it with the theoretical solution bounds generated by the MCKP solver, we observe that TS is equal or close to the theoretical optimal solutions.

Dans cette thèse, nous étudions trois types de problèmes stochastiques : les problèmes avec contraintes probabilistes, les problèmes distributionnellement robustes et les problèmes avec recours. Les difficultés des problèmes stochastiques sont essentiellement liées aux problèmes de convexité du domaine des solutions, et du calcul de l’espérance mathématique ou des probabilités qui nécessitent le calcul complexe d’intégrales multiples. A cause de ces difficultés majeures, nous avons résolu les problèmes étudiées à l’aide d’approximations efficaces.Nous avons étudié deux types de problèmes stochastiques avec des contraintes en probabilités, i.e., les problèmes linéaires avec contraintes en probabilité jointes (LLPC) et les problèmes de maximisation de probabilités (MPP). Dans les deux cas, nous avons supposé que les variables aléatoires sont normalement distribués et les vecteurs lignes des matrices aléatoires sont indépendants. Nous avons résolu LLPC, qui est un problème généralement non convexe, à l’aide de deux approximations basée sur les problèmes coniques de second ordre (SOCP). Sous certaines hypothèses faibles, les solutions optimales des deux SOCP sont respectivement les bornes inférieures et supérieures du problème du départ. En ce qui concerne MPP, nous avons étudié une variante du problème du plus court chemin stochastique contraint (SRCSP) qui consiste à maximiser la probabilité de la contrainte de ressources. Pour résoudre ce problème, nous avons proposé un algorithme de Branch and Bound pour calculer la solution optimale. Comme la relaxation linéaire n’est pas convexe, nous avons proposé une approximation convexe efficace. Nous avons par la suite testé nos algorithmes pour tous les problèmes étudiés sur des instances aléatoires. Pour LLPC, notre approche est plus performante que celles de Bonferroni et de Jaganathan. Pour MPP, nos résultats numériques montrent que notre approche est là encore plus performante que l’approximation des contraintes probabilistes individuellement.La deuxième famille de problèmes étudiés est celle relative aux problèmes distributionnellement robustes où une partie seulement de l’information sur les variables aléatoires est connue à savoir les deux premiers moments. Nous avons montré que le problème de sac à dos stochastique (SKP) est un problème semi-défini positif (SDP) après relaxation SDP des contraintes binaires. Bien que ce résultat ne puisse être étendu au cas du problème multi-sac-à-dos (MKP), nous avons proposé deux approximations qui permettent d’obtenir des bornes de bonne qualité pour la plupart des instances testées. Nos résultats numériques montrent que nos approximations sont là encore plus performantes que celles basées sur les inégalités de Bonferroni et celles plus récentes de Zymler. Ces résultats ont aussi montré la robustesse des solutions obtenues face aux fluctuations des distributions de probabilités. Nous avons aussi étudié une variante du problème du plus court chemin stochastique. Nous avons prouvé que ce problème peut se ramener au problème de plus court chemin déterministe sous certaine hypothèses. Pour résoudre ce problème, nous avons proposé une méthode de B&B où les bornes inférieures sont calculées à l’aide de la méthode du gradient projeté stochastique. Des résultats numériques ont montré l’efficacité de notre approche. Enfin, l’ensemble des méthodes que nous avons proposées dans cette thèse peuvent s’appliquer à une large famille de problèmes d’optimisation stochastique avec variables entières. / In this thesis, we studied three types of stochastic problems: chance constrained problems, distributionally robust problems as well as the simple recourse problems. For the stochastic programming problems, there are two main difficulties. One is that feasible sets of stochastic problems is not convex in general. The other main challenge arises from the need to calculate conditional expectation or probability both of which are involving multi-dimensional integrations. Due to the two major difficulties, for all three studied problems, we solved them with approximation approaches.We first study two types of chance constrained problems: linear program with joint chance constraints problem (LPPC) as well as maximum probability problem (MPP). For both problems, we assume that the random matrix is normally distributed and its vector rows are independent. We first dealt with LPPC which is generally not convex. We approximate it with two second-order cone programming (SOCP) problems. Furthermore under mild conditions, the optimal values of the two SOCP problems are a lower and upper bounds of the original problem respectively. For the second problem, we studied a variant of stochastic resource constrained shortest path problem (called SRCSP for short), which is to maximize probability of resource constraints. To solve the problem, we proposed to use a branch-and-bound framework to come up with the optimal solution. As its corresponding linear relaxation is generally not convex, we give a convex approximation. Finally, numerical tests on the random instances were conducted for both problems. With respect to LPPC, the numerical results showed that the approach we proposed outperforms Bonferroni and Jagannathan approximations. While for the MPP, the numerical results on generated instances substantiated that the convex approximation outperforms the individual approximation method.Then we study a distributionally robust stochastic quadratic knapsack problems, where we only know part of information about the random variables, such as its first and second moments. We proved that the single knapsack problem (SKP) is a semedefinite problem (SDP) after applying the SDP relaxation scheme to the binary constraints. Despite the fact that it is not the case for the multidimensional knapsack problem (MKP), two good approximations of the relaxed version of the problem are provided which obtain upper and lower bounds that appear numerically close to each other for a range of problem instances. Our numerical experiments also indicated that our proposed lower bounding approximation outperforms the approximations that are based on Bonferroni's inequality and the work by Zymler et al.. Besides, an extensive set of experiments were conducted to illustrate how the conservativeness of the robust solutions does pay off in terms of ensuring the chance constraint is satisfied (or nearly satisfied) under a wide range of distribution fluctuations. Moreover, our approach can be applied to a large number of stochastic optimization problems with binary variables.Finally, a stochastic version of the shortest path problem is studied. We proved that in some cases the stochastic shortest path problem can be greatly simplified by reformulating it as the classic shortest path problem, which can be solved in polynomial time. To solve the general problem, we proposed to use a branch-and-bound framework to search the set of feasible paths. Lower bounds are obtained by solving the corresponding linear relaxation which in turn is done using a Stochastic Projected Gradient algorithm involving an active set method. Meanwhile, numerical examples were conducted to illustrate the effectiveness of the obtained algorithm. Concerning the resolution of the continuous relaxation, our Stochastic Projected Gradient algorithm clearly outperforms Matlab optimization toolbox on large graphs.

La conception de réseaux est un riche sous-domaine de l'optimisation combinatoire ayant de nombreuses applications pratiques. Du point de vue méthodologique, la plupart des problèmes de cette classe sont notoirement difficiles en raison de leur nature combinatoire et de l'interdépendance des décisions qu'ils impliquent. Ce mémoire aborde deux problèmes de conception de réseaux dont les structures respectives posent des défis bien distincts. Tout d'abord, nous examinons un problème déterministe dans lequel un client doit acquérir au prix minimum un certain nombre d'unités d'un produit auprès d'un ensemble de fournisseurs proposant différents coûts fixes et unitaires, et dont les stocks sont limités. Ensuite, nous étudions un problème probabiliste dans lequel une entreprise entrant sur un marché existant cherche, en ouvrant un certain nombre d'installations parmi un ensemble de sites disponibles, à maximiser sa part espérée d'un marché composé de clients maximisant une fonction d'utilité aléatoire. Ces deux problèmes, soit le problème de transport à coût fixe à un puits et le problème d'emplacement d'installations compétitif basé sur les choix, sont étroitement liés au problème du sac à dos et au problème de couverture maximale, respectivement. Nous introduisons de nouvelles reformulations prenant avantage de ces connexions avec des problèmes classiques d'optimisation combinatoire. Dans les deux cas, nous exploitons ces reformulations pour démontrer de nouvelles propriétés théoriques et développer des méthodes de résolution efficaces. Notre nouvel algorithme pour le problème de transport à coûts fixes à un puits domine les meilleurs algorithmes de la littérature, réduisant le temps de résolution des instances de grande taille jusqu'à quatre ordres de grandeur. Une autre contribution notable de ce mémoire est la démonstration que la fonction objectif du problème d'emplacement d'installations compétitif basé sur les choix est sous-modulaire sous n'importe quel modèle de maximisation d’utilité aléatoire. Notre méthode de résolution basée sur la simulation exploite cette propriété et améliore l'état de l'art pour plusieurs groupes d'instances. / Network design is a rich subfield of combinatorial optimization with wide-ranging real-life applications. From a methodological standpoint, most problems in this class are notoriously difficult due to their combinatorial nature and the interdependence of the decisions they involve. This thesis addresses two network design problems whose respective structures pose very distinct challenges. First, we consider a deterministic problem in which a customer must acquire at the minimum price a number of units of a product from a set of vendors offering different fixed and unit costs and whose supply is limited. Second, we study a probabilistic problem in which a firm entering an existing market seeks, by opening a number of facilities from a set of available locations, to maximize its expected share in a market composed of random utility-maximizing customers. These two problems, namely the single-sink fixed-charge-transportation problem and the choice-based competitive facility location problem, are closely related to the knapsack problem and the maximum covering problem, respectively. We introduce novel model reformulations that leverage these connections to classical combinatorial optimization problems. In both cases, we exploit these reformulations to prove new theoretical properties and to develop efficient solution methods. Our novel algorithm for the single-sink fixed-charge-transportation problem dominates the state-of-the-art methods from the literature, reducing the solving time of large instances by up to four orders of magnitude. Another notable contribution of this thesis is the demonstration that the objective function of the choice-based competitive facility location problem is submodular under any random utility maximization model. Our simulation-based method exploits this property and achieves state-of-the-art results for several groups of instances.