      PROGRAM HPSERTU
      ALLOCATABLE::Q(:,:),na(:),xi(:),nxi(:),NB(:),P(:,:)
      ALLOCATABLE::NCSIZE(:),NCMEM(:),MEMBER(:,:)
      COMMON/PARAM/NOPT,N,k,mtc
      logical mtc
      CHARACTER*80 FNAME,GNAME,INFORM
      ires=1
5010  WRITE(*,*) ' MAIN MENU '
      WRITE(*,*) '    1 UNWEIGHTED GRADIENT WITHIN ROWS AND COLUMNS '
      write(*,*) '      number of strict consistencies minus '
      write(*,*) '      inconsistencies ABOVE the main diagonal'
      WRITE(*,*) '    2 WEIGHTED GRADIENT WITHIN ROWS AND COLUMNS '
      write(*,*) '      weighted by positive or negative differences'
      WRITE(*,*) '    3 UNWEIGHTED GRADIENT WITHIN ROWS AND COLUMNS'
      WRITE(*,*) '      NUMBER OF INCONSISTENCIES TO BE MINIMIZED'
      WRITE(*,*) '    4 WEIGHTED GRADIENT WITHIN ROWS AND COLUMNS'
      WRITE(*,*) '      WEIGHTED INCONSISTENCIES TO BE MINIMIZED'
      WRITE(*,*) ' CHOICE? '
      READ(*,1) NOPT
      WRITE(*,552)
      WRITE(*,*) '1 FOR WITHIN ROW COMPARISONS ONLY, 2 FOR WITHIN COLUM
     &N COMPARISONS ONLY, 3 FOR BOTH COMPARISONS-- THESE CHOICES ARE
     &FOR THE SQUARE DERIVED MATRIX'
      READ(*,*) NCOMP
