# OR-Notes

## 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

• 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

```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: