Vast Difference Between PROC INTPOINT and PROC LP Results

Vast Difference Between PROC INTPOINT and PROC LP Results

Post by topkat » Tue, 14 Sep 2004 23:10:38


i.

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
422 sparsedata
423 bytes = 100000000
424 maxiterb = 1999
425 rttol = 1E-12
426 maximize
427 ;
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
variables.
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
6 variables.
NOTE: There were 453607 observations read from the data set
SFD.SO04_S26_USE03_LPM_2S.
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
520 sparsedata
521 preprocess
522 MAXIT1=99999
523 MAXIT2=99999
524 epsilon = 1E-4
525 time = 4800
526 ;
527 * print best ; * evidently only for integer soln ;
528
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
10 variables.
NOTE: PROCEDURE LP used:
real time 50:36.25
cpu time 47:56.57


530
531 %put _ORLP_ = ;
_ORLP_ =
532 %put &_ORLP_. ;
STATUS=SUCCESSFUL PHASE=2 OBJECTIVE=577043483485.813 P_FEAS=YES D_FEAS=YES
PHASE1_ITER=22795
PHASE2_ITER=20209 PHASE3_ITER=0
533
534 quit / save ;
535
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