A reduction dynamic programming algorithm for the bi-objective integer knapsack problem

DOI10.1016/j.ejor.2013.05.045zbMath1317.90270OpenAlexW2042516553MaRDI QIDQ2356097

Aiying Rong, José Rui Figueira

Publication date: 28 July 2015

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2013.05.045

zbMATH Keywords

dynamic programmingmulti-objective programmingstate reductiondominance relationcore conceptinteger knapsack problem

Mathematics Subject Classification ID

Integer programming (90C10) Multi-objective and goal programming (90C29) Combinatorial optimization (90C27) Dynamic programming (90C39)

Related Items (7)

Dynamic programming algorithms for the bi-objective integer knapsack problem ⋮ Route-reduction-based dynamic programming for large-scale satellite range scheduling problem ⋮ An enhanced branch-and-bound algorithm for the talent scheduling problem ⋮ An improved version of a core based algorithm for the multi-objective multi-dimensional knapsack problem: a computational study and comparison with meta-heuristics ⋮ A branch-and-bound based heuristic algorithm for convex multi-objective MINLPs ⋮ An exact algebraic \(\epsilon \)-constraint method for bi-objective linear integer programming based on test sets ⋮ Heuristic and exact reduction procedures to solve the discounted 0-1 knapsack problem

Uses Software

• MOTGA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithmic improvements on dynamic programming for the bi-objective \(\{0,1\}\) knapsack problem
• Dynamic programming based algorithms for the discounted \(\{0-1\}\) knapsack problem
• A two phase method for multi-objective integer programming and its application to the assignment problem with three objectives
• Computational performance of basic state reduction based dynamic programming algorithms for bi-objective 0-1 knapsack problems
• Using the idea of expanded core for the exact solution of bi-objective multi-dimensional knapsack problems
• A two state reduction based dynamic programming algorithm for the bi-objective \(0\)-\(1\) knapsack problem
• A scatter search method for the bi-criteria multi-dimensional \(\{0,1\}\)-knapsack problem using surrogate relaxation
• Multicriteria branch and bound: a vector maximization algorithm for mixed 0-1 multiple objective linear programming
• Integrating partial optimization with scatter search for solving bi-criteria \({0, 1}\)-knapsack problems
• A method for finding well-dispersed subsets of non-dominated vectors for multiple objective mixed integer linear programs
• MOTGA: a multiobjective Tchebycheff based genetic algorithm for the multidimensional knapsack problem
• Solving efficiently the 0-1 multi-objective knapsack problem
• Using support vector machines to learn the efficient set in multiple objective discrete optimization
• Exact algorithm for bi-objective 0-1 knapsack problem
• Implementing an efficient fptas for the 0-1 multi-objective knapsack problem
• Labeling algorithms for multiple objective integer knapsack problems
• Multi-objective integer programming: a general approach for generating all non-dominated solutions
• Solving multiobjective, multiconstraint knapsack problems using mathematical programming and evolutionary algorithms
• Solving the bi-objective multi-dimensional knapsack problem exploiting the concept of core
• Heuristic algorithms for the multiple knapsack problem
• A reduction algorithm for integer multiple objective linear programs
• Two-phases method and branch and bound procedures to solve the bi-objective knapsack problem
• Solving bicriteria 0--1 knapsack problems using a labeling algorithm.
• Unbounded knapsack problem: Dynamic programming revisited
• Tabu search based procedure for solving the 0-1 multiobjective knapsack problem: The two objectives case
• A bicriteria knapsack program for planning remediation of contaminated lightstation sites
• Greedy algorithms for a class of knapsack problems with binary weights
• A method for finding the set of non-dominated vectors for multiple objective integer linear programs
• A survey and annotated bibliography of multiobjective combinatorial optimization
• On the computational efficiency of multiple objective metaheuristics. The knapsack problem case study
• Solving the biobjective zero-one knapsack problem by an efficient LP-based heuristic
• Relocation problems arising in conservation biology
• \(K\)-PPM: a new exact method to solve multi-objective combinatorial optimization problems
• Core problems in bi-criteria \(\{0,1\}\)-knapsack problems
• A scatter search method for bi-criteria \(\{0,1\}\)-knapsack problems
• An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method
• Approximating the nondominated frontiers of multi‐objective combinatorial optimization problems
• A New Algorithm for the 0-1 Knapsack Problem
• Generating the Discrete Efficient Frontier to the Capital Budgeting Problem
• An Algorithm for Large Zero-One Knapsack Problems
• Multicriteria integer programming: A (hybrid) dynamic programming recursive approach
• A General Algorithm for One-Dimensional Knapsack Problems
• Multi‐objective combinatorial optimization problems: A survey
• Multicriteria Optimization
• Multi-objective meta-heuristics: An overview of the current state-of-the-art

This page was built for publication: A reduction dynamic programming algorithm for the bi-objective integer knapsack problem