Title

Experiments With The "Oregon Trail Knapsack Problem"

Abstract

This paper presents hybrid algorithms for a variation of the Bounded Knapsack Problem which we call the Oregon Trail Knapsack. Our problem entails imposing a cost as well as a weight limit, constraining the values of types of items by means of a variety of value functions, and allowing the value of one item type to be dependent on the presence or absence of another type in the knapsack. These modifications to the original problem make it more complex and require adaptations of known knapsack algorithms. To solve this problem, we combine constraint propagation techniques and domain pruning with classic branch and bound approaches that require a sorting of the items. Our experments compare a constraint-language implementation with a simulation of the constraint-based system in a procedural language. Results indicate that the constraint-based solution is natural to the problem and efficient enough to solve large problem instances typical of the application.

Publication Date

12-1-1999

Publication Title

Electronic Notes in Discrete Mathematics

Volume

1

Number of Pages

1-10

Document Type

Article

Personal Identifier

scopus

Socpus ID

53149104363 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/53149104363

This document is currently not available here.

Share

COinS