UNIVERSITY PARK, Pa. — Computer simulations help global companies optimize systems and processes across varying industries and disciplines. Major companies in America have been doing it for years: General Motors uses simulations to test their vehicle trim mix of new products before releasing to the market; Amazon uses simulations to evaluate dynamic purchasing, order fulfillment and warehouse capacity management policies; and Uber uses simulations to decide on pricing policies for Uberpool.
Companies need to make informed decisions within a timely manner, but their decision-making problems are increasingly complex and tricky to solve. Companies may take shortcuts to try to solve a problem quickly, but it doesn’t always guarantee that the given answer is the best. So, what can individuals and companies do to ensure they make sound decisions within deadline constraints?
The National Science Foundation’s Division of Mathematical Sciences has awarded principal investigator Eunhye Song, Harold and Inge Marcus Early Career Assistant Professor of Industrial and Manufacturing Engineering at Penn State, $140,000 to push the frontier of large-scale discrete simulation optimization. Song’s goal is to create a new algorithm that is computationally efficient while simultaneously providing a statistical optimality guarantee.
A set of decision variables is said to be discrete if their values are countable, such as the number of kittens in a litter. There can’t be fractions of a kitten, so this means that they are counted as whole numbers, or integers. Song plans to create an algorithm for problems with discrete decision variables to find the optimal solution, the best possible answer among the possible solutions.
“At the highest level, this is a project to solve a decision-making problem within a system,” Song said. “Oftentimes, simulation optimization isn’t very efficient for large-scale, high-dimensional questions with integer solutions. Our goal is to make an improved algorithm to save time, money and resources.”
Song said an online retailer’s warehouse staffing decisions are examples of large-scale problems with discrete solutions that may benefit from simulation optimization.
Because of the high volume of orders a warehouse receives, varying numbers of staff members need to be allocated to different departments. Managers must decide how many staff members should be assigned to each department to maximize performance.
“Let’s say there are 20 departments and you need to choose from employing one to 10 in each department,” Song said. “This is essentially choosing from 10 levels for 20 decisions. This number is more than a thousand times the age of the Earth in seconds. This is an example of a large-scale problem and you can’t possibly simulate every single solution.”
Song states that to solve a problem like this, the algorithm should be able to provide a solution that has the best possible outcome within a deadline. Her approach aims to provide an estimate of the optimality gap of the selected solution to detect if the solution is meeting the defined goal. The optimality gap is the difference between the selected solution and the optimal solution.
“In a realistic setting, decision-makers tend to have a small optimality gap that they care about,” said Song. “For example, the manager may not care that the cost difference between solutions is less than $100 a month because that still fits within their goal. This means that we can stop the algorithm before it finds the optimal solution if we provide them with something that has an optimality gap below $100.”
In order to find integer solutions that are likely to include the optimum, Song will employ a multi-resolution algorithm. Song compares this approach to zooming in on Google Maps.
“I like to think of this as layers of grids,” said Song. “The globe represents the set of entire possible solutions. To find a near-optimal solution faster, we aim to find the most promising area on the grid and ‘zoom in’ to it. By further zooming in, we have a more detailed grid of solutions within which we focus our search for the optimal solution; this is how we make the algorithm more efficient. Without this, it’s like looking at millions of cities on Google Maps at the same time to pick the best one. That would be a very hard problem.”
While Song’s work is theoretical, the study has real-world implications.
“Once this project is finished, we plan to make it an open-source package for others to use,” said Song. “This kind of algorithm can be used in military, medical, the sharing economy and anywhere that has large-scale decisions to make involving integer solutions.”
This project, which began in July 2019, will run for three years. Song will complete the study with Xinru Li, an industrial engineering doctoral student at Penn State.
The grant is in partnership with faculty from Northwestern University’s Robert R. McCormick School of Engineering and Applied Science: lead Northwestern investigator Barry Nelson, Walter P. Murphy Professor of Industrial Engineering and Management Science, and co-principal investigator Andreas Waechter, associate professor of industrial engineering and management sciences.