Distributed Optimization

In many cases, there are multiple, possibly competing, objectives that need to be optimized. While it is sometimes possible to finesse this problem using clever approaches and algorithms that allow progress on more than one objective simultaneously, sometimes each solution to one problem creates an entirely different search space for the other. For example, when managing a fleet of vehicles and ports, the route and departure time for one vehicle may affect when warehouse space is available at its destination, how much cargo is available to be picked up at en route points, etc.

In such cases, the complexity of the multi-objective optimization problem may be too high to handle in the time available for planning. One solution OTS has pioneered involves decomposing the multiple optimization problems in such a way that work can be distributed over a 'cloud' of computers, with partial results from different stages of the search being used to dynamically reshape the distributed computation.

This approach has been successfully aplied in the DWARP distributed fleet management prototype that OTS developed for the USAF's Air Force Research Laboratory. DWARP searches in a two-tiered fashion, partitioning the search space into problems that involve only one aircraft and those that require information about several planes to solve. DWARP breaks the problem down by distinguishing between searching for the optimal distribution of resources across multiple missions and searching for the optimal individual mission routing given these constraints.

Individual mission optimization is distributed across the cloud, while the overarching fleet-wide problem is handled centrally. Good overal solutions are found rapidly based on constraints inferred from partial information obtained from the distributed search nodes; these solutions both influence the specific optimization subproblems shipped to the cloud and are refined by new information that becomes available as the distributed search progresses.