COMMON/ONE/IDIS(20,20),IFLOW(20,20)
      COMMON/TWO/IPAIR(20,20),ICOST(20,20,20,20),ICONST(20,20)
      COMMON/THREE/NUMP(400),NUML(400),IFREEP(20),IFREEL(20),IROW(20),
     /ICOL(20)
      COMMON/FOUR/IGILAW(20,20),C(20,20),IRSL(20)
      COMMON/FIVE/ICUR(20),IFIX1(20,2)
      INTEGER C
c     real       time(2), tstart, tstop, dtime, etime, temp
C     real       tstart,tstop,dtime 
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
c     temp=etime(time)
c     tstart=time(1)
C     DO 1000 ICOUNT =1,4
C     TSTART = MCLOCK()/100.
CCCCCC NEWLP.f generates MPS files for the linearization of Problem
CCCCCC QAP with the appropriate substitution of variables.
      CALL INPUT(M,MMONE,MMTWO)
C     WRITE(6,*)M
      MTWO=M+M
      AT=1.
      MM=M*M
      AAT=-1.
      MTM=2*(M-1)
      WRITE(6,10)M
   10 FORMAT(T1,'NAME',T10,'NEWLP',I2.2)
CCCCCC LIST THE CONSTRAINTS
      WRITE(6,11)
   11 FORMAT(T1,'ROWS')
      WRITE(6,12)
   12 FORMAT(T3,'N',T5,'NOBJ')
CCCCCC THE CONSTRAINTS SUM OF X'S = 1
      DO 14 I=1,MTWO
         WRITE(6,13) I
   13 FORMAT(T3,'E',T5,'NX',I2.2)
   14 CONTINUE
CCCCCC THE CONSTRAINTS SUM OF Y'S = XKL
      DO 16 J=1,MM
      DO 16 I=1,MTM
         WRITE(6,15) I,J
   15 FORMAT(T3,'E',T5,'C',I2.2,'A',I3.3)
   16 CONTINUE
CCCCCC LIST THE VARIABLES & EQUATIONS IN WHICH THEY APPEAR
      WRITE(6,23)
   23 FORMAT(T1,'COLUMNS')
CCCCCC LIST THE X VARIALBLES
      K=0
      DO 27 I=1,M
      DO 27 J=1,M
         K=K+1
         MPJ=M+J
         WRITE(6,24)K,I,AT
         WRITE(6,24)K,MPJ,AT
   24 FORMAT(T5,'X',I3.3,T15,'NX',I2.2,T25,F3.1)
         DO 26 L=1,MTM
            WRITE(6,25)K,L,K,AAT
   25 FORMAT(T5,'X',I3.3,T15,'C',I2.2,'A',I3.3,T25,F4.1)
   26    CONTINUE
   27 CONTINUE
CCCCCC LIST THE YIJKL VARIABLES
CCCCCC IR DESIGNATES THE ROW OF THE FIRST M-1 ROWS OF EACH SUB
CCCCCC PROBLEM & IC DESIGNATES THE POSITION IN THE ROW WHICH
CCCCCC DETERMINES WHICH CONSTRAINT OF 2ND SET OF M-1 CONSTRAINTS
CCCCCC OF EACH SUBPROBLEM THE VARIABLE IS IN (USING IT)
      IRA=0
      DO 39 K=1,M
         IRA=IRA+1
         ICA=0
      DO 39 L=1,M
         KL=(K-1)*M+L
         ICA=ICA+1
         IR=0
         DO 38 I=1,M
            IR=IR+1
            IF(I.LE.K) GO TO 38
CCCCCC
CCCCCC I>K
            IC=0
            DO 33 J=1,M
               IF(J.EQ.L) GO TO 33
               OCOEF=FLOAT(ICOST(I,J,K,L))+FLOAT(ICOST(K,L,I,J))
               IC=IC+1
               IT=IC+M-1
               IF(J.LT.L)GO TO 31
CCCCCC J>L
               IJ=(I-2)*(M-1)+J-1
               ITA=ICA+M-1
               GO TO 32
CCCCCC J<L
   31          IJ=(I-2)*(M-1)+J
               ITA=ICA+M-2
   32          II=K
               JJ=L
               KK=I
               LL=J
               KLA=(KK-1)*M+LL
               IHOLD=IR-1
CCCCCC II<KK
               IF(JJ.LT.LL) GO TO 34
CCCCCC JJ>LL
               IJA=(II-1)*(M-1)+JJ-1
               GO TO 35
