Small CISE-ANR: A Local Optima Tunneling Engine for Scalable Graybox Optimization

Many modern real-world manufacturing and scheduling problems need to satisfy multiple goals. For example, in automotive design we would like to increase safety and fuel efficiency, while at the same time decreasing cost and harmful emissions. However, a good solution must balance these conflicting goals.

The need to balance conflicting goals is common across virtually all industrial and engineering problems. Traditional optimization tools are designed to achieve the best possible outcome for one goal, but do not work well when solving for multiple goals. Modern multiobjective methods are increasingly being used by industry but are not as well understood as single objective methods.

Part of the problem is that there is not a single best solution, but rather there will be a family of solutions representing the possible trade-off between different goals. In shipping and logistics, we want to ensure on-time arrival of goods, while also minimizing shipping costs and the risk of shipping disruptions. But, if one solution reduces average shipping cost, while another solution reduces the risk of disruption, which is the right answer?

Multiobjective tools do not provide a best solution, but instead give a human decision maker a family of options to select from, which highlights the trade-offs between the different conflicting goals.

This project will improve multiobjective optimization tools. The family of best solutions under multiobjective optimization form what is known as a Pareto Front. Given two solutions that lie on the Pareto Front, how do we efficiently find other solutions that also lie on the Pareto Front?

Most current multiobjective optimization tools are highly stochastic in nature. This project exploits new mathematical methods that have the potential to deterministically explore the Pareto Front. These new methods take two (locally optimal) solutions and then remove all nonlinear interactions in each evaluation function that are not locally relevant to these two solutions.

The nonlinearity of the evaluation function in this lower dimensional space is guaranteed to be less than (if not equal to) the nonlinearity of the full space. Simplifying the evaluation function in the lower dimensional space will often decompose the full evaluation function, causing it to become locally linearly separable in the reduced space. When this occurs, we can provably generate the best of exponentially many piecewise locally optimal solutions in linear time.

We have already shown this method works extremely well on classic NP-Hard problems. If we take two solutions on the Pareto Front, we can also define a lower dimensional space between pairs of solutions. Given two solutions, this gives us a highly efficient deterministic method to search for other solutions that potentially lie along the Pareto Front.

Our work will also look at hardware and software innovations as well as parallel implementations to support our new multiobjective optimization tool. This project is a collaboration between a French and US Investigator under the CISE-ANR funding agreement.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.