𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the determination of the upper bound for the knapsack problem with additional constraints

✍ Scribed by B. G. Litvak; A. V. Naivel't

Publisher
Springer US
Year
1973
Tongue
English
Weight
121 KB
Volume
7
Category
Article
ISSN
1573-8337

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Calculating the upper bound of the Multi
Calculating the upper bound of the Multiple-Choice Knapsack Problem
✍ Yuji Nakagawa; Masachika Kitao; Mitsuhiro Tsuji; Yoshinobu Teraoka πŸ“‚ Article πŸ“… 2001 πŸ› John Wiley and Sons 🌐 English βš– 179 KB

## Abstract An upper bound or a lower bound of the Multiple‐Choice Knapsack Problem can be calculated by solving LP relaxation. In 1979, Sinha and Zoltners proposed a branch‐and‐bound algorithm for solving the Multiple‐Choice Knapsack Problem, and provided a method to obtain the strict upper bound.

The critical-item, upper bounds, and a b
The critical-item, upper bounds, and a branch-and-bound algorithm for the tree knapsack problem
✍ Shaw, Dong X.; Cho, Geon πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 155 KB πŸ‘ 2 views

The tree knapsack problem (TKP) is a generalized 0-1 knapsack problem where all the items (nodes) are subjected to a partial ordering represented by a rooted tree. If a node is selected to be packed into the knapsack, then all the items on the path from the selected node to the root must also be pac

An efficient algorithm for the Lagrangea
An efficient algorithm for the Lagrangean dual of nonlinear knapsack problems with additional nested constraints
✍ W.O. Riha; J. Walker πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 471 KB

This paper presents an efficient algorithm for solving the Lagrangean dual of nonlinear knapsack problems with additional nested constraints. The dual solution provides a feasible primal solution (if it exists) and associated lower and upper bounds on the optimal objective function value of the prim