A tropical geometry and discrete convexity approach to bilevel programming : application to smart data pricing in mobile telecommunication networks
Jean Bernard Eytard · HAL (Le Centre pour la Communication Scientifique Directe) · 2018
Bilevel programming deals with nested optimization problems involving two players. A leader annouces a decision to a follower, who responds by selecting a solution of an optimization problem whose data depend on this decision (low level problem). The optimal decision of the leader is the solution of another optimization problem whose data depend on the follower's response (high level problem). When the follower's response is not unique, one distinguishes between optimistic and pessimistic bilevel problems, in which the leader takes into account the best or worst possible response of the follower.Bilevel problems are often used to model pricing problems.We are interested in applications in which the leader is a seller who announces a price, and the follower models the behavior of a large number of customers who determine their consumptions depending on this price.Hence, the dimension of the low-level is large. However, most bilevel problems are NP-hard, and in practice, there is no general method to solve efficiently large-scale bilevel problems.In this thesis, we introduce a new approach to tackle bilevel programming. We assume that the low level problem is a linear program, in continuous or discrete variables, whose cost function is determined by the leader. Then, the follower responses correspond to the cells of a special polyhedral complex, associated to a tropical hypersurface. This is motivated by recent applications of tropical geometry to model the behavior of economic agents.We use the duality between this polyhedral complex and a regular subdivision of an associated Newton polytope to introduce a decomposition method, in which one solves a series of subproblems associated to the different cells of the complex. Using results about the combinatorics of subdivisions, we show thatthis leads to an algorithm to solve a wide class of bilevel problemsin a time that is polynomial in the dimension of the low-level problem when the dimension of the high-level problem is fixed.Then, we identify special structures of bilevel problems forwhich this complexity bound can be improved.This is the case when the leader's cost function depends only on the follower's response. Then, we showthe optimistic bilevel problem can be solved in polynomial time.This applies in particular to high dimensional instances in which the datasatisfy certain discrete convexity properties. We also show that the solutions of such bilevel problems are limits of competitive equilibria.In the second part of this thesis, we apply this approach to a price incentive problem in mobile telecommunication networks.The aim for Internet service providers is to use pricing schemes to encourage the different users to shift their data consumption in time(and so, also in space owing to their mobility),in order to reduce the congestion peaks.This can be modeled by a large-scale bilevel problem.We show that a simplified case can be solved in polynomial time by applying the previous decomposition approach together with graph theory and discrete convexity results. We use these ideas to develop an heuristic method which applies to the general case. We implemented and validated this method on real data provided by Orange.