Emerging Solutions for Operations Research on AWS
AWS Architecture BlogEmerging Solutions for Operations Research on AWSby Randy DeFauw | on03 SEP 2021| inAmazon Braket,Amazon DynamoDB,Amazon OpenSearch Service,Amazon SageMaker,Architecture,AWS Glue,AWS Lambda,Expert (400)|Permalink|ShareSeptember 8, 2021: Amazon Elasticsearch Service has been renamed to Amazon OpenSearch Service.See details.Operations research (OR) uses mathematical and analytical tools to arrive at optimal solutions for complex business problems like workforce scheduling. The mathematical techniques used to solve these problems, such as linear programming and mixed-integer programming, require the use of optimization software (solvers).  There are several popular and powerful solvers available, ranging from commercial options likeIBM CPLEXto open-source packages likeORTools. While these solvers incorporate decades of algorithmic expertise and can solve large and complex problems effectively, they have some scalability limitations.In this post, we’ll describe three alternatives that you can consider for solving OR problems (see Figure 1). None of these are as general purpose as traditional solvers, but they should be on your “emerging technologies” radar.Figure 1. OR optimization optionsThese include:A traditional solver running on a compute platformReinforcement and machine learning (ML) algorithms running onAmazon SageMakerA quantum computing algorithm running onAmazon Braket. Experiments are collected inAmazon DynamoDBand the results are visualized inAmazon Elasticsearch Service.A reference problem and solutionLet’s start with a reference problem and solve it with a traditional solver. We’ll tackle an inventory management issue (see Figure 2). We have a sales depot that supplies products for local sales outlets. For the depot’s Region, there are seven weeks of historical sales data for each product. We also know how much each product costs and for how much it can be sold. Finally, we know the overall weekly capacity of the depot. This depends on logistical constraints like the size of the warehouse and transportation availability. This scenario is loosely based on the Grupo Bimbo retailer’sKaggle competition and dataset.Figure 2. Sales depot inventory management scenarioOur job is to place an inventory order to restock our sales depot each week. We quantify our work through a reward function. We want to maximize our revenue:revenue = (sale price * number of units sold)(Note that the sample dataset does not include cost of goods sold, only sale price.)We use these constraints:total units sold <= depot capacity0 <= quantity sold of any given item <= forecasted demand for that itemThere are many possible solutions to this problem. Using ORTools, we get an average reward (profit) of about $5,700, in about 1,000 simulations.We can make the scenario slightly more realistic by acknowledging that our sales forecasts are not perfect. After we get the solution from the solver, we can penalize the reward (profit) by subtracting the cost of unsold goods. With this approach, we get a reward of about $2,450.Solving OR problems with reinforcement learningAn alternative approach to the traditional solver is reinforcement learning (RL). RL is a field of ML that handles problems where the right answer is not immediately known, like playing a game of chess. RL fits our sales depot scenario, because we don’t know how well we will do untilafterwe place the order and are able to view a week of sales activity.Our sales depot problem resembles aknapsack problem. This is a common OR pattern where we want to fill a container (in this case, our sales depot) with as many items as possible until capacity is reached. Each item has a value (sales price) and a weight (cost). In RL we have to translate this into an observation space, an action space, a state, and a reward (see Figure 3).Theobservation spaceis what our purchasing agent sees. This includes our depot capacity, the sales price, and the forecasted demand. Theaction spaceis what our agent can do. In the simplest case, it’s the number of each item to order for the depot, each week. Thestateis what the agent sees right now, and we model that as the sales results from last week. Finally, therewardfunction is our profit equation.One important distinction between OR solvers and RL is that we can’t easily enforce hard constraints in RL. We can limit the amount of an individual product we purchase each week, but we can’t enforce an overall limit on the number of items purchased. We may exceed the capacity of our depot. The simplest way to handle that is to enforce a penalty. There are more sophisticated techniques available, such as interpreting our action as the percentage of budget to spend on each item. But let’s illustrate the simple case here.Using an RL algorithm from theRay RLLibpackage, our reward was $7,000 on average, including penalties for ordering too much of any given item.Figure 3. Translating OR problem to RLSolving OR problems with machine learningIt’s possible to model a knapsack problem using ML rather than RL in some cases, and there are simplereference implementationsavailable. The design assumes that we know, or can accurately estimate the reward for a given week. With our simple scenario, we can compute the reward using estimates of future sales. We can use this in a custom loss function to train a neural network.Solving OR problems with quantum computingQuantum computers are fundamentally different than the computers most of us use. The appeal of quantum computers is that they can tackle some types of problems much more efficiently than standard computers. Quantum computers can, in theory, solve prime number factoring for decryption in orders of magnitude faster than a standard computer. But they are still in their infancy and limited to the size of problem they can handle, due to hardware limitations.D-Wave Systems, which make some of the types of quantum computers available through Amazon Braket, has a solver calledQBSolv. QBSolv works on a specific type of optimization problem called quadratic unconstrained binary optimization (QUBO). It breaks large problems into smaller pieces that a quantum computer can handle. There is areference patternfor translating a knapsack problem to a QUBO problem.Running the sales depot problem through QBSolv on Amazon Braket and using a subset of the data, I was able to obtain a reward of $900. When I tried to run on the full dataset, I was not able to complete the decomposition step, likely due to a hardware limitation.ConclusionIn this blog post, I review OR problems and traditional OR solvers. I then discussed three alternative approaches, RL, ML, and quantum computing. Each of these alternatives has drawbacks and none is a general-purpose replacement for traditional OR solvers.However, RL and ML are potentially more scalable because you can train those solutions on a cluster of machines, rather than running an OR solver on a single machine. RL agents can also learn from experience, giving them flexibility to handle scenarios that may be difficult to incorporate into an OR solver. Quantum computing solutions are promising but the current state of the art for quantum computers limits their application to small-scale problems at the moment. All of these alternatives can potentially derive a solution more quickly than an OR solver.Further Reading:OR-Gym: A Reinforcement Learning Library for Operations Research ProblemsCombining Machine Learning and Operations Research Methods to Advance the Project Management PracticeQuantum optimization: The future of operations researchTAGS:Reinforcement learningRandy DeFauwI’m an electrical engineer by training who’s been working in technology for 23 years at companies ranging from start-ups to large defense firms. A fascination with distributed consensus systems led me into the Big Data space, where I discovered a passion for analytics and machine learning. I started using AWS in my Hadoop days, where I saw how easy it was to set up large complex infrastructure, and then realized that the cloud solved some of the challenges I saw with Hadoop. I picked up an MBA so I could learn how business leaders think and talk, and found that the ‘soft skill’ classes were some of the most interesting ones I took. Lately I’ve been dabbling with reinforcement learning as a way to tackle optimization problems, and re-reading Martin Kleppmann’s book on data intensive design.
September 8, 2021: Amazon Elasticsearch Service has been renamed to Amazon OpenSearch Service. See details. Operations research (OR) uses mathematical and analytical tools to arrive at optimal solutions for complex business problems like workforce scheduling. The mathematical techniques used to solve these problems, such as linear programming and mixed-integer programming, require the use of optimization […]
Randy DeFauw
Amazon Braket Amazon DynamoDB Amazon OpenSearch Service Amazon SageMaker Architecture AWS Glue AWS Lambda Expert (400)