Tree Harvesting Linear Programming Problem

[Titansguy2121]

The State of Virginia is one of the largest produces of wood furniture in the United States, with the furniture industry accounting for 50% of value added to wood materials. Over the past 40 years the inventory volume of wood in Virginia’s forests has increased by 81%. Today, 15.4 million acres, which is well over half of the state, are covered in forest. Private owners hold 77% of this land. When making decisions about which trees to harvest, forestry professionals consider many factors and must follow numerous laws and regulations.
The figure below depicts a tract of forested land that has been sectioned off into 16 harvestable areas, indicated by dashed lines. Area E provides the only access to the forest via a paved road, so any timber cut ultimately must be transported out of the forest through Area E. Currently, there are no roads through this forest. So to harvest the timber, forest roads must be built. The allowable routes for these roads are also shown in the figure below. They are determined largely by the geography of the land and by the location of streams and wildlife habitat.
Not all areas of the forest have to be harvested. However, to harvest any area, a forest road must be built to that area. The cost of building each section of forest road (in $1000s) is indicated in the figure. Also, note that road connecting G->K or K->G costs the same, $12,000. Finally, the value of the harvestable timber in each area is estimated as follows:

Harvested Value (in $ 1000s)
Area A B C D E F G H I J K L M N O P
Value $13 $7 $17 $19 $8 $13 $17 $18 $13 $13 $10 $20 $8 $16 $13 $9



The diagram is listed below. I really need help on formulating this in LINDO

[Guest]

Presumably you want to maximize your profits. This is an integer programming problem as you have binary variables (variables that can either be 0 or 1) you want to determine like whether to build a road or not.

I would choose to have a binary variable for whether each road is built or not, and a binary variable for whether each area is reachable or not. This makes the objective function nice and linear. The constraints are given by the fact that whether an area is reachable or not depends on whether it's neighbouring areas are reachable and whether there is a road from such a neighbour.

As an example let:
[tex]v_G[/tex] = area G is reachable
[tex]v_F[/tex] = area F is reachable
[tex]v_K[/tex] = area K is reachable
[tex]r_{FG}[/tex] = road from F to G is built
[tex]r_{KG}[/tex] = road from K to G is built
be binary variables, then [tex]v_G[/tex] is clearly constrained by
[tex]v_G[/tex] = ([tex]v_F[/tex] AND [tex]r_{FG}[/tex]) OR ([tex]v_K[/tex] AND [tex]r_{KG}[/tex])
where "OR" and "AND" are binary operators. Unfortunately this statement isn't linear, so we need to fix it.

We can replace "AND" with multiplications e.g.
[tex]x[/tex] AND [tex]y[/tex] AND [tex]z[/tex] = [tex]xyz[/tex]
We can replace "OR" with multiplications and additions e.g.
[tex]x[/tex] OR [tex]y[/tex] OR [tex]z[/tex] = [tex]1-(1-x)(1-y)(1-z) = x+y+z-xy-xz-yz+xyz[/tex]
we can replace a product of variables with an auxiliary binary variable, e.g. the set of linear constraints for the binary variable [tex]a[/tex]
[tex]a \leq x[/tex]
[tex]a \leq y[/tex]
[tex]a \leq z[/tex]
[tex]a \geq x+y+z-2[/tex]
are equivalent to saying [tex]a=xyz[/tex].

Using these tricks you can convert the constraints into proper linear constraints.

Hope this helped,

R. Baber.

[Guest]

Sorry, I should have also added that you should add constraints that say that there are no circular paths, e.g.
[tex]r_{JK}[/tex] AND [tex]r_{KO}[/tex] AND [tex]r_{ON}[/tex] AND [tex]r_{NJ}[/tex] = 0.

R. Baber.

[Guest]

Apologies again, that still doesn't get rid of the problem of an isolated area thinking it is connected to region E (for example suppose only road AB is built then [tex]v_A=v_B=1[/tex] satisfies the constraints but is not what we intended).

What you need is two variables per road, e.g. [tex]r_{AB}[/tex] and [tex]r_{BA}[/tex], where
[tex]r_{AB}[/tex] = Timber in region A can get out by going through B,
[tex]r_{BA}[/tex] = Timber in region B can get out by going through A,
and an extra constraint that says [tex]r_{AB}[/tex] AND [tex]r_{BA}[/tex] = 0 (the route timber takes to get out never goes back on itself). You still need constraints that forbid cycles as well.

R. Baber.

[Guest]

I have the same problem in a linear programming class I am taking. I am having a hard time determining the OBJ Function. I understand the networking aspect moving grid to grid maximizing profit of harvesting each grid while keeping road cost at a minimum.

I get the constraints to keep from building the same road twice
ex) KJ +JK <=1
KG-JK-KL-FG<=0

I am going with combining cost & profit to approach this problem; would the OBJ Func. be where I combine this?
MAX 4BA-2BC....

[Guest]

The objective function would be something like:
Maximize [tex]13v_A -9 r_{AB} -9 r_{BA}[/tex]... etc.
where 13 is the money made from harvesting [tex]A[/tex] and 9 is the cost of building a road between [tex]A[/tex] and [tex]B[/tex].

R. Baber.

[Guest]

I think you are using a different program from Lindo. I need assistance with formulating it in Lindo. I'm trying to translate it but it is kind of difficult. Thanks for the help though it's really appreciated!

[Guest]

I have the same problem in a linear programming class I am taking. I am having a hard time determining the OBJ Function. I understand the networking aspect moving grid to grid maximizing profit of harvesting each grid while keeping road cost at a minimum.

I get the constraints to keep from building the same road twice
ex) KJ +JK <=1
KG-JK-KL-FG<=0

I am going with combining cost & profit to approach this problem; would the OBJ Func. be where I combine this?
MAX 4BA-2BC....

I thought the objective function would look something like this. MAX 4BA + 2BC + 7FB + 8HD - 2EF + 4FG + 6GH + 0EI + 1IJ - 3JK + 10KL + 0IM + 0JN + 5NO + 0KO + 0LP

but I could be totally wrong

[Guest]

I think you are using a different program from Lindo. I need assistance with formulating it in Lindo. I'm trying to translate it but it is kind of difficult. Thanks for the help though it's really appreciated!

I'm not actually using any program. From my understanding of LINDO it can accept anything that looks like a linear program (e.g. expressions that look like [tex]4x+y+6z \leq 2[/tex] but not things like [tex]xy=1[/tex] as [tex]xy[/tex] is a non-linear term). It also allows constraints on the types of variables, like [tex]x[/tex] must be 0 or 1, which I think LINDO specifies with the "INT" keyword. Problems of this form are more generally known as integer programming problems and there are well known ways of converting expressions such as [tex]x[/tex] AND [tex]y[/tex]=0 (which is a more natural way of phrasing constraints in the problem you're trying to solve) into linear constraints which integer programming solvers like LINDO prefer. All I was trying to do was point out how such conversions work, unfortunately you still have to do a lot of the work yourself, as LINDO won't do this conversion for you (and neither will I ). Good luck with translating the problem,

R. Baber.

[Guest]

I thought the objective function would look something like this. MAX 4BA + 2BC + 7FB + 8HD - 2EF + 4FG + 6GH + 0EI + 1IJ - 3JK + 10KL + 0IM + 0JN + 5NO + 0KO + 0LP

but I could be totally wrong

You are combining the road cost with the harvesting profit. This is fine for roads like H to D as the only point of building such a road would be to harvest D. However, what about road G to K was the road built to harvest G or to harvest K, when you write the coefficient of GK in your objective function what should you put? Both scenarios are possible. I get around this by having a separate variable for whether an area is harvested.

R. Baber.

[Guest]

