J E Beasley

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.

Structured problems

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: