Example 6.6 Adding Side Constraints, Using a Warm Start

The manufacturer of Gizmo chips, which are parts needed to make televisions, can supply only 2600 chips to factory 1 and 3750 chips to factory 2 in time for production in each of the months of March and April. However, Gizmo chips will not be in short supply in May. Three chips are required to make each 19-inch TV while the 25-inch TVs require four chips each. To limit the production of televisions produced at factory 1 in March so that the TVs have the correct number of chips, a side constraint called FACT1 MAR GIZMO is used. The form of this constraint is

  3 * prod f1 19 mar   +   4 * prod f1 25 mar   <=   2600

prod f1 19 mar is the name of the arc directed from the node fact1_1 toward node f1_mar_1 and, in the previous constraint, designates the flow assigned to this arc. The ARCDATA= and ARCOUT= data sets have arc names in a variable called _name_.

The other side constraints (shown below) are called FACT2 MAR GIZMO , FACT1 APL GIZMO, and FACT2 APL GIZMO.

  3 * prod f2 19 mar   +   4 * prod f2 25 mar   <=   3750
  3 * prod f1 19 apl   +   4 * prod f1 25 apl   <=   2600
  3 * prod f2 19 apl   +   4 * prod f2 25 apl   <=   3750

To maintain customer goodwill, the total number of backorders is not to exceed 50 sets. The side constraint TOTAL BACKORDER that models this restriction is:

  back f1 19 apl  +  back f1 25 apl  +  
  back f2 19 apl  +  back f2 25 apl  + 
  back f1 19 may  +  back f1 25 may  +
  back f2 19 may  +  back f2 25 may   <=   50

The sparse CONDATA= data set format is used. All side constraints are less than or equal type. Because this is the default type value for the DEFCONTYPE= option, type information is not necessary in the following CONDATA=CON3. Also, DEFCONTYPE= <= does not have to be specified in the PROC NETFLOW statement that follows. Notice that the _column_ variable value CHIP/BO LIMIT indicates that an observation of the CON3 data set contains rhs information. Therefore, specify RHSOBS='CHIP/BO LIMIT'.

title 'Adding Side Constraints and Using a Warm Start';
title2 'Production Planning/Inventory/Distribution';
data con3;
  input _column_ &$14. _row_ &$15. _coef_ ;
  datalines;
prod f1 19 mar  FACT1 MAR GIZMO  3
prod f1 25 mar  FACT1 MAR GIZMO  4
CHIP/BO LIMIT   FACT1 MAR GIZMO  2600
prod f2 19 mar  FACT2 MAR GIZMO  3
prod f2 25 mar  FACT2 MAR GIZMO  4
CHIP/BO LIMIT   FACT2 MAR GIZMO  3750
prod f1 19 apl  FACT1 APL GIZMO  3
prod f1 25 apl  FACT1 APL GIZMO  4
CHIP/BO LIMIT   FACT1 APL GIZMO  2600
prod f2 19 apl  FACT2 APL GIZMO  3
prod f2 25 apl  FACT2 APL GIZMO  4
CHIP/BO LIMIT   FACT2 APL GIZMO  3750
back f1 19 apl  TOTAL BACKORDER  1
back f1 25 apl  TOTAL BACKORDER  1
back f2 19 apl  TOTAL BACKORDER  1
back f2 25 apl  TOTAL BACKORDER  1
back f1 19 may  TOTAL BACKORDER  1
back f1 25 may  TOTAL BACKORDER  1
back f2 19 may  TOTAL BACKORDER  1
back f2 25 may  TOTAL BACKORDER  1
CHIP/BO LIMIT   TOTAL BACKORDER  50
;

The four pairs of data sets that follow can be used as ARCDATA= and NODEDATA= data sets in the following PROC NETFLOW run. The set used depends on which cost information the arcs are to have and whether a warm start is to be used.

  ARCDATA=arc0    NODEDATA=node0
  ARCDATA=arc1    NODEDATA=node2
  ARCDATA=arc2    NODEDATA=node2
  ARCDATA=arc3    NODEDATA=node3

arc0, node0, arc1, and node2 were created in Example 6.4. The first two data sets are the original input data sets. arc1 and node2 were the ARCOUT= and NODEOUT= data sets of a PROC NETFLOW run with FUTURE1 specified. Now, if you use arc1 and node2 as the ARCDATA= data set and NODEDATA= data set in a PROC NETFLOW run, you can specify WARM, as these data sets contain additional information describing a warm start.

