OR-Notes are a series of introductory notes on topics that fall under the broad heading of the field of operations research (OR). They were originally used by me in an introductory OR course I give at Imperial College. They are now available for use by any students and teachers interested in OR subject to the following conditions.

A full list of the topics available in OR-Notes can be found here.

To illustrate the concept of structure in a mathematical program consider the following LP:

maximise c_{1}x_{1}+ c_{2}x_{2}+ c_{3}x_{3}+ c_{4 }x_{4 }+ c_{5}x_{5}+ c_{6}x_{6}

subject to

x_{1}+x_{2}<= 1

x_{3}+x_{4}<= 1

x_{5}+x_{6}<= 1

x_{i}>= 0 i=1,...,6

where the c_{i}>=0 i=1,...,6 are known constants.

Whilst it is plain that we could solve this LP (via a computer package using simplex or interior point) it is obvious that the constraints of this LP have a special structure - namely

- each variable appears in just one constraint; and
- each constraint involves only two variables.

Using this information it is clear that the optimal solution of this LP can be obtained by inspection (technically in polynomial time) and is given by

x_{1}= 1 if c_{1}>=c_{2}= 0 otherwise

x_{2}= 1-x_{1}

x_{3}= 1 if c_{3}>=c_{4}= 0 otherwise

x_{4}= 1-x_{3}

x_{5}= 1 if c_{5}>=c_{6}= 0 otherwise

x_{6}= 1-x_{5}

with the optimal objective function value being given by

max[c_{1},c_{2}] + max[c_{3},c_{4}] + max[c_{5},c_{6}]

i.e. we have obtained the optimal solution *without* using a complicated
algorithm (and, in computer terms, at considerably less computational cost).

In essence *structured problems* are problems which can be formulated
as LP's/IP's but which, because of the structure of the constraints, can
be solved much more efficiently by algorithms which take advantage of this
structure (as compared with solving them by using the general LP (simplex/interior
point) or IP (tree search) algorithms).

Examples of structured problems considered in this course are: