The Network Solver

Solving over Subsets of Nodes and Links (Filters)

You can solve a problem over a subgraph without declaring new link and node sets. You can specify the LINKS= and NODES= suboptions of the SUBGRAPH= option to filter nodes and links before PROC OPTMODEL builds and solves the instance. If you want to see the resulting subgraph, you can specify the LINKS= and NODES= suboptions of the OUT= option. If you just want to produce a subgraph, you do not need to invoke an algorithm.

You can keep all the input and output arrays defined over the original graph and define a subgraph by providing any combination of the LINKS= and NODES= suboptions of the SUBGRAPH= option. If you specify either of the suboptions of the SUBGRAPH= option, then union semantics apply. PROC OPTMODEL uses the following rules:

Only the links that are included in the set named in the LINKS= option are used to create the instance.
Only the nodes that appear either in the NODES= suboption of the SUBGRAPH= option or that appear as the head or tail of a link in the LINKS= suboption are used to create the instance.
A node or a link that appears only in the SUBGRAPH= option, but not in the original graph, is discarded. To add nodes or links that do not have attributes, see the INCLUDE= suboption of the LINKS= and NODE= options.

If the value of the LOGLEVEL= suboption is equal to or greater than 3, PROC OPTMODEL issues a message for each of the nodes and links that it discards until the number of messages reaches the value of the MSGLIMIT= option in the PROC OPTMODEL statement. If the value of the LOGLEVEL= suboption is greater than 0, PROC OPTMODEL also issues a summary that shows the total count of discarded nodes and links from each input array or set.

The following statements start a PROC OPTMODEL session and declare a five-node complete undirected graph; a subset of links that contains all links between nodes 1, 2, 3, and 4; and a subset of nodes that contains nodes 3, 4, and 5:

proc optmodel;
   set NODES = 1..5;
   set LINKS = {vi in NODES, vj in NODES: vi < vj};
   num distance {<vi,vj> in LINKS} = 10*vi + vj;

   set <num,num> TOUR;

   /* Build a link set using only nodes 1..4 nodes */
   set <num,num> LINKS_BETWEEN_1234 = {vi in 1..3, vj in (vi+1)..4};
   /* Build a node subset consisting of nodes 3..5 */
   set NODES_345 = 3..5;

After the sets are declared, the statements in the following steps solve several traveling salesman problems (TSPs) on subgraphs. For more information about TSPs, see the section Traveling Salesman Problem.

