The 0–1 knapsack problem with multiple choice constraints |
| |
Authors: | Robert M. Nauss |
| |
Affiliation: | University of Missouri-St. Louis, 8001 Natural Bridge Road, St. Louis, MO 63121, U.S.A. |
| |
Abstract: | In this paper we consider the 0–1 knapsack problem with multiple choice constraints appended. Such a problem may arise in a capital budgeting context where only one project may be selected from a particular group of projects. Thus the problem is to choose one project from each group such that the budgetary constraint is satisfied and the maximum return is realized. We formulate two branch and bound algorithms which use two different relaxations as the primary bounding relaxations. In addition, theoretical results are given for a simple reduction in the number of variables in the problem. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|