by Peter Lohmander
www.Lohmander.com
Short abstract (A longer abstract is found below)
Typical decision problems in companies in the forest sector are sequential.
Important information, which was not available when the first
decisions in the chain were taken, becomes available before the final decisions have to be made.
The optimal decisions can usually not be found via deterministic multi period optimizations methods.
This paper focuses on a linear programming approach to the true adaptive, large dimension, multi period problem with sequential information.
You can handle such problems in case "dynamic information constraints" are introduced. An application to a forest company sample problem is included.
The objective is to minimize the expected present value of the total cost (including costs of harvesting, transport and stocks)
during one year. The developments of snow, rain and road problems are not known in advance.
Abstract
Typical decision problems in companies in the forest sector and in several other sectors of the economy are sequential.
A series of decisions are taken over time. Important information, which was not available (or perfectly predictable) when the first
decisions in the chain were taken, becomes available before the final decisions have to be taken.
In this situation, the optimal first (and later!) decisions in the chain can usually not be found via deterministic multi period optimizations methods.
The standard approach to adaptive dynamic optimization is stochastic dynamic programming. That approach however makes it computationally impossible
to handle a large state space, typical in logistics problems.
This paper focuses on a linear programming approach to the true adaptive multi period problem with sequential information.
It has been found that you really can handle such problems, typical to many companies in the forest sector and many other sectors, in case
"dynamic information constraints" are introduced in the linear programming constraint set.
An application to a sample forest company problem is included in the paper.
The objective is to minimize the expected present value of the total cost (including costs of harvesting, transport and stocks)
during one year. The developments of snow, rain and road problems are not known in advance.
The information concerning these matters is sequentially revealed, exactly as in the real world.
The forest harvesting volume constraints, the sequentially revealed road capacity constraints and the stock level constraints however have
to be met, irrespective of what happens. The wood deliveries necessary for full industrial production in different periods have to reach the forest industry mills.
In a more complete version of this model, one could maximize the expected present value of all activities in the firm, making it
possible to stop industrial production in some cases. Of course, one could easily include harvester and forwarder capacity constraints.
Other developments would be to introduce quadratic harvesting and transport cost functions with increasing marginal costs in each period.
The model would then still converge to the global optimum in a finite number of iterations and the number of dimensions could be very large,
thanks to the efficient quadratic programming algorithms.
Time scale = 1 year
Random weather: Click
here!
Sequential information: Click
here!
Sample problem (Norra Norrland):
! AdaptTP6.lng;
! "Adaptive
forest sector harvesting, logistics and management".
The objective is to minimize
the expected present value of the
The developments of snow, rain
and road problems are not known in advance. The information concerning
these matters is sequentially revealed, exactly as in the real world.
The forest harvesting volume constraints, the sequentially
revealed
The wood deliveries necessary
for full industrial production in different periods have to
reach the forest industry mills.
In a more complete version of
this model, one could maximize the expected present value of
all activities in the firm, making it
Of course, one could easily include
harvester and forwarder capacity constraints.
Other developments would be to
introduce quadratic harvesting and
The model would then still converge
to the global optimum in a finite number of iterations and the number of
dimensions could be very large, thanks to the efficient quadratic programming
algorithms.
www.Lohmander.com
;
MODEL:
! These
parameters roughly represent the region "Norra Norrland", the two counties
in the far north in Sweden.
The units are "1000 cubic metres".;
htot = 12010;
min = TCOST;
TCOST = TCh + TCSI + TCSL + TCLI
+ TCSTO;
TCh = 70*h1
TCSI = 50*TSI1
+ 0.98*(1/3)*
+ 0.96*(1/9)*
TCSL = 40*TSL1
+ 0.98*(1/3)*
+ 0.96*(1/9)*
TCLI = 30*TLI1
TCSTO = 40*(Lsec + L1ut1)/2
L1ut1 = Lsec + TSL1
- TLI1;
! In period 1, the state is 1
and we harvest h1.
In period 2, the state will be 1, 2 or 3
In period 3, we come to a state which is not yet known,
namely 1, 2 or 3.
Depending on the (at that point in time known) state
path,
! Harvest volume constraints;
h1 + h11 + h111 < htot;
h1 + h12 + h121 < htot;
h1 + h13 + h131 < htot;
! The roundwood volumes sent
from the forest to the mill and/or to the stock can not exceed the harvest.
This must be true for each period and scenario.;
[hcon1] TSI1 + TSL1 < h1;
[hcon11] TSI11 + TSL11 < h11;
[hcon111] TSI111 + TSL111 <
h111;
[hcon121] TSI121 + TSL121 <
h121;
[hcon131] TSI131 + TSL131 <
h131;
! The roundwood volume sent from
the stock to the mill can not exceed the final volume in that stock in
the earlier period. This must be true for each period and scenario.
(These constraints are not necessary. Other constraints
in this model make sure that these constraints are not violated. These
constraints are included just to make it possible for the user to investigate
the option to take extra volumes from the security stock in critical situations.);
[Lcon1] TLI1 < Lsec;
[Lcon11] TLI11 < Lsec + TSL1
- TLI1;
[Lcon111] TLI111 < Lsec +
TSL1 + TSL11 - TLI1 - TLI11;
[Lcon121] TLI121 < Lsec +
TSL1 + TSL12 - TLI1 - TLI12;
[Lcon131] TLI131 < Lsec +
TSL1 + TSL13 - TLI1 - TLI13;
! The roundwood volumes transported
on the roads are, if some road quality scenarios occur, constrained.;
[Rcon1] TSI1 + TSL1 < 8000;
[Rcon11] TSI11 + TSL11 < 4000;
[Rcon111] TSI111 + TSL111 <
10000;
[Rcon121] TSI121 + TSL121 <
9000;
[Rcon131] TSI131 + TSL131 <
8000;
! The roundwood volumes going
to the mill must be correct in every period, irrespective of the scenario.;
[D1d] TSI1 + TLI1
= D1;
[D11d] TSI11 + TLI11 =
D2;
[D111d] TSI111 + TLI111 = D3;
[D121d] TSI121 + TLI121 = D3;
[D131d] TSI131 + TLI131 = D3;
! The roundwood volumes in the stock must be positive
in every period, irrespective of the scenario.;
[L1]Lsec + TSL1 - TLI1 > 0;
[L11]Lsec + TSL1 + TSL11 - TLI1 - TLI11 > 0;
[L111]Lsec + TSL1 + TSL11 + TSL111 - TLI1 - TLI11 -
TLI111 = Lsec;
[L121]Lsec + TSL1 + TSL12 + TSL121 - TLI1 - TLI12 -
TLI121 = Lsec;
[L131]Lsec + TSL1 + TSL13 + TSL131 - TLI1 - TLI13 -
TLI131 = Lsec;
end
Results in graphs: Click
here!
Rows= 85 Vars=
62 No. integer vars= 0 ( all are linear)
Global optimal solution found at step:
69
Variable Value
Reduced Cost
HTOT 12010.00
0.0000000
TCOST 1850580.
0.0000000
H1 6500.000
0.0000000
H11 0.0000000
0.0000000
H111 5500.000
0.0000000
H121 5500.000
0.0000000
H131 5000.000
0.0000000
TSI1 3000.000
0.0000000
TSI11 0.0000000
16.09333
TSI111 5500.000
0.0000000
TSI121 5500.000
0.0000000
TSI131 5000.000
0.0000000
TSL1 3500.000
0.0000000
TSL11 0.0000000
22.62667
TSL111 0.0000000
2.133333
TSL121 0.0000000
2.133333
TSL131 0.0000000
2.133333
TLI1 0.0000000
20.00000
TLI11 2000.000
0.0000000
TLI111 1500.000
0.0000000
TLI121 1500.000
0.0000000
TLI131 2000.000
0.0000000
L1UT1 4500.000
0.0000000
Row Slack or Surplus Dual
Price
HCON1 0.0000000
70.00000
LCON1 1000.000
0.0000000
RCON1 1500.000
0.0000000
D1D 0.0000000
-120.0000
L1 4500.000
0.0000000
Conclusions:
A. It is possible to optimize the relevant regional
forest sector problem:
Time scale = 1 year
B. The true sequential structure of information and
decisions has been included in the analysis.
C. The demonstrated sample model shows how the sequential
information and optimal adaptive decisions can be consistently managed
in the optimization procedure.
D. Complete regional analyses with high resolution
data can and should be made.
E. In order to reach the full potential of the approach,
parallell algorithms and/or other super computer approaches should be integrated.
F. Cooperation including the the Kvarken region, Holmen
and Mitthögskolan is proposed.
G. Research grants and efficient program administration
are needed.
Spatial scale = Region
Harvesting, roundwood transport,
stocks, forest industry mills, Infrastructure,
Random
weather conditions
! Peter Lohmander Version 2002-02-12;
total cost (including costs
of harvesting, transport and stocks)
during one year.
road capacity constraints and the stock level constraints
however have
to be met, irrespective of what happens.
possible to stop industrial
production in some cases.
transport cost functions with
increasing marginal costs in each period.
D1 = 3000;
D2 = 2000;
D3 = 7000;
Lsec = 1000;
+ 70*0.98*(1/3)*
(h11
+ h12 + h13)
+ 70*0.96*(1/9)*
( h111
+ h112 + h113
+ h121
+ h122 + h123
+ h131
+ h132 + h133);
(50*TSI11 + 52*TSI12 + 54*TSI13)
( 50*TSI111 + 52*TSI112 + 54*TSI113
+ 50*TSI121 + 52*TSI122 + 55*TSI123
+ 51*TSI131 + 53*TSI132 + 56*TSI133);
( 40*TSL11+42*TSL12+44*TSL13)
( 40*TSL111 + 42*TSL112 + 44*TSL113
+ 40*TSL121 + 42*TSL122 + 45*TSL123
+ 41*TSL131 + 43*TSL132 + 46*TSL133);
+ 30*0.98*(1/3)*
(TLI11 + TLI12 + TLI13)
+ 30*0.96*(1/9)*
( TLI111 + TLI112 + TLI113
+ TLI121 + TLI122 + TLI123
+ TLI131 + TLI132 + TLI133);
+ 40*0.98*(1/3)*(
(L1ut1 + L2ut11)/2
+ (L1ut1 + L2ut12)/2
+ (L1ut1 + L2ut13)/2)
+ 60*0.96*(1/3)*(
(L2ut11 + Lsec)/2
+ (L2ut12 + Lsec)/2
+ (L2ut13 + Lsec)/2);
L2ut11 = L1ut1 + TSL11 - TLI11;
L2ut12 = L1ut1 + TSL12 - TLI12;
L2ut13 = L1ut1 + TSL13 - TLI13;
(we do not know that state in advance) and we harvest
h11, h12 or h13 depending on which state we come to.
111, 112, 113, 121, 122, 123, 131, 132 or 133, we
harvest hijk
(where i is the state in the first period, j in the
second and k in the
third period.);
h1 + h11 + h112 < htot;
h1 + h11 + h113 < htot;
h1 + h12 + h122 < htot;
h1 + h12 + h123 < htot;
h1 + h13 + h132 < htot;
h1 + h13 + h133 < htot;
[hcon12] TSI12 + TSL12 <
h12;
[hcon13] TSI13 + TSL13 <
h13;
[hcon112] TSI112 + TSL112 <
h112;
[hcon113] TSI113 + TSL113 <
h113;
[hcon122] TSI122 + TSL122 <
h122;
[hcon123] TSI123 + TSL123 <
h123;
[hcon132] TSI132 + TSL132 <
h132;
[hcon133] TSI133 + TSL133 <
h133;
[Lcon12] TLI12 < Lsec + TSL1
- TLI1;
[Lcon13] TLI13 < Lsec + TSL1
- TLI1;
[Lcon112] TLI112 < Lsec +
TSL1 + TSL11 - TLI1 - TLI11;
[Lcon113] TLI113 < Lsec +
TSL1 + TSL11 - TLI1 - TLI11;
[Lcon122] TLI122 < Lsec +
TSL1 + TSL12 - TLI1 - TLI12;
[Lcon123] TLI123 < Lsec +
TSL1 + TSL12 - TLI1 - TLI12;
[Lcon132] TLI132 < Lsec +
TSL1 + TSL13 - TLI1 - TLI13;
[Lcon133] TLI133 < Lsec +
TSL1 + TSL13 - TLI1 - TLI13;
[Rcon12] TSI12 + TSL12 <
1500;
[Rcon13] TSI13 + TSL13 <
500;
[Rcon112] TSI112 + TSL112 <
9000;
[Rcon113] TSI113 + TSL113 <
7000;
[Rcon122] TSI122 + TSL122 <
8000;
[Rcon123] TSI123 + TSL123 <
6000;
[Rcon132] TSI132 + TSL132 <
7000;
[Rcon133] TSI133 + TSL133 <
5000;
[D12d] TSI12 + TLI12 =
D2;
[D13d] TSI13 + TLI13 =
D2;
[D112d] TSI112 + TLI112 = D3;
[D113d] TSI113 + TLI113 = D3;
[D122d] TSI122 + TLI122 = D3;
[D123d] TSI123 + TLI123 = D3;
[D132d] TSI132 + TLI132 = D3;
[D133d] TSI133 + TLI133 = D3;
[L12]Lsec + TSL1 + TSL12 - TLI1 - TLI12 > 0;
[L13]Lsec + TSL1 + TSL13 - TLI1 - TLI13 > 0;
[L112]Lsec + TSL1 + TSL11 + TSL112 - TLI1 - TLI11
- TLI112 = Lsec;
[L113]Lsec + TSL1 + TSL11 + TSL113 - TLI1 - TLI11
- TLI113 = Lsec;
[L122]Lsec + TSL1 + TSL12 + TSL122 - TLI1 - TLI12
- TLI122 = Lsec;
[L123]Lsec + TSL1 + TSL12 + TSL123 - TLI1 - TLI12
- TLI123 = Lsec;
[L132]Lsec + TSL1 + TSL13 + TSL132 - TLI1 - TLI13
- TLI132 = Lsec;
[L133]Lsec + TSL1 + TSL13 + TSL133 - TLI1 - TLI13
- TLI133 = Lsec;
Nonzeros= 378 Constraint nonz=
323( 267 are +- 1) Density=0.071
Smallest and largest elements in abs value=
1.00000 48800.0
No. < : 48 No. =: 32 No. > :
4, Obj=MIN, GUBs <= 30
Single cols= 0
Objective value:
1850580.
D1 3000.000
0.0000000
D2 2000.000
0.0000000
D3 7000.000
0.0000000
LSEC 1000.000
0.0000000
TCH 824833.3
0.0000000
TCSI 427780.0
0.0000000
TCSL 140000.0
0.0000000
TCLI 101900.0
0.0000000
TCSTO 356066.7
0.0000000
H12 0.0000000
0.0000000
H13 500.0000
0.0000000
H112 5500.000
0.0000000
H113 5500.000
0.0000000
H122 5500.000
0.0000000
H123 5500.000
0.0000000
H132 5000.000
0.0000000
H133 5000.000
0.0000000
TSI12 0.0000000
16.64000
TSI13 500.0000
0.0000000
TSI112 5500.000
0.0000000
TSI113 5500.000
0.0000000
TSI122 5500.000
0.0000000
TSI123 5500.000
0.0000000
TSI132 5000.000
0.0000000
TSI133 5000.000
0.0000000
TSL12 0.0000000
23.17333
TSL13 0.0000000
6.533333
TSL112 0.0000000
2.133333
TSL113 0.0000000
2.133333
TSL122 0.0000000
2.133333
TSL123 0.0000000
2.133333
TSL132 0.0000000
2.133333
TSL133 0.0000000
2.133336
TLI12 2000.000
0.0000000
TLI13 1500.000
0.0000000
TLI112 1500.000
0.0000000
TLI113 1500.000
0.0000000
TLI122 1500.000
0.0000000
TLI123 1500.000
0.0000000
TLI132 2000.000
0.0000000
TLI133 2000.000
0.0000000
L2UT11 2500.000
0.0000000
L2UT12 2500.000
0.0000000
L2UT13 3000.000
0.0000000
HCON11 0.0000000
22.86667
HCON12 0.0000000
22.86667
HCON13 0.0000000
22.86667
HCON111 0.0000000
7.466667
HCON112 0.0000000
7.466667
HCON113 0.0000000
7.466667
HCON121 0.0000000
7.466667
HCON122 0.0000000
7.466667
HCON123 0.0000000
7.466667
HCON131 0.0000000
7.466667
HCON132 0.0000000
7.466667
HCON133 0.0000000
7.466667
LCON11 2500.000
0.0000000
LCON12 2500.000
0.0000000
LCON13 3000.000
0.0000000
LCON111 1000.000
0.0000000
LCON112 1000.000
0.0000000
LCON113 1000.000
0.0000000
LCON121 1000.000
0.0000000
LCON122 1000.000
0.0000000
LCON123 1000.000
0.0000000
LCON131 1000.000
0.0000000
LCON132 1000.000
0.0000000
LCON133 1000.000
0.0000000
RCON11 4000.000
0.0000000
RCON12 1500.000
0.0000000
RCON13 0.0000000
92.17333
RCON111 4500.000
0.0000000
RCON112 3500.000
0.0000000
RCON113 1500.000
0.0000000
RCON121 3500.000
0.0000000
RCON122 2500.000
0.0000000
RCON123 500.0000
0.0000000
RCON131 3000.000
0.0000000
RCON132 2000.000
0.0000000
RCON133 0.0000000
109.1467
D11D 0.0000000
-23.10667
D12D 0.0000000
-23.21333
D13D 0.0000000
-132.6800
D111D 0.0000000
-12.80000
D112D 0.0000000
-13.01333
D113D 0.0000000
-13.22667
D121D 0.0000000
-12.80000
D122D 0.0000000
-13.01333
D123D 0.0000000
-13.33333
D131D 0.0000000
-12.90667
D132D 0.0000000
-13.12000
D133D 0.0000000
-122.5867
L11 2500.000
0.0000000
L12 2500.000
0.0000000
L13 3000.000
0.0000000
L111 0.0000000
-9.600000
L112 0.0000000
-9.813334
L113 0.0000000
-10.02667
L121 0.0000000
-9.600000
L122 0.0000000
-9.813334
L123 0.0000000
-10.13333
L131 0.0000000
-9.706667
L132 0.0000000
-9.920000
L133 0.0000000
-119.3867
Spatial scale = Region
Harvesting, roundwood transport,
stocks, forest industry mills, Infrastructure,
Random
weather conditions