MAX 8E-2EF+2BC+4FG+8HD+0EI-3JK-2GK+10KL+0LP+0IM+0JN+5NO-3OK-3NJ+0KO+4BA-7FB-5IE+0GF+8ON+5KG+0KJ-7FE+6GH+1JI
SUBJECT TO
2) BA-FB<=0
3) BC-FB<=0
4) HD-GH<=0
5) GH-GK-FG<=0
6) FG-EF-KG<=0
7) EF-E-EI<=0
IM-EI-IJ<=0
9) KG-JK-KL-FG<=0
10) LP-KL<=0
11) OK-JK-KL-NO<=0
12) JN-IJ-JK<=0
13) NO-JN-LK<=0
14) ON-KO-JN<=0
15) EI+IE<=1
16) FG+GF<=1
17) JI+IJ<=1
18) OK+KO<=1
19) JN+NJ<=1
20) ON+NO<=1
21) GK+KG<=1
22) JK+KJ<=1
23) GH+HG<=1
24) E<=1
25) GK-FG<=0
26) JI-KJ-EI<=0
27) KL+LK<=1
28) EF-EI<=0
29) BF+FB<=1
END



This keeps giving me an optimal solution of 50 but the answer is 53. And all my roads don't connect. I'm missing something.

[Guest]

Sorry the answer is 43

[Guest]

I didn't want to do this, but here is an integer program that works.

Maximize 8-2AB+4BA+2BC-8CB-1BF-7FB+8HD+7DH-2EF-7FE+4FG+0GF+6GH+5HG+0EI-5IE+5KG-2GK+1IJ+1JI-3JK+0KJ+10KL+0LK+5MI+0IM-3NJ+0JN-3OK+0KO+0LP+11PL+5NO+8ON

Such that:

There are no loops:
AB+BA<=1
BC+CB<=1
BF+FB<=1
HD+DH<=1
EF+FE<=1
FG+GF<=1
GH+HG<=1
EI+IE<=1
KG+GK<=1
IJ+JI<=1
JK+KJ<=1
KL+LK<=1
MI+IM<=1
NJ+JN<=1
OK+KO<=1
LP+PL<=1
NO+ON<=1
EF+FG+GK+KJ+JI+IE<=5
EI+IJ+JK+KG+GF+FE<=5
JK+KO+ON+NJ<=3
JN+NO+OK+KJ<=3
EF+FG+GK+KO+ON+NJ+JI+IE<=7
EI+IJ+JN+NO+OK+KG+GF+FE<=7

The roads are connected:
AB<=0
BA<=FB+CB
BC<=AB+FB
CB<=0
BF<=AB+CB
FB<=EF+GF
HD<=GH
DH<=0
EF<=1
FE<=BF+GF
FG<=EF+BF
GF<=HG+KG
GH<=FG+KG
HG<=DH
EI<=1
IE<=MI+JI
KG<=LK+OK+JK
GK<=HG+FG
IJ<=EI+MI
JI<=KJ+NJ
JK<=IJ+NJ
KJ<=GK+LK+OK
KL<=GK+JK+OK
LK<=PL
MI<=0
IM<=EI+JI
NJ<=ON
JN<=IJ+KJ
OK<=NO
KO<=JK+GK+LK
LP<=KL
PL<=0
NO<=JN
ON<=KO

There aren't two routes to the same area:
BA<=1
AB+FB+CB<=1
BC<=1
HD<=1
FE+IE<=0
EF+BF+GF<=1
FG+KG+HG<=1
GH+DH<=1
EI+JI+MI<=1
IJ+NJ+KJ<=1
JK+GK+LK+OK<=1
KL+PL<=1
IM<=1
JN+ON<=1
NO+KO<=1
LP<=1

All variables are binary.


The optimal value for the objective function is 43, there are 8 solutions given by building roads:
HD, GH, EI, KG, IJ, JK, KL, KO, ON
and optionally building (any subset of)
GF, IM, LP.

Hope this helped,

R. Baber.