The NETFLOW Procedure

Warm Starts

Using a warm start can increase the overall speed of PROC NETFLOW when it is used repetitively on problems with similar structure. It is most beneficial when a solution of a previous optimization is close to the optimum of the same network with some of its parameters, for example, arc costs, changed. Whether a problem is changed or not, a nonoptimal solution resulting from a previous optimization can be used to restart optimization, thereby saving PROC NETFLOW from having to repeat work to reach the warm start already available.

Time also is saved in the data structure initialization part of the NETFLOW procedure's execution. Information about the previous optimal solution, particularly concerning the size of the problem, a description of the basis spanning tree structure, and what is basic in constraint rows, is known. Information about which nonbasic arcs have capacity flow and which nonbasic nonarc variables are at their respective upper bounds also makes up part of the warm start. The procedure can place arc data into the internal arc length arrays in precisely defined locations, in order of ascending head node internal number. It is not necessary to have multiple passes through the data because literals such as node, nonarc variable, arc, constraint, and special row names are defined and meaning is attached to each. This saves a considerable amount of memory as well. None of the pre-optimization feasibility checks need be repeated.

Warm starts also are useful if you want to determine the effect of arcs being closed to carrying flow. The costs of these arcs are set high enough to ensure that the next optimal solution never has flow through them. Similarly, the effect of opening arcs can be determined by changing the cost of such arcs from an extreme to a reasonable value.

Specify the FUTURE1 or FUTURE2 option to ensure that additional data about a solution to be used as a warm start are output to output data sets. If the FUTURE1 option is specified, extra observations with information on what is to be the warm start are set up for the NODEOUT= and ARCOUT= data sets. The warm start solution in these data sets is a solution obtained after optimization neglecting side constraints. Any cost list variable value in the ARCOUT= data set (and, if there are side constraints, any constraint data in the CONDATA= data set) can be changed before the solution is used as a warm start in a subsequent PROC NETFLOW run. Any nonarc variable data in the CONDATA= data set can be changed at this time as well. New nonarc variables not present in the original problem when the warm start was generated can also be added to the CONDATA= data set before the problem is warm started.

If the FUTURE2 option is specified, extra variables containing information on what will be the warm start solution are set up for the DUALOUT= and CONOUT= data sets. The warm start solution in these data sets is obtained after optimization that considers side constraints has been performed. Part of the warm start is concerned with the constraint part of the basis. Only cost list variable values in the CONOUT= data set can be changed before the solution is used as a warm start in a subsequent PROC NETFLOW run.

If a primal simplex optimization is to use a warm start, the WARM option must be specified in the PROC NETFLOW statement. Otherwise, the primal simplex network algorithm processes the data for a cold start and the extra information is not used.

The ARCDATA= data set is either the ARCOUT= data set from a previous run of PROC NETFLOW with the FUTURE1 option specified (if an unconstrained warm start is used) or the CONOUT= data set from a previous run of PROC NETFLOW with the FUTURE2 option specified (if the warm start was obtained after optimization that considers side constraints was used).

The NODEDATA= data set is the NODEOUT= data set from a previous run of PROC NETFLOW with FUTURE1 specified if an unconstrained warm start is being used. Otherwise, the DUALIN= is the DUALOUT= data sets from a previous run of PROC NETFLOW with FUTURE2 specified, if the warm start was obtained after optimization that considers side constraints was used.

You never need to alter the NODEOUT= data set or the DUALOUT= data set between the time they are generated and when they are used as a warm start. The results would be unpredictable if incorrect changes were made to these data sets, or if a NODEDATA= or a DUALIN= data set were used with an ARCDATA= data set of a different solution.

It is possible, and often useful, to specify WARM and either FUTURE1 or FUTURE2, or both, in the same PROC NETFLOW statement if a new warm start is to be generated from the present warm start.

The extent of the changes allowed to a primal simplex warm start between the time it is generated and when it is used depends on whether the warm start describes an unconstrained or constrained solution. The following list describes parts of a constrained or an unconstrained warm start that can be altered:

