The INTPOINT Procedure

Example 2.5: Nonarc Variables in the Side Constraints

You can verify that the FACT2 MAR GIZMO constraint has a left-hand-side activity of 3,470, which is not equal to the _RHS_ of this constraint. Not all of the 3,750 chips that can be supplied to factory 2 for March production are used. It is suggested that all the possible chips be obtained in March and those not used be saved for April production. Because chips must be kept in an air-controlled environment, it costs one dollar to store each chip purchased in March until April. The maximum number of chips that can be stored in this environment at each factory is 150. In addition, a search of the parts inventory at factory 1 turned up 15 chips available for their March production.

Nonarc variables are used in the side constraints that handle the limitations of supply of Gizmo chips. A nonarc variable called f1 unused chips has as a value the number of chips that are not used at factory 1 in March. Another nonarc variable, f2 unused chips, has as a value the number of chips that are not used at factory 2 in March. f1 chips from mar has as a value the number of chips left over from March used for production at factory 1 in April. Similarly, f2 chips from mar has as a value the number of chips left over from March used for April production at factory 2 in April. The last two nonarc variables have objective function coefficients of 1 and upper bounds of 150. The Gizmo side constraints are

  
    3*prod f1 19 mar + 4*prod f1 25 mar + f1 unused chips = 2615 
    3*prod f2 19 apl + 4*prod f2 25 apl + f2 unused chips = 3750 
    3*prod f1 19 apl + 4*prod f1 25 apl - f1 chips from mar = 2600 
    3*prod f2 19 apl + 4*prod f2 25 apl - f2 chips from mar = 3750 
    f1 unused chips + f2 unused chips - 
    f1 chips from mar - f2 chips from mar >= 0
 

The last side constraint states that the number of chips not used in March is not less than the number of chips left over from March and used in April. Here, this constraint is called CHIP LEFTOVER.

The following SAS code creates a new data set containing constraint data. It seems that most of the constraints are now equalities, so you specify DEFCONTYPE=EQ in the PROC INTPOINT statement from now on and provide constraint type data for constraints that are not "equal to" type, using the default TYPEOBS value _TYPE_ as the _COLUMN_ variable value to indicate observations that contain constraint type data. Also, from now on, the default RHSOBS value is used.

  
    title2 'Nonarc Variables in the Side Constraints'; 
    data con6; 
       input _column_ &$17. _row_ &$15. _coef_ ; 
       datalines; 
    prod f1 19 mar     FACT1 MAR GIZMO  3 
    prod f1 25 mar     FACT1 MAR GIZMO  4 
    f1 unused chips    FACT1 MAR GIZMO  1 
    _RHS_              FACT1 MAR GIZMO  2615 
    prod f2 19 mar     FACT2 MAR GIZMO  3 
    prod f2 25 mar     FACT2 MAR GIZMO  4 
    f2 unused chips    FACT2 MAR GIZMO  1 
    _RHS_              FACT2 MAR GIZMO  3750 
    prod f1 19 apl     FACT1 APL GIZMO  3 
    prod f1 25 apl     FACT1 APL GIZMO  4 
    f1 chips from mar  FACT1 APL GIZMO  -1 
    _RHS_              FACT1 APL GIZMO  2600 
    prod f2 19 apl     FACT2 APL GIZMO  3 
    prod f2 25 apl     FACT2 APL GIZMO  4 
    f2 chips from mar  FACT2 APL GIZMO  -1 
    _RHS_              FACT2 APL GIZMO  3750 
    f1 unused chips    CHIP LEFTOVER    1 
    f2 unused chips    CHIP LEFTOVER    1 
    f1 chips from mar  CHIP LEFTOVER    -1 
    f2 chips from mar  CHIP LEFTOVER    -1 
    _TYPE_             CHIP LEFTOVER    1 
    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 
    _TYPE_             TOTAL BACKORDER  -1 
    _RHS_              TOTAL BACKORDER  50 
    ;
 

The nonarc variables f1 chips from mar and f2 chips from mar have objective function coefficients of 1 and upper bounds of 150. There are various ways in which this information can be furnished to PROC INTPOINT. If there were a TYPE list variable in the CONDATA= data set, observations could be in the form

  
    _COLUMN_           _TYPE_  _ROW_ _COEF_ 
    f1 chips from mar  objfn     .       1 
    f1 chips from mar  upperbd   .     150 
    f2 chips from mar  objfn     .       1 
    f2 chips from mar  upperbd   .     150
 

It is desirable to assign ID list variable values to all the nonarc variables:

  
    data arc6; 
       set arc5; 
       drop oldcost oldfc oldflow _flow_ _fcost_ ; 
       run; 
  
    data arc6_b; 
       input _name_ &$17. _cost_ _capac_ factory key_id $ ; 
       datalines; 
    f1 unused chips    .   . 1 chips 
    f2 unused chips    .   . 2 chips 
    f1 chips from mar  1 150 1 chips 
    f2 chips from mar  1 150 2 chips 
    ;
 

  
    proc append force 
       base=arc6 data=arc6_b; 
       run; 
  
    proc intpoint 
       bytes=1000000 
       printlevel2=2 
       nodedata=node0 arcdata=arc6 
       condata=con6 defcontype=eq sparsecondata 
       conout=arc7; 
       run;
 

The following messages appear on the SAS log:

  
    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 nonarc variables= 4 . 
    NOTE: Number of <= side constraints= 1 . 
    NOTE: Number of == side constraints= 4 . 
    NOTE: Number of >= side constraints= 1 . 
    NOTE: Number of side constraint coefficients= 24 . 
    NOTE: The following messages relate to the equivalent 
          Linear Programming problem solved by the Interior 
          Point algorithm. 
    NOTE: Number of <= constraints= 1 . 
    NOTE: Number of == constraints= 25 . 
    NOTE: Number of >= constraints= 1 . 
    NOTE: Number of constraint coefficients= 160 . 
    NOTE: Number of variables= 72 . 
    NOTE: After preprocessing, number of <= constraints= 1. 
    NOTE: After preprocessing, number of == constraints= 24. 
    NOTE: After preprocessing, number of >= constraints= 1. 
    NOTE: The preprocessor eliminated 1 constraints from the 
          problem. 
    NOTE: The preprocessor eliminated 9 constraint coefficients 
          from the problem. 
    NOTE: 2 columns, 0 rows and 2 coefficients were added to 
          the problem to handle unrestricted variables, 
          variables that are split, and constraint slack or 
          surplus variables. 
    NOTE: There are 78 nonzero elements in A * A transpose. 
    NOTE: Of the 26 rows and columns, 15 are sparse. 
    NOTE: There are 87 nonzero superdiagonal elements in the 
          sparse rows of the factored A * A transpose. This 
          includes fill-in. 
    NOTE: There are 104 operations of the form 
          u[i,j]=u[i,j]-u[q,j]*u[q,i]/u[q,q] to factorize the 
          sparse rows of A * A transpose. 
 Iter Complem_aff Complem-ity  Duality_gap Tot_infeasb  Tot_infeasc Tot_infeasd 
    0   -1.000000   182185121     0.837584       55030        37757       47382 
    1    56730833    28510760     0.910015 5004.066395  3433.344938 6917.139928 
    2     9604878     2589633     0.665677           0 1.309672E-10  226.047223 
    3      328091      309636     0.191136           0            0   26.943297 
    4      135892       89815     0.063031           0            0    6.389904 
    5       62039       31604     0.022877           0            0           0 
    6       16881 7606.584128     0.005568           0            0           0 
    7 3753.426021 1918.980183     0.001408           0            0           0 
    8  709.549939  330.027670     0.000242           0            0           0 
    9  155.181759   36.697802  0.000026949           0            0           0 
   10    3.865957    0.421161  0.000000309           0            0           0 
   11    0.001557 0.000021177 1.557982E-11           0            0           0 
    NOTE: The Primal-Dual Predictor-Corrector Interior Point algorithm 
          performed 11 iterations. 
    NOTE: Objective = -1295542.742. 
    NOTE: The data set WORK.ARC7 has 68 observations and 14 
          variables. 
    NOTE: There were 68 observations read from the data set 
          WORK.ARC6. 
    NOTE: There were 8 observations read from the data set 
          WORK.NODE0. 
    NOTE: There were 31 observations read from the data set 
          WORK.CON6.
 

The optimal solution data set, CONOUT=ARC7, is given in Output 2.5.1.

  
    proc print data=arc7; 
       var _tail_ _head_ _name_ _cost_ _capac_ _lo_ 
           _flow_ _fcost_; 
       sum _fcost_; 
       run;
 

The optimal value of the nonarc variable f2 unused chips is 280. This means that although there are 3,750 chips that can be used at factory 2 in March, only 3,470 are used. As the optimal value of f1 unused chips is zero, all chips available for production in March at factory 1 are used. The nonarc variable f2 chips from mar also has zero optimal value. This means that the April production at factory 2 does not need any chips that could have been held in inventory since March. However, the nonarc variable f1 chips from mar has value of 20. Thus, 3,490 chips should be ordered for factory 2 in March. Twenty of these chips should be held in inventory until April, then sent to factory 1.

Output 2.5.1: CONOUT=ARC7
Nonarc Variables in the Side Constraints

Obs _tail_ _head_ _name_ _cost_ _capac_ _lo_ _FLOW_ _FCOST_
1 fact1_1 f1_apr_1 prod f1 19 apl 78.60 600 50 540.000 42444.00
2 f1_mar_1 f1_apr_1   15.00 50 0 0.000 0.00
3 f1_may_1 f1_apr_1 back f1 19 may 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 prod f1 25 apl 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 back f1 25 may 49.20 15 0 0.000 0.00
8 f2_apr_2 f1_apr_2   21.00 25 0 25.000 525.00
9 fact1_1 f1_mar_1 prod f1 19 mar 127.90 500 50 338.333 43272.83
10 f1_apr_1 f1_mar_1 back f1 19 apl 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 prod f1 25 mar 217.90 400 40 400.000 87160.00
13 f1_apr_2 f1_mar_2 back f1 25 apl 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 116.667 10511.67
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 20.000 220.00
22 fact2_1 f2_apr_1 prod f2 19 apl 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 back f2 19 may 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 prod f2 25 apl 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 back f2 25 may 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 prod f2 19 mar 88.00 450 35 290.000 25520.00
31 f2_apr_1 f2_mar_1 back f2 19 apl 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 prod f2 25 mar 182.00 650 35 650.000 118300.00
34 f2_apr_2 f2_mar_2 back f2 25 apl 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 0.000 0.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 148.333 -48601.42
42 f1_apr_1 shop1_1   -300.00 250 0 250.000 -75000.00
43 f1_may_1 shop1_1   -285.00 250 0 1.667 -475.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 250.000 -72500.00
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   -515.02 99999999 0 347.500 -178969.45
50 f2_mar_2 shop1_2   -567.83 500 0 500.000 -283915.00
51 f2_apr_2 shop1_2   -542.19 500 0 52.500 -28464.98
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 245.000 -134671.60
61 f1_may_2 shop2_2   -500.00 99999999 0 2.500 -1250.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 500.000 -279595.00
64 f2_may_2 shop2_2   -519.06 500 0 122.500 -63584.85
65     f1 chips from mar 1.00 150 0 20.000 20.00
66     f1 unused chips 0.00 99999999 0 0.000 0.00
67     f2 chips from mar 1.00 150 0 0.000 0.00
68     f2 unused chips 0.00 99999999 0 280.000 0.00
                -1295542.74




Previous Page | Next Page | Top of Page