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.

EVENTHDLR_DESC

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

Definition at line 76 of file event_solvingphase.c.

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.

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 80 of file event_solvingphase.c.

DEFAULT_SETNAME

#define DEFAULT_SETNAME   "-"

default settings file name for solving phase setting files

Definition at line 81 of file event_solvingphase.c.

DEFAULT_TRANSITIONMETHOD

#define DEFAULT_TRANSITIONMETHOD   'r'

the default transition method

Definition at line 82 of file event_solvingphase.c.

DEFAULT_NODEOFFSET

#define DEFAULT_NODEOFFSET   50L

default node offset before transition to proof phase is active

Definition at line 83 of file event_solvingphase.c.

DEFAULT_FALLBACK

#define DEFAULT_FALLBACK   FALSE

should the phase transition fall back to suboptimal phase?

Definition at line 84 of file event_solvingphase.c.

DEFAULT_INTERRUPTOPTIMAL

#define DEFAULT_INTERRUPTOPTIMAL   FALSE

should solving process be interrupted if optimal solution was found?

Definition at line 85 of file event_solvingphase.c.

DEFAULT_ENABLED

#define DEFAULT_ENABLED   FALSE

should the event handler be executed?

Definition at line 87 of file event_solvingphase.c.

DEFAULT_TESTMODE

#define DEFAULT_TESTMODE   FALSE

should the event handler test the criteria?

Definition at line 88 of file event_solvingphase.c.

DEFAULT_USERESTART1TO2

#define DEFAULT_USERESTART1TO2   FALSE

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

Definition at line 90 of file event_solvingphase.c.

DEFAULT_USERESTART2TO3

#define DEFAULT_USERESTART2TO3   FALSE

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

Definition at line 91 of file event_solvingphase.c.

DEFAULT_USEEMPHSETTINGS

#define DEFAULT_USEEMPHSETTINGS   TRUE

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

Definition at line 92 of file event_solvingphase.c.

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 95 of file event_solvingphase.c.

LOGREGRESSION_XTYPES

#define LOGREGRESSION_XTYPES   "lnt"

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

Definition at line 96 of file event_solvingphase.c.

eventCopySolvingphase

#define eventCopySolvingphase   NULL

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

Definition at line 1241 of file event_solvingphase.c.

DISP_NAME_NRANK1NODES

#define DISP_NAME_NRANK1NODES   "nrank1nodes"

Definition at line 1462 of file event_solvingphase.c.

DISP_DESC_NRANK1NODES

#define DISP_DESC_NRANK1NODES   "current number of rank1 nodes left"

Definition at line 1463 of file event_solvingphase.c.

DISP_HEAD_NRANK1NODES

#define DISP_HEAD_NRANK1NODES   "rank1"

Definition at line 1464 of file event_solvingphase.c.

DISP_WIDT_NRANK1NODES

#define DISP_WIDT_NRANK1NODES   7

Definition at line 1465 of file event_solvingphase.c.

DISP_PRIO_NRANK1NODES

#define DISP_PRIO_NRANK1NODES   40000

Definition at line 1466 of file event_solvingphase.c.

DISP_POSI_NRANK1NODES

#define DISP_POSI_NRANK1NODES   500

Definition at line 1467 of file event_solvingphase.c.

DISP_STRI_NRANK1NODES

#define DISP_STRI_NRANK1NODES   TRUE

Definition at line 1468 of file event_solvingphase.c.

DISP_NAME_NNODESBELOWINC

#define DISP_NAME_NNODESBELOWINC   "nnodesbelowinc"

Definition at line 1485 of file event_solvingphase.c.

DISP_DESC_NNODESBELOWINC

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

Definition at line 1486 of file event_solvingphase.c.

DISP_HEAD_NNODESBELOWINC

#define DISP_HEAD_NNODESBELOWINC   "nbInc"

Definition at line 1487 of file event_solvingphase.c.

DISP_WIDT_NNODESBELOWINC

#define DISP_WIDT_NNODESBELOWINC   6

Definition at line 1488 of file event_solvingphase.c.

DISP_PRIO_NNODESBELOWINC

#define DISP_PRIO_NNODESBELOWINC   40000

Definition at line 1489 of file event_solvingphase.c.

DISP_POSI_NNODESBELOWINC

#define DISP_POSI_NNODESBELOWINC   550

Definition at line 1490 of file event_solvingphase.c.

DISP_STRI_NNODESBELOWINC

#define DISP_STRI_NNODESBELOWINC   TRUE

