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

#### Definition

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.

#### Two Mines Company

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.

#### Guessing

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.

#### Two Mines 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:

1. variables
2. constraints
3. 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).

#### Discussion

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.
• 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.

• our model has an objective, that is something which we are trying to optimise.
• 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.

#### Philosophy

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.

#### Phases of an OR project

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.

#### Example OR projects

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.

#### Operational research example 1987 UG exam

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?

#### Solution

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

#### Operational research example 1987 UG exam

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

#### Solution

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

1. problem identification
2. formulation as a mathematical model
3. model validation
4. solution of the model
5. implementation

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

#### US projects

• 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.

#### UK projects

• 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.