The INTPOINT Procedure

Example 4.3 Adding Side Constraints

The manufacturer of Gizmo chips, which are parts needed to make televisions, can supply only 2,600 chips to factory 1 and 3,750 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 CONOUT= 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 of 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 INTPOINT 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'

title2 'Adding Side Constraints';
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 INTPOINT run. The set used depends on which cost information the arcs are to have.

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

arc0, node0, and arc1 were created in Example 4.1. The first two data sets are the original input data sets.

In the previous example, arc2 was created by modifying arc1 to reflect different arc costs. arc2 and node0 can also be used as the ARCDATA= and NODEDATA= data sets in a PROC INTPOINT run.

If you are going to continue optimization using the changed arc costs, it is probably best to use arc3 and node0 as the ARCDATA= and NODEDATA= data sets.

PROC INTPOINT is used to find the changed cost network solution that obeys the chip limit and backorder side constraints. 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 intpoint
   bytes=1000000
   printlevel2=2
   nodedata=node0 arcdata=arc3
   condata=con3 sparsecondata rhsobs='CHIP/BO LIMIT'
   conout=arc4;
   id diagonal factory key_id mth_made;
   run;
proc print data=arc4;
   var _tail_ _head_ _cost_ _capac_ _lo_ _flow_ _fcost_;
       /* to get this variable order */
   sum _fcost_;
   run;

The following messages appear on the SAS log:

NOTE: The following variables in ARCDATA do not belong to any SAS variable list.   
      These will be ignored.                                                       
      _FLOW_                                                                       
      _FCOST_                                                                      
      oldcost                                                                      
      oldfc                                                                        
      oldflow                                                                      
NOTE: Number of nodes= 20 .                                                        
NOTE: Number of supply nodes= 4 .                                                  
NOTE: Number of demand nodes= 4 .                                                  
NOTE: Total supply= 4350 , total demand= 4150 .                                    
NOTE: Number of arcs= 64 .                                                         
NOTE: Number of <= side constraints= 5 .                                           
NOTE: Number of == side constraints= 0 .                                           
NOTE: Number of >= side constraints= 0 .                                           
NOTE: Number of side constraint coefficients= 16 .                                 
NOTE: The following messages relate to the equivalent Linear Programming problem   
      solved by the Interior Point algorithm.                                      
NOTE: Number of <= constraints= 5 .                                                
NOTE: Number of == constraints= 21 .                                               
NOTE: Number of >= constraints= 0 .                                                
NOTE: Number of constraint coefficients= 152 .                                     
NOTE: Number of variables= 68 .                                                    
NOTE: After preprocessing, number of <= constraints= 5.                            
NOTE: After preprocessing, number of == constraints= 20.                           
NOTE: After preprocessing, number of >= constraints= 0.                            
NOTE: The preprocessor eliminated 1 constraints from the problem.                  
NOTE: The preprocessor eliminated 9 constraint coefficients from the problem.      
NOTE: 5 columns, 0 rows and 5 coefficients were added to the problem to handle     
      unrestricted variables, variables that are split, and constraint slack or    
      surplus variables.                                                           
NOTE: There are 74 sub-diagonal nonzeroes in the unfactored A Atranspose matrix.   
NOTE: The 25 factor nodes make up 17 supernodes                                    
NOTE: There are 88 nonzero sub-rows or sub-columns outside the supernodal          
      triangular regions along the factors leading diagonal.                       
 Iter  Complem_aff  Complem-ity  Duality_gap  Tot_infeasb  Tot_infeasc  Tot_infeasd
    0    -1.000000    199456613     0.894741        65408        35351        10906
    1     38664128     25735020     0.919726  4738.839318  2561.195456   248.292591
    2      5142982      1874540     0.595158            0            0     6.669426
    3       366112       338310     0.207256            0            0     1.207816
    4       172159        90907     0.063722            0            0     0.238703
    5        48403        38889     0.027839            0            0     0.115586
    6        28882        17979     0.013029            0            0     0.019825
    7  7800.003324  3605.779203     0.002631            0            0     0.004077
    8  1564.193112   422.251530     0.000309            0            0     0.000225
    9    94.768595    16.589795  0.000012126            0            0            0
   10     0.294833     0.001048  5.96523E-10            0            0            0
NOTE: The Primal-Dual Predictor-Corrector Interior Point algorithm performed 10    
      iterations.                                                                  
NOTE: Optimum reached.                                                             
NOTE: Objective= -1282708.622.                                                     
NOTE: The data set WORK.ARC4 has 64 observations and 14 variables.                 
NOTE: There were 64 observations read from the data set WORK.ARC3.                 
NOTE: There were 8 observations read from the data set WORK.NODE0.                 
NOTE: There were 21 observations read from the data set WORK.CON3.                 


Output 4.3.1: CONOUT=ARC4

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