• COST list variable values
• the value of an arc's capacity, as long as the new capacity value is not less than the lower flow bound or the flow through the arc
• any nonarc variable information, in an unconstrained warm start
• for an unconstrained warm start, any side constraint data

The changes that can be made in constraint data for a constrained warm start are more restrictive than those for an unconstrained warm start. The lhs coefficients, type, and rhs value of a constraint can be changed as long as that constraint's slack, surplus, or artificial variable is basic. The constraint name cannot be changed.

Example of a Warm Start

The following sample SAS session demonstrates how the warm start facilities are used to obtain optimal solutions to an unconstrained network where some arc cost changes occur or optimization is halted before the optimum is found.

  
                  /* data already in data sets node0 and arc0 */ 
   proc netflow 
      nodedata=node0  /* if supply_demand information  */ 
                      /* is in this SAS data set       */ 
      arcdata=arc0; 
                  /* variable list specifications go here    */ 
                  /* assume that they are not necessary here */ 
                  /* if they are, they must be included in   */ 
                  /* all the PROC NETFLOW calls that follow  */ 
      reset 
         future1 
         nodeout=node2  /* nodeout and arcout are necessary  */ 
                        /* when FUTURE1 is used              */ 
         arcout=arc1; 
   proc print 
         data=arc1;     /* display the optimal solution      */ 
   proc fsedit 
         data=arc1;     /* change some arc costs             */ 
   data arc2; 
      reset arc1; 
         oldflow=_flow_; 
         oldfc=_fcost_; 
                  /* make duplicates of the flow and flowcost*/ 
                  /* variables. If a id list was explicitly  */ 
                  /* specified, add oldflow and oldfc to this*/ 
                  /* list so that they appear in subsequently*/ 
                  /* created arcout= data sets               */
 

The following PROC NETFLOW uses the warm start created previously, performs 250 stage 2 iterations and saves that solution, which (as FUTURE1, ARCOUT=, and NODEOUT= are specified) can be used as a warm start in another PROC NETFLOW run.

  
   proc netflow 
        warm 
        nodedata=node2 
        arcdata=arc2; 
      reset 
        maxit1=250 
        future1; 
      run; 
      save 
        nodeout=savelib.node3 
        arcout=savelib.arc3; 
               /* optimization halted because 250 iterations */ 
               /* were performed to resume optimization,     */ 
               /* possibly in another session (the output    */ 
               /* data sets were saved in a SAS library      */ 
               /* called savelib)                            */
 

Using the latest warm start, PROC NETFLOW is re-invoked to find the optimal solution.

  
   proc netflow 
        warm 
        nodedata=savelib.node3 
        arcdata=savelib.arc3; 
      reset 
        future1 
        nodeout=node4 
        arcout=arc4; 
      run;
 

If this problem has constraints with data in a data set called CON0, then in each of the previous PROC NETFLOW statements, specify CONDATA=CON0. Between PROC NETFLOW runs, you can change constraint data. In each of the RESET statements, you could specify the CONOUT= data set to save the last (possibly optimal) solution reached by the optimizer if it reaches stage 2. You could specify FUTURE2 and the DUALOUT= data set to generate a constrained warm start.

  
   proc netflow 
        warm 
        nodedata=node4 
        arcdata=arc4 
        condata=con0; 
      reset 
        maxit2=125 /* optional, here as a reason why         */ 
                   /* optimum will not be obtained           */ 
        scratch    /* optional, but warm start might be good */ 
                   /* enough to start stage 2 optimization   */ 
        future2 
      run; 
        /* optimization halted after 125 stage 2 iterations  */ 
      save dualout=dual1 conout=conout1;
 

Stage 2 optimization halted before optimum was reached. Now you can make cost and nonarc variable objective function coefficient changes. Then to restart optimization, use

  
   proc netflow 
        warm 
        condata=con0 
              /* NB. NETFLOW reads constraint data only     */ 
        dualin=dual1 
        arcdata=con1; 
      reset 
        future2 
        dualout=dual2 
        conout=con2; 
      run;