A new enumeration scheme for the knapsack problem

DOI10.1016/0166-218X(87)90024-2zbMath0631.90044MaRDI QIDQ1095029

Nei Yoshihiro Soma, Horacio Hideki Yanasse

Publication date: 1987

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

enumeration; linear diophantine equations; one-dimensional knapsack problem; pseudopolynomial

Mathematics Subject Classification ID

90C10: Integer programming

11D04: Linear Diophantine equations

Related Items

Checkerboard pattern: proposals for its generation, An algorithm for determining the K-best solutions of the one-dimensional Knapsack problem, A new lower bound for the linear knapsack problem with general integer variables, A relation between the knapsack and group knapsack problems, On dominated terms in the general knapsack problem, The one dimensional Compartmentalised Knapsack problem: a case study, Solving Medium-Density Subset Sum Problems in Expected Polynomial Time: An Enumeration Approach

Uses Software

• Algorithm 37

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Dynamic programming algorithms for the zero-one knapsack problem
• An algorithm for the solution of the 0-1 knapsack problem
• An upper bound for the zero-one knapsack problem and a branch and bound algorithm
• Algorithm 37. Algorithm for the solution of the 0-1 single Knapsack problem
• An algorithm for the computation of knapsack functions
• Technical Note—Computational Viability of a Constraint Aggregation Scheme for Integer Linear Programming Problems
• Worst-case analysis of greedy algorithms for the subset-sum problem
• Polynomial-Time Aggregation of Integer Programming Problems
• Fast Approximation Algorithms for Knapsack Problems
• Hard Knapsack Problems
• An Algorithm for Large Zero-One Knapsack Problems
• The knapsack problem: A survey
• Resolution of the 0–1 knapsack problem: Comparison of methods
• Merging and Sorting Applied to the Zero-One Knapsack Problem
• Computing Partitions with Applications to the Knapsack Problem
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Approximate Algorithms for the 0/1 Knapsack Problem
• Computational results with a branch-and-bound algorithm for the general knapsack problem
• Shortest-Route Methods: 2. Group Knapsacks, Expanded Networks, and Branch-and-Bound
• A Linear Programming Approach to the Cutting Stock Problem—Part II
• Multistage Cutting Stock Problems of Two and More Dimensions
• Discrete-Variable Extremum Problems
• A Finite Renewal Algorithm for the Knapsack and Turnpike Models
• The Theory and Computation of Knapsack Functions
• Bounds on Multiprocessing Timing Anomalies
• Technical Note—Solution of the Value-Independent Knapsack Problem by Partitioning