Arthur M. Geoffrion
John E. Anderson Graduate School of Management
University of California, Los Angeles, CA, 90095-1481
Introduction: Structured modeling was developed as a comprehensive response to perceived shortcomings of modeling systems available in the 1980s. It is a systematic way of thinking about models and their implementations, based on the idea that every model can be viewed as a collection of distinct elements, each of which has a definition that is either primitive or based on the definition of other elements in the model. Elements are categorized into five types (so-called primitive entity, compound entity, attribute, function, and test), grouped by similarity into any number of classes called genera, and organized hierarchically as a rooted tree of modules so as to reflect the model's high-level structure. It is natural to diagram the definitional dependencies among elements as arcs in a directed acyclic graph. Moreover, this dependency graph can be computationally active because every function and test element has an associated mathematical expression for computing its value.
Using a model for any specific purpose involves subjective intentions. Structured modeling makes a sharp distinction between the resulting user-defined "problems" or "tasks" associated with a model, and the relatively objective model per se. A typical problem or task has to do with ad hoc query, drawing inferences, evaluating model behavior with specified inputs, determining a constrained solution, or optimization, and requires applying a computerized model manipulation tool ("solver"). For certain recurring kinds of problems and tasks, these tools are highly developed and readily available for incorporation into a structured modeling software system.
The theoretical foundation of structured modeling is formalized in Geoffrion (1989), which presents a rigorous semantic framework that deliberately avoids committing to a representational formalism. The framework is "semantic" because it casts every model as a system of definitions styled to capture semantic content. Ordinary mathematics, in contrast, typically leaves more of the meaning implicit. Twenty-eight definitions and eight propositions establish the notion of model structure at three levels of detail (so-called elemental, generic, and modular structure), the essential distinction between model class and model instance, certain related concepts and constructs, and basic theoretical properties. This framework has points in common with certain ideas found in the computer science literature on knowledge representation, programming language design, and semantic data modeling, but is designed specifically for modeling as practiced in OR/MS and related fields (Geoffrion, 1987, Sec. 4).
Structured Modeling Languages: An executable model description language called SML (Structured Modeling Language) fully supports structured modeling's semantic framework Geoffrion (1992). Other languages for (at least parts of) structured modeling also exist, including ones that are graph-based, logic-based, SQL-oriented, subscript-free, or object-oriented. SML can be viewed in terms of four upwardly compatible levels of increasing expressive power. The first level encompasses simple definitional systems and directed graph models such as those found in Harary, Norman and Cartwright (1965). The second level covers more complex extensions of these, spreadsheet models, numeric formulas, and propositional calculus models. The third level encompasses mathematical programming and predicate calculus models with simple indexing over sets and Cartesian products. Finally, the fourth level covers sparse versions of the above plus relational and semantic database models.
The following exhibits from Geoffrion (1987) show an SML schema
(third level) specifying the general structure of the classical feedmix
model, and sample SML elemental detail tables specifying model elements.
The latter, together with the schema, yield a specific feedmix model instance.
MIN (NUTRi) /a/ : Real+ For each NUTRIENT there is a MINIMUM
DAILY REQUIREMENT (units per day per animal).
UCOST (MATERIALm) /a/ Each MATERIAL has a UNIT COST ($ per pound of material).
ANALYSIS (NUTRi, MATERIALm) /a/ : Real+ For each NUTRIENT-MATERIAL
combination, there is an ANALYSIS (units of nutrient per pound of
NLEVEL (ANALYSISi., Q) /f/ ; @SUMm (ANALYSISim * Qm) Once the QUANTITIES are chosen, there is a NUTRITION LEVEL (units per day per animal) for each NUTRIENT calculable from the ANALYSIS.
T:NLEVEL (NLEVELi, MINi) /t/ ; NLEVELi >= MINi For each NUTRIENT there is a NUTRITION TEST to determine whether the NUTRITION LEVEL is at least as large as the MINIMUM DAILY REQUIREMENT.
TOTCOST (UCOST, Q) /f/ ; @SUMm (UCOSTm * Qm) There is a TOTAL
COST (dollars per day per animal) associated with the chosen QUANTITIES.
Space does not permit a proper description of SML's syntax, but a few hints are as follows. Schemas are organized as a tree of paragraphs whose leaves are the genera and whose interior nodes are the modules. The boldfaced part of each paragraph is the formal definition of the genus or module, as the case may be, and the rest consists of documentary comments about the formal part which are informal except for conventions about the use of underlining and upper case. The formal definition of a genus paragraph begins with the name of the genus, a parenthetical statement of definitional dependencies (if any), a slash-delimited statement of genus type, a colon-announced statement of data type if an attribute genus, and a semicolon-announced mathematical expression called a generic rule if a function or test genus. The formal definition of a module paragraph consists only of its name. Note that a schema is always specified independently of any problem or task that might be posed on it. A common problem associated with the above schema is to find values for all Q elements such that all T:NLEVEL elements evaluate to true and the value of the TOTCOST element is minimal.
The structure and sequence of the elemental detail tables are determined procedurally from the schema. Each table is named, has column names that usually coincide with genus names, and has a row for each element of the corresponding genus.
The final figure shows the so-called genus graph associated with
the above schema. It represents definitional dependencies at the level
Structured Modeling Systems: Owing to the design of the underlying semantic framework and of SML itself, SML-based modeling systems can have certain features often lacking in modeling systems of more conventional design, including:
Opportunities: An ample foundation has been laid for the development of software intended for commercial application. To date, experimental studies and a few real applications have taken place in the consumer appliance, food, industrial gases, oil, steel, and tire industries.
Likely topics for future work include discrete event simulation (Lenard, 1993), graph-based modeling (Jones, 1992), integration with database systems (Dolk, 1988), language-directed editors (Vicuña, 1990), object-oriented systems (Muhanna, 1993), model integration (Dolk and Kottemann 1993, Gagliardi and Spera 1995), improved languages for model definition and manipulation, applications to early and late modeling life-cycle phases not supported by conventional modeling systems, and structured modeling-based enhancements and usage disciplines for other modeling approaches and systems. See Geoffrion (1999) for a survey of recent work and selected research directions, and a 65-item bibliography.
See Mathematical model; Model management; Algebraic
Chari, K. and T. Sen (1998). "An Implementation of a Graph-Based Modeling System for Structured Modeling (GBMS/SM)," Decision Support Systems, 22:2, 103-120.
Dolk, D.R. (1988). "Model Management and Structured Modeling: The Role of an Information Resource Dictionary System," Comm. ACM, 31:6, 704-718.
Dolk, D. and J. Kottemann (1993). "Model Integration and a Theory of Models," Decision Support Systems, 9:1, 51-63.
Gagliardi, M. and C. Spera (1995). "Toward a Formal Theory of Model Integration," in I. Maros and G. Mitra (eds.), Annals of Operations Research, 58, 405-440.
Geoffrion, A.M. (1987). "An Introduction to Structured Modeling," Management Science, 33:5, 547-588.
Geoffrion, A.M. (1989). "The Formal Aspects of Structured Modeling," Operations Research, 37:1, 30-51.
Geoffrion, A.M. (1991). "FW/SM: A Prototype Structured Modeling Environment," Management Science, 37:12, 1513-1538.
Geoffrion, A.M. (1992). "The SML Language for Structured Modeling," Operations Research, 40:1, 38-75.
Geoffrion, A.M. (1999). "Structured Modeling: Survey and Future Research Directions," ITORMS, 1:3 (on-line at http://catt.bus.okstate.edu/itorms/).
Hamacher, S. (1995). Modeling Systems for Operations Research Problems: Study and Applications, Ph.D. Dissertation, Industrial Engineering, Ecole Paris Centrale, Paris, 235 pages (in French).
Harary, F., R. Norman and D. Cartwright (1965). Structural Models: An Introduction to the Theory of Directed Graphs, Wiley, New York.
Jones, C.V. (1992). "Attributed Graphs, Graph-Grammars, and Structured Modeling," Annals of Operations Research, 38, 281-324. (Special volume on Model Management in Operations Research edited by B. Shetty, H. Bhargava, and R. Krishnan.)
Lenard, M.L. (1993). "A Prototype Implementation of a Model Management System for Discrete-Event Simulation Models," Proceedings of the 1993 Winter Simulation Conference, IEEE, Piscataway, NJ, 560-568.
Maturana, S. and Y. Eterovic (1995). "Vehicle Routing and Production Planning Decision Support Systems: Designing Graphical User Interfaces," International Transactions in Operational Research, 2:3, 233-247.
Muhanna, W. (1993). "An Object-Oriented Framework for Model Management and DSS Development," Decision Support Systems, 9:2, 217-229.
Neustadter, L., A. Geoffrion, S. Maturana, Y. Tsai and F. Vicuña (1992). "The Design and Implementation of a Prototype Structured Modeling Environment," Annals of Operations Research, 38, 453-484. (Special volume on Model Management in Operations Research edited by B. Shetty, H. Bhargava, and R. Krishnan.)
Vicuña, F. (1990). Semantic Formalization in Mathematical Modeling Languages, Ph.D. Dissertation, Computer Science Department, UCLA.
Wright, G., N.D. Worobetz, M. Kang, R. Mookerjee and R. Chandrasekharan (1997). "OR/SM: A Prototype Integrated Modeling Environment Based on Structured Modeling," INFORMS J. on Computing, 9:2, 134-153.