On linear stochastic differential games with average cost criterions

In this paper, we consider scalar linear stochastic differential games with average cost criterions. We solve the dynamic programming equations for these games and give the synthesis of saddle-point and Nash equilibrium solutions.The authors wish to thank A. Ichikawa for providing the initial impetus and helpful advice.     

Stochastic vendor selection problem: chance-constrained model and genetic algorithms

We study a vendor selection problem in which the buyer allocates an order quantity for an item among a set of suppliers such that the required aggregate quality, service, and lead time requirements are achieved at minimum cost. Some or all of these characteristics can be stochastic and hence, we treat the aggregate quality and service as uncertain. We develop a class of special chance-constrained programming models and a genetic algorithm is designed for the vendor selection problem. The solution procedure is tested on randomly generated problems and our computational experience is reported. The results demonstrate that the suggested approach could provide managers a promising way for studying the stochastic vendor selection problem. The authors would like to thank the referees for providing constructive comments that led to an improved version of the paper. Also, this research was partially supported by grants from National Natural Science Foundation (60776825)—China, 863 Programs (2007AA11Z208)—China, Doctorate Foundation (20040004012)—China, Villanova University Research Sabbatical Fall 2006, and the National Science Foundation (0332490)—USA.     

Primal-Dual Simplex Method for Multiobjective Linear Programming

We develop a primal-dual simplex algorithm for multicriteria linear programming. It is based on the scalarization theorem of Pareto optimal solutions of multicriteria linear programs and the single objective primal-dual simplex algorithm. We illustrate the algorithm by an example, present some numerical results, give some further details on special cases and point out future research. The paper was written during a visit of the first author to the University of Sevilla financed by a grant of the Andalusian Consejería de Educación. The research of the first author was partially supported by University of Auckland Grant 3602178/9275. The research of the second and third authors was partially financed by Spanish Grants BFM2001-2378, BFM2001-4028, MTM2004-0909 and HA2003-0121. We thank Anthony Przybylski for the implementation and making his results available. We thank the anonymous referees, whose comments have helped us to improve the presentation of the paper.     

♣ Does not imply the existence of a Suslin tree

We prove that ♣ does not imply the existence of a Suslin tree, so answering a question of I. Juhász. The authors thank the Israel Academy of Sciences and Humanities for partial support through the Basic Research Foundation Grant number 0327398. Mirna Džamonja would in addition like to thank The Hebrew University of Jerusalem and The Lady Davis Foundation for the Forchheimer Postdoctoral Fellowship during the academic year 1994/95, and Rutgers University for their hospitality during a visit in November 1995, when part of the research for this paper was conducted. Some of the research was also conducted while Mirna Džamonja was a visiting assistant professor at the University of Wisconsin-Madison. This publication is denoted [DjSh 604] in the list of publications of Saharon Shelah.     

Direct training method for a continuous-time nonlinear optimal feedback controller

The solutions of most nonlinear optimal control problems are given in the form of open-loop optimal control which is computed from a given fixed initial condition. Optimal feedback control can in principle be obtained by solving the corresponding Hamilton-Jacobi-Bellman dynamic programming equation, though in general this is a difficult task. We propose a practical and effective alternative for constructing an approximate optimal feedback controller in the form of a feedforward neural network, and we justify this choice by several reasons. The controller is capable of approximately minimizing an arbitrary performance index for a nonlinear dynamical system for initial conditions arising from a nontrivial bounded subset of the state space. A direct training algorithm is proposed and several illustrative examples are given.This research was carried out with the support of a grant from the Australian Research Council.We thank the anonymous reviewers for their helpful comments.     

On the convergence of two branch-and-bound algorithms for nonconvex programming problems

This note presents a new convergence property for each of two branch-and-bound algorithms for nonconvex programming problems (Falk-Soland algorithms and Horst algorithms). For each algorithm, it has been shown previously that, under certain conditions, whenever the algorithm generates an infinite sequence of points, at least one accumulation point of this sequence is a global minimum. We show here that, for each algorithm, in fact, under these conditions, every accumulation point of such a sequence is a global minimum.The author would like to thank Professor R. M. Soland for his helpful comments concerning this paper.     

Estimation of an optimal solution of a LP problem with unknown objective function

We consider a linear programming problem with unknown objective function. Random observations related to the unknown objective function are sequentially available. We define a stochastic algorithm, based on the simplex method, that estimates an optimal solution of the linear programming problem. It is shown that this algorithm converges with probability one to the set of optimal solutions and that its failure probability is of order inversely proportional to the sample size. We also introduce stopping criteria for the algorithm. The asymptotic normality of some suitably defined residuals is also analyzed. The proposed estimation algorithm is motivated by the stochastic approximation algorithms but it introduces a generalization of these techniques when the linear programming problem has several optimal solutions. The proposed algorithm is also close to the stochastic quasi-gradient procedures, though their usual assumptions are weakened.Mathematics Subject Classification (2000): 90C05, 62L20, 90C15Acknowledgments. I would like to thank two unknown referees for their fruitful suggestions that have helped to improve the paper.     

Error estimation and adaptive discretization for the discrete stochastic Hamilton–Jacobi–Bellman equation

Summary. Generalizing an idea from deterministic optimal control, we construct a posteriori error estimates for the spatial discretization error of the stochastic dynamic programming method based on a discrete Hamilton–Jacobi–Bellman equation. These error estimates are shown to be efficient and reliable, furthermore, a priori bounds on the estimates depending on the regularity of the approximate solution are derived. Based on these error estimates we propose an adaptive space discretization scheme whose performance is illustrated by two numerical examples.Mathematics Subject Classification (2000): 93E20, 65N50, 49L20, 49M25, 65N15Acknowledgments. This research was supported by the Center for Empirical Macroeconomics, University of Bielefeld. The support is gratefully acknowledged. I would also like to thank an anonymous referee who suggested several improvements for the paper.     

The dam problem with leaky boundary conditions

The goal of this paper is to study the fluid flow through a two-dimensional porous medium when we impose a leaky boundary condition. We show in particular that the situation is quite different from the one with the usual Dirichlet boundary condition.This work was initiated at the Universidad Complutense in Madrid and at the University of Bonn. We would like to thank these institutions. We also thank the I.M.A. (University of Minnesota) for providing its support and a nice working atmosphere to the second author during the completion of this paper.     

Parallel and distributed computing for stochastic dual dynamic programming

Computational Management Science - We study different parallelization schemes for the stochastic dual dynamic programming (SDDP) algorithm. We propose a taxonomy for these parallel algorithms,...     

A multi-period inventory model with multi-dimensional procurement bidding

We consider a multi-period inventory model with raw material procurements carried out via a reverse auction. Bids are multi-dimensional, and they consist of supplier information of price, shortage quantity and lead time. This work is an extension of our earlier work that has focused on multi-dimensional procurement auctions in single-period inventory models, to multi-period settings. The new model is based on a hybrid approach combining stochastic dynamic programming and simulation.     

On stochastic lot-sizing problems with random lead times

We give multi-stage stochastic programming formulations for lot-sizing problems where costs, demands and order lead times follow a general discrete-time stochastic process with finite support. We characterize the properties of an optimal solution and give a dynamic programming algorithm, polynomial in the scenario tree size, when orders do not cross in time.     

Decomposition Algorithms for Stochastic Programming on a Computational Grid

We describe algorithms for two-stage stochastic linear programming with recourse and their implementation on a grid computing platform. In particular, we examine serial and asynchronous versions of the L-shaped method and a trust-region method. The parallel platform of choice is the dynamic, heterogeneous, opportunistic platform provided by the Condor system. The algorithms are of master-worker type (with the workers being used to solve second-stage problems), and the MW runtime support library (which supports master-worker computations) is key to the implementation. Computational results are presented on large sample-average approximations of problems from the literature.     

Iterative linear programming solution of convex programs

An iterative linear programming algorithm for the solution of the convex programming problem is proposed. The algorithm partially solves a sequence of linear programming subproblems whose solution is shown to converge quadratically, superlinearly, or linearly to the solution of the convex program, depending on the accuracy to which the subproblems are solved. The given algorithm is related to inexact Newton methods for the nonlinear complementarity problem. Preliminary results for an implementation of the algorithm are given.This material is based on research supported by the National Science Foundation, Grants DCR-8521228 and CCR-8723091, and by the Air Force Office of Scientific Research, Grant AFOSR-86-0172. The author would like to thank Professor O. L. Mangasarian for stimulating discussions during the preparation of this paper.     

Control of linear processes with distributed lags using dynamic programming from first principles

A simple dynamic programming argument is presented for the quadratic-cost controller synthesis problem for discrete-time linear processes with delay. Distributed delays are allowed in both state and control. The solution obtained has a discrete-time Riccati difference structure closely analogous to the Riccati differential structure associated with delay problems in continuous time. Extensions are provided for the cases of varying lag-limits, performance criterion dependent on past variables, and the time-invariant regulator problem. A feedback solution is also obtained for a continuous-time problem with distributed delays in the control, by passage to limit from the discrete results.This work was supported by the Operations Research Center, University of California, Berkeley, California, under NSF Grant No. GP-30961X2. The author would like to thank Professor S. E. Dreyfus for guidance and helpful suggestions.     

A Scalable Parallel Interior Point Algorithm for Stochastic Linear Programming and Robust Optimization

