# Stuck on an Integer Programming problem

## Homework Statement

I've tried hours and hours to model this problem but i didn't succeed. Can you help me ?

We want to realize n projects in the next T years. For each project, a
profitability index pi is known, which expresses the expected final
gain (in Euro) and a cost profile ai = (ai1, ai2, ..., aiT) for each
year of the period considered. Moreover, in each year j of the period
a budget of bj € is available. Which projects should be selected to
maximize the expected profit while respecting budget constraints?

Assume that the projects have a duration of T '< T years. For each
selected project, we also want to identify the start year.

note: take care that if i start a project at year 2 , all the $a_{i}$ are shifted by 2 from the initial year ( that is 1))

## The Attempt at a Solution

[/B]
Sometime ago i succeeded in modeling the non-bold part of the problem, however if i try to add also the last requirement i dont understand what to change of my original formulation, that is :

$$max \sum_{i=1}^{n} p_{i}x_{i}$$

$$\sum_{i=1}^{n} a_{ij}x_{i}=b_{j} , j=1..T$$

$$x_{i}\in \left \{ 0,1 \right \} , i=1..n$$

mfb
Mentor

• Aleoa
Can you show me a prototype ? I spent a lot of time on this problem and i have no more valid ideas

Ray Vickson
Homework Helper
Dearly Missed

## Homework Statement

I've tried hours and hours to model this problem but i didn't succeed. Can you help me ?

We want to realize n projects in the next T years. For each project, a
profitability index pi is known, which expresses the expected final
gain (in Euro) and a cost profile ai = (ai1, ai2, ..., aiT) for each
year of the period considered. Moreover, in each year j of the period
a budget of bj € is available. Which projects should be selected to
maximize the expected profit while respecting budget constraints?

Assume that the projects have a duration of T '< T years. For each
selected project, we also want to identify the start year.

note: take care that if i start a project at year 2 , all the $a_{i}$ are shifted by 2 from the initial year ( that is 1))

## The Attempt at a Solution

[/B]
Sometime ago i succeeded in modeling the non-bold part of the problem, however if i try to add also the last requirement i dont understand what to change of my original formulation, that is :

$$max \sum_{i=1}^{n} p_{i}x_{i}$$

$$\sum_{i=1}^{n} a_{ij}x_{i}=b_{j} , j=1..T$$

$$x_{i}\in \left \{ 0,1 \right \} , i=1..n$$

One way to model the scenario would be to introduce additional variables, such as
$$x_{ij} = \begin{cases}1 &\text{if start project i in period j} \\ 0 &\text{otherwise} \end{cases}$$

• Aleoa
One way to model the scenario would be to introduce additional variables, such as
$$x_{ij} = \begin{cases}1 &\text{if start project i in period j} \\ 0 &\text{otherwise} \end{cases}$$

Yes, i also attempt this way and after defining the decision variables as you suggested i tried to create a matrix M where put the coefficients $a_{i,j}$ based on the starting year of the i-th problem. However i didn't succeed in doing this, can you help me ?

$max \sum_{i=0}^{n-1} p_{i}(\sum_{j=0}^{y-1}x_{i,j})$

$x_{i,j}M_{i,j+k}=x_{i,j}a_{i,k}$ j=0..y , k=0..Ti-1

$\sum_{j=0}^{y}M_{i,j}\leq \sum_{j=0}^{y}a_{i,j}$ i=0..n-1

$\sum_{j=0}^{n-1}M_{i,j}\leq b_{i}$ i=0..y-1

$M_{i,j} \geq 0$ , $x_{i,j} \in \left \{ 0,1 \right \}$

y represents the number of years,
n represents the number of projects

Anyone can tell me if is correct ? Or propose your own version?

:)

Ray Vickson
Homework Helper
Dearly Missed
Anyone can tell me if is correct ? Or propose your own version?

:)

No, it is incorrect---at least if you want a linear integer programming formulation. If your ##M_{ij}## are (real) variables, some of your constraints contain nonlinear terms because they involve products ##x_{ij} M_{i,j+k}## of the variables. Anyway the formulation is incomprehensible without some explanation of what the ##M##-variables represent.

• StoneTemplePython
StoneTemplePython
Gold Member
my sense is you're close and just a little bit of refinement will get you there...

