event_solvingphase.c File Reference

Detailed Description

event handler for solving phase dependent parameter adjustment

Author

Gregor Hendel

this event handler provides methods to support parameter adjustment at every new of the three solving phases:

• Feasibility phase - before the first solution is found
• Improvement phase - after the first solution was found until an optimal solution is found or believed to be found
• Proof phase - the remaining time of the solution process after an optimal or believed-to-be optimal incumbent has been found.

Of course, this event handler cannot detect by itself whether a given incumbent is optimal prior to termination of the solution process. It rather uses heuristic transitions based on properties of the search tree in order to determine the appropriate stage. Settings files can be passed to this event handler for each of the three phases.

This approach of phase-based parameter adjustment was first presented in

Gregor Hendel Empirical Analysis of Solving Phases in Mixed-Integer Programming Master thesis, Technical University Berlin (2014)

with the main results also available from

Gregor Hendel Exploiting solving phases in mixed-integer programs (2015)

Definition in file event_solvingphase.c.

#include "scip/event_solvingphase.h"
#include "scip/pub_disp.h"
#include "scip/pub_event.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_misc_sort.h"
#include "scip/pub_paramset.h"
#include "scip/pub_tree.h"
#include "scip/scip_disp.h"
#include "scip/scip_event.h"
#include "scip/scip_general.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_sol.h"
#include "scip/scip_solve.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_timing.h"
#include "scip/scip_tree.h"
#include <string.h>

Go to the source code of this file.

Data Structures
struct	DepthInfo

Macros
#define	EVENTHDLR_NAME   "solvingphase"
#define	EVENTHDLR_DESC   "event handler to adjust settings depending on current stage"
#define	EVENTHDLR_EVENT   SCIP_EVENTTYPE_BESTSOLFOUND | SCIP_EVENTTYPE_NODEBRANCHED | SCIP_EVENTTYPE_NODEFOCUSED
#define	TRANSITIONMETHODS   "elor"
#define	DEFAULT_SETNAME   "-"
#define	DEFAULT_TRANSITIONMETHOD   'r'
#define	DEFAULT_NODEOFFSET   50L
#define	DEFAULT_FALLBACK   FALSE
#define	DEFAULT_INTERRUPTOPTIMAL   FALSE
#define	DEFAULT_ENABLED   FALSE
#define	DEFAULT_TESTMODE   FALSE
#define	DEFAULT_USERESTART1TO2   FALSE
#define	DEFAULT_USERESTART2TO3   FALSE
#define	DEFAULT_USEEMPHSETTINGS   TRUE
#define	DEFAULT_LOGREGRESSION_XTYPE   'n'
#define	LOGREGRESSION_XTYPES   "lnt"
#define	eventCopySolvingphase   NULL
#define	DISP_NAME_NRANK1NODES   "nrank1nodes"
#define	DISP_DESC_NRANK1NODES   "current number of rank1 nodes left"
#define	DISP_HEAD_NRANK1NODES   "rank1"
#define	DISP_WIDT_NRANK1NODES   7
#define	DISP_PRIO_NRANK1NODES   40000
#define	DISP_POSI_NRANK1NODES   500
#define	DISP_STRI_NRANK1NODES   TRUE
#define	DISP_NAME_NNODESBELOWINC   "nnodesbelowinc"
#define	DISP_DESC_NNODESBELOWINC   "current number of nodes with an estimate better than the current incumbent"
#define	DISP_HEAD_NNODESBELOWINC   "nbInc"
#define	DISP_WIDT_NNODESBELOWINC   6
#define	DISP_PRIO_NNODESBELOWINC   40000
#define	DISP_POSI_NNODESBELOWINC   550
#define	DISP_STRI_NNODESBELOWINC   TRUE

Typedefs
typedef enum SolvingPhase	SOLVINGPHASE
typedef struct DepthInfo	DEPTHINFO

Enumerations
enum	SolvingPhase {   SOLVINGPHASE_UNINITIALIZED = -1,   SOLVINGPHASE_FEASIBILITY = 0,   SOLVINGPHASE_IMPROVEMENT = 1,   SOLVINGPHASE_PROOF = 2 }

Functions
static	SCIP_DECL_SORTPTRCOMP (sortCompTreeinfo)
static SCIP_RETCODE	addNodesInformation (SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata, SCIP_NODE **nodes, int nnodes)
static void	removeNode (SCIP_NODE *node, SCIP_EVENTHDLRDATA *eventhdlrdata)
static int	getNRank1Nodes (SCIP *scip)
static int	getNNodesBelowIncumbent (SCIP *scip)
static SCIP_RETCODE	recomputeNodeInformation (SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata)
static SCIP_RETCODE	createDepthinfo (SCIP *scip, DEPTHINFO **depthinfo)
static SCIP_RETCODE	freeDepthinfo (SCIP *scip, DEPTHINFO **depthinfo)
static void	releaseNodeFromDepthInfo (SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata, SCIP_NODE *node)
static SCIP_RETCODE	ensureDepthInfoArraySize (SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata, SCIP_NODE *node)
static SCIP_RETCODE	releaseNodeInformation (SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata, SCIP_NODE *node)
static int	checkLeavesBelowIncumbent (SCIP *scip)
static SCIP_Real	getX (SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata)
static SCIP_Real	getCurrentRegressionTangentAxisIntercept (SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata)
static SCIP_Bool	checkRankOneTransition (SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata)
static SCIP_Bool	checkEstimateCriterion (SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata)
static SCIP_Bool	checkLogCriterion (SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata)
static SCIP_Bool	checkOptimalSolution (SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata)
static SCIP_Bool	transitionPhase3 (SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata)
static void	determineSolvingPhase (SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata)
static SCIP_RETCODE	changeEmphasisParameters (SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata)
static SCIP_RETCODE	changeParametersUsingSettingsFiles (SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata)
static SCIP_RETCODE	fixOrUnfixRelevantParameters (SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata, SCIP_Bool fix)
static SCIP_RETCODE	adaptSolverBehavior (SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata)
static SCIP_RETCODE	applySolvingPhase (SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata)
static SCIP_RETCODE	updateLogRegression (SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata)
static SCIP_RETCODE	updateDataStructures (SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata, SCIP_EVENTTYPE eventtype)
static void	testCriteria (SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata)
static	SCIP_DECL_EVENTFREE (eventFreeSolvingphase)
static	SCIP_DECL_EVENTINITSOL (eventInitsolSolvingphase)
static	SCIP_DECL_EVENTEXITSOL (eventExitsolSolvingphase)
static SCIP_RETCODE	collectNondefaultParams (SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata)
static	SCIP_DECL_EVENTINIT (eventInitSolvingphase)
static	SCIP_DECL_EVENTEXIT (eventExitSolvingphase)
static	SCIP_DECL_EVENTEXEC (eventExecSolvingphase)
static	SCIP_DECL_DISPOUTPUT (dispOutputNRank1Nodes)
static	SCIP_DECL_DISPOUTPUT (dispOutputNnodesbelowinc)
SCIP_RETCODE	SCIPincludeEventHdlrSolvingphase (SCIP *scip)

