In Chapters 2, 4 and 7–9 we considered the evolution of a network towards optimality by, essentially, following the steepest-descent path of a prescribed criterion function, even if sometimes this calculation took a simple and intuitive form. However, one generally thinks of ‘evolution’ as something much less premeditated, in which some simple and plausible response rule induces structural changes in the system, whose effect and whose effective guiding principle (if any) become evident only with time. In the case of Darwinian evolution, the effective guiding principle is that of survival. The degree of sophistication induced by this stark criterion still lies beyond our full comprehension, and is comparable in scale only to the time and tirelessness of trial needed to achieve it.

Interest in these matters is demonstrated by the growing literature on evolving automata, artificial neural networks and the like. However, the Worldwide Web now presents an example, if simple, of spontaneous evolution in a technological context.

Random graphs and the Web

Real-life response rules will in general be local, in that a change is induced in some part of the system in response to stimuli or information manifest in that part. The execution of the rule and the information on which it is based will also show natural variability, i.e. be ‘random’. In the case of networks we are thus considering the generation of a random graph from local rules, and are interested to see whether the network thus generated can be seen as a statistical solution to an implied optimisation problem, and what its character may be.

There is now a large literature on random graphs.

The subject of structural design is of course a long-established and sophisticated one, with an enormous literature. Explicit optimisation was however long regarded as too ambitious a target, whose attempt would entrain risky over-simplifications and the neglect of the wealth of intuition gained by practical experience. However, the advent of powerful computers has made the ambition a realisable one, and revived interest in the class of ideas revealed by Michell.

These developments have now generated a substantial literature in their turn; see Section 8.4 for references. We shall draw particularly, however, on the recent text by Bendsøe and Sigmund (2003). These authors have cast the optimality equations into a form suitable for efficient computation, and have acquired a vast computational experience on a range of practical problems, many of them highly sophisticated, to the point that their programmes virtually deliver production-ready working drawings. In many respects their work may be said to lead theoretical insight rather than follow it.

We refer to the Bendsøe–Sigmund text often enough that it is convenient to use the abbreviation BS. The text by Xie and Stevens (1997) uses somewhat different techniques, and so supplies interesting comparisons; we shall refer to it as XS.

Solid materials

BS consider largely the case of a linear, elastic medium (so that α = β = 2 and the medium follows the same linear Hooke's law in tension and in compression). Terms like ‘work’ and ‘strain energy’ then have their conventional mechanical interpretations.

The treatment of the last chapter ignored the statistical variation in input under a fixed demand pattern. However, one should check that this does not lead one to miss points of real significance, affecting both performance and operation. As far as operation goes, we simply assumed in Chapter 15 that the optimal quotas determined for admission and routing could be achieved somehow. ‘How?’ can only be settled by consideration of a model that is both dynamic and stochastic. A stochastic formulation forces one to develop control rules in terms of current state, which alone can extract best advantage from fortuitous variation while observing constraints.

The adaptability to stochastic state thus achieved can also provide a substantial degree of adaptability to changes in demand. However, as far as the optimisation of design is concerned, the effect of stochastic variation of state for fixed demand will be secondary in comparison with that of the major variations in demand considered in Section 15.3.

A single exchange; Erlang's formula

Before considering the stochastic version of the full net, it is useful to consider the case of a single exchange. Suppose that an exchange offers a single link to some other destination, consisting of G parallel circuits, any one of which can carry a call. Calls arrive in a Poisson stream of rate λ, and will be accepted if there is a circuit free. Once connected, the call will terminate with a probability intensity μ, independently of the state of the exchange. This state is then described by n, the number of busy circuits.

In Sections 11.1 to 11.3 we developed the idea of an associative memory as a device that is intrinsically dynamic, although this aspect was not emphasised in the later sections. If one is to keep the biological archetype in mind then one should also formulate a more realistic dynamic model of the neuron. In a sequence of publications W. Freeman (see the reference list) has developed a model which, while simple, captures the biological essentials with remarkable fidelity. It represents the pulse input to the neuron as driving a linear secondorder differential equation, whose output constitutes the ‘membrane potential’. The law by which this potential discharges and stimulates a pulse output implies, ultimately, a nonlinear activation function of the sigmoid form.

This dynamic view is related to the second point made at the close of Chapter 11: that it is unrealistic to assume that the absolute level of activation or pulse rate can convey any real information in a biological context. These variables are too fuzzy, even when aggregated, and a variable scaling is all the time being applied to keep activity at an optimal level. Neural signals are typically oscillatory, in an irregular kind of way, and it is the pattern of this oscillation which conveys information – by binding the relevant neural units into a joint dynamic state. This is a line of thought which Freeman has developed particularly, and that is combined with the ideas of Chapter 11 in Whittle (1998).

These are important network aspects which appear nowhere else in the text, and whose consequences we shall review in this chapter.

The topic of communication networks is now one of immense range and sophistication, concerned with the management of many competing forms of information traffic between many kinds of agents and devices. In this part we consider only some of the simplest representative cases that have implications for the design question. As ever, the problem is that design cannot be tackled before efficient operating policies have been agreed, and this first stage poses questions enough.

Loss networks are characterised by the fact that a call is accepted only if a clear path through the net is immediately available for it. As observed in Section 13.5, this makes them special in the class of queueing networks, in that they are by fiat both stable and queueless. Their operating rules then amount merely to the formulation of policies for call admission and routing. Under rather stark assumptions this reduces to solution of a simple linear programme. The analysis of Section 5.3 is invoked to show that the features of seminvariant costs, variable load and environmental penalty can all be incorporated. The hierarchical arrangement of exchanges suggested in Chapter 5 certainly gives the easiest analysis of reliability, and perhaps the best protection.

The stochastic upgrading in Chapter 16 of the basic version owes much to F. P. Kelly, although this is work he has now long left behind him. Kelly perceived the stochastic analogues of the shadow prices generated by the linear programme analysis, and their implications for routing and for updating of a network. A deeper contribution was his achievement of efficient self-regulation in the form of minimally interventionist and minimally centralised trunk reservation rules.

By ‘processing’ we mean ‘industrial processing’, often referred to more restrictively as job-shop scheduling. Although this may be computerised, we shall not stray into the profoundly specialised and developed fields of computer processing or computer networks.

We are then concerned with the situation in which items under manufacture undergo a sequence of processing operations before they are completed. The aim is then to so schedule these that congestion at any part of the processing line is avoided, by the optimal allocation of fixed or mobile capacity.

This application does not constitute such a strong example of network optimisation, because the fact that the sequence of operations is prescribed means that the form of the network is both simple and largely preordained. Nevertheless, the application is one that in fact generated the concept of a queueing network, and raises the question of the prioritisation of competing flows.

Even here we need something of a disclaimer. The subject of scheduling is a strongly developed one in its own right, founded on both empirical experience and theoretical investigation, and to step in claiming insight would be the highest presumption. Nevertheless, the subject has itself generated at least two discernable bodies of fundamental theory. One is that which views manufacture as a queueing network, to be optimised in operation by appropriate state-dependent rules, with design optimisation then following. There are difficulties, not least those of local versus central implementation, and the possibly dire effects of misconceived priority rules.

Artificial neural networks (with the recognised abbreviation of ANN) embody a fascinating concept: a stripped-down idealisation of the biological neural network, with the promise of genuine application. The state of the net is described by the activities at its nodes, rather than, as hitherto, by the flows on its arcs. There are such flows, however: the output of a node is a particular nonlinear function (the activation function) of a linear combination of its inputs from other nodes. It is the coefficients of these linear functions (the weights) that parameterise the net. The specimen aim to which we shall largely restrict ourselves is: to choose the weights so that the system output of the network shall approximate as well as possible a prescribed function of system input. Here by ‘system output’ we mean the output from a recognised subset of ‘output nodes’, and by ‘system input’ the environmental input to a recognised subset of ‘input nodes’. However, this design problem is solved, not by a deliberate optimisation algorithm, but by an adaptive procedure that modifies the weights iteratively in such a way as to bring net input and net output into the desired correspondence.

To clarify the biological parallel: the activation function provides a crude version of the operation of a biological neuron; the weightings represent the strengths of interneuronal connections, the axons, and so define the net. The animal neural system is a remarkable processor, converting sensory inputs into what one might term inferences on the environment and then into stimuli for appropriate action.

The seminal works are those of Gittins (1979, 1989), which presented the key insight and unlocked the multi-armed bandit problem, and Klimov (1974, 1978), which developed a frontal attack on the tax problem. Gittins had in fact perceived the essential step to solution by 1968, and described this at the European Meeting of Statisticians in 1972; see Gittins and Jones (1974). By this time Olivier (1972) had independently hit upon much the same approach. A direct dynamic programming proof of the optimality of the Gittins index policy was given in Whittle (1980), and then generalised to the cases of an open process and of the tax problem in Whittle (1981b, 2005).

For present purposes, we shall not follow the historical sequence of steps that suggested the Gittins index, but shall simply give the dynamic programming arguments that confirm optimality of the index policy and evaluate its performance. We consider only the undiscounted case, which shows particular simplifications and covers the needs of the text.

As mentioned in the text, there are at least two levels of aspiration to optimality in the undiscounted case. One is simply to minimise the average cost, and the second is to minimise also the transient cost: the extra cost incurred in passage from a given initial state to the equilibrium regime. As it turns out, the index policy is optimal at both levels.

Bandit processes

Consider a Markov decision process with the same dynamics over states as that supposed for items over nodes in Chapter 14.

In this book, we are going to examine various types of numerical problems and develop techniques for solving them. We will gradually build up the necessary tools and use a number of case studies to:

1. illustrate the process of formulating a problem, by which we mean translating from an intuitive idea of the problem by writing it down mathematically,

2. motivate and develop algorithms to solve problems, that is, descriptions of operations that can be implemented in software to take a problem specification and return a solution, and

3. illustrate how to match the formulation of the problem to the capabilities of available algorithms, involving, in some cases, transformation of the problem from its initial formulation.

We illustrate how to think about and describe problems to make them amenable to solution by optimization software. In brief: formulation of problems to facilitate their solution.

In the five parts of this book, we will consider five general problem classes. The first problem class is the solution of linear systems of equations (Part I). Solving linear systems of equations will turn out to be at the center of much of our subsequent work. For example, our second problem class, solving non-linear systems of equations (Part II), will be solved by an algorithm that requires repeated solution of linear systems of equations.

We will then go on to use these two algorithms as building blocks in algorithms for:

• unconstrained optimization (Part III), which will in turn form part of the algorithms for:

• equality-constrained optimization (Part IV), which will again form part of the algorithms for:

• inequality-constrained optimization (Part V).