Mathematical Optimization in our Daily Lives
In our daily lives, we benefit from the application of Mathematical Optimization algorithms. They are used, for example, by GPS systems, by shipping companies delivering packages to our homes, by financial companies, airline reservations systems, etc. Mathematical Optimization, also known as Mathematical Programming, Operations Research, or simply Optimization, is a discipline that solves a great variety of applied problems in diverse areas: medicine, manufacturing, transportation, supply chain, finance, government, physics, economics, artificial intelligence, etc.
In this article, I provide several examples that will help people identify situations where Optimization can be applied, while avoiding mathematical jargon as much as possible. As you read, think about the implications of combining these algorithms and the vast computational power currently available.
Gartner Analytics Maturity Model proposes four phases: Descriptive (What Happened?), Diagnostic (Why did it happen?), Predictive (What will happen?) and Prescriptive (How can we make it happen). Optimization is at the heart of the Prescriptive stage indicating how to use resources efficiently to achieve the best possible goal under a series of conditions.
In an optimization model, the goal can be to minimize cost in a production system (i.e. oil refinery) where the resources are labor, raw materials, etc. and production targets must be achieved. In a hospital, the goal can be to minimize the wait time for patients in the emergency room before they are seen by a doctor where the resources are the doctors, the nurses, the rooms, the equipment, etc. In Marketing, the goal can be to maximize the profit obtained by targeting the right customers under budget and operational conditions. In a Humanitarian Operation the goal would be to reach as many affected people as quickly as possible to distribute resources water, food, and medical services by designing optimal routes.
More properly (and succinctly), one can say that an optimization problem searches the decision variables which maximize or minimize an objective function under several conditions or constraints. That definition hints that optimization problems are expressed as mathematical models and to solve them requires specialized training. In this article, I will provide several examples describing the problem to be solved. For most of these examples, I will identify their decision variables, objective, and constraints and provide a close description of the meaning of the decision variables and the constraints, since providing the exact definition would involve writing the mathematical models.
I selected most of the examples from the Edelman Award and the Wagner Prize competitions. I have enjoyed serving as the Chair for the Wagner competition in 2017 and 2018, and I have participated in the Edelman Award as a judge and coach. I selected those examples to show the variety of areas where Optimization is applied, and because I believe these examples easily illustrate similar situations where analytics and Optimization could be applied again.
The Edelman Award is given to an implementation of mathematical programming and analytics to an important business problem with a big impact. The Wagner Prize emphasizes mathematics applied to real-world problems, supported by clear and intelligible writing, and verifiable practice success. It was extremely difficult for me to select just a few examples, but the Interfaces Journal devotes its January issue to the Edelman entries and the September issue to the Wagner entries. Most of the links provided below correspond to the journal articles, but you can view additional Edelman videos.
Optimization of the Production Planning and Trade of Lily Flowers at Jan de Wit Company
Think of this example as a general production-planning problem. It could refer to other situations such as, producing furniture, textiles, lacteous products, agricultural products, beauty products, etc. These other situations have the same objective, similar constraints and decision variables.
To manage its lily flower business, Jan de Wit Company implemented a decision-support system for the production, planning and trade. In 2001 in its Edelman entry, they reported that between 1999 and 2000, company revenue grew 26 percent, sales increased 14.8 percent for pots of lilies and 29.3 percent for bunches of lilies, costs fell from 87.9 to 84.7 percent of sales, income from operations increased 60 percent, return on owner’s equity went from 15.1 to 22.5 percent, and best quality cut lilies jumped from 11 to 61 percent of the quantities sold. The system also suggested changes in the product mix.
The Linear Programming (LP) goal was to “maximize the farm’s total contribution margin” subject to such constraints as market defined sales limits, market requirements, characteristics of the production cycle duration, technical requirements, bulb inventory, and greenhouse limitations. The main decision variable to be calculated was the number of flower beds in a specific greenhouse, from a specific bulb batch, of a specific variety, for a specific purpose, taking into consideration planting and expected harvesting weeks.
Dell’s Channel Transformation: Leveraging Operations Research to Unleash Potential Across the Value Chain
This example illustrates how integrated the four stages of the Garner Analytics Maturity Model are, and the variety of analytical techniques that were used to improve Dell’s processes. Think on how many other industries could benefit from following similar analytical processes as Dell did.
In 2007, Dell launched several strategic initiatives to drive channel transformation by offering fixed configurations through online channels, retailers, distributors, and other channel partners. In 2014 in its Edelman entry, Dell reported that since 2007, Operations Research (OR) had helped Dell solve complex business problems and had facilitated its growth in the FHC business to $15 billion. Since 2010, these OR solutions had delivered a margin impact of more than $140 million by reducing markdown expenditures, improving online conversion rates, increasing ocean shipments, and enhancing customer satisfaction.
In the next two paragraphs notice the two types of mathematical optimization models that Dell used, as wells as, how a variety of analytical techniques produced inputs for these models.
Dell used a variety of analytical and statistical techniques (e.g., A/B testing, multivariate regression, ANOVA, as inputs for a nonlinear mixed integer program) to improve the design of its website and increase the conversion rate of prospective customers to purchasers, leading to increased revenues and customer satisfaction.
Dell’s analytics team created an initial set of fixed hardware configurations (FHCs) based on techniques such as factor and clustering analysis. These initial configurations were upgraded with additional options and features through a quadratic programming model, which considered both costs and maximizing the anticipated revenue coverage.
Operations Research Advances Cancer Therapeutics (2007 Edelman Winner)
Using mathematical programming approaches, this winning entry presented sophisticated optimization modeling and computational techniques for real-time (intraoperative) treatment of prostate cancer using brachytherapy (the placement of radioactive “seeds” inside a tumor). The resulting system offered significantly safer and more reliable treatment outcomes.
The goal was to “Minimize the deviations of the dose level at a given tumor point from its target bounds” under the following conditions (or constraints): 1) At each voxel, the radiation dosage should be within specified lower and upper limits, and it can’t deviate from the prescribed dosage by more than a given percentage, 2) Dose-volume coverage constraints for the tumor (for example, that at least 95% of the tumor receives the prescription dose), 3) Total number of radioactive seeds to be used, 4) Total number of needles to be used, and 5) Additional technical constraints.
This Mixed Integer Programming Problem had as main decision variables: 1) The location of the radioactive seeds in the tumor and 2) a variable that indicates if the prescribed radiation was achieved at specific sample points (called voxels) in the tumor.
Obviously, this work can be applied to other types of cancers. View the video.
INDEVAL Develops a New Operating and Settlement System Using Operations Research (2010 Edelman Winner)
INDEVAL is the Mexican Central Securities Depository (CSD). A CSD provides the services related to the custody and management of financial securities and their settlement. A settlement occurs when the securities and funds are transferred between the participants of the transaction. In 2010, INDEVAL’s mathematical optimization system, called Dali, reduced the intraday financing costs for market participants by more than USD 150 million annually because of lower daily liquidity requirements of approximately USD 130 billion. Dali made those settlements close to real-time to minimize the difference between the posted price and the actual price in which the financial transactions takes place effectively reducing risk exposure. Lehman Brothers failure can remind us of how important is to reduce this exposure.
Dali’s goal was to “Maximize the number of transactions to settle” while satisfying close to 1,814 security balance constraints (these are related to the number of securities that are in each participant account), and its decision variables were which transactions to settle and their numbers.
This problem is an Integer Problem (IP). However, when cash constraints are removed, its LP formulation is unimodular and it has an optimal solution that is integer. View the video.
There are several similar financial applications, for other countries CSDs and financial brokers. BNY Mellon Optimization Reduces Intraday Credit Risk by $1.4 Trillion describes how the Bank of New York Mellon developed a set of integrated mixed-integer programming models to solve collateral-management challenges involving short-term secured loans. Its objectives were to minimize intraday credit exposure and the liquidity usage of its clients. View the video.
Calibrated Route Finder: Improving the Safety, Environmental Consciousness, and Cost Effectiveness of Truck Routing in Sweden (2016 Wagner Winner)
The goal for the 2016 winner was to find routes for heavy logging trucks in Sweden, that is, “minimum cost” routes that are as close as possible to the “best” routes and satisfy the stakeholders constraints.
Routes for heavy logging trucks start at the supply points in the forests and end at the demand points or mills and consider a myriad of constraints due to the many stakeholders in the Swedish forest industry. Some of these considerations are distances, quality of the roads (hilliness, curvature), routes must not pass closed to specially marked places (cities center, hospitals, kindergartens, etc.). Also, routes must include environment considerations.
Traditionally, Swedish heavy logging trucks preferred to use the “best” routes. However, those routes do not have all the considerations that stakeholders asked to be considered, and this project found “minimum cost” routes that included all those considerations. View the video.
Possible Similar Applications: Routing problems for delivery and pickup. For example, see UPS Optimizes Delivery Routes (2016 Edelman Winner). View the video.
Guns or Butter: Decision Support for Determining the Size and Shape of the South African National Defense Force (1996 Edelman Winner)
In the absence of a conventional military threat and with a limited budget, what should the size and shape of the South African National Defense Force (SANDF)? The goal for this winner was to maximize the defense value or risk reduction under the conditions for a limited budget and specific army tasks characteristics. Each answer of the mathematical model developed included the tasks, warning periods required, military strategies, force design and cost of the SANDF.
This work was commended highly by South African President Nelson Mandela, and the Edelman judges found it to be excellent.
US Environmental Protection Agency: US Environmental Protection Agency Uses Operations Research to Reduce Contamination Risks in Drinking Water
This project competed for the Edelman in 2008. In my opinion, it could be extended to include SAS Event Stream Processing (ESP) that allows you to analyze high-velocity streaming data and take appropriate action instantly.
The US Environmental Protection Agency (EPA) Threat Ensemble Vulnerability Assessment (TEVA-SPOT) Research Program developed contamination warning systems to counter contamination threats against large water-distribution networks throughout the United States that reduce potential public health consequences by thousands of lives and potential economic consequences by billions of dollars.
The goal of the standard TEVA-SPOT optimization model was to minimize the expected impact of the contamination incidents, while considering the overall impact of placing a sensor in a given location and budgets.
This integer program had as decision variables where to locate the sensors in the water-distribution network. View the video.
Non-profit government related projects were the 2017 winners of the Edelman Award and Wagner Prize.
The 2017 Wagner winner was The Inmate Assignment and Scheduling Problem and its Application in the Pennsylvania Department of C... which solves the complex problem of assigning the inmates to correctional institutions (CIs) and of scheduling their rehabilitation treatment programs while considering about 100 additional factors, such as inmate’s criminal history, demographic characteristics, etc. Inmates who receive timely programming of their rehabilitation treatment programs have a better chance of becoming eligible for parole and leaving the correctional institution earlier, reducing unnecessary overcrowding of the CIs.
This is a complex model, and it considers several goals (or objectives). The multi-objective mixed integer linear optimization problem minimizes the penalties of the weighted sum of all the goals. General factors have the highest priority in assigning inmates to CIs. Minimizing the maximum waiting time for each inmate is second in the hierarchy of objectives. Assigning in the range of the minimum and maximum capacity of each facility has the next highest priority. Additionally, to reduce the population of the CIs, program waiting lists have a high priority in the objective function. Assigning inmates to a facility near their home county is less important compared to the other objectives.
There are several decision variables, some of them are to which facility the inmate is assigned, time when his/her rehabilitation program starts, number of inmates assigned to each CI who start their rehabilitation program at time t, maximum waiting time to start program p, etc. The constraints are related to the 100 factors that affect the inmate assignment, for example the capacity of each CI, the factors that apply to each inmate, the courses that are available at any given time, the distance between the home county of each inmate and the CIs. View the video.
The 2017 Edelman winner was the US Federal Communications Commission for its use of Operations Research and incentive auction to relieve the “spectrum crunch”, with their entry: Unlocking the Beachfront: Using O.R. to Repurpose Wireless Spectrum. For me, the importance of this project is summarized in this paragraph from the article How the FCC won the Edelman Award: “… Asked to sum up the monumental project and its financial impact, Hoffman says, “Forget the $20 billion dollars, forget the $7 billion for deficit reduction. This relates to the future ability of the United States to have the wireless spectrum it needs for 5G and the Internet of Things. This is the wireless economy. It’s the app economy, and if the FCC didn’t do this, we couldn’t move forward.” Watch the presentation.
Conclusion
Every day we benefit from the applications of mathematical optimization, from its well-known use in production systems to its role in having wireless spectrum for 5G and the Internet of Things and its use in Artificial Intelligence. I invite you to see many more inspiring applications at the Edelman Award and Wagner Prize web pages.
