Stuck on an Integer Programming problem

  • Thread starter Aleoa
  • Start date
  • #1
128
5

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 [itex]a_{i}[/itex] 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 dont understand what to change of my original formulation, that is :

[tex]max \sum_{i=1}^{n} p_{i}x_{i}[/tex]

[tex] \sum_{i=1}^{n} a_{ij}x_{i}=b_{j} , j=1..T[/tex]

[tex]x_{i}\in \left \{ 0,1 \right \} , i=1..n[/tex]
 

Answers and Replies

  • #2
35,258
11,510
You can add shifts si.
 
  • Like
Likes Aleoa
  • #3
128
5
You can add shifts si.
Can you show me a prototype ? I spent a lot of time on this problem and i have no more valid ideas
 
  • #4
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728

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 [itex]a_{i}[/itex] 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 dont understand what to change of my original formulation, that is :

[tex]max \sum_{i=1}^{n} p_{i}x_{i}[/tex]

[tex] \sum_{i=1}^{n} a_{ij}x_{i}=b_{j} , j=1..T[/tex]

[tex]x_{i}\in \left \{ 0,1 \right \} , i=1..n[/tex]
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}$$
 
  • Like
Likes Aleoa
  • #5
128
5
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 [itex]a_{i,j}[/itex] based on the starting year of the i-th problem. However i didn't succeed in doing this, can you help me ?
 
  • #6
128
5
[itex]max \sum_{i=0}^{n-1} p_{i}(\sum_{j=0}^{y-1}x_{i,j})[/itex]

[itex]x_{i,j}M_{i,j+k}=x_{i,j}a_{i,k}[/itex] j=0..y , k=0..Ti-1

[itex]\sum_{j=0}^{y}M_{i,j}\leq \sum_{j=0}^{y}a_{i,j}[/itex] i=0..n-1

[itex]\sum_{j=0}^{n-1}M_{i,j}\leq b_{i}[/itex] i=0..y-1

[itex]M_{i,j} \geq 0[/itex] , [itex]x_{i,j} \in \left \{ 0,1 \right \}[/itex]

y represents the number of years,
n represents the number of projects
 
  • #7
128
5
Anyone can tell me if is correct ? Or propose your own version?

:)
 
  • #8
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728
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.
 
  • Like
Likes StoneTemplePython
  • #9
StoneTemplePython
Science Advisor
Gold Member
1,179
577
my sense is you're close and just a little bit of refinement will get you there...
 
  • #10
128
5
In order to reformulate the problem i'm trying to model this in linear programming

[itex]\sum_{t=y}^{C}x_{t}= a[/itex]
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:
  • #11
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728
In order to reformulate the problem i'm trying to model this in linear programming

[itex]\sum_{t=y}^{C}x_{t}= a[/itex]
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.
 
  • #12
128
5
I tried to find a way to build a matrix with the [itex]a_{i,j}[/itex] shifted based on the start year of i-th project.

I came out with this:

[itex]M_{i,j}=\sum_{y=1}^{j}(a_{i,y})(x_{i,j+1-y})[/itex]

Is this correct ?
 
  • #13
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728
I tried to find a way to build a matrix with the [itex]a_{i,j}[/itex] shifted based on the start year of i-th project.

I came out with this:

[itex]M_{i,j}=\sum_{y=1}^{j}(a_{i,y})(x_{i,j+1-y})[/itex]

Is this correct ?
How can we tell? You do not explain what the matrix ##M## is supposed to represent!
 
  • #14
128
5
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

[itex]\sum_{i=1}^{p}M_{i,j}\leq b_{j}[/itex]
for j=1..Years

assure me that the budget per year is respected.
 
  • #15
128
5

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 [itex]a_{i}[/itex] 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 dont understand what to change of my original formulation, that is :

[tex]max \sum_{i=1}^{n} p_{i}x_{i}[/tex]

[tex] \sum_{i=1}^{n} a_{ij}x_{i}=b_{j} , j=1..T[/tex]

[tex]x_{i}\in \left \{ 0,1 \right \} , i=1..n[/tex]
Months have passed and I could not create the model. Is anyone kind enough to show me a possible solution?
 
  • #16
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728
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}$$
 
Last edited:

Related Threads on Stuck on an Integer Programming problem

  • Last Post
Replies
8
Views
1K
Replies
3
Views
713
  • Last Post
Replies
9
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
8
Views
1K
  • Last Post
Replies
11
Views
1K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
4
Views
512
Replies
2
Views
1K
Top