Optimizing Over the Efficient Set of the Binary Bi-objective Knapsack Problem
DOI:
https://doi.org/10.2298/YJOR210915015CKeywords:
Multiple Objective Programming, Bi-objective Knapsack Problem, Dynamic Programming, Efficient Set, Optimal SolutionAbstract
This paper deals with the problem of optimizing a linear function over the efficient set of a 0-1 bi-objective knapsack problem. Such a function represents the main criterion of the problem posed. The resolution process is based essentially on dynamic programming. The proposed method provides a subset of efficient solutions including one which optimizes the main criterion without having to enumerate all the efficient solutions of the problem. Numerical experiments are reported, different instances with large sizes of the associated efficient sets are considered to show the efficiency of our algorithm compared with an approach proposed in the literature.References
E.L., Ulungu, Optimisation combinatoire multicritre: Détermination de l’Ensemble des Solutions Efficaces et Méthodes Interactives, these de doctorat, universitéde Mons-Hainaut, octobre 1993.
M. Visée, J. Teghem, M. Pirlot, and EL. Ulungu, “Two-phases method and branch and bound procedures to solve the bi-objective knapsack problem”, Journal of Global Optimization, vol. 12, pp. 139-55, 1998.
E. Captivo, J. Climaco, J. Figueira, E. Martins and J. L. Santos, “bicriteria 0-1 knapsack problems using a labeling algorithm”, Computers & Operational Research, vol. 30, pp. 1865-1886, 2003.
C. Bazgan, H. Hugot and D. Vanderpooten, “Solving efficiently the 0-1 multi-objective knapsack problem”, Computers & Operations Research, vol. 36, pp. 260-279, 2009.
J. Figueira, L. Paquete, M. Sim˜oes and D. Vanderpooten, “Algorithmic improvements on dynamic programming for the bi-objective {0,1} knapsack problem”. Comput Optim Appl, vol. 56, pp. 97-111, 2013.
P. Correia, L. Paquete and J. Figueira, “Compressed data structures for bi-objective {0,1}-knapsack problems”, Computers and Operations Research, vol. 89, pp. 82-93, 2018.
T. Erlebach, H. Kellerer and U. Pferschy, “Approximating multi-objective knapsack problems”, Management Sciences, vol. 48, pp. 1603-1612, 2002.
C. Bazgan, H. Hugot and D. Vanderpooten, “Implementing an efficient fptas for the 0-1 multi-objective knapsack problem”, European Journal of Operational Research, vol. 198, pp. 47-56, 2009.
J. Jorge, X. Gandibleux and M.Wiecek, A priori reduction of the size of the binary multiobjective knapsack problem, MOPGP’08 Multi-Objective Programming and Goal Programming, Portsmouth, UK, 2008.
M. Daoud and D. Chaabane, “New reduction strategy in the biobjective knapsack problem”, Intl. Trans. in Op. Res, vol. 25, pp. 1739-1762, 2016.
H.P. Bensen, “Optimization over the Efficient Set”, J. Math. Anal. Appl, vol. 98, pp. 562-580, 1984.
H.P. Bensen, “A finite Non adjacent Extreme Point Search Algorithm over the Efficient Set”, J. Opt. Theor. Appl, vol. 73, pp. 47-64, 1992.
H.P. Benson and S. Sayin, “Optimizing over the Efficient Set: Four Special Cases”, J. Optim. Theor. Appl, vol. 80, pp. 3-18, 1994.
J.G. Ecker and J.H. Song, “Optimizing a Linear Function over an Efficient Set”, J. Optim. Theor. Appl, vol. 83, pp. 541-563, 1994.
S. Sayin, “Optimizing over the Efficient Set using a Top-Down Search of Faces”, Oper. Res, vol. 48, pp. 65-72, 2000.
Y. Yamamoto, “Optimization over the efficient set: Overview, dedicated to Professor Reiner Horst on his 60th birthday”, Journal of Global Optimization, vol. 22, pp. 285-317, 2002.
N.C. Nguyen, An algorithm for optimizing a linear function over the integer efficient set, Konrad-Zuse- Zentrum fur Informations technik, Berlin, 1992.
M. Abbas and D. Chaabane, “Optimizing a linear function over an integer efficient set”, European Journal of Operational Research, vol. 174, pp. 1140-1161, 2006.
J.M. Jorge, “An algorithm for optimizing a linear function over an integer efficient set”, European Journal of Operational Research, vol. 195, pp. 98-103, 2009.
J. Sylva and A. Crema,“A method for finding the set of non-dominated vectors for multiple objective integer linear programs”, European Journal of Operational Research, vol. 158, pp. 46-55, 2004.
D. Chaabane and M. Pirlot, “A method for optimizing over the integer efficient set”, Journal of Industrial and Management Optimization, vol. 6, pp. 811-823, 2010.
D. Chaabane, B. Brahmi and Z. Ramdani, “The augmented weighted Tchebychev norm for optimizing a linear function over an integer efficient set of a multicriteria linear program”, International Transactions in Operational Research, vol. 19, pp. 531-545, 2012.
N. Boland, H. Charkhgard and M. Savelsbergh, “A new method for optimizing a linear function over the efficient set of a multiobjective integer program”, European Journal of Operational Research, vol. 260, pp. 904-919, 2017.
S. Mahdi and D. Chaabane, “A linear fractional optimization over an integer efficient set”, RAIRO Operations Research, vol. 49, pp. 265-278, 2015.
W. Drici, F.Z. Ouail and M. Moulai, “Optimizing a linear fractional function over the integer efficient set”, Ann Oper Res, vol. 267, pp. 135-151, 2017.
J.G. Ecker and I.A. Kouada, “Finding Efficient Points for Multi-objective Linear Programs”, Mathematical Programming, vol. 8, pp. 375-377, 1975.
S. Martello and P. Toth, Knapsack Problems: Algorithms and Computer Implementations, John Wiley & sons, New York, 1990.
Downloads
Published
Issue
Section
License
Copyright (c) YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
