Solving Resource Allocation Problem in Wifi Network by Dantzig-Wolfe Decomposition Algorithm
Main Article Content
Abstract
Online advertising and advancements is a recent trend in marketing technology, in this context we consider a new form of contract which allows advertisers to specify in the Wifi system. Based on the structure of the system, we have to organize and manage resource allocation such that the guaranteed display is satisfied. We introduce a new mathematical model and develop an optimization framework that aims to optimize “fairness” of allocation each campaign over its targeted location. Because of large scale problem, the Dantzig-Wolfe decomposition is proposed for solving it. Dantzig-Wolfe decomposition is a technique for dealing with large scale linear programming and modified to solve linear integer programming, nonlinear programming. Especially, it is used mostly in linear programming when its size is very large, and its structure is appropriate. The technique has been successfully applied in a variety of contexts. In this paper, we introduce a new model of a resource allocation problem in Wifi network and represent Dantzig-Wolfe decomposition for solving this problem by dividing the number of advertisement impressions when users access the Wifi network. The numerical simulation shows the efficiency of our proposed method.
Keywords
Dantzig-Wolfe decomposition, resource allocation, wifi network, online advertising.
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
References
[1] Hana Choi, Carl F. Mela, Santiago R. Balseiro, Adam Leary, Online display advertising markets: A literature review and future directions, Information Systems Research, vol. 31, No. 2, 2020. https://doi.org/10.1287/isre.2019.0902 [2] Hana Choi, Carl Mela, Santiago R.Balseiro, Adam Leary, Online display advertising markets: A literature review and future directions, SSRN Electronic Journal, Jan. 2019. https://doi.org/10.2139/ssrn.3070706
[3] A. Z. Broder, Computational advertising and recommender systems, In Proceedings of the 2008 ACM conference on Recommender systems, 2008. https://doi.org/10.1145/1454008.1454009
[4] J. Yang, E. Vee, S. Vassilvitskii, J. Tomlin, J. Shanmugasundaram, T. Anastasakos, O. Kennedy, Inventory allocation for online graphical display advertising, arXiv:1008.3551, Aug. 2010. https://doi.org/10.48550/arXiv.1008.3551
[5] J. Yang, E. Vee, S. Vassilvitskii, J. Tomlin, J. Shanmugasundaram, T. Anastasakos and O. Kennedy, Inventory allocation for online grahpical display Advertising using multi-objective optimization, In Proceedings of the 1st International Conference on Operations Research and Enterprise Systems, pp. 293- 304, 2012. https://doi.org/10.5220/0003752802930304
[6] Hong Zhang, Lan Zhang, Lan Xu, Xiaoyang Ma, Zhengtao Wu, Cong Tang, Wei Xu, Yiguo Yang, A Request-level guaranteed delivery advertising planning: forecasting and allocation, Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD '20), pp. 2980-2988, Aug. 2020. https://doi.org/10.1145/3394486.3403348
[7] James Richard Tebboth, A Computational study of Dantzig-Wolfe Decomposition, Thesis submitted for the degree of Doctor of Philosophy in the University of Buckingham 2001.
[8] Antonio J. Conejo, Enrique Castillo, Roberto M´ınguez, Raquel Garc´ıaBertrand, Decomposition Techniques in Mathematical Programming, Springer-Verlag Berlin Heidelberg, The Netherlands, 2006. https://doi.org/10.1007/3-540-27686-6
[9] Ted Ralphs, Anahita Hassanzadeh, Jiadong Wang, Matthew Galati, Menal Gu¨zelsoy, Scott Denegre, Decomposition methods for discrete optimization, In Proceeding INFORMS Computing Society Conference, Jan. 2013.
[3] A. Z. Broder, Computational advertising and recommender systems, In Proceedings of the 2008 ACM conference on Recommender systems, 2008. https://doi.org/10.1145/1454008.1454009
[4] J. Yang, E. Vee, S. Vassilvitskii, J. Tomlin, J. Shanmugasundaram, T. Anastasakos, O. Kennedy, Inventory allocation for online graphical display advertising, arXiv:1008.3551, Aug. 2010. https://doi.org/10.48550/arXiv.1008.3551
[5] J. Yang, E. Vee, S. Vassilvitskii, J. Tomlin, J. Shanmugasundaram, T. Anastasakos and O. Kennedy, Inventory allocation for online grahpical display Advertising using multi-objective optimization, In Proceedings of the 1st International Conference on Operations Research and Enterprise Systems, pp. 293- 304, 2012. https://doi.org/10.5220/0003752802930304
[6] Hong Zhang, Lan Zhang, Lan Xu, Xiaoyang Ma, Zhengtao Wu, Cong Tang, Wei Xu, Yiguo Yang, A Request-level guaranteed delivery advertising planning: forecasting and allocation, Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD '20), pp. 2980-2988, Aug. 2020. https://doi.org/10.1145/3394486.3403348
[7] James Richard Tebboth, A Computational study of Dantzig-Wolfe Decomposition, Thesis submitted for the degree of Doctor of Philosophy in the University of Buckingham 2001.
[8] Antonio J. Conejo, Enrique Castillo, Roberto M´ınguez, Raquel Garc´ıaBertrand, Decomposition Techniques in Mathematical Programming, Springer-Verlag Berlin Heidelberg, The Netherlands, 2006. https://doi.org/10.1007/3-540-27686-6
[9] Ted Ralphs, Anahita Hassanzadeh, Jiadong Wang, Matthew Galati, Menal Gu¨zelsoy, Scott Denegre, Decomposition methods for discrete optimization, In Proceeding INFORMS Computing Society Conference, Jan. 2013.