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
- A comparative study of multiple-objective metaheuristics on the bi-objective set covering problem and the Pareto memetic algorithm
- A Multiphase-Dual Algorithm for the Zero-One Integer Programming Problem
- 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
- 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?)
- 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
- Metaheuristics. From design to implementation.
- MOSA method: a tool for solving multiobjective combinatorial optimization problems
- MOTGA: a multiobjective Tchebycheff based genetic algorithm for the multidimensional knapsack problem
- 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
(37)- A fuzzy programming approach to multiobjective multidimensional 0-1 knapsack problems
- Many-objective Pareto local search
- A cooperative swarm intelligence algorithm for multi-objective discrete optimization with application to the Knapsack problem
- Cutting and surrogate constraint analysis for improved multidimensional knapsack solutions
- Bridging game theory and the knapsack problem: a theoretical formulation
- An improved version of the augmented \(\varepsilon\)-constraint method (AUGMECON2) for finding the exact Pareto set in multi-objective integer programming problems
- The binary knapsack problem with qualitative levels
- The multiple multidimensional knapsack with family-split penalties
- Solving 0-1 bi-objective multi-dimensional knapsack problems using binary genetic algorithm
- Learning-based multi-objective evolutionary algorithm for batching decision problem
- Knapsack problems -- an overview of recent advances. I: Single knapsack problems
- Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems
- Variable and large neighborhood search to solve the multiobjective set covering problem
- Proper balance between search towards and along Pareto front: biobjective TSP case study
- Optimal selection of touristic packages based on user preferences during sports mega-events
- A criterion space search algorithm for biobjective integer programming: the balanced box method
- Approximating multiobjective knapsack problems
- Anytime Pareto local search
- Surrogate upper bound sets for bi-objective bi-dimensional binary knapsack problems
- Robust efficiency measures for linear knapsack problem variants
- Choquet optimal set in biobjective combinatorial optimization
- scientific article; zbMATH DE number 5733644 (Why is no real title available?)
- scientific article; zbMATH DE number 1488081 (Why is no real title available?)
- New perspectives on multi-objective knapsack problems
- scientific article; zbMATH DE number 7368387 (Why is no real title available?)
- Network Models for Multiobjective Discrete Optimization
- Approximate and exact merging of knapsack constraints with cover inequalities
- A decentralized heuristic for multiple-choice combinatorial optimization problems
- Systematic reviews as a metaknowledge tool: caveats and a review of available options
- Balancing the profit and capacity under uncertainties: a target‐based distributionally robust knapsack problem
- Ordinal optimization through multi-objective reformulation
- Literature reviews in operations research: a new taxonomy and a meta review
- A decomposition approach for multidimensional knapsacks with family‐split penalties
- An improved version of a core based algorithm for the multi-objective multi-dimensional knapsack problem: a computational study and comparison with meta-heuristics
- MOTGA: a multiobjective Tchebycheff based genetic algorithm for the multidimensional knapsack problem
- Multi-objective variable neighborhood search: an application to combinatorial optimization problems
- Multi-start and path relinking methods to deal with multiobjective Knapsack problems
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)
