Abstract.

Recently, there is an urgent need to develop an effective model and algorithmic apparatus for the top level of the project management system, on which there should be a subsystem for selecting and managing the portfolio of projects to be implemented. In this paper, we consider the optimal selection of the project portfolio and the allocation of resources for its implementation in the form of a discrete optimization problem – the multidimensional Knapsack problem. The paper presents known theoretical results for a greedy heuristic for solving a one-dimensional Knapsack problem. Necessary and sufficient conditions for optimality; estimation of the error of the algorithm and its asymptotic error for the behavior in the mean. A direct greedy heuristic at unit cost is proposed for solving the multidimensional Knapsack problem. To improve its effectiveness, we use a local limited search, which improves the greedy solution, as well as the addition and local optimization of the previous stages. Greedy heuristics are fast, with a polynomial time complexity.

Keywords:

knapsack problem, multidimensional Knapsack problem, project portfolio, improved greedy heuristic, local limited search, polynomial time complexity.

PP. 54-64.

DOI: 10.14357/20790279190206

References

1. Gelrud Ya. D. 2015. Metodologiya sozdaniya informatsionno-analiticheskoy sistemy upravleniya proyektami na osnove kompleksa matematicheskikh modeley funktsionirovaniya steykkholderov. [Methodology for creating an information and analytical system for project management on the basis of a complex of mathematical models of the functioning of stakeholders]: Dr. Sci. Thesis. Chelyabinsk. The South Urals State University (SRU). 43 р.
2. Lopukhin M.M. 1971. PATTERN – metod planirovaniya i prognozirovaniya nauchnykh rabot. [PATTERN – a method of planning and forecasting research developments.] M .: Soviet radio.
3. Cetron M.J. 1967. QUEST Status Report. IEEE Transactions on Engineering Management. 14(1):443.
4. Nutt A.B. 1969. Testing TORQUE – a quantitative R&D research allocation system. IEEE Trans. on Eng. Manag. EM-16(4).
5. The Analysis and Evaluation of Public Expenditures: the PPB System. 1969. Washington: U.S. Govern. Print Office.
6. Jantsch E. 1967. Technological forecasting in perspective: a framework for technological forecasting, its techniques and organization - Paris : Organization for Economic Co-operation and Development, – 401 р.
7. Larichev O.I., Boychenko V.S., Moshkovich E.N., Sheptalova L.P. 1978. Metody iyerarkhicheskikh skhem v programmno-tselevom planirovanii nauchnykh issledovaniy [Methods of hierarchical schemes in goal-oriented research planning] / Preprint.[ Working Paper] M .: VNIISI.
8. Martello S., Toth P. 1990. Knapsack problems: Algorithms and computer implementations / in: Series in Discrete Mathematics and Optimization. N. Y.: Wiley Inter Sciences, 296 р.
9. Kellerer H., Pferschy U., Pisinger D. 2004. Knapsack Problems. Berlin / Heidelberg: Springer-Verlag, 548 р.
10. Dantzig G.B. 1957. Discrete-Variable Extremum Problems. Oper. Res. (INFORMS). 5( 2): 266–277.
11. Vizvari B. 1992. On the Optimality of the Greedy Solutions of the General Knapsack Problems. Optimization. 23(2):125-138.
12. Dyubin G.N., Korbut A.A. 1999. Zhadnyye algoritmy dlya zadach o rantse: povedeniye v srednem [Greedy algorithms for Knapsack problems: average behavior.]. Sibirskiy zhurnal industrial’noy matematiki. [Siberian Journal of Industrial Mathematics.]. 2 (2(4)): 68-93.
13. Korte B. 1986. Kombinatorische Optimierung und algorithmische Prinzipien // Ökonomische Prognose-, Enstscheidungs- und Gleichgewichtsmodelle. Weinheim: VCH Verlagsgesellschaft,. рр. 286-341.
14. Gafarov E.R., Lazarev A.A., Werner F. 2010. Algorithms for Some Maximization Scheduling Problems on a Single Machine . Automation and Remote Control. 71(10): 2070–2084.
15. Lazarev A., Salnikov A., Baranov A. 2011. Graphical Algorithm for the Knapsack Problems. Lecture Notes in Computer Science. 6873: 459-466.
16. Weingartner H.M., Ness D.N. 1967. Method for the solution for the multidimensional 0–1 knapsack problem . Operations Research. 15: 83–103.
17. Lorie J., Savage L.J. 1955. Three problems in capital rationing. Journal of Business. 28: 229–239.
18. Manne A.S., Markowitz H.M. 1957. On the solution of discrete programming problems. Econometrica. 25: 84–110.
19. Freville А. 2004. The multidimensional 0–1 knapsack problem: An overview. European Journal of Operational Research. 155: 1–21.
20. Levin M. Sh., Safonov A.V. 2009. Evristicheskiy algoritm dlya mnogokriterial’noy blochnoy zadachi o ryukzake [Heuristic algorithm for the multi-criteria block Knapsack problem]. Iskusstvennyy intellekt i prinyatiye resheniy. [Artificial intelligence and decision making.] 4: 53-64.
21. Burkova I.V., Tkachenko M.V., Churakov P.P. 2010. Zadacha vybora mnozhestva proyektov pri vypuske innovatsionnoy produktsii [The problem of selecting a set of projects for the release of innovative products]. Vestnik Voronezhskogo gosudarstvennogo tekhnicheskogo universiteta. [Newsletter of the Voronezh State Technical University.]. 6(9):.120-124.
22. Burkov V.N., Burkova I.V., Uandykov B.K., Chu D.S. 2015. Metod dopustimykh resheniy v mnogomernoy zadache o rantse [The method of admissible solutions in the multidimensional Knapsack problem]. Ekonomika i menedzhment sistem upravleniya. [Economics and management of control systems.]. 18(4.1): 136-144.
23. Burkova I.V., Puzhanova Ye.O., Marin O.L. 2014. Zadacha o rantse i yeye modifikatsii [The Knapsack problem and its modifications]. Nauchnyy vestnik Voronezhskogo gosudarstvennogo arkhitekturno-stroitel’nogo universiteta. Seriya: Upravleniye stroitel’stvom. [Scientific herald of the Voronezh State Architectural and Construction University. Series: Management of construction.] Voronezh: VGASU, 1(6): 103-112.
24. Burkov V.N., Burkova I.V., Popok M.V., Ovchinnikova T.I. 2005. Metod setevogo programmirovaniya [Method of network programming ]. Problemy upravleniya. [Control problems.] 3: 23 – 29.
25. Finkel’shtein Iu.Iu. 1976. Priblizhennye metody i prikladnye zadachi diskretnogo programmirovaniia [Approximate Methods and Applied Problems of Discrete Programming]. Moscow: Nauka, 264 p.
26. Gafarov E.R., Dolgui A., Lazarev A.A., Werner F. 2016. A New Effective Dynamic Program for an Investment Problem. Automation and Remote Control. 77(9): 1633-1648.
27. Rubinshteyn M.I., Topka V.V. 1991. Zhadnyi algoritm resheniya mnogomernoy zadachi o ryukzake [Greedy algorithm for solving the multidimensional Knapsack problem]. Trudy IV-oy Vsesoyuznoy shkoly-seminara «Statisticheskiy i diskretnyi analiz dannykh i ekspertnoye otsenivaniye» [4th School-Seminar (All-Union) “Statistical and Discrete Data Analysis and Expert Evaluation” Proceedings ]. Odessa. 273-274.
28. Schrijver A. 1986. Theory of Linear and Integer Programming. N.Y.: J. Wiley & Sons Ltd, 702 p.
29. Shani S. 1975. Approximate algorithms for the 0–1 knapsack problem. Journal of Association for Computing Machinery. 22: 115–124.
30. Chandra A.K., Hirschberg D.S., Wong C.K. 1976. Approximation algorithms for some generalized knapsack problems. Theoretical Computer Sciences. 3: 293–304.
31. Magazine M.J., Oguz O. 1981. A fully polynomial approximation algorithm for the 0–1 knapsack problem. European Journal of Operational Research. 8: 270–273.