Prioritizing Project Selection to Hedge Against Uncertainty

One limitation of traditional optimization models for capital budgeting is that they do not account for risk and uncertainty in profit and cost streams associated with individual projects, nor do they account for risk in resource availability in future years. Projects can incur cost overruns, especially when projects are large, performed infrequently, or when there is risk regarding technical viability, external contractors, and/or suppliers of requisite parts and materials. Occasionally, projects are performed ahead of schedule and with savings in cost. Planned budgets for capital improvements can be cut, and key personnel may be lost. Or, there may be surprise budgetary windfalls for maintenance activities due to decreased costs for “unplanned” maintenance.

In such cases, how should we resolve capital budgeting when we have risk forecasts for costs, profits, and budgets? One approach is to re-solve the models described in the previous section once refined forecasts for these parameters become available. However, it is not always practical to fully revise a project portfolio whenever better forecasts become available.

To prioritize project selection using a risk forecast for these parameters, a two-stage stochastic optimization model [3] is employed to provide priority lists to decision-makers and support better risk-informed decisions. Its inputs include those described in the previous sections for different variants of the capital budgeting problem, except that a probabilistic description of the uncertain parameters is integrated into the optimization process.

The two-stage stochastic optimization model forms a priority list as its first-stage decision, then forms a corresponding project portfolio for each scenario as its second-stage decision. When forming the optimal second-stage project portfolio under a specific scenario, the model ensures that the portfolio is consistent with the first-stage prioritization (i.e., a project can be selected only if all higher-priority projects are also selected). Thus, the portfolios of projects corresponding to different scenarios are nested.

Notation and formulation

Indices and sets

  • t \in T: time periods (years).

  • i, i' \in I: candidate projects.

  • j \in J_i: options for selecting project i.

  • k \in K: types of resources.

  • m \in M: units of the nuclear power plant (NPP).

  • \omega \in \Omega: scenarios.

Data

  • a_i^\omega: reward for selecting project i under scenario \omega.

  • a_{ij}^\omega: reward for selecting project i via option j under scenario \omega.

  • b^\omega: available budget under scenario \omega.

  • b_k^\omega: available budget for a resource of type k under scenario \omega.

  • b_t^\omega: available budget in year t under scenario \omega.

  • b_m^\omega: available budget for unit m under scenario \omega.

  • b_{kt}^\omega: available budget for a resource of type k in year t under scenario \omega.

  • c_i^\omega: cost of investment i under scenario \omega.

  • c_{ik}^\omega: consumption of resource of type k if project i is selected under scenario \omega.

  • c_{ijt}^\omega: consumption of resources in year t if project i is performed via option j under scenario \omega.

  • c_{ijkt}^\omega: consumption of resource of type k in year t if project i is performed via option j under scenario \omega.

  • q^\omega: probability of scenario \omega.

Decision variables

  • x_i^\omega: equals 1 if project i is selected under scenario \omega; 0 otherwise.

  • x_{im}^\omega: equals 1 if project i is selected for unit m under scenario \omega; 0 otherwise.

  • x_{ij}^\omega: equals 1 if project i is selected via option j under scenario \omega; 0 otherwise.

  • y_{ii'}: equals 1 if project i has no lower priority than project i'; 0 otherwise.

Risk-Informed Single Knapsack Problem Optimization

Risk-Informed Simple Knapsack Problem

Formulation

(12)\begin{aligned} \max_{x} \quad & \sum_{\omega \in \Omega} q^\omega \sum_{i \in I} a_i^\omega x_i^\omega \\ \text{s.t.} \quad & \sum_{i \in I} c_i^\omega x_i^\omega \le b^\omega, && \forall \omega \in \Omega, \\ & y_{ii'} + y_{i'i} \ge 1, && i < i', \\ & x_i^\omega \ge x_{i'}^\omega + y_{ii'} - 1, && i \ne i',\ \forall \omega \in \Omega. \end{aligned}

For simplicity in what follows, the variable y_{ii'} = 1 means that project i is of higher priority than i', even though the variable definition allows for ties (i.e., projects of the same priority).

  • Constraint Eq. 12 (budget constraint) requires the solution to be within budget under each scenario.

  • Constraint y_{ii'} + y_{i'i} \ge 1 indicates that either project i is of higher priority than project i', or vice versa, or that both are of equal priority (i.e., a tie).

  • Constraint x_i^\omega \ge x_{i'}^\omega + y_{ii'} - 1 indicates that if project i is of higher priority than project i' (y_{ii'} = 1) and we select the lower priority project, then we must also select the higher priority project. If y_{ii'} = 0, or if x_{i'}^\omega = 0, then the constraint is vacuous.

