Stuck on an Integer Programming problem

In summary, In order to model the scenario of trying to maximize expected profit while respecting a budget constraint, you would need to introduce decision variables x_{ij} to model the start year of the ith problem.
  • #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 don't 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]
 
Physics news on Phys.org
  • #2
You can add shifts si.
 
  • Like
Likes Aleoa
  • #3
mfb said:
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
Aleoa said:

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 don't 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
Ray Vickson said:
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
[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
Anyone can tell me if is correct ? Or propose your own version?

:)
 
  • #8
Aleoa said:
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
my sense is you're close and just a little bit of refinement will get you there...
 
  • #10
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
Aleoa said:
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
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
Aleoa said:
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
Ray Vickson said:
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
Aleoa said:

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 don't 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
Aleoa said:
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:

1. How do I know if my problem is an Integer Programming problem?

If your problem involves variables that can only take on integer values, then it is an Integer Programming problem. This type of problem is commonly used in operations research, where the decision variables represent discrete choices.

2. What are the common techniques used to solve Integer Programming problems?

Some common techniques used to solve Integer Programming problems include branch and bound, cutting-plane methods, and heuristics. These methods involve breaking down the problem into smaller subproblems and using different rules and algorithms to find the optimal solution.

3. How do I formulate my problem into an Integer Programming model?

Formulating an Integer Programming model involves identifying the decision variables, the objective function, and the constraints. The decision variables represent the choices that need to be made, the objective function is what you want to optimize, and the constraints are the limitations or requirements that must be met.

4. What is the difference between Integer Programming and Linear Programming?

The main difference between Integer Programming and Linear Programming is that in Linear Programming, the decision variables can take on any real value, while in Integer Programming, the decision variables can only take on integer values. This makes Integer Programming problems more complex and difficult to solve, but they can model real-world problems more accurately.

5. Can I use Integer Programming to solve my real-world problems?

Yes, Integer Programming can be used to solve a wide range of real-world problems, such as resource allocation, production planning, and scheduling. However, it is important to note that formulating the problem into an Integer Programming model and finding the optimal solution can be challenging and time-consuming.

Suggested for: Stuck on an Integer Programming problem

Replies
13
Views
625
Replies
13
Views
1K
Replies
13
Views
2K
Replies
9
Views
1K
Replies
4
Views
569
Replies
2
Views
993
Back
Top