A nonlinear approximation method for solving stochastic, dynamic resource allocation problems

In this dissertation, we introduce a technique called Concave, Adaptive Value Estimation (CAVE) to approximate recourse functions found in stochastic programs. CAVE constructs and refines a sequence of concave (or convex) piecewise-linear approximations using sample gradients of the recourse function at different points in the domain. The result is a nonlinear approximation that is more responsive than traditional stochastic quasi-gradient methods and more flexible than analytical techniques. CAVE does not require any particular type of structure to the problem or distribution information regarding the random second-stage variables. Instead, it performs the updates using the dual variable from sequential realizations of the second-stage problem. Experimentally, we demonstrate near-optimal behavior of the CAVE approximation involving three different types of stochastic programs---single point estimation of a function, the newsvendor stochastic inventory problem, and two-stage distribution problems with network recourse.; The bulk of the dissertation considers applying the CAVE algorithm to a stochastic version of a dynamic resource allocation problem. In this setting, reusable, homogeneous resources must be assigned to demands that arise randomly over time. Satisfying a demand generally will change the attributes of a resource. These problems arise in fleet management, personnel training and assignment, and the remnant inventory problem. We start with a problem in which we assume single period travel times for the resources, and then extend the approach to the more general multiperiod travel time case. In either case, we formulate the problem as a multistage dynamic program, and suggest an approximation strategy that naturally yields integer solutions, and based on experimental evidence, provides near-optimal results.