| The INTPOINT Procedure |
Example 2.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 2.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 nonzero elements in A * A transpose.
NOTE: Of the 25 rows and columns, 14 are sparse.
NOTE: There are 74 nonzero superdiagonal elements in the
sparse rows of the factored A * A transpose. This
includes fill-in.
NOTE: There are 65 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 176663849 0.834344 52835 39643 49140
1 51289701 21890177 0.912033 2958.813395 2220.091192 2621.647223
2 4297808 1359558 0.517260 0 7.06244E-11 42.614836
3 341918 246210 0.159762 0 0 7.723054
4 124303 68295 0.049237 0 0 1.115512
5 46970 29876 0.021786 0 0 0.482224
6 9976.439552 6294.587840 0.004647 0 0 0.094764
7 3266.423958 1984.437170 0.001468 0 0 0.022740
8 472.139836 257.075141 0.000190 0 0 0.003062
9 24.953361 6.458585 0.000004781 0 0 0.000114
10 0.007991 0.000361 2.671196E-10 0 0 0
NOTE: The Primal-Dual Predictor-Corrector Interior Point algorithm
performed 10 iterations.
NOTE: Objective = -1282708.625.
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 2.3.1: CONOUT=ARC4
Copyright © 2008 by SAS Institute Inc., Cary, NC, USA. All rights reserved.