Solving the bi-objective multidimensional knapsack problem exploiting the concept of core

Mavrotas, George and Figueira, José Rui and Florios, Kostas (2009): Solving the bi-objective multidimensional knapsack problem exploiting the concept of core. Published in: Applied Mathematics and Computation , Vol. 215, No. 7 (1 December 2009): pp. 2502-2514.

Abstract

This paper discusses the bi-objective multi-dimensional knapsack problem. We propose the refinement of the core concept that has already effectively been used in the single objective multi-dimensional knapsack. The core concept is based on the divide and conquer principle. Instead of solving the whole problem with n variables, several sub-problems with less than n variables are solved, in several variables which comprise the cores. The quality of the obtained solution can be adjusted according to the core size and there is always a balance between the solution time and quality. First, the core variables are defined, and subsequently the bi-objective integer program is solved, that comprises only the core variables using the Multicriteria Branch and Bound algorithm that generates the complete Pareto set. Small and medium sized examples are solved. Also, a very small example is used to illustrate the method while computational issues are also discussed.

• Item Type: MPRA Paper
• Language: English
• Keywords: Combinatorial optimization, Branch-and-bound, Multi-objective programming, Multi-dimensional knapsack problems
• Subjects: C - Mathematical and Quantitative Methods > C6 - Mathematical Methods ; Programming Models ; Mathematical and Simulation Modeling > C61 - Optimization Techniques ; Programming Models ; Dynamic Analysis; C - Mathematical and Quantitative Methods > C6 - Mathematical Methods ; Programming Models ; Mathematical and Simulation Modeling > C63 - Computational Techniques ; Simulation Modeling

References

E. Balas, E., Zemel, E., 1980. An algorithm for large zero-one knapsack problems. Operations Research 28, 1130-1154.

Gomes da Silva, C., Climaco, J., Figueira, J., 2004. A scatter search method for the bi-criteria multi-dimensional {0,1}-knapsack problem using surrogate relaxation, Journal of Mathematical Modelling and Algorithms 3, 183-208.

Gomes da Silva, C., Climaco, J., Figueira, J., 2008. Core problems in bi-criteria {0, 1}-knapsack problems, Computers & Operations Research 35, 2292-2306.

Fréville A., 2004. The multidimensional 0-1 knapsack problem: An overview. European Journal of Operational Research 155, 1-21.

Kellerer, H., Pferschy U., Pisinger, D., 2004. Knapsack Problems. Springer. Berlin

Laumanns, M., Thiele, L., Zitzler, E., 2006. An efficient, adaptive parameter variation scheme for Metaheuristics based on the epsilon-constraint method. European Journal of Operational Research 169, 932-942.

Martello, S., Toth, P. A new algorithm for the 0-1 knapsack problem. Management Science 34, 633-644, 1988.

Martello, S., Toth., P., 1990. Knapsack problems - algorithms and computer implementations, Wiley, New York.

Mavrotas, G., 2000, Multiple Objective Programming under Uncertainty: Development of a Decision Support System and Implementation in Energy Planning. Ph.D. Thesis, National Technical University of Athens, Athens.

Mavrotas, G., Diakoulaki, D., 1998. A Branch and Bound Algorithm for Mixed Zero-One Multiple Objective Linear Programming. European Journal of Operational Research 107, 530-541.

Mavrotas, G., Diakoulaki, D., 2005. Multi-criteria branch & bound: a vector maximization algorithm for mixed 0-1 multiple objective linear programming. Applied Mathematics & Computation 171, 53-71.

Pisinger, D., 1995. Algorithms for Knapsack problems. Ph.D. Thesis.Dept. of Computer Science, University of Copenhagen.

Puchinger, J., Raidl, G.R., Pferschy, U., 2006. The core concept for the multidimensional knapsack problem, in: Gottileb, J. and Raidl, G.R. (eds.), LNCS 3906, pp.195-208.

Steuer, R.E. 1989. Multiple Criteria Optimization-Theory, Computation and Application (2nd ed). Krieger, Malabar FL.

Steuer, R.E., 1995. The ADBASE Multiple Objective Linear Programming Package. In: Gu J, Chen G, Wei Q, Wang S (ed) Multiple Criteria Decision Making. Windsor,England, pp. 1-6