Approximate solutions to the multiple-choice knapsack problem by multiobjectivization and Chebyshev scalarization

• Autorzy: Bednarczuk Ewa M. , Kaliszewski Ignacy , Miroforidis Janusz

Identyfikatory

DOI

10.37190/ord240403

• Języki publikacji: EN

Abstrakty

EN

The method BISSA, proposed by Bednarczuk, Miroforidis, and Pyzel, provides approximate solutions to the multiple-choice knapsack problem. To fathom the optimality gap that is left by BISSA, we present a method that starts from the BISSA solution and it is able to provide a better approximation and in consequence a tighter optimality gap. Like BISSA, the new method is based on the multiobjectivization of the multiple-choice knapsack problem but instead of the linear scalarization used in BISSA, it makes use of the Chebyshev scalarization. We validate the new method on the same set of problems as the one used to validate BISSA.

Słowa kluczowe

EN

multiobjectivization; multiple-choice knapsack problem; Chebyshev scalarization; BISSA algorithm

• Wydawca: Oficyna Wydawnicza Politechniki Wrocławskiej
• Czasopismo: Operations Research and Decisions
• Rocznik: 2024
• Tom: Vol. 34, No. 4
• Strony: 53--66
• Opis fizyczny: Bibliogr. 20 poz., rys.

Twórcy

autor

Bednarczuk Ewa M.

• Faculty of Mathematics and Information Science, Warsaw University of Technology, Warsaw, Poland

• https://orcid.org/0000-0003-3683-6881

autor

Kaliszewski Ignacy

• Systems Research Institute, Polish Academy of Sciences, Warsaw, Poland

• https://orcid.org/0000-0001-5404-7400

autor

Miroforidis Janusz

• Systems Research Institute, Polish Academy of Sciences, Warsaw, Poland

• https://orcid.org/0000-0002-1319-6239

Bibliografia

• [1] Bednarczuk, E. M., Miroforidis, J., and Pyzel, P. A multi-criteria approach to approximate solution of multiple-choice knapsack problem. Computational Optimization and Applications 70, 3 (2018), 889–910.
• [2] Brownlee, A. E. I., Wright, J. A., He, M., Lee, T., and McMenemy, P. A novel encoding for separable large-scale multi-objective problems and its application to the optimisation of housing stock improvements. Applied Soft Computing 96 (2020), 106650.
• [3] Cacchiani, V., Iori, M., Locatelli, A., and Martello, S. Knapsack problems – An overview of recent advances. Part I: Single knapsack problems. Computers and Operations Research 143 (2022), 105692.
• [4] Ehrgott, M. Multicriteria Optimization. Springer-Verlag, Berlin, Heidelberg, 2005.
• [5] Kaliszewski, I. A modified weighted Tchebycheff metric for multiple objective programming. Computers and Operations Research 14, 4 (1987), 315–323.
• [6] Kaliszewski, I. Soft Computing for Complex Multiple Criteria Decision Making. Springer Science & Business Media, New York, 2006.
• [7] Kaliszewski, I., Miroforidis, J., and Podkopaev, D. Multiple Criteria Decision Making by Multiobjective Optimization. A Toolbox. Springer International Publishing, 2016.
• [8] Kellerer, H., Pferschy, U., and Pisinger, D. Knapsack problems. Springer, Berlin, 2004.
• [9] Khan, M. S. Quality Adaptation in a Multisession Multimedia System: Model, Algorithms and Architecture. PhD thesis, University of Victoria, Victoria, B. C., Canada, 1998.
• [10] Klamroth, K., and Tind, J. Constrained optimization using multiple objective programming. Journal of Global Optimization 37, 3 (2007), 325–355.
• [11] Knowles, J. D., Watson, R. A., and Corne, D. W. Reducing local optima in single-objective problems by multiobjectivization. In Evolutionary Multi-Criterion Optimization. First International Conference, EMO 2001, Zurich, Switzerland, March 7-9, 2001 Proceedings (Berlin, 2001), E. Zitzler, L. Thiele, K. Deb, C. A. Coello Coello, and D. Cornepp, Eds., vol. 1993 of Lecture Notes in Computer Science, Springer-Verlag, pp. 269–283.
• [12] Kwong, C. K., Mu, L. F, Tang, J. F., and Luo, X. G. Optimization of software components selection for component-based software system development. Computers & Industrial Engineering 58, 4 (2010), 618–624.
• [13] Lee, C., Lehoczky, J., Rajkumar, R. R., and Siewiorek, D. On quality of service optimization with discrete QoS options. In Proceedings of the Fifth IEEE Real-Time Technology and Applications Symposium (Vancouver, BC, Canada, 1999), IEEE, pp. 276–286.
• [14] Martello, S., and Toth, P. Knapsack Problems: Algorithms and Computer Implementations. John Wiley and Sons, New York, 1990.
• [15] Miettinen, K. M. Nonlinear Multiobjective Optimization. Kluwer Academic Publishers, 1999.
• [16] Nauss, R. M. The 0–1 knapsack problem with multiple choice constraints. European Journal of Operational Research 2, 2 (1978), 125–131.
• [17] Pisinger, D. Budgeting with bounded multiple-choice constraints. European Journal of Operational Research 129, 3 (2001), 471–480.
• [18] Pyzel, P. On measures of risk related to IT system selection problem. Techniki Informacyjne – Teoria i Zastosowania, Wybrane Problemy 4, 16 (2014), 99–112.
• [19] Segura, C., Coello Coello, C. A., Miranda, G., León, C. Using multi-objective evolutionary algorithms for singleobjective constrained and unconstrained optimization Annals of Operations Research 240, 1 (2016), 217–250.
• [20] Sinha, P., and Zoltners, A. A. The multiple-choice knapsack problem. Operations Research 27, 3 (1979), 503–515.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa nr POPUL/SP/0154/2024/02 w ramach programu "Społeczna odpowiedzialność nauki II" - moduł: Popularyzacja nauki (2025).