Definition at line 1491 of file event_solvingphase.c.

Typedef Documentation

SOLVINGPHASE

typedef enum SolvingPhase SOLVINGPHASE

Definition at line 109 of file event_solvingphase.c.

DEPTHINFO

typedef struct DepthInfo DEPTHINFO

Definition at line 122 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 102 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 173 of file event_solvingphase.c.

References 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 210 of file event_solvingphase.c.

References DepthInfo::minestimate, DepthInfo::minnodes, DepthInfo::minnodescapacity, DepthInfo::nminnodes, nnodes, DepthInfo::nsolvednodes, NULL, 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(), 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 268 of file event_solvingphase.c.

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

Referenced by 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 299 of file event_solvingphase.c.

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

Referenced by checkRankOneTransition(), 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 318 of file event_solvingphase.c.

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

Referenced by 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 337 of file event_solvingphase.c.

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

Referenced by 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 384 of file event_solvingphase.c.

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

Referenced by ensureDepthInfoArraySize().

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 409 of file event_solvingphase.c.

References NULL, SCIP_OKAY, SCIPfreeBlockMemory, and SCIPfreeBlockMemoryArray.

Referenced by 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 428 of file event_solvingphase.c.

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

Referenced by 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 472 of file event_solvingphase.c.

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

Referenced by 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 517 of file event_solvingphase.c.

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

Referenced by 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 552 of file event_solvingphase.c.

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

Referenced by 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 600 of file event_solvingphase.c.

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

Referenced by 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 645 of file event_solvingphase.c.

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

Referenced by checkLogCriterion().

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 678 of file event_solvingphase.c.

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

Referenced by 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 692 of file event_solvingphase.c.

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

Referenced by 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 717 of file event_solvingphase.c.

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

Referenced by 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 746 of file event_solvingphase.c.

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

Referenced by 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 769 of file event_solvingphase.c.

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

Referenced by determineSolvingPhase().

determineSolvingPhase()

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

static

Parameters

scip	SCIP data structure
eventhdlrdata	event handler data

Definition at line 830 of file event_solvingphase.c.

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

Referenced by applySolvingPhase().

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 847 of file event_solvingphase.c.

References 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().

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 881 of file event_solvingphase.c.

References DEFAULT_SETNAME, 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().

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 935 of file event_solvingphase.c.

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

Referenced by adaptSolverBehavior().

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 1005 of file event_solvingphase.c.

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

Referenced by applySolvingPhase().

applySolvingPhase()

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

static

Parameters

scip	SCIP data structure
eventhdlrdata	event handler data

Definition at line 1035 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, and TRUE.

Referenced by 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 1091 of file event_solvingphase.c.

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

Referenced by 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 1118 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(), TRUE, and updateLogRegression().

Referenced by SCIP_DECL_EVENTEXEC().

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 1184 of file event_solvingphase.c.

References checkEstimateCriterion(), checkLogCriterion(), checkOptimalSolution(), checkRankOneTransition(), NULL, SCIP_VERBLEVEL_NORMAL, SCIPgetNNodes(), SCIPgetSolvingTime(), SCIPverbMessage(), and TRUE.

Referenced by SCIP_DECL_EVENTEXEC().

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 1246 of file event_solvingphase.c.

References EVENTHDLR_NAME, NULL, 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 1267 of file event_solvingphase.c.

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

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 1286 of file event_solvingphase.c.

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

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 1314 of file event_solvingphase.c.

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

Referenced by 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 1359 of file event_solvingphase.c.

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

SCIP_DECL_EVENTEXIT()

static SCIP_DECL_EVENTEXIT ( eventExitSolvingphase  )

static

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

Definition at line 1406 of file event_solvingphase.c.

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

SCIP_DECL_EVENTEXEC()

static SCIP_DECL_EVENTEXEC ( eventExecSolvingphase  )

static

execution method of event handler

Definition at line 1426 of file event_solvingphase.c.

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

SCIP_DECL_DISPOUTPUT() [1/2]

static SCIP_DECL_DISPOUTPUT ( dispOutputNRank1Nodes  )

static

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

Definition at line 1472 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 1495 of file event_solvingphase.c.

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

SCIPincludeEventHdlrSolvingphase()

SCIP_RETCODE SCIPincludeEventHdlrSolvingphase

(

SCIP *

scip

)

creates event handler for Solvingphase event

Parameters

scip	SCIP data structure

Definition at line 1508 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 SCIPincludeDefaultPlugins().