# Selecting Large Portfolios of Social Projects in Public Organizations

Authors: Igor Litvinchev; Fernando Lopez-Irarragorri; Nancy Maribel Arratia-Martínez; José Antonio Marmolejo
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

We address the portfolio selection of social projects in public organizations considering interdependencies (synergies) affecting project funds requirements and tasks. A mixed integer linear programming model is proposed incorporating the most relevant aspects of the problem found in the literature. The model supports both complete (all or nothing) and partial (a certain amount from a given interval of funding) resource allocation policies. Numerical results for large-scale problem instances are presented.


---

## Body

## 1. Introduction

One of the main management problems in many organizations and institutions in the public sector is to decide how to invest and manage funds available to support potential research and development projects in various areas [1]. A classification of the portfolio problem [2] distinguishes two types: (a) static and (b) dynamic. In (a), only projects proposals for funding are involved, while, in (b), at certain moments, some active projects are withdrawn from the portfolio and some inactive projects are activated.Selecting portfolio of social projects is a periodical activity, involving a group of projects with social impact competing for financial support. This problem is categorized under the static type of portfolio problems.It is important to highlight the differences between portfolio problems in public and private sectors. In contrast to public sector, the problem that occurs in private organizations is typically a dynamic one. Along with other differences, such as selection criteria and characteristics of the projects, in private sector, the projects can be evaluated more than once during the implementation. Moreover, criteria used to measure the portfolio in private sector are typically related to economic factors, such as expected sales, return of inversion or profit, and market situation. In the selection of portfolios of social projects, an important criterion is the social impact. Typically return of inversion or profit is not expected.We refer to a social project as a group of tasks or activities consuming funds, carried out during a given period of time in one or more regions, with an impact on the objectives set by an organization, and focused on providing solution to problems or needs of the society.Structural characteristics of the problem are as follows.(1)
There is a set of projects proposals competing only for funding. Every proposal is evaluated by a group of experts (reviewers) assigning to the proposal a value of its social impact (benefit).
(2)
Every proposal has its own estimation of the funds required.
(3)
The reviewers suggest a range of funding for each project.
(4)
Each project belongs to a certain area of interest defined in the call for proposals. In particular, the area can be associated with geographical regions.
(5)
The available budget is lower than the total amount of funds requested by all the proposals.
(6)
Maximal and minimal value of funds that can be assigned to a given area are defined according to the organization rules.
(7)
The total amount of funds requested by each proposal has to be divided between the tasks included in the proposal. Since it is difficult to set up a priori an exact value of funding for each task, a range of funding is defined, indicating the minimal and the maximal amounts of funds to be allocated to each task.
(8)
The decision of funding is taken only once in a given period of time.
(9)
All the projects are scheduled to start and finish in the same time period.
(10)
All the tasks included in the project must start and finish in the same time period.
(11)
There are interdependences between projects or tasks, resulting in synergies affecting the benefice and/or providing increase-decrease of required funds.
(12)
According to organization rules, there may be certain relationships between projects/tasks, which restrict a number of projects/tasks included in the portfolio.Below we summarize principal characteristics of our approach to portfolio selection problem.(i) Characterization of Projects through a Set of Tasks.It is natural to see the project as a set of tasks requiring funds for their implementation. If so, each of these tasks must make a contribution to the impact of the project, contributing to the quality measure of the portfolio. Thus it is necessary to include the amount of funds requested by the task, as well as an index of its importance for achieving objectives of the project.(ii) Flexibility of the Funds Allocated to Tasks.In most of references on portfolio selection, the projects are either supported by the complete amount requested in the proposal or not supported at all. However, in many real-word problems, a part of the requested amount can also be assigned. Taking this into account, we assume that reviewers (if necessary, supported by experts) are able to analyze if the request is overestimated (underestimated). This way, an interval of possible funds assignment is defined allowing flexible assignment within the interval. Similarly, for the tasks. Hence, the funding of the project can vary according to funds assigned to its tasks.(iii) Interdependences between Projects or Project Tasks. Another important factor to consider is the existence of synergies between tasks produced by interdependencies in tasks and/or projects. According to Rungi [3], projects synergies appear when the measure of the quality of all the projects is different from the sum of the measures of individual projects. In this paper, we consider the interdependencies between tasks of two or more projects producing synergies of the following types: (
1
) synergies of benefit or impact, (
2
) synergies which result in an increase in funds, (
3
) synergies which results in a decrease in funds, and (
4
) technical synergies. These are defined for groups of synergies indicating that only a subset of them can be active. Technical synergies are used to have greater control over the synergies of any kind.The following assumptions are used in this paper.(i)
There is a person (or persons) referred to as the decision maker (DM) and representing preferences and priorities of the organization. Typically the DM is represented by reviewers of the project proposals.
(ii)
The DM is able to express the advantages/disadvantages providing by synergies.
(iii)
Each project can be divided into a number of tasks requiring funds.
(iv)
The tasks of each project have different impacts on the objectives of the project they belong to. The value of impact is provided in the proposal and is evaluated by reviewers.
(v)
The reviewers are able to define the interval of funds allocated for each task and project.Bearing in mind the characteristics stated above, the solution of the problem consists in making the following decisions:(1)
selection of projects and corresponding tasks to be included in the portfolio,
(2)
allocation of funds to tasks of selected projects,
(3)
evaluation of synergetic effects produced by interdependences between projects/tasks included in the portfolio.


## 2. Some Background

Tables1 and 2 summarize some characteristics of portfolio problems considered in the references.Table 1
General characteristics.
Paper
Objectives
Maximum number of projects in portfolio
Resource allocation policy
Solution methodology
Ghasemzadeh and Archer, 2000 [18]
General benefits integrated in a weighted sum
10
Complete
Integer linear programming model adjusted interactively
Stummer and Heidenberger, 2003 [4]
General benefit and resources consumption by period of scheduling
30
Complete
Integer linear programming model  to get efficient solutions; the best compromise solution is selected interactively
Wang and Hwang, 2007 [6]
Total benefit obtained by summing expected returns of the projects minus total inversion
20
Partial
Fuzzy model
Gutjahr et al., 2008 [7]
Economic gains and strategic gains
18
Partial
Nonlinear mixed integer programming model, greedy heuristic, and two alternative metaheuristics (ACO and GA)
Carazo et al., 2010 [5]
General benefit categories
90
Complete
Metaheuristics (SS-PPS, Scatter Search)
Gutjahr et al., 2010 [8]
Economic benefits and competence benefits
18
Partial
Mixed integer linear model, two metaheuristics (NSGA-II and P-ACO)
Litvinchev et al., 2010 [15]
Portfolio quality and number of projects in portfolio integrated in a weighted sum
25000
Partial
Mixed integer linear programming model; a compromise solution is obtained interactively
Litvinchev et al., 2011 [16]
Portfolio quality and number of projects in portfolio integrated in a weighted sum
10000
Partial
Mixed integer linear programming model; a compromise solution is obtained interactively
Gutjahr and Froeschl, 2013 [9]
Expected return minus outsourced costs
15
Partial
Metaheuristic method (S-VNS) and the Frank-Wolfe algorithmTable 2
Specific characteristics.
Paper
Balance constraints
Tasks
Interdependencies
Scheduling
Risk
Ghasemzadeh and Archer, 2000 [18]
No
No
General
Multiple periods
As an attribute of portfolio
Stummer and Heidenberger, 2003 [4]
No
No
Benefit, increment, or decrement in resources consumption
Multiple periods
No
Wang and Hwang, 2007 [6]
No
No
No
Single period
Risk aversion
Gutjahr et al., 2008 [7]
No
Yes
No
Multiple periods
No
Carazo et al., 2010 [5]
No
No
Benefit, increment, or decrement in resources consumption
Multiple periods
As an attribute in portfolio
Gutjahr et al., 2010 [8]
No
Yes
No
Multiple periods
No
Litvinchev et al., 2010 [15]
No
No
No
Single period
Neutral position
Litvinchev et al., 2011 [16]
Yes
Yes
Benefit, increment, or decrement in resources consumption
Single period
Neutral position
Gutjahr and Froeschl, 2013 [9]
No
Yes
Yes
Multiple periods
Risk aversion by penalizing the variance of the returnTable1 shows that there is a tendency to consider more than one objective in the evaluation of the portfolio.These objectives can be of general form as in [4, 5] or may represent specific measures associated with a set of attributes. Portfolio problems in the private sector are focused mainly on inversion related objectives and sales, among other market related issues. In social or public areas, usually the aim is to maximize the quality of the portfolio related to the social impact of the projects selected.The total allocation of resources means that once a project was selected for inclusion in the portfolio, it receives all requested resources. However, in many real situations, it is important to consider partial allocations of resources when a project receives less than what was requested.In the work of Wang and Hwang [6], they consider the uncertain character of the project cost and use fuzzy sets concept for modeling. Though resource assignment was not considered explicitly in their model, a partial assignment is implied.Table2 presents some characteristics of social portfolios. Balance constraints may be established by organizations to set upper/lower bounds for funds designated, in particular, for R&D areas. This way, the portfolio can be balanced to assure at least minimal funding for some specific areas.Another important characteristic of the social portfolio problems is considering a project as a set of tasks, each with a certain impact on the project objectives. In [7–9], the projects are represented by tasks that require human resources and that have relations of precedence in the planning horizon. In [10, 11], tasks are also used in project portfolio scheduling. It was pointed out in [12] that, by representing projects by tasks, it is possible to have a control of expenses or resources consumption or even of the impact of projects on portfolio impact measures.Since, in social area, usually only one time period is considered, only a single evaluation of proposals is implemented and a single decision on funding is taken. In contrast, in private area, proposals can be reevaluated to continue funding or even stop funding and choose another project for support if a project is no longer attractive for investment.


## 3. The Model

