A network optimization tool
Copyright 2001 A.V. Hill Associates 10316 Meade Lane Eden Prairie, MN 55347 USA ahill@[Link] 952-942-56790
Netsolver is a network optimization tool that can quickly find the optimal solution to a wide variety of problems. All you have to do is to define the network of arcs on the "arcs" worksheet, and then go to the "optimize" worksheet and click "start." Netsolver quickly finds the minimum cost flow through the network that satisfies all of the arc constraints -- and then reports the results on the optimization worksheet. A network is defined in terms of nodes and arcs. Arcs are defined in terms of a beginning node label, an ending node label, a minimum flow, a maximum flow, and a cost per unit flow. Node labels can be of any length, are not case sensitive, and can include special characters (including internal blanks). You must have one node labeled as the "source" node and another as the "sink" node. The algorithm will follow the conservation of flow rule which states that the flow going into an arc must equal the flow going out of an arc. You can have more than one arc between any two nodes -- but Netsolver will always put flow through the cheaper arc first. Netsolver uses "short" integers for the minimum flow, maximum flow, cost/unit flow, and the flow variables. So be careful that you don't have a cost or flow that is greater than the largest "short" integer, which is 32,767. It is okay, however, for the total cost for an arc or for the solution to be greater than this value. Do not use any decimals anywhere in Netsolver. This code is an implementation of the Ford and Fulkerson out-of-kilter algorithm. This is not the fastest algorithm available -- but is still quite fast and meets the needs of most users. The student version of the code is limited to 20 nodes and 100 arcs. Netsolver is an implementation of the Ford and Fulkerson out-of-kilter algorithm. This is not the fastest algorithm available -- but is still quite fast and meets the needs of most users. The student version is limited to 20 nodes and 100 arcs. The premium edition with over 1,000 nodes and 10,000 arcs is available from the author.
Netsolver is a powerful way to handle a variety of important single-commodity standard problems such as (1) the assignment problem, (2) the transportation problem, and (3) the transshipment problem. Multiple period problems can be handled easily by "shipping" product from one period into the next (with the appropriate carrying cost). The model can be applied to shipping problems, shortest path problems, dynamic demand lotsizing problems, and many others.
Revised 4/7/01
Disclamer: The author makes no guarantees that this works correctly!
Arcs
From Source Source Source Source Source A1 A1 A1 A1 B1 B1 B1 B1 C1 C1 C1 C1 D1 D1 D1 D1 E1 E1 E1 E1 A2 B2 C2 D2 E2 To A1 B1 C1 D1 E1 B2 C2 D2 E2 A2 C2 D2 E2 A2 B2 D2 E2 A2 B2 C2 E2 A2 B2 C2 D2 Sink Sink Sink Sink Sink Minimum Maximum Cost/unit flow flow flow 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 0 1 2 0 1 2 0 1 5 0 1 6 0 1 2 0 1 4 0 1 3 0 1 4 0 1 2 0 1 4 0 1 7 0 1 6 0 1 5 0 1 3 0 1 7 0 1 1 0 1 6 0 1 4 0 1 6 0 1 1 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0
Optimize
Click to start or stop the optimization
Start
Summary of the results
Number of nodes 12 Number of arcs 31 Final status Feasible Elapsed time (seconds) 0.2 Total cost 10 Number of iterations 813
Stop
Netsolver student edition program limits: Maximum number of nodes Maximum number of arcs
20 100
Arc results (If a feasible solution is found, only arcs with Cost x Flow greater than zero are shown.)
From node A1 B1 C1 D1 E1 To node B2 C2 A2 E2 D2 Minimum 0 0 0 0 0 Maximum Cost/unit 1 2 1 4 1 2 1 1 1 1 Flow 1 1 1 1 1 Cost x Flow 2 4 2 1 1