Skip to main content
main-content

Über dieses Buch

DLP denotes a dynamic-linear modeling and optimization approach to computational decision support for resource planning problems that arise, typically, within the natural resource sciences and the disciplines of operations research and operational engineering. It integrates techniques of dynamic programming (DP) and linear programming (LP) and can be realized in an immediate, practical and usable way. Simultaneously DLP connotes a broad and very general modeling/ algorithmic concept that has numerous areas of application and possibilities for extension. Two motivating examples provide a linking thread through the main chapters, and an appendix provides a demonstration program, executable on a PC, for hands-on experience with the DLP approach.

Inhaltsverzeichnis

Frontmatter

The D L P Nucleus Model

Chapter 1. Motivating Examples

Abstract
This introductory chapter describes two very simple resource decision problems. Its purpose is to provide
  • a detailed illustration of the D L P nucleus optimiz ation model;
  • examples of the D L P format interface, a low-level language for specifying a model to the optimization routine;
  • examples of the output format used to return an optimal solution.
John Lawrence Nazareth

Chapter 2. D L P Nucleus Model

Abstract
We now describe the D L P approach to modeling a resource decision problem. We will discuss various aspects of model creation and clarify the discussion with the examples of Chapter 1. Our primary goal is to describe the basic structure of the D L P nucleus, i.e., the gist of the D L P approach to conceptualizing and representing a general resource decision problem in the form of a set of decision alternatives with associated constraints and objectives. The modeling enterprise itself, which seeks to create a D L P model for a particular resource and to assert its validity, is treated much more briefly here. It will be discussed in more detail in Part II of this book within the context of a variety of practical applications.
John Lawrence Nazareth

Chapter 3. The DLPFI Language

Abstract
Once a model has been formulated along lines described in the previous chapter, it must be specified to the D L P decision support system using the D L P format interface language, henceforth called DLPFI (pronounced ‘Delphi’). Examples of this low-level language have been presented in Chapters 1 and 2. We now give a more detailed and complete description of DLPFI, which has been designed with the following objectives and usage in mind:
1.
It provides the means for making a precise statement of a D L P model to the D L P decision support system, in much the same way that standard MPS input format provides the means for precisely specifying a linear programming model to a Mathematical Programming System, for example, MINOS (Murtagh and Saunders [1983]). MPS input format is very rigid—character and numeric data must be provided within specific column ranges in each input record. It is, in essence, a set of conventions for specifying the non-zero elements of a large, sparse LP matrix. In constrast, much of the DLPFI input data is format-free, and local and global constraints and objectives can all be specified with considerable flexibility. Each DLPFI data record has a specific meaning in relation to a D L P model. Thus DLPFI can be viewed as a low-level, simple, very easy-to-learn language for D L P modeling.
 
2.
In conformity with a principle used within most modern modeling systems, DLPFI provides a mechanism for separating D L P modeling and optimization phases. Standard MPS input format plays an identical role vis-à-vis the linear programming model/algorithm interface.
 
3.
DLPFI can serve as a target language for user-supplied front-end routines that are written in a high-level programming or modeling language and can accept data in a more convenient, application-specific way. In standard linear programming, such a set of routines is called a ‘matrix generator’. Here, ‘D L P model generator’ would be the corresponding analog.
 
4.
DLPFI is designed to be extensible, in order to facilitate the implementation of D L P model/algorithm enhancements discussed in Chapter 10.
 
John Lawrence Nazareth

Chapter 4. D L P Output Format

Abstract
The D L P output format is a set of conventions used to return an optimal solution. As with the input format, two types of usage are envisioned, namely:
1.
The D L P output can be read and manipulated directly by a decision maker in order to obtain information on the optimal solution that has been returned, or on the nature of the infeasibility, if the problem specified has no feasible solution.
 
2.
In analogy with standard linear programming, a user-supplied routine, called a report generator, can be written to turn the D L P output information into a more presentable form—tabular, histogram, graphical or pie-chart—as suits the needs of the application at hand.
 
John Lawrence Nazareth

Usage

Frontmatter

Chapter 5. Philosophy

Abstract
Traditional operations research models for resource decision problems are often large-scale, dependent on large quantities of unreliable data, and implemented as ‘black-boxes’ that are inflexible and difficult to extend or modify. The assumptions on which such models are premised can change during the long lead-time required for their development. And, not infrequently, their overly-detailed prescriptions come into conflict with the intuitions and experience of decision makers for whom the models are intended.
John Lawrence Nazareth

Chapter 6. Modeling Issues and Applications

Abstract
Modeling issues raised in Chapters 1 and 2 are now explored in more detail within the context of resource decision problems from several application areas, in particular:
  • range, timber, multiple-use;
  • infrastructure rehabilitation/maintenance, in particular, for highway pavements;
  • agriculture, irrigation, water supply;
  • energy generation, in particular, hydroelectric energy;
  • other potential applications, for example, soil-conservation, land reclamation, mining, pest control and aquaculture.
John Lawrence Nazareth

Techniques

Frontmatter

Chapter 7. D L P Nucleus Mathematical Model

Abstract
The description of the D L P nucleus model of Chapter 2 is enlarged in this chapter. In particular, we formulate a linear programming model that is mathematically equivalent to it. This equivalent LP model is tot generated explicitly by the D L P system, but serves as an intermediary that is very useful for clarifying the description of the D L P nucleus model in this chapter, and for describing the techniques used to solve it in the next.
John Lawrence Nazareth

Chapter 8. The D L P Algorithm

Abstract
The D L P algorithm applies dantzig-Wolfe decomposition to the equivalent linear program (7.10) of the previous chapter, and exploits substantial simplifications that arise from the special structure in this linear program, in particular, from the network specification of the decision alternatives. It circumvents having to generate all decision alternatives (paths in the networks) explicitly, working instead directly on the D L P networks and extracting paths as needed. We emphasize again that the quivalent linear program (7.10) is not generated explicitly.
John Lawrence Nazareth

Chapter 9. Implementation of the D L P Nucleus

Abstract
A prototype decision support system that implements the D L P nucleus is described in this chapter. This carefully designed computer programhenceforth called DLPEDU—comprises several thousand lines of Fortran-77 code, and its implementation was a very challenging undertaking. It is neither possible nor desirable to describe this implementation in complete detail in the present chapter. However, we will overview its principal features, in particular:
  • the main data structures around which the implementation is built;
  • the programming practices employed in implementing the data structures and the principal subroutines of the system. The function of each such subroutine is briefly summarized along with the overall pattern and hierarchy of subroutine calls;
  • the validation and testing of the implementation and the debugging and tracing aids that are included.
John Lawrence Nazareth

Extensions

Frontmatter

Chapter 10. Stochastic and Other Extensions

Abstract
In this concluding chapter, we extend the DP L P model/algorithm and associated decision support system in order to incorporate uncertainty of data. Motivation for D L P optimization under certainty (stochastic extension of the model) can be found in Chapter 6, Subsection 6.2.2.
John Lawrence Nazareth

Backmatter

Weitere Informationen