It is assumed that there is a set of projects competing for funding in a number of areas of research and development, such that every project belongs to a single area. The project consists of a number of tasks and the project is supported if at least one of its tasks is supported.The project is funded sufficiently if it receives support in a certain interval of funding. The corresponding benefit function increases linearly on this interval and is zero for funding below the minimal value (see [13] for details). Sufficient funding for tasks is defined similarly.To represent interdependency between different projects/tasks, the concept of synergy is used. Generally speaking, synergy arises when the total indicator corresponding to elements (projects, tasks, etc.) from the synergy is different from the sum of indicators corresponding to the same elements considered independently. More specifically, synergy is interpreted as a set of tasks corresponding to certain projects that, being supported sufficiently, produce an effect of changing the benefit or increase/decrease of funds. In [4], it was assumed that synergy is activated if all its elements are funded sufficiently; that is, cardinality of synergy coincides with that of the set of the elements funded. In this paper, we use a more flexible definition of synergy. Similar to [5, 14], we say that synergy is activated if a number of its elements funded sufficiently lie within certain bounds.Three types of synergies are considered. Benefit synergies, being activated, result in increase/decrease of the overall benefit of the portfolio. Resource synergies result in increase/decrease of the overall funding to elements of synergy. It is assumed that resource synergies are defined for tasks corresponding to projects of the same area. Technical synergies aimed to limit the number of activated synergies of certain type. To state the model mathematically, the following notation is used.


### 3.1. Sets and Parameters

J: set of projects competing for financial support, j
=
1,2
,
3
,
…
,
|
J
|.
K: set of areas of research and development, its indices k
=
1,2
,
3
,
…
,
|
K
|.
J
k: set of projects belonging to area k.
I: set of tasks i
=
1,2
,
3
,
…
|
I
|.
C: set of synergies, s
=
1,2
,
3
,
…
|
C
|.
C
s: set of elements (pairs) of synergy s, C
s
=
{
(
j
1
,
i
1
)
,
(
j
2
,
i
2
)
,
…
,
(
j
|
C
s
|
,
i
|
C
s
|
)
}.
B: set of benefit type synergies, B
⊂
C.
L: set of synergies of funds reduction, L
⊂
C.
H: set of synergies of funds enlargement, H
⊂
C.
τ: set of technical synergies.
η
s: value of synergetic effect of funds reduction by synergy s.
λ
s: value of synergetic effect of funds enlargement by synergy s.
ν
s: value of synergetic effect of benefit by synergy s.
w
j: the social impact of the project j.
ρ
j
i: relative importance of the task i of the project j.
P
G: available budget.
R
j
i
-, R
j
i
+: minimum and maximum amount to fund the task j
,
i.
P
k
-, P
k
+: minimum and maximum amount of funds to the area k.
M
j
-, M
j
+: minimum and maximum amount to fund the project j.
m
s
-, m
s
+: minimum and maximum number of tasks to enable synergy s.
E
T
-, E
T
+: minimum and maximum number of synergies to enable technical synergy T.
d
j
-, d
j
+: minimum and maximum number of projects to fund by area.


### 3.2. Variables