In Example 6.5, arc2 was created by modifying arc1 to reflect different arc costs. arc2 and node2 can also be used as the ARCDATA= and NODEDATA= data sets in a PROC NETFLOW run. Again, specify WARM, as these data sets contain additional information describing a warm start. This start, however, contains the optimal basis using the original costs.

If you are going to continue optimization using the changed arc costs, it is probably best to use arc3 and node3 as the ARCDATA= and NODEDATA= data sets. These data sets, created in Example 6.6 by PROC NETFLOW when the FUTURE1 option was specified, contain an optimal basis that can be used as a warm start.

PROC NETFLOW is used to find the changed cost network solution that obeys the chip limit and backorder side constraints. The FUTURE2 option is specified in case further processing is required. An explicit ID list has also been specified so that the variables oldcost, oldfc and oldflow do not appear in the subsequent output data sets.

proc netflow
  nodedata=node3 arcdata=arc3 warm
  condata=con3 sparsecondata rhsobs='CHIP/BO LIMIT'
  future2 dualout=dual4 conout=con4;
     id diagonal factory key_id mth_made;
     run;
     quit;
proc print data=con4 heading=h width=min;
sum _fcost_;
var _tail_ _head_ _cost_ _capac_ _lo_ _name_ _supply_ _demand_ _flow_ _fcost_;
run;
proc print data=con4 heading=h width=min;
var _rcost_ _anumb_ _tnumb_ _status_ diagonal factory key_id mth_made;
run;
proc print data=dual4;
  run;

The following messages appear on the SAS log:

NOTE: The following 3 variables in ARCDATA do not belong to any SAS variable    
      list. These will be ignored.                                              
      oldcost                                                                   
      oldfc                                                                     
      oldflow                                                                   
NOTE: Number of nodes= 21 .                                                     
NOTE: Number of supply nodes= 4 .                                               
NOTE: Number of demand nodes= 5 .                                               
NOTE: The greater of total supply and total demand= 4350 .                      
NOTE: Number of iterations performed (neglecting any constraints)= 1 .          
NOTE: Of these, 0 were degenerate.                                              
NOTE: Optimum (neglecting any constraints) found.                               
NOTE: Minimal total cost= -1285086.45 .                                         
NOTE: Number of <= side constraints= 5 .                                        
NOTE: Number of == side constraints= 0 .                                        
NOTE: Number of >= side constraints= 0 .                                        
NOTE: Number of arc and nonarc variable side constraint coefficients= 16 .      
NOTE: Number of iterations, optimizing with constraints= 14 .                   
NOTE: Of these, 1 were degenerate.                                              
NOTE: Optimum reached.                                                          
NOTE: Minimal total cost= -1282708.625 .                                        
NOTE: The data set WORK.CON4 has 68 observations and 18 variables.              
NOTE: The data set WORK.DUAL4 has 27 observations and 14 variables.             

Output 6.6.1: CONOUT=CON4

