The Network Solver

Input and Output Options

The following options enable you to specify the graph to run algorithms on. These options take array and set names. They are known as identifier expressions in Chapter 5: The OPTMODEL Procedure. Also see Table 9.4 for semantic requirements and the section Input Data for the Network Solver for use cases.

LINKS=( suboptions )

groups link-indexed data. For more information, see the section Input Data for the Network Solver.

You can specify the following suboptions:

INCLUDE=set-name

names a set of links to include in the graph definition even if no weights or bounds are available for them. For more information, see Example 9.1: Articulation Points in a Terrorist Network. The set must be numeric, and it must be indexed over a subset of the links of the graph.

LOWER=array-name

specifies the flow lower bound for each link. The array must be numeric, and it must be indexed over a subset of the inks of the graph.

UPPER=array-name

specifies the flow upper bound for each link. The array must be numeric, and it must be indexed over a subset of the links of the graph.

WEIGHT=array-name

specifies link weights. The array must be numeric, and it must be indexed over a subset of the links of the graph. If you specify this suboption, then any link that does not appear in the index set of the WEIGHT= array has weight 0. If you do not specify this suboption, then every link has weight 1.

NODES=( suboptions )

groups node-indexed data. For more information, see the section Input Data for the Network Solver.

You can specify the following suboptions:

INCLUDE=set-name

names a set of nodes to include in the graph definition even if no weights are available for them. For more information, see the section Connected Components.

WEIGHT=array-name

specifies node weights. The array must be numeric, and it must be indexed over a subset of the nodes of the graph.

WEIGHT2=array-name

specifies node supply upper bounds in the minimum-cost network flow problem. The array must be numeric, and it must be indexed over a subset of the nodes of the graph. For more information, see the section Minimum-Cost Network Flow.

OUT=( suboptions )

specifies the output sets or arrays for each algorithm (see Table 9.4 for which OUT= suboptions you can specify for each algorithm). You can use some of these options (even if you do not invoke any algorithm) to see the filtering outcome that is produced by the SUBGRAPH= option.

If you do not specify a suboption that matches the algorithm option in the statement, the algorithm runs and only updates the objective.

If you specify a suboption that does not match the algorithm option in the statement, OPTMODEL issues a warning.

When you declare arrays that are indexed over nodes, over links, or over sets of nodes or links, you must use the same type you used in your node definition.

See the various algorithm sections for examples of the use of these OUT= suboptions.

ARTPOINTS=set-name

specifies the output set for articulation points. Each element of the set represents a node ID. This suboption is used with the BICONCOMP algorithm option.

ASSIGNMENTS=set-name

specifies the output set for linear assignment. This suboption is used with the LINEAR_ASSIGN­MENT algorithm option.

BICONCOMP=array-name

specifies the array to contain the biconnected component of each link. This suboption is used with the BICONCOMP algorithm option.

CLIQUES=set-name

specifies the output set for cliques. Each tuple of the set represents clique ID and node ID. This suboption is used with the CLIQUE algorithm option.

CONCOMP=array-name

specifies the output array for connected components. This suboption is used with the CONCOMP algorithm option.

CUTSETS=set-name

specifies the output set for the cut-sets for minimum cuts. Each tuple of the set represents the cut ID, the tail node ID, and the head node ID. This suboption is used with the MINCUT algorithm option.

CYCLES=set-name

specifies the output set for cycles. Each tuple of the set represents a cycle ID, the order within that cycle, and the node ID. This suboption is used with the CYCLE algorithm option.

FLOW=array-name

specifies the output array for the flow on each link. This suboption is used with the MINCOSTFLOW algorithm option.

FOREST=set-name

specifies the output set for the minimum spanning tree (forest). This suboption is used with the MINSPANTREE algorithm option.

LINKS=set-name

specifies the output set for the links that remain after the SUBGRAPH= option is applied. Each tuple of the set represents tail and head nodes, followed by a sequence of numbers which correspond to the attributes you provide in the LINKS= suboptions. The length of the tuples must be the number of attributes you specify plus two (for the tail and head node information). The options you specify in the LINKS= option will appear in the output in the order: WEIGHT= , LOWER= , and UPPER= . For an example, see Figure 9.12 in Solving over Subsets of Nodes and Links (Filters).

NODES=set-name

specifies the output set for the nodes that remain after the SUBGRAPH= option is applied. Each tuple of the set represents a node, followed by a sequence of numbers which correspond to the attributes you provide in the NODES= suboptions. The length of the tuples must be the number of attributes you specify plus one (for node information). The options you specify in the NODES= option will appear in the output in the order: WEIGHT= and WEIGHT2= . For an example, see the section Minimum-Cost Network Flow with Flexible Supply and Demand.

ORDER=array-name

specifies the numeric array to contain the position of each node within the optimal tour. This suboption is used with the TSP algorithm option.

PARTITIONS=set-name

specifies the output set for the partitions for minimum cuts. The set contains, for each partition, the node IDs in the smaller of the two subsets. Each tuple of the set represents a cut ID and a node ID. This suboption is used with the MINCUT algorithm option.

SPPATHS=set-name

specifies the set to contain the link sequence for each path. Each tuple of the set represents a source node ID, a sink node ID, a sequence number, a tail node ID, and a head node ID. This suboption is used with the SHORTPATH algorithm option.

SPWEIGHTS=array-name

specifies the numeric array to contain the path weight for each source and sink node pair. This suboption is used with the SHORTPATH algorithm option.

TOUR=set-name

specifies the output set for the tour in the traveling salesman problem. This suboption is used with the TSP algorithm option.

TRANSCL=set-name

specifies the set to contain the pairs $(u,v)$ of nodes where v is reachable from u. This suboption is used with the TRANSITIVE_CLOSURE algorithm option.

SUBGRAPH=( suboptions )

specifies the input sets that enable you to solve a problem over a subgraph. For more information, see the section Input Data for the Network Solver.

You can specify the following suboptions:

LINKS=set-name

specifies the subset of links to use. If you specify a node pair that is not referenced in any of the suboptions of the LINKS= option, then the network solver returns an error.

NODES=set-name

specifies the subset of nodes to use. If you specify a node that is not referenced in any of the suboptions of the LINKS= option or the NODES= option, then the network solver returns an error.