Macro Definition Documentation

EVENTHDLR_NAME

#define EVENTHDLR_NAME   "solvingphase"

Definition at line 75 of file event_solvingphase.c.

Referenced by getNNodesBelowIncumbent(), getNRank1Nodes(), SCIP_DECL_EVENTEXIT(), SCIP_DECL_EVENTFREE(), SCIP_DECL_EVENTINIT(), SCIPincludeEventHdlrSolvingphase(), and testCriteria().

EVENTHDLR_DESC

#define EVENTHDLR_DESC   "event handler to adjust settings depending on current stage"

Definition at line 76 of file event_solvingphase.c.

Referenced by SCIPincludeEventHdlrSolvingphase().

EVENTHDLR_EVENT

#define EVENTHDLR_EVENT   SCIP_EVENTTYPE_BESTSOLFOUND | SCIP_EVENTTYPE_NODEBRANCHED | SCIP_EVENTTYPE_NODEFOCUSED

the actual event to be caught

Definition at line 78 of file event_solvingphase.c.

Referenced by SCIP_DECL_EVENTEXEC(), and SCIP_DECL_EVENTINIT().

TRANSITIONMETHODS

#define TRANSITIONMETHODS   "elor"

which heuristic transition method: (e)stimate based, (l)ogarithmic regression based, (o)ptimal value based (cheat!), (r)ank-1 node based?

Definition at line 79 of file event_solvingphase.c.

Referenced by SCIPincludeEventHdlrSolvingphase().

DEFAULT_SETNAME

#define DEFAULT_SETNAME   "-"

default settings file name for solving phase setting files

Definition at line 82 of file event_solvingphase.c.

Referenced by changeParametersUsingSettingsFiles(), and SCIPincludeEventHdlrSolvingphase().

DEFAULT_TRANSITIONMETHOD

#define DEFAULT_TRANSITIONMETHOD   'r'

the default transition method

Definition at line 83 of file event_solvingphase.c.

Referenced by SCIPincludeEventHdlrSolvingphase().

DEFAULT_NODEOFFSET

#define DEFAULT_NODEOFFSET   50L

default node offset before transition to proof phase is active

Definition at line 84 of file event_solvingphase.c.

Referenced by SCIPincludeEventHdlrSolvingphase().

DEFAULT_FALLBACK

#define DEFAULT_FALLBACK   FALSE

should the phase transition fall back to suboptimal phase?

Definition at line 85 of file event_solvingphase.c.

Referenced by SCIPincludeEventHdlrSolvingphase().

DEFAULT_INTERRUPTOPTIMAL

#define DEFAULT_INTERRUPTOPTIMAL   FALSE

should solving process be interrupted if optimal solution was found?

Definition at line 86 of file event_solvingphase.c.

Referenced by SCIPincludeEventHdlrSolvingphase().

DEFAULT_ENABLED

#define DEFAULT_ENABLED   FALSE

should the event handler be executed?

Definition at line 88 of file event_solvingphase.c.

Referenced by SCIPincludeEventHdlrSolvingphase().

DEFAULT_TESTMODE

#define DEFAULT_TESTMODE   FALSE

should the event handler test the criteria?

Definition at line 89 of file event_solvingphase.c.

Referenced by SCIPincludeEventHdlrSolvingphase().

DEFAULT_USERESTART1TO2

#define DEFAULT_USERESTART1TO2   FALSE

should a restart be applied between the feasibility and improvement phase?

Definition at line 91 of file event_solvingphase.c.

Referenced by SCIPincludeEventHdlrSolvingphase().

DEFAULT_USERESTART2TO3

#define DEFAULT_USERESTART2TO3   FALSE

should a restart be applied between the improvement and the proof phase?

Definition at line 92 of file event_solvingphase.c.

Referenced by SCIPincludeEventHdlrSolvingphase().

DEFAULT_USEEMPHSETTINGS

#define DEFAULT_USEEMPHSETTINGS   TRUE

should emphasis settings be used for the different solving phases, or settings files?

Definition at line 93 of file event_solvingphase.c.

Referenced by SCIPincludeEventHdlrSolvingphase().

DEFAULT_LOGREGRESSION_XTYPE

