A Minimal Algorithm for the 0-1 Knapsack Problem
From MaRDI portal
Publication:4393123
DOI10.1287/opre.45.5.758zbMath0902.90126OpenAlexW1966693694WikidataQ58826514 ScholiaQ58826514MaRDI QIDQ4393123
Publication date: 10 August 1998
Published in: Operations Research (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/8dcdff6a283a7961ccc8be089533d79c9f66e80a
Large-scale problems in mathematical programming (90C06) Integer programming (90C10) Dynamic programming (90C39) Boolean programming (90C09)
Related Items (76)
An exact algorithm for large knapsack sharing problems ⋮ Exactly solving a two-level location problem with modular node capacities ⋮ Robust optimization approach for a chance-constrained binary knapsack problem ⋮ A family of composite discrete bivariate distributions with uniform marginals for simulating realistic and challenging optimization-problem instances ⋮ New exact approaches and approximation results for the penalized knapsack problem ⋮ A new class of hard problem instances for the 0-1 knapsack problem ⋮ An approach to the asymmetric multi-depot capacitated arc routing problem ⋮ Surrogate upper bound sets for bi-objective bi-dimensional binary knapsack problems ⋮ An exact decomposition algorithm for the generalized knapsack sharing problem ⋮ Robust efficiency measures for linear knapsack problem variants ⋮ Separation algorithms for 0-1 knapsack polytopes ⋮ An implementation of exact knapsack separation ⋮ Choquet optimal set in biobjective combinatorial optimization ⋮ Bi-dimensional knapsack problems with one soft constraint ⋮ Combined cutting stock and lot-sizing problem with pattern setup ⋮ A dynamic programming algorithm for the knapsack problem with setup ⋮ A cutting plane method for knapsack polytope ⋮ Exact makespan minimization of unrelated parallel machines ⋮ Algorithmic improvements on dynamic programming for the bi-objective \(\{0,1\}\) knapsack problem ⋮ Model and algorithms for multi-period sea cargo mix problem ⋮ The quadratic knapsack problem -- a survey ⋮ A Progressive Approximation Approach for the Exact Solution of Sparse Large-Scale Binary Interdiction Games ⋮ Exact Approaches for Single Machine Total Weighted Tardiness Batch Scheduling ⋮ An exact algorithm for large multiple knapsack problems ⋮ Avoiding anomalies in the \(MT2\) algorithm by Martello and Toth ⋮ A novel reformulation for the single-sink fixed-charge transportation problem ⋮ Bin Packing Problem with Time Lags ⋮ Multi-objective unconstrained combinatorial optimization: a polynomial bound on the number of extreme supported solutions ⋮ LP relaxation and dynamic programming enhancing VNS for the multiple knapsack problem with setup ⋮ An exact approach for the bilevel knapsack problem with interdiction constraints and extensions ⋮ Features for the 0-1 knapsack problem based on inclusionwise maximal solutions ⋮ Dynamic programming based algorithms for the discounted \(\{0-1\}\) knapsack problem ⋮ Discrete facility location and routing of obnoxious activities. ⋮ Column generation for extended formulations ⋮ The inverse \(\{0,1\}\)-knapsack problem: theory, algorithms and computational experiments ⋮ Automation and Combination of Linear-Programming Based Stabilization Techniques in Column Generation ⋮ Exact algorithms for the joint object placement and request routing problem in content distribution networks ⋮ Primal Heuristics for Branch and Price: The Assets of Diving Methods ⋮ An incentive dynamic programming method for the optimization of scholarship assignment ⋮ Lifting of probabilistic cover inequalities ⋮ Exact algorithms for unconstrained three-dimensional cutting problems: A comparative study ⋮ Solving the swath segment selection problem through Lagrangean relaxation ⋮ A dynamic programming based reduction procedure for the multidimensional 0-1 knapsack problem ⋮ Algorithms for solving the single-sink fixed-charge transportation problem ⋮ An optimization algorithm for a penalized knapsack problem ⋮ A best first search exact algorithm for the multiple-choice multidimensional knapsack problem ⋮ Core problems in bi-criteria \(\{0,1\}\)-knapsack problems ⋮ The multi-band robust knapsack problem -- a dynamic programming approach ⋮ Tolerance analysis for 0-1 knapsack problems ⋮ Heuristic approaches for the two- and three-dimensional knapsack packing problem ⋮ A cut and branch approach for the capacitated \(p\)-median problem based on Fenchel cutting planes ⋮ An exact method with variable fixing for solving the generalized assignment problem ⋮ Two heuristics for the capacitated multi-period cutting stock problem with pattern setup cost ⋮ A computational study of exact knapsack separation for the generalized assignment problem ⋮ An efficient algorithm for the collapsing knapsack problem ⋮ Where are the hard knapsack problems? ⋮ Outbound supply chain network design with mode selection, lead times and capacitated vehicle distribution centers ⋮ Tree knapsack approaches for local access network design ⋮ Revisiting \textit{where are the hard knapsack problems?} Via instance space analysis ⋮ An exact algorithm for the subset sum problem ⋮ A reactive local search-based algorithm for the multiple-choice multi-dimensional knapsack problem ⋮ An improved Lagrangian relaxation and dual ascent approach to facility location problems ⋮ Solving bin packing problems using VRPSolver models ⋮ Maximum probabilistic all-or-nothing paths ⋮ An Exact Algorithm for the Multiple-Choice Multidimensional Knapsack Based on the Core ⋮ A branch-and-price algorithm for the two-dimensional level strip packing problem ⋮ An efficient algorithm of dead-end controls for solving combinatorial optimization problems ⋮ A fast algorithm for strongly correlated knapsack problems ⋮ 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 ⋮ Heuristic and exact reduction procedures to solve the discounted 0-1 knapsack problem ⋮ Integrating workload smoothing and inventory reduction in three intermodal logistics platforms of a European car manufacturer ⋮ Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems ⋮ Approximate and exact algorithms for the fixed-charge knapsack problem ⋮ Heuristics for the container loading problem ⋮ Exploring search space trees using an adapted version of Monte Carlo tree search for combinatorial optimization problems
Uses Software
This page was built for publication: A Minimal Algorithm for the 0-1 Knapsack Problem
