Integrating Optimization and Machine Learning: A Conversation with Irv Lustig and Paul Maiste

Thursday, July 13, 2023

Irv was interviewed by Lityx CEO Paul Maiste for the Data Stories podcast. Following are lightly edited excerpts. Listen to the full conversation here.

Paul Maiste: We talk a lot in this podcast about data, analytics, and machine learning, and how they help businesses solve challenges and grow. What is it about a business problem that makes it uniquely an operations research problem or an optimization problem?

Irv Lustig: It’s a really good question. Optimization is one big field of OR, which also includes simulation techniques, decision analysis, and other probabilistic techniques. We like to think of optimization as finding the best way to allocate limited resources. The applications are far and wide across many industries. For example, if you are a manufacturer and you've got to decide where to build a plant, you’re limited in your budget—you can't build a lot of plants, and you want to be able to serve your different customers in different places. You're making a big, capital‑oriented type of decision. The airlines use optimization every day to determine which planes go on which flights, and to route and schedule their staff. If you have an investment portfolio like a 401(k), the professional helping you manage your money is often using asset allocation tools that leverage optimization to decide how to allocate different amounts of your portfolio to maximize return while limiting your risk exposure based upon your risk tolerance. Some machine learning applications, for example in marketing, might train a data set to determine which customers to make offers to, but they are not necessarily making trade‑offs so that one set of choices is better than another. Optimization usually has the concept of an objective function where you're measuring a key performance indicator (KPI) so that you can determine when one set of decisions is better than another set of decisions.

Paul: That’s helpful. I usually like to think of it as constraints that sit on top of the problem—that’s where the trade‑offs come into play.

Irv: It’s the limited resources. Another way to say it—and I should credit a former colleague at ILOG for this concept—is the “TLC + Data” approach. This means having a Target, something you’re trying to optimize, and having Limits on the Choices you can make, and you have Data that's going to help you make that decision.

Paul: With our clients, the problems we solve always include data and they almost always include machine learning and making predictions, but they don't always include the optimization component, because we tend not to necessarily dive into problems that have that limited resources and constrained overlay. To put a little meat on the bones, can you walk through a problem that you've helped a client with recently, one that perhaps has integrated machine learning predictions as a part of the data set, and involves something on the optimization side?

Irv: We supported a project at the US Census Bureau for the 2020 census. The decennial census was historically conducted in two phases: mailers were sent asking people to fill out a survey, which was completed by 60 to 65 percent of households; then around 500,000 temporary enumerators were hired to knock on the doors of the people who had not completed the survey. These enumerators were typically given their work by a supervisor at a McDonald's or a Starbucks: they would be given a set of files to work, and then they would go out and determine when they wanted to work, and the route they would take. Enumerators are paid by both the hour and for mileage. An innovative team at the Census Bureau said, “Let’s change the process and use technology. We’ll give all the enumerators a smartphone, tell them every day which households to visit, route them efficiently to reduce miles, and send them to homes at times when people are more likely to respond.” As a result of the new process, the productivity of the enumerators, in terms of successful visits, went up by almost a factor of two, allowing the Census Bureau to use only 300,000 enumerators and far fewer field offices, resulting in a multibillion-dollar cost reduction. There was a machine learning component for predictions of how likely household members would be home at a specific hour of the day, but then the pandemic hit and essentially everybody was home. Census Bureau leaders later said that when the pandemic hit, they could change things and carry through because optimization was a driving factor. We were honored to be part of that team that did that great work.

Paul: It sounds like, in that case, there are multiple objective functions, from minimizing time, maximizing response. A lot of interplay. Part of the trade‑offs that you were mentioning.

