Project selection with discounted returns and multiple constraints

Abstract

This paper considers the problem of selecting a subset of N projects subject to multiple resource constraints. The objective is to maximize the net present value of the total return, where the return from each project depends on its completion time and the previously implemented projects. It is observed that the optimal order (sequence) of projects does not depend on the particular subset of selected projects and hence the overall problem reduces to a multiconstraint nonlinear integer (0–1) problem. This problem can be solved optimally in pseudo-polynomial time using a dynamic programming method but the method is impractical except when the number of constraints, K, is very small. We therefore propose two heuristic methods which require O(N3K) and O(N4K) computations, respectively, and evaluate them computationally on 640 problems with up to 100 projects and up to 8 constraints. The results show that the best heuristic is on the average within 0.08% of the optimum for the single-constraint case and within 2.61% of the optimum for the multiconstraint case.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 38 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.