CCCCCC JJ<LL
   34          IJA=(II-1)*(M-1)+JJ
   35          WRITE(6,28)IJ,KL,OCOEF
   28 FORMAT(T5,'Y',I3.3,'A',I3.3,T15,'NOBJ',T25,F10.1)
               WRITE(6,29)IJ,KL,IHOLD,KL,AT
               WRITE(6,29)IJ,KL,IT,KL,AT
   29 FORMAT(T5,'Y',I3.3,'A',I3.3,T15,'C',I2.2,'A',I3.3,T25,F3.1)
               WRITE(6,30)IJ,KL,IRA,KLA,AT
               WRITE(6,30)IJ,KL,ITA,KLA,AT
   30 FORMAT(T5,'Y',I3.3,'A',I3.3,T15,'C',I2.2,'A',I3.3,T25,F3.1)
   33       CONTINUE
            GO TO 38
CCCCCC
   38     CONTINUE
   39 CONTINUE           
CCCCCC GIVE THE RIGHT HAND SIDES OF THE CONSTRAINTS
      WRITE(6,40)
   40 FORMAT(T1,'RHS')
      DO 42 I=1,MTWO
         WRITE(6,41) I,AT
   41 FORMAT(T5,'RHS',T15,'NX',I2.2,T25,F3.1)
   42 CONTINUE
      WRITE(6,43)
   43 FORMAT(T1,'ENDATA')               
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
c     temp=etime(time)
c     tstop=time(1)
C     tstop = mclock()/100.
C     dtime=tstop-tstart
C     write(6,*) 'Execution Time =', dtime
      STOP
      END
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
C     END OF MAIN PROGRAM
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
C     SUBROUTINES
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
C     THE PURPOSE OF THIS SUBROUTINE IS TO READ THE INPUT DATA WHICH
C     CONSISTS OF THE PROBLEM SIZE M AND A MATRIX (M,M) WITH THE
C     ORIGINAL DISTANCES IN THE UPPER HALF AND THE ORIGINAL FLOW IN THE
C     LOWER HALF.  THIS DATA IS THEN COMPILED TO FORM THE PAIRWISE
C     COST DATA STORED IN ICOST(M,M,M,M).
C     ICONST(M,M) STORES THE FIXED COSTS IF THERE ARE ANY.
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
C
      SUBROUTINE INPUT(M,MMONE,MMTWO)
      COMMON/ONE/IDIS(20,20),IFLOW(20,20)
      COMMON/TWO/IPAIR(20,20),ICOST(20,20,20,20),ICONST(20,20)
      DIMENSION IA(20,20)
C
      READ(5,*)M
      MMONE = M - 1
      MMTWO = M - 2
      DO 10 I = 1,M
         READ(5,*)(IA(I,J),J=1,M)
  10  CONTINUE
      DO 30 I =1,MMONE
         IDIS(I,I) = 0
         IPLUS1 = I + 1
         DO 20 J = IPLUS1,M
            IDIS(I,J) = IA(I,J)
            IDIS(J,I) = IA(I,J)
  20     CONTINUE
  30  CONTINUE
      IDIS(M,M) = 0
      DO 50 I = 2,M
         IFLOW(I,I) = 0
         IMINUS = I - 1
         DO 40 J = 1,IMINUS
            IFLOW(I,J) = IA(I,J)
            IFLOW(J,I) = IA(I,J)
  40     CONTINUE
  50  CONTINUE
      IFLOW(1,1) = 0
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
C     COMPUTE THE ORIGINAL COSTS
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
      DO 80 L = 1,M
      DO 80 K = 2,M
         KMIN1 = K - 1
         DO 70 J = 1,M
            IF ( J .EQ. L ) GO TO 70
               DO 60 I = 1,KMIN1
                  IT = IFLOW(I,K)*IDIS(J,L)
                  ICOST(I,J,K,L) = IT
                  ICOST(K,L,I,J) = IT
C                 NCOST(I,J,K,L) = ICOST(I,J,K,L)
C                 NCOST(K,L,I,J) = ICOST(K,L,I,J)
  60           CONTINUE
  70        CONTINUE
  80  CONTINUE
      DO 90 I = 1,M
      DO 90 J = 1,M
         ICONST(I,J) = 0
  90  CONTINUE
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
C     WRITE OUT THE ICOST MATRIX
C
C     DO 400 I = 1,M
C     DO 400 J = 1,M
C     WRITE(6,401)I,J
C401  FORMAT(1X,'I=',3X,I2,3X,'J=',3X,I2)
C     KT = I + 1
C     IF (KT .GT. M) GO TO 399
C     DO 435 K = KT,M
C     DO 398 L =1,M
C        IF (L .EQ. J) GO TO 397
C        WRITE(6,402) K,L,ICOST(I,J,K,L)
C 402 FORMAT(1X,'K=',3X,I2,3X,'L=',3X,I2,3X,'COST=',3X,I4)
C 397 CONTINUE
C 398 CONTINUE
C 435 CONTINUE
C 399 CONTINUE
C 400 CONTINUE
C     WRITE(6,404) M
C 404 FORMAT(1X,'M=',2X,I2)
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
      RETURN
      END
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC