The Theory and Computation of Knapsack Functions

P. C. Gilmore and R. E. Gomory
Additional contact information
P. C. Gilmore: International Business Machines Corporation, Yorktown Heights, New York
R. E. Gomory: International Business Machines Corporation, Yorktown Heights, New York

Operations Research, 1966, vol. 14, issue 6, 1045-1074

Abstract: 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.

Date: 1966
References: Add references at CitEc
Citations: View citations in EconPapers (62)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.14.6.1045 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:14:y:1966:i:6:p:1045-1074

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().