A continuous optimization model for a joint problem of pricing and resource allocation
RAIRO - Operations Research - Recherche Opérationnelle, Volume 43 (2009) no. 2, pp. 115-143.

This paper investigates the problem of maximizing the revenue of a telecommunications operator by simultaneously pricing point-to-point services and allocating bandwidth in its network, while facing competition. Customers are distributed into market segments, i.e., groups of customers with a similar preference for the services. This preference is expressed using utility functions, and customers choose between the offers of the operator and of the competition according to their utility. We model the problem as a leader-follower game between the operator and the customers. This kind of problem has classically been modeled as a bilevel program. A market segmentation is usually defined by a discrete distribution function of the total demand for a service; in this case, the problem can be modeled as a combinatorial optimization problem. In this paper, however, we motivate the use of a continuous distribution function and investigate the nonlinear continuous optimization problem obtained in this case. We analyze the mathematical properties of the problem, and in particular we give a necessary and sufficient condition for its convexity. We introduce methods to solve the problem and we provide encouraging numerical results on realistic telecommunications instances of the problem, showing that it can be solved efficiently.

DOI: 10.1051/ro/2009008
Classification: 90C90
Keywords: optimization, bilevel programming, revenue management, pricing, resource allocation, telecommunications
@article{RO_2009__43_2_115_0,
     author = {Bouhtou, Mustapha and Erbs, Guillaume},
     title = {A continuous optimization model for a joint problem of pricing and resource allocation},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {115--143},
     publisher = {EDP-Sciences},
     volume = {43},
     number = {2},
     year = {2009},
     doi = {10.1051/ro/2009008},
     mrnumber = {2527859},
     zbl = {1176.90683},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ro/2009008/}
}
TY  - JOUR
AU  - Bouhtou, Mustapha
AU  - Erbs, Guillaume
TI  - A continuous optimization model for a joint problem of pricing and resource allocation
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2009
SP  - 115
EP  - 143
VL  - 43
IS  - 2
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ro/2009008/
DO  - 10.1051/ro/2009008
LA  - en
ID  - RO_2009__43_2_115_0
ER  - 
%0 Journal Article
%A Bouhtou, Mustapha
%A Erbs, Guillaume
%T A continuous optimization model for a joint problem of pricing and resource allocation
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2009
%P 115-143
%V 43
%N 2
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ro/2009008/
%R 10.1051/ro/2009008
%G en
%F RO_2009__43_2_115_0
Bouhtou, Mustapha; Erbs, Guillaume. A continuous optimization model for a joint problem of pricing and resource allocation. RAIRO - Operations Research - Recherche Opérationnelle, Volume 43 (2009) no. 2, pp. 115-143. doi : 10.1051/ro/2009008. http://archive.numdam.org/articles/10.1051/ro/2009008/

[1] G. Aydin and J. Ryan, Product line selection with stochastic utility (2000) (submitted).

[2] M. Ben-Akiva and M. Bierlaire, Discrete choice methods and their applications to short term travel decisions, in Handbook of transportation science, edited by R. Hall, International Series in Operations Research and Management Science, Vol. 23. Kluwer Academic Publishers, Dordrecht (1999) 5-34.

[3] T. Bergstrom and M. Bagnoli, Log-concave probability and its applications. Econ. Theory 26 (2005) 445-469. | MR | Zbl

[4] M. Bouhtou, M. Diallo and L. Wynter, Capacitated network revenue management through shadow pricing, in Group communications and charges; technology and business models, edited by B. Stiller, G. Carle, M. Karsten and P. Reichl, Lect. Notes Comput. Sci. 2816, Springer-Verlag, Berlin, Heidelberg (2003) 342-352. | MR

[5] M. Bouhtou, M. Diallo and L. Wynter, Fair network resource allocation and link pricing: A numerical study, in Optimization and optimal control, edited by P. Pardalos, I. Tsevendorj and R. Enkhbat, World Scientific Publishing, Singapore (2003) 37-58. | MR | Zbl

[6] M. Bouhtou, G. Erbs and M. Minoux, Pricing and resource allocation for point-to-point telecommunication services in a competitive market: a bilevel optimization approach, in Telecommunications planning: innovations in pricing, network design and management, edited by G. Anandalingam and S. Raghavan, Operations Research/Computer Science Interfaces Series, Vol. 33. Springer-Verlag, New York (2005) 1-16.

