The knapsack problem with generalized upper bounds

DOI10.1016/0377-2217(89)90110-0MaRDI QIDQ1122484zbMATH OpenOpenAlexFDO

Authors Salah E. Elmaghraby

Publication date 1989

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0377-2217(89)90110-0

zbMATH Keywords

approximationenumerationgeneralized upper boundsknapsack problemproduction scheduling

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Production models (90B30) Deterministic scheduling theory in operations research (90B35) Integer programming (90C10) Dynamic programming (90C39)

Review text

A pipe production scheduling problem is modelled. The corresponding model is an integer programming problem with nonnegative coefficients in the constraints. The author calls it a knapsack problem with generalized upper bounds. Dynamic programming is used to achieve a solution. A knapsack problem solved by enumeration and approximation methods is applied as a subproblem.

Recommendations

• A new upper bound for the multiple knapsack problem
• Bounds for nested knapsack problems
• A solution procedure for general knapsack problems with a few constraints
• Publication:3481489
• Exact methods for the knapsack problem and its generalizations
• An algorithm for solving a class of knapsack problems and its generalization
• scientific article; zbMATH DE number 4189472
• scientific article; zbMATH DE number 4139486
• Upper Bounds and Algorithms for Hard 0-1 Knapsack Problems
• Improved lower and upper bounds for the number of feasible solutions to a knapsaek problem

Cites work

• A better step-off algorithm for the knapsack problem
• A heuristic solution of the rectangular cutting stock problem
• A note on the knapsack problem with special ordered sets
• A o(n logn) algorithm for LP knapsacks with GUB constraints
• An Algorithm for Large Zero-One Knapsack Problems
• Approximate Algorithms for the 0/1 Knapsack Problem
• APPROXIMATE ALGORITHMS FOR THE MULTIPLE-CHOICE CONTINUOUS KNAPSACK PROBLEMS
• Computational results with a branch-and-bound algorithm for the general knapsack problem
• Dynamic programming algorithms for the zero-one knapsack problem
• Experiments in integer programming
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Hard Knapsack Problems
• Heuristic algorithms for the multiple knapsack problem
• scientific article; zbMATH DE number 3687091 (Why is no real title available?)
• scientific article; zbMATH DE number 3694936 (Why is no real title available?)
• scientific article; zbMATH DE number 3599820 (Why is no real title available?)
• New Greedy-Like Heuristics for the Multidimensional 0-1 Knapsack Problem
• On the reduction method for integer linear programs. II
• Technical Note—The Multiperiod Knapsack Problem
• The imbedded state approach to reducing dimensionality in dynamic programs of higher dimensions
• The knapsack problem: A survey
• The Linear Multiple Choice Knapsack Problem
• The Multiple-Choice Knapsack Problem

Cited in

(5)

• Limiting the number of each piece in two-dimensional cutting stock patterns
• The continuous knapsack problem with capacities
• A well-solvable special case of the bounded knapsack problem
• scientific article; zbMATH DE number 431495 (Why is no real title available?)
• L-class enumeration algorithms for a discrete production planning problem with interval resource quantities

This page was built for publication: The knapsack problem with generalized upper bounds

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