module PseudoCosts

! ************************************************************************
! ************************************************************************

  integer :: numberOfVariables

  ! Up and down pseudo-costs of the variables.
  real(kind=8), allocatable :: upPseudoCosts(:)
  integer,      allocatable :: numComputedUpPseudoCosts(:)
  real(kind=8), allocatable :: downPseudoCosts(:)
  integer,      allocatable :: numComputedDownPseudoCosts(:)

  real(kind=8), allocatable :: lastUpPseudoCosts(:)
  real(kind=8), allocatable :: lastDownPseudoCosts(:)

! ************************************************************************
! ************************************************************************

contains

  subroutine initializePseudoCosts(n)

    implicit none

    ! Initialize pseudo-costs.

    ! SCALAR ARGUMENTS
    integer, intent(in) :: n

    allocate(upPseudoCosts(n))
    allocate(numComputedUpPseudoCosts(n))
    allocate(downPseudoCosts(n))
    allocate(numComputedDownPseudoCosts(n))

    allocate(lastUpPseudoCosts(n))
    allocate(lastDownPseudoCosts(n))

    numberOfVariables = n

    upPseudoCosts   = 0.0d0
    downPseudoCosts = 0.0d0

    numComputedUpPseudoCosts   = 0
    numComputedDownPseudoCosts = 0

  end subroutine initializePseudoCosts

! ************************************************************************
! ************************************************************************

  subroutine deallocatePseudoCosts()

    implicit none

    ! Deallocate pseudo-costs.

    deallocate(upPseudoCosts)
    deallocate(numComputedUpPseudoCosts)
    deallocate(downPseudoCosts)
    deallocate(numComputedDownPseudoCosts)

    deallocate(lastUpPseudoCosts)
    deallocate(lastDownPseudoCosts)

  end subroutine deallocatePseudoCosts

! ************************************************************************
! ************************************************************************

  logical function isPseudoCostsInitialized(index)

    implicit none

    ! SCALAR ARGUMENTS
    integer, intent(in) :: index

    if(numComputedUpPseudoCosts(index) .gt. 0 .and. &
         numComputedDownPseudoCosts(index) .gt. 0) then

       isPseudoCostsInitialized = .true.

    else

       isPseudoCostsInitialized = .false.

    end if

  end function isPseudoCostsInitialized

! ************************************************************************
! ************************************************************************

  logical function arePseudoCostsReliable(index,options_)

    use BranchAndBound_Options

    implicit none

    ! SCALAR ARGUMENTS
    integer, intent(in) :: index

    ! OTHER ARGUMENTS
    type(bb_options), intent(in) :: options_

    ! LOCAL SCALARS
    integer :: updatesBeforeTrust

    updatesBeforeTrust = getNumberOfUpdatesBeforeTrust(options_)

    if(updatesBeforeTrust .gt. 0 .and. &
       numComputedUpPseudoCosts(index) .ge. updatesBeforeTrust .and. &
       numComputedDownPseudoCosts(index) .ge. updatesBeforeTrust) then

       arePseudoCostsReliable = .true.

    else

       arePseudoCostsReliable = .false.

    end if

  end function arePseudoCostsReliable

! ************************************************************************
! ************************************************************************

  subroutine updatePseudoCost(index,value,downBranch,z,z_branch)

    implicit none

    ! SCALAR ARGUMENTS
    integer,      intent(in) :: index
    logical,      intent(in) :: downBranch
    real(kind=8), intent(in) :: value,z,z_branch

    ! Parameters of the subroutine:
    ! =============================
    !
    ! On Entry:
    ! =========
    !
    ! INDEX integer: Index of the variable whose pseudo-cost will be updated.
    ! -------------
    !
    ! VALUE real(kind=8): Value of the variable when the branch was performed.
    ! ------------------
    !
    ! DOWNBRANCH logical: Indicate whether the branch was made down or not.
    ! ------------------
    !
    ! Z real(kind=8): Value of the objective function at the solution
    ! --------------  of the problem before the branch.
    !
    ! Z_BRANCH real(kind=8): Value of the objective function at the solution
    ! ---------------------  of the problem after the branch.
    
    if(downBranch) then

       lastDownPseudoCosts(index) = abs(z_branch - z) / (value - real(floor(value), kind=8))
       
       downPseudoCosts(index) = downPseudoCosts(index) + lastDownPseudoCosts(index)

       numComputedDownPseudoCosts(index) = numComputedDownPseudoCosts(index) + 1

    else

       lastUpPseudoCosts(index) = abs(z_branch - z) / (real(ceiling(value), kind=8) - value)

       upPseudoCosts(index) = upPseudoCosts(index) + lastUpPseudoCosts(index)

       numComputedUpPseudoCosts(index) = numComputedUpPseudoCosts(index) + 1

    end if

  end subroutine updatePseudoCost