Irv: Exactly. They had to assign enumerators to groups of households and then, within those households, route them while minimizing the time and mileage, and maximizing, if you will, the chance of a good response. Regarding applications involving machine learning and optimization, we did work for a trucking company. In long‑haul trucking, when you pick up a load in one place, say Newark, and you drive it to Chicago, you now have a driver and a tractor sitting in Chicago, and the driver wants to get home. The question is do you have a load in Chicago that's going to go to Newark? Maybe the driver is going to need to go to Texas first and then go to Newark. The trucking company has to make a decision that when it receives a tender —an offer for a load—should it take it and at what price? We built machine learning models to predict the value of repositioning this driver if he were to accept this load. The worst thing that can happen is he has to drive home empty, which is not a revenue‑generating move if you were to drive from Chicago to Newark. We had a number of different machine learning models that then were input into an optimization model that would understand the network value of the repositioning. It’s not just about one driver, it's about lots and lots of drivers and lots of loads all happening at the same time over a long time-horizon. We needed to predict and say, "What do we believe is going to be the demand coming from one origin to another destination in the future?" For example, a cross‑country load will take a driver four or five days to drive across the country. We needed to know four or five days from now whether there will be something for him to take at his destination or near his destination, because maybe he just has to drive a couple hundred miles from there to pick up his next load. We had a big diagram of how these models were feeding each other—some machine learning models feeding others, and then a number of them feeding an optimization model to help make that decision.

Paul: It's interesting because it's not necessarily the case that you know if there will be an additional load to pick up, but it comes down to the likelihood or the probabilities based on the model. Of course, that feeds into the trade‑offs in the calculations. It’s interesting that both of your examples are very tactical and dynamic. Like in the census—one day the enumerators are out there. They may not hit as many of the households as they planned, or someone gets sick, and the environment changes. In the trucking example, a new offer comes in for a load that's in a place you weren't prepared for. Very dynamic and shifting. You got to make split‑second decisions. I think classically, people will often think of the optimization space in these problems as being a bit more on the planning and strategic side of things. You make a decision once, and you don't have to revisit the problem or rerun the optimization for another year or a couple of years, but seems like it's been moving a lot more towards that tactical side as well.

Irv: Absolutely. Now we're starting to see applications where people are making decisions every single day, sometimes even more quickly. We worked with an e‑commerce retailer that runs a 24-by-7 operation, and every five minutes they are deciding which of their 15 warehouses is going to ship orders to the customers. From a cost perspective, you have to look at where your inventory is. The company tries to make sure that all the warehouses have the same inventory, but sometimes people order a specialty product. Typically, it’s cheaper to ship from the closest warehouse, but what if it doesn't have the products you want? Or say you've ordered five products, and the closest warehouse doesn't have one, but the company wants to avoid splitting shipments. If the customer lives in Miami, they could ship from Seattle because it has all five products, but they can trade that off by shipping three from North Carolina and two from Texas because the split shipment reduces overall costs. Every five minutes, a batch of 500 orders is allocated. Another trade‑off is considered: they have to balance the workload because there are workers at distribution centers making the boxes, putting products in the boxes, and shipping them out. In the morning on the East Coast, most orders originate on the East Coast and the closest warehouses are on the East Coast—but the West Coast warehouses have no orders to work on. Similarly, late in the day on the West Coast they are really busy, but you have to keep the East Coast facilities busy. Optimization is taking advantage of all these different trade‑offs and being used in these very operational areas, making decisions.

Paul: From my experience with clients and solving some complex optimization problems, mostly in the marketing space, the trade‑offs can lead to what a client might see as a counterintuitive result or decision.

Irv: Yes, we often work with clients to make sure that they can get an understanding. One way is to say, "Well, if you feel that there's a better answer, we can plug it in and show you its key performance indicators, KPIs." As you were alluding, there are often competing objectives. In a project when we present a model’s proposed schedule or allocation, the client executive might say, “I would have done it differently.” We evaluate and ask why, and we often uncover a different KPI or a new constraint we weren’t initially informed of.

Paul: Very interesting, Irv. We've covered a lot of ground here. Any last thoughts?

Irv: I've spent much of my career trying to get more people to recognize the applications of optimization. It is everywhere! It's the secret sauce that helps a lot of companies make better decisions, reduce costs, improve revenues and profits, and make things generally much more efficient.

Paul: Thanks for your time!