Obs _tail_ _head_ _cost_ _capac_ _lo_ _name_ _SUPPLY_ _DEMAND_ _FLOW_ _FCOST_
1 fact1_1 _EXCESS_ 0.00 99999999 0   1000 200 5.000 0.00
2 fact2_1 _EXCESS_ 0.00 99999999 0   850 200 45.000 0.00
3 fact1_2 _EXCESS_ 0.00 99999999 0   1000 200 0.000 0.00
4 fact2_2 _EXCESS_ 0.00 99999999 0   1500 200 150.000 0.00
5 fact1_1 f1_apr_1 78.60 600 50 prod f1 19 apl 1000 . 533.333 41920.00
6 f1_mar_1 f1_apr_1 15.00 50 0   . . 0.000 0.00
7 f1_may_1 f1_apr_1 33.60 20 0 back f1 19 may . . 0.000 0.00
8 f2_apr_1 f1_apr_1 11.00 40 0   . . 0.000 0.00
9 fact1_2 f1_apr_2 174.50 550 50 prod f1 25 apl 1000 . 250.000 43625.00
10 f1_mar_2 f1_apr_2 20.00 40 0   . . 0.000 0.00
11 f1_may_2 f1_apr_2 49.20 15 0 back f1 25 may . . 0.000 0.00
12 f2_apr_2 f1_apr_2 21.00 25 0   . . 0.000 0.00
13 fact1_1 f1_mar_1 127.90 500 50 prod f1 19 mar 1000 . 333.333 42633.33
14 f1_apr_1 f1_mar_1 33.60 20 0 back f1 19 apl . . 20.000 672.00
15 f2_mar_1 f1_mar_1 10.00 40 0   . . 40.000 400.00
16 fact1_2 f1_mar_2 217.90 400 40 prod f1 25 mar 1000 . 400.000 87160.00
17 f1_apr_2 f1_mar_2 38.40 30 0 back f1 25 apl . . 30.000 1152.00
18 f2_mar_2 f1_mar_2 20.00 25 0   . . 25.000 500.00
19 fact1_1 f1_may_1 90.10 400 50   1000 . 128.333 11562.83
20 f1_apr_1 f1_may_1 12.00 50 0   . . 0.000 0.00
21 f2_may_1 f1_may_1 13.00 40 0   . . 0.000 0.00
22 fact1_2 f1_may_2 113.30 350 40   1000 . 350.000 39655.00
23 f1_apr_2 f1_may_2 18.00 40 0   . . 0.000 0.00
24 f2_may_2 f1_may_2 13.00 25 0   . . 0.000 0.00
25 f1_apr_1 f2_apr_1 11.00 99999999 0   . . 13.333 146.67
26 fact2_1 f2_apr_1 62.40 480 35 prod f2 19 apl 850 . 480.000 29952.00
27 f2_mar_1 f2_apr_1 18.00 30 0   . . 0.000 0.00
28 f2_may_1 f2_apr_1 30.00 15 0 back f2 19 may . . 0.000 0.00
29 f1_apr_2 f2_apr_2 23.00 99999999 0   . . 0.000 0.00
30 fact2_2 f2_apr_2 196.70 680 35 prod f2 25 apl 1500 . 577.500 113594.25
31 f2_mar_2 f2_apr_2 28.00 50 0   . . 0.000 0.00
32 f2_may_2 f2_apr_2 64.80 15 0 back f2 25 may . . 0.000 0.00
33 f1_mar_1 f2_mar_1 11.00 99999999 0   . . 0.000 0.00
34 fact2_1 f2_mar_1 88.00 450 35 prod f2 19 mar 850 . 290.000 25520.00
35 f2_apr_1 f2_mar_1 20.40 15 0 back f2 19 apl . . 0.000 0.00
36 f1_mar_2 f2_mar_2 23.00 99999999 0   . . 0.000 0.00
37 fact2_2 f2_mar_2 182.00 650 35 prod f2 25 mar 1500 . 650.000 118300.00
38 f2_apr_2 f2_mar_2 37.20 15 0 back f2 25 apl . . 0.000 0.00
39 f1_may_1 f2_may_1 16.00 99999999 0   . . 115.000 1840.00
40 fact2_1 f2_may_1 128.80 250 35   850 . 35.000 4508.00
41 f2_apr_1 f2_may_1 20.00 30 0   . . 0.000 0.00
42 f1_may_2 f2_may_2 26.00 99999999 0   . . 350.000 9100.00
43 fact2_2 f2_may_2 181.40 550 35   1500 . 122.500 22221.50
44 f2_apr_2 f2_may_2 38.00 50 0   . . 0.000 0.00
45 f1_mar_1 shop1_1 -327.65 250 0   . 900 143.333 -46963.17
46 f1_apr_1 shop1_1 -300.00 250 0   . 900 250.000 -75000.00
47 f1_may_1 shop1_1 -285.00 250 0   . 900 13.333 -3800.00
48 f2_mar_1 shop1_1 -297.40 250 0   . 900 250.000 -74350.00
49 f2_apr_1 shop1_1 -290.00 250 0   . 900 243.333 -70566.67
50 f2_may_1 shop1_1 -292.00 250 0   . 900 0.000 0.00
51 f1_mar_2 shop1_2 -559.76 99999999 0   . 900 0.000 0.00
52 f1_apr_2 shop1_2 -524.28 99999999 0   . 900 0.000 0.00
53 f1_may_2 shop1_2 -475.02 99999999 0   . 900 0.000 0.00
54 f2_mar_2 shop1_2 -567.83 500 0   . 900 500.000 -283915.00
55 f2_apr_2 shop1_2 -542.19 500 0   . 900 400.000 -216876.00
56 f2_may_2 shop1_2 -491.56 500 0   . 900 0.000 0.00
57 f1_mar_1 shop2_1 -362.74 250 0   . 900 250.000 -90685.00
58 f1_apr_1 shop2_1 -300.00 250 0   . 900 250.000 -75000.00
59 f1_may_1 shop2_1 -245.00 250 0   . 900 0.000 0.00
60 f2_mar_1 shop2_1 -272.70 250 0   . 900 0.000 0.00
61 f2_apr_1 shop2_1 -312.00 250 0   . 900 250.000 -78000.00
62 f2_may_1 shop2_1 -299.00 250 0   . 900 150.000 -44850.00
63 f1_mar_2 shop2_2 -623.89 99999999 0   . 1450 455.000 -283869.95
64 f1_apr_2 shop2_2 -549.68 99999999 0   . 1450 220.000 -120929.60
65 f1_may_2 shop2_2 -460.00 99999999 0   . 1450 0.000 0.00
66 f2_mar_2 shop2_2 -542.83 500 0   . 1450 125.000 -67853.75
67 f2_apr_2 shop2_2 -559.19 500 0   . 1450 177.500 -99256.23
68 f2_may_2 shop2_2 -519.06 500 0   . 1450 472.500 -245255.85
                    -1282708.63


