We have considered the bilevel programming problem in the case where the lower-level problem admits more than one optimal solution. It is well-known in the literature that in such a situation, the problem is ill-posed from the view point of scalar objective optimization. Thus the optimistic and pessimistic approaches have been suggested earlier in the literature to deal with it in this case. In the thesis, we have developed a unified approach to derive necessary optimality conditions for both the optimistic and pessimistic bilevel programs, which is based on advanced tools from variational analysis. We have obtained various constraint qualifications and stationarity conditions depending on some constructive representations of the solution set-valued mapping of the follower’s problem. In the auxiliary developments, we have provided rules for the generalized differentiation and robust Lipschitzian properties for the lower-level solution setvalued map, which are of a fundamental interest for other areas of nonlinear and nonsmooth optimization. Some of the results of the aforementioned theory have then been applied to derive stationarity conditions for some well-known transportation problems having the bilevel structure.

Le problème de tarification qui nous intéresse ici consiste à maximiser le revenu généré par les usagers d'un réseau de transport. Pour se rendre à leurs destinations, les usagers font un choix de route et utilisent des arcs sur lesquels nous imposons des tarifs. Chaque route est caractérisée (aux yeux de l'usager) par sa "désutilité", une mesure de longueur généralisée tenant compte à la fois des tarifs et des autres coûts associés à son utilisation. Ce problème a surtout été abordé sous une modélisation déterministe de la demande selon laquelle seules des routes de désutilité minimale se voient attribuer une mesure positive de flot. Le modèle déterministe se prête bien à une résolution globale, mais pèche par manque de réalisme. Nous considérons ici une extension probabiliste de ce modèle, selon laquelle les usagers d'un réseau sont alloués aux routes d'après un modèle de choix discret logit. Bien que le problème de tarification qui en résulte est non linéaire et non convexe, il conserve néanmoins une forte composante combinatoire que nous exploitons à des fins algorithmiques. Notre contribution se répartit en trois articles. Dans le premier, nous abordons le problème d'un point de vue théorique pour le cas avec une paire origine-destination. Nous développons une analyse de premier ordre qui exploite les propriétés analytiques de l'affectation logit et démontrons la validité de règles de simplification de la topologie du réseau qui permettent de réduire la dimension du problème sans en modifier la solution. Nous établissons ensuite l'unimodalité du problème pour une vaste gamme de topologies et nous généralisons certains de nos résultats au problème de la tarification d'une ligne de produits. Dans le deuxième article, nous abordons le problème d'un point de vue numérique pour le cas avec plusieurs paires origine-destination. Nous développons des algorithmes qui exploitent l'information locale et la parenté des formulations probabilistes et déterministes. Un des résultats de notre analyse est l'obtention de bornes sur l'erreur commise par les modèles combinatoires dans l'approximation du revenu logit. Nos essais numériques montrent qu'une approximation combinatoire rudimentaire permet souvent d'identifier des solutions quasi-optimales. Dans le troisième article, nous considérons l'extension du problème à une demande hétérogène. L'affectation de la demande y est donnée par un modèle de choix discret logit mixte où la sensibilité au prix d'un usager est aléatoire. Sous cette modélisation, l'expression du revenu n'est pas analytique et ne peut être évaluée de façon exacte. Cependant, nous démontrons que l'utilisation d'approximations non linéaires et combinatoires permet d'identifier des solutions quasi-optimales. Finalement, nous en profitons pour illustrer la richesse du modèle, par le biais d'une interprétation économique, et examinons plus particulièrement la contribution au revenu des différents groupes d'usagers. / The network pricing problem consists in finding tolls to set on a subset of a network's arcs, so to maximize a revenue expression. A fixed demand of commuters, going from their origins to their destinations, is assumed. Each commuter chooses a path of minimal "disutility", a measure of discomfort associated with the use of a path and which takes into account fixed costs and tolls. A deterministic modelling of commuter behaviour is mostly found in the literature, according to which positive flow is only assigned to \og shortest\fg\: paths. Even though the determinist pricing model is amenable to global optimization by the use of enumeration techniques, it has often been criticized for its lack of realism. In this thesis, we consider a probabilistic extension of this model involving a logit dicrete choice model. This more realistic model is non-linear and non-concave, but still possesses strong combinatorial features. Our analysis spans three separate articles. In the first we tackle the problem from a theoretical perspective for the case of a single origin-destination pair and develop a first order analysis that exploits the logit assignment analytical properties. We show the validity of simplification rules to the network topology which yield a reduction in the problem dimensionality. This enables us to establish the problem's unimodality for a wide class of topologies. We also establish a parallel with the product-line pricing problem, for which we generalize some of our results. In our second article, we address the problem from a numerical point of view for the case where multiple origin-destination pairs are present. We work out algorithms that exploit both local information and the pricing problem specific combinatorial features. We provide theoretical results which put in perspective the deterministic and probabilistic models, as well as numerical evidence according to which a very simple combinatorial approximation can lead to the best solutions. Also, our experiments clearly indicate that under any reasonable setting, the logit pricing problem is much smoother, and admits less optima then its deterministic counterpart. The third article is concerned with an extension to an heterogeneous demand resulting from a mixed-logit discrete choice model. Commuter price sensitivity is assumed random and the corresponding revenue expression admits no closed form expression. We devise nonlinear and combinatorial approximation schemes for its evaluation and optimization, which allow us to obtain quasi-optimal solutions. Numerical experiments here indicate that the most realistic model yields the best solution, independently of how well the model can actually be solved. We finally illustrate how the output of the model can be used for economic purposes by evaluating the contributions to the revenue of various commuter groups.

