Stuck on an Integer Programming problem

[Aleoa]

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))

Homework Equations

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 don't 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]

You can add shifts s_i.

 

[Aleoa]

You can add shifts s_i.

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 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))

Homework Equations

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 don't 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 ?

 

[Aleoa]

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

 

[Aleoa]

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

:)

 

[Ray Vickson]

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]

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

 

[Aleoa]

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>

 

[Ray Vickson]

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.

 

[Aleoa]

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]

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!

 

[Aleoa]

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[1] is the cost of project i the first year it starts, ai[2] 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.

 

[Aleoa]

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))

Homework Equations

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 don't 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]

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

As I said before, we are not allowed to do that. However, I can give some more details for a 2-project case, where each project lasts for two periods. That means that we must allow ourselves three periods for the expenditures, but only two periods for project starts----somewhat artificial, I know. So, if the 0-1 variables $x_{ij}$ are as in post #4, we have:
$$\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}$$