The first SOLVE statement solves a TSP on the original graph. Note that the links in the tour (see Figure 9.8 are returned with the same orientation that you provide in the input. For example, the second step on the tour goes from node 4 to node 2 using link $(2,4)$ . This guarantees that you do not need to do extra processing of output to check for link orientation. You can just use the output directly.

   /* Implicit network 1: solve over nodes 1..5 -- The original network*/
   solve with NETWORK /
      links=( weight=distance )
      out=( tour=TOUR )
      tsp
   ;
   put TOUR=;

As shown in Figure 9.8, all links implied by the WEIGHT= suboption of the LINKS= option become part of the graph.

Figure 9.8: SOLVE WITH NETWORK Log: Traveling Salesman Tour of an Unfiltered Graph

NOTE: The number of nodes in the input graph is 5.                              
NOTE: The number of links in the input graph is 10.                             
NOTE: Processing the traveling salesman problem.                                
NOTE: The initial TSP heuristics found a tour with cost 111 using 0.04 (cpu:    
      0.03) seconds.                                                            
NOTE: The MILP presolver value NONE is applied.                                 
NOTE: The MILP solver is called.                                                
NOTE: Optimal.                                                                  
NOTE: Objective = 111.                                                          
NOTE: Processing the traveling salesman problem used 0.07 (cpu: 0.06) seconds.  
TOUR={<1,4>,<2,4>,<2,3>,<3,5>,<1,5>}

To access the objective value of a network problem, use the _OROPTMODEL_NUM_ predefined array. The network solver ignores the _OBJ_ predefined symbol, which is part of the current named problem. The current named problem is independent of the network solver, because the network solver uses sets and numeric arrays for input and output. For more information, see the sections Multiple Subproblems and Solver Status Parameters in Chapter 5: The OPTMODEL Procedure.

   put _OROPTMODEL_NUM_['OBJECTIVE'];

The next SOLVE statement solves a TSP on the subgraph that is defined by the link set LINKS_BETWEEN_1234.

   /* Filter on LINKS: solve over nodes 1..4 */
   solve with NETWORK /
      links=( weight=distance )
      subgraph=( links=LINKS_BETWEEN_1234 )
      out=( tour=TOUR )
      tsp
   ;
   put TOUR=;

As shown in Figure 9.9, the network solver now ignores node 5.

Figure 9.9: SOLVE WITH NETWORK Log: Traveling Salesman Tour over Nodes $N=\{ 1,2,3,4\}$

111                                                                             
NOTE: The SUBGRAPH= option filtered 4 elements from 'distance.'                 
NOTE: The number of nodes in the input graph is 4.                              
NOTE: The number of links in the input graph is 6.                              
NOTE: Processing the traveling salesman problem.                                
NOTE: The initial TSP heuristics found a tour with cost 74 using 0.04 (cpu:     
      0.05) seconds.                                                            
NOTE: The MILP presolver value NONE is applied.                                 
NOTE: The MILP solver is called.                                                
NOTE: Optimal.                                                                  
NOTE: Objective = 74.                                                           
NOTE: Processing the traveling salesman problem used 0.07 (cpu: 0.08) seconds.  
TOUR={<1,3>,<2,3>,<2,4>,<1,4>}

The next SOLVE statement solves a TSP on the subgraph that is defined by the node set NODES_345.

   /* Filter on NODES: solve over nodes 3..5 */
   solve with NETWORK /
      links=( weight=distance )
      subgraph=( nodes=NODES_345 )
      out=( tour=TOUR )
      tsp
   ;
   put TOUR=;

As shown in Figure 9.10, the network solver now ignores nodes 1 and 2, along with any links incident to them.

Figure 9.10: SOLVE WITH NETWORK Log: Traveling Salesman Tour over Nodes $N=\{ 3,4,5\}$

NOTE: The SUBGRAPH= option filtered 7 elements from 'distance.'                 
NOTE: The number of nodes in the input graph is 3.                              
NOTE: The number of links in the input graph is 3.                              
NOTE: Processing the traveling salesman problem.                                
NOTE: The initial TSP heuristics found a tour with cost 114 using 0.03 (cpu:    
      0.03) seconds.                                                            
NOTE: The MILP presolver value NONE is applied.                                 
NOTE: The MILP solver is called.                                                
NOTE: Optimal.                                                                  
NOTE: Objective = 114.                                                          
NOTE: Processing the traveling salesman problem used 0.07 (cpu: 0.06) seconds.  
TOUR={<3,4>,<4,5>,<3,5>}

The next SOLVE statement attempts to solve a TSP on the subgraph that is defined by the node set NODES_345 and the link set that is defined by the links on the nodes $\{ 1,2,3,4\}$ . This subgraph creates an infeasible instance because the links $\{ (1,5),(2,5),(3,5),(4,5)\}$ that were defined in the original graph have been filtered out. Thus, node 5 is disconnected and no tour can exist.

   /* Explicit nodes and links: semantic error over nodes 1..5
    * Links <u,5> are undefined and no documented default exists. */
   solve with NETWORK /
      links=( weight=distance )
      subgraph=( nodes=NODES_345 links=LINKS_BETWEEN_1234 )
      out=( tour=TOUR )
      tsp
   ;

As shown in Figure 9.11, the network solver identifies that no tour exists over the surviving nodes and links.

Figure 9.11: SOLVE WITH NETWORK Log: Infeasible Traveling Salesman Problem after Filtering

NOTE: The SUBGRAPH= option filtered 4 elements from 'distance.'                 
NOTE: The number of nodes in the input graph is 5.                              
NOTE: The number of links in the input graph is 6.                              
NOTE: Processing the traveling salesman problem.                                
NOTE: Infeasible.                                                               
NOTE: Processing the traveling salesman problem used 0.00 (cpu: 0.00) seconds.

The last SOLVE statement uses the LINKS= suboption of the OUT= option to capture exactly which nodes and links were generated and with which attributes. In this case, because the only attribute defined is link weight, the set LINKS_OUT has tuples of length three.

   /* make room for tail, head, and weight */
   set<num,num,num> LINKS_OUT;
   solve with NETWORK /
      links=( weight=distance )
      subgraph=( nodes=NODES_345 links=LINKS_BETWEEN_1234 )
      out=( tour=TOUR links=LINKS_OUT )
      tsp
   ;
   put LINKS_OUT=;
quit;

As shown in Figure 9.12, the network solver can return the graph after filtering. This feature can sometimes help you identify why you might get counterintuitive results.

Figure 9.12: SOLVE WITH NETWORK Log: Remaining Links after Filtering

NOTE: The SUBGRAPH= option filtered 4 elements from 'distance.'                 
NOTE: The number of nodes in the input graph is 5.                              
NOTE: The number of links in the input graph is 6.                              
NOTE: Processing the traveling salesman problem.                                
NOTE: Infeasible.                                                               
NOTE: Processing the traveling salesman problem used 0.00 (cpu: 0.00) seconds.  
LINKS_OUT={<1,2,12>,<1,3,13>,<1,4,14>,<2,3,23>,<2,4,24>,<3,4,34>}               
NOTE: The PROCEDURE OPTMODEL printed pages 5-14.