Knowledge that Transforms

The multiple-choice knapsack problem is defined as a binary knapsack problem with the addition of disjoint multiple-choice constraints. The strength of the branch-and-bound algorithm we present for this problem resides with the quick solution of the linear programming relaxation and its efficient, subsequent reoptimization as a result of branching. An implemented version of this algorithm has performed well on a large set of test problems. We cite computational results as well as a comparison with a previously reported algorithm. Several useful applications of the multiple-choice knapsack problem are also suggested.

A continuous time Markov decision process with uniformly bounded transition rates is shown to be equivalent to a simpler discrete time Markov decision process for both the discounted and average reward criteria on an infinite horizon. This result clarifies some earlier work in this area.