!  This file is an example of the Corana et al. simulated annealing algorithm
!  for multimodal and robust optimization as implemented and modified by
!  Goffe, Ferrier and Rogers.  Counting the above line
!  ABSTRACT as 1, the routine itself (SA), with its supplementary
!  routines, is on lines 232-990. A multimodal example from Judge et al.
!  (FCN) is on lines 150-231. The rest of this file (lines 1-149) is a
!  driver routine with values appropriate for the Judge example.  Thus, this
!  example is ready to run.

!  To understand the algorithm, the documentation for SA on lines 236-
!  484 should be read along with the parts of the paper that describe
!  simulated annealing. Then the following lines will then aid the user
!  in becomming proficient with this implementation of simulated annealing.

!  Learning to use SA:
!      Use the sample function from Judge with the following suggestions
!  to get a feel for how SA works. When you have done this, you should be
!  ready to use it on most any function with a fair amount of expertise.
!    1. Run the program as is to make sure it runs okay. Take a look at
!       the intermediate output and see how it optimizes as temperature
!       (T) falls.  Notice how the optimal point is reached and how
!       falling T reduces VM.
!    2. Look through the documentation to SA so the following makes a
!       bit of sense. In line with the paper, it should not be that hard
!       to figure out. The core of the algorithm is described on pp. 68-70
!       and on pp. 94-95. Also see Corana et al. pp. 264-9.
!    3. To see how it selects points and makes decisions about uphill and
!       downhill moves, set IPRINT = 3 (very detailed intermediate output)
!       and MAXEVL = 100 (only 100 function evaluations to limit output).
!    4. To see the importance of different temperatures, try starting
!       with a very low one (say T = 10E-5).  You will see (i) it never
!       escapes from the local optima (in annealing terminology, it
!       quenches) & (ii) the step length (VM) will be quite small.  This
!       is a key part of the algorithm: as temperature (T) falls, step
!       length does too. In a minor point here, note how VM is quickly
!       reset from its initial value. Thus, the input VM is not very
!       important.  This is all the more reason to examine VM once the
!       algorithm is underway.
!    5. To see the effect of different parameters and their effect on
!       the speed of the algorithm, try RT = .95 & RT = .1.  Notice the
!       vastly different speed for optimization. Also try NT = 20.  Note
!       that this sample function is quite easy to optimize, so it will
!       tolerate big changes in these parameters.  RT and NT are the
!       parameters one should adjust to modify the runtime of the
!       algorithm and its robustness.
!    6. Try constraining the algorithm with either LB or UB.


module simulated_anneal_sp

! ABSTRACT:
!   Simulated annealing is a global optimization method that distinguishes
!   between different local optima.  Starting from an initial point, the
!   algorithm takes a step and the function is evaluated. When minimizing a
!   function, any downhill step is accepted and the process repeats from this
!   new point. An uphill step may be accepted. Thus, it can escape from local
!   optima. This uphill decision is made by the Metropolis criteria. As the
!   optimization process proceeds, the length of the steps decline and the
!   algorithm closes in on the global optimum. Since the algorithm makes very
!   few assumptions regarding the function to be optimized, it is quite
!   robust with respect to non-quadratic surfaces. The degree of robustness
!   can be adjusted by the user. In fact, simulated annealing can be used as
!   a local optimizer for difficult functions.

!   This implementation of simulated annealing was used in "Global Optimizatio
!   of Statistical Functions with Simulated Annealing," Goffe, Ferrier and
!   Rogers, Journal of Econometrics, vol. 60, no. 1/2, Jan./Feb. 1994, pp.
!   65-100. Briefly, we found it competitive, if not superior, to multiple
!   restarts of conventional optimization routines for difficult optimization
!   problems.

!   For more information on this routine, contact its author:
!   Bill Goffe, bgoffe@whale.st.usm.edu

! This version in Fortran 90 has been prepared by Alan Miller.
! It is compatible with Lahey ELF90 compiler.
! N.B. The 3 last arguments have been removed from subroutine sa.   these
!      were work arrays and are now internal to the routine.
! e-mail:  amiller @ bigpond.net.au
! URL   :  http://users.bigpond.net.au/amiller

! Latest revision of Fortran 90 version - 3 August 1997

USE sep
use simann_general

IMPLICIT NONE

INTEGER, PARAMETER,private          :: dp = SELECTED_REAL_KIND(14, 60)
integer,public,save                 :: pwval
real, private, allocatable          :: scan(:,:,:,:),dso(:)

! The following variables were in COMMON /raset1/
REAL, SAVE    :: u(97), cc, cd, cm
INTEGER, SAVE :: i97, j97

CONTAINS
!==================================================================
subroutine sa(n, x, max, rt, eps, ns, nt, neps, maxevl, lb, ub, c, iprint,  &
              iseed1, iseed2, t, vm, xopt, fopt, nacc, nfcnev, nobds, ier)

!  Version: 3.2
!  Date: 1/22/94.
!  Differences compared to Version 2.0:
!     1. If a trial is out of bounds, a point is randomly selected
!        from LB(i) to UB(i). Unlike in version 2.0, this trial is
!        evaluated and is counted in acceptances and rejections.
!        All corresponding documentation was changed as well.
!  Differences compared to Version 3.0:
!     1. If VM(i) > (UB(i) - LB(i)), VM is set to UB(i) - LB(i).
!        The idea is that if T is high relative to LB & UB, most
!        points will be accepted, causing VM to rise. But, in this
!        situation, VM has little meaning; particularly if VM is
!        larger than the acceptable region. Setting VM to this size
!        still allows all parts of the allowable region to be selected.
!  Differences compared to Version 3.1:
!     1. Test made to see if the initial temperature is positive.
!     2. WRITE statements prettied up.
!     3. References to paper updated.

!  Synopsis:
!  This routine implements the continuous simulated annealing global
!  optimization algorithm described in Corana et al. article "Minimizing
!  Multimodal Functions of Continuous Variables with the Simulated Annealing
!  Algorithm" in the September 1987 (vol. 13, no. 3, pp. 262-280) issue of
!  the ACM Transactions on Mathematical Software.

!  A very quick (perhaps too quick) overview of SA:
!     SA tries to find the global optimum of an N dimensional function.
!  It moves both up and downhill and as the optimization process
!  proceeds, it focuses on the most promising area.
!     To start, it randomly chooses a trial point within the step length
!  VM (a vector of length N) of the user selected starting point. The
!  function is evaluated at this trial point and its value is compared
!  to its value at the initial point.
!     In a maximization problem, all uphill moves are accepted and the
!  algorithm continues from that trial point. Downhill moves may be
!  accepted; the decision is made by the Metropolis criteria. It uses T
!  (temperature) and the size of the downhill move in a probabilistic
!  manner. The smaller T and the size of the downhill move are, the more
!  likely that move will be accepted. If the trial is accepted, the
!  algorithm moves on from that point. If it is rejected, another point
!  is chosen instead for a trial evaluation.
!     Each element of VM periodically adjusted so that half of all
!  function evaluations in that direction are accepted.
!     A fall in T is imposed upon the system with the RT variable by
!  T(i+1) = RT*T(i) where i is the ith iteration. Thus, as T declines,
!  downhill moves are less likely to be accepted and the percentage of
!  rejections rise. Given the scheme for the selection for VM, VM falls.
!  Thus, as T declines, VM falls and SA focuses upon the most promising
!  area for optimization.

!  The importance of the parameter T:
!     The parameter T is crucial in using SA successfully. It influences
!  VM, the step length over which the algorithm searches for optima. For
!  a small intial T, the step length may be too small; thus not enough
!  of the function might be evaluated to find the global optima. The user
!  should carefully examine VM in the intermediate output (set IPRINT =
!  1) to make sure that VM is appropriate. The relationship between the
!  initial temperature and the resulting step length is function
!  dependent.
!     To determine the starting temperature that is consistent with
!  optimizing a function, it is worthwhile to run a trial run first. Set
!  RT = 1.5 and T = 1.0. With RT > 1.0, the temperature increases and VM
!  rises as well. Then select the T that produces a large enough VM.

!  For modifications to the algorithm and many details on its use,
!  (particularly for econometric applications) see Goffe, Ferrier
!  and Rogers, "Global Optimization of Statistical Functions with
!  Simulated Annealing," Journal of Econometrics, vol. 60, no. 1/2,
!  Jan./Feb. 1994, pp. 65-100.
!  For more information, contact
!              Bill Goffe
!              Department of Economics and International Business
!              University of Southern Mississippi
!              Hattiesburg, MS  39506-5072
!              (601) 266-4484 (office)
!              (601) 266-4920 (fax)
!              bgoffe@whale.st.usm.edu (Internet)

!  As far as possible, the parameters here have the same name as in
!  the description of the algorithm on pp. 266-8 of Corana et al.

!  In this description, SP is single precision, DP is double precision,
!  INT is integer, L is logical and (N) denotes an array of length n.
!  Thus, DP(N) denotes a double precision array of length n.

