If the Java applet fails to start due to

To start the applet, click the * Go Networking * button.
Go ahead, click on it now. After clicking, the applet will launch
a new window in which you can build and solve min-cost network-flow problems.

The window that pops up has some control buttons and textfields across the top and bottom. In the middle is a drawing canvas for creating and solving network flow problems.

There are two ways to create a problem. One is to build it up one node at a time. The other is to let the applet generate a random problem having a specified number of nodes. Since the latter is easier to explain, we start with it.

To generate just a random topology, choose the *Build Network*
mode with the choice box and then click on *Generate Random Problem*.

To generate random data for a previously defined topology, choose
the *Edit Supplies/Costs*
mode with the choice box and then click on *Generate Random Problem*.

The textfield labeled * Nodes * can be editted to specify
the number of nodes in the network (the window can be resized as desired
to accomodate larger networks). If the * Seed * field is left blank then
an internally generated seed value will be used and the behavior of the
generator will be different every time the applet is run.
If,
however, a seed value is given (it must be an integer), then that value is
used to seed the random number generator.
Specifying a value for the number of
nodes and for the seed uniquely determines the sequence of problems
generated.

If the second mouse click is not on any existing node, then a new node is automatically created at the clicked location and an arc is created as before.

The applet always initializes the network with one preexisting node, which
is labeled *a*. We refer to this node as the * root node*. It
plays a special role in the following discussion.

By forcing you to build the network arc by arc always using an existing node
for the first click, we guarantee that the network will be connected. Also, we
use those arcs which involved the creation of a new node as the
* tree arcs * for an initial spanning tree.
All other arcs are non-tree arcs. Tree arcs are shown in red.

Note that the root node's supply is automatically set so that the total supply equals the total demand. Hence, there is no need ever to edit the supply at the root node. In this way the applet ensures that none of the problems are trivially infeasible in the sense of a misbalance between total supply and total demand.

In this mode, the supply and cost data disappear and instead you see current
values of * arc flows * on tree arcs and * dual slacks *
(i.e., * reduced costs *) on non-tree arcs. Negative values for any of
these arc variables are highlighted in bright pink. If the network does not
show any pink, then the current spanning tree defines an optimal
solution to the problem. To confirm that a solution is optimal, you can click
on the * Optimal * button. Similarly, if you think that a current
solution clearly demonstates that the problem is primal or dual infeasible, you
can click on the corresponding button to confirm.

To facilitate pivoting, there is a set of artificial arc variables (both flows
and dual slacks) that are initially set all to one but which change as pivots
are done. To keep the canvas uncluttered, these artificial variables are not
displayed unless specifically requested by using the pull-down *Show*
menu at the top of the window. When the artificial variables are being shown,
each one appears just after the corresponding regular variable. If an
artificial variable is negative (i.e., infeasible), it is highlighted in
yellow.
Using the artificial variables appropriately, one can use the pivot tool
to carry out the following
methods from *Linear Programming: Foundations and Extensions*:

- Primal-Phase-I, Dual-Phase-II, Simplex Method
- Dual-Phase-I, Primal-Phase-II, Simplex Method
- Primal-Dual Simplex Method

- Build Network
- Edit Supplies/Costs
- Pivot

One of the options in the *Show* menu is to show *Node Variables*.
These are the dual variables associated with each node. Since none of the three
variants of the simplex method mentioned above use the dual variables in the
pivot selection rule, these values are by default not shown (again, to keep
the network from looking too cluttered). But it is important to be able to get
these values---the *Show* menu makes it possible.
Note that
the dual variables are computed so that the root node's dual is zero.

If all information is shown simultaneously, the network can look quite cluttered. But some effort has been made to prevent overlapping numerical fields. In particular supply/demand data is shown above the node to which it applies, whereas dual variables are shown below the node. Similarly cost data is shown shifted up slightly from the centroid of the arc whereas arc variables are shown shifted down slightly. If nonetheless some data gets clobbered, you can use the mouse to drag (slowly, please) the nodes around some to get a better layout.