Search

This paper concerns an algorithm, proposed by C. C. Gotlieb (4) and modified by J. Csima (1;2), for a recent combinatorial problem whose application includes the construction of school time-tables. Theoretically, the problem is related to systems of distinct subset representatives, the construction of Latin arrays, the colouring of graphs, and flows in networks (1;2;3). I t was conjectured by Gotlieb and Csima that if solutions to a given time-table problem existed, i.e. if time-tables incorporating certain pre-assigned meetings existed, their algorithm would find one.

The requirement for methods of optimization arises from the mathematical complexity necessary to describe the theory of systems, processes, equipment, and devices which occur in practice. Even quite simple systems must sometimes be represented by theory which may contain approximations, by parameters which change with time, or by parameters that vary in a random manner. For many reasons the theory is imperfect, yet it must be used to predict the optimum operating conditions of a system such that some performance criterion is satisfied. At best such theory can predict only that the system is near to the desired optimum. Optimization methods are then used to explore the local region of operation and predict the way that the system parameters should be adjusted to bring the system to optimum.

Some of the problems encountered in the minimization of functions of n variables were introduced in Chapter 1. One additional problem, best illustrated by an example, is the enormity of hyperspace. Consider a 10 dimensional unit hypercube in which a search has determined that the volume from the origin to the point ½ in each dimension does not contain the minimum. The volume of the ½ unit cube eliminated from the search is equal to (½)10 ≈ 1/1000. The portion of the unit hypercube which remains is therefore 99.9% of the whole. Any form of complete search is clearly out of the question and attention must be given to the local area of a first estimate to the solution. All methods can therefore guarantee only to find the local minimum.

The problem considered in this chapter is that of minimizing the value $$ {\text{minimize}}\,E = f(x). $$