!  Input Parameters:
!    Note: The suggested values generally come from Corana et al. To
!          drastically reduce runtime, see Goffe et al., pp. 90-1 for
!          suggestions on choosing the appropriate RT and NT.
!    N - Number of variables in the function to be optimized. (INT)
!    X - The starting values for the variables of the function to be
!        optimized. (DP(N))
!    MAX - Denotes whether the function should be maximized or minimized.
!          A true value denotes maximization while a false value denotes
!          minimization.  Intermediate output (see IPRINT) takes this into
!          account. (L)
!    RT - The temperature reduction factor.  The value suggested by
!         Corana et al. is .85. See Goffe et al. for more advice. 
!    EPS - Error tolerance for termination. If the final function
!          values from the last neps temperatures differ from the
!          corresponding value at the current temperature by less than
!          EPS and the final function value at the current temperature
!          differs from the current optimal function value by less than
!          EPS, execution terminates and IER = 0 is returned. (EP)
!    NS - Number of cycles.  After NS*N function evaluations, each element of
!         VM is adjusted so that approximately half of all function evaluations
!         are accepted.  The suggested value is 20. (INT)
!    NT - Number of iterations before temperature reduction. After
!         NT*NS*N function evaluations, temperature (T) is changed
!         by the factor RT.  Value suggested by Corana et al. is
!         MAX(100, 5*N).  See Goffe et al. for further advice. (INT)
!    NEPS - Number of final function values used to decide upon termi-
!           nation.  See EPS.  Suggested value is 4. (INT)
!    MAXEVL - The maximum number of function evaluations.  If it is
!             exceeded, IER = 1. (INT)
!    LB - The lower bound for the allowable solution variables. (DP(N))
!    UB - The upper bound for the allowable solution variables. (DP(N))
!         If the algorithm chooses X(I) .LT. LB(I) or X(I) .GT. UB(I),
!         I = 1, N, a point is from inside is randomly selected. This
!         This focuses the algorithm on the region inside UB and LB.
!         Unless the user wishes to concentrate the search to a particular
!         region, UB and LB should be set to very large positive
!         and negative values, respectively.  Note that the starting
!         vector X should be inside this region.  Also note that LB and
!         UB are fixed in position, while VM is centered on the last
!         accepted trial set of variables that optimizes the function.
!    C - Vector that controls the step length adjustment.  The suggested
!        value for all elements is 2.0. (DP(N))
!    IPRINT - controls printing inside SA. (INT)
!             Values: 0 - Nothing printed.
!                     1 - Function value for the starting value and
!                         summary results before each temperature
!                         reduction. This includes the optimal
!                         function value found so far, the total
!                         number of moves (broken up into uphill,
!                         downhill, accepted and rejected), the
!                         number of out of bounds trials, the
!                         number of new optima found at this
!                         temperature, the current optimal X and
!                         the step length VM. Note that there are
!                         N*NS*NT function evalutations before each
!                         temperature reduction. Finally, notice is
!                         is also given upon achieveing the termination
!                         criteria.
!                     2 - Each new step length (VM), the current optimal
!                         X (XOPT) and the current trial X (X). This
!                         gives the user some idea about how far X
!                         strays from XOPT as well as how VM is adapting
!                         to the function.
!                     3 - Each function evaluation, its acceptance or
!                         rejection and new optima. For many problems,
!                         this option will likely require a small tree
!                         if hard copy is used. This option is best
!                         used to learn about the algorithm. A small
!                         value for MAXEVL is thus recommended when
!                         using IPRINT = 3.
!             Suggested value: 1
!             Note: For a given value of IPRINT, the lower valued
!                   options (other than 0) are utilized.
!    ISEED1 - The first seed for the random number generator RANMAR.
!             0 <= ISEED1 <= 31328. (INT)
!    ISEED2 - The second seed for the random number generator RANMAR.
!             0 <= ISEED2 <= 30081. Different values for ISEED1
!             and ISEED2 will lead to an entirely different sequence
!             of trial points and decisions on downhill moves (when
!             maximizing).  See Goffe et al. on how this can be used
!             to test the results of SA. (INT)

!  Input/Output Parameters:
!    T - On input, the initial temperature. See Goffe et al. for advice.
!        On output, the final temperature. 
!    VM - The step length vector. On input it should encompass the region of
!         interest given the starting value X.  For point X(I), the next
!         trial point is selected is from X(I) - VM(I)  to  X(I) + VM(I).
!         Since VM is adjusted so that about half of all points are accepted,
!         the input value is not very important (i.e. is the value is off,
!         SA adjusts VM to the correct value). (DP(N))

!  Output Parameters:
!    XOPT - The variables that optimize the function. (DP(N))
!    FOPT - The optimal value of the function. 
!    NACC - The number of accepted function evaluations. (INT)
!    NFCNEV - The total number of function evaluations. In a minor
!             point, note that the first evaluation is not used in the
!             core of the algorithm; it simply initializes the
!             algorithm. (INT).
!    NOBDS - The total number of trial function evaluations that
!            would have been out of bounds of LB and UB. Note that
!            a trial point is randomly selected between LB and UB. (INT)
!    IER - The error return number. (INT)
!          Values: 0 - Normal return; termination criteria achieved.
!                  1 - Number of function evaluations (NFCNEV) is
!                      greater than the maximum number (MAXEVL).
!                  2 - The starting value (X) is not inside the
!                      bounds (LB and UB).
!                  3 - The initial temperature is not positive.
!                  99 - Should not be seen; only used internally.

!  Work arrays that must be dimensioned in the calling routine:
!       RWK1 (DP(NEPS))  (FSTAR in SA)
!       RWK2 (DP(N))     (XP    "  " )
!       IWK  (INT(N))    (NACP  "  " )
!  N.B. In the Fortran 90 version, these are automatic arrays.

!  Required Functions (included):
!    EXPREP - Replaces the function EXP to avoid under- and overflows.
!             It may have to be modified for non IBM-type main-
!             frames. 
!    RMARIN - Initializes the random number generator RANMAR.
!    RANMAR - The actual random number generator. Note that
!             RMARIN must run first (SA does this). It produces uniform
!             random numbers on [0,1]. These routines are from
!             Usenet comp.lang.fortran. For a reference, see
!             "Toward a Universal Random Number Generator"
!             by George Marsaglia and Arif Zaman, Florida State
!             University Report: FSU-SCRI-87-50 (1987).
!             It was later modified by F. James and published in
!             "A Review of Pseudo-random Number Generators." For
!             further information, contact stuart@ads.com. These
!             routines are designed to be portable on any machine
!             with a 24-bit or more mantissa. I have found it produces
!             identical results on a IBM 3081 and a Cray Y-MP.

!  Required Subroutines (included):
!    PRTVEC - Prints vectors.
!    PRT1 ... PRT10 - Prints intermediate output.
!    OBJFCN - Function to be optimized. The form is
!            subroutine OBJFCN(N, X, F)
!            IMPLICIT NONE
!            INTEGER, PARAMETER     :: dp = SELECTED_REAL_KIND(14, 60)
!            INTEGER, INTENT(IN)    :: N
!            REAL , INTENT(IN)  :: X(N)
!            REAL , INTENT(OUT) :: F
!            ...
!            function code with F = F(X)
!            ...
!            RETURN
!            end
!  Note: This is the same form used in the multivariable
!        minimization algorithms in the IMSL edition 10 library.

!  Machine Specific Features:
!    1. EXPREP may have to be modified if used on non-IBM type main-
!       frames. Watch for under- and overflows in EXPREP.
!    2. Some FORMAT statements use G25.18; this may be excessive for
!       some machines.
!    3. RMARIN and RANMAR are designed to be protable; they should not
!       cause any problems.

!  Type all external variables.
REAL , INTENT(IN)     :: lb(:), ub(:), c(:), eps, rt
REAL , INTENT(IN OUT) :: x(:), t, vm(:)
REAL , INTENT(OUT)    :: xopt(:), fopt
INTEGER, INTENT(IN)       :: n, ns, nt, neps, maxevl, iprint, iseed1, iseed2
INTEGER, INTENT(OUT)      :: nacc, nfcnev, nobds, ier
LOGICAL, INTENT(IN)       :: max

!  Type all internal variables.
REAL  :: f, fp, p, pp, ratio, xp(n), fstar(neps),temp(ntot)
INTEGER   :: nup, ndown, nrej, nnew, lnobds, h, i, j, m, nacp(n),iii,i1,i2
LOGICAL   :: quit

!INTERFACE
!  subroutine objfcn(n, theta, h)
!    IMPLICIT NONE
!    INTEGER, PARAMETER     :: dp = SELECTED_REAL_KIND(14, 60)
!    INTEGER, INTENT(IN)    :: n
!    REAL , INTENT(IN)  :: theta(:)
!    REAL , INTENT(OUT) :: h
!  end subroutine objfcn
!end INTERFACE

!  Initialize the random number generator RANMAR.
call rmarin(iseed1, iseed2)

!  Set initial values.
nacc = 0
nobds = 0
nfcnev = 0
ier = 99

xopt = x
nacp = 0
fstar = 1.0D+20

!  If the initial temperature is not positive, notify the user and
!  return to the calling routine.
if (t <= 0.0) then
  WRITE(*,'(/, "  THE INITIAL TEMPERATURE IS not POSITIVE. "/,  &
        &    "  reset the variable t. "/)')
  ier = 3
  RETURN
end if

!  If the initial value is out of bounds, notify the user and return
!  to the calling routine.
do  i = 1, n
  if ((x(i) > ub(i)) .OR. (x(i) < lb(i))) then
    call prt1()
    ier = 2
    RETURN
  end if
end do 

!  Evaluate the function with input X and return value as F.
iii=1
call objfcn(x, f,iii)

!  If the function is to be minimized, switch the sign of the function.
!  Note that all intermediate and final output switches the sign back
!  to eliminate any possible confusion for the user.
if(.not. max) f = -f
nfcnev = nfcnev + 1
fopt = f
fstar(1) = f
if(iprint >= 1) call prt2(max, n, x, f)

!  Start the main loop. Note that it terminates if (i) the algorithm
!  succesfully optimizes the function or (ii) there are too many
!  function evaluations (more than MAXEVL).

if (rt.gt.1) open(unit=3,file="test.out")
100 nup = 0
    nrej = 0
    nnew = 0
    ndown = 0
    lnobds = 0

    do m = 1, nt
       do j = 1, ns
          do h = 1, n
      
!  Generate XP, the trial value of X. Note use of VM to choose XP.
             do i = 1, n
                if (i == h) then
                   xp(i) = x(i) + (ranmar()*2. - 1.) * 0.002!vm(i)
                else
                   xp(i) = x(i)
                end if

!  If XP is out of bounds, select a point in bounds for the trial.
                if((xp(i) < lb(i)) .OR. (xp(i) > ub(i))) then
                   xp(i) = lb(i) + (ub(i) - lb(i))*ranmar()
                   lnobds = lnobds + 1
                   nobds = nobds + 1
                   if(iprint >= 3) call prt3(max, n, xp, x, f)
                end if
             end do 
      
! smoother x
!             temp=xp
!             do i2=2,n2-1
!                do i1=2,n1-1
!                   xp((i2-1)*n2+i1)=(4*temp((i2-1)*n2+i1)+temp((i2-1)*n2+i1-1)+temp((i2-1)*n2+i1+1)+ &
!                                    temp((i2-2)*n2+i1)+temp((i2)*n2+i1))/8
!                end do
!             end do
!             write(0,*) minval(xp),maxval(xp)
!  Evaluate the function with the trial point XP and return as FP.

             iii=iii+1
             call objfcn(xp, fp, iii)
             if(.not. max) fp = -fp
             nfcnev = nfcnev + 1
             if(iprint >= 3) call prt4(max, n, xp, x, fp, f)
      
!  If too many function evaluations occur, terminate the algorithm.
             if(nfcnev >= maxevl) then
                call prt5()
                if (.not. max) fopt = -fopt
                ier = 1
                return
             end if
      
!  Accept the new point if the function value increases.
             if(fp >= f) then
                if(iprint >= 3) then
                   WRITE(*,'("  POINT ACCEPTED")')
                end if
                x(1:n) = xp(1:n)
                f = fp
                nacc = nacc + 1
                nacp(h) = nacp(h) + 1
                nup = nup + 1
        
!  If greater than any other point, record as new optimum.
                if (fp > fopt) then
                   if(iprint >= 3) then
                      WRITE(*,'("  NEW OPTIMUM")')
                   end if
                   xopt(1:n) = xp(1:n)
                   fopt = fp
                   nnew = nnew + 1
                end if
        
!  If the point is lower, use the Metropolis criteria to decide on
!  acceptance or rejection.
             else
                p = exprep((fp - f)/t)
                pp = ranmar()
                if (pp < p) then
                   if(iprint >= 3) call prt6(max)
                   x(1:n) = xp(1:n)
                   f = fp
                   nacc = nacc + 1
                   nacp(h) = nacp(h) + 1
                   ndown = ndown + 1
                else
                   nrej = nrej + 1
                   if(iprint >= 3) call prt7(max)
                end if
             end if
          end do 
       end do 
  
!  Adjust VM so that approximately half of all evaluations are accepted.
       do i = 1, n
          ratio = (nacp(i)) /(ns)
          if (ratio > .6) then
             vm(i) = vm(i)*(1. + c(i)*(ratio - .6)/.4)
          else if (ratio < .4) then
             vm(i) = vm(i)/(1. + c(i)*((.4 - ratio)/.4))
          end if
          if (vm(i) > (ub(i)-lb(i))) then
             vm(i) = ub(i) - lb(i)
          end if
       end do 
  
       if(iprint >= 2) then
          call prt8(n, vm, xopt, x)
       end if
       nacp(1:n) = 0
    end do 
    if(iprint >= 1) then
       call prt9(max,n,t,xopt,vm,fopt,nup,ndown,nrej,lnobds,nnew)
    end if

!  Check termination criteria.
    quit = .false.
    fstar(1) = f
    if ((fopt - fstar(1)) <= eps) quit = .true.
    do i = 1, neps
       if (ABS(f - fstar(i)) > eps) quit = .false.
    end do 

!  Terminate SA if appropriate.
    if (quit) then
      x(1:n) = xopt(1:n)
      ier = 0
      if (.not. max) fopt = -fopt
      if(iprint >= 1) call prt10()
      return
    end if

