Project Portfolio Selection Problem (PPSP)

Efficient formulations for PPSP problem considering cardinality and interdependency

Introduction

In the project portfolio selection problem (PPSP), a decision maker must select a set of projects to launch and try to maximize the profit. Meanwhile, there are some factors considered by a DM. In this study, we consider (1.) project interdependency and (2.) cardinality constraint only.

1. Project Interdependency: PPSP may be affected by synergy effect from the various combinations of different projects. For instance, if we launch 2 projects simultaneously, then it may earn you additional benefits a.k.a. synergestic benefit. Moreover, resource interdependency occurs when common resources are shared by various projects. Thus, to find a novel combinations of projects may increase the potential benefit.
2. Cardinality Constraint: Cardinality is the number of projects selected in the portfolio. Thus, this number is restricted below a given numbr in this constraint.

In the rest of this tutorial, there are model formulation, Python + Gurobi implementation, an example and advanced topics.

Model Formulaton

In the original paper, both equality and inequality cardinality constraint cases are considered, but I will demonstrate the equality constraint cases only in this tutorial. You can find inequality constraint cases referred to the paper [2].

We first introduce some notations.

For instance, if project and are selected, which means . Then, the total benefit will be , and this combination will consume resoure in the mean time. One can notice that there is a minus sign in the equation about resource, since shared-used concept is considered here. This concept follows standard Venn diagram (文氏圖).

Nonlinear Model

Nonlinear model is quite simple in this problem. Our objective is to maximize the total benefit subject to cardinality and resource constraints.

Although this model is quite simple to understand, it's inefficient due to the polynomial integer programming property. Thus, its implementaion is omitted.

Conventional Model (Equality Cardinality Constraint)

In thish model, we introduce 2 set of decicsion variables and . One can notice that the subscripts of each decision variables are in an ascending order s.t. every combination will have an unique representation.

Proposed Model (Equality Cardinality Constraint)

In this model, decision variables are replaced with via some equations. Related proofs can be found in [2].

Conventional and Proposed Model (Inequality Cardinality Constraint)

The basic idea is to introduce a set of binary variables in order to represent the cardinality, which is less than or equal to .

The details of the formulation can be also found in the original paper [2].

Python + Gurobi Implementation

First, make sure you have installed the following packages and have Gurobi license:

numpy
gurobipy

I implemented four kinds of models including conventional model and proposed model with equality/ inequality cardinality constraint.

Problem Solver

def PPSP_solver(N, m, r_i, r_ij, r_ijk, d_i, d_ij, d_ijk, b, mode, equality=True)

• Parameters

  • N: int
  • m: int
  • r_i: dict of 1-D index, e.g., r_i[1] means the benefit from implementing project 1.
  • r_ij: dict of 2-D index, e.g., r_ij[1, 2] means the benefit from implementing project 1 and 2.
  • r_ijk: dict of 3-D index, e.g., r_ijk[1, 2, 3] means the benefit from implementing project 1, 2 and 3.
  • d_i: dict of 1-D index, e.g., d_i[1] means the resource required from implementing project 1.
  • d_ij: dict of 2-D index, e.g., d_ij[1, 2] means the resource required from implementing project 1 and 2.
  • d_ijk: dict of 3-D index, e.g., d_ijk[1, 2, 3] means the resource required from implementing project 1, 2 and 3.
  • b: float
  • mode: {'conventional', 'proposed'}, default='proposed'
  • equality: bool, default='True'
  • time_limit: int, default=3600, the time limit to optimize the model
  • is_quiet: bool, default=True, enables or disables solver output

• Returns

  • gurobipy.Model

The parameter mode can be either 'conventional' or 'proposed' with equality being 'True' or 'False'. So, there are 4 kinds of model. The output of this function is an optimized Gurobi model. You can access it directly.

Instance Generator

Additionally, you can automatically generate the instances by given N and m.

The parameters are basically uniformly distributed, which follows [1]:

• Resource
  • 
  • 
  • 
  • 
• Benefit
  • 
  • 
  • 

def instance_generator(N, m)

• Parameters
  • N: int
  • m: int
• Returns
  • dict

Example

Please access 'example.ipynb' to run the code.

import numpy as np
import gurobipy as gp
from gurobipy import GRB

from model import PPSP_solver, instance_generator

# generate a problem instance with N = 16 and m = 3
instance = instance_generator(16, 3)

# solve the instance with four kinds of models and print the result with running time
for is_equal in [True, False]:
    if is_equal:
        print('-----------  Equality Cardinality Constraint  -----------')
    else:
        print('-----------  InEquality Cardinality Constraint  -----------')
        
    for mode_ in ['conventional', 'proposed']:
        model = PPSP_solver(**instance, mode=mode_, equality=is_equal)
        
        if  model.status == GRB.OPTIMAL:
            portfolio = []
            for v in model.getVars():
                if 'x' in v.varName and abs(v.x-1) <= 0.0001:  # avoid rounding error
                    name = v.varName
                    portfolio.append(name[name.find('[') + 1:-1])

            print(f'Mode: {mode_}')
            print(f'\t Objective Value: {model.ObjVal}')
            print(f'\t Optimal Portfolio:', ','.join(portfolio))
            print(f'\t Running Time: {model.RunTime}')
    print()

Advanced Topics

So far, we have already handled order two and order three terms, but I want to provide the treatment for higher order terms. Basically, the extension of properties and theorems from [2] can reach the goal. Thus, there are two corollaries below. The first one is the extension from proposition 1 and 2, and the second one is extended from theorem 1 in [2].

---

Corollary 1. Let and be given positive integers such that and assume that for satisfying . For a set of non-negative variables with all of the subscripts being distinct, if

then

Proof. If and denote , then there are elements in . We have if and only if and is not in . For any , the value of the right-hand side is . Since there are possible nonzero terms like , and for on the left-hand side, and all 's are no more than 1, it follows that for and .

---

Corollary 2. For a vector , one set of non-negative variables , and one set of non-negative variables with all of the subscripts being distinct and , where and are two integer variables. Let be the additional benefit from implementing project simultaneously. If the constraints from Corollary 1. with and , and are satisfied, then

Proof. If , there exist unique such that . Denote .

1. It is clear that when any projects are selected (i.e., if then ), the left-hand side becomes
2. Similarily, when any projects are selected (i.e., if then ), the right-hand side becomes . Without loss of generality, we can take for example. In the RHS, , where with . It shows that will repeat times compared to LHS, so there is a coefficient in front of the summation.

Proved.

With Corollary 2., one can extend propsion 3, 4 and 5 in [2] easily.

References

[1] Xingmei Li, Yao-Huei Huang, Shu-Cherng Fang and Zhibin Deng (2016), Reformulations for project portfolio selection problem considering interdependence and cardinality, Pacific Journal of Optimization, 12(2), 355-366.
[2] Xingmei Li, Yao-Huei Huang , Shu-Cherng Fang , Youzhong Zhang (2020), An alternative efficient representation for the project portfolio selection problem, European Journal of Operational Research, 281(1), 100-113.