Knapsack Problems : Algorithms and Computer Implementations

Hoboken, NJ, U.S.A.: John Wiley & Sons, Incorporated, 1990. Clock & Rose Press, 2018. Reprint. Hard cover, 308 pp. Includes diskette with implementations. This book presents a state-of-the-art (as of 1990) on exact and approximate algorithms for a number of important NP-hard problems in the field of linear programming which are grouped under the term "knapsack". The reader will find not only the "classical" knapsack problems (binary, bounded, unbounded, binary multiple), but also less familiar problems (subset-sum, change-making) or well-known problems (fractional, multidimensional, non-linear) and only a limited treatment of the case of generalized upper bound constraints. For each problem, the authors give a mathematical model, discussing its relaxations and deriving procedures for the computation of bounds. They then develop approximate algorithms, approximination schemes, dynamic programming techniques and brand-and-bound algorithms. They analyze the computational complexity and the worst-case performance of bounds and approximate methods. The average performance of the computer implementations of exact and approximate algorithms is finally examined through extensive computational experiments. The Fortran codes implementing the most effective methods are provided in the included diskette. New book and CD.. Reprint. Hard Cover. New. 8vo - over 7¾" - 9¾" tall.