Optimization problems, Operation Research, Combinatorial Optimization, and software
Recently, I traveled to Florida. When the Airline assigned seats to the passengers, almost all families despite having tickets bought together (and the airline had the information about it) got seats remote from each other ‘because of COVID-related constraints’ as a flight attendant told us. Kids were seated far from their parents. Inside the airplane, people started negotiation with each other about swapping seats. Soon all families were sitting together and all constraints were still satisfied.
Despite the seat assignment is a simple constraint satisfaction problem with a simple optimization function, the airline company could not solve it well, bringing a negative experience to its customers.
Through my experience in the industry, I saw many optimization problems of various types related to operations research, planning, constraint satisfaction.
In 2021 many automobile companies had to stop production and stop their plants due to lack of chips and other supply problems produced by disruption of supply chains in 2020. Ford had to stop 6 factories. As cited by the Washington Post, it’s estimated that the global auto industry will make somewhere between 1.5 million and five million fewer vehicles this year than originally expected. But Toyota has been doing well [1 2] because they built effective optimization solutions to optimize supply chains to provide a continuous supply of necessary parts.
Industrial optimization problems are ubiquitous: Shelf placement in the grocery or apparel or any retail businesses (location and allocation of merchandise). Order and placement of items in warehouses based on demand predictions, item sizes, and volume, storage requirements, and Warehouse location, warehouse layout optimization, and many other warehouse optimizations. Assortment planning, inventory planning (Amazon) in retail and eCommerce. Optimal packaging. Product substitution when a firm sells products to customers and products might be not available (from online grocery to agriculture). Efficient assignment of grocery orders to pickers in online grocery shopping (Google). Optimal routing in Maps applications (finding the best route) for personal and business delivery such as Amazon’s delivery of packages to a doorstep (Amazon) or Instacart’s delivery of groceries. Fleet management from cars to drones. Supply chain optimization (see the example with Toyota). Optimal assignment of grocery deliveries to cars in grocery delivery businesses. Optimal routing and task assignment inside the supermarket to workers in grocery delivery. Placement of data and computations in data centers. Hardware load balancing (see, for example, cache-aware load balancing in Google with double-digit percentage improvement in throughput of google search backend), virtual machine assignment to maximize availability, and minimize hardware utilization. In-Data center scheduling to minimize energy consumption providing required availability for various computational tasks, data center capacity planning (Microsoft) to provide the required quality of service and availability with minimal costs, energy-efficient cloud operations, or other types of dynamic resource allocation of the cloud resources (Microsoft). Routing internet traffic and constructing optimal networks (Google). Corporate structure optimization for multi-national companies. The food service operations (catering, vending machines, repairs,)where optimization reduced fleet size two wold without loss of quality of the food service (Microsoft + Compass Group, one of the largest food delivery services in the world). Planning the number of shoppers in store per hour in an instant grocery delivery business to minimize lost deliveries and shopper idleness (Instacart). Freight pricing @ Uber. Capacity planning for transportation hubs. New store location (Starbucks)for other chains. Various optimization problems for a lifetime, energy consumption, number of sensors, costs in Sensor Networks (I attended a summer school on Sensor Networks in Lipary in 2005. The half of the lectures were about optimization algorithms). Pricing and revenue optimization at Amazon, Uber, Disney (the author of the book is a director in amazon). Inventory optimization. Advertisement campaigns, optimizing ads budgets by various parameters: from the number of visitors to the number of catalogs items visited, the number of catalog sections, diversity of the audience, ad delivery planning. Planning and traffic allocation for online controlled experiments. Deployment of surveillance CCTV cameras, wifi spots, IoT devices, where optimization leads to very substantial hardware, deployment, and maintenance costs. Price assignments for products. Disaster response management (Governments). Optimal pricing, scheduling (Uber)for ride-sharing businesses such as Uber. Tons of other problems where optimization brings a big impact to business and customers. I saw multi-million $ optimization problems in every industry I worked in.
Intel saved 25 billion since 2009 applying optimization methods. NBC increased revenues by 200 million applying operation research. American airlines generated 1.4 billion in incremental revenues. HP used operation research for product portfolio optimization yielding 500 million of incremental profits in three year period. Proctor and Gamble have been applying Operational Research, 67 million annually by selecting the best source, lashed the order-and-delivery cycle for store displays from 20 weeks to just eight, billion was saved through plant management. Using OR to make better scheduling of trains by Dutch Railways let to avoid 10B expenses and created an additional 60 million dollars profit in 2007.
OR has a big impact on Google. See information about Google organization structure (and here ) to enable Operation Research and optimization impact at that scale.
But the problem is :
How to scale Operation Research, Combinatorial Optimization so it can be applied efficiently by many software engineers without specialized OR degrees to many different business use cases, for many different lines of business, to build efficient, reliable, scalable, evolvable, high load, price-efficient, evolvable systems
Beyond financials: US Army estimates 4500 avoided casualties by reducing helicopter and ground convoy movements through optimization, CDC project on US Epidemics estimates 6000 lives per year saved due to applications of Operation Research.
Personal optimization problems such as planning. Scheduling meetings under many constraints from schedulers and all other participants' calendars. Outlook added a very basic scheduling assistant just recently. Very simple scheduling features in the calendar, basically, simple optimization features added to the online calendar, made a company with 3 billion evaluation, — Calendly (despite there are plenty of online calendars such as Google’s one)
Despite the prominence and impact of optimization problems, there are very few good libraries to be used on an industrial scale. There are a lot of libraries produced as research libraries for various tasks in planning (see ICAPS competition), space placement optimization, etc, but most of them are not scalable, have no support, and little known outside of the community of Ph.D. researchers in this particular domain.
Perhaps, one of the reasons the optimization did not go much of open-source software supports the way deep learning got it recently because it did not get so much media attention. Because of stronger impact on the public imagination, Computer Vision and Natural Language processing get more attention from popular media outlets than programs saving dozens of millions of dollars by saving hardware and maintenance costs through optimization such as by the better placing of observational video cameras in shops and other IoT placement optimization, or other big savings from solving optimization problems.
So many companies solve business problems reducable to the optimization problems, operation research problems, constraint satisfaction, planning, using low-level optimization libraries (linear algebra (LAPACK family), convex optimization (CVXPY, POGS), Semidefinite programming (SDPA)), Gurobi (fast, commercial solver for LP, QP, QCP, MIQCP)since there is no software support for higher-level business-oriented problems, and there is no standard solution for solving optimization problems from major cloud providers
Someone replying to the first draft of this article mentioned that in his company a team worked on applying bayesian optimization and they used GPyOpt. There were very significant delays and costs with delivery due to bugs in GPyOpt and no support (recently it was announced end-of-life GPyOpt because the core team developing it was hired by Amazon).
There are plenty of very narrow use optimization packages for different narrow use cases (think about different libraries for recognizing cats and dogs based on deep learning CV). Typically they are very expensive, not evolvable, not open, not extendable to very large data sets, not possible to run under strict low latency, high throughput requirements needed for some business tasks. For example, fleet management software such as Bringg, Verizon Connect, Teletrac Navman, and Fleetio contain optimization functions for vehicle routing problems, but fleet management businesses have many other optimization problems. Or applications such as OptimoRoute, RoutManager from WorkWave, Verizon’s MapQuest, Rout4me, Badger Maps, there are plenty of companies providing services in this segment of optimization which shows the value of the problem. Even for vehicle routing, the commercial software is hard to adopt once the task is different from the standard. From points of view such as operational, quality of service, availability, expense/costs, integration with other business systems, support, it’s frequently better to have an optimization team having the expertise to solve many different problems across different lines of business, and a technology stack solving different problems, rather than having multiple teams in every line of business or use cases, and different software stacks for different use cases. Almost every company operating at scale has to write its own optimization software from scratch.
There are some startups that attack this problem in some domains such as nextmv which recently raised 8M for its optimization platform. Interesting that investors are from Github, Stripe, and Seamless, companies that must be heavily dependent on optimization and they must know the value of it. Both founders are from GrubHub for which optimization is the core of successful business operations. The size of the food delivery market which is heavily dependent on optimization to be profitable is 200 billion dollars. From TechCrunch: “On the heels of this latest round, nextmv is working to simplify its product. The company has launched nextmv Cloud to allow developers, not just operations researchers, to use its software. Nextmv Cloud has quick-start models in the routing and delivery space to allow developers to automate decision-making, with plans to launch into new verticals in the coming months. Before nextmv, it could take an entire team of operations researchers to optimize decision-making models and simulate test environments. When nextmv launched, a team still needed to have at least one operations researcher to use the product. Now, developers can hop on the platform and get started.” Certainly, a set in the right direction to scale operation research
I think optimization platforms and open source software solutions for running optimization at scale will be as big and popular business as AI platforms now where dozens of startups and big cloud companies offer various end-to-end and partial software solutions and services.
Large companies write their own solutions from scratch the same way they were writing machine learning libraries before TensorFlow, Keras, PyTorch, NLP before: Transformers, Spacy, etc. Smaller companies buy Gurobi, CPlex, use SCIP Optimization Suite, and others. There are great tools such as tools within COIN-OR initiative. But to build tools solving business use cases in production, both small and large need to build from scratch or on the top of low-level libraries. It requires OR and optimization expertise. It reduces the number of business use cases that can be solved, increases development and operational costs, times, budgets, in many cases decrease quality. The situation can not be compared to the software support of deep learning with the abundance of low-level and high-level libraries (TensorFlow, TensorFlow Serving, PyTorch, Transformers, all sort of libraries to support training, deployment, inference in various setting, model monitoring, feature stores, online controlled experiments) for every aspect of training, inference, deployment, monitoring, and libraries for particular applications (computer vision, natural language processing, time series, etc) and support libraries (annotation, data and model versioning, monitoring etc). For example, if one writes a natural language processing algorithm to be used to extract certain information from incoming documents, there is a whole ecosystem of tools to let you build continuous retraining of this model, deployment of this model, run A/B experiments of one model vs another, monitor performance of the model. In case, if one builds an algorithm to find the best route for a vehicle in the city, or find the best assignment of grocery orders to vehicles for faster and cheaper delivery, one has to build such an ecosystem. Google published Google OR tools (see information about the prominence of Operation Research in Google above, most probably OR tools is 1/1000th of what Google developed inside) which is a good toolset and the step in the right direction, but it’s limited in functionality
One of future big impact software development can be the development of well supported high-quality software for solving various optimization problems from planning to routing to space placement etc
In many practical applications, the environment is so complex that it is infeasible to lay a comprehensive theoretical model and use classical algorithmic theory and mathematical optimization. It is necessary as well as beneficial to take a robust approach: apply an optimization method that learns as one goes along, learning from experience as more aspects of the problem are observed. This view of optimization as a process has become prominent in varied fields and led to some spectacular success in modeling and systems that are now part of our daily lives.
extending this view
We need software systems helping to build processes of continuous improvement of businesses and customer experience using optimization, operation research: including software quality monitoring of such systems, testing, optimal performance of optimization models for various serving cases, continuous evaluation and monitoring of optimization models, and their outcomes to end-to-end accuracy, the performance and costs of customer-facing and business software systems, measurement of business impact, debugging and interpretation.
There are multiple different types of optimization tasks from business and software requirements points of view. A) Tasks such as placement of a new store or a new datastore that require optimization are computed relatively rarely and there are no strict latency and throughput requirements, but there is a strong requirement in finding the most optimal solution. B) Tasks such as finding the best route for the vehicle and other similar consumer-facing tasks may be called hundreds of millions of times per day (iOS and Android, Google maps as an example) with strict latency and throughput requirements and may tolerate some approximation to the most optimal solution. There is a wide specter of optimization tasks from A to B. The overall industry does quite well with A types of tasks, but nevertheless having good business-focused packages may significantly help to adopt such tasks across multiple lines of business and increase their impact on business significantly by wider adoption. The B) type of tasks are very little addressed by the current software but the majority of businesses mentioned above are based on them, every company builds optimization stacks from zero for B) tasks and new software can be a huge differentiator there.
I exclude from this essay a big topic of optimization methods for machine learning [1, 2 as surveys, plenty of recent papers] as there is a more narrow and specialized community, there is strong software support but anyway, many ML teams write optimization methods from scratch
PS after I wrote this story, IBM bought a resource optimization company for datacenters Turbonomic for 1.5B