There are many real cases where a company needs to determine the price of its products so as to maximise its revenue or profit.<p>To do so, the company must consider customers' reactions to these prices, as they may refuse to buy a given product or service if its price is too high. This is commonly known in literature as a pricing problem.<p>This class of problems, which is typically bilevel, was first studied in the 1990s and is NP-hard, although polynomial algorithms do exist for some particular cases. Many questions are still open on this subject.<p><p>The aim of this thesis is to investigate mathematical properties of pricing problems, in order to find structural properties, formulations and solution methods that are as efficient as possible. In particular, we focus our attention on pricing problems over a network. In this framework, an authority owns a subset of arcs and imposes tolls on them, in an attempt to maximise his/her revenue, while users travel on the network, seeking for their minimum cost path.<p><p>First, we provide a detailed review of the state of the art on bilevel pricing problems. <p>Then, we consider a particular case where the authority is using an unit toll scheme on his/her subset of arcs, imposing either the same toll on all of them, or a toll proportional to a given parameter particular to each arc (for instance a per kilometre toll). We show that if tolls are all equal then the complexity of the problem is polynomial, whereas in case of proportional tolls it is pseudo-polynomial.<p>We then address a robust approach taking into account uncertainty on parameters. We solve some polynomial cases of the pricing problem where uncertainty is considered using an interval representation.<p><p>Finally, we focus on another particular case where toll arcs are connected such that they constitute a path, as occurs on highways. We develop a Dantzig-Wolfe reformulation and present a Branch-and-Cut-and-Price algorithm to solve it. Several improvements are proposed, both for the column generation algorithm used to solve the linear relaxation and for the branching part used to find integer solutions. Numerical results are also presented to highlight the efficiency of the proposed strategies. This problem is proved to be APX-hard and a theoretical comparison between our model and another one from the literature is carried out. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

We have considered the bilevel programming problem in the case where the lower-level problem admits more than one optimal solution. It is well-known in the literature that in such a situation, the problem is ill-posed from the view point of scalar objective optimization. Thus the optimistic and pessimistic approaches have been suggested earlier in the literature to deal with it in this case. In the thesis, we have developed a unified approach to derive necessary optimality conditions for both the optimistic and pessimistic bilevel programs, which is based on advanced tools from variational analysis. We have obtained various constraint qualifications and stationarity conditions depending on some constructive representations of the solution set-valued mapping of the follower’s problem. In the auxiliary developments, we have provided rules for the generalized differentiation and robust Lipschitzian properties for the lower-level solution setvalued map, which are of a fundamental interest for other areas of nonlinear and nonsmooth optimization. Some of the results of the aforementioned theory have then been applied to derive stationarity conditions for some well-known transportation problems having the bilevel structure.

In this thesis, we derive necessary optimality conditions for bilevel programming problems (BPPs for short) in Banach spaces. This rather abstract setting reflects our desire to characterize the local optimal solutions of hierarchical optimization problems in function spaces arising from several applications. Since our considerations are based on the tools of variational analysis introduced by Boris Mordukhovich, we study related properties of pointwise defined sets in function spaces. The presence of sequential normal compactness for such sets in Lebesgue and Sobolev spaces as well as the variational geometry of decomposable sets in Lebesgue spaces is discussed. Afterwards, we investigate mathematical problems with complementarity constraints (MPCCs for short) in Banach spaces which are closely related to BPPs. We introduce reasonable stationarity concepts and constraint qualifications which can be used to handle MPCCs. The relations between the mentioned stationarity notions are studied in the setting where the underlying complementarity cone is polyhedric. The results are applied to the situations where the complementarity cone equals the nonnegative cone in a Lebesgue space or is polyhedral. Next, we use the three main approaches of transforming a BPP into a single-level program (namely the presence of a unique lower level solution, the KKT approach, and the optimal value approach) to derive necessary optimality conditions for BPPs. Furthermore, we comment on the relation between the original BPP and the respective surrogate problem. We apply our findings to formulate necessary optimality conditions for three different classes of BPPs. First, we study a BPP with semidefinite lower level problem possessing a unique solution. Afterwards, we deal with bilevel optimal control problems with dynamical systems of ordinary differential equations at both decision levels. Finally, an optimal control problem of ordinary or partial differential equations with implicitly given pointwise state constraints is investigated.