In order to reformulate the problem i'm trying to model this in linear programming

$\sum_{t=y}^{C}x_{t}= a$
where y is a variable (and also ##x_{t}##; C and a are constants)

However i didn't succeed, can you show me ?

<edit: fix latex>

Last edited by a moderator:
Ray Vickson
Homework Helper
Dearly Missed
In order to reformulate the problem i'm trying to model this in linear programming

$\sum_{t=y}^{C}x_{t}= a$
where y is a variable (and also $x_{t}$; C and a are constants)

However i didn't succeed, can you show me ?

No, we are not allowed to do that. However, I think I can give some hints for a 2-period, 2-project example.

So, the variables are ##x_{11}, x_{21}## for starting projects 1 and 2 in period 1; similarly for ##x_{12}, x_{22}.## The resource-usage in period 1 is ##a_{11} x_{11} + a_{21} x_{21}.## The resource-usage in period 2 is ##a_{12} x_{11}+ a_{22}x_{21}+a_{11} x_{12} + a_{21} x_{22}.## We need ##x_{11}+x_{12} \leq 1,## because project 1 can be started at most once.

I tried to find a way to build a matrix with the $a_{i,j}$ shifted based on the start year of i-th project.

I came out with this:

$M_{i,j}=\sum_{y=1}^{j}(a_{i,y})(x_{i,j+1-y})$

Is this correct ?

Ray Vickson
Homework Helper
Dearly Missed
I tried to find a way to build a matrix with the $a_{i,j}$ shifted based on the start year of i-th project.

I came out with this:

$M_{i,j}=\sum_{y=1}^{j}(a_{i,y})(x_{i,j+1-y})$

Is this correct ?
How can we tell? You do not explain what the matrix ##M## is supposed to represent!

How can we tell? You do not explain what the matrix ##M## is supposed to represent!

Is a matrix nxm of variables where n is the number of projects and m are the total years.
In row i is placed the cost vector ai ( ai is the cost of project i the first year it starts, ai is the cost of the second year since is started) .
In this way

$\sum_{i=1}^{p}M_{i,j}\leq b_{j}$
for j=1..Years

assure me that the budget per year is respected.

## Homework Statement

I've tried hours and hours to model this problem but i didn't succeed. Can you help me ?

We want to realize n projects in the next T years. For each project, a
profitability index pi is known, which expresses the expected final
gain (in Euro) and a cost profile ai = (ai1, ai2, ..., aiT) for each
year of the period considered. Moreover, in each year j of the period
a budget of bj € is available. Which projects should be selected to
maximize the expected profit while respecting budget constraints?

Assume that the projects have a duration of T '< T years. For each
selected project, we also want to identify the start year.

note: take care that if i start a project at year 2 , all the $a_{i}$ are shifted by 2 from the initial year ( that is 1))

## The Attempt at a Solution

[/B]
Sometime ago i succeeded in modeling the non-bold part of the problem, however if i try to add also the last requirement i dont understand what to change of my original formulation, that is :

$$max \sum_{i=1}^{n} p_{i}x_{i}$$

$$\sum_{i=1}^{n} a_{ij}x_{i}=b_{j} , j=1..T$$

$$x_{i}\in \left \{ 0,1 \right \} , i=1..n$$

Months have passed and I could not create the model. Is anyone kind enough to show me a possible solution?

Ray Vickson
$$\begin{array}{rcll} \max Z &=& p_1(x_{11}+x_{12}) + p_2 (x_{21} + x_{22}) & \text{(total gain)} \\ \text{s.t.} &&& \\ && x_{11} + x_{12} \leq 1 & \text{(start proj. 1 at most once)} \\ && x_{21} + x_{22} \leq 1 & \text{(start proj. 2 at most once)} \\ && c_{11} x_{11} + c_{21} x_{21} \leq b_1 &\text{(period 1 limit)} \\ &&c_{12} x_{11}+c_{22} x_{21} + c_{11} x_{12} + c_{21} x_{22} \leq b_2 & \text{(period 2 limit)} \\ && c_{12} x_{12} + c_{22} x_{22} \leq b_3 & \text{(period 3 limit)}\\ && x_{ij} \in \{0,1\}, \;\; i,j = 1,2& \end{array}$$