Letx
j
i be an amount of funds assigned to task i of project j. Consider
(1)
y
j
=
{
1
,
the
project
j
is
enough
supported
0
,
otherwise
z
j
i
=
{
1
,
the
task
j
,
i
is
enough
supported
0
,
otherwise
σ
1
s
=
{
1
,
synergetic
set
has
cardinality
≥
m
s
-
0
,
otherwise
σ
2
s
=
{
1
,
synergetic
set
has
cardinality
≤
m
s
+
0
,
otherwise
σ
s
=
{
1
,
synergy
s
is
activated
,
σ
s
=
σ
1
s
+
σ
2
s
-
1
0
,
otherwise
.


### 3.3. Objectives

Two objectives are considered:(
1
) represents the quality of the portfolio in a similar way as in Litvinchev et al. [15] and (
2
) represents the total amount of funded projects:
(2)
∑
j
∈
J
w
j
(
∑
i
∈
I
(
a
j
i
z
j
i
+
b
j
i
x
j
i
)
·
ρ
j
i
)
+
∑
s
∈
B
ν
s
σ
s
(3)
∑
j
∈
J
y
j
.
We consider the number of funded projects as an objective since if we have two portfolios with equal quality and resource consumption, the portfolio with more projects is preferable.In (2), the parameters a
j
i and b
j
i are defined similarly to Litvinchev et al. [15] but adjusted to the representation of projects by tasks. Essentially, the predicate “a task is sufficiently funded” is modeled with a degree of truth represented by a piecewise linear function μ
j
i, Figure 1 increasing on [R
j
i
-
,
R
j
i
+], such that μ
j
i
(
R
j
i
+
)
=
α
j
i and μ
j
i
(
R
j
i
-
)
=
1 [15].Figure 1
Representation of the piecewise linear function.In this way, the parametersa
j
i and b
j
i are defined such that a
j
i
+
b
j
i
x
j
i
=
1 for x
j
i
=
R
j
i
+ and a
j
i
+
b
j
i
x
=
α
j
i for x
j
i
=
R
j
i
-.Thus,(4)
a
j
i
=
α
j
i
-
R
j
i
-
(
1
-
α
j
i
)
R
j
i
+
-
R
j
i
-
,
b
j
i
=
(
1
-
α
j
i
)
R
j
i
+
-
R
j
i
-
.
For the case R
j
i
-
<
R
j
i
+, the expressions in (4), as well as the coefficients of the objective (2), are well defined. If R
j
i
-
=
R
j
i
+ or are very close to each other, the objective (2) has to be modified. For R
j
i
-
=
R
j
i
+, we may set a
j
i
=
1, b
j
i
=
0, such that the corresponding benefit is either 0 or a
j
i. Note that, in this case by constraint (8) below, the task is either supported completely (z
j
i
=
1) or not supported at all (z
j
i
=
0).


### 3.4. Constraints

The constraints of the model are(5)
∑
j
∈
J
∑
i
∈
I
x
j
i
≤
P
G
(6)
P
k
-
≤
∑
j
∈
J
k
∑
i
∈
I
x
j
i
≤
P
k
+
,
k
∈
K
(7)
M
j
-
y
j
≤
∑
i
∈
I
x
j
i
≤
M
j
+
y
j
,
j
∈
J
(8)
R
j
i
-
z
j
i
≤
x
j
i
≤
R
j
i
+
z
j
i
,
{
i
∈
I
,
j
∈
J
(
j
,
i
)
∉
L
∪
H
(9)
y
j
≤
∑
i
∈
I
z
j
i
,
j
∈
J
(10)
∑
i
∈
I
z
j
i
≤
|
I
|
y
j
,
j
∈
J
(11)
∑
(
j
,
i
)
∈
C
s
z
j
i
-
m
s
-
+
1
≤
|
C
s
|
σ
1
s
,
s
∈
C
(12)
|
C
s
|
σ
1
s
≤
∑
(
j
,
i
)
∈
C
s
z
j
i
-
m
s
-
+
|
C
s
|
,
s
∈
C
(13)
m
s
+
-
∑
(
j
,
i
)
∈
C
s
z
j
i
+
1
≤
|
C
s
|
σ
2
s
,
s
∈
C
(14)
|
C
s
|
σ
2
s
≤
m
s
+
-
∑
(
j
,
i
)
∈
C
s
z
j
i
+
|
C
s
|
,
s
∈
C
(15)
σ
s
=
σ
1
s
+
σ
2
s
-
1
,
s
∈
C
(16)
∑
(
j
,
i
)
∈
C
s
x
j
i
≤
∑
(
j
,
i
)
∈
C
s
R
j
i
+
z
j
i
-
η
s
σ
s
,
s
∈
L
(17)
∑
(
j
,
i
)
∈
C
s
x
j
i
≥
∑
(
j
,
i
)
∈
C
s
R
j
i
-
z
j
i
+
λ
s
σ
s
,
s
∈
H
(18)
∑
(
j
,
i
)
∈
C
s
x
j
i
≥
∑
(
j
,
i
)
∈
C
s
R
j
i
-
z
j
i
-
η
s
σ
s
,
s
∈
L
(19)
∑
(
j
,
i
)
∈
C
s
x
j
i
≤
∑
(
j
,
i
)
∈
C
s
R
j
i
+
z
j
i
+
λ
s
σ
s
,
s
∈
H
(20)
E
T
-
≤
∑
s
∈
T
σ
s
≤
E
T
+
,
T
∈
τ
(21)
x
j
i
≥
0
,
y
j
,
z
j
i
,
σ
s
,
σ
1
s
,
σ
2
s
∈
{
0,1
}
.
Constraints (5)–(8) are typical budged constraints, defined at portfolio, area, project, and task levels, respectively. Constraints (9)-(10) relate tasks to projects. All these constraints are defined in Litvinchev et al. [16].Constraints (11)–(15) represent the activation of synergies. Defining synergies at the task level provides more flexibility comparing with the definition of synergies at the project level. Here a synergy is activated if a subset of tasks in C
s is funded with cardinality less than a number m
s
+and greater than a m
s
- (see also [5]).Ifm
s
+
=
m
s
-, this implies that the synergy s is activated only if all the tasks associated with that synergy are supported. In (11)–(14), variables σ
1
s and σ
2
s correspond to lower and upper limits, respectively. We define σ
s in terms of the previous two variables to verify that the synergy s is activated. Variables σ
1
s and σ
2
s cannot be equal to zero simultaneously, since that would imply that the sum ∑
(
j
,
i
)
∈
C
s
z
j
i is less than m
s
-and greater than m
s
+. This is impossible since m
s
-
≤
m
s
+. Moreover, our formulation for the restriction (20) eliminates the nonlinearity of the model of Carazo et al. [5]. Constraints (16)–(19) represent resources synergies.Technical synergies are defined to keep control over the synergies of tasks that could be activated. The aim is to limit a number of active synergies from a group of them. We callT the set containing the indices of synergies to be limited; that is, T
=
{
s
1
,
s
2
,
s
3
,
…
,
s
|
T
|
}, so that only a number less than or equal to E
T
+ and/or greater than or equal to E
T
- of them can be active. The set of all T’s is τ. In our model, technical constraints are represented by constraint (20). This representation allows incorporating more than two groups of mutually exclusive groups of tasks.Other Constraints. In some cases, it is desirable to balance the portfolio for the number of projects supported by area. That is,
(22)
d
j
-
≤
∑
j
∈
J
k
y
j
≤
d
j
+
,
where d
j
- and d
j
+ are respective lower and upper bounds.


## 3.1. Sets and Parameters

J: set of projects competing for financial support, j
=
1,2
,
3
,
…
,
|
J
|.
K: set of areas of research and development, its indices k
=
1,2
,
3
,
…
,
|
K
|.
J
k: set of projects belonging to area k.
I: set of tasks i
=
1,2
,
3
,
…
|
I
|.
C: set of synergies, s
=
1,2
,
3
,
…
|
C
|.
C
s: set of elements (pairs) of synergy s, C
s
=
{
(
j
1
,
i
1
)
,
(
j
2
,
i
2
)
,
…
,
(
j
|
C
s
|
,
i
|
C
s
|
)
}.
B: set of benefit type synergies, B
⊂
C.
L: set of synergies of funds reduction, L
⊂
C.
H: set of synergies of funds enlargement, H
⊂
C.
τ: set of technical synergies.
η
s: value of synergetic effect of funds reduction by synergy s.
λ
s: value of synergetic effect of funds enlargement by synergy s.
ν
s: value of synergetic effect of benefit by synergy s.
w
j: the social impact of the project j.
ρ
j
i: relative importance of the task i of the project j.
P
G: available budget.
R
j
i
-, R
j
i
+: minimum and maximum amount to fund the task j
,
i.
P
k
-, P
k
+: minimum and maximum amount of funds to the area k.
M
j
-, M
j
+: minimum and maximum amount to fund the project j.
m
s
-, m
s
+: minimum and maximum number of tasks to enable synergy s.
E
T
-, E
T
+: minimum and maximum number of synergies to enable technical synergy T.
d
j
-, d
j
+: minimum and maximum number of projects to fund by area.


## 3.2. Variables

Letx
j
i be an amount of funds assigned to task i of project j. Consider
(1)
y
j
=
{
1
,
the
project
j
is
enough
supported
0
,
otherwise
z
j
i
=
{
1
,
the
task
j
,
i
is
enough
supported
0
,
otherwise
σ
1
s
=
{
1
,
synergetic
set
has
cardinality
≥
m
s
-
0
,
otherwise
σ
2
s
=
{
1
,
synergetic
set
has
cardinality
≤
m
s
+
0
,
otherwise
σ
s
=
{
1
,
synergy
s
is
activated
,
σ
s
=
σ
1
s
+
σ
2
s
-
1
0
,
otherwise
.


## 3.3. Objectives

Two objectives are considered:(
1
) represents the quality of the portfolio in a similar way as in Litvinchev et al. [15] and (
2
) represents the total amount of funded projects:
(2)
∑
j
∈
J
w
j
(
∑
i
∈
I
(
a
j
i
z
j
i
+
b
j
i
x
j
i
)
·
ρ
j
i
)
+
∑
s
∈
B
ν
s
σ
s
(3)
∑
j
∈
J
y
j
.
We consider the number of funded projects as an objective since if we have two portfolios with equal quality and resource consumption, the portfolio with more projects is preferable.In (2), the parameters a
j
i and b
j
i are defined similarly to Litvinchev et al. [15] but adjusted to the representation of projects by tasks. Essentially, the predicate “a task is sufficiently funded” is modeled with a degree of truth represented by a piecewise linear function μ
j
i, Figure 1 increasing on [R
j
i
-
,
R
j
i
+], such that μ
j
i
(
R
j
i
+
)
=
α
j
i and μ
j
i
(
R
j
i
-
)
=
1 [15].Figure 1
Representation of the piecewise linear function.In this way, the parametersa
j
i and b
j
i are defined such that a
j
i
+
b
j
i
x
j
i
=
1 for x
j
i
=
R
j
i
+ and a
j
i
+
b
j
i
x
=
α
j
i for x
j
i
=
R
j
i
-.Thus,(4)
a
j
i
=
α
j
i
-
R
j
i
-
(
1
-
α
j
i
)
R
j
i
+
-
R
j
i
-
,
b
j
i
=
(
1
-
α
j
i
)
R
j
i
+
-
R
j
i
-
.
For the case R
j
i
-
<
R
j
i
+, the expressions in (4), as well as the coefficients of the objective (2), are well defined. If R
j
i
-
=
R
j
i
+ or are very close to each other, the objective (2) has to be modified. For R
j
i
-
=
R
j
i
+, we may set a
j
i
=
1, b
j
i
=
0, such that the corresponding benefit is either 0 or a
j
i. Note that, in this case by constraint (8) below, the task is either supported completely (z
j
i
=
1) or not supported at all (z
j
i
=
0).


## 3.4. Constraints

The constraints of the model are(5)
∑
j
∈
J
∑
i
∈
I
x
j
i
≤
P
G
(6)
P
k
-
≤
∑
j
∈
J
k
∑
i
∈
I
x
j
i
≤
P
k
+
,
k
∈
K
(7)
M
j
-
y
j
≤
∑
i
∈
I
x
j
i
≤
M
j
+
y
j
,
j
∈
J
(8)
R
j
i
-
z
j
i
≤
x
j
i
≤
R
j
i
+
z
j
i
,
{
i
∈
I
,
j
∈
J
(
j
,
i
)
∉
L
∪
H
(9)
y
j
≤
∑
i
∈
I
z
j
i
,
j
∈
J
(10)
∑
i
∈
I
z
j
i
≤
|
I
|
y
j
,
j
∈
J
(11)
∑
(
j
,
i
)
∈
C
s
z
j
i
-
m
s
-
+
1
≤
|
C
s
|
σ
1
s
,
s
∈
C
(12)
|
C
s
|
σ
1
s
≤
∑
(
j
,
i
)
∈
C
s
z
j
i
-
m
s
-
+
|
C
s
|
,
s
∈
C
(13)
m
s
+
-
∑
(
j
,
i
)
∈
C
s
z
j
i
+
1
≤
|
C
s
|
σ
2
s
,
s
∈
C
(14)
|
C
s
|
σ
2
s
≤
m
s
+
-
∑
(
j
,
i
)
∈
C
s
z
j
i
+
|
C
s
|
,
s
∈
C
(15)
σ
s
=
σ
1
s
+
σ
2
s
-
1
,
s
∈
C
(16)
∑
(
j
,
i
)
∈
C
s
x
j
i
≤
∑
(
j
,
i
)
∈
C
s
R
j
i
+
z
j
i
-
η
s
σ
s
,
s
∈
L
(17)
∑
(
j
,
i
)
∈
C
s
x
j
i
≥
∑
(
j
,
i
)
∈
C
s
R
j
i
-
z
j
i
+
λ
s
σ
s
,
s
∈
H
(18)
∑
(
j
,
i
)
∈
C
s
x
j
i
≥
∑
(
j
,
i
)
∈
C
s
R
j
i
-
z
j
i
-
η
s
σ
s
,
s
∈
L
(19)
∑
(
j
,
i
)
∈
C
s
x
j
i
≤
∑
(
j
,
i
)
∈
C
s
R
j
i
+
z
j
i
+
λ
s
σ
s
,
s
∈
H
(20)
E
T
-
≤
∑
s
∈
T
σ
s
≤
E
T
+
,
T
∈
τ
(21)
x
j
i
≥
0
,
y
j
,
z
j
i
,
σ
s
,
σ
1
s
,
σ
2
s
∈
{
0,1
}
.
Constraints (5)–(8) are typical budged constraints, defined at portfolio, area, project, and task levels, respectively. Constraints (9)-(10) relate tasks to projects. All these constraints are defined in Litvinchev et al. [16].Constraints (11)–(15) represent the activation of synergies. Defining synergies at the task level provides more flexibility comparing with the definition of synergies at the project level. Here a synergy is activated if a subset of tasks in C
s is funded with cardinality less than a number m
s
+and greater than a m
s
- (see also [5]).Ifm
s
+
=
m
s
-, this implies that the synergy s is activated only if all the tasks associated with that synergy are supported. In (11)–(14), variables σ
1
s and σ
2
s correspond to lower and upper limits, respectively. We define σ
s in terms of the previous two variables to verify that the synergy s is activated. Variables σ
1
s and σ
2
s cannot be equal to zero simultaneously, since that would imply that the sum ∑
(
j
,
i
)
∈
C
s
z
j
i is less than m
s
-and greater than m
s
+. This is impossible since m
s
-
≤
m
s
+. Moreover, our formulation for the restriction (20) eliminates the nonlinearity of the model of Carazo et al. [5]. Constraints (16)–(19) represent resources synergies.Technical synergies are defined to keep control over the synergies of tasks that could be activated. The aim is to limit a number of active synergies from a group of them. We callT the set containing the indices of synergies to be limited; that is, T
=
{
s
1
,
s
2
,
s
3
,
…
,
s
|
T
|
}, so that only a number less than or equal to E
T
+ and/or greater than or equal to E
T
- of them can be active. The set of all T’s is τ. In our model, technical constraints are represented by constraint (20). This representation allows incorporating more than two groups of mutually exclusive groups of tasks.Other Constraints. In some cases, it is desirable to balance the portfolio for the number of projects supported by area. That is,
(22)
d
j
-
≤
∑
j
∈
J
k
y
j
≤
d
j
+
,
where d
j
- and d
j
+ are respective lower and upper bounds.


## 4. Numerical Experiments

Different groups of instances were generated varying the number of projects proposals, tasks, and synergies. The objective of the first part of the numerical study was to test the tractability of the model for large-scale instances. The commercial software CPLEX 12.5 was used for optimization running on a server DELL PowerEdge 2950 with 8 cores. Six classes of instances were generated each having 15 replications:(
1
) 100 projects, 2 areas, 5 tasks, and 5 synergies; (
2
) 500 projects, 2 areas, 15 tasks, and 40 synergies; (
3
) 1000 projects, 2 areas, 15 tasks, and 80 synergies; (
4
) 1000 projects, 2 areas, 15 tasks, and 200 synergies; (
5
) 10000 projects, 4 areas, 15 tasks, and 0 synergies; and (
6
) 25000 projects, 4 areas, 1 task, and 0 synergies. The instances were coded according to Projects Areas Tasks Synergies, such that P100A2T5S5 corresponds to the first class.Table3 shows the results for one run of the model using a weighted sum of the objectives (weighting parameters of 0.5 for both objectives were used in all experiments). For instances with less than 1000 projects, the running time was on average less than 1 min. For large-scale instances with more than 1000 projects, the running time increased in the worst case up to 10 min.Table 3
CPU time.
Instance
Mean CPU time (sec.)
Std. dev.
P100A2T5S5
0.208
0.034
P500A2T15S40
6.397
1.035
P1000A2T15S80
59.158
17.462
P1000A2T15S200
328.233
132.692
P10000A4T15S0
588.47
223.18
P25000A4T1S0
8.67
2.11From Table3, we may conclude that the number of projects is not a critical factor for the increasing of CPU time. However the number of tasks and, especially, the number of synergies represent a key factor for the complexity of the problem, as can be observed in instances P25000A4T15S0 and P1000A4T15S200. Bearing in mind that the model is used for long-term decisions, we may conclude that the model provides decisions in a reasonable time. For more numerical experiments for very large-scale instances, see Irarragori and Martínez [17].The second part of the numerical experiment was conducted to see the behavior of the model subject to changes in some parameters. In particular, upper and lower bounds for the funds to be assigned for projects and tasks were of special interest. Three classes of 15 instances were considered (P100A2T5S5, P500A2T15S40, and P1000A2T15S80).First, all instances were solved and the respective values of the objectives (quality of the portfolio and number of projects) and the solution time were stored. Then we reduced the interval[
R
j
i
-
,
R
j
i
+
] of possible funding for each task of the project. This was done by shifting the minimal amount R
j
i
- towards the maximal value R
j
i
+ keeping the later constant. The new interval was obtained in the form [
R
j
i
-
+
γ
(
R
j
i
+
-
R
j
i
-
)
,
R
j
i
+
], where γ
∈
[
0,1
] represents the index of reduction. In the experiment 7 levels of reduction were considered corresponding to different values of γ (in %): 10%, 30%, 50%, 90%, 95%, and 100%. Reduction 100% (γ
=
1) corresponds to R
j
i
-
=
R
j
i
+. In this case by constraint (8), the task is either supported completely (z
j
i
=
1) or not supported at all (z
j
i
=
0). The reduction of funds was applied to a different number of projects. We selected randomly 25%, 50%, 75%, and 100% of all the projects being subject to funds reduction.The results of the corresponding computational experiment are summarized in Tables4–6. The indicators presented in these tables are the average (over all problem instances) reductions in number of projects supported and in the quality measure. More specifically, the quality reduction indicator (QR) in Tables 4(a), 5(a), and 6(a) was defined as QR
=
(
1
-
N
Q
/
Q
)
·
100
%, where Q denotes the quality measure without funds reduction, while N
Q states the quality measure after funds reduction. Similarly, the project reduction indicator (PR) in Tables 4(b), 5(b), and 6(b) was defined as PR
=
(
1
-
N
P
/
P
)
·
100
%, where P and N
P denote the number of projects before and after funds reduction, respectively.Table 4
QR (a) and PR (b) for instances of P100A2T5S5.
(a)
Projects with reduction (in %)
Reduction indexγ (in %)
10
30
50
90
95
100
25
0.847
1.138
1.753
5.913
5.655
5.816
50
0.907
2.367
3.401
9.925
9.757
9.851
75
1.858
4.217
5.731
13.018
12.741
12.890
100
1.652
4.659
7.650
15.259
16.043
16.784
(b)
Projects with reduction (in %)
Reduction indexγ (in %)
10
30
50
90
95
100
25
0.816
2.961
5.621
11.173
11.664
11.749
50
1.968
6.348
11.636
19.274
20.020
20.689
75
2.637
9.438
17.877
29.812
30.555
30.965
100
4.635
13.324
23.844
39.151
39.900
40.994Table 5
QR (a) and PR (b) for instances of P500A2T15S40.
(a)
Projects with reduction (in %)
Reduction indexγ (in %)
10
30
50
90
95
100
25
0.169
0.680
0.346
8.360
9.217
9.966
50
0.869
0.902
1.488
12.197
12.930
13.535
75
1.100
1.787
3.383
15.283
16.404
16.971
100
1.344
2.729
5.038
18.564
20.431
20.726
(b)
Projects with reduction (in %)
Reduction indexγ (in %)
10
30
50
90
95
100
25
1.512
4.066
7.152
12.771
12.711
13.348
50
2.401
8.149
13.050
21.857
23.123
23.555
75
3.726
11.790
19.031
31.944
33.467
34.114
100
5.279
15.393
24.978
41.012
43.177
43.922Table 6
QR (a) and PR (b) for instances of  P1000A2T15S80.
(a)
Projects with reduction (in %)
Reduction indexγ (in %)
10
30
50
90
95
100
25
0.770
1.066
1.614
8.833
9.123
9.236
50
0.903
2.127
3.355
12.525
13.251
13.664
75
1.178
3.240
4.806
16.196
17.662
17.930
100
1.594
4.360
6.217
19.996
21.760
22.157
(b)
Projects with reduction (in %)
Reduction indexγ (in %)
10
30
50
90
95
100
25
0.811
3.744
6.172
12.461
12.882
13.047
50
2.386
7.456
12.476
22.131
23.036
23.546
75
3.614
11.195
18.733
31.243
32.798
33.440
100
4.849
14.914
24.714
40.698
42.640
43.480Observing the columns in Tables4–6, we may conclude that both QR and PR increase monotonously as long as the number of projects with funds reduction is increased. This holds for all problem instances and all indices γ of funds reduction. That is, applying funds reduction to more projects results in stronger decrease for both objectives of the problem, the quality, and the number of projects in the portfolio.Considering the rows in Tables4–6, we see that, for the fixed number of projects with funds reduction, both QR and PR typically increase as long as the value of the funds reduction index γ is increased. However, this is not always the case. For example, comparing the first 3 rows in Table 4(a), we see that the QR slightly decreases when γ changes from 90% to 95%. That is, reducing the funds results in increase of the quality. However, this is “compensated” by decrease in the number of projects supported.Generally speaking, the weighted criterion (the weighted sum of the quality and the number of projects) decreases as long as the funds reductionγ increases. This holds since solution to the weighted problem (2)–(22) obtained for a smaller funding interval remains feasible for the same problem with a larger funding interval. But this does not mean that both terms, quality and projects, have to be decreased. An increase of one term can be compensated by a larger decrease of the other.Table7 presents the values of indicator characterizing relative changes of CPU time due to funds reduction. This indicator was defined as TR
=
(
N
T
/
T
-
1
)
100
%, where T is CPU time without funds reduction and N
T corresponds to CPU time after funds reduction. Note that a negative value of TR indicates that N
T is less than T. The average (over 15 problem instances) value of the indicator is presented.Table 7
Relative change of CPU time for P100A2T5S5 (a), P500A2T15S40 (b), and P1000A2T15S80 (c).
(a)
Projects with reduction (in %)
Reduction indexγ (in %)
10
30
50
90
95
100
25
5.77
10.10
7.69
25.00
20.67
20.67
50
−1.44
13.46
16.83
22.12
30.77
29.33
75
2.88
0.96
34.62
11.54
13.46
21.63
100
5.29
15.87
42.31
53.37
26.92
8.17
(b)
Projects with reduction (in %)
Reduction indexγ (in %)
10
30
50
90
95
100
25
0.86
41.30
70.60
88.93
40.19
39.91
50
11.46
63.87
112.47
108.32
57.56
30.31
75
34.23
82.15
166.30
149.74
101.00
70.17
100
45.24
153.93
236.38
349.07
221.23
182.21
(c)
Projects with reduction (in %)
Reduction indexγ (in %)
10
30
50
90
95
100
25
0.85
−23.97
−19.04
−18.20
−13.98
−12.55
50
5.24
−38.80
8.84
−17.29
−36.57
−28.56
75
6.19
−11.91
86.36
0.44
−30.70
−45.96
100
16.25
65.65
165.24
44.41
63.64
56.82As we can see from Table7, if funds reduction is applied to all projects (the last row in tables), then reducing interval of funding always results in increase of CPU time (all values in the last row are positive). That is, instances with complete (all or nothing) type of funding for all projects are more difficult to solve for this model. However, if funds reduction is applied only to a part of projects, CPU time may either increase or decrease (negative values in the table). Comparing with the values of CPU time presented in Table 3, we may conclude that even if CPU time increases, it is still reasonably low.


## 5. Conclusions

This paper studies portfolio selection problem for R&D projects in public organizations. Two objectives are considered: benefit (the quality of portfolio related to the social impact of projects) and number of projects supported. It is assumed that there is a set of projects competing for funding in a number of areas of R&D, such that every project belongs to a single area. The project consists of a number of tasks and the project is supported if at least one task is supported. The project/task is funded sufficiently if it receives support in a certain interval of funding. The interdependency between projects/tasks is modeling using the general concept of synergy. A synergy is active if a number of its elements supported sufficiently are within certain bounds. Three types of synergies are considered, affecting the benefit, changing resource consumptions, and the so-called technical synergies, aimed at limiting the number of active synergies. A corresponding mixed integer linear model is presented providing solutions to large-scale instances in a reasonable time.We demonstrated that, within the proposed model, the project/task can be supported, completely, receiving the funds requestedor, partially, receiving funds within a certain interval; that is, the concept of sufficient (continuous) funding was implemented.The computational experiment demonstrates that increasing the number of projects subject to funds reduction results in decrease for both objectives. However, if the number of projects subject to funds reduction is fixed but the strength of funds reduction is increased, one of the objectives may increase at the expense of a larger decrease of another.Only one type of the resources (funds) was considered in the model. An interesting direction for future research is studying problems with multiple resources, where synergetic effects can arise not only at the level of projects/tasks, but also at the level of resources.



---

*Source: 654293-2014-04-23.xml*