#define DEFAULT_LOGREGRESSION_XTYPE   'n'

default type to use for log regression - (t)ime, (n)odes, (l)p iterations

Definition at line 96 of file event_solvingphase.c.

Referenced by SCIPincludeEventHdlrSolvingphase().

LOGREGRESSION_XTYPES

#define LOGREGRESSION_XTYPES   "lnt"

available types for log regression - (t)ime, (n)odes, (l)p iterations

Definition at line 97 of file event_solvingphase.c.

Referenced by SCIPincludeEventHdlrSolvingphase().

eventCopySolvingphase

#define eventCopySolvingphase   NULL

copy method for event handler (called when SCIP copies plugins)

Definition at line 1242 of file event_solvingphase.c.

Referenced by SCIPincludeEventHdlrSolvingphase(), and testCriteria().

DISP_NAME_NRANK1NODES

#define DISP_NAME_NRANK1NODES   "nrank1nodes"

Definition at line 1463 of file event_solvingphase.c.

Referenced by SCIP_DECL_DISPOUTPUT(), and SCIPincludeEventHdlrSolvingphase().

DISP_DESC_NRANK1NODES

#define DISP_DESC_NRANK1NODES   "current number of rank1 nodes left"

Definition at line 1464 of file event_solvingphase.c.

Referenced by SCIPincludeEventHdlrSolvingphase().

DISP_HEAD_NRANK1NODES

#define DISP_HEAD_NRANK1NODES   "rank1"

Definition at line 1465 of file event_solvingphase.c.

Referenced by SCIPincludeEventHdlrSolvingphase().

DISP_WIDT_NRANK1NODES

#define DISP_WIDT_NRANK1NODES   7

Definition at line 1466 of file event_solvingphase.c.

Referenced by SCIP_DECL_DISPOUTPUT(), and SCIPincludeEventHdlrSolvingphase().

DISP_PRIO_NRANK1NODES

#define DISP_PRIO_NRANK1NODES   40000

Definition at line 1467 of file event_solvingphase.c.

Referenced by SCIPincludeEventHdlrSolvingphase().

DISP_POSI_NRANK1NODES

#define DISP_POSI_NRANK1NODES   500

Definition at line 1468 of file event_solvingphase.c.

Referenced by SCIPincludeEventHdlrSolvingphase().

DISP_STRI_NRANK1NODES

#define DISP_STRI_NRANK1NODES   TRUE

Definition at line 1469 of file event_solvingphase.c.

Referenced by SCIPincludeEventHdlrSolvingphase().

DISP_NAME_NNODESBELOWINC

#define DISP_NAME_NNODESBELOWINC   "nnodesbelowinc"

Definition at line 1486 of file event_solvingphase.c.

Referenced by SCIP_DECL_DISPOUTPUT(), and SCIPincludeEventHdlrSolvingphase().

DISP_DESC_NNODESBELOWINC

#define DISP_DESC_NNODESBELOWINC   "current number of nodes with an estimate better than the current incumbent"

Definition at line 1487 of file event_solvingphase.c.

Referenced by SCIPincludeEventHdlrSolvingphase().

DISP_HEAD_NNODESBELOWINC

#define DISP_HEAD_NNODESBELOWINC   "nbInc"

Definition at line 1488 of file event_solvingphase.c.

Referenced by SCIPincludeEventHdlrSolvingphase().

DISP_WIDT_NNODESBELOWINC

#define DISP_WIDT_NNODESBELOWINC   6

Definition at line 1489 of file event_solvingphase.c.

Referenced by SCIP_DECL_DISPOUTPUT(), and SCIPincludeEventHdlrSolvingphase().

DISP_PRIO_NNODESBELOWINC

#define DISP_PRIO_NNODESBELOWINC   40000

Definition at line 1490 of file event_solvingphase.c.

Referenced by SCIPincludeEventHdlrSolvingphase().

DISP_POSI_NNODESBELOWINC

#define DISP_POSI_NNODESBELOWINC   550

Definition at line 1491 of file event_solvingphase.c.

Referenced by SCIPincludeEventHdlrSolvingphase().

DISP_STRI_NNODESBELOWINC

#define DISP_STRI_NNODESBELOWINC   TRUE

Definition at line 1492 of file event_solvingphase.c.

Referenced by SCIPincludeEventHdlrSolvingphase().

Typedef Documentation

SOLVINGPHASE

typedef enum SolvingPhase SOLVINGPHASE

Definition at line 110 of file event_solvingphase.c.

DEPTHINFO

typedef struct DepthInfo DEPTHINFO

Definition at line 123 of file event_solvingphase.c.

Enumeration Type Documentation

SolvingPhase

enum SolvingPhase

enumerator to represent the current solving phase

Enumerator
SOLVINGPHASE_UNINITIALIZED	solving phase has not been initialized yet
SOLVINGPHASE_FEASIBILITY	no solution was found until now
SOLVINGPHASE_IMPROVEMENT	current incumbent solution is suboptimal
SOLVINGPHASE_PROOF	current incumbent is optimal

Definition at line 103 of file event_solvingphase.c.

Function Documentation

SCIP_DECL_SORTPTRCOMP()

static SCIP_DECL_SORTPTRCOMP ( sortCompTreeinfo  )

static

nodes are sorted first by their estimates, and if estimates are equal, by their number

Definition at line 174 of file event_solvingphase.c.

References addNodesInformation(), SCIP_Longint, SCIP_Real, SCIPnodeGetEstimate(), and SCIPnodeGetNumber().

addNodesInformation()

static SCIP_RETCODE addNodesInformation ( SCIP *  scip, SCIP_EVENTHDLRDATA *  eventhdlrdata, SCIP_NODE **  nodes, int  nnodes  )

static

insert an array of open nodes (leaves/siblings/children) into the event handler data structures and update the transition information

Parameters

scip	SCIP data structure
eventhdlrdata	event handler data
nodes	array of nodes
nnodes	number of nodes

Definition at line 211 of file event_solvingphase.c.

References DepthInfo::minestimate, DepthInfo::minnodes, DepthInfo::minnodescapacity, DepthInfo::nminnodes, nnodes, DepthInfo::nsolvednodes, NULL, removeNode(), SCIP_CALL, SCIP_NODETYPE_CHILD, SCIP_NODETYPE_LEAF, SCIP_NODETYPE_SIBLING, SCIP_OKAY, SCIP_Real, SCIPgetUpperbound(), SCIPisGE(), SCIPisLT(), SCIPnodeGetDepth(), SCIPnodeGetEstimate(), SCIPnodeGetType(), SCIPreallocBlockMemoryArray, and SCIPsortedvecInsertPtr().

Referenced by recomputeNodeInformation(), SCIP_DECL_SORTPTRCOMP(), and updateDataStructures().

removeNode()

static void removeNode ( SCIP_NODE *  node, SCIP_EVENTHDLRDATA *  eventhdlrdata  )

static

remove a node from the data structures of the event handler

Parameters

node	node that should be removed
eventhdlrdata	event handler data

Definition at line 269 of file event_solvingphase.c.

References getNRank1Nodes(), DepthInfo::minnodes, DepthInfo::nminnodes, NULL, SCIP_Bool, SCIPnodeGetDepth(), SCIPsortedvecDelPosPtr(), and SCIPsortedvecFindPtr().

Referenced by addNodesInformation(), and releaseNodeFromDepthInfo().

getNRank1Nodes()

static int getNRank1Nodes ( SCIP *  scip )

static

returns the current number of rank 1 nodes in the tree

Parameters

scip	SCIP data structure

Definition at line 300 of file event_solvingphase.c.

References EVENTHDLR_NAME, getNNodesBelowIncumbent(), NULL, SCIP_STAGE_SOLVING, SCIPeventhdlrGetData(), SCIPfindEventhdlr(), and SCIPgetStage().

Referenced by checkRankOneTransition(), removeNode(), SCIP_DECL_DISPOUTPUT(), and transitionPhase3().

getNNodesBelowIncumbent()

static int getNNodesBelowIncumbent ( SCIP *  scip )

static

returns the current number of open nodes which have an estimate lower than the incumbent solution

Parameters

scip	SCIP data structure

Definition at line 319 of file event_solvingphase.c.

References EVENTHDLR_NAME, NULL, recomputeNodeInformation(), SCIP_STAGE_SOLVING, SCIPeventhdlrGetData(), SCIPfindEventhdlr(), and SCIPgetStage().

Referenced by getNRank1Nodes(), and SCIP_DECL_DISPOUTPUT().

recomputeNodeInformation()

static SCIP_RETCODE recomputeNodeInformation ( SCIP *  scip, SCIP_EVENTHDLRDATA *  eventhdlrdata  )

static

discards all previous node information and renews it

Parameters

scip	SCIP data structure
eventhdlrdata	event handler data

Definition at line 338 of file event_solvingphase.c.

References addNodesInformation(), createDepthinfo(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_STAGE_SOLVING, SCIPgetOpenNodesData(), and SCIPgetStage().

Referenced by getNNodesBelowIncumbent(), releaseNodeInformation(), and updateDataStructures().

createDepthinfo()

static SCIP_RETCODE createDepthinfo ( SCIP *  scip, DEPTHINFO **  depthinfo  )

static

allocates memory for a depth info

Parameters

scip	SCIP data structure
depthinfo	pointer to depth information structure

Definition at line 385 of file event_solvingphase.c.

References freeDepthinfo(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, and SCIPinfinity().

Referenced by ensureDepthInfoArraySize(), and recomputeNodeInformation().

freeDepthinfo()

static SCIP_RETCODE freeDepthinfo ( SCIP *  scip, DEPTHINFO **  depthinfo  )

static

frees depth information data structure

Parameters

scip	SCIP data structure
depthinfo	pointer to depth information structure

Definition at line 410 of file event_solvingphase.c.

References NULL, releaseNodeFromDepthInfo(), SCIP_OKAY, SCIPfreeBlockMemory, and SCIPfreeBlockMemoryArray.

Referenced by createDepthinfo(), and SCIP_DECL_EVENTEXITSOL().

releaseNodeFromDepthInfo()

static void releaseNodeFromDepthInfo ( SCIP *  scip, SCIP_EVENTHDLRDATA *  eventhdlrdata, SCIP_NODE *  node  )

static

removes the node itself and updates the data if this node defined an active estimate globally or locally at its depth level

Parameters

scip	SCIP data structure
eventhdlrdata	event handler data
node	node to be removed from the data structures of the event handler

Definition at line 429 of file event_solvingphase.c.

References ensureDepthInfoArraySize(), DepthInfo::minestimate, DepthInfo::minnodes, DepthInfo::nminnodes, DepthInfo::nsolvednodes, NULL, removeNode(), SCIPgetUpperbound(), SCIPisGT(), SCIPisLT(), SCIPnodeGetDepth(), and SCIPnodeGetEstimate().

Referenced by freeDepthinfo(), and releaseNodeInformation().

ensureDepthInfoArraySize()

static SCIP_RETCODE ensureDepthInfoArraySize ( SCIP *  scip, SCIP_EVENTHDLRDATA *  eventhdlrdata, SCIP_NODE *  node  )

static

ensures sufficient size for depthInfo array

Parameters

scip	SCIP data structure
eventhdlrdata	event handler data
node	node to be removed from the data structures of the event handler

Definition at line 473 of file event_solvingphase.c.

References createDepthinfo(), releaseNodeInformation(), SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPnodeGetDepth(), and SCIPreallocBlockMemoryArray.

Referenced by releaseNodeFromDepthInfo(), and releaseNodeInformation().

releaseNodeInformation()

static SCIP_RETCODE releaseNodeInformation ( SCIP *  scip, SCIP_EVENTHDLRDATA *  eventhdlrdata, SCIP_NODE *  node  )

static

ensures the capacity of the event handler data structures and removes the current node

Parameters

scip	SCIP data structure
eventhdlrdata	event handler data
node	node to be removed from the data structures of the event handler

Definition at line 518 of file event_solvingphase.c.

References checkLeavesBelowIncumbent(), ensureDepthInfoArraySize(), NULL, recomputeNodeInformation(), releaseNodeFromDepthInfo(), SCIP_CALL, SCIP_OKAY, SCIPgetNDelayedCutoffs(), and SCIPgetNNodesLeft().

Referenced by ensureDepthInfoArraySize(), and updateDataStructures().

checkLeavesBelowIncumbent()

static int checkLeavesBelowIncumbent ( SCIP *  scip )

static

ensures correctness of counters by explicitly summing up all children, leaves, and siblings with small estimates

Definition at line 553 of file event_solvingphase.c.

References getX(), nnodes, SCIP_OKAY, SCIP_Real, SCIPgetChildren(), SCIPgetLeaves(), SCIPgetNNodesLeft(), SCIPgetSiblings(), SCIPgetUpperbound(), SCIPisLT(), and SCIPnodeGetEstimate().

Referenced by releaseNodeInformation(), and updateDataStructures().

getX()

static SCIP_Real getX ( SCIP *  scip, SCIP_EVENTHDLRDATA *  eventhdlrdata  )

static

get the point of the X axis for the regression according to the user choice of X type (time/nodes/iterations)

Parameters

scip	SCIP data structure
eventhdlrdata	event handler data

Definition at line 601 of file event_solvingphase.c.

References getCurrentRegressionTangentAxisIntercept(), MAX, SCIP_Real, SCIP_STAGE_SOLVED, SCIP_STAGE_SOLVING, SCIPgetNLPIterations(), SCIPgetNTotalNodes(), SCIPgetSolvingTime(), SCIPgetStage(), and x.

Referenced by checkLeavesBelowIncumbent(), getCurrentRegressionTangentAxisIntercept(), and updateLogRegression().

getCurrentRegressionTangentAxisIntercept()

static SCIP_Real getCurrentRegressionTangentAxisIntercept ( SCIP *  scip, SCIP_EVENTHDLRDATA *  eventhdlrdata  )

static

get axis intercept of current tangent to logarithmic regression curve

Parameters

scip	SCIP data structure
eventhdlrdata	event handler data structure

Definition at line 646 of file event_solvingphase.c.

References checkRankOneTransition(), getX(), NULL, SCIP_Bool, SCIP_Real, SCIPinfinity(), SCIPregressionGetIntercept(), SCIPregressionGetNObservations(), and SCIPregressionGetSlope().

Referenced by checkLogCriterion(), and getX().

checkRankOneTransition()

static SCIP_Bool checkRankOneTransition ( SCIP *  scip, SCIP_EVENTHDLRDATA *  eventhdlrdata  )

static

checks if rank-1 transition has been reached, that is, when all open nodes have a best-estimate higher than the best previously checked node at this depth

Parameters

scip	SCIP data structure
eventhdlrdata	event handler data

Definition at line 679 of file event_solvingphase.c.

References checkEstimateCriterion(), FALSE, getNRank1Nodes(), SCIP_Bool, SCIPgetNNodes(), and SCIPgetNSols().

Referenced by getCurrentRegressionTangentAxisIntercept(), testCriteria(), and transitionPhase3().

checkEstimateCriterion()

static SCIP_Bool checkEstimateCriterion ( SCIP *  scip, SCIP_EVENTHDLRDATA *  eventhdlrdata  )

static

check if Best-Estimate criterion was reached, that is, when the active estimate is not better than the current incumbent solution

Parameters

scip	SCIP data structure
eventhdlrdata	event handler data

Definition at line 693 of file event_solvingphase.c.

References checkLogCriterion(), FALSE, SCIP_Bool, SCIP_STAGE_SOLVING, SCIPgetNNodes(), SCIPgetNSols(), and SCIPgetStage().

Referenced by checkRankOneTransition(), testCriteria(), and transitionPhase3().

checkLogCriterion()

static SCIP_Bool checkLogCriterion ( SCIP *  scip, SCIP_EVENTHDLRDATA *  eventhdlrdata  )

static

check if logarithmic phase transition has been reached.

the logarithmic phase transition is reached when the slope of the logarithmic primal progress (as a function of the number of LP iterations or solving nodes) becomes gentle. More concretely, we measure the slope by calculating the axis intercept of the tangent of the logarithmic primal progress. We then compare this axis intercept to the first and current primal bound and say that the logarithmic phase transition is reached as soon as the axis intercept passes the current primal bound so that the scalar becomes negative.

While it would be enough to directly compare the primal bound and the axis intercept of the tangent to check the criterion, the scalar allows for a continuous indicator how far the phase transition is still ahead

Parameters

scip	SCIP data structure
eventhdlrdata	event handler data

Definition at line 718 of file event_solvingphase.c.

References checkOptimalSolution(), FALSE, getCurrentRegressionTangentAxisIntercept(), SCIP_Bool, SCIP_Real, SCIPgetFirstPrimalBound(), SCIPgetNSols(), SCIPgetPrimalbound(), SCIPisInfinity(), SCIPisNegative(), and TRUE.

Referenced by checkEstimateCriterion(), testCriteria(), and transitionPhase3().

checkOptimalSolution()

static SCIP_Bool checkOptimalSolution ( SCIP *  scip, SCIP_EVENTHDLRDATA *  eventhdlrdata  )

static

check if incumbent solution is nearly optimal; we allow a relative deviation of 10^-9

Parameters

scip	SCIP data structure
eventhdlrdata	event handler data

Definition at line 747 of file event_solvingphase.c.

References EPSZ, FALSE, REALABS, SCIP_Bool, SCIP_Real, SCIPgetPrimalbound(), SCIPisInfinity(), transitionPhase3(), and TRUE.

Referenced by checkLogCriterion(), testCriteria(), and transitionPhase3().

transitionPhase3()

static SCIP_Bool transitionPhase3 ( SCIP *  scip, SCIP_EVENTHDLRDATA *  eventhdlrdata  )

static

check if we are in the proof phase

Parameters

scip	SCIP data structure
eventhdlrdata	event handler data

Definition at line 770 of file event_solvingphase.c.

References checkEstimateCriterion(), checkLogCriterion(), checkOptimalSolution(), checkRankOneTransition(), determineSolvingPhase(), FALSE, getNRank1Nodes(), NULL, SCIP_VERBLEVEL_NORMAL, SCIPgetNNodes(), SCIPgetPrimalbound(), SCIPgetSolvingTime(), SCIPverbMessage(), SOLVINGPHASE_PROOF, and TRUE.

Referenced by checkOptimalSolution(), and determineSolvingPhase().

determineSolvingPhase()

static void determineSolvingPhase ( SCIP *  scip, SCIP_EVENTHDLRDATA *  eventhdlrdata  )

static

Parameters

scip	SCIP data structure
eventhdlrdata	event handler data

Definition at line 831 of file event_solvingphase.c.

References changeEmphasisParameters(), SCIPgetNSols(), SOLVINGPHASE_FEASIBILITY, SOLVINGPHASE_IMPROVEMENT, SOLVINGPHASE_PROOF, and transitionPhase3().

Referenced by applySolvingPhase(), and transitionPhase3().

changeEmphasisParameters()

static SCIP_RETCODE changeEmphasisParameters ( SCIP *  scip, SCIP_EVENTHDLRDATA *  eventhdlrdata  )

static

changes parameters by using emphasis settings

Parameters

scip	SCIP data structure
eventhdlrdata	event handler data

Definition at line 848 of file event_solvingphase.c.

References changeParametersUsingSettingsFiles(), FALSE, SCIP_CALL, SCIP_OKAY, SCIP_PARAMEMPHASIS_DEFAULT, SCIP_PARAMEMPHASIS_PHASEFEAS, SCIP_PARAMEMPHASIS_PHASEIMPROVE, SCIP_PARAMEMPHASIS_PHASEPROOF, SCIPABORT, SCIPdebugMsg, SCIPsetEmphasis(), SOLVINGPHASE_FEASIBILITY, SOLVINGPHASE_IMPROVEMENT, SOLVINGPHASE_PROOF, and SOLVINGPHASE_UNINITIALIZED.

Referenced by adaptSolverBehavior(), and determineSolvingPhase().

changeParametersUsingSettingsFiles()

static SCIP_RETCODE changeParametersUsingSettingsFiles ( SCIP *  scip, SCIP_EVENTHDLRDATA *  eventhdlrdata  )

static

change general solving strategy of SCIP depending on the phase by reading from settings file

Parameters

scip	SCIP data structure
eventhdlrdata	event handler data

Definition at line 882 of file event_solvingphase.c.

References DEFAULT_SETNAME, fixOrUnfixRelevantParameters(), NULL, SCIP_CALL, SCIP_INVALIDCALL, SCIP_OKAY, SCIP_VERBLEVEL_NORMAL, SCIPdebugMsg, SCIPreadParams(), SCIPverbMessage(), SCIPwarningMessage(), SOLVINGPHASE_FEASIBILITY, SOLVINGPHASE_IMPROVEMENT, SOLVINGPHASE_PROOF, and SOLVINGPHASE_UNINITIALIZED.

Referenced by adaptSolverBehavior(), and changeEmphasisParameters().

fixOrUnfixRelevantParameters()

static SCIP_RETCODE fixOrUnfixRelevantParameters ( SCIP *  scip, SCIP_EVENTHDLRDATA *  eventhdlrdata, SCIP_Bool  fix  )

static

fix/unfix relevant solving parameters that should not accidentally be set to default values

Parameters

scip	SCIP data structure
eventhdlrdata	event handler data
fix	should the parameters be fixed (true) or unfixed?

Definition at line 936 of file event_solvingphase.c.

References adaptSolverBehavior(), SCIP_CALL, SCIP_OKAY, SCIPfixParam(), SCIPparamGetName(), SCIPparamIsFixed(), and SCIPunfixParam().

Referenced by adaptSolverBehavior(), and changeParametersUsingSettingsFiles().

adaptSolverBehavior()

static SCIP_RETCODE adaptSolverBehavior ( SCIP *  scip, SCIP_EVENTHDLRDATA *  eventhdlrdata  )

static

change settings depending whether emphasis settings should be used, or settings files

Parameters

scip	SCIP data structure
eventhdlrdata	event handler data

Definition at line 1006 of file event_solvingphase.c.

References applySolvingPhase(), changeEmphasisParameters(), changeParametersUsingSettingsFiles(), FALSE, fixOrUnfixRelevantParameters(), SCIP_CALL, SCIP_OKAY, SCIP_PARAMEMPHASIS_DEFAULT, SCIPsetEmphasis(), and TRUE.

Referenced by applySolvingPhase(), and fixOrUnfixRelevantParameters().

applySolvingPhase()

static SCIP_RETCODE applySolvingPhase ( SCIP *  scip, SCIP_EVENTHDLRDATA *  eventhdlrdata  )

static

Parameters

scip	SCIP data structure
eventhdlrdata	event handler data

Definition at line 1036 of file event_solvingphase.c.

References adaptSolverBehavior(), determineSolvingPhase(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_VERBLEVEL_NORMAL, SCIPinterruptSolve(), SCIPrestartSolve(), SCIPverbMessage(), SOLVINGPHASE_IMPROVEMENT, SOLVINGPHASE_PROOF, TRUE, and updateLogRegression().

Referenced by adaptSolverBehavior(), SCIP_DECL_EVENTEXEC(), and SCIP_DECL_EVENTINIT().

updateLogRegression()

static SCIP_RETCODE updateLogRegression ( SCIP *  scip, SCIP_EVENTHDLRDATA *  eventhdlrdata  )

static

update the logarithmic regression

Parameters

scip	SCIP data structure
eventhdlrdata	data of event handler

Definition at line 1092 of file event_solvingphase.c.

References getX(), SCIP_OKAY, SCIP_Real, SCIPgetPrimalbound(), SCIPisEQ(), SCIPregressionAddObservation(), SCIPregressionRemoveObservation(), and updateDataStructures().

Referenced by applySolvingPhase(), and updateDataStructures().

updateDataStructures()

static SCIP_RETCODE updateDataStructures ( SCIP *  scip, SCIP_EVENTHDLRDATA *  eventhdlrdata, SCIP_EVENTTYPE  eventtype  )

static

update data structures based on the event type caught

Parameters

scip	SCIP data structure
eventhdlrdata	data of event handler
eventtype	type of the caught event

Definition at line 1119 of file event_solvingphase.c.

References addNodesInformation(), checkLeavesBelowIncumbent(), FALSE, recomputeNodeInformation(), releaseNodeInformation(), SCIP_CALL, SCIP_EVENTTYPE_BESTSOLFOUND, SCIP_EVENTTYPE_NODEBRANCHED, SCIP_EVENTTYPE_NODEFOCUSED, SCIP_OKAY, SCIP_STAGE_SOLVING, SCIPgetChildren(), SCIPgetCurrentNode(), SCIPgetNChildren(), SCIPgetNNodesLeft(), SCIPgetStage(), testCriteria(), TRUE, and updateLogRegression().

Referenced by SCIP_DECL_EVENTEXEC(), and updateLogRegression().

testCriteria()

static void testCriteria ( SCIP *  scip, SCIP_EVENTHDLRDATA *  eventhdlrdata  )

static

test all criteria whether they have been reached

Parameters

scip	SCIP data structure
eventhdlrdata	data of event handler

Definition at line 1185 of file event_solvingphase.c.

References checkEstimateCriterion(), checkLogCriterion(), checkOptimalSolution(), checkRankOneTransition(), eventCopySolvingphase, EVENTHDLR_NAME, NULL, SCIP_CALL, SCIP_DECL_EVENTCOPY, SCIP_OKAY, SCIP_VERBLEVEL_NORMAL, SCIPeventhdlrGetName(), SCIPgetNNodes(), SCIPgetSolvingTime(), SCIPincludeEventHdlrSolvingphase(), SCIPverbMessage(), and TRUE.

Referenced by SCIP_DECL_EVENTEXEC(), and updateDataStructures().

SCIP_DECL_EVENTFREE()

static SCIP_DECL_EVENTFREE ( eventFreeSolvingphase  )

static

destructor of event handler to free user data (called when SCIP is exiting)

Definition at line 1247 of file event_solvingphase.c.

References EVENTHDLR_NAME, NULL, SCIP_DECL_EVENTINITSOL(), SCIP_OKAY, SCIPeventhdlrGetData(), SCIPeventhdlrGetName(), SCIPeventhdlrSetData(), SCIPfreeBlockMemory, and SCIPregressionFree().

SCIP_DECL_EVENTINITSOL()

static SCIP_DECL_EVENTINITSOL ( eventInitsolSolvingphase  )

static

initialization method of event handler (called after problem was transformed)

Definition at line 1268 of file event_solvingphase.c.

References FALSE, NULL, SCIP_DECL_EVENTEXITSOL(), SCIP_OKAY, SCIPeventhdlrGetData(), and SCIPgetNDelayedCutoffs().

Referenced by SCIP_DECL_EVENTFREE().

SCIP_DECL_EVENTEXITSOL()

static SCIP_DECL_EVENTEXITSOL ( eventExitsolSolvingphase  )

static

solving process deinitialization method of event handler (called before branch and bound process data is freed)

Definition at line 1287 of file event_solvingphase.c.

References collectNondefaultParams(), freeDepthinfo(), NULL, SCIP_CALL, SCIP_OKAY, SCIPeventhdlrGetData(), and SCIPfreeBlockMemoryArray.

Referenced by SCIP_DECL_EVENTINITSOL().

collectNondefaultParams()

static SCIP_RETCODE collectNondefaultParams ( SCIP *  scip, SCIP_EVENTHDLRDATA *  eventhdlrdata  )

static

collects all parameters that are set to non-default values and stores them in eventhdlrdata

Parameters

scip	SCIP data structure
eventhdlrdata	data of event handler

Definition at line 1315 of file event_solvingphase.c.

References NULL, SCIP_CALL, SCIP_DECL_EVENTINIT(), SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPgetNParams(), SCIPgetParams(), SCIPparamIsDefault(), and SCIPreallocBlockMemoryArray.

Referenced by SCIP_DECL_EVENTEXITSOL(), and SCIP_DECL_EVENTINIT().

SCIP_DECL_EVENTINIT()

static SCIP_DECL_EVENTINIT ( eventInitSolvingphase  )

static

initialization method of event handler (called after problem was transformed)

Definition at line 1360 of file event_solvingphase.c.

References applySolvingPhase(), collectNondefaultParams(), EVENTHDLR_EVENT, EVENTHDLR_NAME, FALSE, NULL, SCIP_CALL, SCIP_DECL_EVENTEXIT(), SCIP_INVALID, SCIP_OKAY, SCIPcatchEvent(), SCIPeventhdlrGetData(), SCIPeventhdlrGetName(), SCIPregressionReset(), and SOLVINGPHASE_UNINITIALIZED.

Referenced by collectNondefaultParams().

SCIP_DECL_EVENTEXIT()

static SCIP_DECL_EVENTEXIT ( eventExitSolvingphase  )

static

deinitialization method of event handler (called before problem is freed)

Definition at line 1407 of file event_solvingphase.c.

References EVENTHDLR_NAME, NULL, SCIP_DECL_EVENTEXEC(), SCIP_OKAY, SCIPeventhdlrGetData(), SCIPeventhdlrGetName(), and SCIPfreeBlockMemoryArrayNull.

Referenced by SCIP_DECL_EVENTINIT().

SCIP_DECL_EVENTEXEC()

static SCIP_DECL_EVENTEXEC ( eventExecSolvingphase  )

static

execution method of event handler

Definition at line 1427 of file event_solvingphase.c.

References applySolvingPhase(), EVENTHDLR_EVENT, NULL, SCIP_CALL, SCIP_EVENTTYPE_NODEFOCUSED, SCIP_OKAY, SCIPeventGetNode(), SCIPeventGetType(), SCIPeventhdlrGetData(), SCIPgetCurrentNode(), testCriteria(), and updateDataStructures().

Referenced by SCIP_DECL_EVENTEXIT().

SCIP_DECL_DISPOUTPUT() [1/2]

static SCIP_DECL_DISPOUTPUT ( dispOutputNRank1Nodes  )

static

output method of display column to output file stream 'file'

Definition at line 1473 of file event_solvingphase.c.

References DISP_NAME_NRANK1NODES, DISP_WIDT_NRANK1NODES, getNRank1Nodes(), NULL, SCIP_OKAY, SCIPdispGetName(), SCIPdispInt(), and SCIPgetMessagehdlr().

SCIP_DECL_DISPOUTPUT() [2/2]

static SCIP_DECL_DISPOUTPUT ( dispOutputNnodesbelowinc  )

static

output method of display column to output file stream 'file'

Definition at line 1496 of file event_solvingphase.c.

References DISP_NAME_NNODESBELOWINC, DISP_WIDT_NNODESBELOWINC, getNNodesBelowIncumbent(), NULL, SCIP_OKAY, SCIPdispGetName(), SCIPdispInt(), SCIPgetMessagehdlr(), and SCIPincludeEventHdlrSolvingphase().

SCIPincludeEventHdlrSolvingphase()

SCIP_RETCODE SCIPincludeEventHdlrSolvingphase

(

SCIP *

scip

)

creates event handler for Solvingphase event

Parameters

scip	SCIP data structure

Definition at line 1509 of file event_solvingphase.c.

References DEFAULT_ENABLED, DEFAULT_FALLBACK, DEFAULT_INTERRUPTOPTIMAL, DEFAULT_LOGREGRESSION_XTYPE, DEFAULT_NODEOFFSET, DEFAULT_SETNAME, DEFAULT_TESTMODE, DEFAULT_TRANSITIONMETHOD, DEFAULT_USEEMPHSETTINGS, DEFAULT_USERESTART1TO2, DEFAULT_USERESTART2TO3, DISP_DESC_NNODESBELOWINC, DISP_DESC_NRANK1NODES, DISP_HEAD_NNODESBELOWINC, DISP_HEAD_NRANK1NODES, DISP_NAME_NNODESBELOWINC, DISP_NAME_NRANK1NODES, DISP_POSI_NNODESBELOWINC, DISP_POSI_NRANK1NODES, DISP_PRIO_NNODESBELOWINC, DISP_PRIO_NRANK1NODES, DISP_STRI_NNODESBELOWINC, DISP_STRI_NRANK1NODES, DISP_WIDT_NNODESBELOWINC, DISP_WIDT_NRANK1NODES, eventCopySolvingphase, EVENTHDLR_DESC, EVENTHDLR_NAME, FALSE, LOGREGRESSION_XTYPES, NULL, SCIP_CALL, SCIP_DISPSTATUS_OFF, SCIP_INVALID, SCIP_LONGINT_MAX, SCIP_OKAY, SCIP_REAL_MAX, SCIP_REAL_MIN, SCIPaddBoolParam(), SCIPaddCharParam(), SCIPaddLongintParam(), SCIPaddRealParam(), SCIPaddStringParam(), SCIPallocBlockMemory, SCIPincludeDisp(), SCIPincludeEventhdlrBasic(), SCIPregressionCreate(), SCIPsetEventhdlrCopy(), SCIPsetEventhdlrExit(), SCIPsetEventhdlrExitsol(), SCIPsetEventhdlrFree(), SCIPsetEventhdlrInit(), SCIPsetEventhdlrInitsol(), and TRANSITIONMETHODS.

Referenced by SCIP_DECL_DISPOUTPUT(), SCIPincludeDefaultPlugins(), and testCriteria().