We present a computationally efficient implementation of an interior point algorithm for solving large-scale problems arising in stochastic linear programming and robust optimization. A matrix factorization procedure is employed that exploits the structure of the constraint matrix, and it is implemented on parallel computers. The implementation is perfectly scalable. Extensive computational results are reported for a library of standard test problems from stochastic linear programming, and also for robust optimization formulations.The results show that the codes are efficient and stable for problems with thousands of scenarios. Test problems with 130 thousand scenarios, and a deterministic equivalent linear programming formulation with 2.6 million constraints and 18.2 million variables, are solved successfully.     

Using stochastic optimization to determine threshold values for the control of unreliable manufacturing systems

A manufacturing system with two tandem machines producing one part type is considered in this work. The machines are unreliable, each having two states, up and down. Both surplus controls and Kanban systems are considered. Algorithms for approximating the optimal threshold values are developed. First, perturbation analysis techniques are employed to obtain consistent gradient estimates based on a single simulation run. Then, iterative algorithms of the stochastic optimization type are constructed. It is shown that the algorithms converge to the optimal threshold values in an appropriate sense. Numerical examples are provided to demonstrate the performance of the algorithms.The research of these authors was supported in part by grants from URIF, MRCO, National Science Foundation, and Wayne State University. The authors would like to thank Dr. X. R. Cao, Digital Equipment Corporation, for the valuable initial discussion and Dr. X. Y. Zhou, University of Toronto, for his helpful comments.     

Solving fractional problems with dynamic multistart improving hit-and-run

Fractional programming has numerous applications in economy and engineering. While some fractional problems are easy in the sense that they are equivalent to an ordinary linear program, other problems like maximizing a sum or product of several ratios are known to be hard, as these functions are highly nonconvex and multimodal. In contrast to the standard Branch-and-Bound type algorithms proposed for specific types of fractional problems, we treat general fractional problems with stochastic algorithms developed for multimodal global optimization. Specifically, we propose Improving Hit-and-Run with restarts, based on a theoretical analysis of Multistart Pure Adaptive Search (cf. the dissertation of Khompatraporn (2004)) which prescribes a way to utilize problem specific information to sample until a certain level α of confidence is achieved. For this purpose, we analyze the Lipschitz properties of fractional functions, and then utilize a unified method to solve general fractional problems. The paper ends with a report on numerical experiments. This work was initiated while Mirjam Dür was spending a three-month research visit at the University of Washington. She would like to thank the Fulbright Commission for financial support and the optimization group at UW for their warm hospitality. The work of C. Khompatraporn and Z.B. Zabinsky was partially supported by the NSF grant DMI-0244286.     

A parallel method for finding the global minimum of univariate functions

We describe a new parallel method for solving global optimization problems. The formulation of the decision rules of this method is presented. We examine convergence conditions of the proposed algorithm and establish conditions which guarantee a considerable speedup with respect to the sequential version of the algorithm. We also present some numerical experiments executed on Alliant FX/80 for one class of multiextremal functions.The authors are greatly indebted to R. G. Strongin who stimulated the fulfillment of this research. They also would like to thank the anonymous referees for their useful suggestions.The research of the first author was partially supported by Grant 9494/NC/89 from the Italian Government under the Italian-Soviet Agreement about the Cultural and Scientific Exchange in 1990–1991. He thanks the Systems Department, University of Calabria, where he was a Visitor.     

PySP: modeling and solving stochastic programs in Python

Although stochastic programming is a powerful tool for modeling decision-making under uncertainty, various impediments have historically prevented its wide-spread use. One factor involves the ability of non-specialists to easily express stochastic programming problems as extensions of their deterministic counterparts, which are typically formulated first. A second factor relates to the difficulty of solving stochastic programming models, particularly in the mixed-integer, non-linear, and/or multi-stage cases. Intricate, configurable, and parallel decomposition strategies are frequently required to achieve tractable run-times on large-scale problems. We simultaneously address both of these factors in our PySP software package, which is part of the Coopr open-source Python repository for optimization; the latter is distributed as part of IBM’s COIN-OR repository. To formulate a stochastic program in PySP, the user specifies both the deterministic base model (supporting linear, non-linear, and mixed-integer components) and the scenario tree model (defining the problem stages and the nature of uncertain parameters) in the Pyomo open-source algebraic modeling language. Given these two models, PySP provides two paths for solution of the corresponding stochastic program. The first alternative involves passing an extensive form to a standard deterministic solver. For more complex stochastic programs, we provide an implementation of Rockafellar and Wets’ Progressive Hedging algorithm. Our particular focus is on the use of Progressive Hedging as an effective heuristic for obtaining approximate solutions to multi-stage stochastic programs. By leveraging the combination of a high-level programming language (Python) and the embedding of the base deterministic model in that language (Pyomo), we are able to provide completely generic and highly configurable solver implementations. PySP has been used by a number of research groups, including our own, to rapidly prototype and solve difficult stochastic programming problems.