The Theory and Computation of Knapsack Functions

In earlier papers on the cutting stock problem we indicated the desirability of developing fast methods for computing knapsack functions. A one-dimensional knapsack function is defined by: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}$$f(x)= \max \{\Pi_{1} Z_{1} + \cdots + \Pi_{m}Z_{m};\enspace l_{1}Z_{1} + \cdots + l_{M}Z_{m}\leq x,\; Z_{i}\geq 0,\; Z_{i}\ \mbox{integer}\}$$\end{document} where Π i and l i are given constants, i = 1, …, m . Two-dimensional knapsack functions can also be defined. In this paper we give a characterization of knapsack functions and then use the characterization to develop more efficient methods of computation. For one-dimensional knapsack functions we describe certain periodic properties and give computational results.