A multiobjective evolutionary approach for linearly constrained project selection under uncertainty

https://doi.org/10.1016/j.ejor.2005.03.068Get rights and content

Abstract

In the project selection problem a decision maker is required to allocate limited resources among an available set of competing projects. These projects could arise, although not exclusively, in an R&D, information technology or capital budgeting context. We propose an evolutionary method for project selection problems with partially funded projects, multiple (stochastic) objectives, project interdependencies (in the objectives), and a linear structure for resource constraints. The method is based on posterior articulation of preferences and is able to approximate the efficient frontier composed of stochastically nondominated solutions. We compared the method with the stochastic parameter space investigation method (PSI) and illustrate it by means of an R&D portfolio problem under uncertainty based on Monte Carlo simulation.

Introduction

In the project selection problem a decision maker allocates limited resources to a set of competing projects. In addition, while selecting projects and allocating resources, the decision maker must take into consideration one or more corporate goals or objectives.

There are two major taxonomies of the project selection literature. The first taxonomy is based on the application context. Within this classification, the project selection problem arises primarily in the context of research and development (R&D) [1], [15], [19], [33], [34], information technology (IT) [25], [28], [29], [37], [38], [39], [40], [43], and capital budgeting [17], [31], [48], [49]. The second taxonomy is based on the nature of the tools used for solving the project selection problem. This taxonomy classifies project selection models into one of two streams: the management science stream and the financial optimization stream. For more information about the project selection problem refer to [18].

In this paper, we propose a method for solving any project selection problem with the following characteristics:

  • 1.

    Partially funded projects. Projects can be partially funded, or conversely, fully or not funded at all (i.e., zero-one). The proposed method allows the decision maker to engage in partially funded projects. For a sample of zero-one project selection refer to [22], [39].

  • 2.

    Multiple objectives. The decision maker may wish to simultaneously satisfy several corporate goals (e.g., minimize time-to-market and maximize economic return). Often, these goals will be in conflict, resulting in a more complicated, yet realistic, decision making process. The proposed model takes into consideration multiple (possibly conflicting) objectives.

  • 3.

    Posterior articulation of preferences. The methods for multiobjective project selection can be classified based on how the decision maker expresses his/her preferences in the decision making process. Some methods have been proposed based on prior [23] and progressive [36] articulation of preferences, but few based on posterior articulation of preferences. The proposed method, based on posterior articulation of preferences, requires the least amount of information from the decision maker and could be completely automated.

  • 4.

    Uncertainty in the objectives. Some elements of the project selection process may be uncertain. For instance, some uncertain elements that could affect a project’s evaluation are interest rates, opportunity cost, risk, revenues, inflation, and cash flows, among others. During project evaluation, the proposed method allows uncertain elements in the objectives to be included as random coefficients in complex expressions (even nonlinear). Moreover, the method also allows the treatment of the whole project as a black-box. In this case, the method simulates the project and evaluates its performance measures (objectives) subject to random events.

  • 5.

    Project interdependencies. In the project selection literature, there are mainly three types of interdependencies: resource, benefit, and technical interdependencies [38]. Interdependencies preclude the linearity of the models. For example, suppose there are two projects, A and B, with interdependent benefits of $500 and $1000, respectively. The benefits of implementing both projects could exceed $1500 (=$500 + $1000) due to the additional benefits accrued from a pooling effect. This benefit interdependence could be modeled using non-linear terms as in [15], [38]. The proposed model allows project interdependencies to be modelled in the objective functions.

  • 6.

    Linearly-constrained resources. Project selection problems are constrained by their use of scarce resources (e.g., capital, labor, space requirements, and personnel, among others). Linear optimization models [12] have been popular due in part to the fact that many problem conditions are suitable to be expressed in linear form. The proposed method uses common, yet expressive, linear relations to model the restrictions on the various resources.

The stochastic parameter space investigation (PSI) method [35] is able to solve the project selection problem with the above characteristics. The stochastic PSI proceeds as follows: (1) project allocations are generated based on box constraints on the variables representing them (i.e., lower and upper bounds); (2) if a project allocation does not satisfy the constraints on the resources, that configuration is discarded; (3) if a project allocation is feasible, the objectives are simulated and evaluated; (4) statistics of central tendency and deviation are computed based on the simulation results (i.e., mean and kth percentile); and (5) if the project allocation is nondominated (based on Definition 1 in Section 2), it is preserved for future presentation to the decision maker at the end of the procedure (otherwise, it is discarded).

