A Metastrategy for Large-Scale Resource Management Based on Informational Decomposition

This paper addresses the solution of large, complex resource allocation problems, examples of which include large freight transportation companies and supply chain management. Some instances of these problems involve millions of constraints and tens of millions of variables. Classical formulations focus on modeling the physical problem alone. In this paper, we focus on modeling the organization of information and decisions, producing a natural decomposition based on how decisions are actually made. Restricting the size of a subproblem to the sizes of problems actually solved by real decision makers, we avoid the computational demands posed by large problems. The algorithmic challenge is producing high quality solutions that reflect the interaction between subproblems. Linear approximations have been a widely used tool for decomposition, but these can produce unstable solutions of only moderate quality. We introduce the concept of using nonlinear approximations, which creates special technical problems but also produces solutions of very high quality. The strategy is simulated on two problem classes (fleet management and supply chains) and compared against standard modeling strategies. Synchronous and asynchronous strategies are also compared.