The OPTNET procedure includes a number of graph theory, combinatorial optimization, and network analysis algorithms. The algorithm classes are listed in Table 2.1.
Table 2.1: Algorithm Classes in PROC OPTNET
Algorithm Class |
PROC OPTNET Statement |
Biconnected components |
|
Maximal cliques |
|
Connected components |
|
Cycle detection |
|
Weighted matching |
|
Minimum-cost network flow |
|
Minimum cut (experimental) |
|
Minimum spanning tree |
|
Shortest path |
|
Transitive closure |
|
Traveling salesman |
The OPTNET procedure can be used to analyze relationships between entities. These relationships are typically defined by using a graph. A graph, , is defined over a set of nodes and a set of arcs. A node is an abstract representation of some entity (or object), and an arc defines some relationship (or connection) between two nodes. The terms node and vertex are often interchanged when describing an entity. The term arc is often interchanged with the term edge or link when describing a connection.