The research objectives of this award are (1) to develop advanced methodologies based on decomposition for the solution of large-scale optimization problems, (2) to integrate these methodologies with current state-of-the-art techniques, and (3) to make these methodologies accessible to users through modeling languages and extensions to the standard APIs (Application Program Interfaces) provided by current state-of-the-art optimization software. Although decomposition techniques have proven very effective in certain applications, these methods have not been adopted in commercial solvers due to lack of a mathematical theory integrating other advanced techniques; difficulties in implementation; challenges associated with automatic detection of model structure; and lack of support in modeling languages for expressing decomposition strategies. This research aims to overcome these challenges and to develop practical methodologies and implementations of advanced methods, along with support for modeling by practitioners.
The impact of this research will be in allowing practitioners to have access to powerful methods of optimizing large-scale systems, whose ever-increasing complexity is being driven in practice by the increased availability of data and storage. Among other things, decomposition methods are the methods of choice for the optimization of large-scale systems consisting of smaller subsystems linked by relatively few system-level constraints. One typical example of such a system is a logistics system consisting of geographically distributed warehouses, each with an associated fleet of delivery vehicles. When the system-level constraints are relaxed, the underlying optimization problem decomposes, leading to more efficient solution methods. Decomposition may provide a practical approach to parallelization and thus a means of capitalizing on the commoditization of multi-core/multi-processor architectures. All methodologies will be implemented in open source and distributed through the COIN-OR open source repository (www.coin-or.org), ensuring wide dissemination.
Optimization is the process of selecting the best alternative for operating a complex system from among what is typically an immense set of possible choices. The "system" can be anything from an airline to a manufacturing facility to an investment portfolio. The optimization process involves determining how to make the many individual decisions required to operate the system in an optimal way. In discrete optimization, some of the individual decisions to be made are "discrete," which means that we must choose from a small set of mutually exclusive alternatives. In the simplest case, the choices are either "yes or "no", e.g., should we build a warehouse in Poughkeepsie? Although we may only have a few options for each individual decision, discrete optimization problems tend to be very difficult when accounting for all possible combinations of all decisions. State-of-the-art solution methods still involve some amount of brute-force enumeration. A common feature of many complex systems is that they consist of a number of smaller subsystems, each with their own individual operational constraints. These subsystems are then linked by global constraints on shared resources. For example, a third-party logistics provider may operate many warehouses for which there are independent operational decision to be made on a daily basis, such as how to deliver the goods already present in the warehouse. At a global level, the decisions that link the warehouses are those such as through which warehouse to route inventory in the first place. One approach that has proven successful for solving large-scale optimization problems with structure such as that described above is known as decomposition. Decomposition-based algorithms attempt to exploit the structure of these large-scale models by using sophisticated methods that iterate between optimization of the subsystems and a sort of reconciliation step in which imputed costs that account for violations of the global constraints are imposed as a form of coordination. This drives the solution closer to both feasibility and optimality. When combined with some amount of enumeration, these methods are sometimes vastly more efficient than traditional methods. Despite the proven effectiveness of decomposition-based methods in many important applications, the methodology is challenging to adopt in practice because of the difficulty of implementation, which has traditionally been a tedious and costly process involving the development of custom software and requiring human expertise in multiple domains. The end goal of this project was both to address the challenges that have prevented this methodology from being put into the hands of practitioners, as well as to advance the state of the art with respect to the underlying theory. Achieving the goal involved automating the steps that are usually must be painstakingly undertaken by human experts: determining how to decompose the system into subsystems and then transforming the model and manually applying the decomposition-based methodology. Decomposition of a complex system can be done either by using automated methods to "guess" the structure or by allowing a practitioner to identify it in a natural way when building the original model. The first approach may not always lead to improved solution times overall, since identifying the structure without domain knowledge is a difficult problem in itself. For the second approach, we provide a modeling language similar to those typically used by practitioners in which it is possible to describe the overall system as a linked set of subsystems. This is a natural concept for most practitioners and the language makes it easy to express this structure. We even embedded this modeling language in an Excel plug-in, making it possible to access this very sophisticated modeling environment from a spreadsheet (see attached images). Once the model and the decomposition are determined, a sophisticated solution framework automatically reformulates the model and may apply a number of different decomposition-based methodologies (in parallel) in order to solve the problem and determine the optimal decision. In our experience, the application of decomposition-based methods to real-world systems can be a game-changer. It is not difficult to find real-world systems can be easily optimized with this methodology in a simple spreadsheet, while existing software struggles with the task. From the standpoint of solution speed, another important aspect of this methodology is that it enables the solver to efficiently capitalize on modern computer architectures by using multiple compute cores to optimize different parts of the system in parallel, thereby improving solution times even further. In summary, we have developed a decomposition-based modeling and solution framework that is accessible to non-expert practitioners using tools with which they are already familiar. The modeling is in the widely-used Python programming language and can even be done from within a spreadsheet. We are already seeing evidence that this overall approach will have a high impact in practice. Adoption of the technology by commercial software vendors has already begun, with one vendor already implementing these ideas in a commercial product.
