Min Net Path and Min Span Tree with ORMSware Discrete Event Simulator
Objectives
Note: Skip Background section below to General Approach section if you would like to get right to explanation of MP and MST problems and ORMSware algorithm for solving both.
Background
[First few minutes of https://vimeo.com/392474632 (Discrete-Event-Simulation-Powered Programming) covers the background provided here.]
An important evolutionary step in discrete event simulation (DES) was the onset of simulation language systems. There was an article in Interfaces sometime in late 1970s or early 1980s about the state of DES at the time.
Reporting on results of a survey on what Operations Researchers (Decision Scientists) preferred to use for developing simulations at the time, the article said (to the best of my recollection) that 71% of simulations were written mostly from scratch, typically in Fortran 77, and that what any given organization used for sim depended on the preference of the dominant analyst in the group.?
SIMSCRIPT was the simulation language system analysts were using to model operations and performance of cruise missiles in Systems Analysis Directorate at HQ, US Army Armament Command at Rock Island Arsenal in the early 1970s. I never used it then or later but from the thick listings I recall various analysts perusing, I think the systems they were simulating were large, and the analysts were doing quite a bit of programming.?
I came to know about SLAM and SIMAN in early 1980s and used SIMAN/CINEMA and Micro Saint to develop several models for our Administrative Process Simplification (APS) projects at [Lockheed] Martin Marietta. Scope of APS expanded to analyze a variety of problems, including engineering processes such as Max Air Loads analysis for TITAN space launch vehicles. I liked using Fortran exit available in SIMAN/CINEMA to capture process steps, durations, and resource requirements in text files for quick implementation of those simulations (in 1988, long before process reengineering became all the rage in the industry).
Next evolutionary step I recall Interfaces covering was simulators (parameter-driven simulation systems). APS projects at Lockheed Martin were already there with homegrown systems when that article came out. Getting process network information from text files, while very helpful in the beginning, had reached its limits and I had developed SPIF (Simulation for Process Improvement and Facilitation), and later SURGE (for "unconstrained reengineering and growth...," I think!).
SURGE was not only parameter-driven but the models built with it were also compiled to create standalone EXEs that would execute without the presence of SURGE. Micro Saint in Boulder provided some of the information I needed on the innards of Micro Saint so that I could use it to collect, map and print process/problem networks and feed model's network data into SURGE.
Paradigm shift to simulators in the commercial sector seemed to have been caused also by the desire to eliminate virtually any programming for developing simulations. That certainly was a great goal, but it seemed that that too would eventually constrain analysts with insufficient flexibility.
Serendipitously, I was drawn to a perspective of viewing discrete event simulation as a programming problem (though I am a decision scientist and not an IT professional) and gravitated towards an approach of relying on unconstrained programming to complement the parameter-driven part of discrete event simulators, rather than to follow the masses towards attempting to totally eliminate programming from simulation modeling.
In SPIF and SURGE problems were formulated as birth-and-death systems using queuing networks and a Customer-Surrogate, one-to-many association paradigm in which entities fanned out and flowed through task/process networks. Now OMRSware uses a similar paradigm but with the addition of network hierarchies, accommodating nested logical networks under nodes as well as arcs.
As in SPIF/SURGE "Customers" arriving are given tokens at "Arrival" into the system (birth), and tokens are collected back at "Departure" (death) for reuse. Surrogates (or probes or other descriptive/communicative names fitting the context of the problem) represent Customers as they (probes) fan out and travel through the problem/solution network evoking calculations and other tasks/logic specified by the modeler.
General Approach
It occurred to me one day at [Lockheed] Martin Marietta (in 1988) that simulators such as SURGE leveraging network structure of problems would already have the capability to solve shortest and longest path/route problems. Colleagues were skeptical but discovered that I had already tested it and it was a breeze to implement both solutions in SURGE. They tried several examples in their collection to break such off-the-wall notions, to no avail. Back on track, it never occurred to us at the time to investigate solving Minimum Spanning Tree problem using the same general approach. Better 34 years later than never, I'd say!
This article shows how both MP and MST problems can be solved with ORMSware, using essentially the same approach on both. There are numerous videos and articles on MP and MST on the Internet. Algorithmically, the approach here is not different from most of them. The difference here is mostly in terms of ease of implementation, because ORMSware (or any network-structured modeling system in general) has the approach already in it. Almost.
The strategy, just as the general approach to both MP and MST problems, is to use the greedy approach, of course. That is to always make the best possible move at any given point without considering if that move might end up costing more in the long run. However, as people in disciplines using these algorithms know, this strategy does not mean simply taking shots in the dark and hoping it all works out in the end. It is based on logical/mathematical proof that the strategy will yield the MP and MST answers we are seeking.
Min Path (MP) problem statement
Given a connected, undirected network of nodes and arcs (such as the network in the black rectangle in example below, but with any number of nodes and arcs), find the shortest path between any desired pair of nodes.
Minimum Spanning Tree (MST) problem statement
Given a connected, undirected network of nodes and arcs, find a set of arcs that connects all nodes in the network, yielding the lowest sum of "arc weights." Arc weights imply units of measurements, such as time, distance, cost, mass, etc.
The need to "see" when blindfolded
What those who are unfamiliar with our discipline (Operations Research/Decision Science) tend not to realize is that models, for solving problems such as the two defined above, cannot physically "see" a network as human beings can by looking at an image such as the one you see below.
To appreciate what is involved, one needs to imagine trying to solve (say) the two problems above blindfolded. All you will know at the outset is, in your mind's eye, where you are, what immediate connections you have to places you can get to in one hop, and how far each place is. Merely from the information just mentioned, one probably has better appreciation now for the nature of these very interesting puzzles.
Finding an MP solution
Since MP is simpler than MST to implement with ORMSware, and to explain, let us use MP for discussing the algorithm. Extending the discussion then to cover MST will be easier.
For the reader's convenience, this article's cover image with the network example and algorithm logic network is repeated here.
In the image above, nodes (rectangles) and arcs on the left show the program containing the MP/MST algorithm, and nodes (circles) and arcs on the right show the data network on which the algorithm operates. The heart of the MP/MST algorithm implemented here are displayed on the yellow rectangle background (portrait orientation) above.
To get started, let us consider minimum path from node A to node J in the data network. There is more than one MP in this A-J problem. Multiple minimum solutions will have the same final answer regardless of the MP taken to get from A to J. The path ORMSware-based algorithm found has total weight of 10 measurement units. Here's the path it took...
Path starts at A (top row, 4th col), hopping to E (5th col). That is because the A-to-E successor arc of A has the lowest weight of 1.00000 (6th col) compared to A-to-B and A-to-D successor arcs. Choosing greedily the same way the algorithm then hops from E to D with an arc weight of 2.00000, then D to H, etc.
领英推荐
For better insight into how the simulator's events queue automatically sequences and schedules all these hops with no extra work from the modeler, you might want to peruse a file at the link below. It contains a log of the moves ORMSware Simulator made to find an optimum (minimum) path from A to J.
https://www.ushar.com/ORMSware/Models/MinSpanTree/Output/MP-EventsQ.TXT (Ctrl-Click to open in new window. Else LinkedIn will return you to top of article.)
In the table above, notice that the Clock column (last col) and the Running Total Weight column (col before the last) have same numbers. That is because we are modeling the units on simulation clock to be the same as the performance measure (abstractly called "weight").
During each hop the simulator adds the Duration of the hop to the simulation clock, which is exactly what we do to get the accumulated/running total "weight" during each hop. Here in the MP problem we are interested in total weight accumulated while connecting A to J. In MST problem, however, we are not only interested in connecting A to J, but also to all other nodes in the network. This can be done by using this same MP algorithm but ignoring the Clock. We will discuss this in the upcoming MST section.
Before MST, however, let us examine the path ORMSware takes if we ask for Min Path from J to A rather than from A to J as we did earlier. Here's the path...
The hops the simulator found from A to J and J to A are different but the Min Path is still 10 units of "weight."
For ease of explanation let us assume now that the unit of "weight" here is an hour.
MP Algorithm Summary (Min Path between any pair of nodes in a network)
Step 1: From specified Source data node launch probes to all feasible successor nodes.
In this case we start the search at node A. Successor nodes are nodes that are connected to any given node. In the case of node A, successor nodes are B, D and E. Feasible nodes are nodes that have not yet been fathomed/visited at the time of a launch. ORMSware simulator then schedules the landing of these probes on destinations B, D and E based on the transit times for reaching them from A.
Step 2: When a probe lands on its destination node, repeat Step 1 for that node, provided (a) it is not the Sink/Target node (in this case node J), or (b) the destination node was not fathomed while the probe was in transit. If destination node was fathomed while the node was in transit, discard the probe. If the destination node is the Sink/Target node, we have reached the goal.
Rationale for discarding probes
We discard a probe when the node it is destined for has already been fathomed. That is because a node gets labeled as fathomed only when a probe reaches it while it is still unfathomed. Therefore, it is pointless to send a probe to a fathomed node, because it implies that a probe with a superior thread/path has already been at the destination node and that the later arriving probe cannot possibly overtake the earlier probe to reach the Target in MP. In MST, fathomed destination node automatically renders any incoming probe disabled.
Advantage of Customer-Surrogate paradigm in MST algorithm
In discussing this solution approach in ORMSware I have leaned towards referring to entities that represent Customers as probes rather than surrogates (please see Background section if you need to know more about all that). There is only one Customer in this MP/MST algorithm, and that is the default Customer already present in the system. Its ID is zero and its name is T0-C0.
Very first column in the A-to-J Min Path table (the first table above) shows names of surrogates that traversed each segment (arc) in this MP. Name of the very first surrogate/probe in the table, S23-T0-C0, indicates that it is Surrogate 23 (consider it a random name) representing Token Zero, which in turn represents Customer Zero.
When a node has multiple Exit arcs, probe/surrogate at that divergence node may need to be duplicated. These probes become independent of one another and properties of diverged probes would likely be transformed as they traverse the network. In time (simulated time, that is) a probe may carry little resemblance to its siblings, even while traversing immediate successor arcs of a divergence node. However, these spawned surrogates have continuous relationship with their Customer. This characteristic is quite helpful in tracking node visitation history of surrogates in ORMSware implementation of MST algorithm.
Note: In case you are wondering, yes, it would have been possible to label node visitations directly by using a one-dimensional logical variable array corresponding to the number of data nodes in the problem. But then I wouldn't be able to talk about the nice Customer-Surrogate arrangement which comes in handy often.
MST Algorithm Summary (Min total weight connecting all nodes, no cycles)
ORMSware implementation of MST algorithm is the same as MP algorithm, with two simple exceptions in Step 2:
a) Stopping rule. In MP we stop when Sink/Target node is reached. In MST we stop when all nodes are connected/fathomed, without creating cycles.
Checking to ensure there will be no cycles in solution is implicit in algorithm logic.
b) We do not let the simulation clock advance. The easiest way to do that is to subtract simulation clock time from the expression for arc weight on every successor arc. That can be done in the expression for Duration of every arc in play. Thus, when the simulator adds arc Duration to the existing Clock time to schedule completion time of an arc event, the automatic clock advance gets neutralized, and the completion time becomes same as Duration time (weight expression) of the arc. (Arc Duration = Arc Weight Expression - Clock) ==> Arc Completion = Clock + Arc Weight Expression - Clock ==> Arc Completion = Arc Weight Expression.)
Note: There is only one arc in this algorithm with expression for Duration. That is arc [17] over the yellow rectangle (portrait orientation) in the Visio diagram showing the logic of the algorithm. This is an abstract arc representing actual arcs connecting data nodes in the network in the black rectangle on the right side of the image. Other arcs in the Visio network have no expressions entered. The simulator treats their Durations as non-factors. Here is an image of arc [17]'s Duration property. The lines in green/blue are inactive logic...
File at link below provides a log of the moves ORMSware Simulator made, starting at node B to find a Minimum Spanning Tree in the network. All Min Span Trees starting at any node in a connected, undirected network will have the same total weight (14 in this problem).
https://www.ushar.com/ORMSware/Models/MinSpanTree/Output/MST-EventsQ.TXT (Ctrl-Click to open in new window. Else LinkedIn will return you to top of article.)
Table below is a summary of the above log showing a MST in the example network...
An inverted/negative image of the data network in black rectangle in this article's cover image is repeated below for your convenience so that you can print it if you like to follow the log showing the algorithm as it executes.
I will post all files promised at the top of this article (under Objectives) in a Zip file, and tie up other lose ends, if any, after the holidays.