The stochastic PSI method has several advantages. Among them, it can be applied to a very large class of project selection problems, it is very easy to implement, makes no assumption about the behavior of the decision maker, and accounts for uncertainty in the objectives. However, all the flexibility of the stochastic PSI method does not come for free. From the work on the deterministic PSI by Steuer and Sun [47] and our own experience, the limitations of the stochastic PSI are: the method can only handle project selection problems of limited size (less than ten variables), its computational efficiency is dependent on the relative size of the feasible region to the size of the hypercube that encloses the feasible region (given by the bounds on the variables), and it requires explicit and tight bounds on the values of the decision variables.

In this paper we present a new multiobjective evolutionary algorithm that serves as an alternative to the stochastic PSI method. The proposed method is applicable to project selection problems with partially funded projects, multiple (stochastic) objectives, project interdependencies (in the objectives), and linearly-constrained resources. Furthermore, being a method based on posterior articulation of preferences, it is able to approximate the efficient frontier composed of stochastically nondominated solutions. This paper complements previous work done in [26].

This paper is organized as follows. In Section 2 we present the proposed multiobjective evolutionary algorithm. In Section 3 we present our computational experience with the proposed algorithm. In Section 3.1 we tune the parameters; in Section 3.2 we present a comparison between the stochastic PSI and the proposed evolutionary approach in problems found in the literature; and in Section 3.3 we show an R&D portfolio optimization example that illustrates the flexibility of our approach. This example uses Monte Carlo simulation for evaluating a given set of project allocations. Finally, conclusions and current research directions are given in Section 4.

Section snippets

Project selection as a stochastic multiobjective linearly-constrained optimization problem

Consider the project selection problem seen as the following stochastic multiobjective linearly-constrained optimization problem:maxf1(x,ω),,fk(x,ω),,fK(x,ω)subjecttoxΩ,where x is a solution (vector of n decision variables) representing a nth dimensional array of project allocations; fk(x, ω) is the objective function evaluating the kth criterion and ω represents the stochastic effect in the objectives; and Ω={xRn:gi(x)bi,i=1,,m;x0} is the polyhedral space of feasible project allocations

Computational experiments

In this section we report our computational experience with the proposed evolutionary algorithm for project selection. In Section 3.1 we show how the algorithm’s parameters affect time and quality of the solution. Section 3.1.2 illustrates our experience with a variation of the crossover operator that favors the best parents. In Section 3.2 we compare our approach to the stochastic parameter space investigation method [35], a general purpose method for project selection. For comparison, we use

Concluding remarks

This paper presents a new evolutionary method for solving project selection problems with partially funded projects, multiple objectives, project interdependencies (in the objectives), and a linear structure for resource constraints. The algorithm allows uncertain elements in the objectives to be modelled as random coefficients in complex (nonlinear) expressions. The algorithm also allows project evaluation being treated as a black box. In the latter case, the method simulates the project and

Acknowledgement

This study was partially funded by the grant CIFI-2057 of the Research Fund for Assistant Professors at Universidad de los Andes.

References (50)

  • O. Aristeguieta, S. Begg, R. Bratvold, Improving oil and gas business performance through project portfolio...
  • T. Back et al.

    Extended selection mechanisms in genetic algorithms

  • D. Beasley et al.

    An overview of genetic algorithms: Part 1. Fundamental

    University Computing

    (1993)
  • D. Beasley et al.

    An overview of genetic algorithms: Part 2. Research topics

    University Computing

    (1993)
  • J.E. Beasley

    Population heuristics

  • C.A. Coello

    A short tutorial on evolutionary multiobjective optimization

  • C.A. Coello et al.

    Evolutionary Algorithms for Solving Multi-Objective Problems

    (2002)
  • K. Deb et al.

    A fast and elitist multi-objective genetic algorithm: NSGA-II

    IEEE Transactions on Evolutionary Computation

    (2002)
  • B. Eckel

    Thinking in Java

    (2002)
  • S.C. Fang et al.

    Linear Programming and Extensions

    (1993)
  • L.J. Fogel et al.

    Artificial Intelligence Through Simulated Evolution

    (1966)
  • C.M. Fonseca et al.

    Genetic algorithms for multi-objective optimization: Formulation, discussion and generalization

  • G.E. Fox et al.

    Economic models for R and D project selection in the presence of project interactions

    Management Science

    (1984)
  • D.E. Goldberg

    Genetic Algorithms in Search, Optimization and Machine Learning

    (1989)
  • J. Goldwerger et al.

    Capital budgeting of interdependent projects: Activity analysis and approach

    Management Science

    (1977)
  • Cited by (128)

    • An integrated framework for diversified project portfolio selection

      2023, International Journal of Project Organisation and Management
    View all citing articles on Scopus
    View full text