Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
From MaRDI portal
Publication:3116647
DOI10.1287/mnsc.45.3.414zbMath1231.90338OpenAlexW2156293131WikidataQ58826501 ScholiaQ58826501MaRDI QIDQ3116647
David Pisinger, Silvano Martello, 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
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Multi-objective and goal programming (90C29) Combinatorial optimization (90C27)
Related Items
Sensitivity Analysis to Perturbations of the Weight of a Subset of Items: The Single Knapsack Case Study, A New Lagrangian Based Branch and Bound Algorithm for the 0-1 Knapsack Problem, Tight bounds on indefinite separable singly-constrained quadratic programs in linear-time, A modified descent method-based heuristic for binary quadratic knapsack problems with conflict graphs, Inversion of convection-diffusion equation with discrete sources, A dynamic programming algorithm for the bilevel Knapsack problem, An experimental study of random knapsack problems, A family of composite discrete bivariate distributions with uniform marginals for simulating realistic and challenging optimization-problem instances, A new class of hard problem instances for the 0-1 knapsack problem, A generalization of column generation to accelerate convergence, Decomposition based hybrid metaheuristics, Surrogate upper bound sets for bi-objective bi-dimensional binary knapsack problems, Knapsack problems -- an overview of recent advances. I: Single knapsack problems, Exact algorithms for the 0-1 time-bomb knapsack problem, A Branch-and-Price Algorithm for the Multiple Knapsack Problem, An exact decomposition algorithm for the generalized knapsack sharing problem, Robust efficiency measures for linear knapsack problem variants, Bilevel Knapsack with Interdiction Constraints, Smallest covering regions and highest density regions for discrete distributions, Exact solution of the robust knapsack problem, Heuristic and Exact Algorithms for the Interval Min–Max Regret Knapsack Problem, Integrating dock-door assignment and vehicle routing with cross-docking, A relax-and-cut framework for large-scale maximum weight connected subgraph problems, Exact approaches for the knapsack problem with setups, Integrated model for software component selection with simultaneous consideration of implementation and verification, On the product knapsack problem, Determining the \(K\)-best solutions of knapsack problems, Cutting plane versus compact formulations for uncertain (integer) linear programs, A Fast Large Neighborhood Search for Disjunctively Constrained Knapsack Problems, A branch-and-price algorithm for the capacitated facility location problem, New upper bounds and exact methods for the knapsack sharing problem, Exact makespan minimization of unrelated parallel machines, Exact algorithms for the bin packing problem with fragile objects, An exact algorithm for parallel machine scheduling with conflicts, Combinatorial Benders' Cuts for the Strip Packing Problem, Reduction strategies and exact algorithms for the disjunctively constrained knapsack problem, A weighted-sum method for solving the bi-objective traveling thief problem, Recent advances in selection hyper-heuristics, An effective dynamic programming algorithm for the minimum-cost maximal knapsack packing problem, Analysis of divide-and-conquer strategies for the \(0-1\) minimization knapsack problem, Tight bounds for the identical parallel machine‐scheduling problem: Part II, Lower and upper bounds for the bin packing problem with fragile objects, An exact approach for the bilevel knapsack problem with interdiction constraints and extensions, Dynamic programming based algorithms for the discounted \(\{0-1\}\) knapsack problem, Stochastic binary problems with simple penalties for capacity constraints violations, An exact algorithm for bilevel 0-1 knapsack problems, An exact algorithm for the 0-1 linear knapsack problem with a single continuous variable, Reliability aware scheduling of bag of real time tasks in cloud environment, Interdiction Games and Monotonicity, with Application to Knapsack Problems, An incentive dynamic programming method for the optimization of scholarship assignment, Enhanced Pseudo-polynomial Formulations for Bin Packing and Cutting Stock Problems, Branch-and-cut-and-price for capacitated connected facility location, Lock-free parallel dynamic programming, Algorithms for solving the single-sink fixed-charge transportation problem, An improved cut-and-solve algorithm for the single-source capacitated facility location problem, An optimization algorithm for a penalized knapsack problem, A best first search exact algorithm for the multiple-choice multidimensional knapsack problem, A dual RAMP algorithm for single source capacitated facility location problems, Core problems in bi-criteria \(\{0,1\}\)-knapsack problems, Sensitivity analysis of the optimum to perturbation of the profit of a subset of items in the binary knapsack problem, The packing while traveling problem, Tolerance analysis for 0-1 knapsack problems, Complexity results and exact algorithms for robust knapsack problems, A new exact approach for the 0-1 collapsing knapsack problem, A column generation heuristic for optimal wireless sensor network design with mobile sinks, A dynamic reformulation heuristic for generalized interdiction problems, Zero duality gap in surrogate constraint optimization: a concise review of models, LP bounds in various constraint programming approaches for orthogonal packing, Measuring instance difficulty for combinatorial optimization problems, An exact algorithm for the knapsack sharing problem, A note on upper bounds to the robust knapsack problem with discrete scenarios, An efficient algorithm for the collapsing knapsack problem, Where are the hard knapsack problems?, Stochastic set packing problem, A data mining-constraint satisfaction optimization problem for cost effective classification, Revisiting \textit{where are the hard knapsack problems?} Via instance space analysis, The bilevel knapsack problem with stochastic right-hand sides, A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts, A reactive local search-based algorithm for the multiple-choice multi-dimensional knapsack problem, A fast exact method for the capacitated facility location problem with differentiable convex production costs, Sensitivity of the optimum to perturbations of the profit or weight of an item in the binary Knapsack problem, Optimization algorithms for the disjunctively constrained knapsack problem, A computational comparison of flow formulations for the capacitated location-routing problem, Sensitivity analysis to perturbations of the weight of a subset of items: the knapsack case study, A faster FPTAS for knapsack problem with cardinality constraint, A 0-1 knapsack model for evaluating the possible electoral college performance in two-party US presidential elections, A hybrid algorithm for the unbounded knapsack problem, A Simple but Usually Fast Branch-and-Bound Algorithm for the Capacitated Facility Location Problem, Semi-Infinite Relaxations for the Dynamic Knapsack Problem with Stochastic Item Sizes, Solving robust bin-packing problems with a branch-and-price approach, A branch-and-price algorithm for the two-dimensional level strip packing problem, New trends in exact algorithms for the \(0-1\) knapsack problem, A cooperative local search-based algorithm for the multiple-scenario max-min knapsack problem, Two-machine shop scheduling: Compromise between flexibility and makespan value, Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems, Approximate and exact algorithms for the fixed-charge knapsack problem, Branch-and-price algorithms for the dual bin packing and maximum cardinality bin packing problem, Submodular maximization of concave utility functions composed with a set-union operator with applications to maximal covering location problems, Exploring search space trees using an adapted version of Monte Carlo tree search for combinatorial optimization problems, On the exact separation of cover inequalities of maximum-depth, A novel reformulation for the single-sink fixed-charge transportation problem, A binary search algorithm for the general coupled task scheduling problem, Exact methods for discrete \({\varGamma}\)-robust interdiction problems with an application to the bilevel knapsack problem, Balanced-evolution genetic algorithm for combinatorial optimization problems: the general outline and implementation of balanced-evolution strategy based on linear diversity index, A fast combinatorial algorithm for the bilevel knapsack problem with interdiction constraints, Mixed integer bilevel optimization with a \(k\)-optimal follower: a hierarchy of bounds, Hybrid branch-and-price-and-cut algorithm for the two-dimensional vector packing problem with time windows, Optimizing a multi-echelon location-inventory problem with joint replenishment: a Lipschitz \(\epsilon\)-optimal approach using Lagrangian relaxation, A general purpose exact solution method for mixed integer concave minimization problems, Solving the skiving stock problem by a combination of stabilized column generation and the reflect arc-flow model, An exact method for binary fortification games, Features for the 0-1 knapsack problem based on inclusionwise maximal solutions, Solving the temporal knapsack problem via recursive Dantzig-Wolfe reformulation, A faster FPTAS for knapsack problem with cardinality constraint
Uses Software