1     FORMAT(BN,I6)
      WRITE(*,*) '1 FOR WITHIN ROW COMPARISONS ONLY, 2 FOR WITHIN COLUM
     &N COMPARISONS ONLY, 3 FOR BOTH COMPARISONS-- THESE CHOICES ARE
     &FOR THE ORIGINAL RECTANGULAR MATRIX'
      READ(*,*) MCOMP
      WRITE(*,*) ' NUMBER OF ROWS IN THE INPUT MATRIX '
      READ(*,1) NR
      WRITE(*,552)
      WRITE(*,*) ' NUMBER OF COLUMNS IN THE INPUT MATRIX'
      READ(*,1) NC
      N=NR+NC
      WRITE(*,*) 'NUMBER OF INITIAL OBJECT CLASSES TO BE SEQUENCED?'
      READ(*,*) NCLAS
      ALLOCATE (Q(N,N),NA(N),NB(N),XI(2**NCLAS),NXI(2**NCLAS),
     &P(NR,NC),NCSIZE(N),NCMEM(N),MEMBER(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 ')
      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,7799) NOPT
7799  FORMAT(' OPTIMIZATION MENU OPTION ',I4)
      WRITE(2,552)
      IF(NCOMP.EQ.1) WRITE(2,*)
     &'WITHIN ROW COMPARISONS ONLY FOR THE DERIVED SQUARE MATRIX'
      IF(NCOMP.EQ.2) WRITE(2,*)
     &'WITHIN COLUMN COMPARISONS ONLY FOR THE DERIVED SQUARE MATRIX'
      IF(NCOMP.EQ.3) WRITE(2,*)
     &'BOTH WITHIN ROW AND COLUMN COMPARISONS USED FOR THE DERIVED
     & SQUARE MATRIX'
      WRITE(2,552)
      IF(MCOMP.EQ.1) WRITE(2,*)
     &'WITHIN ROW COMPARISONS ONLY FOR THE ORIGINAL MATRIX'
      IF(MCOMP.EQ.2) WRITE(2,*)
     &'WITHIN COLUMN COMPARISONS ONLY FOR THE ORIGINAL MATRIX'
      IF(MCOMP.EQ.3) WRITE(2,*)
     &'BOTH WITHIN ROW AND COLUMN COMPARISONS USED FOR THE ORIGINAL
     & MATRIX'
      WRITE(2,552)
      WRITE(2,*) 'INPUT MATRIX '
      DO 1002 I=1,N
      DO 1002 J=1,N
1002  Q(I,J)=0.0
      DO 1006 I=1,NR
      READ(1,INFORM) (Q(I,J+NR),J=1,NC)
      WRITE(2,552)
      WRITE(2,6000) (Q(I,J+NR),J=1,NC)
1006  CONTINUE
6000  FORMAT(2X,6F13.3)
      DO 1004 I=1,N
      DO 1004 J=I+1,N
1004  Q(J,I)=Q(I,J)
      DO 505 I=1,NR
      DO 505 J=1,NC
505   P(I,J)=Q(I,NR+J)
      WRITE(2,552)
      WRITE(*,*) 'OBJECT CLASSES TO BE PARTITIONED?'
      WRITE(*,*) '1 THE SAME AS THE NUMBER OF OBJECTS'
      WRITE(*,*) '2 OBJECT CLASS MEMBERSHIP TO BE INPUT'
      READ(*,*) NOBCL
      IF(NOBCL.EQ.2) GO TO 4000
      DO 4001 I=1,N
      NCSIZE(I)=1
4001  MEMBER(I,1)=I
      GO TO 4002
4000  WRITE(*,*) 'INPUT CLASS MEMBERSHIP(SEPARATED BY BLANKS)'
      WRITE(*,*) 'WITH ZEROS INDICATING A DELETED OBJECT'
      READ(*,*) (NCMEM(I),I=1,N)
4003  FORMAT(40I2)
      DO 4004 I=1,N
4004  NCSIZE(I)=0
      DO 4005 I=1,N
      DO 4006 J=1,N
      IF(NCMEM(I).EQ.J) NCSIZE(J)=NCSIZE(J)+1
      IF(NCMEM(I).EQ.J) MEMBER(J,NCSIZE(J))=I
4006  CONTINUE
4005  CONTINUE
4002  WRITE(2,*) 'CLASS NUMBER / OBJECT MEMBERSHIP IN CLASS'
      DO 4009 I=1,NCLAS
4009  WRITE(2,4008) I,(MEMBER(I,J),J=1,NCSIZE(I))
4008  FORMAT(I3,10X,20I3)
6500  WRITE(*,*) ' PROGRAM RUNNING '
      WRITE(*,552)
      Z=-1.0e+20
      IF(NOPT.LE.2) Z=Z
      IF(NOPT.GT.2) Z=-Z
      NZ=0
      NSUM=(2**NCLAS)-1
      DO 2 I=1,NSUM
      xi(i)=z
2     nxi(i)=nz
      DO 560 I=1,NCLAS
      INDEX=2**(I-1)
      xi(index)=0.0
560   nxi(index)=i
564   K=0
4     K=K+1
      WRITE(*,3012) K
3012  FORMAT(' PROCESSING SUBSETS OF SIZE ',I4)
      IF(K.EQ.NCLAS) 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.(NCLAS-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.(NCLAS-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,NCLAS
      DO 8 J=1,K
      IF(NA(J).EQ.I) GO TO 7
8     CONTINUE
      NB(JJ)=I
      JJ=JJ+1
7     CONTINUE
      NK=NCLAS-K
      DO 9 JJ=1,NK
      J1=NB(JJ)
      SUM=0.0
      GO TO (13,5005,13,5005) NOPT
13    IF(NCOMP.EQ.2) GO TO 8000
      DO 15 I=1,K
      DO 15 L1=1,NCSIZE(NA(I))
      I1=NA(I)
      DO 16 J=1,NK
      DO 16 L2=1,NCSIZE(NB(J))
      DO 16 L3=1,NCSIZE(J1)
      J2=NB(J)
      IF(J2.EQ.J1) GO TO 16
      IF((MEMBER(I1,L1).LE.NR).AND.((MEMBER(J1,L3).LE.NR).OR.
     &(MEMBER(J2,L2).LE.NR))) GO TO 16
      IF((MEMBER(I1,L1).GT.NR).AND.((MEMBER(J1,L3).GT.NR).OR.  
     &(MEMBER(J2,L2).GT.NR))) GO TO 16
      IF((MCOMP.EQ.1).AND.(MEMBER(I1,L1).GT.NR)) GO TO 16
      IF((MCOMP.EQ.2).AND.(MEMBER(I1,L1).LE.NR)) GO TO 16
      IF((NOPT.EQ.1).AND.(Q(MEMBER(I1,L1),MEMBER(J1,L3)).LT.  
     &Q(MEMBER(I1,L1),MEMBER(J2,L2)))) SUM=SUM+1.0
      IF(Q(MEMBER(I1,L1),MEMBER(J1,L3)).GT.
     &Q(MEMBER(I1,L1),MEMBER(J2,L2))) SUM=SUM-1.0
16    CONTINUE
15    CONTINUE
8000  IF(NCOMP.EQ.1) GO TO 14
      DO 17 J=1,NK
      DO 17 L2=1,NCSIZE(NB(J))
      J2=NB(J)
      IF(J2.EQ.J1) GO TO 17
      DO 18 I=1,K
      DO 18 L1=1,NCSIZE(NA(I))
      DO 18 L3=1,NCSIZE(J1)
      I1=NA(I)
      IF((MEMBER(J2,L2).LE.NR).AND.((MEMBER(J1,L3).LE.NR).OR.
     &(MEMBER(I1,L1).LE.NR))) GO TO 18
      IF((MEMBER(J2,L2).GT.NR).AND.((MEMBER(J1,L3).GT.NR).OR.  
     &(MEMBER(I1,L1).GT.NR))) GO TO 18
      IF((MCOMP.EQ.1).AND.(MEMBER(J2,L2).GT.NR)) GO TO 18
      IF((MCOMP.EQ.2).AND.(MEMBER(J2,L2).LE.NR)) GO TO 18
      IF((NOPT.EQ.1).AND.(Q(MEMBER(J1,L3),MEMBER(J2,L2)).LT.  
     &Q(MEMBER(I1,L1),MEMBER(J2,L2)))) SUM=SUM+1.0
      IF(Q(MEMBER(J1,L3),MEMBER(J2,L2)).GT.
     &Q(MEMBER(I1,L1),MEMBER(J2,L2))) SUM=SUM-1.0
18    CONTINUE
17    CONTINUE
      GO TO 14
5005  IF(NCOMP.EQ.2) GO TO 8001
      DO 715 I=1,K
      DO 715 L1=1,NCSIZE(NA(I))
      I1=NA(I)
      DO 716 J=1,NK
      J2=NB(J)
      DO 716 L2=1,NCSIZE(NB(J))
      DO 716 L3=1,NCSIZE(J1)
      IF(J2.EQ.J1) GO TO 716
      IF((MEMBER(I1,L1).LE.NR).AND.((MEMBER(J1,L3).LE.NR).OR.  
     &(MEMBER(J2,L2).LE.NR))) GO TO 716
      IF((MEMBER(I1,L1).GT.NR).AND.((MEMBER(J1,L3).GT.NR).OR.  
     &(MEMBER(J2,L2).GT.NR))) GO TO 716
      IF((MCOMP.EQ.1).AND.(MEMBER(I1,L1).GT.NR)) GO TO 716
      IF((MCOMP.EQ.2).AND.(MEMBER(I1,L1).LE.NR)) GO TO 716
      IF(NOPT.EQ.2) SUM=SUM+
     &Q(MEMBER(I1,L1),MEMBER(J2,L2))-Q(MEMBER(I1,L1),MEMBER(J1,L3))
      IF((NOPT.EQ.4).AND.((Q(MEMBER(I1,L1),MEMBER(J2,L2))-
     &Q(MEMBER(I1,L1),MEMBER(J1,L3))).LT.0.0))
     &SUM=SUM+Q(MEMBER(I1,L1),MEMBER(J2,L2))-
     &Q(MEMBER(I1,L1),MEMBER(J1,L3))
716    CONTINUE
715    CONTINUE
8001  IF(NCOMP.EQ.1) GO TO 14
      DO 717 J=1,NK
      DO 717 L2=1,NCSIZE(NB(J))
      J2=NB(J)
      IF(J2.EQ.J1) GO TO 717
      DO 718 I=1,K
      DO 718 L1=1,NCSIZE(NA(I))
      DO 718 L3=1,NCSIZE(J1)
      I1=NA(I)
      IF((MEMBER(J2,L2).LE.NR).AND.((MEMBER(J1,L3).LE.NR).OR.  
     &(MEMBER(I1,L1).LE.NR))) GO TO 718
      IF((MEMBER(J2,L2).GT.NR).AND.((MEMBER(J1,L3).GT.NR).OR.  
     &(MEMBER(I1,L1).GT.NR))) GO TO 718
      IF((MCOMP.EQ.1).AND.(MEMBER(J2,L2).GT.NR)) GO TO 718
      IF((MCOMP.EQ.2).AND.(MEMBER(J2,L2).LE.NR)) GO TO 718
      IF(NOPT.EQ.2) SUM=SUM+
     &Q(MEMBER(I1,L1),MEMBER(J2,L2))-Q(MEMBER(J1,L3),MEMBER(J2,L2))
      IF((NOPT.EQ.4).AND.((Q(MEMBER(I1,L1),MEMBER(J2,L2))-
     &Q(MEMBER(J1,L3),MEMBER(J2,L2))).LT.0.0))
     &SUM=SUM+Q(MEMBER(I1,L1),MEMBER(J2,L2))-
     &Q(MEMBER(J1,L3),MEMBER(J2,L2))
718    CONTINUE
717    CONTINUE
      GO TO 14
14    s=xi(index)
      IF(NOPT.GT.2) SUM=ABS(SUM)
      TEMP=S+SUM
      INDEXT=INDEX+2**(J1-1)
      cp=xi(indext)
      IF((NOPT.LE.2).AND.(TEMP.LT.CP)) GO TO 9
      IF((NOPT.GT.2).AND.(TEMP.GT.CP)) GO TO 9
      xi(indext)=temp
      nxi(indext)=j1
9     CONTINUE
      IF(MTC) GO TO 6
      GO TO 4
5     smax=xi(nsum)
      nt=nxi(nsum)
      WRITE(2,552)
      WRITE(2,*) ' CUMULATIVE OBJECTIVE FUNCTION     PERMUTATION IN REVE
     &RSE ORDER '
      WRITE(2,1010) SMAX,NT
      NA(NCLAS)=NT
1010  FORMAT(9X,F13.3,13X,I12)
      NN=NCLAS-1
      INDEX=NSUM
      DO 12 I=1,NN
      INDEX=INDEX-(2**(NT-1))
      nt=nxi(index)
      s=xi(index)
      NA(NCLAS-I)=NT
12    WRITE(2,1010) S,NT
      GO TO (2000,5006,2000,5006) NOPT
5006  WRITE(2,552)
      WRITE(2,5007) SMAX
      XNCON=0.0
      XNDIF=0.0
      DO 8022 K=1,NCLAS
      DO 8022 L3=1,NCSIZE(NA(K))
      DO 8022 J=1,K-1
      DO 8022 L2=1,NCSIZE(NA(J))
      DO 8022 I=1,J-1
      DO 8022 L1=1,NCSIZE(NA(I))
      IF(((K.EQ.J).OR.(K.EQ.I)).OR.(J.EQ.I)) GO TO 8022
      IF(((MEMBER(NA(I),L1).LE.NR).AND.((MEMBER(NA(K),L3).LE.NR).OR.  
     &(MEMBER(NA(J),L2).LE.NR))).OR.((MEMBER(NA(I),L1).GT.NR).AND.  
     &((MEMBER(NA(K),L3).GT.NR).OR.(MEMBER(NA(J),L2).GT.NR))))
     &GO TO 9051
      IF(((MCOMP.EQ.1).AND.(MEMBER(NA(I),L1).GT.NR)).OR.  
     &((MCOMP.EQ.2).AND.(MEMBER(NA(I),L1).LE.NR))) GO TO 9051
      IF((NCOMP.NE.2).AND.(Q(MEMBER(NA(I),L1),MEMBER(NA(J),L2)).LT.  
     &Q(MEMBER(NA(I),L1),MEMBER(NA(K),L3))))
     &XNCON=XNCON+Q(MEMBER(NA(I),L1),MEMBER(NA(K),L3))-
     &Q(MEMBER(NA(I),L1),MEMBER(NA(J),L2))
      IF((NCOMP.NE.2).AND.(Q(MEMBER(NA(I),L1),MEMBER(NA(J),L2)).GT.  
     &Q(MEMBER(NA(I),L1),MEMBER(NA(K),L3))))
     &XNDIF=XNDIF+Q(MEMBER(NA(I),L1),MEMBER(NA(J),L2))-
     &Q(MEMBER(NA(I),L1),MEMBER(NA(K),L3))
9051  IF(((MEMBER(NA(K),L3).LE.NR).AND.((MEMBER(NA(I),L1).LE.NR).OR.
     &(MEMBER(NA(J),L2).LE.NR))).OR.((MEMBER(NA(K),L3).GT.NR).AND.  
     &((MEMBER(NA(I),L1).GT.NR).OR.(MEMBER(NA(J),L2).GT.NR))))
     &GO TO 8022
      IF(((MCOMP.EQ.1).AND.(MEMBER(NA(K),L3).GT.NR)).OR.((MCOMP.EQ.2)
     &.AND.(MEMBER(NA(K),L3).LE.NR))) GO TO 8022
      IF((NCOMP.NE.1).AND.(Q(MEMBER(NA(J),L2),MEMBER(NA(K),L3)).LT.  
     &Q(MEMBER(NA(I),L1),MEMBER(NA(K),L3))))
     &XNCON=XNCON+Q(MEMBER(NA(I),L1),MEMBER(NA(K),L3))-
     &Q(MEMBER(NA(J),L2),MEMBER(NA(K),L3))
      IF((NCOMP.NE.1).AND.(Q(MEMBER(NA(J),L2),MEMBER(NA(K),L3)).GT.  
     &Q(MEMBER(NA(I),L1),MEMBER(NA(K),L3))))
     &XNDIF=XNDIF+Q(MEMBER(NA(J),L2),MEMBER(NA(K),L3))-
     &Q(MEMBER(NA(I),L1),MEMBER(NA(K),L3))
8022  CONTINUE
      WRITE(2,552)
      SUM=XNCON+XNDIF
      DIF=XNCON-XNDIF
      WRITE(2,8003) XNCON,XNDIF,DIF,SUM,DIF/SUM
      GO TO 7777
5007  FORMAT(' INDEX OF GRADIENT COMPARISON IS', F9.3)
552   FORMAT(1H )
2000  CM=1.0
2005  SMAX=SMAX/CM
      WRITE(2,552)
      WRITE(2,5007) SMAX
      XNCON=0.0
      XNDIF=0.0
      DO 8002 K=1,NCLAS
      DO 8002 L3=1,NCSIZE(NA(K))
      DO 8002 J=1,K-1
      DO 8002 L2=1,NCSIZE(NA(J))
      DO 8002 I=1,J-1
      DO 8002 L1=1,NCSIZE(NA(I))
      IF(((K.EQ.J).OR.(K.EQ.I)).OR.(J.EQ.I)) GO TO 8002
      IF(((MEMBER(NA(I),L1).LE.NR).AND.((MEMBER(NA(K),L3).LE.NR).OR.  
     &(MEMBER(NA(J),L2).LE.NR))).OR.((MEMBER(NA(I),L1).GT.NR).AND.  
     &((MEMBER(NA(K),L3).GT.NR).OR.(MEMBER(NA(J),L2).GT.NR))))
     &GO TO 9050
      IF(((MCOMP.EQ.1).AND.(MEMBER(NA(I),L1).GT.NR)).OR.  
     &((MCOMP.EQ.2).AND.(MEMBER(NA(I),L1).LE.NR))) GO TO 9050
      IF((NCOMP.NE.2).AND.(Q(MEMBER(NA(I),L1),MEMBER(NA(J),L2)).LT.  
     &Q(MEMBER(NA(I),L1),MEMBER(NA(K),L3))))
     &XNCON=XNCON+1.0
      IF((NCOMP.NE.2).AND.(Q(MEMBER(NA(I),L1),MEMBER(NA(J),L2)).GT.  
     &Q(MEMBER(NA(I),L1),MEMBER(NA(K),L3))))
     &XNDIF=XNDIF+1.0
9050  IF(((MEMBER(NA(K),L3).LE.NR).AND.((MEMBER(NA(I),L1).LE.NR).OR.  
     &(MEMBER(NA(J),L2).LE.NR))).OR.((MEMBER(NA(K),L3).GT.NR).AND.  
     &((MEMBER(NA(I),L1).GT.NR).OR.(MEMBER(NA(J),L2).GT.NR))))
     &GO TO 8002
      IF(((MCOMP.EQ.1).AND.(MEMBER(NA(K),L3).GT.NR)).OR.((MCOMP.EQ.2)
     &.AND.(MEMBER(NA(K),L3).LE.NR))) GO TO 8002
      IF((NCOMP.NE.1).AND.(Q(MEMBER(NA(J),L2),MEMBER(NA(K),L3)).LT.  
     &Q(MEMBER(NA(I),L1),MEMBER(NA(K),L3))))
     &XNCON=XNCON+1.0
      IF((NCOMP.NE.1).AND.(Q(MEMBER(NA(J),L2),MEMBER(NA(K),L3)).GT.  
     &Q(MEMBER(NA(I),L1),MEMBER(NA(K),L3))))
     &XNDIF=XNDIF+1.0
8002  CONTINUE
      WRITE(2,552)
      SUM=XNCON+XNDIF
      DIF=XNCON-XNDIF
      WRITE(2,8003) XNCON,XNDIF,DIF,SUM,DIF/SUM
8003  FORMAT('CONSISTENCIES ',F10.3,' INCONSISTENCIES ',F10.3,
     &' DIFFERENCE',F10.3,' SUM',F10.3,' RATIO',F10.3)
      GO TO 7777
7777  STOP
      END
