sur ce site

Accueil du site > Résumés des séminaires > Thésard > Séminaire des doctorants - 23 juin 2017

Séminaire des doctorants - 23 juin 2017

Jean-Bernard Eytard (CMAP) - A tropical approach to bilevel programming : application to a price incentives model in mobile data networks

Salle de conférence du CMAP - 16h00

In recent work, tropical geometry methods have been applied to a class of problems in mathematical economy (existence of competitive equilibria for indivisible goods). A key idea is to represent the agent’s response by an arrangement of tropical hypersurfaces. We apply this idea to bilevel programming problems. The latter are a class of (generally hard) optimization problems, omnipresent in optimal pricing. We consider here an application to a price incentives model in mobile data networks. An Internet service provider, wishing to balance the network in order to limit congestion, announces some discounts at certain time and certain place for using data with mobile phones. Then, every customer determines his consumption by optimizing an individual utility function depending on this discount. These consumptions finally determine the number of active customers in the network at each time and each place, and then the objective function of the Internet service provider. By exploiting tropical geometry and discrete convexity methods (M-convexity in the sense of Murota), we show that this problem (and more generally a class of bilevel programming problems) can be solved in polynomial time. We illustrate these results by an application provided by Orange.

CMAP UMR 7641 École Polytechnique CNRS, Route de Saclay, 91128 Palaiseau Cedex France, Tél: +33 1 69 33 46 23 Fax: +33 1 69 33 46 46