Wildlife software SDP: Generalized software for solving stochastic dynamic optimization problems Bruce C. Lubow Abstract Dynamic programming--a mathematical optimization technique--has become a widely used tool in biological research and natural resource management. Stochastic Dynamic Programming software (SDP) was developed to provide a general, flexible, efficient, user friendly means to define and solve a wide range of stochastic optimization problems using dynamic programming. SDP operates with 386 or more recent PC's running DOS and readily available commercial software. SDP solves stochastic and deterministic optimization problems; accommodates broad user-specified conditions; accommodates models that are functions of stage, state, decision, and random variables; minimizes or maximizes the optimal value function; allows jointly distributed and independent random variables in the same problem; solves finite and infinite time-horizon problems; provides Monte Carlo simulation; and reduces computation time dramatically. Key words behavioral ecology, biological models, harvest management, natural resource management, stochastic dynamic programming, stochastic optimization Bruce C. Lubow is with the Colorado Cooperative Fish and Wildlife Research Unit, Department of Fishery and Wildlife Biology, Colorado State University, Fort Collins, CO 80523, USA. The Stochastic Dynamic Programming software package (SDP) provides the means to define and solve a wide range of stochastic optimization problems using the mathematical technique known as dynamic programming (Bellman 1957, 1961), which has become a widely used technique in biological research and natural resource management. SDP combines ease of use with flexibility and power to solve the large and complex problems often encountered in these applications while freeing investigators from much of the tedious programming typically required to implement customized computer code to solve such problems. Dynamic programming is a mathematical optimization technique applicable to systems described by a finite set of state variables where a series of decisions must be made in sequence to optimize some well defined objective. Historically, the technique was applied to the fields of engineering and management science (see examples and references in Bellman and Dreyfus 1962, Bellman and Kalaba 1965, Nemhauser 1966, Bertsekas 1976, 1987, Dreyfus and Law 1977). More recently, applications in the biological sciences and natural resources management have increased. Mangel and Clark (1986, 1988) and Houston et al. (1988) demonstrated the broad applicability of dynamic programming to behavioral ecology. In this context, the modeler presumes that an animal behaves optimally with respect to reproductive fitness (or some surrogate measure of fitness such as survival, energy accumulation, etc.). The condition of the animal at any time is modeled through 1 or more state variables including, possibly, its current energy reserves or reproductive status. The animal is faced with a series of decisions over time, such as choice of foraging patches. These choices present a tradeoff between uncertain (stochastic) rewards (e.g., possibility of finding food) and penalties (e.g., possibility of predation). The animal's decisions may vary with time and with internal state. Various physiological and environmental constraints are also incorporated into the model. The dynamic programming solution predicts the animal's behavior in response to its internal state and current environmental conditions. Problems with a similar structure are widespread in behavioral ecology, and thus, dynamic programming has become a widely used tool in this field (recently reviewed by Clark [1993]). Application of the dynamic programming approach to natural resources management has a longer but more sporadic history. Bellman and Kalaba (1960) recognized its value in population control in their formulation of a simplified approach to optimal predation. Walters and Hilborn (1978) and Williams (1982) demonstrated the general applicability of dynamic programming to natural resources management. Anderson (1985) provided a generalized approach to optimal exploitation in animal populations. Kennedy (1986) presented a wide range of applications to agriculture, land, forestry, and fisheries management. Williams (1989) reviewed applications to renewable resource management of dynamic optimization methods in general, and dynamic programming specifically. In many natural resource problems, a manager is faced with decisions involving tradeoffs between some type of benefits (e.g., harvested resources, increased viability of an endangered population, etc.) and costs (usually economic). A range of possible actions, often highly constrained, is under consideration, and the consequences of a given management action are somewhat uncertain due to stochastic factors. Using a discrete state variable model of the resource system that incorporates variables describing the resource (e.g., populations size) and the environment (e.g., amount of breeding habitat, forage, rainfall, etc.), dynamic programming can provide an optimal strategy with respect to a well defined objective. This strategy indicates the best action to take in each period in response to the current state of the system to optimize the defined objective over time. There have been a few particularly noteworthy applications of dynamic programming to wildlife and fisheries management. Anderson (1975) investigated optimal exploitation of mallard (Anas platyrhynchos) populations. Walters (1975), Hilborn (1976), and Walters and Hilborn (1976) examined optimal exploitation of fisheries. Williams (1985) studied the optimal defoliation of salt desert shrubs in Utah. Stocker (1981, 1983), Walters et al. (1981), and Stocker and Walters (1984) applied dynamic programming to optimal exploitation of ungulates using population dynamics models which incorporated predator, vegetation, and economic components. Dynamic programming offers several advantages over other optimization techniques that make it particularly applicable to biological and natural resource problems (Williams 1982, Anderson 1985, Kennedy 1986). First, dynamic programming provides feedback (closed-loop) decision "strategies" rather than static "policies" (Dreyfus and Law 1977, Anderson 1985, Bertsekas 1987). These decision strategies specify the optimum response to each possible future situation, as opposed to a static policy determined a priori based on expected outcomes. Thus, the technique finds optimal strategies in a stochastic environment that are responsive to changing conditions. Furthermore, unlike most optimization techniques, dynamic programming can readily incorporate nonlinear, discontinuous, and integer-valued functions as well as a large number of constraints on the decision and state variables. This facilitates modeling biological systems with a high degree of realism (Anderson 1975, Mangel and Clark 1988, Williams 1989). Despite these advantages and a series of successful applications to biology and natural resource management spanning nearly 30 years, several practical obstacles confront investigators applying stochastic dynamic programming to complex biological systems. A significant drawback to the dynamic programming technique is the high computational requirements for problems with more than a few state or decision variables ("the curse of dimensionality," Bellman 1957). However, the advent of inexpensive, high performance personal computers and workstations has significantly reduced this problem. Undoubtedly, the highly theoretical and mathematical nature of some literature on dynamic programming has also impeded application of this technique (see the discussion of this problem in Nemhauser [1966:245]). However, the absence of adequate software may pose the most significant obstacle facing potential users of the dynamic programming technique. Morin (1979) identified 10 "fairly general" dynamic programming codes; however, these are now >15 years old, mainframe based, and designed to solve deterministic dynamic programming problems. Labadie (1990) developed CSUDP, a generalized software for microcomputers that incorporates several sophisticated techniques for reducing computation time for large deterministic problems. CSUDP can also solve small (2-state variable) stochastic problems; however, this package can not effectively solve larger stochastic problems. SDP features and capabilities SDP was developed to provide a general, flexible, efficient, user-friendly means to define and solve a wide range of stochastic optimization problems using dynamic programming. As with any sophisticated modeling technique, a well tested, efficiently written, standard software package is a tool that saves time and improves the reliability of results; however, it can not replace user's understanding of the conceptual basis of the technique and its application to biological problems. SDP should not be viewed as a means of providing novices with an easy recipe for solving complex dynamic optimization problems. Rather, it is intended to assist investigators familiar with dynamic programming and the extensive literature on biological applications. These users can save substantial time and effort that would otherwise be required to duplicate the extensive input validation, flexible and efficient dynamic programming algorithm, multi-dimensional linear interpolation, Monte Carlo simulation (forward iteration) capability, report generation, user interface, and other features of SDP. To solve a problem with SDP, the user must provide a data file and 3 functions to define a model and that specifies a scenario. Because SDP incorporates user-supplied functions and provides a flexible scenario definition language, it can solve a wide range of discrete optimization problems. The following list summarizes the most significant features of SDP and the range of dynamic programming problems that it can solve. - SDP handles stochastic and deterministic optimization. - SDP is designed to handle an arbitrary (user specified) number of stages, state variables, decision variables, and random variables. Only computer memory and speed limit the size of the problem that can be solved. - SDP handles problems with decisions that are a function of stage (time) and system state and random variables that are functions of stage, state, and decision. - SDP can minimize or maximize the optimal value function, either with or without application of a discount factor. - SDP allows jointly distributed and independent random variables in the same problem. - In addition to solving finite time-horizon problems, SDP can seek a stationary (time invariant) solution to an infinite time-horizon optimization problem with user-specified convergence criteria. - SDP's Monte Carlo simulation (forward iteration) capability allows the user to simulate the system dynamics under the optimal strategy determined by SDP. Simulation results are a convenient and frequently used means of presenting dynamic programming results. - SDP incorporates several features for reducing computation time while maintaining precision and using computer memory efficiently. Thus, it efficiently solves very large and complex problems. In fact, a 2-state-variable model (Anderson 1975) that required 90 minutes on an IBM 360/65 mainframe computer was solved in only 3 seconds on a 486/33 personal computer (PC) through these features. Using SDP SDP incorporates many features to simplify the process of defining and solving dynamic programming problems. The SDP user interface (SDPUI) is a DOS-based system that provides access to features of SDP. SDPUI displays: (1) pull-down menus, (2) dialog boxes for input, (3) status and error messages, and (4) comprehensive help. SDPUI facilitates management of multiple modeling projects: the user can create, copy, edit, build, run, view, and delete models, data, and reports from SDPUI. The user must define state dynamics, stage return, and terminal value functions. The state dynamics function models the (deterministic or stochastic) response of the system to a given combination of state, decision, and random variables. The stage return and terminal value functions specify measures of benefit (or cost) associated with various combinations of stage, state, decision, and random variables. The user defines these functions by supplying a few lines of computer code written in C programming language. To help the user, SDPUI provides function templates containing a skeleton of each required function. The user must add a few lines of C code to these templates; this rarely requires more than a rudimentary knowledge of C. In fact, the brief introduction to C found in the SDP User's Guide (Lubow 1994a) should provide enough information for most applications. Anyone with a modest background in another programming language such as FORTRAN, BASIC, or PASCAL should be able to master the required concepts in a few hours. SDPUI also automates access to the C compiler and linker; the user needs to have no knowledge of these tools. Despite the limited knowledge of programming required, users with no programming experience are discouraged from using SDP. The user must create a scenario file for input to the model. The input defines: (1) discrete stages, (2) state, decision, and random variables, (3) constraints and increment sizes, (4) solution procedure options, and (5) output options. The input consists of a series of statements that are part of a scenario definition language developed for SDP to facilitate specification of a wide range of dynamic programming problems. The scenario definition language combines simplicity with flexibility through extensive use of defaults and options. This language is thoroughly documented in the SDP User's Guide (Lubow 1994a). The SDP User's Guide (Lubow 1994a) presents a tutorial using 3 sample problems taken from published sources that demonstrate the broad applicability of SDP. These examples include: a shortest-path problem (Dreyfus and Law 1977), a typical problem from behavioral ecology involving an animal choosing a foraging patch (Mangel and Clark 1988), and a multi-dimensional harvest management problem with population and environmental variables (Anderson 1975). Complete model and data files for these examples are distributed with SDP. This tutorial allows users with the proper background (dynamic programming theory and computer programming experience) to rapidly learn techniques required to define and solve dynamic optimization problems in SDP. These examples also illustrate the range of features incorporated into SDP. The SDP User's Guide (Lubow 1994a) contains a detailed reference section to assist the more experienced user. SDP is distributed with an installation program that automatically customizes SDP to the user's computer configuration. A de-installation program allows the user to remove SDP without disturbing other files. SDP requires the following: a 386 or higher PC, MS-DOS (version 5.0 or higher, Microsoft Corporation, Redmond, Wash.), at least 400k of hard drive space, and either the Borland C++ (version 3.0 or 3.1) or Turbo C++ for DOS (version 2.0) compiler (both are products of Borland International, Inc., 1800 Green Hills Road, P.O. Box 660001, Scotts Valley, CA 95067-0001, USA). In addition, the following is strongly recommended: a floating-point math coprocessor, 640k of conventional RAM available for program execution, 2 MB of RAM allocated for use as RAM drive or disk cache, 1 MB or more of hard rive space, a color monitor, and a mouse. The SDP program and documentation are available, free of charge, on the Bird Monitor bulletin board (301-498-0402). SDP is also available on 3.5-inch diskettes from the author at cost ($5). The User's Guide (Lubow 1994a) is distributed electronically in WordPerfect format and is included with the above diskettes. A hard-copy version of the User's Guide is available, upon request, from the author add $20). Although not routinely included, the source code and the SDP Source Code Reference manual (Lubow 1994b) are also available upon request (add $5 for diskette only or $20 for diskette and hard-copy manual). Acknowledgments. I am grateful to the Colorado Division of Wildlife for funding the development of his software. I am indebted to J. W. Labadie for teaching me the theory of dynamic programming and for inspiring this project. Through his software package CSUDP, J. W. Labadie demonstrated the feasibility, general approach, and value of general software for solving dynamic programming problems. P. L. Kennedy assisted in testing and reviewing the software and the user's guide; her help was most valuable. I appreciate the helpful and encouraging comments of 2 anonymous reviewers. I thank D. R. Anderson and G. C. White for their encouragement, support, and nearly unlimited patience as well as for their many useful comments and suggestions regarding the software and documentation. Literature cited ANDERSON, D. R. 1975. Optimal exploitation strategies for an animal population in a Markovian environment: a theory and example. Ecology 56:1,281-1,297. ANDERSON, D. R. 1985. Constrained optimal exploitation: a quantitative theory. Pages 105- 116 in S. L. Beasom and S. F. Roberson, eds. Game harvest management. Caesar Kleberg Wildl. Research Inst., Kingsville, Tex. BELLMAN, R. 1957. Dynamic programming. Princeton Univ. Press, Princeton, NJ. 342pp. BELLMAN, R. 1961. Adaptive control processes: a guided tour. Princeton Univ. Press, Princeton, NJ. 255pp. BELLMAN, R., AND S. E. DREYFUS. 1962. Applied dynamic programming. Princeton Univ. Press, Princeton, NJ. 363pp. BELLMAN, R., AND R. KALABA. 1960. Some mathematical aspects of optimal predation in ecology and boviculture. Proc. National Acad. Sci. 46:718-720. BELLMAN, R., AND R. KALABA. 1965. Dynamic programming and modern control theory. Academic Press, New York, N.Y. 112pp. BERTSEKAS, D. P. 1976. Dynamic programming and stochastic control. Academic Press, New York, N.Y. 397pp. BERTSEKAS, D. P. 1987. Dynamic programming: deterministic and stochastic models. Prentice-Hall, Inc., Englewood Cliffs, NJ. 376pp. CLARK, C. W. 1993. Dynamic models of behavior: an extension of life history theory. Trends in Ecol. Evol. Biol. 8:205-209. DREYFUS, S. E., AND A. M. LAW. 1977. The art and theory of dynamic programming. Academic Press, San Diego, Calif. 284pp. HILBORN, R. 1976. Optimal exploitation of multiple stocks by a common fishery: a new methodology J. Fish. Research Board Can. 33:1-5. HOUSTON, A., C. CLARK, J. MCNAMARA, AND M. MANGEL. 1988. Dynamic models in behavioral and evolutionary ecology. Nature 332:29-34. KENNEDY, J. O. S. 1986. Dynamic programming: applications to agriculture and natural resources. Elsevier Appl. Sci. Publ., Ltd., Barking, Essex, U.K. 335pp. LABADIE, J. W. 1990. Dynamic programming with the microcomputer. Pages 275-337 in A. Kent, J. G. Williams, R. Kent, and C. M. Hall, eds. Encyclopedia of microcomputers, vol. 5. Marcel Dekker, Inc., New York, N.Y. LUBOW, B. C. 1994a. Stochastic dynamic programming (SDP) user's guide. Version 1.06. Colorado Coop Fish and Wildl. Res. Unit, Colorado State Univ., Fort Collins, Colo. 134pp. LUBOW, B. C. 1994b. Stochastic dynamic programming (SDP) source code reference manual. Version 1.06. Colorado (loop. Fish and Wildl. Res. Unit. Colorado State Univ., Fort Collins Colo. 35pp. MANGEL, M., AND C. W. CLARK. 1986. Towards a unified foraging theory. Ecology. 67:1,127-1,138. MANGEL, M., AND C. W. CLARK. 1988. Dynamic modeling in behavioral ecology. Princeton Univ. Press, Princeton, N J. 308pp. MORIN, T. L. 1979. Computational advances in dynamic programming. Pages 53-90 in M. L. Puterman, ed. Dynamic programming and its applications. Academic Press, New York, N.Y. NEMHAUSER, G. L. 1966. Introduction to dynamic programming. John Wiley and Sons, Inc. New York, N.Y. 256pp. STOCKER, M. 1981. Optimization model for a wolf-ungulate system. Ecol. Model. 12:151-172. STOCKER, M. 1983. Ungulate population dynamics and optimization models. Ecol. Model. 18:121-139. STOCKER, M., AND C. J. WALTERS. 1984. Dynamics of a vegetation-ungulate system. Ecol. Model. 12:151-172. WALTERS, C. J. 1975. Optimal harvest strategies for salmon in relation to environmental variability and uncertain production parameters. J. Fish. Res. Board Can. 32:1,777-1,784. WALTERS, C. J., AND R. HILBORN 1976. Adaptive control of fishing systems. J. Fish. Res. Board Can. 33:145-159. WALTERS, C. J., AND R. HILBORN 1978. Ecological optimization and adaptive management. Ann. Rev. Ecol. Syst. 9:157-188. WALTERS, C. J., M. STOCKER, AND G. C. HABER. 1981. Simulation and optimization models for a wolf-ungulate system. Pages in C. W. Fowler and T. D. Smith. eds. Dynamics of populations. John Wiley and Sons, Inc., New York, N.Y. WILLIAMS, B. K. 1982. Optimal stochastic control in natural resource management: framework and examples. Ecol. Model. 16:275-297. WILLIAMS, B. K. 1985. Optimal management strategies in variable : stochastic optimal control methods. J. Environ. Manage. 21:95-115. WILLIAMS, B. K. 1989. Review of dynamic optimization methods in renewable natural resource management. Natural Resource Model. 3:137-216. Bruce C. Lubow received his B.S. and M.S. degrees in Aeronautical Engineering from the Massachusetts Institute of Technology in 1 979 and 1 981, respectively. He has worked as an engineer and consultant in the aviation industry and as a software analyst, manager, and consultant at Digital Equipment Corporation. Bruce is an associate of the Colorado Cooperative Fish and Wildlife Research Unit and is pursuing a Ph.D. in Wildlife Biology at Colorado State University. His current research interests include population dynamics natural resource management, ecological modeling, conservation biology, and behavioral ecology. Associate Editor: Rexstad.