!  If termination criteria is not met, prepare for another loop.
    t = rt*t
    write(0,*) t
    do i = neps, 2, -1
       fstar(i) = fstar(i-1)
    end do 
    f = fopt
    x(1:n) = xopt(1:n)

!  Loop again.
GO TO 100
if (rt.gt.1) close(3)
end subroutine sa
!==================================================================
FUNCTION exprep(rdum) RESULT(fn_val)
!  This function replaces exp to avoid under- and overflows and is
!  designed for IBM 370 type machines. It may be necessary to modify
!  it for other machines. Note that the maximum and minimum values of
!  EXPREP are such that they has no effect on the algorithm.

REAL , INTENT(IN) :: rdum
REAL              :: fn_val

!if (rdum > 174.) then
if (rdum > 88.) then
  fn_val = huge(1.)
!ELSE if (rdum < -180.+dp) then
ELSE if (rdum < -87.+dp) then
  fn_val = 0.0
ELSE
  fn_val = EXP(rdum)
end if

RETURN
end FUNCTION exprep
!==================================================================
subroutine rmarin(ij, kl)
!  This subroutine and the next function generate random numbers. See
!  the comments for SA for more information. The only changes from the
!  orginal code is that (1) the test to make sure that RMARIN runs first
!  was taken out since SA assures that this is done (this test did not
!  compile under IBMs VS Fortran) and (2) typing ivec as integer was
!  taken out since ivec is not used. With these exceptions, all following
!  lines are original.

! This is the initialization routine for the random number generator
!     RANMAR()
! NOTE: The seed variables can have values between:    0 <= IJ <= 31328
!                                                      0 <= KL <= 30081

INTEGER, INTENT(IN) :: ij, kl

INTEGER :: i, j, k, l, ii, jj, m
REAL    :: s, t

if( ij < 0  .OR.  ij > 31328  .OR. kl < 0  .OR.  kl > 30081 ) then
  WRITE(*, '(A)') ' The first random number seed must have a value ',  &
               'between 0 AND 31328'
  WRITE(*, '(A)') ' The second seed must have a value between 0 and 30081'
  STOP
end if
i = MOD(ij/177, 177) + 2
j = MOD(ij    , 177) + 2
k = MOD(kl/169, 178) + 1
l = MOD(kl,     169)
do  ii = 1, 97
  s = 0.0
  t = 0.5
  do  jj = 1, 24
    m = MOD(MOD(i*j, 179)*k, 179)
    i = j
    j = k
    k = m
    l = MOD(53*l+1, 169)
    if (MOD(l*m, 64) >= 32) then
      s = s + t
    end if
    t = 0.5 * t
  end do 
  u(ii) = s
end do 
cc = 362436.0 / 16777216.0
cd = 7654321.0 / 16777216.0
cm = 16777213.0 /16777216.0
i97 = 97
j97 = 33
RETURN
end subroutine rmarin
!==================================================================
FUNCTION ranmar() RESULT(fn_val)
REAL :: fn_val

! Local variable
REAL :: uni

uni = u(i97) - u(j97)
if( uni < 0.0 ) uni = uni + 1.0
u(i97) = uni
i97 = i97 - 1
if(i97 == 0) i97 = 97
j97 = j97 - 1
if(j97 == 0) j97 = 97
cc = cc - cd
if( cc < 0.0 ) cc = cc + cm
uni = uni - cc
if( uni < 0.0 ) uni = uni + 1.0
fn_val = uni

RETURN
end FUNCTION ranmar
!==================================================================
subroutine prt1()
!  This subroutine prints intermediate output, as does PRT2 through
!  PRT10. Note that if SA is minimizing the function, the sign of the
!  function value and the directions (up/down) are reversed in all
!  output to correspond with the actual function optimization. This
!  correction is because SA was written to maximize functions and
!  it minimizes by maximizing the negative a function.

WRITE(*, '(/, "  THE STARTING VALUE (X) IS OUTSIDE THE BOUNDS "/,  &
      &     "  (lb AND ub). execution terminated without any"/,  &
      &     "  optimization. respecify x, ub OR lb so that  "/,  &
      &     "  lb(i) < x(i) < ub(i), i = 1, n. "/)')

RETURN
end subroutine prt1
!==================================================================
subroutine prt2(max, n, x, f)

REAL , INTENT(IN) ::  x(:), f
INTEGER, INTENT(IN)   ::  n
LOGICAL, INTENT(IN)   ::  max

WRITE(*, '("  ")')
!call prtvec(x,n,'INITIAL X')
if (max) then
  WRITE(*, '("  INITIAL F: ",/, G25.18)') f