In order to handle risk in the capital budgeting problems, the entity <Uncertainties> (see Uncertainties) is used to specify different scenarios of input parameters.

Example LOGOS input XML

<Logos>
  <Sets>
    <investments>
      1,2,3,4,5,6,7,8,9,10
    </investments>
  </Sets>

  <Parameters>
    <net_present_values index="investments">
      18,20,17,19,25,21,27,23,25,24
    </net_present_values>
    <costs index="investments">
      1,3,7,4,8,9,6,10,2,5
    </costs>
    <available_capitals>
      15
    </available_capitals>
  </Parameters>

  <Uncertainties>
    <available_capitals>
      <totalScenarios>10</totalScenarios>
      <probabilities>
        0.012, 0.019, 0.032, 0.052, 0.086,
        0.142, 0.235, 0.188, 0.141, 0.093
      </probabilities>
      <scenarios>
        11, 12, 13, 14, 15, 16, 17, 18, 19, 20
      </scenarios>
    </available_capitals>
    <net_present_values>
      <totalScenarios>2</totalScenarios>
      <probabilities>
        0.3, 0.7
      </probabilities>
      <scenarios>
        18,20,17,19,25,21,27,23,25,24,
        18,20,17,19,25,21,27,23,25,24
      </scenarios>
    </net_present_values>
  </Uncertainties>
  ...
</Logos>

When running this case, LOGOS generates a CSV (comma-separated values) file containing solutions for the optimization problem (i.e., values of decision variables and the maximum profit; MaxNPV is used to describe the maximum profit). The header of this CSV file contains the indices listed under <investments>, used as indices for the decision variables, the objective variable MaxNPV, the scenario name, and the associated probability weight. The data provides the values for both decision variables and the objective variable.

Example LOGOS output CSV

Listing 1 Example output for risk-informed simple knapsack
11,10,2,3,4,5,6,7,8,9,ScenarioName,ProbabilityWeight,MaxNPV
21.0,0.0,0.0,0.0,0.0,0.0,0.0,1.0,0.0,1.0,scenario_1,0.0036,70.0
31.0,0.0,0.0,0.0,0.0,0.0,0.0,1.0,0.0,1.0,scenario_6,0.0224,70.0
41.0,0.0,0.0,0.0,0.0,0.0,0.0,1.0,0.0,1.0,scenario_5,0.0096,70.0
5...
61.0,1.0,1.0,0.0,0.0,0.0,0.0,1.0,0.0,1.0,scenario_18,0.0987,114.0

Risk-Informed Multi-Dimensional Knapsack Problem

Formulation

(13)\begin{aligned} \max_{x} \quad & \sum_{\omega \in \Omega} q^\omega \sum_{i \in I} a_i^\omega x_i^\omega \\ \text{s.t.} \quad & \sum_{i \in I} c_{it}^\omega x_i^\omega \le b_t^\omega, && t \in T,\ \forall \omega \in \Omega, \\ & y_{ii'} + y_{i'i} \ge 1, && i < i', \\ & x_i^\omega \ge x_{i'}^\omega + y_{ii'} - 1, && i \ne i',\ \forall \omega \in \Omega. \end{aligned}

Example LOGOS input XML

<Logos>
  <Sets>
    <investments>
      1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16
    </investments>
    <time_periods>
      1,2,3,4,5
    </time_periods>
  </Sets>

  <Parameters>
    <net_present_values index="investments">
      2.315,0.824,22.459,60.589,0.667,5.173,4.003,0.582,0.122,
      -2.870,-0.102,-0.278,-0.322,-3.996,-0.246,-20.155
    </net_present_values>
    <costs index="investments, time_periods">
      0.219,0.257,0.085,0.0,0.0,
      0.0,0.0,0.122,0.103,0.013,
      5.044,1.839,0.0,0.0,0.0,
      6.74,6.134,10.442,0.0,0.0,
      0.425,0.0,0.0,0.0,0.0,
      2.125,2.122,0.0,0.0,0.0,
      2.387,0.19,0.012,2.383,0.192,
      0.0,0.95,0.0,0.0,0.0,
      0.03,0.03,0.688,0.0,0.0,
      0,0.2,0.763,0.739,2.539,
      0.081,0.032,0,0,0,
      0.3,0,0,0,0,
      0.347,0,0,0,0,
      4.025,0.297,0,0,0,
      0.095,0.095,0.095,0,0,
      5.487,5.664,0.5,6.803,6.778
    </costs>
    <available_capitals index="time_periods">
      18,18,18,18,18
    </available_capitals>
  </Parameters>

  <Uncertainties>
    <available_capitals>
      <totalScenarios>10</totalScenarios>
      <probabilities>
        0.012, 0.019, 0.032, 0.052, 0.086,
        0.142, 0.235, 0.188, 0.141, 0.093
      </probabilities>
      <!--
        scenarios is ordered by numberScenarios * parametersIndex,
        numberScenarios * time_periods = 10 * 5
      -->
      <scenarios>
        11, 11, 11, 11, 11,
        12, 12, 12, 12, 12,
        13, 13, 13, 13, 13,
        14, 14, 14, 14, 14,
        15, 15, 15, 15, 15,
        16, 16, 16, 16, 16,
        17, 17, 17, 17, 17,
        18, 18, 18, 18, 18,
        19, 19, 19, 19, 19,
        20, 20, 20, 20, 20
      </scenarios>
    </available_capitals>
  </Uncertainties>

  <Settings>
    <mandatory>10,11,12,13,14,15,16</mandatory>
    <solver>cbc</solver>
    <sense>maximize</sense>
  </Settings>
</Logos>

Example LOGOS output CSV

Listing 2 Example output for risk-informed multi-dimensional knapsack
11,10,11,12,13,14,15,16,2,3,4,5,6,7,8,9,ScenarioName,ProbabilityWeight,MaxNPV
21.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,0.0,0.0,1.0,0.0,0.0,1.0,0.0,scenario_1,0.012,-23.581
3...
41.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,0.0,1.0,1.0,1.0,0.0,1.0,1.0,scenario_10,0.093,42.303

Risk-Informed Multiple Knapsack Problem Optimization

Model formulation

Objective and priority consistency

(14)\mathop{\max}_{x,y} \; \sum_{\omega \in \Omega} q^\omega \sum_{i \in I} \sum_{m \in M} a_i^\omega x_{im}^\omega

subject to

(15)y_{ii'} + y_{i'i} \ge 1, \qquad i < i',\ i,i' \in I,

(16)\sum_{m=1}^M x_{im}^\omega \ge \sum_{m=1}^M x_{i'm}^\omega + y_{ii'} - 1, \qquad i \ne i',\ i,i' \in I,\ \omega \in \Omega.

Constraint Eq. 15 indicates that either project i is of higher priority than project i', or vice versa, or that both are of equal priority (i.e., a tie).

Constraint Eq. 16 indicates that if project i is higher priority than project i' (y_{ii'} = 1), and we select the lower priority project for some unit, then we must also select the higher priority project. If y_{ii'} = 0, or if \sum_{m=1}^{M} x_{i'm}^\omega = 0, then the constraint is vacuous.

