search query: @indexterm Dynamic programming / total: 309
reference: 19 / 309
Author: | Pisinger, D. |
Title: | Budgeting with bounded multiple-choice constraints |
Journal: | European Journal of Operational Research
2001 : MAR 16, VOL. 129:3, p. 471-480 |
Index terms: | INTEGER PROGRAMMING DYNAMIC PROGRAMMING KNAPSACK PROBLEM BUDGETING |
Language: | eng |
Abstract: | The author considers a budgeting problem where a specified number of projects from some disjoint classes has to be selected such that the overall gain is largest possible, and such that costs of the chosen projects do not exceed a fixed upper limit. The problem has several application in government budgeting, planning, and as relaxation from other combinatorial problems. It is demonstrated that the problem can be transformed to equivalent multiple-choice knapsack problem through dynamic programming. Computation experiments are presented, showing that the developed algorithm is orders of magnitude faster than a general LP/MIP algorithm. |
SCIMA