! ************************************************************************
! ************************************************************************

  function getUpPseudoCost(index,options_) result(upPseudoCost)

    use BranchAndBound_Options

    implicit none

    ! SCALAR ARGUMENTS
    integer, intent(in) :: index

    ! OTHER ARGUMENTS
    type(bb_options), intent(in) :: options_

    ! LOCAL SCARLARS
    integer :: numProblems

    ! RETURN VARIABLE
    real(kind=8) :: upPseudoCost

    if(numComputedUpPseudoCosts(index) .gt. 0) then

       if(arePseudoCostsReliable(index,options_)) then

          upPseudoCost = lastUpPseudoCosts(index)

       else

          upPseudoCost = upPseudoCosts(index) / &
               real(numComputedUpPseudoCosts(index), kind=8)

       end if

    else

       numProblems = sum(numComputedUpPseudoCosts)       

       if(numProblems .gt. 0) then

          upPseudoCost = sum(upPseudoCosts) / real(numProblems, kind=8)

       else

          upPseudoCost = 0.0d0

       end if

    end if

  end function getUpPseudoCost

! ************************************************************************
! ************************************************************************

  function getDownPseudoCost(index,options_) result(downPseudoCost)

    use BranchAndBound_Options

    implicit none

    ! SCALAR ARGUMENTS
    integer, intent(in) :: index

    ! OTHER ARGUMENTS
    type(bb_options), intent(in) :: options_

    ! LOCAL SCARLARS
    integer :: numProblems

    ! RETURN VARIABLE
    real(kind=8) :: downPseudoCost

    if(numComputedDownPseudoCosts(index) .gt. 0) then

      if(arePseudoCostsReliable(index,options_)) then

         downPseudoCost = lastDownPseudoCosts(index)

      else

          downPseudoCost = downPseudoCosts(index) / &
               real(numComputedDownPseudoCosts(index), kind=8)

      end if

    else

       numProblems = sum(numComputedDownPseudoCosts)       

       if(numProblems .gt. 0) then

          downPseudoCost = sum(downPseudoCosts) / real(numProblems, kind=8)

       else

          downPseudoCost = 0.0d0

       end if

    end if

  end function getDownPseudoCost

! ************************************************************************
! ************************************************************************

  function evaluatePseudoCost(index,value,options_) result(pseudoCost)

    use BranchAndBound_Options

    implicit none

    ! SCALAR ARGUMENTS
    integer,      intent(in) :: index
    real(kind=8), intent(in) :: value

    ! OTHER ARGUMENTS
    type(bb_options), intent(in) :: options_

    ! LOCAL SCALARS
    real(kind=8) :: alpha1,alpha2,alpha3
    real(kind=8) :: d_down,d_up,DD_down,DD_up
    real(kind=8) :: downPseudoCost,upPseudoCost

    ! RETURN VARIABLE
    real(kind=8) :: pseudoCost

    alpha1 = 0.0d0
    alpha2 = 1.0d0
    alpha3 = 0.0d0

    downPseudoCost = getDownPseudoCost(index,options_)
    upPseudoCost   = getUpPseudoCost(index,options_)

    d_up = real(ceiling(value), kind=8) - value

    d_down = value - real(floor(value), kind=8)
 
    DD_up = upPseudoCost * d_up

    DD_down = downPseudoCost * d_down

    pseudoCost = alpha1 * min(d_up,d_down) + alpha2 * min(DD_up,DD_down) + &
                 alpha3 * max(DD_up,DD_down)

  end function evaluatePseudoCost

! ************************************************************************
! ************************************************************************

end module PseudoCosts
