PERIODO: APRILE 2017

il corso sarà tenuto dalla Prof.ssa Luce Brotcorne - INRIA, Team INOCS



The purpose of this curse is to introduce the field of bilevel optimization and its applications. The schedule will be divided into two parts: a theoretical study of bilevel programs and a focus on two applications in logistics and in the energy field.
Bilevel programming is a fairly recent branch of optimization that deals with programs whose constraints embed an auxiliary mathematical program. More precisely, bilevel programs allow modeling those situations in which a main agent, whom we call the leader, strives to optimize a given quantity but controls only a subset of the decision variables. The remaining variables fall under the control of a second agent, the follower, who solves its own problem by taking into account the decisions taken by the leader.
The optimal solution to such an interactive process constitutes what economists call an equilibrium problem where the demand function results from the solution of an optimization program. Bilevel programs are also closely related to Stackelberg (leader-follower) games [8], to the principal-agent paradigm [9] in economics, as well as to equilibrium constrained mathematical programs (MPECs), where the lower level problem characterizes the equilibrium state of some physical or economical system, and is frequently modelled as a variational inequality.
Although a wide range of applications fit the bilevel programming framework (see [2], [4], [5], [6], [7]), real-life implementations are scarce, due mainly to the lack of efficient algorithms for tackling large-scale problems. Indeed, as a general rule, bilevel models are nonconvex and nondifferentiable. Therefore, the structure of the problem has to be exploited in the design of efficient solution methods.
The first application we consider is a price setting problem (PPLHT) involving two long haul full load carriers (A and B) operating in similar markets ([2]). A product is defined as a quantity of goods with the same characteristics: origin, destination, pick up time and delivery time. We assume, that carrier B, cannot serve all the transportation requests with his own transportation fleet. He thus needs to use outsourcing: carrier A or his competitors. Carrier A, has to define the prices for carrier B transportation requests. Once carrier A has given its prices for the operations, it is B’s decision to turn to A or to another carrier. Both agents’ decisions are made according to their objectives: carrier B wants to minimize transportation cost while A seeks to maximize the revenue while balancing the free load length (limiting the free load distances). This sequential and non-cooperative decision making process can be adequately represented as a bilevel program. Carrier A (the leader) explicitly incorporates the reaction of carrier B (the follower) in his optimization process. At the first level, the carrier A (leader) maximizes its revenue by taking into account the reaction of the carrier B (the follower) who wants to satisfy all the demands at lower cost.
The second application deals with a pricing problem in the energy field ([1]). More precisely, pricing models for demand side management methods are traditionally used to control electricity demand,preno which became quite irregular recently and resulted in inefficiency in supply. In this cursus, we investigate bilevel pricing models to explore the relationship between energy suppliers and customers who are connected to a smart grid. The smart grid technology allows customers to keep track of hourly prices and shift their demand accordingly, and allows the provider to observe the actual demand response to its pricing strategy. In our setting, the energy provider acts as a leader (upper level) that takes into account a smart grid (lower level) that minimizes the sum of users' disutilities. The latter bases its decisions on the hourly prices set by the leader, as well as the schedule preferences set by the users for each task. The pricing problems, we model, belong to the category of single leader single follower problems.
For each of these two applications, we first define the models and study their properties. Next we present solution methods based on the structures of the problems and give numerical results.

Course schedule
All the classes will be held in the DAUIN Room C - goo.gl/BIPhN1

April 11, h. 9-12
April 12, h. 15-18
April 13, h. 9-12