Introduction to Mathematical Optimization
Business insights is a key success factor influencing the performance of decision makers, specifically the quality of their decisions. Nowadays, sheer amounts of data are available for organizations to collect and analyze. Data is considered the raw material of the 21st century. The majority of raw data does not offer a lot of value in its unprocessed state. The extraction of knowledge from these datasets can help decision makers gaining valuable insights.
When making a decision, one usually needs to consider a large number of alternatives. Each of these must be evaluated using one or several criteria in order to determine the “best” decision. Mathematical optimization is the discipline of developing realistic plans or schedules to assist highly data-intensive businesses and organizations making better decisions that provides the best possible balance between customer service and revenue goals.
“All our lives is about making decisions. So in some sense the whole world is about analytics and optimization. Isn’t it?” — Jai Menon (IBM Fellow).
According to Cambridge Advanced Learner’s Dictionary, "optimization" is the process of making something as good or effective as possible. The ‘something’ here is a problem or situation to solve. Mathematical optimization is always about a set of problem and solution, which is described by mathematical abstract or model. How ‘good’ a solution is by a given measure. If the goal is measurable in absolute terms, i.e. money and time, then the closer the solution is to the extreme i.e. minimum or maximum, of a goal, the better. That is, optimization is a kind of search among the alternatives.
Real World Application: Supermarket Cashiers Scheduling
Nobody likes to wait in lines to pay groceries. The check-out cashiers are often the only members of the supermarket personnel to come in contact with the customers. For this reason, along with others, the check-out operation of the supermarket should always be at its best in order to give customers a favorable impression of the store. This impression can be enhanced by proper scheduling of cashiers in order that customers can be serviced promptly or with a minimum time spent in check-out lines.
Consider this. You understand that the overall service is the key for the success of a supermarket. As a scheduling manager, you need to schedule cashiers for a large supermarket with 10 stores in different areas. There are total 100 individual tills scheduled 16 hours per day. Commonly, you will schedule over 1000 cashiers of full time and part time in a month. Most are fully trained cashiers but there are also other, new cashiers with less experience. The schedule is a monthly schedule and is posted one month in advance, although adjustments are made after posting.
Your goals is to minimize labor costs, provided the constraints:
- a cashier’s weekly schedule must be for one and only one shift (day, evening or night).
- a cashier’s shift can be for 6, 8, 10 or 12 hours.
- a cashier may not work more than three 12-hour shifts in a row within a week.
- there must be at least 24 hours between the end of the last shift in a week and the start of the a new one in the next week.
- a group of new cashiers (maximum 3) must be accompanied by an experienced cashier for training purpose.
- cashier’s shift and vacation requests should be respected based on seniority.
This is a typical workforce scheduling problem that can leverage prescriptive analytics for best solution. For more information about supermarket cashiers scheduling, please read Supermarket Cashier Scheduling Problems and Solutions. Successful companies are staying competitive by transforming their approach to commerce using deeper actionable insights from mathematical optimization.
- A major transportation company reduced EUR 20 million operating costs annually through better allocation of rolling stock.
- A central securities depository saved 160 million for financial institutions in one year by faster clearing of securities transactions.
- A power system operator reduced EUR 22 million of annual costs to consumers through better dispatch of generators.
- A major hotel chain increased 226 million of annual revenue by offering the right product to the right customer at the right price.
More Industry Applications
Manufacturing / Consumer & Industrial Engineering
- Inventory optimization
- supply chain network design
- production planning
- detailed scheduling
- shipment planning
- truck loading
- maintenance scheduling
Transportation & Logistics
- depot / warehouse location
- fleet assignment
- network design
- vehicle & container loading
- vehicle routing & delivery scheduling
- yard, crew, driver & maintenance scheduling
- inventory optimization
Financial services & Banking
- portfolio optimization & rebalancing
- Portfolio in-kinding
- trade crossing
- loan pooling
- product / price recommendations
Natural Resources, Energy & Utilities
- supply portfolio planning
- power generation scheduling
- distribution planning
- water reservoir management
- mine operations
- timber harvesting
Telecom
- network capacity planning
- routing
- adaptive network configuration
- equipment and service configuration
- antenna and concentrator location
Retail
- Workforce scheduling
- advertising scheduling
- marketing campaign optimization
- store operations
- merchandise planning
Hospitality & Leisure
- revenue / yield management
- appointment & field service scheduling
- combinatorial auctions for procurement
History of Mathematical Optimization
For over 2000 years, humans have been working with geometry, algebra and logic to find better solutions to our most challenging problems. Mathematical optimization is a more of a general term for Operations Research (OR), the application of mathematical and scientific methods to solve complex and real-life problems. Operations Research was first developed for military operations during World War Two (WW2). British Navy and the US Navy apply the techniques to determine the best locations for radar stations and anti-submarine resources. After the war, scientists started applying mathematical optimization to similar problems in the industry.
Read: Optimization Engines Make The Industry Efficient
The Advanced Analytics Landscape
Advanced analytics is a grouping of analytic techniques used to predict future outcomes. Advanced analytics increases the organization’s breakaway capability through 3 levels of analytics sophistication, which are descriptive analytics, predictive analytics and prescriptive analytics (mathematical optimization).
0) Data Collection
In any decision making setup, the first step is to capture lots of information, the structured and unstructured data from all kind of sources i.e. numeric, text or social, of the past and present. We definitely want to collect reliable and clean data. As the principle "Garbage in, Garbage out", the best methods will produce as good result as the data quality is.
1) Descriptive Analytics
The descriptive analytics is the simplest sophistication of analytics. It allows us to condense big data into smaller, more useful summary of information. With the enough data in hand, we start to see patterns and relate the data in a way which may shed light on connections. We can filter and drill into details to find out what happened in the past and what is happening now. For small businesses, it is still meaningful to make decisions based on these information with some industry assumptions. We can estimate that more than 80% of business analytics is still staying at this descriptive analytics level.
Rule-based System
The knowledge and experience is in the head of the expert. We can create plan visually on the screen manually. There is always a possibility that human experience is enough. The best solution has been found already and it will not change significantly in the future.
The human experience and knowledge can be converted to rules and it is easily understandable by the planner. Expert’s knowledge can be automated for some conditions and actions over a set of objects which are truly in their business domain (BOM). With these rules or some propagation engines, a solution checker can check on what constraints or conditions the plan should satisfy with visual and highlighting the ‘not yet satisfied’ parts. The rules can be automatically executed without (almost) no human interaction. However, when the plan doesn’t satisfy all the constraints, the human correction is necessary. This is a Rule-based or Expert System:
IF a given set of conditions are met THEN certain actions should be taken.
Next best heuristic approach
Heuristics were the main tool used to solve optimization problems in the industry. Below is an example of sequence dependent set-ups. Time shown is the time to switch from one job to the next.
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | x | 5 | 8 | 4 | 3 |
| 2 | x | x | 1 | 10 | 15 |
| 3 | x | 5 | x | 12 | 5 |
| 4 | x | 7 | 9 | x | 3 |
| 5 | x | 3 | 7 | 13 | x |
Question: Assume Job 1 is running, what is the best sequence?
If we use a heuristic, we can do things that look good at the start. The sequence is 1, 5, 2, 3, 4 which the total set up is 19. It is from 3 to 4 that we get in trouble.
The optimal approach can help us find the right sequence and avoid running into pitfalls later. The optimal sequence is 1, 4, 5, 2, 3 with the total set up of 11.
There are lots of ways to potentially organize the sequence but we cannot figure it out in our head or on a piece of paper or in a simple spreadsheet, especially when the data is larger and more complex. With prescriptive analytics, we can model decisions mathematically based on a data model, creating a useful, albeit imperfect abstraction of the real world.
2) Predictive Analytics
Predictive analytics is the next step up in data reduction. It utilizes a variety of statistical methods, modeling, data mining and machine learning techniques to study the patterns of the recent and historical data. These include preparing and managing the data through scoring and classification. Thereby analysts can easily build predictive models, such as demand forecast, market segmentation and product clustering, to forecast and simulate what scenarios might happen in the future.
3) Prescriptive Analytics
The emerging technology of prescriptive analytics goes beyond descriptive and predictive models by recommending (prescribing) both the action necessary to achieve the predicted outcomes and showing the likely outcomes / effects of each decision. The prescriptive analytics is an extension of predictive analytics with two additional components, i.e. actionable data and a feedback system that tracks the outcome produced by the action taken.
Uncertainty can be dealt with many ways. Businesses and organizations want to respond to the changes in their operation processes and improve their performance. Using the predicted data as input, given our objectives, various choices and influences that might affect the outcome, we can explore alternatives and understand trade-offs. As a result, we can create all possible plans or schedules that are measured by KPIs and ROI. We can fully automate expert’s knowledge by having a expert creates some models of the world and evaluate (search in) the world based on that model. Finally, we can find the optimal solution and prescribe the best possible course of action for the future.
We can make only those decisions which can be reversible (even not always possible). Depending on how fast we can react, we can make smaller decisions, synchronize with reality more frequently and re-planning or rescheduling all the time.
In short, prescriptive analytics predicts the possible consequences based on different choice of action. With that, it can recommend the best course of action for any pre-specified outcome. The more we go to the direction of prescriptive, the more sophistication is needed, the more value it can bring.
More and more businesses start looking into prescriptive analytics now. The efficient use of resources has never been more critical in terms of impact on profitability. Changes in the economy and in business process management are making smart, agile economic planning and scenario comparison a necessity. Besides that, the development in hardware and software technology had been improved exponentially. We can leverage tools that deliver a huge head start toward higher quality decisions in less time. Advances in computer hardware and optimization software have made it possible to evaluate large planning and scheduling problems that were too difficult for computers as recently as five years ago. Advances in software technology are making optimization accessible to nontechnical planners, schedulers and managers who make the decisions in most organizations.
Comparison of Advanced Analytics
| Use case | Data | Predict | Optimize |
|---|---|---|---|
| What had happened in the past and happening now? | What could happen? | what should happen? | |
| Pricing Optimization | Past sales, price levels, | Predict sales level from price | Set prices in order to maximize profit / revenue |
| Cloud Capacity | System usage, CPUs, system capacity | predict storage and memory needs | Optimize how a virtual system is configured |
| Consumer Goods | history of product sales | what will be any sales forecast for the next month? | With the forecasted data, where should I place my inventory? How much safety stock do I need? |
| Retail | history of customer purchasing data | will you be able to predict what items will interest them? | What items should I place in which stores? What campaigns would be best to promote those items? How do I minimize discounts? |
| Manufacturing | history of machine data | will you be able to predict when your machine might breakdown? | Using the predicted machine breakdown data, do you know the best times to schedule and conduct preventive maintenance? (Demand, inventory…) |
Rule-based System vs Mathematical Optimization
Below is the detailed comparison between rule-based system and mathematical optimization.
| Rule-based System | Mathematical Optimization |
|---|---|
| Reactive – when conditions are met, rules are triggered. | Proactive – all predefined constraints should be (usually) satisfied in a plan/solution. |
| Local – when conditions are met, rules are triggered. | Global – it is a search guided by a goal (function). |
| Not really abstraction of the problem/business, the rules are working on the business domain. | Abstract model is made (on which a search is conducted) to find the best values for the variables. |
| Most cases, it’s faster than OR-based approach as no search at all, just actions if conditions met. | |
| Rules may contradict one another but for real life problem the solution is satisfactory. | If constraints are contradicting, then there is no solution for real life problem and the user will know that in advance. It is possible to make suggestions which constraints should be eliminated to produce a plan/solution which satisfies the remaining constraints. |
| When to Use | |
| the reality/data is changing too fast, no meaning to make an optimized plan because the plan is obsolete by the time. | the aim is optimality. There is enough time to make/change the plan. |
| Time to react is more important than the quality of the plan. It doesn’t matter much if the solutions is not perfect (maybe contradictory) or there might be better one. | The solution has to be bulletproof (no contradictions are acceptable). So, the quality of planning data is clean, available and cover reality. |
| There is already accumulated human knowledge and it is valued over any machine made one. | The problem is too complex to solve it by rules. Maintaining the rule system is too costly. |
| Changing the planning / business process is either risky or require too much change. | When even small change in the plan can result in huge improvements. |
| The problem could be described as a control problem. | The problem can be described best by constraints. The problem is difficult to express in rules, too many combinations to express. |
| The cost of not using better solution to be considered. | The cost of building one is higher. |
As a summary, mathematical optimization helps businesses to meet aggressive goals with limited resources when there is no clear way to do it best or successfully.
Even though the mathematical optimization (prescriptive analytics) is the most sophisticated level analytics, every technology should be used for what it does best. We need to consider the cost to make plan with or without the prescriptive analytics. With the mathematical optimization, we may find a better solution, in which we not even knowing there is one by rule-based system. There is an opportunity cost of not using the better solution. However, the cost of building the mathematical optimization application is relatively high. Usually the combination of both technology gives the best/optimal business value.