Bilevel optimization of a distribution of interbudget transfers within given limitations

1Semenov, VV
1V.М. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv
Dopov. Nac. akad. nauk Ukr. 2019, 10:11-20
https://doi.org/10.15407/dopovidi2019.10.011
Section: Information Science and Cybernetics
Language: Ukrainian
Abstract: 

The problems of optimal distributing of transfers are defined and investigated within given budget limitations with the purpose of maximization of the social welfare in accordance with predefined criteria. The mathematical model is presented as a bilevel optimization problem, containing a linear problem of integer optimization at the bottom level, whose optimal solution is used for setting a feasible region of a bilevel problem. The optimistic and pessimistic problem definitions on the optimal distributing of transfers are considered. For the approximate solution of the optimistic version of a bilevel problem on the basis of the method of directing neighborhoods, the algorithm of finding the solutions for a parametric problem of integer programming of a lower level is proposed. The integer programming problem of a higher level with Boolean variables is solved on the basis of local algorithms.

Keywords: bilevel optimization problem, Boolean variables, integer optimization, local algorithm, parametric programming
References: 

1. Sergienko, I. V. & Semenov, V. V. (2013). Modeling the System of Intergovernmental Transfers in Ukraine. J. Automation and Information Sciences, 45, No. 8, pp. 1-10. doi: https://doi.org/10.1615/JAutomatInfScien.v45.i8.10
2. Semenov, V. V. (2013). Modeling the impact of Ukraine’s interbudget transfers on financing the social infrastructure. Dopov. Nac. acad. nauk Ukr., No. 10, pp. 47-53 (in Ukrainian)
3. Sergienko, I. V. (2014). Topical directions of informatics. In memory of V.M. Glushkov. New York ets.: Springer. 286 p. doi: https://doi.org/10.1007/978-1-4939-0476-1
4. Semenov, V. V. (2008). Economic and statistical models and methods of research of social processes: are inequality, poverty, polarization. Kyiv: EPD PUCCU. Vol. 1, 238 p., Vol. 2, 270 p. (in Ukrainian).
5. Sergienko, I. V., Kozeratska, L. & Lebedeva, T. T. (1995). Research of stability and parametric analysis of discrete optimization problems. Kyiv: Naukova Dumka (in Russian).
6. Sergienko, I. V. & Shilo, V. P. (2003). Tasks of Discrete Optimization: Problems, Methods of Solution and Research. Kyiv: Naukova Dumka (in Russian).
7. Beyko, I. V., Zinko, P. M. & Nakonechnyi, O. G. (2011). Problems, methods and algorithms of optimiza tion. Rivne: EPD NUWEUN (in Ukrainian).
8. Вen-Ayed, O. (1993). Bilevel linear programming. Comput. Oper. Res., 20. No. 5, pp. 485-501. doi: https://doi.org/10.1016/0305-0548(93)90013-9
9. Semenova, N. V. (2007). Methods of searching for guaranteeing and optimistic solutions to integer optimization problems under uncertainty. Cybernetics and Systems Analysis, 43. No. 1, pp. 85-93 (in Russian). doi: https://doi.org/10.1007/s10559-007-0028-8
10. Dempe, S. (2002). Foundations of Bilevel Programming. Dordrecht: Kluwer Acad. Publ.
11. Sinha, A., Malo, P. & Deb, K. (2018). A Review on Bilevel Optimization: From Classical to Evolutionary Approaches and Applications. IEEE Transactions on Evolutionary Computation, 22. No. 2, pp. 278-295. doi: https://doi.org/10.1109/TEVC.2017.2712906
12. Vicente, L., Savard, G. & Judice, J. (1996). Discrete linear bilevel programming problem. J. optimization theory and applications, 89. No. 3, pp. 597-614. doi: https://doi.org/10.1007/BF02275351