13
The optimal solution, listed in figure 1, took 24 hours of computing time on an Olivetti M6 460
with a clock speed of 66 MHz. This is of course too long for any practical implementation, and
another procedure for generating good, feasible solution in a reasonable amount of time dad to be
found. A special branching method was used, and will be discussed below. This method was
used to generate the results of the three scenarios, and produced good feasible solutions in about
two minutes on a HP9000. Although the HP9000 is about three times as fast as the Olivetti M6
460, the computation time was brought down to a manageable level. However, the notion of
achieving an absolute optimal solution was abandoned.
The branching method consisted of:
- branching on 0.2
- priority on binary variable mjt
- SOS branching
“Branching on 0.2” means that, when the LP-relaxation solution for a particular binary variable
x is for instance x=0.25, the branch that sets x at 1 will be processed first, because the cut-off
point is 0.2. In general, the LP relaxation solution shows which cut-off point is best used. In this
model, quite a lot of variables had an LP solution of about 0.25.
Setting priority on mjt means the model first decides on the values of these variables, before
proceeding with the optimization. This measure proves very effective in situations where a clear
priority rule exists, like in a transportation model where the mode of transportation (trucks, train,
and the like) and the number of transportation vehicles to be purchased or leased, are to be
decided. In such a case, priority is clearly set on the mode of transportation.
The last measure taken was to let the optimization package perform SOS branching, that is,
branching on constraints. Say, for example, that the following constraint exists:
K
∑xk = 1
k=1
Branching will then be done in two directions, corresponding with two parts of the constraint:
∑k∈Sxk=1
∑ k ∈ S ' Xk = O
This leads to more efficient branching and less branches. The branching method reduced the
computing time significantly. To show how close the feasible solution came to the optimal, we
ran the basic scenario model of the previous chapter, with the above mentioned method. The
program produced a feasible solution in about six minutes with an objective function value of
278,950 dollars. Comparing this to the optimal solution of 277,620 dollars, we may conclude that
the branching heuristic performed very well.
To get an idea about the performance of this method for larger problems, a fifth scenario was
generated using the basic model for a 30 period planning horizon. The model complexity is
illustrated in table 8, the third column relating to the fifth scenario. The relaxed problem (LP)
solution (lower bound) was found in 18 minutes and 11 seconds, the first good solution (less than
double of the lower bound value) being produced in 48 minutes, all computations being
performed on the HP9000.
As can be seen in table 8 the number of variables, but especially the number of constraints,
increases dramatically with the number of time periods. The number of binary variables is a
linear function in i,j and t: f(i,j,t) = j(i+1)(t+1), but the total number of variables and the number
of constraints have a more complicated structure in i,j and t; defined as: