Problem-solving tool for network and enhanced network models

By Joan M. Donohue

Many operations research problems involve developing a mathematical model of a real-world system. One of the first steps in the model development process is often drawing a diagram of the system under analysis. Such visual representations can enhance understanding of the system and its model. Network models of systems such as urban transportation, telephone communications, and natural gas distribution can be easily displayed in graphical form using two types of entities: nodes and arcs. Nodes represent locations that are interconnected by unidirectional arcs or links. Links might represent streets in a transportation network, telephone lines in a communications network, pipes in a natural gas distribution network or the flow of money between time periods in a capital budget.

Solution methods for network models generally take advantage of special structures inherent in the model in order to efficiently reach an optimal solution. However, network models can also be formulated as Mixed Integer Linear Programming (MILP) problems and solved using standard techniques based on the simplex algorithm.

NETWK, the software package under review, translates network diagrams into solvable MILP formulations. The optimal solution is then determined using standard mixed integer linear programming software. Many types of network and enhanced network models can be formulated and solved with NETWK. For example, network problems such as shortest path, maximum flow, minimal spanning tree, transportation, assignment, critical path, multi-commodity flow and the traveling salesman problems can be represented and solved with the NETWK software. In addition, problems that may not initially be thought of as networks may both be modeled and visualized as enhanced NETWK networks. For example, the classic variable proportions linear program known as the diet problem.

NETWK implements traditional networks with a small set of enhancements. First, NETWK allows groups of network elements (links or nodes) to be defined and maximum and/or minimum levels to be defined for the total flows over those groups. Second, the flows through a specified network element may be required to be zero unless the flow through another specified network element (or network element set) is at its maximum. Finally, the flow through a particular network element may be constrained (maximum, minimum or equality) by a quantity proportional to flow through another network element or group. These enhancements are often used to relate flows in unconnected subnetworks. As a result of these enhancements, the set of problems representable by NETWK can be shown to be equivalent to the set of problems representable by mixed integer linear programs.

Using the Program
The NETWK program operates in the Windows environment. The first window that the user encounters is the network applications window shown in Figure 1. At the top of the screen is a command line menu bar and a speedbar menu. When a new file is opened, a dialog box allows for selection of the size and number of pages for the network diagram. The next screen is the network-building window shown in Figure 2. The command line menu bar is now extended to include network-building features and there is a command palette that provides easy access to nine tools used in the model-building process.

Building a network diagram involves the placement of nodes and links (arcs) in the network window. For example, clicking on the plain circle in the command palette creates a standard node at the location selected in the network-building window. A node dialog box (see Figure 3) requests information regarding the supply, market demand and unit prices at the node. Zero is the default value for each of these parameters (flow neither originates nor terminates at nodes using the default parameter values). Supply parameters specify the unit price and number of units originating at the node, and market parameters specify the unit price and number of units terminating at the node.

After entering a pair of nodes on the network diagram, the nodes can be connected with a link. The upper-right command palette icon is used to create links between nodes. Placing a link in the network involves clicking on the starting and ending nodes, then filling in the requested information in the link dialog box (see Figure 4). Min and max refer to the number of units of flow that can simultaneously pass through the link (a max of -1 means there is no upper bound). Rate is the price per unit of flow and shrink specifies the increase or decrease in flow (e.g., a shrink value of 0.98 indicates that for each unit entering the link, 0.98 units depart the link). The default values for a link specify unbounded flow, no cost and no shrinkage.

The command palette offers a number of different node symbols. Choosing the tree, oil well, factory, or plain circle results in the dialog box shown in Figure 3. (Other node symbols can be customized by using appropriate third party software.) Text can be added to the network by using the "ab" icon in the command palette. Except for node names, parameters associated with links and nodes do not appear on the network diagram. Therefore, users may want to annotate the diagram with price and unit flow information. Parameter information is, however, immediately accessible by double clicking on any node or link on the diagram of interest.

Figure 5 illustrates a simple transshipment network with two supply nodes, two transshipment nodes, two market nodes, and eight connecting links. Since the parameters of the nodes and links do not appear on the diagram but must be individually queried, the user must view the spreadsheet form of the network in order to see simultaneously all the parameter specifications. NETWK can store the model information in a spreadsheet that can be viewed by clicking on the speedbar spreadsheet icon. The top of the spreadsheet for the transshipment network is shown in Figure 6. The model diagram and parameter information is stored in a Windows document file with extension .nwk and the spreadsheet formulation may be stored in a .dat file as a tab delimited ASCII file or in an EXCEL .xls file.

In addition to nodes and links, the NETWK model menu (see Figure 2) allows users to include the following: constraints on individual flows and prices, constraints on and between groups of nodes and links, required nodes and links, and metanodes. A metanode is a node on the network diagram that is itself an .nwk document. This generalization allows the user to encapsulate different parts of a large model into separate networks; and, for example, enables the user to hierarchically structure the top level of the model to show only those portions of the network that are of most interest.

Upon completion of the network diagram, NETWK can be used to translate the network into an MILP formulation that can be solved using standard linear programming solution techniques. The network is formulated as a maximization problem; that is, the objective is to use the least costly supply, transport units via the least costly links, and sell units at the highest market price. If the specified network has only revenues, NETWK automatically maximizes those revenues; if it has only costs, NETWK automatically minimizes those costs; and if the network has both, it automatically maximizes the net profit.

To run an optimization of a network model, optimize is selected from the model menu bar (see Figure 2) or the optimize speedbar icon. The MILP software then solves the network flow problem (while you wait) and overlays the solution on the original network. Figure 7 illustrates the optimal solution to the transshipment problem. The maximum profit, as well as revenue and costs, is provided and the optimal path through the network is highlighted (in your choice of color and line thickness). Optimal path parameter values may be viewed individually by double clicking on any node or link in the solution path or all at once by clicking on the speedbar spreadsheet icon.

The solution output from the optimization of a network is stored in two files. The route file (.rot extension) contains information about the supply to market flows in the optimal solution. The report file (.rpt extension) is a spreadsheet that contains optimal flows on each link as well as information about the utilization of supply and market quantities. Figure 8 illustrates the spreadsheet form of the report file, which is accessed by clicking on the speedbar spreadsheet icon. In this transshipment example, the optimal solution specifies that 90 units are to be shipped from Supply B to Market A via Transshipment Location 1. Revenues of $1,160 and supply costs of $1,150 lead to an optimal profit of $10.

Features and Capabilities
In addition to building networks graphically (developing the .nwk file as explained previously), users can build a network using a spreadsheet representation of the model. The NETWK software will generate the network diagram and formulate the model as an MILP problem using the spreadsheet version of the network (the .dat file). This feature adds flexibility to the modeling process and is especially useful for large and cumbersome network diagrams, for systems already being analyzed with a spreadsheet package, and for large models produced automatically from corporate databases.

Another nice feature of the NETWK software is its ability to handle two network modeling approaches simultaneously. Traditional network algorithms use one of the following two approaches for representation of the underlying model structure: 1.) elements are nodes and connections are links; and 2.) elements are links and connections are nodes.

Since NETWK allows specification of price and unit flows on both nodes and links, the two modeling approaches can be combined in one network.

Conventional network representations generally require a connected graph. With NETWK, however, the graph need not be connected because there are many ways of jointly constraining unconnected components of a network. Another interesting aspect of the software is that, unlike many algorithms for network programming, the network enhancements in NETWK avoid the need for dummy nodes and links so that the network model is as similar as possible to the actual system being modeled.

There are other capabilities of the software that deserve mentioning. In addition to a linear objective function, NETWK can handle piece-wise linear, step, convex and quadratic functions. Logical conditions such as negation, conjunctions, inclusive and exclusive disjunctions, and implications can be represented. Network diagrams can also be enhanced by superimposing them on background bitmaps of the user's choice such as a bitmap of the world for transportation systems. Lastly, NETWK is a useful tool for formulating and solving a wide variety of operations research problems, such as:

Potential Improvement
An "alpha version" of the NETWK software was reviewed for this article. There was no on-line help facility and formal documentation was not yet available. Therefore, any suggestions made here regarding potential improvements may not be applicable to the "release version" of the product. Well-prepared documentation is absolutely necessary before releasing the final version of NETWK. Hands-on tutorials that set up and explain examples of typical network flow problems (assignment, max flow, shortest route, transportation, etc.) would be useful for beginners.

After learning to use NETWK at the beginner 1evel, I found only a few features that could use improvement. For example, when specifying a node name, spaces are accepted, but anything typed after a space is ignored. The user should be warned of this to avoid duplicate node names that result in errors when running the optimization. Also, the network diagram includes only nodes, links and node names, and parameter values cannot be automatically placed on the graphical representation of the network. It would be nice if the user had the choice of whether or not to include node and link parameter specifications on the network diagram.

Overall, I found the NETWK software to be a useful problem-solving tool for network and enhanced network models. Developing models graphically, as opposed to mathematically, has the advantage of being less likely to lead to formulation errors, as does quick turnaround between problem formulation and solution presentation. Furthermore, visual representations of systems are much more appealing to managers than mathematical formulations. The software is a simple, powerful enhancement to traditional network constructs. The software would also be useful to academics and practitioners for both research and graduate level coursework in linear and network programming, and for solving large, complex optimization problems.

Joan M. Donohue is an associate professor of Management Science in the College of Business Administration at the University of South Carolina.
To view the NETWK vendor comments and product information, click here.

Wanted: Software Reviewers
Saba Bahouth, OR/MS Today software review editor, is in the process of enlarging the pool of software reviewers. Individuals interested in reviewing software for OR/MS Today should contact Bahouth directly at the University of Central Oklahoma, College of Business Administration, Edmond, OK, 73034-5209; telephone: (405) 341-2980, ext. 2163; Fax: (405) 330-3821; E-mail:

OR/MS Today copyright © 1995 by the Institute for Operations Research and the Management Sciences. All rights reserved.
Click here to return to the table of contents.