Output 6.6.2: CONOUT=CON4 (continued)

Obs _RCOST_ _ANUMB_ _TNUMB_ _STATUS_ diagonal factory key_id mth_made
1 . 65 1 KEY_ARC BASIC . .    
2 . 66 10 KEY_ARC BASIC . .    
3 30.187 67 11 LOWERBD NONBASIC . .    
4 . 68 20 KEY_ARC BASIC . .    
5 . 4 1 KEY_ARC BASIC 19 1 production April
6 63.650 5 2 LOWERBD NONBASIC 19 1 storage March
7 54.650 6 4 LOWERBD NONBASIC 19 1 backorder May
8 22.000 7 6 LOWERBD NONBASIC 19 . f2_to_1 April
9 . 36 11 KEY_ARC BASIC 25 1 production April
10 94.210 37 12 LOWERBD NONBASIC 25 1 storage March
11 7.630 38 14 LOWERBD NONBASIC 25 1 backorder May
12 30.510 39 16 LOWERBD NONBASIC 25 . f2_to_1 April
13 . 1 1 KEY_ARC BASIC 19 1 production March
14 . 2 3 NONKEY ARC BASIC 19 1 backorder April
15 -34.750 3 5 UPPERBD NONBASIC 19 . f2_to_1 March
16 -31.677 33 11 UPPERBD NONBASIC 25 1 production March
17 -20.760 34 13 UPPERBD NONBASIC 25 1 backorder April
18 -61.060 35 15 UPPERBD NONBASIC 25 . f2_to_1 March
19 . 8 1 KEY_ARC BASIC 19 1 production May
20 6.000 9 3 LOWERBD NONBASIC 19 1 storage April
21 29.000 10 7 LOWERBD NONBASIC 19 . f2_to_1 May
22 -11.913 40 11 UPPERBD NONBASIC 25 1 production May
23 74.620 41 13 LOWERBD NONBASIC 25 1 storage April
24 39.000 42 17 LOWERBD NONBASIC 25 . f2_to_1 May
25 . 14 3 KEY_ARC BASIC 19 . f1_to_2 April
26 -14.077 15 10 UPPERBD NONBASIC 19 2 production April
27 10.900 16 5 LOWERBD NONBASIC 19 2 storage March
28 56.050 17 7 LOWERBD NONBASIC 19 2 backorder May
29 13.490 46 13 LOWERBD NONBASIC 25 . f1_to_2 April
30 . 47 20 KEY_ARC BASIC 25 2 production April
31 11.640 48 15 LOWERBD NONBASIC 25 2 storage March
32 39.720 49 17 LOWERBD NONBASIC 25 2 backorder May
33 55.750 11 2 LOWERBD NONBASIC 19 . f1_to_2 March
34 . 12 10 KEY_ARC BASIC 19 2 production March
35 42.550 13 6 LOWERBD NONBASIC 19 2 backorder April
36 104.060 43 12 LOWERBD NONBASIC 25 . f1_to_2 March
37 -23.170 44 20 UPPERBD NONBASIC 25 2 production March
38 68.610 45 16 LOWERBD NONBASIC 25 2 backorder April
39 . 18 4 KEY_ARC BASIC 19 . f1_to_2 May
40 22.700 19 10 LOWERBD NONBASIC 19 2 production May
41 9.000 20 6 LOWERBD NONBASIC 19 2 storage April
42 . 50 14 KEY_ARC BASIC 25 . f1_to_2 May
43 . 51 20 NONKEY ARC BASIC 25 2 production May
44 78.130 52 16 LOWERBD NONBASIC 25 2 storage April
45 . 21 2 KEY_ARC BASIC 19 1 sales March
46 -21.000 22 3 UPPERBD NONBASIC 19 1 sales April
47 . 23 4 NONKEY ARC BASIC 19 1 sales May
48 -14.500 24 5 UPPERBD NONBASIC 19 2 sales March
49 . 25 6 NONKEY ARC BASIC 19 2 sales April
50 9.000 26 7 LOWERBD NONBASIC 19 2 sales May
51 47.130 53 12 LOWERBD NONBASIC 25 1 sales March
52 8.400 54 13 LOWERBD NONBASIC 25 1 sales April
53 1.040 55 14 LOWERBD NONBASIC 25 1 sales May
54 -42.000 56 15 UPPERBD NONBASIC 25 2 sales March
55 . 57 16 KEY_ARC BASIC 25 2 sales April
56 10.500 58 17 LOWERBD NONBASIC 25 2 sales May
57 -37.090 27 2 UPPERBD NONBASIC 19 1 sales March
58 -23.000 28 3 UPPERBD NONBASIC 19 1 sales April
59 38.000 29 4 LOWERBD NONBASIC 19 1 sales May
60 8.200 30 5 LOWERBD NONBASIC 19 2 sales March
61 -24.000 31 6 UPPERBD NONBASIC 19 2 sales April
62 . 32 7 KEY_ARC BASIC 19 2 sales May
63 . 59 12 KEY_ARC BASIC 25 1 sales March
64 . 60 13 KEY_ARC BASIC 25 1 sales April
65 33.060 61 14 LOWERBD NONBASIC 25 1 sales May
66 . 62 15 KEY_ARC BASIC 25 2 sales March
67 . 63 16 KEY_ARC BASIC 25 2 sales April
68 . 64 17 KEY_ARC BASIC 25 2 sales May


