      PROGRAM DPSERPH
      ALLOCATABLE:: Q(:,:),NA(:),NB(:),XI(:,:),NXI(:,:),NPREC(:,:)
      COMMON/PARAM/NOPT,N,k,mtc
      logical mtc
      CHARACTER*80 FNAME,GNAME,INFORM
501   WRITE(*,*) ' MAIN MENU '
      write(*,*) '    1 MINIMUM PATH'
      write(*,*) '    2 MINIMAX PATH'
      WRITE(*,*) '    3 MAXIMUM PATH'
      WRITE(*,*) '    4 MAXIMIN PATH'
      WRITE(*,*) '    5 MINIMUM CIRCULAR PATH'
      WRITE(*,*) '    6 MINIMAX CIRCULAR PATH'
      WRITE(*,*) '    7 MAXIMUM CIRCULAR PATH'
      WRITE(*,*) '    8 MAXIMIN CIRCULAR PATH'
      WRITE(*,*) ' CHOICE? '
      READ(*,1) NOPT
      WRITE(*,552)
1     FORMAT(BN,I6)
552   FORMAT(1H )
      WRITE(*,*) ' NUMBER OF ROWS/COLUMNS IN THE INPUT MATRIX '
      READ(*,1) N
      WRITE(*,*) '0 FOR NO PRECEDENT MATRIX TO BE READ IN AFTER THE
     &DATA; 1 IF A SQUARE PRECEDENT MATRIX TO BE USED (20I2 FORMAT; 0/1
     &WHERE A 1 IF THE ROW OBJECT MUST COME AFTER THE COLUMN OBJECT'
      READ(*,*) MPREC
      ALLOCATE (Q(N,N),NA(N),XI(2**N,N),NXI(2**N,N),NB(N),NPREC(N,N),
     &STAT=IERR)
      IF(IERR.NE.0) WRITE(*,*) 'ARRAY ALLOCATION ERROR'
      IF(IERR.NE.0) STOP
      IF(IERR.EQ.0) WRITE(*,*) 'ARRAY ALLOCATION SUCCESSFUL'
      WRITE(*,*) ' FILE NAME FOR THE INPUT MATRIX '
      READ(*,'(A)') FNAME
      WRITE(*,552)
      WRITE(*,*) ' FILE NAME FOR THE OUTPUT '
      READ(*,'(A)') GNAME
      WRITE(*,552)
      WRITE(*,550)
      WRITE(*,*) FNAME
      WRITE(*,*) GNAME
550   FORMAT(' INPUT AND OUTPUT FILES ARE ')
505   WRITE(*,*) ' IS THE INPUT MATRIX SYMMETRIC AND READ AS A LOWER'
      WRITE(*,*) ' TRIANGULAR MATRIX WITHOUT DIAGONAL ENTRIES OR AS'
      WRITE(*,*) ' A COMPLETE SQUARE MATRIX '
      WRITE(*,*) '    1 LOWER TRIANGULAR '
      WRITE(*,*) '    2 COMPLETE SQUARE '
      WRITE(*,*) ' CHOICE? '
      READ(*,1) NSYM
      WRITE(*,552)
      GO TO (504,504) NSYM
      GO TO 505
504   WRITE(*,*) ' PROVIDE FORMAT FOR THE INPUT MATRIX '
      READ(*,'(A)') INFORM
      WRITE(*,552)
      WRITE(*,551)
      WRITE(*,*) INFORM
551   FORMAT(' INPUT FORMAT IS ')
      OPEN(1,FILE=FNAME)
      OPEN(2,FILE=GNAME,STATUS='NEW')
      WRITE(2,552)
      WRITE(2,552)
      WRITE(2,7799) NOPT
7799  FORMAT( 'OPTIMIZATION MENU OPTION', I4)
      WRITE(2,552)
      WRITE(2,*) 'INPUT MATRIX '
      IF(NSYM.EQ.2) GO TO 1001
      DO 1002 I=2,N
      ISTOP=I-1
      READ(1,INFORM) (Q(I,J),J=1,ISTOP)
      WRITE(2,552)
      WRITE(2,677) (Q(I,J),J=1,ISTOP)
1002  CONTINUE
      DO 1004 I=1,N
      Q(I,I)=0.0
      DO 1004 J=I+1,N
      Q(I,J)=Q(J,I)
1004  CONTINUE
      WRITE(2,552)
      GO TO 7777
1001  DO 1006 I=1,N
      READ(1,INFORM) (Q(I,J),J=1,N)
      WRITE(2,552)
      WRITE(2,677) (Q(I,J),J=1,N)
      Q(I,I)=0.0
1006  CONTINUE
677   FORMAT(2X,6F13.3)
7777  WRITE(2,552)
      IF(MPREC.EQ.0) GO TO 6500
      WRITE(2,*) 'PRECEDENT MATRIX'
      WRITE(2,552)
      DO 6501 I=1,N
      READ(1,6502) (NPREC(I,J),J=1,N)
      WRITE(2,6502) (NPREC(I,J),J=1,N)
6501  CONTINUE
      WRITE(2,552)
6502  FORMAT(20I2)
6500  WRITE(*,*) ' PROGRAM RUNNING '
      WRITE(*,552)
      Z=0.0
      NZ=0
      ZBIG=1.0E+20
      IF((NOPT.EQ.1).OR.((NOPT.EQ.2).OR.((NOPT.EQ.5).OR.(NOPT.EQ.6))))
     &ZINT=ZBIG
      IF((NOPT.EQ.3).OR.((NOPT.EQ.4).OR.((NOPT.EQ.7).OR.(NOPT.EQ.8))))
     &ZINT=Z
      NSUM=(2**N)-1
      DO 2 I=1,NSUM
      DO 2 J=1,N
      NXI(I,J)=NZ
2     XI(I,J) =ZINT
      DO 7050 I=1,N
      INDEX=2**(I-1)
      XI(INDEX,I)=0.0
      IF(((NOPT.EQ.5).OR.(NOPT.EQ.6)).AND.(I.NE.1)) XI(INDEX,I)=ZBIG
      IF(((NOPT.EQ.7).OR.(NOPT.EQ.8)).AND.(I.NE.1)) XI(INDEX,I)=-ZBIG
7050  CONTINUE
      K=0
4     K=K+1
      WRITE(*,3012) K
3012  FORMAT(' PROCESSING SUBSETS OF SIZE ',I4)
      IF(K.EQ.N) GO TO 5
      MTC=.FALSE.
6     go to 30
30    IF(MTC) GO TO 40
      M2=0
      nH=K
      GO TO 50
40    IF(M2.LT.(N-nH)) nH=0
      nH=nH+1
      M2=NA(K+1-nH)
50    DO 51 J=1,nH
51    NA(K+J-nH)=M2+J
      MTC=NA(1).NE.(N-K+1)
      go to 6050
6050  INDEX=0
      DO 10 I=1,K
10    INDEX=INDEX+2**(NA(I)-1)
      JJ=1
      DO 7 I=1,N
      DO 8 J=1,K
      IF(NA(J).EQ.I) GO TO 7
8     CONTINUE
      NB(JJ)=I
      JJ=JJ+1
7     CONTINUE
      NK=N-K
      IF(MPREC.EQ.0) GO TO 20
      IOUT=0
      DO 6506 I=1,K
      DO 6506 J=1,NK
      IF(NPREC(NA(I),NB(J)).EQ.1) IOUT=1
      IF(NPREC(NA(I),NB(J)).EQ.1) EXIT
6506  CONTINUE
      IF(IOUT.EQ.0) GO TO 20
      IF(MTC) GO TO 6
      GO TO 4
20    DO 9 JJ=1,NK
      J1=NB(JJ)
      DO 800 II=1,K
      I1=NA(II)
      SUM=0.0
      SUM=Q(I1,J1)
      S=XI(INDEX,I1)
      GO TO (8060,8061,8060,8062,8060,8061,8060,8062) NOPT
8060  TEMP=S+SUM
      GO TO 8091
8062  TEMP=MIN(S,SUM)
      IF((K.EQ.1).AND.(NOPT.EQ.4)) TEMP=SUM
      IF((K.EQ.1).AND.((NOPT.EQ.8).AND.(I1.EQ.1))) TEMP=SUM
      GO TO 8091
8061  TEMP=MAX(S,SUM)
8091  INDEXT=INDEX+2**(J1-1)
      CP=XI(INDEXT,J1)
      IF((TEMP.LT.CP).AND.(((NOPT.EQ.3).OR.(NOPT.EQ.4)).OR.
     &((NOPT.EQ.7).OR.(NOPT.EQ.8)))) GO TO 800
      IF((TEMP.GT.CP).AND.(((NOPT.EQ.1).OR.(NOPT.EQ.2)).OR.
     &((NOPT.EQ.5).OR.(NOPT.EQ.6)))) GO TO 800
      XI(INDEXT,J1) = TEMP
      NXI(INDEXT,J1)=I1
800   CONTINUE
9     CONTINUE
      IF(MTC) GO TO 6
      GO TO 4
5     INDEX=NSUM
      SMIN=1.0E+20
      SMAX=0.0
      NTMIN=0
      NTMAX=0
      DO 806 I=1,N
      IF(NOPT.GE.5) GO TO 8000
      IF(XI(INDEX,I).GT.SMAX) NTMAX=I
      IF(XI(INDEX,I).GT.SMAX) SMAX=XI(INDEX,I)
      IF(XI(INDEX,I).LT.SMIN) NTMIN=I
      IF(XI(INDEX,I).LT.SMIN) SMIN=XI(INDEX,I)
      GO TO 806
8000  IF((NOPT.EQ.5).AND.((XI(INDEX,I)+Q(I,1)).LT.SMIN)) NTMIN=I
      IF((NOPT.EQ.5).AND.((XI(INDEX,I)+Q(I,1)).LT.SMIN))
     &SMIN=XI(INDEX,I)+Q(I,1)
      IF((NOPT.EQ.6).AND.(MAX(XI(INDEX,I),Q(I,1)).LT.SMIN))
     &NTMIN=I
      IF((NOPT.EQ.6).AND.(MAX(XI(INDEX,I),Q(I,1)).LT.SMIN))
     &SMIN=MAX(XI(INDEX,I),Q(I,1))
      IF((NOPT.EQ.7).AND.((XI(INDEX,I)+Q(I,1)).GT.SMAX)) NTMAX=I
      IF((NOPT.EQ.7).AND.((XI(INDEX,I)+Q(I,1)).GT.SMAX))
     &SMAX=XI(INDEX,I)+Q(I,1)
      IF((NOPT.EQ.8).AND.(MIN(XI(INDEX,I),Q(I,1)).GT.SMAX))
     &NTMAX=I
      IF((NOPT.EQ.8).AND.(MIN(XI(INDEX,I),Q(I,1)).GT.SMAX))
     &SMAX=MIN(XI(INDEX,I),Q(I,1))
806   CONTINUE
      WRITE(2,552)
      IF(((NOPT.EQ.1).OR.(NOPT.EQ.2)).OR.((NOPT.EQ.5).OR.(NOPT.EQ.6)))
     &IOPT=1
      IF(((NOPT.EQ.3).OR.(NOPT.EQ.4)).OR.((NOPT.EQ.7).OR.(NOPT.EQ.8)))
     &IOPT=2
      DO 807 J=1,N-1
      IF(IOPT.EQ.1) WRITE(2,810) SMIN,NTMIN
      IF(IOPT.EQ.2) WRITE(2,810) SMAX,NTMAX
810   FORMAT('CUMULATIVE OBJECTIVE',F10.3,'    LAST OBJECT',I10)
      IF(IOPT.EQ.1) NA(N-J+1) = NTMIN
      IF(IOPT.EQ.2) NA(N-J+1) = NTMAX
      IF(IOPT.EQ.1) NTMIN=NXI(INDEX,NTMIN)
      IF(IOPT.EQ.2) NTMAX=NXI(INDEX,NTMAX)
      INDEX=INDEX-(2**(NA(N-J+1)-1))
      IF(IOPT.EQ.1) SMIN=XI(INDEX,NTMIN)
      IF(IOPT.EQ.2) SMAX=XI(INDEX,NTMAX)
807   CONTINUE
      DO 830 I=1,N
      IF(INDEX.EQ.(2**(I-1))) NA(1)=I
830   CONTINUE
      WRITE(2,831) XI(INDEX,NA(1)),NA(1)
831   FORMAT('BEGINNING OBJECTIVE'  ,F10.3,'    FIRST OBJECT',I10)
      WRITE(2,552)
      WRITE(2,*) ' REORDERED MATRIX '
      DO 600 I=1,N
      IP=NA(I)
      WRITE(2,552)
      WRITE(2,677) (Q(IP,NA(J)),J=1,N)
600   CONTINUE
      STOP
      END
