Algorithmic improvements on dynamic programming for the bi-objective \(\{0,1\}\) knapsack problem

DOI10.1007/s10589-013-9551-xzbMath1276.90057OpenAlexW2020127609MaRDI QIDQ360382

Marco Simões, Luís Paquete, Daniel Vanderpooten, José Rui Figueira

Publication date: 26 August 2013

Published in: Computational Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10589-013-9551-x

zbMATH Keywords

multi-objective combinatorial optimizationbi-objective \{0,1\} knapsack problemsbi-objective simplex algorithmbounds setsdichotomic search

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Dynamic programming (90C39)

Related Items (11)

Dynamic programming algorithms for the bi-objective integer knapsack problem ⋮ Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems ⋮ Solution approaches for equitable multiobjective integer programming problems ⋮ Bi-dimensional knapsack problems with one soft constraint ⋮ Compressed data structures for bi-objective \(\{0,1\}\)-knapsack problems ⋮ Network Models for Multiobjective Discrete Optimization ⋮ Computing representations using hypervolume scalarizations ⋮ Ordinal optimization through multi-objective reformulation ⋮ Bridging game theory and the knapsack problem: a theoretical formulation ⋮ Finding multi-objective supported efficient spanning trees ⋮ A reduction dynamic programming algorithm for the bi-objective integer knapsack problem

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Integrating partial optimization with scatter search for solving bi-criteria \({0, 1}\)-knapsack problems
• Bound sets for biobjective combinatorial optimization problems
• Solving efficiently the 0-1 multi-objective knapsack problem
• Implementing an efficient fptas for the 0-1 multi-objective knapsack problem
• 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.
• A bicriteria knapsack program for planning remediation of contaminated lightstation sites
• Relocation problems arising in conservation biology
• Core problems in bi-criteria \(\{0,1\}\)-knapsack problems
• A scatter search method for bi-criteria \(\{0,1\}\)-knapsack problems
• Approximating Multiobjective Knapsack Problems
• Discrete Dynamic Programming and Capital Allocation
• Generating the Discrete Efficient Frontier to the Capital Budgeting Problem
• Bicriteria Transportation Problem
• A Minimal Algorithm for the 0-1 Knapsack Problem

This page was built for publication: Algorithmic improvements on dynamic programming for the bi-objective \(\{0,1\}\) knapsack problem