English version:
Journal of Applied and Industrial Mathematics, 2016, 10:3, 356-369

Volume 23, No 3, 2016, P. 35-60

UDC 519.87+519.854
S. M. Lavlinskii, A. A. Panin, and A. V. Plyasunov
Comparison of models of planning public-private partnership

We propose two new mathematical formulation of the planning problem of public-private partnership. One of the models is bilevel and the other is one-level. The results that characterize the computational complexity of these models are shown. We develop some exact and approximate algorithms for solving these problems. A special model polygon is built to carry out a computational experiment. The polygon takes into account the specificity of the original information base. On the basis of the numerical results of the experiment, we compare the properties of optimal solutions in different models. This allows us to assess the adequacy of the underlying assumptions of the models with the current state of affairs in the field of project management of public-private partnership.
Ill. 13, bibliogr. 16.

Keywords: public-private partnership, bilevel problem, approximation hierarchy, NPO-hard problem, class $\Sigma^{P}_{2} O$, hybrid algorithm, local search.

DOI: 10.17377/daio.2016.23.527

Sergey M. Lavlinskii 1
Artem A. Panin 1,2

Alexander V. Plyasunov 1,2
1. Sobolev Institute of Mathematics,
4 Koptyug Ave., 630090 Novosibirsk, Russia
2. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: lavlin@math.nsc.ru, arteam1897@gmail.com, apljas@math.nsc.ru

Received 11 April 2016
Revised 10 May 2016


[1] I. P. Glazyrina, S. M. Lavlinskii, and I. A. Kalgina, Public and private partnership in the mineral resources sector of Zabaikalskii krai: Problems and perspectives, Geogr. Prir. Resur., No. 4, 89–95, 2014.

[2] I. A. Davydov, Tabu search for the discrete (r|p)-centroid problem, Diskretn. Anal. Issled. Oper., 19, No. 2, 19–40, 2012.

[3] A. I. Kibzun, A. V. Naumov, and S. V. Ivanov, A bilevel optimization problem for railway transport hub planning, in Upravlenie bol’shimi sistemami (Large-Scale Systems Control), Vol. 38, pp. 140–160, Inst. Probl. Upr., Moscow, 2012.

[4] Yu. A. Kochetov, Computational bounds for local search in combinatorial optimization, Zh. Vychisl. Mat. Mat. Fiz., 48, No. 5, 788–807, 2008. Translated in Comput. Math. Math. Phys., 48, No. 5, 747–763, 2008.

[5] S. M. Lavlinskii, Modeli indikativnogo planirovaniya sotsial’no-ekonomicheskogo razvitiya resursnogo regiona (Indicator-planning models for social and economy development of a resource region), Izd. SO RAN, Novosibirsk, 2008.

[6] S. M. Lavlinskii, Public and private partnership in a resource territory: Ecological problems, models, and perspectives, Probl. Progn., No. 1, 99–111, 2010.

[7] S. M. Lavlinskii and I. A. Kalgina, Methods to estimate public and private partnership in the mineral and raw material sector of Zabaikalskii krai. Vestn. ZabGU, No. 9, 96–102, 2012.

[8] S. M. Lavlinskii, A. A. Panin, and A. V. Plyasunov, A bilevel planning model for public-private partnership, Avtom. Telemekh., No. 11, 89–103, 2015. Translated in Autom. Remote Control, 76, No. 11, 1976–1987, 2015.

[9] A. A. Panin, M. G. Pashchenko, and A. V. Plyasunov, Bilevel competitive facility location and pricing problems, Avtom. Telemekh., No. 4, 153–169, 2014. Translated in Autom. Remote Control, 75, No. 4, 715–727, 2014.

[10] E. O. Rapoport On some problems of ground rent modeling in a mixed economy, Sib. Zh. Ind. Mat., 14, No. 2, 95–105, 2011.

[11] C. Audet, G. Savard, and W. Zghal, New branch-and-cut algorithm for bilevel linear programming, J. Optim. Theory Appl., 134, No. 2, 353–370, 2007.

[12] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti- Spaccamela, and M. Protasi, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer,
Berlin; Heidelberg, 1999.

[13.] I. A. Davydov, Yu. A. Kochetov and E. Carrizosa, VNS heuristic for the (r|p)-centroid problem on the plane, Electron. Notes Discrete Math., 39, 5–12, 2012.

[14] I. A. Davydov, Yu. A. Kochetov and A. V. Plyasunov, On the complexity of the (r|p)-centroid problem in the plane, TOP, 22, No. 2, 614–623, 2014.

[15] S. Dempe, Foundations of Bilevel Programming, Kluwer Acad. Publ., Dordrecht, 2002.

[16] S. T. DeNegre and T. K. Ralphs, A branch-and-cut algorithm for integer bilevel linear programs, in Operations Research and Cyber-Infrastructure, pp. 65–78
 © Sobolev Institute of Mathematics, 2015