Algorithms for some hard knapsack problems
Access Status
Authors
Date
2000Supervisor
Type
Education Level
Metadata
Show full item recordAbstract
The Knapsack Problems are among the simplest integer programs which are NPhard. Problems in this class are typically concerned with selecting from a set of given items, each with a specified weight and value, a subset of items whose weight sum does not exceed a prescribed capacity and whose value is maximum. The specific problem that arises depends on the number of knapsacks (single or multiple) to be filled and on the number of available items of each type (bounded or unbounded). The classical 01Knapsack Problem arises when there is one knapsack and one item of each type.Knapsack Problems have been intensively studied over the past forty years because of their direct application to problems arising in industry (for example, cargo loading, cutting stock, and budget control) and also for their contribution to the solution methods for integer programming problems.Several exact algorithms based on branch and bound and dynamic programming have been proposed to solve the Knapsack Problems. For some types of data instances, very efficient algorithms have been found. However, a number of hard knapsack instances have been identified. For example, subset sum and strongly correlated data types. This has motivated some researchers to develop specialized algorithms for particular hard problems.This thesis considers a number of hard Knapsack Problems with a single constraint. A number of specialized algorithms are developed. Our work focuses on some hard instances of the 01Knapsack Problem, the Bounded Knapsack Problem, the Unbounded Knapsack Problem and the ChangeMaking Problem.Chapter 1 provides the background of the Knapsack Problem including some important Knapsack Problems and standard types of data instances, terminology, and a summary of our work. Chapter 2 gives a review of the applications and the solution methods that have been proposed. The remaining chapters present the details of our specialized algorithms.Chapter 3 proposes algorithms for the hard 01Knapsack Problems instances of subset sum, strongly correlated, and inverse strongly correlated. The algorithms for the Bounded Knapsack Problem instances of strongly correlated and subset sum are also presented. Extensive computational results show that our algorithms are able to solve large problems of size up to one million variables in less than 7 seconds.Chapter 4 proposes algorithms for some hard Unbounded Knapsack Problems. Two algorithms one for the Unbounded Strongly Correlated Knapsack Problem (algorithm CKU1) and one for the Unbounded Subset Sum Problem (algorithm CKU2) are presented. Extensive computational results establish that our two algorithms are able to solve large problems with up to one million variables in less than 0.3 second.Finally, Chapter 5 proposes exact algorithms for the ChangeMaking Problem. The problem is a particular type of single Knapsack Problems. This chapter proposes two exact algorithms: algorithm CKUC for the Unbounded ChangeMaking Problem (UCMP) and algorithm CKBC for the Bounded ChangeMaking Problem (BCMP). The algorithms can solve largesized problems, when the item types are generated in small ranges, in less than 51 milliseconds for UCMP and less than 3.5 seconds for BCMP.
School
Collection
Related items
Showing items related by title, author, creator and subject.

Chong, Yen N. (2001)General routing problems deal with transporting some commodities and/or travelling along the axes of a given network in some optimal manner. In the modern world such problems arise in several contexts such as distribution ...

Grigoleit, Mark Ted (2008)The Constrained Shortest Path Problem (CSPP) consists of finding the shortest path in a graph or network that satisfies one or more resource constraints. Without these constraints, the shortest path problem can be solved ...

Lam, Bee K. (1999)A network is a system that involves movement or flow of some commodities such as goods and services. In fact any structure that is in the form of a system of components some of which interact can be considered as a network. ...