Information relaxations and duality in stochastic dynamic programs

We describe a general technique for determining upper bounds on maximal values (or lower bounds on minimal costs) in stochastic dynamic programs. In this approach, we relax the nonanticipativity constraints that require decisions to depend only on the information available at the time a decision is made and impose a "penalty" that punishes violations of nonanticipativity. In applications, the hope is that this relaxed version of the problem will be simpler to solve than the original dynamic program. The upper bounds provided by this dual approach complement lower bounds on values that may be found by simulating with heuristic policies. We describe the theory underlying this dual approach and establish weak duality, strong duality, and complementary slackness results that are analogous to the duality results of linear programming. We also study properties of good penalties. Finally, we demonstrate the use of this dual approach in an adaptive inventory control problem with an unknown and changing demand distribution and in valuing options with stochastic volatilities and interest rates. These are complex problems of significant practical interest that are quite difficult to solve to optimality. In these examples, our dual approach requires relatively little additional computation and leads to tight bounds on the optimal values. © 2010 INFORMS.

Programming stress-induced altruistic death in engineered bacteria.

Programmed death is often associated with a bacterial stress response. This behavior appears paradoxical, as it offers no benefit to the individual. This paradox can be explained if the death is 'altruistic': the killing of some cells can benefit the survivors through release of 'public goods'. However, the conditions where bacterial programmed death becomes advantageous have not been unambiguously demonstrated experimentally. Here, we determined such conditions by engineering tunable, stress-induced altruistic death in the bacterium Escherichia coli. Using a mathematical model, we predicted the existence of an optimal programmed death rate that maximizes population growth under stress. We further predicted that altruistic death could generate the 'Eagle effect', a counter-intuitive phenomenon where bacteria appear to grow better when treated with higher antibiotic concentrations. In support of these modeling insights, we experimentally demonstrated both the optimality in programmed death rate and the Eagle effect using our engineered system. Our findings fill a critical conceptual gap in the analysis of the evolution of bacterial programmed death, and have implications for a design of antibiotic treatment.

Scheduling Optimization with LDA and Greedy Algorithm

Scheduling optimization is concerned with the optimal allocation of events to time slots. In this paper, we look at one particular example of scheduling problems - the 2015 Joint Statistical Meetings. We want to assign each session among similar topics to time slots to reduce scheduling conflicts. Chapter 1 briefly talks about the motivation for this example as well as the constraints and the optimality criterion. Chapter 2 proposes use of Latent Dirichlet Allocation (LDA) to identify the topic proportions in each session and talks about the fitting of the model. Chapter 3 translates these ideas into a mathematical formulation and introduces a Greedy Algorithm to minimize conflicts. Chapter 4 demonstrates the improvement of the scheduling with this method.