Foreword
History of Optimum Decison Making Techniques and Their Applications
During my High School education, I had a mathematics teacher who used to prove one theorem after another in his class. In that class I got the impression that his aim, and in fact the aim of mathematics as a subject, is to maximize the number of theorems proved. After seeing what felt like close to 100 theorems, I thought of the question, what is the very first mathematical result realized by mankind? The textbook did not discuss this aspect at all. So one day, I picked up enough courage to ask the teacher about it. He thought about it for a long time, and then said that he does not know the answer, but will discuss with other colleagues and let me know. My question went up all the way to the level of the Head Master, but none of the teachers knew the answer.
Thinking about that question now, I believe that the discovery of the first mathematical result realized by mankind goes back well over 100,000 years ago. In those days people used to live in caves, and they needed to fetch water from the nearby river for their living. So they faced the problem of finding the shortest route from the center of their cave entrance to the nearest point to it on the river bank (an instance of an unconstrained decision-making problem, as there are no constraints on the route taken), and they realized that this shortest route is the straight line joining the two points. This, I believe, is the first mathematical result realized by man.
In this way, I believe that the human urge to find optimum solutions to the decisionmaking problems that they faced in their daily living provided the motivation for the development of mathematics.
Solving a decision making problem optimally involves the following steps: (1) Construct an appropriate mathematical model for it, (2) then select an efficient algorithm for solving that model, and (3) finally implement the solution obtained by the algorithm.
v
vi
Foreword
History of Mathematical Modeling
For the first step above, both Chinese and Indians can feel proud that their ancestors pioneered the development of mathematical modeling over 2500 years ago. It involves representing the quantities that we want to determine by symbols—usually letters of the alphabet like x, y, z (the symbols representing the unknown quantities to be determined are nowadays called unknowns, or variables, or decision variables) then express the relationships between the quantities represented by these symbols in the form of equations, or other functional relationships. This process is called modeling or mathematical modeling. The earliest mathematical models constructed were systems of linear equations.
The Chinese text Chiu-Chang Suanshu (Nine Chapters on the Mathematical Art (a summary of this ancient Chinese text can be seen at the website: http://www-groups.dcs.st-and.ac.uk/history/HistTopics/Nine-chapters.html) composed over 2000 years ago describes the modeling process using a problem of determining the yield (measured in units called "tou") of an alcoholic drink made from rice. Rice grain produced by farmers contains three grades of grain: inferior, medium, and superior. Yield data from rice grain procured from three different farmers, Farmers 1, 2, and 3 are given. The composition of rice from these farmers (in terms of the percentage by weight of the three grades) and the yield from it is given in the following table:
Rice from farmer	Weight percent of grade			Yield of drink in tou/unit
	Inferior	Medium	Superior	
1	50	30	20	6
2	45	25	30	8
3	30	30	40	9
The problem considered is to determine the yield of the drink if it is made from pure inferior, medium, and superior grades of rice. Denote these quantities by the symbols:
jci = yield in tou from one unit of inferior grade rice X2 = yield in tou from one unit of medium grade rice jc3 = yield in tou from one unit of superior grade rice
Then the mathematical model for determining the values of these variables is:
50*i + 30a;2 + 20*3 = 6 45*i + 25*2 + 30*3 = 8 30*i + 30*2 + 40*3 = 9
Ancient Indian texts Sulabha suutrah (Easy Solution Procedures), and the Bakshali Manuscript, with origin during the same period describe the process in terms of models consisting of systems of two (three) linear equations in two (three) variables; for
Foreword
vii
information on these texts, and a summary see: http://www.tica.com/adults/origin-math.html. One of the problems considered deals with a fruit seller in a farmer's market. She is selling the following bundles of fruit:
Bundle	Price
8 citrons + 5 mangoes	20
5 citrons + 4 mangoes	15
The problem is to determine how much she is charging for each individual citron, mango respectively. So, it is to detrmine the values of the following variables:
xi = price in Rs. of an individual citron X2 — price in Rs. of an individual mango
Then the mathematical model for determining the values of these variables is:
8xi + 5jc2 = 20 5xi + 4x2 = 15
The Chinese and the Indians developed the elimination method for solving linear equation models, independently around that same period, more than 2000 years ago. This method was almost unknown in Europe until the German mathematician Gauss rediscovered it in the eighteenth century, hence it is now-a-days called the Gaussian ehmination method.
History of the Word "Algorithm"
Methods for solving mathematical models are called algorithms. This word itself has a very strange connection to India. For many centuries, Muslim, Arabs, and Persians have invaded India. Many of these invaders settled down in India, but a few of them also returned to their home lands after some stay in India. One of those is a Persian, Muhammad ibn-Musa Alkhawarizmi, who left India after learning mathematics from Indian teachers in the ninth century CE. Then in 825 CE, he wrote a book Kitab al-Jam 'a wal-Tafreeq bil Hisab al-Hindi, in Arabic, the lingua-franca in the Middle East in those days. This book appeared in a Latin translation under the title Algoritmi de Numero Indorum, meaning Al-Khwarizmi Concerning the Hindu Art of Reckoning; it was based on earlier Indian and Arabic treatises. Today this book survives only in its Latin translation, because all the copies of the original Arabic version have been lost or destroyed. The word algorithm (meaning procedures for solving algebraic systems) originated from the title of this Latin translation. Algorithms seem to have originated in the work of ancient Indian mathematicians on rules for solving linear and quadratic equations.
viii
Foreword
What Steps to Take Before Implementing an Algorithm in Practice
When an algorithm is developed for a decision-making problem, we need to make sure, either through a mathematical analysis of its performance, or through a computational test, that it outputs a guaranteed optimal or near optimal solution.
I will relate my experience once. I was talking with the DMs (Decision Makers) at a company on the benefits their company can gain by using optimal decisionmaking techniques for the decisions they make. They told me "Prof. Murty, for every decision we have to make, we use the following approach: we list all possible actions we can take for it, and estimate the profit we can get by taking each of those actions. Among all these actions, we select for implementation, one that is associated with the maximum expected profit. Because of this, we do not see how your optimal decision-making techniques can improve on our performance. If you like, you can try to convince us using an example."
I constructed the following example for them. It deals with a marketing company. The company divided their marketing area into six different zones, Zi-Z6, based on the background and other characteristics of people living there. For example the residents of zone Z\ are administrators and other relatively well-off people. Zone Z2 houses academic communities, etc. Then, they selected six experienced candidates, Ci-Ce with different marketing backgrounds, and other experiences, etc.
Now they are faced with the very important decision-making problem of allocating one candidate as Director of Marketing Operations per zone. These are high level positions with the responsibility of maximizing the growth in company's profit.
Considering the background, experience, and other relevent characteristics of the candidates, and information obtained by market surveys, company's statisticians have come up with the following estimates of the profit to the company/year by the allocation of each candidate to (the Director of Marketing Operations position in) each zone.
	cij = Expected annual profit in $million if candidate Ci is assigned to zone Zj					
Zone =		z2		Z4	z5	
Candidate = CI	29	10	1	17	6	2
C2	36	31	26	32	28	27
C3	35	24	18	25	21	19
C4	30	11	3	20	8	4
C5	34	16	13	23	15	14
C6	33	12	5	22	9	7
Each candidate can be allocated to any of the six zones, so there are six possible actions associated with each candidate (allocating her/him to the position in zone 7 = 1 to 6). Since there are 6 candidates, there are 6x6 = 36 possible actions the company can take ( (Q, Zj) = allocating C,- to the position in Zj\ i,j= 1 to 6). The above table gives the annual expected profit to the company associated with each of these 36 actions.
Foreword
ix
To apply the procedure described by the DMs at the company, we look for the action corresponding to the highest annual expected profit, it is (C2, Zi) yielding $ 36 million in expected annual profit. After taking this action, we are left with candidates Ci, C3 to C$, and zones Z^-Z^. Among the actions available at this stage, the one corresponding to the maximum profit is (C3, Z4), leading to $ 25 million in expected annual profits. Continuing the same way, leads to the solution of allocating candidates C2, C3, C5, Ce, C4, C\ to the position in zones Z\, Z4, Z2, Z5, Z6, Z3 respectively, yielding total annual expected profit of $36+ 25+ 16 + 9 + 4+1=91 million.
To check how good this solution is, we generate a random solution. It allocates candidates C\, C2, C3, C4, C5, Cf, to the position in zones Z4, Z3, Z5, Z6, Z\, Z2 respectively; which yields an annual total expected profit of $17 +26+ 21 + 4 + 34+12 = 114 million; higher than the annual expected profit corresponding to the solution produced by the company's procedure!
Actually, by developing a mathematical model for this problem, and solving it by an algorithm guaranteed to solve the problem exactly, it can be verified that the solution given by the company's procedure, instead of maximizing the total annual expected profit as required, in fact minimizes it!!!
The optimal solution maximizing the total annual expected profit allocates candidates C\, C2, C3, C4, C5, Ce to the position in zones Z\, Z3, Z^, Z\, Z5, Z2 respectively, leading to an annual expected profit of $29+ 26+19 +20+15 + 12 = 121 million.
This shows that optimal decision-making problems are tricky, and procedures for solving them based on instinct and simple hunches may often lead to poor solutions. Hence, the importance of developing an appropriate mathematical model for them, and solving the model using an algorithm guaranteed to produce a good solution for implementation. In this book we discuss applications of this approach in a variety of areas.
IOE Dept., University of Michigan Ann Arbor, MI-48109-2117, USA. 9 September 2012.
Katta Gopalakrishna Murty