Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem

DOI10.1287/MNSC.45.3.414zbMATH Open1231.90338OpenAlexW2156293131WikidataQ58826501 ScholiaQ58826501MaRDI QIDQ3116647FDOQ3116647

Authors: Silvano Martello, David Pisinger, Paolo Toth 

Publication date: 12 February 2012

Published in: Management Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/mnsc.45.3.414

Recommendations

• scientific article; zbMATH DE number 6869279
• Dynamic programming based algorithms for the discounted \(\{0-1\}\) knapsack problem
• Upper Bounds and Algorithms for Hard 0-1 Knapsack Problems
• Improved dynamic programming and approximation results for the knapsack problem with setups
• A dynamic programming algorithm for the discounted \(\{0 - 1\}\) knapsack problem with setup
• The multidimensional 0-1 knapsack problem -- bounds and computational aspects
• \(0\)-\(1\) knapsack problems
• Publication:3481489
• Bounds for nested knapsack problems
• Computing and Selecting ε-Efficient Solutions of {0, 1}-Knapsack Problems

zbMATH Keywords

dynamic programmingknapsack problembranch-and-boundsurrogate relaxation

Mathematics Subject Classification ID

Multi-objective and goal programming (90C29) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Cited In (only showing first 100 items - show all)

• Sensitivity analysis of the optimum to perturbation of the profit of a subset of items in the binary knapsack problem
• Branch-and-price algorithms for the dual bin packing and maximum cardinality bin packing problem
• An Exact Algorithm for the Two-Constraint 0–1 Knapsack Problem
• Cutting plane versus compact formulations for uncertain (integer) linear programs
• \(0\)-\(1\) knapsack problems
• A modified descent method-based heuristic for binary quadratic knapsack problems with conflict graphs
• Lower and upper bounds for the bin packing problem with fragile objects
• An exact algorithm for bilevel 0-1 knapsack problems
• Sensitivity of the optimum to perturbations of the profit or weight of an item in the binary Knapsack problem
• The bilevel knapsack problem with stochastic right-hand sides
• An exact algorithm for the Knapsack problem with setup
• Approximate and exact algorithms for the fixed-charge knapsack problem
• An exact algorithm for 0-1 polynomial Knapsack problems
• Sensitivity analysis to perturbations of the weight of a subset of items: the knapsack case study
• Algorithms for solving the single-sink fixed-charge transportation problem
• A binary search algorithm for the general coupled task scheduling problem
• Inversion of convection-diffusion equation with discrete sources
• A New Algorithm for the 0-1 Knapsack Problem
• Title not available (Why is that?)
• Stochastic set packing problem
• A hybrid algorithm for the unbounded knapsack problem
• Exact solution of the robust knapsack problem
• An incentive dynamic programming method for the optimization of scholarship assignment
• Dynamic programming based algorithms for the discounted \(\{0-1\}\) knapsack problem
• Where are the hard knapsack problems?
• Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems
• Sensitivity analysis to perturbations of the weight of a subset of items: the single knapsack case study
• A dynamic programming algorithm for the bilevel Knapsack problem
• Decomposition based hybrid metaheuristics
• Surrogate upper bound sets for bi-objective bi-dimensional binary knapsack problems
• A branch-and-price algorithm for the capacitated facility location problem
• A cooperative local search-based algorithm for the multiple-scenario max-min knapsack problem
• An exact decomposition algorithm for the generalized knapsack sharing problem
• Robust efficiency measures for linear knapsack problem variants
• LP bounds in various constraint programming approaches for orthogonal packing
• A data mining-constraint satisfaction optimization problem for cost effective classification
• Title not available (Why is that?)
• Two-machine shop scheduling: Compromise between flexibility and makespan value
• Combinatorial Benders' cuts for the strip packing problem
• A 0-1 knapsack model for evaluating the possible electoral college performance in two-party US presidential elections
• New trends in exact algorithms for the \(0-1\) knapsack problem
• Measuring instance difficulty for combinatorial optimization problems
• Reduction strategies and exact algorithms for the disjunctively constrained knapsack problem
• A simple but usually fast branch-and-bound algorithm for the capacitated facility location problem
• A generalization of column generation to accelerate convergence
• A computational comparison of flow formulations for the capacitated location-routing problem
• Integrated model for software component selection with simultaneous consideration of implementation and verification
• An exact algorithm for large unbounded knapsack problems
• Determining the \(K\)-best solutions of knapsack problems
• Stochastic binary problems with simple penalties for capacity constraints violations
• A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts
• Tight bounds for the identical parallel machine‐scheduling problem: Part II
• A column generation heuristic for optimal wireless sensor network design with mobile sinks
• Optimizing a multi-echelon location-inventory problem with joint replenishment: a Lipschitz \(\epsilon\)-optimal approach using Lagrangian relaxation
• Integrating dock-door assignment and vehicle routing with cross-docking
• Branch-and-cut-and-price for capacitated connected facility location
• Complexity results and exact algorithms for robust knapsack problems
• A note on upper bounds to the robust knapsack problem with discrete scenarios
• An exact algorithm for the 0-1 linear knapsack problem with a single continuous variable
• An experimental study of random knapsack problems
• A dynamic reformulation heuristic for generalized interdiction problems
• A best first search exact algorithm for the multiple-choice multidimensional knapsack problem
• Core problems in bi-criteria \(\{0,1\}\)-knapsack problems
• An exact algorithm for the knapsack sharing problem
• A reactive local search-based algorithm for the multiple-choice multi-dimensional knapsack problem
• Exact algorithms for the bin packing problem with fragile objects
• A new Lagrangian based branch and bound algorithm for the 0-1 knapsack problem
• Lock-free parallel dynamic programming
• An improved cut-and-solve algorithm for the single-source capacitated facility location problem
• Dynamic programming revisited: Improving knapsack algorithms
• On the product knapsack problem
• Reoptimizing the 0-1 knapsack problem
• Solving the temporal knapsack problem via recursive Dantzig-Wolfe reformulation
• The packing while traveling problem
• Solving the skiving stock problem by a combination of stabilized column generation and the reflect arc-flow model
• New upper bounds and exact methods for the knapsack sharing problem
• An optimization algorithm for a penalized knapsack problem
• Title not available (Why is that?)
• Submodular maximization of concave utility functions composed with a set-union operator with applications to maximal covering location problems
• A note on the Martello-Toth algorithm for one-dimensional knapsack problems
• Exact makespan minimization of unrelated parallel machines
• Reliability aware scheduling of bag of real time tasks in cloud environment
• Title not available (Why is that?)
• A unified pre-training and adaptation framework for combinatorial optimization on graphs
• A general purpose exact solution method for mixed integer concave minimization problems
• Exploring search space trees using an adapted version of Monte Carlo tree search for combinatorial optimization problems
• A new class of hard problem instances for the 0-1 knapsack problem
• An efficient algorithm for the collapsing knapsack problem
• On the exact separation of cover inequalities of maximum-depth
• A fast large neighborhood search for disjunctively constrained knapsack problems
• Bilevel knapsack with interdiction constraints
• Exact approaches for the knapsack problem with setups
• An exact algorithm for parallel machine scheduling with conflicts
• Tolerance analysis for 0-1 knapsack problems
• A family of composite discrete bivariate distributions with uniform marginals for simulating realistic and challenging optimization-problem instances
• An exact method for binary fortification games
• On the Dietrich-Escudero approach for solving the \(0-1\) knapsack problem with a \(0-1\) objective function
• Features for the 0-1 knapsack problem based on inclusionwise maximal solutions
• Title not available (Why is that?)
• A Branch-and-Price Algorithm for the Multiple Knapsack Problem

Uses Software

• Knapsack

This page was built for publication: Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3116647)