ELSE
  WRITE(*, '("  INITIAL F: ",/, G25.18)') -f
end if

RETURN
end subroutine prt2
!==================================================================
subroutine prt3(max, n, xp, x, f)

REAL , INTENT(IN) ::  xp(:), x(:), f
INTEGER, INTENT(IN)   ::  n
LOGICAL, INTENT(IN)   ::  max

WRITE(*, '("  ")')
!call prtvec(x, n, 'CURRENT X')
if (max) then
  WRITE(*, '("  CURRENT F: ", G25.18)') f
ELSE
  WRITE(*, '("  CURRENT F: ", G25.18)') -f
end if
!call prtvec(xp, n, 'TRIAL X')
WRITE(*, '("  POINT REJECTED SINCE OUT OF BOUNDS")')

RETURN
end subroutine prt3
!==================================================================
subroutine prt4(max, n, xp, x, fp, f)

REAL , INTENT(IN) ::  xp(:), x(:), fp, f
INTEGER, INTENT(IN)   ::  n
LOGICAL, INTENT(IN)   ::  max

WRITE(*,'("  ")')
!call prtvec(x,n,'CURRENT X')
if (max) then
  WRITE(*,'("  CURRENT F: ",G25.18)') f
!  call prtvec(xp,n,'TRIAL X')
  WRITE(*,'("  RESULTING F: ",G25.18)') fp
ELSE
  WRITE(*,'("  CURRENT F: ",G25.18)') -f
!  call prtvec(xp,n,'TRIAL X')
  WRITE(*,'("  RESULTING F: ",G25.18)') -fp
end if

RETURN
end subroutine prt4
!==================================================================
subroutine prt5()

WRITE(*, '(/, "  TOO MANY FUNCTION EVALUATIONS; CONSIDER "/,  &
      &     "  increasing maxevl OR eps, OR decreasing "/,  &
      &     "  nt OR rt. these results are likely TO be "/, "  poor.",/)')

RETURN
end subroutine prt5
!==================================================================
subroutine prt6(max)
LOGICAL, INTENT(IN) ::  max

if (max) then
  WRITE(*,'("  THOUGH LOWER, POINT ACCEPTED")')
ELSE
  WRITE(*,'("  THOUGH HIGHER, POINT ACCEPTED")')
end if

RETURN
end subroutine prt6
!==================================================================
subroutine prt7(max)
LOGICAL, INTENT(IN) :: max

if (max) then
  WRITE(*,'("  LOWER POINT REJECTED")')
ELSE
  WRITE(*,'("  HIGHER POINT REJECTED")')
end if

RETURN
end subroutine prt7
!==================================================================
subroutine prt8(n, vm, xopt, x)

REAL , INTENT(IN) :: vm(:), xopt(:), x(:)
INTEGER, INTENT(IN)   :: n

WRITE(*,'(/, " intermediate results after step length adjustment", /)')
!call prtvec(vm, n, 'NEW STEP LENGTH (VM)')
!call prtvec(xopt, n, 'CURRENT OPTIMAL X')
!call prtvec(x, n, 'CURRENT X')
WRITE(*,'(" ")')

RETURN
end subroutine prt8
!==================================================================
subroutine prt9(max, n, t, xopt, vm, fopt, nup, ndown, nrej, lnobds, nnew)

REAL , INTENT(IN) :: xopt(:), vm(:), t, fopt
INTEGER, INTENT(IN)   :: n, nup, ndown, nrej, lnobds, nnew
LOGICAL, INTENT(IN)   :: max

! Local variable
INTEGER :: totmov

totmov = nup + ndown + nrej

WRITE(*,'(/," intermediate results before next temperature reduction",/)')
WRITE(*,'("  CURRENT TEMPERATURE:            ",G12.5)') t
if (max) then
  WRITE(*, '("  MAX FUNCTION VALUE SO FAR:  ",G25.18)') fopt
  WRITE(*, '("  TOTAL MOVES:                ",I8)') totmov
  WRITE(*, '("     UPHILL:                  ",I8)') nup
  WRITE(*, '("     ACCEPTED DOWNHILL:       ",I8)') ndown
  WRITE(*, '("     REJECTED DOWNHILL:       ",I8)') nrej
  WRITE(*, '("  OUT OF BOUNDS TRIALS:       ",I8)') lnobds
  WRITE(*, '("  NEW MAXIMA THIS TEMPERATURE:",I8)') nnew
ELSE
  WRITE(*, '("  MIN FUNCTION VALUE SO FAR:  ",G25.18)') -fopt
  WRITE(*, '("  TOTAL MOVES:                ",I8)') totmov
  WRITE(*, '("     DOWNHILL:                ",I8)')  nup
  WRITE(*, '("     ACCEPTED UPHILL:         ",I8)')  ndown
  WRITE(*, '("     REJECTED UPHILL:         ",I8)')  nrej
  WRITE(*, '("  TRIALS OUT OF BOUNDS:       ",I8)')  lnobds
  WRITE(*, '("  NEW MINIMA THIS TEMPERATURE:",I8)')  nnew