Output 6.6.3: DUALOUT=DUAL4

Obs _node_ _supdem_ _DUAL_ _NNUMB_ _PRED_ _TRAV_ _SCESS_ _ARCID_ _FLOW_ _FBQ_ _VALUE_ _RHS_ _TYPE_ _row_
1 _ROOT_ 238 0.00 22 0 8 5 3 166.000 -69 0 75    
2 _EXCESS_ -200 -100000193.90 21 1 20 13 65 5.000 65 . .    
3 f1_apr_1 . -100000278.00 3 1 6 2 4 483.333 4 . .    
4 f1_apr_2 . -100000405.92 13 19 11 2 -60 220.000 36 . .    
5 f1_mar_1 . -100000326.65 2 8 1 20 -21 143.333 1 . .    
6 f1_mar_2 . -100000480.13 12 19 13 1 -59 455.000 33 . .    
7 f1_may_1 . -100000284.00 4 1 7 3 8 78.333 8 . .    
8 f1_may_2 . -100000349.30 14 17 15 1 -50 350.000 40 . .    
9 f2_apr_1 . -100000289.00 6 3 4 1 14 13.333 14 . .    
10 f2_apr_2 . -100000415.43 16 20 18 9 47 542.500 46 . .    
11 f2_mar_1 . -100000281.90 5 10 3 1 12 255.000 11 . .    
12 f2_mar_2 . -100000399.07 15 19 10 1 -62 125.000 43 . .    
13 f2_may_1 . -100000300.00 7 4 9 2 18 115.000 18 . .    
14 f2_may_2 . -100000375.30 17 19 14 2 -64 472.500 50 . .    
15 fact1_1 1000 -100000193.90 1 2 21 19 -1 283.333 -1 . .    
16 fact1_2 1000 -100000224.09 11 13 17 1 -36 200.000 -33 . .    
17 fact2_1 850 -100000193.90 10 21 5 2 -66 45.000 -33 . .    
18 fact2_2 1500 -100000193.90 20 21 16 10 -68 150.000 -65 . .    
19 shop1_1 -900 -99999999.00 8 22 2 21 0 0.000 21 . .    
20 shop1_2 -900 -99999873.24 18 16 19 1 57 400.000 53 . .    
21 shop2_1 -900 -100000001.00 9 7 22 1 32 150.000 27 . .    
22 shop2_2 -1450 -99999856.24 19 16 12 7 63 177.500 59 . .    
23   . -1.83 2 8 . . 25 243.333 . 2600 2600 LE FACT1 APL GIZMO
24   . -1.62 0 8 . . 23 13.333 . 2600 2600 LE FACT1 MAR GIZMO
25   . -6.21 3 17 . . 51 87.500 . 3750 3750 LE FACT2 APL GIZMO
26   . 0.00 1 1 . 1 . 280.000 . 3470 3750 LE FACT2 MAR GIZMO
27   . -15.05 4 2 . . 2 20.000 . 50 50 LE TOTAL BACKORDER