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.
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.
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:
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 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).
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:
Considering the Two Mines example given above:
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.
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:
In general terms we can regard OR as being the application of scientific methods/thinking to decision making. Underlying OR is the philosophy that:
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:
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
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:
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:
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.
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 ?
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.
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:
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:
We would be looking for a discussion of these points with reference to one particular problem.