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 c1x1 + c2x2 + c3x3 + c4 x 4 + c5x5 + c6x6
subject to
x1+x2 <= 1
x3+x4 <= 1
x5+x6 <= 1
xi >= 0 i=1,...,6
where the ci>=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
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
x1 = 1 if c1>=c2 = 0 otherwise
x2 = 1-x1
x3 = 1 if c3>=c4 = 0 otherwise
x4 = 1-x3
x5 = 1 if c5>=c6 = 0 otherwise
x6 = 1-x5
with the optimal objective function value being given by
max[c1,c2] + max[c3,c4] + max[c5,c6]
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: