history.h

Go to the documentation of this file.

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/*                                                                           */
/*                  This file is part of the program and library             */
/*         SCIP --- Solving Constraint Integer Programs                      */
/*                                                                           */
/*  Copyright (c) 2002-2024 Zuse Institute Berlin (ZIB)                      */
/*                                                                           */
/*  Licensed under the Apache License, Version 2.0 (the "License");          */
/*  you may not use this file except in compliance with the License.         */
/*  You may obtain a copy of the License at                                  */
/*                                                                           */
/*      http://www.apache.org/licenses/LICENSE-2.0                           */
/*                                                                           */
/*  Unless required by applicable law or agreed to in writing, software      */
/*  distributed under the License is distributed on an "AS IS" BASIS,        */
/*  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
/*  See the License for the specific language governing permissions and      */
/*  limitations under the License.                                           */
/*                                                                           */
/*  You should have received a copy of the Apache-2.0 license                */
/*  along with SCIP; see the file LICENSE. If not visit scipopt.org.         */
/*                                                                           */
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

/**@file   history.h
 * @ingroup INTERNALAPI
 * @brief  internal methods for branching and inference history
 * @author Tobias Achterberg
 * @author Timo Berthold
 */

/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/

#ifndef __SCIP_HISTORY_H__
#define __SCIP_HISTORY_H__


#include "scip/def.h"
#include "blockmemshell/memory.h"
#include "scip/type_retcode.h"
#include "scip/type_set.h"
#include "scip/type_history.h"

#ifdef NDEBUG
#include "scip/struct_history.h"
#endif

#ifdef __cplusplus
extern "C" {
#endif

/** creates an empty history entry */
SCIP_RETCODE SCIPhistoryCreate(
   SCIP_HISTORY**        history,            /**< pointer to store branching and inference history */
   BMS_BLKMEM*           blkmem              /**< block memory */
   );

/** frees a history entry */
void SCIPhistoryFree(
   SCIP_HISTORY**        history,            /**< pointer to branching and inference history */
   BMS_BLKMEM*           blkmem              /**< block memory */
   );

/** resets history entry to zero */
void SCIPhistoryReset(
   SCIP_HISTORY*         history             /**< branching and inference history */
   );

/** unites two history entries by adding the values of the second one to the first one */
void SCIPhistoryUnite(
   SCIP_HISTORY*         history,            /**< branching and inference history */
   SCIP_HISTORY*         addhistory,         /**< history values to add to history */
   SCIP_Bool             switcheddirs        /**< should the history entries be united with switched directories */
   );

/** updates the pseudo costs for a change of "solvaldelta" in the variable's LP solution value and a change of "objdelta"
 *  in the LP's objective value
 */
void SCIPhistoryUpdatePseudocost(
   SCIP_HISTORY*         history,            /**< branching and inference history */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_Real             solvaldelta,        /**< difference of variable's new LP value - old LP value */
   SCIP_Real             objdelta,           /**< difference of new LP's objective value - old LP's objective value */
   SCIP_Real             weight              /**< weight of this update in pseudo cost sum (added to pscostcount) */
   );


/**@defgroup ValueHistory Value Based History
 * @ingroup INTERNALAPI
 * @brief Value based history methods
 *
 * @{
 */

/** creates an empty value history */
SCIP_RETCODE SCIPvaluehistoryCreate(
   SCIP_VALUEHISTORY**   valuehistory,       /**< pointer to store the value based branching and inference histories */
   BMS_BLKMEM*           blkmem              /**< block memory */
   );

/** frees a value history */
void SCIPvaluehistoryFree(
   SCIP_VALUEHISTORY**   valuehistory,       /**< pointer to value based history */
   BMS_BLKMEM*           blkmem              /**< block memory */
   );

/** finds for the given domain value the history if it does not exist yet it will be created */
SCIP_RETCODE SCIPvaluehistoryFind(
   SCIP_VALUEHISTORY*    valuehistory,       /**< value based history */
   BMS_BLKMEM*           blkmem,             /**< block memory */
   SCIP_SET*             set,                /**< global SCIP settings */
   SCIP_Real             value,              /**< domain value of interest */
   SCIP_HISTORY**        history             /**< pointer to store the history for the given domain value */
   );

/** scales the conflict score values with the given scalar for each value history entry */
void SCIPvaluehistoryScaleVSIDS(
   SCIP_VALUEHISTORY*    valuehistory,       /**< value based history */
   SCIP_Real             scalar              /**< scalar to multiply the conflict scores with */
   );

/**@} */

/** returns the opposite direction of the given branching direction */
SCIP_BRANCHDIR SCIPbranchdirOpposite(
   SCIP_BRANCHDIR        dir                 /**< branching direction */
   );

/** returns the expected dual gain for moving the corresponding variable by "solvaldelta" */
SCIP_Real SCIPhistoryGetPseudocost(
   SCIP_HISTORY*         history,            /**< branching and inference history */
   SCIP_Real             solvaldelta         /**< difference of variable's new LP value - old LP value */
   );

/** returns the variance of pseudo costs about the mean. */
SCIP_Real SCIPhistoryGetPseudocostVariance(
   SCIP_HISTORY*         history,            /**< branching and inference history */
   SCIP_BRANCHDIR        direction           /**< direction of variable: 1 for upwards history, 0 for downwards history */
   );

/** returns the (possible fractional) number of (partial) pseudo cost updates performed on this pseudo cost entry in 
 *  the given branching direction
 */
SCIP_Real SCIPhistoryGetPseudocostCount(
   SCIP_HISTORY*         history,            /**< branching and inference history */
   SCIP_BRANCHDIR        dir                 /**< branching direction (downwards, or upwards) */
   );

/** returns whether the pseudo cost entry is empty in the given branching direction (whether no value was added yet) */
SCIP_Bool SCIPhistoryIsPseudocostEmpty(
   SCIP_HISTORY*         history,            /**< branching and inference history */
   SCIP_BRANCHDIR        dir                 /**< branching direction (downwards, or upwards) */
   );

/** increases the conflict score of the history entry by the given weight */
void SCIPhistoryIncVSIDS(
   SCIP_HISTORY*         history,            /**< branching and inference history */
   SCIP_BRANCHDIR        dir,                /**< branching direction */
   SCIP_Real             weight              /**< weight of this update in conflict score */
   );

 /** scales the conflict score values with the given scalar */
void SCIPhistoryScaleVSIDS(
   SCIP_HISTORY*         history,            /**< branching and inference history */
   SCIP_Real             scalar              /**< scalar to multiply the conflict scores with */
   );

/** increases the number of active conflicts by one and the overall length of the history entry by the given weight */
void SCIPhistoryIncNActiveConflicts(
   SCIP_HISTORY*         history,            /**< branching and inference history */
   SCIP_BRANCHDIR        dir,                /**< branching direction */
   SCIP_Real             length              /**< length of the conflict */
   );

/** gets the number of active conflicts of the history entry */
SCIP_Longint SCIPhistoryGetNActiveConflicts(
   SCIP_HISTORY*         history,            /**< branching and inference history */
   SCIP_BRANCHDIR        dir                 /**< branching direction */
   );

/** increases the number of branchings counter */
void SCIPhistoryIncNBranchings(
   SCIP_HISTORY*         history,            /**< branching and inference history */
   SCIP_BRANCHDIR        dir,                /**< branching direction (downwards, or upwards) */
   int                   depth               /**< depth at which the bound change took place */
   );

/** increases the number of inferences counter */
void SCIPhistoryIncInferenceSum(
   SCIP_HISTORY*         history,            /**< branching and inference history */
   SCIP_BRANCHDIR        dir,                /**< branching direction (downwards, or upwards) */
   SCIP_Real             weight              /**< weight of this update in cutoff score */
   );


/** increases the number of cutoffs counter */
void SCIPhistoryIncCutoffSum(
   SCIP_HISTORY*         history,            /**< branching and inference history */
   SCIP_BRANCHDIR        dir,                /**< branching direction (downwards, or upwards) */
   SCIP_Real             weight              /**< weight of this update in cutoff score */
   );

/** get number of branchings counter */
SCIP_Longint SCIPhistoryGetNBranchings(
   SCIP_HISTORY*         history,            /**< branching and inference history */
   SCIP_BRANCHDIR        dir                 /**< branching direction (downwards, or upwards) */
   );

/** returns the average number of inferences per branching */
SCIP_Real SCIPhistoryGetAvgInferences(
   SCIP_HISTORY*         history,            /**< branching and inference history */
   SCIP_BRANCHDIR        dir                 /**< branching direction (downwards, or upwards) */
   );

/** returns the average number of cutoffs per branching */
SCIP_Real SCIPhistoryGetAvgCutoffs(
   SCIP_HISTORY*         history,            /**< branching and inference history */
   SCIP_BRANCHDIR        dir                 /**< branching direction (downwards, or upwards) */
   );

/** returns the average depth of bound changes due to branching */
SCIP_Real SCIPhistoryGetAvgBranchdepth(
   SCIP_HISTORY*         history,            /**< branching and inference history */
   SCIP_BRANCHDIR        dir                 /**< branching direction (downwards, or upwards) */
   );

/** returns true if the given history contains a valid ratio */
SCIP_Bool SCIPhistoryIsRatioValid(
   SCIP_HISTORY*         history             /**< branching and inference history */
   );

/** returns the most recent ratio computed given the variable history */
SCIP_Real SCIPhistoryGetLastRatio(
   SCIP_HISTORY*         history             /**< branching and inference history */
   );

/** returns the most recent value of r/l used to compute this variable's ratio */
SCIP_Real SCIPhistoryGetLastBalance(
   SCIP_HISTORY*         history             /**< branching and inference history */
   );

/** returns the average efficacy value for the GMI cut produced by this variable */
SCIP_Real SCIPhistoryGetAvgGMIeff(
   SCIP_HISTORY*         history             /**< branching and inference history */
   );

/** increases the average efficacy value for the GMI cut produced by this variable */
void SCIPhistoryIncGMIeffSum(
   SCIP_HISTORY*         history,            /**< branching and inference history */
   SCIP_Real             gmieff              /**< normalized efficacy value of a cut which will increase gmieff */
   );

/** returns the most recent efficacy value for the GMI cut produced by this variable */
SCIP_Real SCIPhistoryGetLastGMIeff(
   SCIP_HISTORY*         history             /**< branching and inference history */
   );

/** sets the new most recent efficacy value for the GMI cut produced by this variable */
void SCIPhistorySetLastGMIeff(
   SCIP_HISTORY*         history,            /**< branching and inference history */
   SCIP_Real             gmieff              /**< Efficacy of GMI cut produced from simplex tableau row of this var */
   );

/** sets the ratio history for a particular variable */
void SCIPhistorySetRatioHistory(
   SCIP_HISTORY*         history,            /**< branching and inference history */
   SCIP_Bool             valid,              /**< True iff the ratio computed is valid */
   SCIP_Real             ratio,              /**< Ratio of the characteristic polynomial with gains (1, rightgain/leftgain) */
   SCIP_Real             balance             /**< The value of rightgain/leftgain */
   );

#ifdef NDEBUG

/* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
 * speed up the algorithms.
 */

#define SCIPbranchdirOpposite(dir)                                      \
   ((dir) == SCIP_BRANCHDIR_DOWNWARDS ? SCIP_BRANCHDIR_UPWARDS          \
      : ((dir) == SCIP_BRANCHDIR_UPWARDS ? SCIP_BRANCHDIR_DOWNWARDS : SCIP_BRANCHDIR_AUTO))
#define SCIPhistoryGetPseudocost(history,solvaldelta)                   \
   ( (solvaldelta) >= 0.0 ? (solvaldelta) * ((history)->pscostcount[1] > 0.0 \
      ? (history)->pscostweightedmean[1] : 1.0)      \
      : -(solvaldelta) * ((history)->pscostcount[0] > 0.0               \
         ? (history)->pscostweightedmean[0] : 1.0) )
#define SCIPhistoryGetPseudocostVariance(history, dir)                  \
   ( (history)->pscostcount[dir] >= 1.9 ? 1 / ((history)->pscostcount[dir] - 1)  \
         * ((history)->pscostvariance[dir]) \
         : 0.0)
#define SCIPhistoryGetPseudocostCount(history,dir) ((history)->pscostcount[dir])
#define SCIPhistoryIsPseudocostEmpty(history,dir)  ((history)->pscostcount[dir] == 0.0)
#define SCIPhistoryIncVSIDS(history,dir,weight) (history)->vsids[dir] += (weight)
#define SCIPhistoryScaleVSIDS(history,scalar)  { (history)->vsids[0] *= (scalar); \
      (history)->vsids[1] *= (scalar);  }
#define SCIPhistoryIncNActiveConflicts(history,dir,length) { (history)->nactiveconflicts[dir]++; \
      (history)->conflengthsum[dir] += length; }
#define SCIPhistoryGetNActiveConflicts(history,dir) ((history)->nactiveconflicts[dir])
#define SCIPhistoryIncNBranchings(history,dir,depth) { (history)->nbranchings[dir]++; \
      (history)->branchdepthsum[dir] += depth; }
#define SCIPhistoryIncInferenceSum(history,dir,weight)     (history)->inferencesum[dir] += (weight)
#define SCIPhistoryIncCutoffSum(history,dir,weight)        (history)->cutoffsum[dir] += (weight)
#define SCIPhistoryGetNBranchings(history,dir)     ((history)->nbranchings[dir])
#define SCIPhistoryGetAvgInferences(history,dir)   ((history)->nbranchings[dir] > 0 \
      ? (SCIP_Real)(history)->inferencesum[dir]/(SCIP_Real)(history)->nbranchings[dir] : 0.0)
#define SCIPhistoryGetAvgCutoffs(history,dir)      ((history)->nbranchings[dir] > 0 \
      ? (SCIP_Real)(history)->cutoffsum[dir]/(SCIP_Real)(history)->nbranchings[dir] : 0.0)
#define SCIPhistoryGetAvgBranchdepth(history,dir)  ((history)->nbranchings[dir] > 0 \
      ? (SCIP_Real)(history)->branchdepthsum[dir]/(SCIP_Real)(history)->nbranchings[dir] : 1.0)
#define SCIPhistoryIsRatioValid(history) ((history)->ratiovalid)
#define SCIPhistoryGetLastRatio(history) ((history)->ratio)
#define SCIPhistorySetRatioHistory(history,newvalid,newratio,newbalance) (history)->ratiovalid = newvalid, \
    (history)->ratio = newratio, (history)->balance = newbalance
#define SCIPhistoryGetLastBalance(history) ((history)->balance)
#define SCIPhistoryGetLastGMIeff(history) ((history)->gmieff)
#define SCIPhistorySetLastGMIeff(history,newgmieff) (history)->gmieff = newgmieff
#define SCIPhistoryGetAvgGMIeff(history) ((history)->ngmi > 0 \
      ? (SCIP_Real)(history)->gmieffsum/(SCIP_Real)(history)->ngmi : 0.0)
#define SCIPhistoryIncGMIeffSum(history, newgmieff) { (history)->gmieffsum += newgmieff; \
      (history)->ngmi += 1; }

#endif

#ifdef __cplusplus
}
#endif

#endif