Budget and unit selection constraints

(17)\sum_{i \in I} c_i^\omega x_{im}^\omega \le b_m^\omega, \qquad m \in M,\ \omega \in \Omega,

Constraint Eq. 17 requires that we be within budget for each unit under each scenario.

(18)\sum_{m \in M} x_{im}^\omega \le 1, \qquad i \in I,\ \omega \in \Omega,

Constraint Eq. 18 ensures that each project i is selected for at most one unit.

Example LOGOS input XML

<Logos>
  <Sets>
    <investments>
      1,2,3,4,5,6,7,8,9,10
    </investments>
    <capitals>
      unit_1, unit_2
    </capitals>
  </Sets>

  <Parameters>
    <net_present_values index="investments">
      78, 35, 89, 36, 94, 75, 74, 79, 80, 16
    </net_present_values>
    <costs index="investments">
      18, 9, 23, 20, 59, 61, 70, 75, 76, 30
    </costs>
    <available_capitals index="capitals">
      103, 156
    </available_capitals>
  </Parameters>

  <Uncertainties>
    <available_capitals>
      <totalScenarios>2</totalScenarios>
      <probabilities>
        0.3 0.7
      </probabilities>
      <scenarios>
        103, 156,
        103, 156
      </scenarios>
    </available_capitals>
    <net_present_values>
      <totalScenarios>2</totalScenarios>
      <probabilities>
        0.3, 0.7
      </probabilities>
      <scenarios>
        78, 35, 89, 36, 94, 75, 74, 79, 80, 16,
        78, 35, 89, 36, 94, 75, 74, 79, 80, 16
      </scenarios>
    </net_present_values>
  </Uncertainties>

  <Settings>
    <solver>glpk</solver>
    <sense>maximize</sense>
    <problem_type>MultipleKnapsack</problem_type>
  </Settings>
</Logos>

Example LOGOS output CSV

Listing 3 Example output for risk-informed multiple knapsack
1"('1', 'unit_1')","('1', 'unit_2')","('10', 'unit_1')","('10', 'unit_2')","('2', 'unit_1')","('2', 'unit_2')","('3', 'unit_1')",
2"('3', 'unit_2')","('4', 'unit_1')","('4', 'unit_2')","('5', 'unit_1')","('5', 'unit_2')","('6', 'unit_1')","('6', 'unit_2')",
3"('7', 'unit_1')","('7', 'unit_2')","('8', 'unit_1')","('8', 'unit_2')","('9', 'unit_1')","('9', 'unit_2')",
4ScenarioName,ProbabilityWeight,MaxNPV
51.0,0.0,0.0,0.0,0.0,0.0,1.0,0.0,0.0,1.0,0.0,1.0,1.0,0.0,0.0,0.0,0.0,0.0,0.0,1.0,scenario_1,0.09,452.0
61.0,0.0,0.0,0.0,0.0,0.0,1.0,0.0,0.0,1.0,0.0,1.0,1.0,0.0,0.0,0.0,0.0,0.0,0.0,1.0,scenario_2,0.21,452.0
7...

Risk-Informed Multiple-Choice Multi-Dimensional Knapsack Problem Optimization

Model formulation

Objective and priority consistency

(19)\mathop{\max}_{x,y} \; \sum_{\omega \in \Omega} q^\omega \sum_{i \in I} \sum_{j \in J_i} a_{ij}^\omega x_{ij}^\omega

subject to

(20)y_{ii'} + y_{i'i} \ge 1, \qquad i < i',\ i,i' \in I,

(21)\sum_{j=1}^{J_i} x_{ij}^\omega \ge \sum_{j=1}^{J_i} x_{i'j}^\omega + y_{ii'} - 1, \qquad i \ne i',\ i,i' \in I,\ \omega \in \Omega.

Constraint Eq. 20 indicates that either project i is of higher priority than project i', or vice versa, or that both are of equal priority (i.e., a tie).

Constraint Eq. 21 indicates that if project i is higher priority than project i' (y_{ii'} = 1), and we select the lower priority project under some option, then we must also select the higher priority project. If y_{ii'} = 0, or if \sum_{j=1}^{J_i} x_{i'j}^\omega = 0, then the constraint is vacuous.

Budget and option constraints

(22)\sum_{i \in I} \sum_{j \in J_i} c_{ijkt}^\omega x_{ij}^\omega \le b_{kt}^\omega, \qquad k \in K,\ t \in T,\ \omega \in \Omega,

Constraint Eq. 22 requires that we be within budget in each time period, for each resource type, and under each scenario.

(23)\sum_{j \in J_i} x_{ij}^\omega \le 1, \qquad i \in I,\ \omega \in \Omega.

Constraint Eq. 23 ensures that we select project i via at most one option. This illustrates a situation in which we must include the DoNothing option among the alternatives to optional projects.

Example LOGOS input XML

<Logos>
  <Sets>
    <investments>
      1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
      11, 12, 13, 14, 15, 16, 17
    </investments>
    <options index="investments">
      1;
      1;
      1;
      1,2,3;
      1,2,3,4;
      1,2,3,4,5,6,7;
      1;
      1;
      1;
      1;
      1;
      1;
      1;
      1;
      1;
      1;
      1
    </options>
  </Sets>

  <Parameters>
    <net_present_values index="options">
      2.046
      2.679
      2.489
      2.61
      2.313
      1.02
      3.013
      2.55
      3.351
      3.423
      3.781
      2.525
      2.169
      2.267
      2.747
      4.309
      6.452
      2.849
      7.945
      2.538
      1.761
      3.002
      3.449
      2.865
      3.999
      2.283
      0.9
      8.608
    </net_present_values>
    <costs index="options">
      36538462
      83849038
      4615385
      2788461538
      2692307692
      5480769231
      1634615385
      2981730768
      7211538462
      9038461538
      649038462
      650000000
      216346154
      212500000
      3076923077
      3942307692
      1144230769
      675721154
      1442307692
      99711538
      4807692
      123076923
      138461538
      86538462
      108653846
      75092404
      6413462
      147932692
    </costs>
    <available_capitals>
      15E9
    </available_capitals>
  </Parameters>

  <Uncertainties>
    <available_capitals>
      <totalScenarios>3</totalScenarios>
      <probabilities>
        0.2,0.6,0.2
      </probabilities>
      <scenarios>
        5E9,10E9,15E9
      </scenarios>
    </available_capitals>
  </Uncertainties>

  <Settings>
    <solver>cbc</solver>
    <solverOptions>
      <threads>1</threads>
      <StochSolver>EF</StochSolver>
    </solverOptions>
    <sense>maximize</sense>
    <problem_type>mckp</problem_type>
  </Settings>
</Logos>

Example LOGOS output CSV

Listing 4 Example output for risk-informed multiple-choice knapsack
1"('1', '1')","('10', '1')","('11', '1')","('12', '1')","('13', '1')","('14', '1')","('15', '1')","('16', '1')",
2"('17', '1')","('2', '1')","('3', '1')","('4', '1')","('4', '2')","('4', '3')","('5', '1')","('5', '2')","('5', '3')",
3"('5', '4')","('6', '1')","('6', '2')","('6', '3')","('6', '4')","('6', '5')","('6', '6')","('6', '7')","('7', '1')",
4"('8', '1')","('9', '1')",ScenarioName,ProbabilityWeight,MaxNPV
51.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,1.0,1.0,1.0,1.0,scenario_1,0.2,53.865
61.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,0.0,0.0,1.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,1.0,1.0,1.0,1.0,scenario_2,0.6,59.488
71.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0,0.0,0.0,0.0,0.0,1.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,1.0,1.0,1.0,1.0,scenario_3,0.2,59.826