The multiobjective multidimensional knapsack problem: a survey and a new approach
From MaRDI portal
Abstract: The knapsack problem (KP) and its multidimensional version (MKP) are basic problems in combinatorial optimization. In this paper we consider their multiobjective extension (MOKP and MOMKP), for which the aim is to obtain or to approximate the set of efficient solutions. In a first step, we classify and describe briefly the existing works, that are essentially based on the use of metaheuristics. In a second step, we propose the adaptation of the two-phase Pareto local search (2PPLS) to the resolution of the MOMKP. With this aim, we use a very-large scale neighborhood (VLSN) in the second phase of the method, that is the Pareto local search. We compare our results to state-of-the-art results and we show that we obtain results never reached before by heuristics, for the biobjective instances. Finally we consider the extension to three-objective instances.
Recommendations
- New perspectives on multi-objective knapsack problems
- Approximating multiobjective knapsack problems
- scientific article; zbMATH DE number 1830735
- scientific article; zbMATH DE number 1488081
- Some new results on multi-dimension Knapsack problem
- New greedy heuristics for the multiple-choice multi-dimensional knapsack problem
- Solving the bi-objective multi-dimensional knapsack problem exploiting the concept of core
- A ``reduce and solve approach for the multiple-choice multidimensional knapsack problem
Cites work
- scientific article; zbMATH DE number 4085440 (Why is no real title available?)
- scientific article; zbMATH DE number 3694968 (Why is no real title available?)
- scientific article; zbMATH DE number 1784663 (Why is no real title available?)
- scientific article; zbMATH DE number 3999655 (Why is no real title available?)
- scientific article; zbMATH DE number 1910919 (Why is no real title available?)
- scientific article; zbMATH DE number 915988 (Why is no real title available?)
- scientific article; zbMATH DE number 1423920 (Why is no real title available?)
- A Multiphase-Dual Algorithm for the Zero-One Integer Programming Problem
- A comparative study of multiple-objective metaheuristics on the bi-objective set covering problem and the Pareto memetic algorithm
- A scatter search method for bi-criteria \(\{0,1\}\)-knapsack problems
- A scatter search method for the bi-criteria multi-dimensional \(\{0,1\}\)-knapsack problem using surrogate relaxation
- A survey of very large-scale neighborhood search techniques
- An Algorithm for Large Zero-One Knapsack Problems
- An Effective Heuristic Algorithm for the Traveling-Salesman Problem
- An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method
- Analysis of a multiobjective evolutionary algorithm on the 0-1 knapsack problem
- Approximating multiobjective knapsack problems
- Bound sets for biobjective combinatorial optimization problems
- Core problems in bi-criteria \(\{0,1\}\)-knapsack problems
- Evolutionary Computation in Combinatorial Optimization
- Genetic local search for multi-objective combinatorial optimization
- Guided local search and its application to the traveling salesman problem
- Handbook of metaheuristics
- Implementing an efficient fptas for the 0-1 multi-objective knapsack problem
- Integrating partial optimization with scatter search for solving bi-criteria \({0, 1}\)-knapsack problems
- Local dominance and local recombination in MOEAs on \(0/1\) multiobjective knapsack problems
- MEMOTS: a memetic algorithm integrating tabu search for combinatorial multiobjective optimization
- MOSA method: a tool for solving multiobjective combinatorial optimization problems
- MOTGA: a multiobjective Tchebycheff based genetic algorithm for the multidimensional knapsack problem
- Metaheuristics. From design to implementation.
- Multi-start and path relinking methods to deal with multiobjective Knapsack problems
- Multiple criteria optimization: State of the art annotated bibliographic surveys
- Multi‐objective combinatorial optimization problems: A survey
- Nonlinear multiobjective optimization
- On a Bicriterion Formulation of the Problems of Integrated System Identification and System Optimization
- On the computational efficiency of multiple objective metaheuristics. The knapsack problem case study
- Optimization by ghost image processes in neural networks
- Pareto simulated annealing—a metaheuristic technique for multiple‐objective combinatorial optimization
- Solving bicriteria 0--1 knapsack problems using a labeling algorithm.
- Solving efficiently the 0-1 multi-objective knapsack problem
- Solving multiobjective, multiconstraint knapsack problems using mathematical programming and evolutionary algorithms
- Solving the bi-objective multi-dimensional knapsack problem exploiting the concept of core
- Solving the biobjective zero-one knapsack problem by an efficient LP-based heuristic
- Tabu search based procedure for solving the 0-1 multiobjective knapsack problem: The two objectives case
- Two-phase Pareto local search for the biobjective traveling salesman problem
- Two-phases method and branch and bound procedures to solve the bi-objective knapsack problem
Cited in
(36)- scientific article; zbMATH DE number 7368387 (Why is no real title available?)
- Bridging game theory and the knapsack problem: a theoretical formulation
- Learning-based multi-objective evolutionary algorithm for batching decision problem
- Variable and large neighborhood search to solve the multiobjective set covering problem
- A fuzzy programming approach to multiobjective multidimensional 0-1 knapsack problems
- New perspectives on multi-objective knapsack problems
- A cooperative swarm intelligence algorithm for multi-objective discrete optimization with application to the Knapsack problem
- Many-objective Pareto local search
- A decentralized heuristic for multiple-choice combinatorial optimization problems
- The binary knapsack problem with qualitative levels
- The multiple multidimensional knapsack with family-split penalties
- Optimal selection of touristic packages based on user preferences during sports mega-events
- Systematic reviews as a metaknowledge tool: caveats and a review of available options
- Anytime Pareto local search
- Surrogate upper bound sets for bi-objective bi-dimensional binary knapsack problems
- Knapsack problems -- an overview of recent advances. I: Single knapsack problems
- A decomposition approach for multidimensional knapsacks with family‐split penalties
- Multi-objective variable neighborhood search: an application to combinatorial optimization problems
- Robust efficiency measures for linear knapsack problem variants
- An improved version of the augmented \(\varepsilon\)-constraint method (AUGMECON2) for finding the exact Pareto set in multi-objective integer programming problems
- Approximate and exact merging of knapsack constraints with cover inequalities
- Ordinal optimization through multi-objective reformulation
- Choquet optimal set in biobjective combinatorial optimization
- Literature reviews in operations research: a new taxonomy and a meta review
- Network Models for Multiobjective Discrete Optimization
- Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems
- Cutting and surrogate constraint analysis for improved multidimensional knapsack solutions
- Proper balance between search towards and along Pareto front: biobjective TSP case study
- MOTGA: a multiobjective Tchebycheff based genetic algorithm for the multidimensional knapsack problem
- Balancing the profit and capacity under uncertainties: a target‐based distributionally robust knapsack problem
- scientific article; zbMATH DE number 5733644 (Why is no real title available?)
- A criterion space search algorithm for biobjective integer programming: the balanced box method
- Approximating multiobjective knapsack problems
- An improved version of a core based algorithm for the multi-objective multi-dimensional knapsack problem: a computational study and comparison with meta-heuristics
- Multi-start and path relinking methods to deal with multiobjective Knapsack problems
- Solving 0-1 bi-objective multi-dimensional knapsack problems using binary genetic algorithm
This page was built for publication: The multiobjective multidimensional knapsack problem: a survey and a new approach
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2865172)
