Abstract:
A computer system for data management arranged to provide at least four components: a generator component, a solver component, a simulation component and a visualisation component, wherein the simulation component is arranged to simulate stochastic processes and output simulation data of the simulated process to the generator component; the generator component is arranged to process a model input thereto and to generate a Dynamic Stochastic Program (DSP) therefrom and also to process the simulation data received from the simulation component and output the DSP together with the processed simulation data to the solver component; the solver component being arranged to receive the DSP and the processed simulation data and to process the DSP together with the simulation data; and the visualisation component being arranged to allow the data being processed by the solver to be visualised.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application is a continuation of U.S. application Ser. No. 11/569,796, filed Aug. 1, 2007, now abandoned, which is a National Stage Entry of International Application No. PCT/GB05/02103, filed May 27, 2005, which claims the right of priority based on UK Application No. 0412123.2, filed May 29, 2004. Each of the foregoing is incorporated by reference in its entirety. 
     
    
     BACKGROUND 
       [0002]    This invention relates to a computer system for data manipulation and in particular, but not exclusively, to a computer system arranged to manipulate data to ascertain future trends. Related methods are also provided. 
         [0003]    Linear, and more generally mathematical, programming optimization techniques have been in steady commercial use on the computing systems of the day since the mid 1950s. Sometime in the mid 1970s, independently at both the US Energy Department and the World Bank, the concept of a modelling language for mathematical programming arose. 
         [0004]    Representation of a model in such a language is to the numerical optimization of a mathematical program the analogue of what a database management system schema is to a flat file. It is straightforward for the analyst to turn a mathematical description of a model into statements in a modelling language which then communicates directly with the solver—optimization routine. 
         [0005]    In the intervening years a variety of sophisticated modelling languages have come into every day use for the creation, solution and modification of large scale deterministic linear, nonlinear and discrete optimization models of practical planning problems. 
         [0006]    Dynamic Stochastic Programming (DSP) is a numerical method for solving planning problems that involve uncertainty, now and in the future. Generally, the method involves writing the problem in a mathematical programming language, and passing that program to a suitable solver. However, solving such problems is computationally intensive, making it nigh impossible to solve realistic problems in acceptable time. The present difficulty of the method stems from a number of issues with current DSP tools. It has therefore been a problem to solve such problems involving uncertainty, now and in the future, in an acceptable time or at all. There is a desire to solve such problems in order that predictions about the future can be made. Such predictions are useful for a wide variety of fields including: the supply and demand for energy, oil, or telecommunications bandwidth or in financial markets. Future predictions about the requirement for bandwidth, energy, oil and the like may be useful in determining the size of plant to construct, etc. 
         [0007]    There is an issue of how to represent uncertain future states of the world. Generally this is done by simulation: forecasting alternative scenarios for the future. Stochastic programming involves combining all of these alternative scenarios into the Deterministic Equivalent Problem (DEP). Here lies the problem: too few scenarios and the solution is not robust, too many and the problem cannot be solved in reasonable time. This is particularly problematic for DSP in which there are multiple time-steps and the number of scenarios grows geometrically. 
         [0008]    The second issue is the choice of a suitable solver: one that is adapted to the nature of the problem. General-purpose solvers attempt to map the entire DEP into memory, which constrains the practitioner to unrealistically simple DSP&#39;s or large amounts of memory and computing power would be required to solve DEP of more complexity. The problem thus arises as to how a realistic problem can be solved in reasonable time with the computing power that it is currently readily available. 
       SUMMARY 
       [0009]    According to a first aspect of the invention there is provided a method of managing data to solve a Dynamic Stochastic Programming problem, the method comprising providing a suite of components that allow the DSP to be to be iteratively solved wherein the components comprise a generator component, a solver component, a simulation component and a visualisation component wherein;
       i. the generator component is arranged to generate a Dynamic Stochastic Program (DSP) from a model input thereto and to convert the output of the simulator component for processing by the solver component;   ii. the solver component being arranged to process the DSP;   iii. the simulator component being arranged to simulate stochastic processes for processing by the generator component; and   iv. the visualisation component providing an output of the input model and the results generated by the solver.       
 
         [0014]    An advantage of such a method is that it can improve the efficiency and effectiveness of Dynamic Stochastic Programming (DSP) for real-world planning problems running on equivalent hardware to prior solutions. The components may resolve the hitherto intractable issues of problem size and complexity by supporting stages of an iterative process of finding a robust solution with an integrated set of tools that are specifically designed for each modelling task: simulation, generation, optimization, and visualisation. 
         [0015]    It is advantageous that the visualisation component allows both the input model and the results generated by the solver to viewed as this allows a user to ascertain that the solution to the DEP is acceptable. A comparison of the input model and the results generated by the solver allows an iterative process to be performed until a satisfactory solution to the DEP is provided. 
         [0016]    The components may be thought of as providing an integrated set of tools for solving real-world planning problems using DSP in an iterative process. Other mathematical programming languages used to solve DSP are single-shot, in that they assume that the program is correctly formulated if it is syntactically correct, and that the solution is correct if it can be calculated at all. Previously any attempt to refine the solution is left to the practitioner to edit and re-run the program. 
         [0017]    The method may provide a solution that is arrived at in an iterative process of refinement with different models, scenario structures and simulator data. 
         [0018]    The simulation component may provide a plurality of simulators each arranged to simulate a predetermined characteristic. The visualisation component may comprise a plurality of viewers. The method may couple a viewer in the visualisation component with one or more simulators in the simulator component. It may be possible using the visualisation component to identify shortfalls in the solution and re-run the program with appropriate refinements. 
         [0019]    In some, perhaps the simplest, embodiments the visualisation component may a viewer that allows a file, which may be a text file, or the like, to viewed. In other embodiments the viewer may be more complex and may provide a graphical interface. 
         [0020]    The generator component has a number of advantages at least some of which follow: firstly it allows the formulation of the planning problem to be separated from the structure of the future scenarios. This is revolutionary in the field of stochastic programming, where every other approach has embedded the structure if not the scenarios themselves into the DSP. Such an embedding would otherwise seem inevitable, since the DSP has to be compiled into the DEP so that it can be solved. 
         [0021]    The method may allow the scenario structure to be revised iteratively which is advantageous in that it helps to improve the robustness of the solution and the computational efficiency of the solver. In all other approaches that involve embedding the structure into the program it is difficult and tedious to change this structure even once, let alone repeatedly. What was previously hard-coded, is independent and flexible in the generator component of the current method. Thus the stochastic planning problem can be formulated in the stochastic programming language as if it was deterministically dynamic, with little or no reference to the way in which uncertainty is represented in the scenario structure. 
         [0022]    Secondly the method may cause the generator component to read the scenarios in a piecewise manner whilst solving the DSP. All other stochastic programming tools generate the DEP in full, even if it is then passed to a decomposition solver. This severely constrains the size of the planning problem that can be solved. Therefore, it is an advantage of the current method that less memory and processing power is required to solve the DSP. This limitation is particularly painful for DSP&#39;s where the number of scenarios required to adequately span the future states of the world may be very large indeed. As a consequence other approaches are unable to solve realistic DSP&#39;s in acceptable times, if at all. 
         [0023]    The method may split the DSP into sub-tasks. Further, the generator component may be caused by the method to read sub-tasks of the DSP into the solver component. This may provide a more efficient use of computing resources, and makes it feasible to parallelize the solution process. This approach is facilitated by the tight coupling of the sub-task solution by the generator and solver components. All other approaches involving a decoupled (third-party) solver are forced to instantiate the DEP in full. 
         [0024]    The solver component may utilise any of the following: various adaptations of the nested Benders algorithm appropriate to the DEP structure, with strictly linear constraints, convex non-linear objectives, heuristic aggregation techniques, sequential importance sampling based on the expected value of perfect information, and tight coupling with the generator component (as described above). The benefits of these adaptations are increases both in the speed of solving DSP&#39;s and in the scale of the planning problems that can be solved. 
         [0025]    Furthermore, the solvers within the solver component may support parallelization across a plurality of processors to further increase the size of problems that can be solved, and the speed of solution. Benchmark tests have shown that the solver component may be ten to one hundred times faster than other solvers, for the types of real-world DSP for which the components has been designed. 
         [0026]    The method may allow the visualisation component access to data-structures within the generator component. An advantage of such a method is that a more immediate and interactive interface is possible compared to providing an external viewer; i.e. a viewer that does not have access to the data-structures within the generator component. 
         [0027]    It is usual to customise one or more of the viewers within the visualisation component for a particular application, such as displaying an expected financial portfolio composition as it changes over time towards a forecast horizon. The method may allow external viewers with less direct coupling to the components to be used but advantageously these are used once the model has stabilized. 
         [0028]    The method may allow the simulator component and/or the visualisation component to be customized for particular applications, or replaced in part by sub-components created specifically for a predetermined task. 
         [0029]    The method may also provide a library component which provides a library of routines that may be called by other components. Such a library component facilitates such customization since it allows for efficient interfaces to the functionality and data of the other components. The library component helps to couple the components used by the method making the method more efficient for use on real-world planning problems. The method may separate the scenario structures from the DSP providing for an easier and faster approach to the formulation and solution of problems. 
         [0030]    It is common to represent the DSP as a tree in which each node of the tree represents a decision point at which the future must be assessed in terms of alternative simulated scenarios. This tree may be referred to as a scenario tree and a simulated scenario represents one particular path through the tree. 
         [0031]    The Stochastics Suite includes several solvers that exploit the nodal structure of the DSP, as expressed in the programming language and in the separate scenario tree structure. These solvers achieve dramatic increases in the speed of solving large problems: ten to one hundred times faster than other general-purpose solvers. Not only does this allow real-world problems to be solved in acceptable times, it facilitates solving complex problems that are otherwise insoluble using other solvers. 
         [0032]    According to a second aspect of the invention there is provided a computer system for data management arranged to provide at least four components: a generator component, a solver component, a simulation component and a visualisation component:
       wherein the simulator component is arranged to simulate stochastic processes and output simulation data of the simulated process to the generator component;   the generator component is arranged to process a model input thereto and to generate a Dynamic Stochastic Program (DSP) therefrom and also to process the simulation data received from the simulator component and output the DSP together with the process simulation data to the solver component;   the solver component being arranged to receive the DSP and the processed simulation data and to process the DSP together with the simulation data; and   the visualisation component being arranged to allow the data being processed by the solver to be visualised.       
 
         [0037]    According to a third aspect of the invention there is provided a machine readable medium containing instructions which when read onto a computer cause that computer to provide the method of the first aspect of the invention. 
         [0038]    According to a fourth aspect of the invention there is provided a machine readable medium containing instructions which when read onto a computer cause that computer to provide the computer system of the second aspect of the invention. 
         [0039]    According to a fifth aspect of the invention there is provided a program arranged to solve a Dynamic Stochastic Programming problem, the program providing a suite of components that allow the problem to be to be iteratively solved wherein the components comprise a generator module, a solver module, a simulation module and a visualisation module wherein;
       i. the generator module is arranged to generate a Dynamic Stochastic Program (DSP) from a model input thereto and to convert the output of the simulation module for processing by the solver module;   ii. the solver module being arranged to process the DSP;   iii. the simulation module being arranged to simulate stochastic processes for processing by the generator module; and   iv. the visualisation module providing an output of the inputs and the results generated by the solver module.       
 
         [0044]    According to a sixth aspect of the invention there is provided a machine readable medium containing instructions provide the program of the fifth aspect of the invention. 
         [0045]    The machine readable medium of any of the aspects of the invention may be any of the following non-exhaustive list: a floppy disk, a CD ROM/RAM, a DVD ROM/RAM (including −R/−RW and +R/+RW), a hard drive, a memory, any form of magneto and/or optical disk, a transmitted signal (including an internet download, email, ftp, or the like), a wire. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0046]    There now follows by way of example only a detailed description of the present invention with reference to the accompanying drawings in which: 
           [0047]      FIG. 1  shows, schematically, a suitable computer system for realising one embodiment of the present invention; 
           [0048]      FIG. 2  schematically shows an overview of the components of one embodiment of the present invention; 
           [0049]      FIG. 3  schematically shows how units within the components communicate with one another; and 
           [0050]      FIG. 4  outlines a method of using the invention as shown in  FIGS. 1 and 2 . 
       
    
    
     DETAILED DESCRIPTION 
       [0051]    The computer system  100  shown in  FIG. 1  comprises a display means  102 , in this case an LCD (Liquid Crystal Display) monitor, a keyboard  104 , a mouse  106  and processing circuitry  108 . It will be appreciated that other display means such as LEP (Light Emitting Polymer), CRT (Cathode Ray Tube) displays, projectors, televisions and the like may be equally possible. 
         [0052]    The processing circuitry  108  comprises a processing means  110 , a hard drive  112  (containing a store of data), memory  114  (RAM and ROM), an I/O subsystem  116  and a display driver  117  which all communicate with one another, as is known in the art, via a system bus  118 . The processing means  110  typically comprises at least one INTELT™ PENTIUM™ series processor, (although it is of course possible for other processors to be used) and performs calculations on data. The other processors may include processors such as the AMD™ ATHLON™, POWERPC™, DIGITAL™ ALPHA™, and the like. 
         [0053]    The hard drive is used as mass storage for programs and other data. The memory  114  is described in greater detail below. 
         [0054]    The keyboard  104  and the mouse  106  provide input means to the processing means  110 . Other devices such as CDROMS, DVD ROMS, scanners, etc. could be coupled to the system bus  118  and allow for storage of data, communication with other computers over a network, etc. Any such devices may then comprise further input means. 
         [0055]    The I/O (Input/Output) subsystem  116  is arranged to receive inputs from the keyboard  104  and from the processing means  110  and may allow communication from other external and/or internal devices. The display driver  117  allows the processing means  110  to display information on the display  102 . 
         [0056]    The processing circuitry  108  further comprises a transmitting/receiving means  120 , which is arranged to allow the processing circuitry  108  to communicate with a network. The transmitting/receiving means  120  also communicates with the processing circuitry  108  via the bus  118 . 
         [0057]    The processing circuitry  108  could have the architecture known as a PC, originally based on the IBMT™ specification, but could equally have other architectures. The processing circuitry  108  may be an APPLE™, or may be a RISC system, and may run a variety of operating systems (perhaps HP-UX, LINUX, UNIX, MICROSOFT™ NT, AIX™, or the like). The processing circuitry  108  may also be provided by devices such as Personal Digital Assistants (PDA&#39;s), mainframes, telephones, televisions, watches or the like. 
         [0058]    It will be appreciated that although reference is made to a memory  114  it is possible that the memory could be provided by a variety of devices. For example, the memory may be provided by a cache memory, a RAM memory, a local mass storage device such as the hard disk  112 , any of these connected to the processing circuitry  108  over a network connection such as via the transmitting/receiving means  120 . However, the processing means  110  can access the memory via the system bus  118 , accessing program code to instruct it what steps to perform and also to access the data samples. The processing means  110  then processes the data samples as outlined by the program code. 
         [0059]    The memory  114  is used to hold instructions that are being executed, such as program code, etc., and contains a program storage portion  150  allocated to program storage. The program storage portion  150  is used to hold program code that can be used to cause the processing means  110  to perform predetermined actions. 
         [0060]    The memory  114  also comprises a data storage portion  152  allocated to holding data and in embodiments of the present invention in particular holds a DSP model  154  and a scenario tree  164 . 
         [0061]    The computer system  100  of  FIG. 1  is arranged to provide a suite of components  200  that together allow a Dynamic Stochastic Program (DSP) to be formulated and solved. In this embodiment there are five components which interact with one another as will be described hereinafter but in other embodiments there may be more or fewer components. The components may also be thought of modules within a program running on the computer system. 
         [0062]    Every one of the components is utilised in the overall process of finding an acceptable solution to the DSP. However, bespoke variants of some of the components may be required to customize the suite to a particular application. The components are described below. 
         [0063]    Finding a robust solution generally involves an iterative process of refining the planning problem, rerunning the simulations and the optimization, and interpreting the results. This process is described subsequently. It will be appreciated that when considering planning problems that involve uncertainty, now and in the future it is useful to consider that our present decisions are only based on what we know now, so our planning problems are roughly Markovian. Furthermore our forecasts of future scenarios branch outwards like a tree, one time-stage at a time. This nodal formulation makes decomposition solvers particularly efficient. Much more so than some other approaches that use a general-purpose solver for a flat scenario structure with non-anticipativity constraints. 
       Description of Components 
       [0064]    The generator component  202  is the central component of the Suite  200  and generates the DSP from a model written in a proprietary programming language. It may be considered as a compiler that reads a program that is stored in a text file, combines it with the specified scenario structure, and generates an internal representation of the DEP that can be solved by a solver component  204  of the suite 200. The specific scenario structure is defined by a scenario tree  164  which is maintained within the memory  112 ,  114 . 
         [0065]    The DSP is represented as a tree in which each node of the tree represents a decision point at which the future must be assessed in terms of alternative future scenarios. This tree may be referred to as a scenario tree and a simulated scenario represents one particular path through the tree and as such represents one particular future prediction. It will be appreciated that many scenarios (i.e. paths through the tree) will contain the same branches and nodes and as such there will be redundancy in the scenarios. Some embodiments of the invention may utilise this redundancy and store portions of scenarios that are evaluated in order that that or those portions of a scenario need not be re-evaluated when further scenarios are evaluated. 
         [0066]    The second function of the generator component  202  is to read the scenarios generated by a simulator component  206  into the structure required by the solver component  204  during the solving process. This can be a dynamic process, node by node of the nodal formulation of the scenario, which exploits the partitioning method that is embodied in one of a plurality of a plurality of solvers within the solver component  204 . Some embodiments of the invention may utilise a number of solvers in sequentially. By this means planning problems that are too large to handle all at once can be broken down into manageable sub-tasks. 
         [0067]    The second component of the Suite is the solver component  206 , which comprises several decomposition solvers that are designed to exploit the particular characteristics of real-world DSP&#39;s. These characteristics reflect the ways in which uncertainty evolves in the future as discussed above. 
         [0068]    Typically for any application there will be a number of processes and events that should be forecast in alternative scenarios of the future. The simulation component  206  comprises a set of simulators for financial and economic processes such as stocks, bonds, interest rates, cash flows, production and inflation. In the present embodiment an asset simulator  166  and a liability simulator  168  are provided. There are simulators for real-world processes such as the supply and demand for energy, oil, or telecommunications bandwidth. There are also simulators for real-world events such as sickness and death of individuals. These can be used or adapted to simulate all of the processes and events that are required for the particular planning problem at hand. 
         [0069]    Throughout the modelling process it is desirable to inspect the input data and solver results in order to refine the scenario structure and thereby improve the robustness of the solution. This can be difficult without a graphical representation of the simulated scenarios and the conditional decisions found by the solver, which often comprise a vast amount of numerical data. The visualisation component  208  provides such a tool. 
         [0070]    The visualisation component  208  consists of a selection of graphical viewers for scenario trees and solver results. These can display large distributions of scenarios in a way that helps the practitioner to see the overall shape and flow of the scenarios, without being buried in the fine detail. This is advantageous for successful control of the iterative modelling process. 
         [0071]    The flexibility and customization capabilities of the Suite  200  are provided by a library component  210 , a comprehensive library of routines for creating, editing, processing and viewing models, scenarios and solutions. With this library it is possible to customize the other components (the simulation component  206 , the generator component  202 , the solver component  204  and the visualisation component  208 ) to suit particular applications, such as financial portfolio management or asset and liability management. The library component  210  provides an Application Programming Interface (API) to many of the facilities of these other components, as well as a toolkit of other routines specific to DSP. 
         [0072]    Referring to  FIG. 3  it can be seen that the various components of the Suite  200  communicate by means of procedure calls and data structures that are outlined below. 
         [0073]    The generator component  202  comprises a model compiler  300  which is arranged to read the DSP model  154  from the memory  112 ,  114 , compile it into the DEP, combines it with scenario data, and pass the program to the solver component  204 . In this embodiment the solver component comprises a nested Benders solver  156 . The nested bender solver  156  decomposes the problem using aggregation heuristics, and then solves the problem piece-wise with an adaptation of the nested Benders algorithm. 
         [0074]    The internal structure of the DEP can be inspected by the visualisation component  208 . In particular the visualisation component comprises a structure viewer  158  to determine the optimal form of the program for efficient solving. Once the planning problem is solved, the solution is passed back to the model compiler  300  where it can be inspected by means of solution viewers  160  provided by the visualisation component  208 . 
         [0075]    The model compiler  300  may, if required, create the DEP in the form of a text file that can be read by a solver other than the solver component  204 , by means of the appropriate solver interface. Though flexible, this is constrained and inefficient for the reasons expressed above. 
         [0076]    The model compiler  300  calls the path/tree generator  162  for each piece of the scenario tree  164  that is required by the solver component  204 . The path/tree generator  162  in turn calls simulators  166 ,  168  provided by the simulation component  206  repeatedly to populate each node of the path or tree that has been requested. 
         [0077]    The path/tree generator  162  can, if required, create an entire scenario tree  164  as a data file in depth-first pre-order that can be read by a tree walker  170 , provided by the generator component  202 , whilst solving. This scenario tree  164  can be displayed by a tree viewer  172  provided by the visualisation component  208 . 
         [0078]      FIG. 4  provides a flow chart outlining use of the suite shown in  FIGS. 1 to 3 . This Figure illustrates how the iterative usage of embodiments of the Suite may be used to produce a robust solution for a planning problem. In the Figure, the process starts with the estimation of the stochastic processes. 
       Step  1   400 . 
       [0079]    The practitioner starts the planning process by analysing the nature of the uncertainties or risks associated with his or her forecasts. (Obviously, if the future is known with certainty, then the plan is entirely deterministic and the problem is trivial.) Typically this involves estimating a number of stochastic processes, such as the price of stocks and bonds, or the lifespan and care needs of an individual, for instance. In other examples the stochastic processes may be simulators for real-world processes such as the supply and demand for energy, oil, or telecommunications bandwidth which may be used in the design of equipment and plant. For realism, these models are generally based on historic data samples. A variety of sophisticated statistical tools already exist that are capable of supporting this task. 
       Step  2   402 . 
       [0080]    The next step is to formulate the DSP using the modelling language. As described before, this is most conveniently and uniquely done by describing the problem in a mathematical form that is deterministic, without reference to the structure of the scenarios that will be generated. It suffices to identify which parameters are fixed and which are random. Of course the decision variables are random, and depend on the constraints and objectives that the practitioner specifies. 
         [0081]    These constraints apply consistently throughout time, and without regard to the particular choice of scenario structure. This apparent loss of flexibility, which precludes non-anticipativity constraints for instance, is wholly consistent with the nature of the real-world problems for which DSP is appropriate using the Suite. The major benefit is in a compact representation of the planning problem that need not change with different scenario structures, unlike every other Stochastic Programming (SP) approach. 
       Step  3   404 . 
       [0082]    Once the DSP is formulated, and whilst it is being refined, the practitioner uses the simulation component  206  to simulate the scenarios that are required by the generator component  202  to compile the DSP into the DEP. In this embodiment the asset  166  and the liability  168  simulators are loaded with the parameters estimated in step  1  ( 400  in the Figure). It will be appreciated that there are a plurality of simulators in the simulation component  206  for assets such as stocks and bonds, financial factors such as interest and exchange rates, economic factors such as production and inflation, liabilities such as loans, mortgages and cash flows, and personal events such as sickness or death, together with other, technical and business related ideas. 
         [0083]    Scenarios can be generated individually on demand by the generator component  202  whilst running the solver component  204 , or pre-computed as (sub-)trees which are subsequently ‘walked’ by the tree walker  170  of the solver. The practitioner specifies the time steps and branching structure that are required for each modelling iteration. Typically one starts with a short tree that has few time steps and a low branching factor. But as the model  154  is refined, the number of time steps and branches may be increased, even creating asymmetric trees, in order to refine the solution and prove its robustness. This is done without the need to change the DSP. 
         [0084]    Indeed, by means of the feedback loops shown in the  FIG. 4  (a sequential sampling feedback loop  406 , an adaptive filtering feedback loop  408  and a calibration feedback loop  410 ), it is possible for the suite of components  200  to refine the scenario structure iteratively in a semi-automatic fashion. Sequential sampling provided by the sequential sampling feedback loop  406  is a method of using data obtained from sequential importance sampling based on the expected value of perfect information from the solver to grow the scenario tree only in those areas that require further sampling, thus avoiding redundant input data and maintaining efficiency. Adaptive filtering allows the system to automatically update the model from basic data. 
         [0085]    The calibration feedback loop  410  determines whether coefficients used in the DSP are changing more than may be expected. If this is the case then the DSP may be adjusted in order to reduce this greater than expected change. 
       Step  4   412 . 
       [0086]    With the DSP and scenario structure in place, the practitioner runs the generator component  202  to ‘compile’ the model. The generator component  202  may compile and run the DSP in batch mode, or it can interpret the programming language interactively in a terminal session. As an interpreter it not only provides feedback to assist the user with correct syntax, but it also allows the user to run the solver component  204  iteratively, so that he/she can modify and extend the DSP based on the results (or lack of them) from the solver component  204 . 
         [0087]    This interactive mode is useful for rapid prototyping and development of sophisticated DSP&#39;s. Note that other stochastic programming extensions of third-party mathematical programming languages, unlike the programming language used by embodiments of the current invention, rely on a pre-processing step in compiling these extensions. This means that they do not have this interactive interpretive capability, but can only be used in a more tedious batch mode. 
         [0088]    Furthermore, the programming language used by embodiments of the current invention has specialised extract, display and print commands that can read the results from the solver component  204  and report statistical information about the solution, such as expected values and distributions spanning some, or all, of the scenarios. This capability is not built into other systems, where the scenarios have to be hard-coded, but is convenient for embodiments of the invention providing this feature. 
       Step  5   414 . 
       [0089]    The user invokes the solver component  204 , either interactively or in batch mode, with the ‘solve’ command, just as with any other mathematical programming language. Unlike any other stochastic programming extension, the generator component  202  invokes the solver component  204  directly, writing to and reading from the internal data structures of the solver component  204 . In embodiments in which this feature is provided the responsiveness of the system as a whole is increased. Other stochastic systems, which pass a textual representation of the DEP to another process for it to compile and run do not have this advantage. 
         [0090]    The solver computes an optimal solution to the DEP, compiled from the DSP and the scenario tree (unless the problem is infeasible because of the constraint set of course). As explained earlier, the solver component  204  can compute solutions to real-world problems ten to a hundred times faster than other general-purpose solvers. Which is just as well, because this optimal solution is more or less dependent on the particular set of scenarios generated by the simulators provided by the simulation component  206 . A different sample set will produce a solution that is more or less different. Whether the differences are significant is the subject of subsequent analysis. 
         [0091]    Typically the practitioner will use the suite of components  200  to repeatedly modify the scenario structure to find a balance between the time it takes to solve the problem and the accuracy of the solution. Having found that balance, they may go on to run the model with many different scenario samples to establish the variance of the results. In this respect dynamic stochastic programming is different from deterministic programming: a highly iterative process, rather than right-first-time. 
       Step  6   416   
       [0092]    At each iteration of the model, the practitioner may evaluate the solver&#39;s solution for its realism. Given that the solution may comprise very large numbers of individual forward decisions (the variables at each node of the scenario tree), it is essential to gain an impression of the shape and flow of the solution and its fitness for purpose. It involves comparing the input scenarios (the tree and its branches) with the resulting solution (on average and in distribution). One may view the solution as the equivalent of a decision tree with continuous variables. The term forward decision has been used as the decision must be assessed at a point in time that is in the future. 
         [0093]    This may be better done visually with the visualisation component  208  rather than numerically from the solver component  204 . An advantage of embodiments in which the visualisation component  208  is used rather than the solver component  204  is that the user can quickly spot anomalies and inconsistencies, faulty decision logic, inappropriate outliers, etc. Then they may be able to drill down into the data to diagnose the issue, and correct either the program or the scenario structure. If the issue lies with the simulations, then these can be re-calibrated with feedback from previous iterations of the model. 
         [0094]    Perhaps because stochastic programs have in the past been unrealistically small, other systems have not integrated graphical tools. Previous approaches have sometimes made use of third-party graphics packages, but only ad hoc to illustrate some aspect of a particular problem, not as an integral part of the modelling process. The integrated visualisation component  208  of the suite of components  200  is unique in the field of DSP. 
         [0095]    An example of a suite of components  200  suitable for providing the present invention is provided by Cambridge System Associates Ltd. of 1 Earl Street, Cambridge, CB1 1JR. In this particular suite the generator component  202  is referred to as StochGen™, the solver component  204  is referred to as StochOpt™, the simulation component  206  is referred to as StochSim™ the visualisation component  208  is referred to as StochView™ and the library component  210  is referred to as StochLib™. 
       Example of DSP 
       [0096]      
         [0000]    
       
         
               
               
             
           
               
                   
               
             
             
               
                   
                 # Pioneer CALM Model 
               
               
                   
                 # Initial structure 
               
               
                   
                 # Define the timebase 
               
               
                   
                 # 
               
               
                   
                 # Note that there is no need to define the set of nodes 
               
               
                   
                 # in the scenario tree, nor to define their predecessors, 
               
               
                   
                 # as would be necessary in other programming languages. 
               
               
                   
                 # 
               
               
                   
                 param horizon; 
               
               
                   
                 set times := 0..horizon; 
               
               
                   
                 set start_times := 0..(horizon−1); 
               
               
                   
                 set mean_times := 1..(horizon−1); 
               
               
                   
                 set end_times := 1..horizon; 
               
               
                   
                 # Define the assets &amp; currencies 
               
               
                   
                 # 
               
               
                   
                 set assets; 
               
               
                   
                 set currencies; 
               
               
                   
                 param initial_assets{assets}; 
               
               
                   
                 param initial_cash; 
               
               
                   
                 # Define transaction costs 
               
               
                   
                 # 
               
               
                   
                 param cost; 
               
               
                   
                 param sell_cost := 1 − cost; 
               
               
                   
                 param buy_cost := 1 + cost; 
               
               
                   
                 # Define portfolio constraint parameters 
               
               
                   
                 # 
               
               
                   
                 param min_asset{assets}; 
               
               
                   
                 param max_asset{assets}; 
               
               
                   
                 param max_turnover{assets}; 
               
               
                   
                 param max_borrow{currencies}; 
               
               
                   
                 param max_deposit{currencies}; 
               
               
                   
                 # Get the fixed parameter data and scenario tree-string 
               
               
                   
                 # 
               
               
                   
                 # Note that the tree-string is in an include file, so that 
               
               
                   
                 # it can be changed at will without changing the program 
               
               
                   
                 # 
               
               
                   
                 data “Pioneer.data”; 
               
               
                   
                 include “Pioneer.trst”; 
               
               
                   
                 # Define stochastic rates of return, interest &amp; exchange 
               
               
                   
                 # 
               
               
                   
                 # Here is the first major departure from other programming 
               
               
                   
                 # languages... there is no need to declare large arrays of 
               
               
                   
                 # scenario data, node by node 
               
               
                   
                 # 
               
               
                   
                 # The reference to the simulator data is sufficient for 
               
               
                   
                 # the model compiler to create the DEP at runtime 
               
               
                   
                 # 
               
               
                   
                 param asset_return{times,assets} simulator datasim  
               
               
                   
                 “returns.siml”; 
               
               
                   
                 param asset_exchange{times,assets} simulator datasim  
               
               
                   
                 “exchange.siml”; 
               
               
                   
                 param deposit_rate{times,currencies} simulator datasim  
               
               
                   
                 “deposit.siml”; 
               
               
                   
                 param borrow_rate {times,currencies} simulator datasim  
               
               
                   
                 “borrow.siml”; 
               
               
                   
                 param foreign_exchange{times,currencies} simulator datasim  
               
               
                   
                 “exchange.siml”; 
               
               
                   
                 # Define asset amounts as decision variables, split into 
               
               
                   
                 # bought &amp; sold 
               
               
                   
                 # 
               
               
                   
                 # Notice that the variables are assigned to stages, so 
               
               
                   
                 # that the compiler can declare the corresponding 
               
               
                   
                 # variables in the nodes of the DEP, according to the 
               
               
                   
                 # treestring 
               
               
                   
                 # 
               
               
                   
                 # Again, this avoids the need for large variable arrays, 
               
               
                   
                 # indexed by node as well as time and asset 
               
               
                   
                 # 
               
               
                   
                 var asset_amount{t in start_times, assets} stage t; 
               
               
                   
                 var asset_bought{t in start_times, assets} stage t, &gt; =0; 
               
               
                   
                 var asset_sold{t in start_times, assets} stage t, &gt; =0; 
               
               
                   
                 s.t. initial_rebalance_c{a in assets}: 
               
               
                   
                  asset_amount[0,a] = initial_assets[a] + asset_bought[0,a] −  
               
               
                   
                  asset_sold[0,a]; 
               
               
                   
                 s.t. asset_rebalance_c{t in mean_times, a in assets}: 
               
               
                   
                  asset_amount[t,a] = asset_amount[t−1,a] *  
               
               
                   
                  (1 + asset_return[t,a]) + asset_bought − asset_sold[t,a]; 
               
               
                   
                 # Define currency amounts as decision variables, split into  
               
               
                   
                 deposit &amp; borrow 
               
               
                   
                 # 
               
               
                   
                 var currency_amount{t in start_times, currencies} stage t; 
               
               
                   
                 var currency_deposit{t in start_times, currencies} stage t, &gt; =0; 
               
               
                   
                 var currency_borrow{t in start_times, currencies} stage t, &gt; =0; 
               
               
                   
                 # Balance the source and use of cash 
               
               
                   
                 # 
               
               
                   
                 var cash_sources{t in start_times} stage t, &gt; =0; 
               
               
                   
                 var cash_uses{t in start_times} stage t, &gt; =0; 
               
               
                   
                 # Notice that none of the constraints need take account 
               
               
                   
                 # of the scenario structure 
               
               
                   
                 # 
               
               
                   
                 # Other programming languages would need the constraints 
               
               
                   
                 # indexed by node as well as time 
               
               
                   
                 # 
               
               
                   
                 s.t. initial_cash_sources_t: 
               
               
                   
                   cash_sources[0] = initial_cash + sell_cost * sum{a in assets} 
               
               
                   
                  asset_exchange[0,a] * asset_sold[0,a] + sum{c in currencies} 
               
               
                   
                  foreign_exchange[0,c] * currency_borrow[0,c]; 
               
               
                   
                 s.t. cash_sources_t{t in mean_times}: 
               
               
                   
                  cash_source[t] = sell_cost * sum{a in assets} asset_exchange[t,a] *  
               
               
                   
                  asset_sold[t,a] + sum{c in currencies} foreign_exchange[t,c] * 
               
               
                   
                  (currency_borrow[t,c] + currency_deposit[t−1,c] *  
               
               
                   
                  (1 + deposit_rate[t,c])); 
               
               
                   
                 s.t. initial_cash_uses_t: 
               
               
                   
                  cash_uses[0] = buy_cost * sum{a in assets} asset_exchange[0,a] * 
               
               
                   
                  asset_bought[0,a] + sum{c in currencies } foreign_exchange[0,c] * 
               
               
                   
                  currency_deposit[0,c]; 
               
               
                   
                 s.t. cash_uses_t{t in mean_times}: 
               
               
                   
                  cash_uses[t] = buy_cost * sum{a in assets} asset_exchange[t,a] * 
               
               
                   
                  asset_bought[t,a] + sum{c in currencies} foreign_exchange[t,a] * 
               
               
                   
                  (currency_deposit[t,c] + currency_borrow[t−1,c] *  
               
               
                   
                  (1 + borrow_rate[t,c])); 
               
               
                   
                 s.t. cash_balance_c{t in start_times}: 
               
               
                   
                  cash_sources[t] = cash_uses[t]; 
               
               
                   
                 # Define the wealth terms, before and after rebalancing 
               
               
                   
                 # 
               
               
                   
                 # Once again, there is no need to index by node 
               
               
                   
                 # 
               
               
                   
                 var wealth_before{t in end_times} stage t, &gt; =0; 
               
               
                   
                 var wealth_after{t in start_times} stage t; 
               
               
                   
                 s.t. wealth_before_c{t in end_times}: 
               
               
                   
                  wealth_before[t] = sum{a in assets} asset_exchange[t,a] *  
               
               
                   
                  asset_amount[t−1,a] * (1 + asset_return[t,a] + sum{c in currencies}  
               
               
                   
                  foreign_exchange[t,c] * (currency_deposit[t−1,a] *  
               
               
                   
                  (1 + deposit_rate[t,c] − currency_borrow[t−1,c] *  
               
               
                   
                  (1 + borrow_rate[t,c])); 
               
               
                   
                 s.t. wealth_after_c{t in start_times}: 
               
               
                   
                  wealth_after[t] = sum{a in assets} asset_exchange[t,a] *  
               
               
                   
                  asset_amount + sum{c in currencies} foreign_exchange[t,c] *  
               
               
                   
                  (currency_deposit[t,c] − currency_borrow[t,c]); 
               
               
                   
                 # Define the CARA utility objective 
               
               
                   
                 # 
               
               
                   
                 # Note we use the expected value of a stochastic variable, 
               
               
                   
                 # which would have to be calculated as the average across 
               
               
                   
                 # nodes in other languages 
               
               
                   
                 # 
               
               
                   
                 # This is a proprietary feature of the 
               
               
                   
                 # programming language 
               
               
                   
                 # 
               
               
                   
                 minimize cara_utility_o: 
               
               
                   
                  sum{t in end_times} exp(−wealth_before[t]); 
               
               
                   
                 #Set the portfolio constraints 
               
               
                   
                 # 
               
               
                   
                 s.t. min_asset_c{t in start_times, a in assets}: 
               
               
                   
                   asset_exchange[t,a] * asset_amount[t,a] &gt; = min_asset[a]; 
               
               
                   
                 s.t. max_asset_c{t in start_times, a in assets}: 
               
               
                   
                  asset_exchange[t,a] * asset_amount[t,a] &lt; = max_asset[a] *  
               
               
                   
                  wealth_after[t]; 
               
               
                   
                 s.t. max_turnover_c1{t in mean_times, a in assets}: 
               
               
                   
                  asset_exchange[t,a] * asset_amount[t,a] − asset_exchange[t−1,a] * 
               
               
                   
                  asset_amount[t−1,a] &lt; = max_turnover[a] * wealth_after[t]; 
               
               
                   
                 s.t. max_turnover_c2{t in mean_times, a in assets}: 
               
               
                   
                  asset_exchange[t,a] * asset_amount[t,a] − asset_exchange[t−1,a] * 
               
               
                   
                  asset_amount[t−1,a] &gt; = −max_turnover[a] * wealth_after[t]; 
               
               
                   
                 s.t. max_borrow_c{t in start_times, c in currencies}: 
               
               
                   
                  foreign_exchange[t,c] * currency_borrow[t,c] &lt; = max_borrow[c]; 
               
               
                   
                 s.t. max_deposit_c{t in start_times, c in currencies}: 
               
               
                   
                  foreign_exchange[t,c] * currency_deposit[t,c] &lt; = max_deposit[c] * 
               
               
                   
                  wealth_after[t]; 
               
               
                   
                 # Solve the program 
               
               
                   
                 # 
               
               
                   
                 solve; 
               
               
                   
                 # Display the results 
               
               
                   
                 # 
               
               
                   
                 # This uses features of the StochGen (i.e. the generator component) 
               
               
                   
                 compiler 
               
               
                   
                 # to display the expectation across multiple scenarios, 
               
               
                   
                 # and the individual results by scenario 
               
               
                   
                 # 
               
               
                   
                 # Notice that it does not need to be indexed by node or 
               
               
                   
                 # scenario, as would be the case in other languages 
               
               
                   
                 # 
               
               
                   
                 displaye wealth_before[horizon]; 
               
               
                   
                 displaystoc wealth_before[horizon]; 
               
               
                   
                 displaye{a in assets}: 
               
               
                   
                  asset_exchange[horizon,a] * asset_amount[horizon−1,a] *  
               
               
                   
                  (1 + asset_return[horizon,a]); 
               
               
                   
                 displaye{c in currencies}: 
               
               
                   
                  foreign_exchange[horizon,c] * (currency_deposit[horizon−1,c] *  
               
               
                   
                  (1 + deposit_rate[horizon,c]) − currency_borrow[horizon−1,c] *  
               
               
                   
                  (1 + borrow_rate[horizon,c])); 
               
               
                   
                 # End of program 
               
               
                   
                 # 
               
               
                   
                 # Crucially, this program is much simpler and much 
               
               
                   
                 # shorter than the equivalent in any other mathematical 
               
               
                   
                 # programming language 
               
               
                   
                 # 
               
               
                   
                 # Furthermore, it need not be changed at all to recompute 
               
               
                   
                 # a solution with a different set of scenarios, or even a 
               
               
                   
                 # different scenario tree