This thesis presents the mixed integer bilevel programming problems where some optimality conditions and solution algorithms are derived. Bilevel programming problems are optimization problems which are partly constrained by another optimization problem. The theoretical part of this dissertation is mainly based on the investigation of optimality conditions of mixed integer bilevel program. Taking into account both approaches (optimistic and pessimistic) which have been developed in the literature to deal with this type of problem, we derive some conditions for the existence of solutions. After that, we are able to discuss local optimality conditions using tools of variational analysis for each different approach. Moreover, bilevel optimization problems with semidefinite programming in the lower level are considered in order to formulate more optimality conditions for the mixed integer bilevel program. We end the thesis by developing some algorithms based on the theory presented

Cette thèse est composée de deux parties, chacune portant sur un sous-domaine de l'optimisation combinatoire a priori distant de l'autre. Le premier thème de recherche abordé est la programmation biniveau stochastique. Se cachent derrière ce terme deux sujets de recherche relativement peu étudiés conjointement, à savoir d'un côté la programmation stochastique, et de l'autre la programmation biniveau. La programmation mathématique (PM) regroupe un ensemble de méthodes de modélisation et de résolution, pouvant être utilisées pour traiter des problèmes pratiques que se posent des décideurs. La programmation stochastique et la programmation biniveau sont deux sous-domaines de la PM, permettant chacun de modéliser un aspect particulier de ces problèmes pratiques. Nous élaborons un modèle mathématique issu d'un problème appliqué, où les aspects biniveau et stochastique sont tous deux sollicités, puis procédons à une série de transformations du modèle. Une méthode de résolution est proposée pour le PM résultant. Nous démontrons alors théoriquement et vérifions expérimentalement la convergence de cette méthode. Cet algorithme peut être utilisé pour résoudre d'autres programmes biniveaux que celui qui est proposé.Le second thème de recherche de cette thèse s'intitule "problèmes de coupe et de couverture partielles dans les graphes". Les problèmes de coupe et de couverture sont parmi les problèmes de graphe les plus étudiés du point de vue complexité et algorithmique. Nous considérons certains de ces problèmes dans une variante partielle, c'est-à-dire que la propriété de coupe ou de couverture dont il est question doit être vérifiée partiellement, selon un paramètre donné, et non plus complètement comme c'est le cas pour les problèmes originels. Précisément, les problèmes étudiés sont le problème de multicoupe partielle, de coupe multiterminale partielle, et de l'ensemble dominant partiel. Les versions sommets des ces problèmes sont également considérés. Notons que les problèmes en variante partielle généralisent les problèmes non partiels. Nous donnons des algorithmes exacts lorsque cela est possible, prouvons la NP-difficulté de certaines variantes, et fournissons des algorithmes approchés dans des cas assez généraux. / This thesis is composed of two parts, each part belonging to a sub-domain of combinatorial optimization a priori distant from the other. The first research subject is stochastic bilevel programming. This term regroups two research subject rarely studied together, namely stochastic programming on the one hand, and bilevel programming on the other hand. Mathematical Programming (MP) is a set of modelisation and resolution methods, that can be used to tackle practical problems and help take decisions. Stochastic programming and bilevel programming are two sub-domains of MP, each one of them being able to model a specific aspect of these practical problems. Starting from a practical problem, we design a mathematical model where the bilevel and stochastic aspects are used together, then apply a series of transformations to this model. A resolution method is proposed for the resulting MP. We then theoretically prove and numerically verify that this method converges. This algorithm can be used to solve other bilevel programs than the ones we study.The second research subject in this thesis is called "partial cut and cover problems in graphs". Cut and cover problems are among the most studied from the complexity and algorithmical point of view. We consider some of these problems in a partial variant, which means that the cut or cover property that is looked into must be verified partially, according to a given parameter, and not completely, as it was the case with the original problems. More precisely, the problems that we study are the partial multicut, the partial multiterminal cut, and the partial dominating set. Versions of these problems were vertices are