Second Set of Lecture Notes Templates on Network Models: A Partial Survey of Network Optimization Models
Source:
Lieberman, J. Lasdon, L. Schrage, L., Waren, A. Modeling and Optimization
with GINO, Scientific Press, San Francisco, 1986.
I. Maximum Flow:
Network configuration:
Arc Capacity
(i,j)
cars/minute
(1,2)
10
(1,3)
30
(3,2)
10
(2,4)
30
(3,4)
10
GINO Input:
(LINDO would also work for this example)
MODEL
! Maximum flow example
!
!The objective is to maximize the flow F
MAX = F;
!Subject to what flows into an intersection must
flow out,
! Intersection 1:
F = X12 + X13;
!Intersection 3:
X13 = X32 + X34;
!Intersection 2:
X12 + X32 = X24;
!Intersection 4:
X24 + X34 = F;
!
!And subject to the capacity of each arc:
X12 < 10;
X13 < 30;
X32 < 10;
X24 < 30;
X34 < 10;
END
!
! And subject to the fact that no flow may be
negative
SLB X12 0;
SLB X13 0;
SLB X32 0;
SLB X24 0;
SLB X34 0;
GINO (DOS) Solution:
...
:LOOK ALL
MODEL:
1) MAX= F ;
2) F = X12 + X13 ;
3) X13 = X32 + X34 ;
4) X12 + X32 = X24 ;
5) X24 + X34 = F ;
6) X12 < 10 ;
7) X13 < 30 ;
8) X32 < 10 ;
9) X24 < 30 ;
10) X34 < 10 ;
END
SLB X12 0.000000
SLB X13 0.000000
SLB X32 0.000000
SLB X34 0.000000
SLB X24 0.000000
:go
SOLUTION STATUS: OPTIMAL TO TOLERANCES. DUAL CONDITIONS: SATISFIED.
OBJECTIVE FUNCTION VALUE
1) 30.000000
VARIABLE
VALUE REDUCED COST
F
30.000000 0.000000
X12
10.000000 0.000000
X13
20.000000 0.000000
X32
10.000000 0.000000
X34
10.000000 0.000000
X24
20.000000 0.000000
ROW SLACK OR SURPLUS PRICE
2)
0.000000 1.000000
3) 0.000000
1.000000
4) 0.000000
0.000000
5) 0.000000
0.000000
6) 0.000000
1.000000
7) 10.000000
0.000000
8) 0.000000
1.000000
9) 10.000000
0.000000
10) 0.000000
1.000000
Interpretation of the results:
II. Travel Time vs. Traffic Volume -- Minimizing "Total Delay" for a Given Flow
Let tij = Travel time in arc (i,j)
Arc
tij
(i,j)
(1,2)
5 + 0.1 x12/(1 - x12/10)
(1,2)
x13/(1 - x13/30)
(3,2)
1 + x32/(1 - x32/10)
(2,4)
x24/(1 - x24/30)
(3,4)
5 + 0.1x34/(1 - x3410)
Graphing xij vs tij:
Specify Flow to be 5 cars/minute from nodes 1 to 4.
GINO Input:
...
: LOOK ALL
MODEL:
! Minimize total delay:
MIN = X12*T12 + X13*T13 + X32*T32 + X24*T24 +
X34*T34;
X13 = X32 + X34;
X12 + X32 = X24;
X24+X34 = F;
T12 = 5 + .1 * X12/(1 - X12/10);
T13 = X13 / (1 - X13/30);
T32 = 1 + X32/(1 - X32/10);
T24 = X24 /(1-X24/30);
T34 = 5 + .1*X34/(1-X34/10);
F=5;
END
SLB X12 0
SLB X13 0
SLB X32 0
SLB X24 0
SLB X34 0
GINO Solution:
...
: LOOK ALL
MODEL:
1) MIN= X12 * T12 + X13 * T13 + X32 * T32 + X24
* T24 + X34 * T34 ;
2) X13 = X32 + X34 ;
3) X12 + X32 = X24 ;
4) X24 + X34 = F ;
5) T12 = 5 + .1 * X12 / ( 1 - X12 / 10 ) ;
6) T13 = X13 / ( 1 - X13 / 30 ) ;
7) T32 = 1 + X32 / ( 1 - X32 / 10 ) ;
8) T24 = X24 / ( 1 - X24 / 30 ) ;
9) T34 = 5 + .1 * X34 / ( 1 - X34 / 10 ) ;
10) F = 5 ;
END
SLB X12 0.000000
SLB X13 0.000000
SLB X32 0.000000
SLB X24 0.000000
SLB X34 0.000000
:GO
SOLUTION STATUS: OPTIMAL TO TOLERANCES. DUAL CONDITIONS: SATISFIED.
OBJECTIVE FUNCTION VALUE
1) 40.303030
VARIABLE VALUE REDUCED COST
X12
2.500007 0.000043
T12 5.333335
0.000000
X13 2.499993
0.000000
T13
2.727264 0.000000
X32 0.000000
0.924726
T32 1.000000
0.000000
X24 2.500007
0.000000
T24 2.727281
0.000000
X34 2.499993
0.000000
T34 5.333332
0.000000
F 5.000000
0.000000
ROW SLACK OR SURPLUS
PRICE
2) 0.000000
-5.702461
3) 0.000000
-5.777738
4) 0.000000
-11.480237
5) 0.000000
-2.500007
6) 0.000000
-2.499993
7) 0.000000
0.000000
8) 0.000000
-2.500007
9) 0.000000
-2.499993
10) 0.000000 -11.480237
Interpretation of the Results:
III. Driver-Determined Equilibrium
GINO Input:
MODEL:
! Compute total delay just for reference.
TOTDEL = X12*T12 + X13*T13 + X32*T32 + X24*T24
+ X34*T34;
X13 = X32 + X34;
X12 + X32 = X24;
X24+X34 = F;
T12 = 5 + .1 * X12/(1 - X12/10);
T13 = X13 / (1 - X13/30);
T32 = 1 + X32/(1 - X32/10);
T24 = X24 /(1-X24/30);
T34 = 5 + .1*X34/(1-X34/10);
! Time (1,2,4) = Time (1,3,2,4)
T12 + T24 = T13 + T32 + T24;
! Time (1,2,4) = Time (1,2,3,4)
T12 + T24 = T13 + T34;
F=5;
END
SLB X12 0
SLB X13 0
SLB X32 0
SLB X24 0
SLB X34 0
GINO Solution:
MODEL:
1) TOTDEL = X12 * T12 + X13 * T13
+ X32 * T32 + X24 * T24 + X34 * T34 ;
2) X13 = X32 + X34 ;
3) X12 + X32 = X24 ;
4) X24 + X34 = F ;
5) T12 = 5 + .1 * X12 / ( 1 - X12
/ 10 ) ;
6) T13 = X13 / ( 1 - X13 / 30 )
;
7) T32 = 1 + X32 / ( 1 - X32 / 10
) ;
8) T24 = X24 / ( 1 - X24 / 30 )
;
9) T34 = 5 + .1 * X34 / ( 1 - X34
/ 10 ) ;
10) T12 + T24 = T13 + T32 + T24
;
11) T12 + T24 = T13 + T34 ;
12) F = 5 ;
END
SLB X12 0.000000
SLB X13 0.000000
SLB X32 0.000000
SLB X24 0.000000
SLB X34 0.000000
SOLUTION STATUS: FEASIBLE TO TOLERANCES.
VARIABLE VALUE
TOTDEL 42.643806
X12 2.050761
T12 5.257982
X13 2.949239
T13 3.270784
X32 0.898479
T32 1.987174
X24 2.949239
T24 3.270784
X34
2.050761
T34 5.257982
F 5.000000
ROW SLACK
OR SURPLUS
1) 0.000000
2) 0.000000
3) 0.000000
4) 0.000000
5) 0.000000
6) 0.000000
7) 0.000000
8) 0.000000
9) 0.000000
10) -0.000024
11) 0.000000
12)
0.000000
Interpretation of the Results:
Notice that there is flow on arc (3,2). Also notice that the total delay is slightly higher. Thus, drivers behaving optimally individually do not necessarily produce an optimal overall solution. In fact, the travel time for any driver, 8.528 minutes minutes, is higher than in the previous example (8.060 minutes). Hence, the user-determined equilibrium has the curious feature that if arc (3,2) were deleted, then total delay would actually decrease to 8.060 minutes. This phenomenon is known as Braess’s Paradox in honor of a traffic analyst who noticed that when a certain link was added to the city of Munich’s road system, traffic seemed to get worse.
Preliminaries:
One improtant aspect of project managment is completion time prediction and progress monitoring. Two closely related methodologies for doing this are PERT (Project Evaluatin and Review Technique) and CPM (Critical Path Method). Both methods view a project as a collection of activities, where each activity is described by an activity time, and a set of predecessor activities. A given activity cannot be started until all of its predecessors have finished. The finish time of an activity is its start time plus its activity time.
A second kind of useful information that PERT and CPM generate is the identification of the critical path, that is, the identification of that subset of activities that must be started as early as possible and performed in time no greater than planned if the project is to finish on time. The critical path information essentially "falls out" of the earliest start time calculation.
If in addition one wishes to examine various options for accelerating or "crashing" a project, then calculations are not quite as simple and GINO may be of interest.
House-Building Project Data
Activity Mnemonic
Activity
Normal Predecessor
Time
Cost
of
(Mnemonic)
Dig Basement DIG
3
12
-------
Pour Foundation FOUND
4
10
DIG
Pour Basement Floor
POURB 2
7
FOUND
Install Floor Joists JOISTS
3
8
FOUND
Install Walls
WALLS
5 9
FOUND
Install Rafters RAFTERS
3
10 WALLS,
POURB
Install Flooring
FLOOR 4
11
JOISTS
Fough Interior ROUGH
6
11
FLOOR
Install Roof
ROOF
7
10
RAFTERS
Finish Interior FINISH
5
12 ROUGH,
ROOF
Landscape SCAPE
2
6
POURB,
WALLS
The column labelled Normal Cost is the cost in $1K of performing the activity in the time listed under the Activity Time. The activity times are in days.
Diagram of the building project:
A represents "start digging the basement"; C represents "complete the foundation"; and I represents "complet landscaping and finish interior."
Hence, define the variables A, B, C, .... H, I as the time at which these events occur.
GINO Input:
(LINDO would also work in this case.)
MODEL:
A > 0;! Project Start
B - A > 3;! DIG
C - B > 4;! FOUND
E - C > 2;! POURB
D - C > 3;! JOISTS
E - C > 5;! WALLS
F - D > 4;! FLOORS
G - E > 3;! RAFTERS
H - F > 6;! ROUGH
H - G > 7;! ROOF
I - H > 5;! FINISH
I - E > 2;! SCAPE
MIN = I;
END
GINO Output:
MODEL:
1) A > 0 ;
2) B - A > 3 ;
3) C - B > 4 ;
4) E - C > 2 ;
5) D - C > 3 ;
6) E - C > 5 ;
7) F - D > 4 ;
8) G - E > 3 ;
9) H - F > 6 ;
10) H - G > 7 ;
11) I - H > 5 ;
12) I - E > 2 ;
13) MIN= I ;
END
SOLUTION STATUS: OPTIMAL TO TOLERANCES. DUAL CONDITIONS: SATISFIED.
OBJECTIVE FUNCTION VALUE
13) 27.000000
VARIABLE VALUE REDUCED COST
A 0.000000
0.000000
B 3.000000
0.000000
C 7.000000
0.000000
E 12.000000
0.000000
D 10.000000
0.000000
F 14.000000
0.000000
G 15.000000
0.000000
H 22.000000
0.000000
I 27.000000
0.000000
ROW SLACK
OR SURPLUS PRICE
1)
0.000000 -1.000000
2) 0.000000
-1.000000
3) 0.000000
-1.000000
4) 3.000000
0.000000
5) 0.000000
0.000000
6) 0.000000
-1.000000
7) 0.000000
0.000000
8) 0.000000
-1.000000
9) 2.000000
0.000000
10) 0.000000
-1.000000
11) 0.000000
-1.000000
12) 13.000000
0.000000
Interpretation of the Results:
(Note the ojbective function value equals the CPM)
V. Project Managment -- "Crashing"
Now suppose we can shorten or "crash" an activity by spending more money on the activity.
We shall use one of the simplest forms of such a relationship based on the assumption that the cost of performing an activity is proportional to the speed with which it is done. Equivalently, the cost of an activity is inversely proportional to the actifity of time. The cost relationship for an activity can be written:
(ACTIVITY COST) = K/(ACTIVITY TIME).
Graphically,
One point on the curve is sufficient to determine the value of k. One more variable is needed for each activity to represent the (now varialbe) activity. We shall prefact the activity mnemonic name with a T to denote this time. Now, using the Normal Cost data in the previous table we can, for example write the cost of doing activity DIG as
3 * 12/TDIG = 36/Tdig.
There are now two criteria for judging the success of the project: its completion time and its cost. As is often done, we shall contrain one of them, completion time, and optimize the other, cost.
Requiring the project to be done in no more than 27 days, the complet formulation is:
GINO Input:
MODEL:
!Project management example, including crashing,
for building
! a house
! The completion time requirement:
I - A < 27;
! Precedence Constraints
B - A > TDIG;
C - B > TFOUND;
E - C > TPOURB;
D - C > TJOISTS;
E - C > TWALLS;
F - D > TFLOOR;
G - E > TRAFTERS;
H - F > TROUGH;
H - G > TROOF;
I - H > TFINISH;
I - E > TSCAPE;
MIN = 3*12/TDIG + 4*10/ TFOUND + 2*7/ TPOURB
+ 3*8/TJOISTS + 5*9/TWALLS + 3*10/TRAFTERS + 4*11/TFLOOR
+ 6*11/TROUGH + 7*10/TROOF + 5*12/TFINISH + 2*6/TSCAPE;
END
! The first event can occur no earlier than time
0.
SLB A 0
! Activity times must be positive, hence the following
! "finagle."
SLB TDIG 0.000010
SLB TFOUND 0.000010
SLB TPOURB 0.000010
SLB TJOISTS 0.000010
SLB TWALLS 0.000010
SLB TFLOOR 0.000010
SLB TRAFTERS 0.000010
SLB TROUGH 0.000010
SLB TROOF 0.000010
SLB TFINISH 0.000010
SLB TSCAPE 0.000010
GINO Output:
MODEL:
1) I - A < 27 ;
2) B - A > TDIG ;
3) C - B > TFOUND ;
4) E - C > TPOURB ;
5) D - C > TJOISTS ;
6) E - C > TWALLS ;
7) F - D > TFLOOR ;
8) G - E > TRAFTERS ;
9) H - F > TROUGH ;
10) H - G > TROOF ;
11) I - H > TFINISH ;
12) I - E > TSCAPE ;
13) MIN= 3 * 12 / TDIG + 4 * 10 / TFOUND + 2 *
7 / TPOURB + 3 * 8 /
TJOISTS + 5 * 9 / TWALLS + 3 * 10 / TRAFTERS +
4 * 11 / TFLOOR + 6 *
11 / TROUGH + 7 * 10 / TROOF + 5 * 12 / TFINISH
+ 2 * 6 / TSCAPE ;
END
SLB A 0.000000
SLB TDIG 0.000010
SLB TFOUND 0.000010
SLB TPOURB 0.000010
SLB TJOISTS 0.000010
SLB TWALLS 0.000010
SLB TFLOOR 0.000010
SLB TRAFTERS 0.000010
SLB TROUGH 0.000010
SLB TROOF 0.000010
SLB TFINISH 0.000010
SLB TSCAPE 0.000010
SOLUTION STATUS: OPTIMAL TO TOLERANCES. DUAL CONDITIONS: UNSATISFIED.
OBJECTIVE FUNCTION VALUE
13) 90.549632
VARIABLE VALUE
REDUCED COST
I 27.000000
0.000000
A 0.000000
0.000000
B 3.276574
0.000000
TDIG 3.276574
0.000749
C 6.730184
0.000000
TFOUND 3.453620
0.000376
E 12.384507
0.000000
TPOURB 5.654323
-0.000116
D 10.720083
0.000000
TJOISTS 3.989899
0.001083
TWALLS 5.654323
0.000000
F 16.120414
0.000000
TFLOOR
5.400331 -0.000044
G 16.479489
0.000000
TRAFTERS 4.094982
0.000080
H
22.734538 0.000000
TROUGH 6.614124
0.000000
TROOF 6.255049
0.000000
TFINISH
4.265462 0.000035
TSCAPE 14.615493
0.000000
ROW SLACK
OR SURPLUS PRICE
1) 0.000000
3.353972
2)
0.000000 -3.353972
3) -0.000010
-3.353972
4) 0.000000
-0.437776
5) 0.000000
-1.508687
6)
0.000000 -1.407509
7)
0.000000 -1.508687
8)
0.000000 -1.789108
9)
0.000000 -1.508687
10)
0.000000 -1.789108
11) 0.000000
-3.297795
12)
0.000000 -0.056176
Intreptation of the Results: