I just recently heard about PROC INTPOINT, the specialized new procedure
for linear programming that has been included in SAS/OR since release 8.1.
I only have a more or less nodding acquaintance with the details of
interior point methodology for linear programming, but I was told that PROC
INTPOINT was fast, and could handle larger, more complex LPs than PROC LP,
so I thought I'd check it out.
Here are logs from the same input matrix (in sparse format) to both procs.
For this problem, it took some tuning (e.g., in the numbers of iterations
and time allowed) to get both procedures to run to completion...
PROC INTPOINT output:
420 proc intpoint condata = SFD.SO04_S26_USE03_lpm_2s
421 conout = SFD.SO04_S26_USE03_lpm_2io_d
423 bytes = 100000000
424 maxiterb = 1999
425 rttol = 1E-12
428 run ;
NOTE: Number of variables= 86372 .
NOTE: Number of <= constraints= 4 .
NOTE: Number of == constraints= 0 .
NOTE: Number of >= constraints= 21741 .
NOTE: Number of constraint coefficients= 259116 .
NOTE: 21745 columns, 0 rows and 21745 coefficients were added to the
problem to handle
unrestricted variables, variables that are split, and constraint
slack or surplus
NOTE: There are 172892 nonzero elements in A * A transpose.
NOTE: Of the 21745 rows and columns, 21733 are sparse.
NOTE: There are 173504 nonzero superdiagonal elements in the sparse rows of
the factored A * A
transpose. This includes fill-in.
NOTE: There are 466836 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.
NOTE: The Primal-Dual Predictor-Corrector Interior Point algorithm
performed 1346 iterations.
NOTE: Objective= 885896.14315.
NOTE: The data set SFD.SO04_S26_USE03_LPM_2IO_D has 86372 observations and
NOTE: There were 453607 observations read from the data set
NOTE: PROCEDURE INTPOINT used:
real time 15:00.58
cpu time 14:26.05
PROC LP output:
518 proc lp data = SFD.SO04_S26_USE03_lpm_2s
519 primalout = SFD.SO04_S26_USE03_lpm_2o_d
524 epsilon = 1E-4
525 time = 4800
527 * print best ; * evidently only for integer soln ;
529 run ;
NOTE: Preprocessing 1 ...
NOTE: 10 constraints eliminated.
NOTE: 86372 upper bounds decreased.
NOTE: Preprocessing 2 ...
NOTE: Preprocessing done.
NOTE: The data set SFD.SO04_S26_USE03_LPM_2O_D has 108119 observations and
NOTE: PROCEDURE LP used:
real time 50:36.25
cpu time 47:56.57
531 %put _ORLP_ = ;
532 %put &_ORLP_. ;
STATUS=SUCCESSFUL PHASE=2 OBJECTIVE=577043483485.813 P_FEAS=YES D_FEAS=YES
534 quit / save ;
536 quit ;
PROC INTPOINT certainly did go faster, by a factor of three in this case,
but I know the data well enough to say that the result of PROC LP looks
correct, and the r