[7] M. Bouhtou, G. Erbs and M. Minoux, Joint optimization of pricing and resource allocation in competitive telecommunications networks. Networks 50 (2007) 37-49. | MR | Zbl

[8] M. Bouhtou, S. Van Hoesel, A. Van Der Kraaij and J.-L. Lutton, Tariff optimization in networks. INFORMS J. Comput. 19 (2007) 458-469. | MR

[9] L. Brotcorne, M. Labbé, P. Marcotte and G. Savard, A bilevel model and solution algorithm for a freight tariff setting problem. Transportation Science 34 (2000) 289-302. | Zbl

[10] L. Brotcorne, M. Labbé, P. Marcotte, and G. Savard. A bilevel model for toll optimization on a multicommodity transportation network. Transportation Science 35 (2001) 1-14. | Zbl

[11] J.-P. Côté, P. Marcotte and G. Savard, A bilevel modelling approach to pricing and fare optimisation in the airline industry. J. Revenue Pricing Manag. 2 (2003) 23-36.

[12] K.L. Croxton, B. Gendron and T.L. Magnanti, A comparison of mixed-integer programming models for non-convex piecewise linear cost minimization problems. Manage. Sci. 49 (2003) 1268-1273.

[13] M. Fortin, P. Marcotte and G. Savard, Pricing a segmented market subject to congestion, in Proceedings of the Fifth Triennal Symposium on Transportation Analysis (TRISTAN V), Le Gosier, Guadeloupe, June 13-18 (2004).

[14] F. Gilbert, P. Marcotte and G. Savard, Global and local approaches to a logit-based pricing problem, in 2006 Optimization Days, Montreal, May 8-10 (2006).

[15] A. Grigoriev, S. Van Hoesel, A. Van Der Kraaij, M. Uetz and M. Bouhtou, Pricing network edges to cross a river, in Approximation and online algorithms, edited by G. Persiano and R. Solis-Oba, Lect. Notes Comput. Sci. 3351, Springer-Verlag, Berlin, Heidelberg (2004) 140-153. | MR | Zbl

[16] C.G. Justus, W.R. Hargraves, A. Mikhail and D. Graber, Methods for estimating wind speed frequency distributions. J. Appl. Meteorol. 17 (1978) 350-353.

[17] N. Keon and G. Anandalingam, Optimal pricing for multiple services in telecommunications networks offering quality-of-service guarantees. IEEE/ACM Transactions on Networking 11 (2003) 66-80.

[18] N. Keon and G. Anandalingam, A new pricing model for competitive telecommunications services using congestion discounts. INFORMS J. Comput. 17 (2005) 248-262. | MR

[19] M. Labbé, P. Marcotte and G. Savard, A bilevel model of taxation and its application to optimal highway pricing. Manage. Sci. 44 (1998) 1608-1622. | Zbl

[20] M. Labbé, P. Marcotte and G. Savard, On a class of bilevel programs, in Nonlinear optimization and related topics, edited by G.D. Pillo and F. Giannessi, Kluwer Academic Publishers, Dordrecht, Boston (1999) 183-206. | MR | Zbl

[21] P. Marcotte, G. Savard and D. Zhu, Mathematical structure of a bilevel strategic pricing model. Eur. J. Oper. Res. (2006), (to appear). | MR | Zbl

[22] P. Marcotte and D. Zhu, Equilibria with infinitely many differentiated classes of customers. In Complementarity and variational problems. State of the art, edited by J.-S. Pang and M. Ferris, SIAM Publications, Philadelphia (1997) 234-258. | MR | Zbl

[23] J.I. Mcgill and G.J. Van Ryzin, Revenue management: Research overview and prospects. Transportation Science 33 (1999) 233-256. | Zbl

[24] S.K. Nair and R. Bapna, An application of yield management for internet service providers. Nav. Res. Logist. 48 (2001) 348-362. | MR | Zbl

[25] P. Reichl, D. Hausheer and B. Stiller, The cumulus pricing model as an adaptive framework for feasible, efficient and user-friendly tariffing of internet services. Comput. Networks 43 (2003) 3-24.

[26] R. Savickas, A simple option-pricing formula. Financ. Rev. 37 (2002) 207-226.

[27] A. Wächter and L.T. Biegler, On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming. Math. Program. 106 (2006) 25-57. | MR | Zbl

Cited by Sources: