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.

So far we have avoided the problem of defining exactly what OR is. In order to get a clearer idea of what OR is we shall actually do some by considering the specific problem below and then highlight some general lessons and concepts from this specific example.

The Two Mines Company own two different mines that produce an ore which, after being crushed, is graded into three classes: high, medium and low-grade. The company has contracted to provide a smelting plant with 12 tons of high-grade, 8 tons of medium-grade and 24 tons of low-grade ore per week. The two mines have different operating characteristics as detailed below.

Mine Cost per day (£'000) Production (tons/day) High Medium Low X 180 6 3 4 Y 160 1 1 6

How many days per week should each mine be operated to fulfil the smelting plant contract?

*Note*: this is clearly a very simple (even simplistic) example
but, as with many things, we have to start at a simple level in order to
progress to a more complicated level.

To explore the Two Mines problem further we might simply guess (i.e. use our judgement) how many days per week to work and see how they turn out.

- work one day a week on X, one day a week on Y

This does not seem like a good guess as it results in only 7 tonnes
a week of high-grade, insufficient to meet the contract requirement for
12 tonnes of high-grade a week. We say that such a solution is *infeasible*.

- work 4 days a week on X, 3 days a week on Y

This seems like a better guess as it results in sufficient ore to meet
the contract. We say that such a solution is *feasible*. However it
is quite expensive (costly).

Rather than continue guessing we can approach the problem in a structured
logical fashion as below. Reflect for a moment though that really we would
like a solution which supplies what is necessary under the contract at
**minimum cost**. Logically such a minimum cost solution to this decision
problem must exist. However even if we keep guessing we can never be sure
whether we have found this minimum cost solution or not. Fortunately our
structured approach will enable us to find the minimum cost solution.

What we have is a verbal description of the Two Mines problem. What
we need to do is to translate that verbal description into an *equivalent*
mathematical description.

In dealing with problems of this kind we often do best to consider them in the order:

- variables
- constraints
- objective.

We do this below and note here that this process is often called *formulating*
the problem (or more strictly formulating a mathematical representation
of the problem).

(1) *Variables*

These represent the "decisions that have to be made" or the "unknowns".

Let

x = number of days per week mine X is operated y = number of days per week mine Y is operated

Note here that x >= 0 and y >= 0.

(2) *Constraints*

It is best to first put each constraint into words and then express it in a mathematical form.

- ore production constraints - balance the amount produced with the quantity required under the smelting plant contract

Ore High 6x + 1y >= 12 Medium 3x + 1y >= 8 Low 4x + 6y >= 24

Note we have an inequality here rather than an equality. This implies
that we may produce more of some grade of ore than we need. In fact we
have the general rule: **given a choice between an equality and
an inequality choose the inequality**.

For example - if we choose an equality for the ore production constraints
we have the three equations 6x+y=12, 3x+y=8 and 4x+6y=24 and there are
*no* values of x and y which satisfy all three equations (the problem
is therefore said to be "over-constrained"). For example the
(unique) values of x and y which satisfy 6x+y=12 and 3x+y=8 are x=4/3 and
y=4, but these values do not satisfy 4x+6y=24.

**The reason for this general rule is that choosing an inequality rather
than an equality gives us more flexibility in optimising (maximising or
minimising) the objective (deciding values for the decision variables that
optimise the objective). **

- days per week constraint - we cannot work more than a certain maximum number of days a week e.g. for a 5 day week we have

x <= 5 y <= 5

Constraints of this type are often called *implicit* constraints
because they are implicit in the definition of the variables.

(3) *Objective*

Again in words our objective is (presumably) to minimise cost which is given by 180x + 160y

Hence we have the complete mathematical representation of the problem as:

minimise 180x + 160y subject to 6x + y >= 12 3x + y >= 8 4x + 6y >= 24 x <= 5 y <= 5 x,y >= 0

There are a number of points to note here:

- a key issue behind formulation is that
**IT MAKES YOU THINK**. Even if you never do anything with the mathematics this process of trying to think clearly and logically about a problem can be very valuable.

- a common problem with formulation is to overlook some constraints or variables and the entire formulation process should be regarded as an iterative one (iterating back and forth between variables/constraints/objective until we are satisfied).

- the mathematical problem given above has the form
- all
**variables**continuous (i.e. can take fractional values) - a single
**objective**(maximise or minimise) - the objective and
**constraints**are linear i.e. any term is either a constant or a constant multiplied by an unknown (e.g. 24, 4x, 6y are linear terms but xy is a non-linear term). - any formulation which satisfies these three conditions is called a
*linear program (LP)*. As we shall see later LP's are important..

- we have (implicitly) assumed that it is permissible to work in fractions
of days - problems where this is not permissible and variables
*must*take integer values will be dealt with under*integer programming (IP)*.

- often (strictly) the decision variables should be integer but for reasons of simplicity we let them be fractional. This is especially relevant in problems where the values of the decision variables are large because any fractional part can then usually be ignored (note that often the data (numbers) that we use in formulating the LP will be inaccurate anyway).

- the way the complete mathematical representation of the problem is set out above is the standard way (with the objective first, then the constraints and finally the reminder that all variables are >=0).

Considering the Two Mines example given above:

- this problem was a
*decision problem*

- we have taken a real-world situation and constructed an equivalent
mathematical representation - such a representation is often called a mathematical
*model*of the real-world situation (and the process by which the model is obtained is called*formulating*the model).

Just to confuse things the mathematical model of the problem is sometimes called the*formulation*of the problem.

- having obtained our mathematical model we (hopefully) have some quantitative
method which will enable us to numerically solve the model (i.e. obtain
a numerical solution) - such a quantitative method is often called an
*algorithm*for solving the model. - our model has an
*objective*, that is something which we are trying to*optimise*.

Essentially an algorithm (for a particular model) is a set of instructions which, when followed in a step-by-step fashion, will produce a numerical solution to that model. You will see some examples of algorithms later in this course but note here that many algorithms for OR problems are available in computer packages.

- having obtained the numerical solution of our model we have to translate that solution back into the real-world situation.

On an historical note the Encyclopedia Britannica notes that the word algorithm derives from the Latin translation, Algoritmi de numero Indorum, of the 9th-century Muslim mathematician Abu Ja'far Muhammad ibn Musa Al-Khwarizmi who wrote "Al-Khwarizmi Concerning the Hindu Art of Reckoning."

Hence we have a definition of OR as:

*OR is the representation of real-world systems by mathematical
models together with the use of quantitative methods (algorithms) for solving
such models, with a view to optimising.*

One thing I wish to emphasise about OR is that it typically deals with
**decision problems**. You will see examples of the many different types
of decision problem that can be tackled using OR throughout OR-Notes.

We can also define a mathematical model as consisting of:

- Decision
*variables*, which are the unknowns to be determined by the solution to the model. *Constraints*to represent the physical limitations of the system.- An
*objective*function. - A
*solution*(or*optimal solution*) to the model is the identification of a set of variable values which are feasible (i.e. satisfy all the constraints) and which lead to the optimal value of the objective function.

In general terms we can regard OR as being the application of scientific methods/thinking to decision making. Underlying OR is the philosophy that:

- decisions have to be made; and
- using a quantitative (explicit, articulated) approach will lead (on average) to better decisions than using non-quantitative (implicit, unarticulated) approaches (such as those used (?) by human decision makers).

Indeed it can be argued that although OR is imperfect it offers the
*best* available approach to making a particular decision in many
instances (which is *not* to say that using OR will produce the *right*
decision).

Often the human approach to decision making can be characterised (conceptually) as the "ask Fred" approach, simply give Fred ('the expert') the problem and relevant data, shut him in a room for a while and wait for an answer to appear.

The difficulties with this approach are:

- speed (cost) involved in arriving at a solution
- quality of solution - does Fred produce a good quality solution in any particular case
- consistency of solution - does Fred always produce solutions of the same quality (this is especially important when comparing different options).

You can form your own judgement as to whether OR is better than this approach or not.

Drawing on our experience with the Two Mines problem we can identify the phases that a (real-world) OR project might go through.

1. Problem identification

- Diagnosis of the problem from its symptoms if not obvious (i.e. what is the problem?)
- Delineation of the subproblem to be studied. Often we have to ignore parts of the entire problem.
- Establishment of objectives, limitations and requirements.

2. Formulation as a mathematical model

It may be that a problem can be modelled in differing ways, and the choice of the appropriate model may be crucial to the success of the OR project. In addition to algorithmic considerations for solving the model (i.e. can we solve our model numerically?) we must also consider the availability and accuracy of the real-world data that is required as input to the model.

Note that the "**data barrier**" ("we don't have the
data!!!") can appear here, particularly if people are trying to block
the project. Often data can be collected/estimated, particularly if the
potential benefits from the project are large enough.

You will also find, if you do much OR in the real-world, that some environments
are naturally *data-poor*, that is the data is of poor quality or
nonexistent and some environments are naturally *data-rich*. As examples
of this I have worked on a church
location study (a data-poor environment) and an airport
terminal check-in desk allocation study (a data-rich environment).

This issue of the data environment can affect the model that you build. If you believe that certain data can never (realistically) be obtained there is perhaps little point in building a model that uses such data.

3. Model validation (or algorithm validation)

Model validation involves running the algorithm for the model on the computer in order to ensure:

- the input data is free from errors
- the computer program is bug-free (or at least there are no outstanding bugs)
- the computer program correctly represents the model we are attempting to validate
- the results from the algorithm seem reasonable (or if they are surprising we can at least understand why they are surprising). Sometimes we feed the algorithm historical input data (if it is available and is relevant) and compare the output with the historical result.

4. Solution of the model

Standard computer packages, or specially developed algorithms, can be used to solve the model (as mentioned above). In practice, a "solution" often involves very many solutions under varying assumptions to establish sensitivity. For example, what if we vary the input data (which will be inaccurate anyway), then how will this effect the values of the decision variables? Questions of this type are commonly known as "what if" questions nowadays.

Note here that the factors which allow such questions to be asked and answered are:

- the speed of processing (turn-around time) available by using pc's; and
- the interactive/user-friendly nature of many pc software packages.

5. Implementation

This phase may involve the implementation of the results of the study
or the implementation of the *algorithm* for solving the model as
an operational tool (usually in a computer package).

In the first instance detailed instructions on what has to be done (including time schedules) to implement the results must be issued. In the second instance operating manuals and training schemes will have to be produced for the effective use of the algorithm as an operational tool.

It is believed that many of the OR projects which successfully pass
through the first four phases given above fail at the implementation stage
(i.e. the work that has been done does not have a lasting effect). As a
result one topic that has received attention in terms of bringing an OR
project to a successful conclusion (in terms of implementation) is the
issue of *client involvement*. By this is meant keeping the client
(the sponsor/originator of the project) informed and consulted during the
course of the project so that they come to identify with the project and
want it to succeed. Achieving this is really a matter of experience.

A graphical description of this process is given below.

Not all OR projects get reported in the literature (especially OR projects which fail). However to give you an idea of the areas in which OR can be applied we give below some abstracts from papers on OR projects that have been reported in the literature (all US projects drawn from the journal Interfaces). Some other OR projects can be found here.

Note here that, at this stage of the course, you will probably not understand every aspect of these abstracts but you should have a better understanding of them by the end of the course.

- Yield management at American Airlines

Critical to an airline's operation is the effective use of its reservations
inventory. American Airlines began research in the early 1960's in managing
revenue from this inventory. Because of the problem's size and difficulty,
American Airlines Decision Technologies has developed a series of OR models
that effectively reduce the large problem to three much smaller and far
more manageable subproblems: overbooking, discount allocation and traffic
management. The results of the subproblem solutions are combined to determine
the final inventory levels. American Airlines estimates the quantifiable
benefit at $1.4 billion over the last three years and expects an annual
revenue contribution of over $500 million to continue into the future.

*Yield management* is also sometimes referred to as *capacity management*.
It applies in systems where the cost of operating is essentially fixed
and the focus is primarily, though not exclusively, on revenue maximisation.
For example all transport systems (air, land, sea) operating to a fixed
timetable (schedule) could potentially benefit from yield management. Hotels
and universities would be other examples of systems where the focus should
primarily be on revenue maximisation.

To give you an illustration of the kind of problems involved in yield
management suppose that we consider a specific flight, say the 4pm on a
Thursday from Chicago O'Hare to New York JFK. Further suppose that there
are exactly 100 passenger seats on the plane subdivided into 70 economy
seats and 30 business class seats (and that this subdivision cannot be
changed). An economy fare is $200 and a business class fare is $1000. Then
a fundamental question (a decision problem) is : *How many tickets
can we sell ?*

One key point to note about this decision problem is that it is a **routine**
one, airlines need to make similar decisions day after day about many flights.

Suppose now that at 7am on the day of the flight the situation is that
we have sold 10 business class tickets and 69 economy tickets. A potential
passenger phones up requesting an economy ticket. Then a fundamental question
(a decision problem) is : *Would you sell it to them ? Reflect - do
the figures given for fares $200 economy, $1000 business, affect the answer
to this question or not ?*

Again this decision problem is a routine one, airlines need to make
similar decisions day after day, minute after minute, about many flights.
Also note that in this decision problem an answer must be reached quickly.
The potential passenger on the phone expects an immediate answer. One factor
that may influence your thinking here is consider **certain money**
(money we are sure to get) and **uncertain money **(money we may, or
may not, get).

Suppose now that at 1pm on the day of the flight the situation is that
we have sold 30 business class tickets and 69 economy tickets. A potential
passenger phones up requesting an economy ticket. Then a fundamental question
(a decision problem) is : *Would you sell it to them ?*

- NETCAP - an interactive optimisation system for GTE telephone network planning

With operations extending from the east coast to Hawaii, GTE is the largest local telephone company in the United States. Even before its 1991 merger with Contel, GTE maintained more than 2,600 central offices serving over 15.7 million customer lines. It does extensive planning to ensure that its $300 million annual investment in customer access facilities is well spent. To help GTE Corporation in a very complex task of planning the customer access network, GTE Laboratories developed a decision support tool called NETCAP that is used by nearly 200 GTE network planners, improving productivity by more than 500% and saving an estimated $30 million per year in network construction costs.

- Managing consumer credit delinquency in the US economy: a multi-billion dollar management science application

GE Capital provides credit card services for a consumer credit business exceeding $12 billion in total outstanding dollars. Its objective is to optimally manage delinquency by improving the allocation of limited collection resources to maximise net collections over multiple billing periods. We developed a probabilistic account flow model and statistically designed programs to provide accurate data on collection resource performance. A linear programming formulation produces optimal resource allocations that have been implemented across the business. The PAYMENT system has permanently changed the way GE Capital manages delinquent consumer credit, reduced annual losses by approximately $37 million, and improved customer goodwill.

Note here that GE Capital also operates in the UK. My Debenhams store card is administered/operated by them.

After graduating from Imperial College you find yourself at a business lunch with the managing director of the company employing you. You know that he started as a tea-boy 40 years ago and rose through the ranks of the company (without any formal education) to his present position. He believes that all a person needs to succeed in business are (innate) ability and experience. What arguments would you use to convince him that the decision-making techniques dealt with in this course are of value?

The points that we would expect to see in an answer include:

- OR obviously of value in tactical situations where data well defined
- an advantage of explicit decision making is that it is possible to examine assumptions explicitly
- might expect an "analytical" approach to be better (on average) than a person
- OR techniques combine the ability and experience of many people
- sensitivity analysis can be performed in a systematic fashion
- OR enables problems too large for a person to tackle effectively to be dealt with
- constructing an OR model structures thought about what is/is not important in a problem
- a training in OR teaches a person to think about problems in a logical fashion
- using standard OR techniques prevents a person having to "reinvent the wheel" each time they meet a suitable problem
- OR techniques enable computers to be used with (usually) standard packages and consequently all the benefits of computerised analysis (speed, rapid (elapsed) solution time, graphical output, etc)
- OR techniques an aid (complement) to ability and experience not a substitute for them
- many OR techniques simple to understand and apply
- there have been many successful OR projects (e.g. ...)
- other companies use OR techniques - do we want to be left behind?
- ability and experience are vital but need OR to use these effectively in tackling large problems
- OR techniques free executive time for more creative tasks

Discuss the phases that a typical operational research project might
go through, with reference to *one* particular problem of which you
are aware.

The phases that a typical OR project might go through are:

- problem identification
- formulation as a mathematical model
- model validation
- solution of the model
- implementation

We would be looking for a discussion of these points with reference to one particular problem.

- For Air Products and Chemicals, Inc., inventory management of industrial
gases at customer locations is integrated with vehicle scheduling and despatching.
Their advanced
*decision support system*includes on-line data entry functions, customer usage forecasting, a time/distance network with a shortest path algorithm to compute intercustomer travel times and distances, a mathematical optimization module to produce daily delivery schedules, and an interactive schedule change interface. The optimization module uses a sophisticated Lagrangian relaxation algorithm to solve mixed integer programs with up to 800,000 variables and 200,000 constraints to near optimality. The system, first implemented in October 1981, has been saving between 6% and 10% of operating costs. Note here that the term "decision support system" is one that is becoming increasingly common nowadays. - A mini-computer based information system with on-line optimal route planning capability was developed to assist dispatchers on the complex northern portion of Southern Railway's Alabama Division. The routing plan is revised automatically as conditions change. Since implementation in September 1980, train delay has been more than 15 percent lower, reflecting annual savings of $316,000. The dispatching support system is now being expanded to all other Southern Railway operating divisions with $3,000,000 annual savings expected from reduced train delay.
- An integrated modelling and measurement system, ASSESSOR provides management with forecasts and diagnostic information about the sales potential of new packaged goods before they are test marketed. Over the past decade, Management Decision Systems has applied the methodology to 450 new products. A study indicates that ASSESSOR has helped reduce the failure rate of new products in test market by almost a half and saved the 100 client firms an estimated $120 million.

- This case study describes an investigation which was undertaken for a local shopkeeper after one of his shop assistants had been convicted of theft. The person concerned had admitted stealing a few pounds on just one occasion, but a series of worsening year-end results over a period of three or four years caused the shopkeeper to suspect that stealing had been taking place on a very large scale over a long period of time. Could this be 'proved' by examining in detail records of the shop's business for the years in question? The analysis undertaken involved principally the number of customers each week and the revenue per customer. The most usual form of theft involves 'understriking' (ringing into the till less than the value of the sale and subsequently taking out the difference). This practice will be expected to reduce the revenue per customer and increase the number of customers (because the incorrect entry is usually disguised by immediately ringing in a no-sale or a zero amount). Clear evidence was found of stealing on a much larger scale than had been admitted.
- Defence policy-making has to be set against an uncertain - indeed unpredictable - future. Given this uncertainty surrounding future conflict, air forces play an important part because of their inherent flexibility to undertake a variety of roles. This paper describes the assistance given to the Air Staff in deciding what mix of air-delivered weapons should be stockpiled to provide the RAF with this flexibility, subject to budgetary and other constraints. It is a simple application of linear programming with an unusual objective function. A number of alternative approaches are reviewed, and the rather pragmatic way in which various decisions regarding the conduct of the study were made is discussed.