end if
!call prtvec(xopt, n, 'CURRENT OPTIMAL X')
!call prtvec(vm, n, 'STEP LENGTH (VM)')
WRITE(*, '(" ")')

RETURN
end subroutine prt9
!==================================================================
subroutine prt10()

WRITE(*, '(/, "  SA ACHIEVED TERMINATION CRITERIA. IER = 0. ",/)')

RETURN
end subroutine prt10
!==================================================================
subroutine prtvec(vector, ncols, name)
!  This subroutine prints the double precision vector named VECTOR.
!  Elements 1 thru NCOLS will be printed. NAME is a character variable
!  that describes VECTOR. Note that if NAME is given in the call to
!  PRTVEC, it must be enclosed in quotes. If there are more than 10
!  elements in VECTOR, 10 elements will be printed on each line.

INTEGER, INTENT(IN)           :: ncols
REAL , INTENT(IN)         :: vector(ncols)
CHARACTER (LEN=*), INTENT(IN) :: name

INTEGER :: i, lines, ll

WRITE(*,1001) NAME

if (ncols > 10) then
  lines = INT(ncols/10.)
  
  do  i = 1, lines
    ll = 10*(i - 1)
    WRITE(*,1000) vector(1+ll:10+ll)
  end do 
  
  WRITE(*,1000) vector(11+ll:ncols)
ELSE
  WRITE(*,1000) vector(1:ncols)
end if

1000 FORMAT( 10(g12.5, ' '))
1001 FORMAT(/, 25(' '), a)

RETURN
end subroutine prtvec
!==================================================================
subroutine objfcn(x, f, i, t, vm)
!
integer                :: i
real, optional         :: t, vm(:)
INTEGER, PARAMETER     :: dp = SELECTED_REAL_KIND(14, 60)
REAL , INTENT(IN)      :: x(:)
REAL , INTENT(OUT)     :: f
! Local variables
integer                :: i1,i3,i4
real                   :: rho
real, allocatable      :: xcan(:,:,:)

!if (i==100) allocate(xcan(ns1,ns2,ns3))
f = 0.
do i1=1,ns1;do i3=1,ns3
  rho=x((i3-1)*ns1+i1)
  i4=(rho-os4)/ds4+1.5
!  if (i==100) xcan(i1,:,i3)=scan(i1,:,i3,i4)*dso
  f = f + sum((scan(i1,:,i3,i4)*dso)**2)
end do;end do
write(2, '(i8,"  The obj.fcn: f = ",g25.8)') i,f 
!if (i==100) then
! call to_history("n1",ns1,"xscan");call to_history("d1",ds1,"xscan");call to_history("o1",os1,"xscan");
! call to_history("n2",ns2,"xscan");call to_history("d2",ds2,"xscan");call to_history("o2",os2,"xscan");
! call to_history("n3",ns3,"xscan");call to_history("d3",ds3,"xscan");call to_history("o3",os3,"xscan");
! call srite("xscan",xcan,4*ns1*ns2*ns3)
! deallocate(xcan)
!endif
RETURN
end subroutine objfcn
!==================================================================
subroutine kernel(x)
real     :: x(:),xcan(ns1,ns2,ns3),rho
integer  :: i1,i2,i3,i4
do i1=1,ns1;do i3=1,ns3
  rho=x((i3-1)*ns1+i1)
  i4=(rho-os4)/ds4+1.5
  xcan(i1,:,i3)=scan(i1,:,i3,i4)*dso
end do;end do
call to_history("n1",ns1,"xscan");call to_history("d1",ds1,"xscan");call to_history("o1",os1,"xscan");
call to_history("n2",ns2,"xscan");call to_history("d2",ds2,"xscan");call to_history("o2",os2,"xscan");
call to_history("n3",ns3,"xscan");call to_history("d3",ds3,"xscan");call to_history("o3",os3,"xscan");
call srite("xscan",xcan,4*ns1*ns2*ns3)
end subroutine 
!==================================================================
subroutine sa_init()
  integer  :: i
  allocate(scan(ns1,ns2,ns3,ns4),dso(ns2))
  call sreed("scan",scan,4*ns1*ns2*ns3*ns4)
  do i=1,ns2
     dso(i)=(i-1)*ds2+os2
  end do
  dso=abs(dso)
end subroutine
!==================================================================
subroutine sa_close()
  deallocate(scan,dso)
end subroutine
!==================================================================
end module simulated_anneal_sp
