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)

• 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
• Approximate And Exact Solution Methods For The Hyperbolic 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
• A faster FPTAS for knapsack problem with cardinality constraint
• A faster FPTAS for knapsack problem with cardinality constraint
• Learning generalized strong branching for set covering, set packing, and 0-1 knapsack problems
• Recent advances in selection hyper-heuristics
• A fast exact method for the capacitated facility location problem with differentiable convex production costs
• Exact methods for discrete \({\varGamma}\)-robust interdiction problems with an application to the bilevel knapsack problem
• A fast combinatorial algorithm for the bilevel knapsack problem with interdiction constraints
• An exact approach for the bilevel knapsack problem with interdiction constraints and extensions
• Knapsack problems -- an overview of recent advances. I: Single knapsack problems
• Exact algorithms for the 0-1 time-bomb knapsack problem
• Analysis of divide-and-conquer strategies for the \(0-1\) minimization knapsack problem
• A relax-and-cut framework for large-scale maximum weight connected subgraph problems
• Solving robust bin-packing problems with a branch-and-price approach
• Mixed integer bilevel optimization with a \(k\)-optimal follower: a hierarchy of bounds
• A rigorous method for solving 0-1 polynomial knapsack problem
• Revisiting \textit{Where are the hard knapsack problems?} via instance space analysis
• Computing and Selecting ε-Efficient Solutions of {0, 1}-Knapsack Problems
• Smallest covering regions and highest density regions for discrete distributions
• A dual RAMP algorithm for single source capacitated facility location problems
• Algorithms for some hard knapsack problems
• A branch-and-price algorithm for the two-dimensional level strip packing problem
• Branch-and-bound and dynamic programming approaches for the knapsack problem
• A computational note on the Martello-Toth knapsack algorithm
• A weighted-sum method for solving the bi-objective traveling thief problem
• Enhanced Pseudo-polynomial Formulations for Bin Packing and Cutting Stock Problems
• Balanced-evolution genetic algorithm for combinatorial optimization problems: the general outline and implementation of balanced-evolution strategy based on linear diversity index
• Expectation analysis for bounding solutions of the 0-1 knapsack problem
• Optimization algorithms for the disjunctively constrained knapsack problem
• An effective dynamic programming algorithm for the minimum-cost maximal knapsack packing problem
• Interdiction Games and Monotonicity, with Application to Knapsack Problems
• Title not available (Why is that?)
• An Algorithm for the 0-1 Equality Knapsack Problem
• A practical approach for dealing with hard knapsack problems using general-purpose integer programming software
• Hybrid branch-and-price-and-cut algorithm for the two-dimensional vector packing problem with time windows
• Zero duality gap in surrogate constraint optimization: a concise review of models
• Title not available (Why is that?)
• Heuristic and Exact Algorithms for the Interval Min–Max Regret Knapsack Problem
• Tight bounds on indefinite separable singly-constrained quadratic programs in linear-time
• A novel reformulation for the single-sink fixed-charge transportation problem
• Enhanced capacitated facility location problem for mental accounting management using partial resource concentration
• The daily swab test collection problem
• A new exact approach for the 0-1 collapsing knapsack problem
• High-Dimensional Cost-constrained Regression Via Nonconvex Optimization
• Semi-infinite relaxations for the dynamic knapsack problem with stochastic item sizes
• 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

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)