Formalization of the computer three-dimensional graphics rendering optimization problem as a variant of the multidimensional knapsack problem

The work is devoted to solving the problem of optimizing the rendering of computer three-dimensional graphics, namely the rendering pipeline. This work reduces the mentioned problem to a multidimensional version of the well-known combinatorial optimization knapsack problem. The central element of this optimization is capacity, which in the current context is the user's limited hardware capabilities, and the items to be placed in the capacity, which are various pixel shaders. The capacity is limited by the values of the hardware resources, and the shader items have two properties - utility, expressed in some value of contribution to the quality of render, and weight, which is their computational cost. The main challenge in such a context is to develop a system that will be able to solve such a knapsack problem in real time, in order to determine at each moment the best possible combination of shaders. Thus, it will be possible to obtain the best image quality and avoid downtime or overloading of the hardware. The main application of the described system will be in the sphere of computer games, web advertising, movie making and other spheres using computer graphics. Among the key problems in the development of the described system is the difficulty in determining the contribution of each individual shader to the result, due to the it’s subjectivity. Another difficulty is finding a compromise between the accuracy of the knapsack problem solution and the speed of obtaining the result, taking into account the condition that the system must work in real time and not slow down the program for which the optimization is being performed.

1. Luna F.D. Introduction to 3D Game Programming with DirectX 12. Dulles: Mercury Learning and Information; 2016. 900 p.

2. Castorina M., Sassone G. Mastering Graphics Programming with Vulkan: Develop a modern rendering engine from first principles to state-of-the-art techniques. Birmingham: Packt Publishing Ltd; 2023. 382 p.

3. Dickinson C. Unity 2017 Game Optimization: Optimize all aspects of Unity performance. Birmingham: Packt Publishing Ltd; 2017. 376 p.

4. Martello S., Toth P. Knapsack Problems: Algorithms and Computer Implementations. Chichester: John Wiley & Sons Ltd; 1990. 308 p.

5. Peresunko P., Mamatin D., Antamoshkin O., Peresunko E., Nikitin A. Models of Experts for Shaders Estimation of Rendering Complex 3D Scenes in Real Time. In: 2021 3rd International Conference on Control Systems, Mathematical Modeling, Automation and Energy Efficiency (SUMMA), 10–12 November 2021, Lipetsk, Russia. IEEE; 2021. pp. 895–897. https://doi.org/10.1109/SUMMA53307.2021.9632071

6. Cacchiani V., Iori M., Locatelli A., Martello S. Knapsack problems – An overview of recent advances. Part II: Multiple, multidimensional, and quadratic knapsack problems. Computers & Operations Research. 2022;143. https://doi.org/10.1016/j.cor.2021.105693

7. Andonov R., Poirriez V., Rajopadhye S. Unbounded knapsack problem: Dynamic programming revisited. European Journal of Operational Research. 2000;123(2):394–407. https://doi.org/10.1016/S0377-2217(99)00265-9

8. Pferschy U., Scatamacchia R. Improved dynamic programming and approximation results for the knapsack problem with setups. International Transactions in Operational Research. 2017;25(2):667–682. https://doi.org/10.1111/itor.12381

9. Boyer V., Baz D.E., Elkihel M. Solution of multidimensional knapsack problems via cooperation of dynamic programming and branch and bound. European Journal of Industrial Engineering. 2010;4(4):434–449. https://doi.org/10.1504/EJIE.2010.035653

10. Martello S., Toth P. An Exact Algorithm for the Two-Constraint 0–1 Knapsack Problem. Operations Research. 2003;51(5):826–835. https://doi.org/10.1287/opre.51.5.826.16757

11. Boussier S., Vasquez M., Vimont Y., Hanafi S., Michelon P. A multi-level search strategy for the 0–1 Multidimensional Knapsack Problem. Discrete Applied Mathematics. 2010;158(2):97–109. https://doi.org/10.1016/j.dam.2009.08.007

12. Dantzig G.B. Discrete-Variable Extremum Problems. Operations Research. 1957;5(2):266–288. https://doi.org/10.1287/opre.5.2.266

13. Al-douri T., Hifi M., Zissimopoulos V. An iterative algorithm for the Max–Min knapsack problem with multiple scenarios. Operational Research. 2021;21(1):1355–1392. https://doi.org/10.1007/s12351-019-00463-7

14. Chan T.M. Approximation Schemes for 0-1 Knapsack. In: 1st Symposium on Simplicity in Algorithms (SOSA 2018): Open Access Series in Informatics (OASIcs): Volume 61, 07–10 January 2018, New Orleans, LA, USA. 2018. pp. 5:1–5:12. https://doi.org/10.4230/OASIcs.SOSA.2018.5

15. Jin C. An Improved FPTAS for 0-1 Knapsack. In: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019): Leibniz International Proceedings in Informatics (LIPIcs): Volume 132, 09–12 July 2019, Patras, Greece. 2019. pp. 76:1–76:14. https://doi.org/10.4230/LIPIcs.ICALP.2019.76

16. Zhou Y., Kuang Z., Wang J. A Chaotic Neural Network Combined Heuristic Strategy for Multidimensional Knapsack Problem. In: Advances in Computation and Intelligence: Third International Symposium on Intelligence Computation and Applications, ISICA 2008: Proceedings, 19–21 December 2008, Wuhan, China. Berlin, Heidelberg: Springer; 2008. pp. 715–722. https://doi.org/10.1007/978-3-540-92137-0_78

17. Afshar R.R., Zhang Y., Firat M., Kaymak U. A State Aggregation Approach for Solving Knapsack Problem with Deep Reinforcement Learning. In: 12th Asian Conference on Machine Learning, ACML 2020: Proceedings of Machine Learning Research: Volume 129, 18–20 November 2020, Bangkok, Thailand. PMLR; 2020. pp. 81–96.

18. Mingo López L.F., Gómez Blas N., Arteta Albert A. Multidimensional knapsack problem optimization using a binary particle swarm model with genetic operations. Soft Computing. 2017;22(8):2567–2582. https://doi.org/10.1007/s00500-017-2511-0

19. Ke L., Feng Z., Ren Z.H., Wei X. An ant colony optimization approach for the multidimensional knapsack problem. Journal of Heuristics. 2010;16(1):65–83. https://doi.org/10.1007/s10732-008-9087-x

20. Jalali Varnamkhasti M., Lee L.S. A Fuzzy Genetic Algorithm Based on Binary Encoding for Solving Multidimensional Knapsack Problems. Journal of Applied Mathematics. 2012;2012. https://doi.org/10.1155/2012/703601

21. Djannaty F., Doostdar S. A Hybrid Genetic Algorithm for the Multidimensional Knapsack Problem. International Journal of Contemporary Mathematical Sciences. 2008;3(9):443–456.

22. Kulik A., Shachnai H. There is no EPTAS for two-dimensional knapsack. Information Processing Letters. 2010;110(16):707–710. https://doi.org/10.1016/j.ipl.2010.05.031

23. Beasley J.E. OR-Library: Distributing Test Problems by Electronic Mail. Journal of the Operational Research Society. 1990;41(11):1069–1072. https://doi.org/10.1057/jors.1990.166

24. Kong X., Gao L., Ouyang H., Li S. Solving large-scale multidimensional knapsack problems with a new binary harmony search algorithm. Computers & Operations Research. 2015;63(C):7–22. https://doi.org/10.1016/j.cor.2015.04.018