Detailed Description

data structures and methods for collecting reoptimization information

Author: Jakob Witzig

Definition in file reopt.h.

#include "scip/def.h"
#include "scip/pub_reopt.h"
#include "scip/type_primal.h"
#include "scip/type_retcode.h"
#include "scip/type_reopt.h"
#include "scip/struct_reopt.h"

Go to the source code of this file.

Functions
SCIP_RETCODE	SCIPreoptCreate (SCIP_REOPT *reopt, SCIP_SET set, BMS_BLKMEM *blkmem)

SCIP_RETCODE	SCIPreoptFree (SCIP_REOPT *reopt, SCIP_SET set, SCIP_PRIMAL origprimal, BMS_BLKMEM blkmem)

int	SCIPreoptGetNAddedConss (SCIP_REOPT reopt, SCIP_NODE node)

SCIP_RETCODE	SCIPreoptAddSol (SCIP_REOPT reopt, SCIP_SET set, SCIP_STAT stat, SCIP_PRIMAL origprimal, BMS_BLKMEM blkmem, SCIP_SOL sol, SCIP_Bool bestsol, SCIP_Bool added, SCIP_VAR *vars, int nvars, int run)

SCIP_RETCODE	SCIPreoptAddOptSol (SCIP_REOPT reopt, SCIP_SOL sol, BMS_BLKMEM blkmem, SCIP_SET set, SCIP_STAT stat, SCIP_PRIMAL origprimal)

SCIP_RETCODE	SCIPreoptAddRun (SCIP_REOPT reopt, SCIP_SET set, BMS_BLKMEM blkmem, SCIP_VAR *vars, int nvars, int size)

int	SCIPreoptGetNCheckedSols (SCIP_REOPT *reopt)

void	SCIPreoptSetNCheckedSols (SCIP_REOPT *reopt, int ncheckedsols)

int	SCIPreoptGetNImprovingSols (SCIP_REOPT *reopt)

void	SCIPreoptSetNImprovingSols (SCIP_REOPT *reopt, int nimprovingsols)

int	SCIPreoptGetNSolsRun (SCIP_REOPT *reopt, int run)

int	SCIPreoptGetNSols (SCIP_REOPT *reopt)

SCIP_RETCODE	SCIPreoptGetSolsRun (SCIP_REOPT reopt, int run, SCIP_SOL sols, int solssize, int nsols)

int	SCIPreoptGetNSavedSols (SCIP_REOPT *reopt)

SCIP_RETCODE	SCIPreoptCheckRestart (SCIP_REOPT reopt, SCIP_SET set, BMS_BLKMEM blkmem, SCIP_NODE node, SCIP_VAR *transvars, int ntransvars, SCIP_Bool restart)

SCIP_Real	SCIPreoptGetSimToPrevious (SCIP_REOPT *reopt)

SCIP_Real	SCIPreoptGetSimToFirst (SCIP_REOPT *reopt)

SCIP_Real	SCIPreoptGetSimilarity (SCIP_REOPT reopt, SCIP_SET set, int run1, int run2, SCIP_VAR **transvars, int ntransvars)

SCIP_SOL *	SCIPreoptGetLastBestSol (SCIP_REOPT *reopt)

SCIP_REOPTNODE *	SCIPreoptGetReoptnode (SCIP_REOPT *reopt, unsigned int id)

SCIP_Real	SCIPreoptGetOldObjCoef (SCIP_REOPT *reopt, int run, int idx)

SCIP_SOL *	SCIPreoptGetBestSolRun (SCIP_REOPT *reopt, int run)

void	SCIPreoptResetSolMarks (SCIP_REOPT *reopt)

int	SCIPreoptGetNNodes (SCIP_REOPT reopt, SCIP_NODE node)

SCIP_RETCODE	SCIPreoptAddInfNode (SCIP_REOPT reopt, SCIP_SET set, BMS_BLKMEM blkmem, SCIP_NODE node)

SCIP_RETCODE	SCIPreoptCheckCutoff (SCIP_REOPT reopt, SCIP_SET set, BMS_BLKMEM blkmem, SCIP_NODE node, SCIP_EVENTTYPE eventtype, SCIP_LPSOLSTAT lpsolstat, SCIP_Bool isrootnode, SCIP_Bool isfocusnode, SCIP_Real lowerbound, int effectiverootdepth)

SCIP_RETCODE	SCIPreoptAddDualBndchg (SCIP_REOPT reopt, SCIP_SET set, BMS_BLKMEM blkmem, SCIP_NODE node, SCIP_VAR *var, SCIP_Real newval, SCIP_Real oldval)

int	SCIPreoptGetNDualBndchgs (SCIP_REOPT reopt, SCIP_NODE node)

int	SCIPreoptGetNLeaves (SCIP_REOPT reopt, SCIP_NODE node)

SCIP_RETCODE	SCIPreoptGetChildIDs (SCIP_REOPT reopt, SCIP_SET set, BMS_BLKMEM blkmem, SCIP_NODE node, unsigned int childs, int childssize, int nchilds)

SCIP_RETCODE	SCIPreoptGetLeaves (SCIP_REOPT reopt, SCIP_NODE node, unsigned int leaves, int leavessize, int nleaves)

SCIP_Real	SCIPreoptGetSavingtime (SCIP_REOPT *reopt)

SCIP_RETCODE	SCIPreoptAddGlbCons (SCIP_REOPT reopt, SCIP_VAR vars, SCIP_Real vals, int nvars, BMS_BLKMEM *blkmem)

SCIP_RETCODE	SCIPreoptApplyGlbConss (SCIP scip, SCIP_REOPT reopt, SCIP_SET set, SCIP_STAT stat, BMS_BLKMEM *blkmem)

SCIP_Bool	SCIPreoptGetSolveLP (SCIP_REOPT reopt, SCIP_SET set, SCIP_NODE *node)

SCIP_RETCODE	SCIPreoptApply (SCIP_REOPT reopt, SCIP scip, SCIP_SET set, SCIP_STAT stat, SCIP_PROB transprob, SCIP_PROB origprob, SCIP_TREE tree, SCIP_LP lp, SCIP_BRANCHCAND branchcand, SCIP_EVENTQUEUE eventqueue, SCIP_CLIQUETABLE cliquetable, BMS_BLKMEM blkmem, unsigned int randseed, SCIP_REOPTNODE reoptnode, unsigned int id, SCIP_Real estimate, SCIP_NODE childnodes, int ncreatedchilds, int naddedconss, int childnodessize, SCIP_Bool success)

SCIP_RETCODE	SCIPreoptDeleteNode (SCIP_REOPT reopt, SCIP_SET set, unsigned int id, BMS_BLKMEM *blkmem)

SCIP_RETCODE	SCIPreoptResetDualBndchgs (SCIP_REOPT reopt, SCIP_NODE node, BMS_BLKMEM *blkmem)

SCIP_RETCODE	SCIPreoptSplitRoot (SCIP_REOPT reopt, SCIP_TREE tree, SCIP_SET set, BMS_BLKMEM blkmem, unsigned int randseed, int ncreatedchilds, int naddedconss)

SCIP_RETCODE	SCIPreoptApplyCompression (SCIP_REOPT reopt, SCIP_SET set, BMS_BLKMEM blkmem, SCIP_REOPTNODE representatives, int nrepresentatives, SCIP_Bool success)

SCIP_RETCODE	SCIPreoptSaveOpenNodes (SCIP_REOPT reopt, SCIP_SET set, BMS_BLKMEM blkmem, SCIP_NODE leaves, int nleaves, SCIP_NODE childs, int nchilds, SCIP_NODE *siblings, int nsiblings)

void	SCIPreoptnodeInit (SCIP_REOPTNODE reoptnode, SCIP_SET set)

SCIP_RETCODE	SCIPreoptnodeReset (SCIP_REOPT reopt, SCIP_SET set, BMS_BLKMEM blkmem, SCIP_REOPTNODE reoptnode)

SCIP_RETCODE	SCIPreoptnodeDelete (SCIP_REOPTNODE *reoptnode, BMS_BLKMEM blkmem)

SCIP_RETCODE	SCIPreoptnodeAddBndchg (SCIP_REOPTNODE reoptnode, BMS_BLKMEM blkmem, SCIP_VAR *var, SCIP_Real val, SCIP_BOUNDTYPE boundtype)

SCIP_RETCODE	SCIPreoptnodeAddCons (SCIP_REOPTNODE reoptnode, BMS_BLKMEM blkmem, SCIP_VAR *consvars, SCIP_Real consvals, int nvars, REOPT_CONSTYPE constype)

void	SCIPreoptnodeGetPath (SCIP_REOPT reopt, SCIP_REOPTNODE reoptnode, SCIP_VAR *vars, SCIP_Real vals, SCIP_BOUNDTYPE boundtypes, int varssize, int nbndchgs, int *nbndchgsafterdual)

Function Documentation

SCIP_RETCODE SCIPreoptCreate	(	SCIP_REOPT **	reopt,
		SCIP_SET *	set,
		BMS_BLKMEM *	blkmem
	)

creates reopt data

constructor for the reoptimization data

Parameters

reopt	pointer to reoptimization data structure
set	global SCIP settings
blkmem	block memory

Definition at line 3977 of file reopt.c.

References BMSallocBlockMemoryArray, BMSallocMemory, BMSallocMemoryArray, createReopttree(), createSolTree(), DEFAULT_MEM_RUN, EVENTHDLR_DESC, EVENTHDLR_NAME, NULL, SCIP_ALLOC, SCIP_CALL, SCIP_CLOCKTYPE_DEFAULT, SCIP_OKAY, SCIPclockCreate(), SCIPeventhdlrCreate(), and SCIPsetIncludeEventhdlr().

Referenced by SCIPenableReoptimization().

SCIP_RETCODE SCIPreoptFree	(	SCIP_REOPT **	reopt,
		SCIP_SET *	set,
		SCIP_PRIMAL *	origprimal,
		BMS_BLKMEM *	blkmem
	)

frees reopt data

frees reoptimization data

Parameters

reopt	reoptimization data structure
set	global SCIP settings
origprimal	original primal
blkmem	block memory

Definition at line 4042 of file reopt.c.

References BMSfreeBlockMemory, BMSfreeBlockMemoryArray, BMSfreeMemory, BMSfreeMemoryArray, freeReoptTree(), freeSolTree(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_STAGE_INIT, SCIP_STAGE_PROBLEM, and SCIPclockFree().

Referenced by SCIPenableReoptimization(), and SCIPfreeProb().

int SCIPreoptGetNAddedConss	(	SCIP_REOPT *	reopt,
		SCIP_NODE *	node
	)

returns the number of constraints added by the reoptimization plug-in

Parameters

reopt	reoptimization data structure
node	node of the search tree

Definition at line 4131 of file reopt.c.

References MAX, SCIP_ReoptNode::nconss, NULL, SCIP_ReoptTree::reoptnodes, SCIP_Reopt::reopttree, SCIPnodeGetDepth(), SCIPnodeGetNAddedConss(), and SCIPnodeGetReoptID().

Referenced by SCIPreoptCheckCutoff().

SCIP_RETCODE SCIPreoptAddSol	(	SCIP_REOPT *	reopt,
		SCIP_SET *	set,
		SCIP_STAT *	stat,
		SCIP_PRIMAL *	origprimal,
		BMS_BLKMEM *	blkmem,
		SCIP_SOL *	sol,
		SCIP_Bool	bestsol,
		SCIP_Bool *	added,
		SCIP_VAR **	vars,
		int	nvars,
		int	run
	)

add a solution to the solution tree

Parameters

reopt	reoptimization data
set	global SCIP settings
stat	dynamic problem statistics
origprimal	original primal
blkmem	block memory
sol	solution to add
bestsol	is the current solution an optimal solution?
added	pointer to store the information if the soltion was added
vars	variable array
nvars	number of variables
run	number of the current run (1,2,...)

Definition at line 4155 of file reopt.c.

References ensureSolsSize(), SCIP_Reopt::noptsolsbyreoptsol, SCIP_SolTree::nsols, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), SCIPsolGetHeur(), SCIP_SolTree::sols, SCIP_Reopt::soltree, and soltreeAddSol().

Referenced by SCIPsolve().

SCIP_RETCODE SCIPreoptAddOptSol	(	SCIP_REOPT *	reopt,
		SCIP_SOL *	sol,
		BMS_BLKMEM *	blkmem,
		SCIP_SET *	set,
		SCIP_STAT *	stat,
		SCIP_PRIMAL *	origprimal
	)

add optimal solution

we want to store the optimal solution of each run in a separate array

Parameters

reopt	reoptimization data structure
sol	solution to add
blkmem	block memory
set	global SCIP settings
stat	dynamic problem statistics
origprimal	original primal

Definition at line 4208 of file reopt.c.

References NULL, SCIP_Reopt::prevbestsols, SCIP_Reopt::run, SCIP_CALL, SCIP_OKAY, and SCIPsolCopy().

Referenced by SCIPsolve().

SCIP_RETCODE SCIPreoptAddRun	(	SCIP_REOPT *	reopt,
		SCIP_SET *	set,
		BMS_BLKMEM *	blkmem,
		SCIP_VAR **	transvars,
		int	ntransvars,
		int	size
	)

add a run

add a new iteration after changing the objective function

Parameters

reopt	reoptimization data sturcture
set	global SCIP settings
blkmem	block memory
transvars	transformed variables
ntransvars	number of transformed variables
size	number of expected solutions

Definition at line 4234 of file reopt.c.

References BMSallocBlockMemoryArray, ensureRunSize(), NULL, reoptSaveNewObj(), resetStats(), SCIP_Reopt::run, SCIP_ALLOC, SCIP_CALL, SCIP_OKAY, SCIP_SolTree::sols, SCIP_SolTree::solssize, and SCIP_Reopt::soltree.

Referenced by SCIPsolve().

int SCIPreoptGetNCheckedSols ( SCIP_REOPT * reopt )

get the number of checked solutions during the reoptimization process

get the number of checked during the reoptimization process

Parameters

reopt reoptimization data structure

Definition at line 4266 of file reopt.c.

References SCIP_Reopt::ncheckedsols, and NULL.

Referenced by SCIPprintReoptStatistics().

void SCIPreoptSetNCheckedSols	(	SCIP_REOPT *	reopt,
		int	ncheckedsols
	)

update the number of checked solutions during the reoptimization process

update the number of checked during the reoptimization process

Parameters

reopt	reoptimization data structure
ncheckedsols	number of updated solutions

Definition at line 4276 of file reopt.c.

References SCIP_Reopt::ncheckedsols, and NULL.

int SCIPreoptGetNImprovingSols ( SCIP_REOPT * reopt )

get the number of checked during the reoptimization process

Parameters

reopt reoptimization data structure

Definition at line 4287 of file reopt.c.

References SCIP_Reopt::nimprovingsols, and NULL.

Referenced by SCIPprintReoptStatistics().

void SCIPreoptSetNImprovingSols	(	SCIP_REOPT *	reopt,
		int	nimprovingsols
	)

update the number of checked during the reoptimization process

Parameters

reopt	reoptimization data structure
nimprovingsols	number of improving solutions

Definition at line 4297 of file reopt.c.

References SCIP_Reopt::nimprovingsols, and NULL.

int SCIPreoptGetNSolsRun	(	SCIP_REOPT *	reopt,
		int	run
	)

returns number of solution

returns number of solution of a given run

Parameters

reopt	reoptimization data structure
run	number of the run (1,2,..)

Definition at line 4308 of file reopt.c.

References SCIP_SolTree::nsols, NULL, SCIP_SolTree::sols, and SCIP_Reopt::soltree.

int SCIPreoptGetNSols ( SCIP_REOPT * reopt )

returns number of all solutions of all runs

Parameters

reopt reoptimization data structure

Definition at line 4323 of file reopt.c.

References SCIP_SolTree::nsols, NULL, SCIP_Reopt::run, and SCIP_Reopt::soltree.

SCIP_RETCODE SCIPreoptGetSolsRun	(	SCIP_REOPT *	reopt,
		int	run,
		SCIP_SOL **	sols,
		int	solssize,
		int *	nsols
	)

return the stored solutions of a given run

Parameters

reopt	reoptimization data structure
run	number of the run (1,2,...)
sols	array of solutions to fill
solssize	length of the array
nsols	pointer to store the number of added solutions

Definition at line 4339 of file reopt.c.

References SCIP_SolTree::nsols, NULL, SCIP_OKAY, SCIP_SolNode::sol, SCIP_SolTree::sols, SCIP_Reopt::soltree, TRUE, and SCIP_SolNode::updated.

Referenced by SCIPgetReopSolsRun().

int SCIPreoptGetNSavedSols ( SCIP_REOPT * reopt )

returns the number of saved solutions overall runs

Parameters

reopt reoptimization data structure

Definition at line 4381 of file reopt.c.

References SCIP_SolNode::lchild, NULL, SCIP_SolNode::rchild, SCIP_SolTree::root, SCIP_Reopt::soltree, and soltreeNInducedSols().

SCIP_RETCODE SCIPreoptCheckRestart	(	SCIP_REOPT *	reopt,
		SCIP_SET *	set,
		BMS_BLKMEM *	blkmem,
		SCIP_NODE *	node,
		SCIP_VAR **	transvars,
		int	ntransvars,
		SCIP_Bool *	restart
	)

Check if the reoptimization process should be (locally) restarted.

First, we check whether the current node is the root node, e.g., node == NULL. In this case, we do not need to calculate the similarity again. We trigger a restart if

the objective function has changed too much, or
the number of stored nodes is exceeded, or
the last n optimal solutions were found by heur_reoptsols (in this case, the stored tree was only needed to prove the optimality and this can probably be done faster by solving from scratch).

If the current node is different to the root node we calculate the local similarity, i.e., exclude all variables that are already fixed at the given node.

check if the reoptimization process should be (locally) restarted.

First, we check whether the current node is the root node, e.g., node == NULL. in this case, we do not need to calculate the similarity again. we trigger a restart if

the objective function has changed too much
the number of stored nodes is exceeded
the last n optimal solutions were found by heur_reoptsols (in this case, the stored tree was only needed to prove the optimality and this can be probably faster by solving from scratch)

If the current node is different to the root node we calculate the local similarity, i.e., exclude all variable that are already fixed by bounding.

Parameters

reopt	reoptimization data structure
set	global SCIP settings
blkmem	block memory
node	current node of the branch and bound tree (or NULL)
transvars	transformed problem variables
ntransvars	number of transformed problem variables
restart	pointer to store if the reoptimization process should be restarted

Definition at line 4408 of file reopt.c.

References FALSE, SCIP_Reopt::noptsolsbyreoptsol, SCIP_ReoptTree::nreoptnodes, NULL, reoptCheckLocalRestart(), reoptRestart(), SCIP_Reopt::reopttree, SCIP_Reopt::run, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPsetIsFeasLT(), SCIP_Reopt::simtolastobj, and TRUE.

Referenced by SCIPcheckReoptRestart(), and SCIPsolve().

SCIP_Real SCIPreoptGetSimToPrevious ( SCIP_REOPT * reopt )

returns the similarity to the previous objective function

returns the similarity to the previous objective function, if no exist return -2.0

Parameters

reopt reoptimization data structure

Definition at line 4471 of file reopt.c.

References NULL, and SCIP_Reopt::simtolastobj.

Referenced by SCIPgetReoptSimilarity().

SCIP_Real SCIPreoptGetSimToFirst ( SCIP_REOPT * reopt )

returns the similarity to the first objective functions

returns the similarity to the first objective different to the zero-function function, if no exist return -2.0

Parameters

reopt reoptimization data structure

Definition at line 4480 of file reopt.c.

References NULL, and SCIP_Reopt::simtofirstobj.

SCIP_Real SCIPreoptGetSimilarity	(	SCIP_REOPT *	reopt,
		SCIP_SET *	set,
		int	run1,
		int	run2,
		SCIP_VAR **	transvars,
		int	ntransvars
	)

return the similarity between two of objective functions of two given runs

Parameters

reopt	reoptimization data structure
set	global SCIP settings
run1	number of the first run
run2	number of the second run
transvars	original problem variables
ntransvars	number of original problem variables

Definition at line 4489 of file reopt.c.

References NULL, and reoptSimilarity().

Referenced by SCIPgetReoptSimilarity().

SCIP_SOL* SCIPreoptGetLastBestSol ( SCIP_REOPT * reopt )

returns the best solution of the last run

Parameters

reopt reoptimization data structure

Definition at line 4508 of file reopt.c.

References NULL, SCIP_Reopt::prevbestsols, and SCIP_Reopt::run.

Referenced by SCIPgetReoptLastOptSol().

SCIP_REOPTNODE* SCIPreoptGetReoptnode	(	SCIP_REOPT *	reopt,
		unsigned int	id
	)

returns the node of the reoptimization tree corresponding to the unique id

Parameters

reopt	reoptimization data structure
id	unique id

Definition at line 4524 of file reopt.c.

References NULL, SCIP_ReoptTree::reoptnodes, and SCIP_Reopt::reopttree.

Referenced by SCIPgetReoptnode().

SCIP_Real SCIPreoptGetOldObjCoef	(	SCIP_REOPT *	reopt,
		int	run,
		int	idx
	)

returns the coefficent of variable with index idx in run run

returns the coefficient of variable with index idx in run run

Parameters

reopt	reoptimization data structure
run	number of the run (1,2,...)
idx	index of variable

Definition at line 4538 of file reopt.c.

References NULL, and SCIP_Reopt::objs.

Referenced by reoptCheckLocalRestart(), and SCIPgetReoptOldObjCoef().

SCIP_SOL* SCIPreoptGetBestSolRun	(	SCIP_REOPT *	reopt,
		int	run
	)

return the best solution of a given run

Note: the returned solution is part of the original space.

return the best solution of a given run.

Note: the return solution is part of the original space.

Parameters

reopt	reoptimization data structure
run	number of the run (1,2,...)

Definition at line 4554 of file reopt.c.

References NULL, and SCIP_Reopt::prevbestsols.

void SCIPreoptResetSolMarks ( SCIP_REOPT * reopt )

reset marks of stored solutions to not updated

Parameters

reopt reoptimization data structure

Definition at line 4566 of file reopt.c.

References SCIP_SolNode::lchild, NULL, SCIP_SolNode::rchild, SCIP_SolTree::root, SCIP_Reopt::soltree, and soltreeResetMarks().

Referenced by SCIPresetReoptSolMarks().

int SCIPreoptGetNNodes	(	SCIP_REOPT *	reopt,
		SCIP_NODE *	node
	)

returns the number of stored nodes

returns the number of stored nodes in the subtree induced by node

Parameters

reopt	reoptimization data structure
node	node of the search tree

Definition at line 4581 of file reopt.c.

References SCIP_ReoptTree::nreoptnodes, NULL, SCIP_Reopt::reopttree, reopttreeGetNNodes(), SCIPnodeGetDepth(), and SCIPnodeGetReoptID().

Referenced by compressReoptTree(), and SCIPgetNReoptnodes().

SCIP_RETCODE SCIPreoptAddInfNode	(	SCIP_REOPT *	reopt,
		SCIP_SET *	set,
		BMS_BLKMEM *	blkmem,
		SCIP_NODE *	node
	)

save information that given node is infeasible

Parameters

reopt	reoptimization data structure
set	global SCIP settings
blkmem	block memory
node	node of the search tree

Definition at line 4801 of file reopt.c.

References SCIP_ReoptTree::ninfnodes, SCIP_ReoptTree::ntotalinfnodes, NULL, REOPT_CONSTYPE_INFSUBTREE, SCIP_Reopt::reopttree, saveGlobalCons(), SCIP_CALL, and SCIP_OKAY.

Referenced by SCIPreoptCheckCutoff().

SCIP_RETCODE SCIPreoptCheckCutoff	(	SCIP_REOPT *	reopt,
		SCIP_SET *	set,
		BMS_BLKMEM *	blkmem,
		SCIP_NODE *	node,
		SCIP_EVENTTYPE	eventtype,
		SCIP_LPSOLSTAT	lpsolstat,
		SCIP_Bool	isrootnode,
		SCIP_Bool	isfocusnode,
		SCIP_Real	lowerbound,
		int	effectiverootdepth
	)

check the reason for cut off a node and if necessary store the node

Parameters

reopt	reoptimization data structure
set	global SCIP settings
blkmem	block memory
node	node of the search tree
eventtype	eventtype
lpsolstat	solution status of the LP
isrootnode	the node is the root
isfocusnode	the node is the current focus node
lowerbound	lower bound of the node
effectiverootdepth	effective root depth

Definition at line 4825 of file reopt.c.

References addNode(), SCIP_Reopt::currentnode, deleteLastDualBndchgs(), SCIP_Reopt::dualcons, FALSE, SCIP_Reopt::lastbranched, SCIP_Reopt::lastseennode, NULL, LogicOrData::nvars, REOPT_CONSTYPE_INFSUBTREE, REOPT_CONSTYPE_STRBRANCHED, SCIP_Bool, SCIP_CALL, SCIP_EVENTTYPE_NODEBRANCHED, SCIP_EVENTTYPE_NODEFEASIBLE, SCIP_EVENTTYPE_NODEINFEASIBLE, SCIP_LPSOLSTAT_INFEASIBLE, SCIP_LPSOLSTAT_NOTSOLVED, SCIP_LPSOLSTAT_OBJLIMIT, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_REOPTTYPE_FEASIBLE, SCIP_REOPTTYPE_INFSUBTREE, SCIP_REOPTTYPE_LOGICORNODE, SCIP_REOPTTYPE_PRUNED, SCIP_REOPTTYPE_STRBRANCHED, SCIP_REOPTTYPE_TRANSIT, SCIPdebugMessage, SCIPnodeGetDepth(), SCIPnodeGetNDualBndchgs(), SCIPnodeGetNumber(), SCIPreoptAddDualBndchg(), SCIPreoptAddInfNode(), SCIPreoptGetNAddedConss(), SCIPreoptGetNDualBndchgs(), SCIPreoptResetDualBndchgs(), and TRUE.

Referenced by nodeToLeaf(), SCIPnodeCutoff(), SCIPnodeFocus(), SCIPnodepqBound(), SCIPsolveCIP(), SCIPtreeCutoff(), and solveNodeLP().

SCIP_RETCODE SCIPreoptAddDualBndchg	(	SCIP_REOPT *	reopt,
		SCIP_SET *	set,
		BMS_BLKMEM *	blkmem,
		SCIP_NODE *	node,
		SCIP_VAR *	var,
		SCIP_Real	newval,
		SCIP_Real	oldval
	)

store bound change based on dual information

Parameters

reopt	reoptimization data structure
set	global SCIP settings
blkmem	block memory
node	node of the search tree
var	variables
newval	new bound
oldval	old bound

Definition at line 5073 of file reopt.c.

References checkMemDualCons(), SCIP_Reopt::currentnode, DEFAULT_MEM_DUALCONS, SCIP_Reopt::dualcons, NULL, LogicOrData::nvars, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPnodeGetNumber(), SCIPsetIsFeasEQ(), SCIPvarGetName(), SCIPvarGetOrigvarSum(), SCIPvarIsOriginal(), LogicOrData::vals, LogicOrData::vars, and LogicOrData::varssize.

Referenced by SCIPaddReoptDualBndchg(), and SCIPreoptCheckCutoff().

int SCIPreoptGetNDualBndchgs	(	SCIP_REOPT *	reopt,
		SCIP_NODE *	node
	)

returns the number of bound changes based on dual information

Parameters

reopt	reoptimization data structure
node	node of the search tree

Definition at line 5138 of file reopt.c.

References SCIP_Reopt::currentnode, SCIP_Reopt::dualcons, NULL, LogicOrData::nvars, and SCIPnodeGetNumber().

Referenced by SCIPreoptCheckCutoff().

int SCIPreoptGetNLeaves	(	SCIP_REOPT *	reopt,
		SCIP_NODE *	node
	)

returns the number of leaf nodes of the subtree induced by node (of the whole tree if node == NULL)

Parameters

reopt	reoptimization data structure
node	node of the search tree (or NULL)

Definition at line 4766 of file reopt.c.

References SCIP_ReoptNode::childids, SCIP_ReoptNode::nchilds, NULL, reoptGetNLeaves(), SCIP_ReoptTree::reoptnodes, SCIP_Reopt::reopttree, SCIPnodeGetDepth(), and SCIPnodeGetReoptID().

Referenced by SCIPcomprExec(), and SCIPgetNReoptLeaves().

SCIP_RETCODE SCIPreoptGetChildIDs	(	SCIP_REOPT *	reopt,
		SCIP_SET *	set,
		BMS_BLKMEM *	blkmem,
		SCIP_NODE *	node,
		unsigned int *	childs,
		int	childssize,
		int *	nchilds
	)

returns the child nodes of node that need to be reoptimized next or NULL if node is a leaf

Parameters

reopt	reoptimization data structure
set	global SCIP settings
blkmem	block memory
node	node of the search tree
childs	array to store the child ids
childssize	size of the childs array
nchilds	pointer to store the number of child nodes

Definition at line 5158 of file reopt.c.

References SCIP_ReoptNode::childids, dryBranch(), SCIP_ReoptNode::nchilds, NULL, SCIP_ReoptTree::reoptnodes, SCIP_Reopt::reopttree, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPnodeGetDepth(), SCIPnodeGetReoptID(), and TRUE.

Referenced by SCIPgetReoptChildIDs().

SCIP_RETCODE SCIPreoptGetLeaves	(	SCIP_REOPT *	reopt,
		SCIP_NODE *	node,
		unsigned int *	leaves,
		int	leavessize,
		int *	nleaves
	)

returns all leaves of the subtree induced by node

Parameters

reopt	reoptimization data
node	node of the search tree
leaves	array to the the ids
leavessize	size of leaves array
nleaves	pointer to store the number of leav node

Definition at line 5211 of file reopt.c.

References SCIP_ReoptNode::childids, SCIP_ReoptNode::nchilds, NULL, reoptGetLeaves(), SCIP_ReoptTree::reoptnodes, SCIP_Reopt::reopttree, SCIP_CALL, SCIP_OKAY, and SCIPnodeGetReoptID().

Referenced by SCIPgetReoptLeaveIDs().

SCIP_Real SCIPreoptGetSavingtime ( SCIP_REOPT * reopt )

returns the time needed to store the nodes for reoptimization

Parameters

reopt reoptimization data structure

Definition at line 6126 of file reopt.c.

References NULL, SCIP_Reopt::savingtime, and SCIPclockGetTime().

Referenced by SCIPprintReoptStatistics().

SCIP_RETCODE SCIPreoptAddGlbCons	(	SCIP_REOPT *	reopt,
		SCIP_VAR **	vars,
		SCIP_Real *	vals,
		int	nvars,
		BMS_BLKMEM *	blkmem
	)

store a global constraint that should be added at the beginning of the next iteration

Parameters

reopt	reoptimization data structure
vars	array to store the variables of the constraint
vals	array to store the coefficients of the variables
nvars	pointer to store the size of the constraints
blkmem	block memory

Definition at line 6136 of file reopt.c.

References SCIP_Reopt::allocmemglbconss, BMSallocBlockMemory, BMSduplicateBlockMemoryArray, checkMemGlbCons(), SCIP_Reopt::glbconss, SCIP_Reopt::nglbconss, NULL, LogicOrData::nvars, SCIP_ALLOC, SCIP_CALL, SCIP_OKAY, LogicOrData::vals, LogicOrData::vars, and LogicOrData::varssize.

SCIP_RETCODE SCIPreoptApplyGlbConss	(	SCIP *	scip,
		SCIP_REOPT *	reopt,
		SCIP_SET *	set,
		SCIP_STAT *	stat,
		BMS_BLKMEM *	blkmem
	)

add the stored constraints globally to the problem

Parameters

scip	SCIP data structure
reopt	reoptimization data structure
set	global SCIP settings
stat	dynamic problem statistics
blkmem	block memory

Definition at line 6173 of file reopt.c.

References FALSE, SCIP_Reopt::glbconss, SCIP_Reopt::nglbconss, NULL, LogicOrData::nvars, SCIP_CALL, SCIP_OKAY, SCIPaddCons(), SCIPallocBufferArray, SCIPcreateConsLogicor(), SCIPdebugMessage, SCIPdebugPrintCons, SCIPfreeBlockMemoryArrayNull, SCIPfreeBlockMemoryNull, SCIPfreeBufferArray, SCIPreleaseCons(), SCIPsetIsFeasEQ(), SCIPvarGetTransVar(), SCIPvarNegate(), TRUE, LogicOrData::vals, and LogicOrData::vars.

Referenced by SCIPsolve().

SCIP_Bool SCIPreoptGetSolveLP	(	SCIP_REOPT *	reopt,
		SCIP_SET *	set,
		SCIP_NODE *	node
	)

check if the LP of the given node should be solved or not

Parameters

reopt	reoptimization data structure
set	global SCIP settings
node	node of the current search tree

Definition at line 6252 of file reopt.c.

References FALSE, SCIP_ReoptNode::nchilds, NULL, SCIP_ReoptNode::nvars, SCIP_ReoptTree::reoptnodes, SCIP_Reopt::reopttree, SCIPnodeGetDepth(), SCIPnodeGetReoptID(), SCIPnodeGetReopttype(), SCIPsetIsGT(), SCIP_Reopt::simtolastobj, and TRUE.

Referenced by solveNode().

SCIP_RETCODE SCIPreoptApply	(	SCIP_REOPT *	reopt,
		SCIP *	scip,
		SCIP_SET *	set,
		SCIP_STAT *	stat,
		SCIP_PROB *	transprob,
		SCIP_PROB *	origprob,
		SCIP_TREE *	tree,
		SCIP_LP *	lp,
		SCIP_BRANCHCAND *	branchcand,
		SCIP_EVENTQUEUE *	eventqueue,
		SCIP_CLIQUETABLE *	cliquetable,
		BMS_BLKMEM *	blkmem,
		unsigned int	randseed,
		SCIP_REOPTNODE *	reoptnode,
		unsigned int	id,
		SCIP_Real	estimate,
		SCIP_NODE **	childnodes,
		int *	ncreatedchilds,
		int *	naddedconss,
		int	childnodessize,
		SCIP_Bool *	success
	)

reactivate the given reoptnode and split them into several nodes if necessary

Parameters

reopt	reoptimization data structure
scip	SCIP data structure
set	global SCIP settings
stat	dynamic problem statistics
transprob	transformed problem
origprob	original problem
tree	branching tree
lp	current LP
branchcand	branching candidate
eventqueue	event queue
cliquetable	clique table
blkmem	block memory
randseed	seed value for random generator
reoptnode	node of the reoptimization tree to reactivate
id	id of the node to reactivate
estimate	estimate of the child nodes that should be created
childnodes	array to store the created child nodes
ncreatedchilds	pointer to store number of created child nodes
naddedconss	pointer to store number of generated constraints
childnodessize	available size of childnodes array
success	pointer store the result

Definition at line 5738 of file reopt.c.

References addLocalConss(), addSplitcons(), changeAncestorBranchings(), LogicOrData::constype, SCIP_ReoptNode::dualconscur, SCIP_ReoptNode::dualfixing, FALSE, fixBounds(), fixInterdiction(), SCIP_ReoptNode::lowerbound, SCIP_ReoptNode::nafterdualvars, SCIP_ReoptNode::nconss, NULL, LogicOrData::nvars, permuteRandom(), REALABS, REOPT_CONSTYPE_INFSUBTREE, REOPT_CONSTYPE_STRBRANCHED, SCIP_ReoptTree::reoptnodes, reoptnodeUpdateDualConss(), SCIP_Reopt::reopttree, SCIP_ReoptNode::reopttype, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIP_REOPTTYPE_INFSUBTREE, SCIP_REOPTTYPE_LOGICORNODE, SCIP_REOPTTYPE_NONE, SCIP_REOPTTYPE_STRBRANCHED, SCIP_REOPTTYPE_TRANSIT, SCIPdebugMessage, SCIPnodeCreateChild(), SCIPnodeGetLowerbound(), SCIPnodeGetNumber(), SCIPnodeSetEstimate(), SCIPnodeSetReoptID(), SCIPnodeSetReopttype(), SCIPsetIsInfinity(), SCIPsetIsRelGE(), TRUE, LogicOrData::vals, LogicOrData::vars, and LogicOrData::varssize.

Referenced by SCIPapplyReopt().

SCIP_RETCODE SCIPreoptDeleteNode	(	SCIP_REOPT *	reopt,
		SCIP_SET *	set,
		unsigned int	id,
		BMS_BLKMEM *	blkmem
	)

delete a node stored in the reoptimization tree

Parameters

reopt	reoptimization data structure
set	global SCIP settings
id	id of a stored node
blkmem	block memory

Definition at line 5719 of file reopt.c.

References NULL, SCIP_ReoptTree::reoptnodes, SCIP_Reopt::reopttree, reopttreeDeleteNode(), SCIP_CALL, SCIP_OKAY, and TRUE.

SCIP_RETCODE SCIPreoptResetDualBndchgs	(	SCIP_REOPT *	reopt,
		SCIP_NODE *	node,
		BMS_BLKMEM *	blkmem
	)

reset the stored information abound bound changes based on dual information

Parameters

reopt	reoptimization data structure
node	node of the search tree
blkmem	block memory

Definition at line 5639 of file reopt.c.

References NULL, reoptnodeResetDualConss(), SCIP_ReoptTree::reoptnodes, SCIP_Reopt::reopttree, SCIP_CALL, SCIP_OKAY, SCIPnodeGetDepth(), and SCIPnodeGetReoptID().

Referenced by addNode(), SCIPreoptCheckCutoff(), and SCIPresetReoptnodeDualcons().

SCIP_RETCODE SCIPreoptSplitRoot	(	SCIP_REOPT *	reopt,
		SCIP_TREE *	tree,
		SCIP_SET *	set,
		BMS_BLKMEM *	blkmem,
		unsigned int	randseed,
		int *	ncreatedchilds,
		int *	naddedconss
	)

splits the root into several nodes and moves the child nodes of the root to one of the created nodes

Parameters

reopt	reoptimization data structure
tree	branch and bound tree
set	global SCIP settings
blkmem	block memory
randseed	seed value for random generator
ncreatedchilds	pointer to store the number of created nodes
naddedconss	pointer to store the number added constraints

Definition at line 5420 of file reopt.c.

References BMSallocBlockMemory, BMSduplicateBlockMemoryArray, SCIP_ReoptNode::conss, LogicOrData::constype, createReoptnode(), SCIP_ReoptNode::dualconscur, SCIP_ReoptNode::dualfixing, SCIP_ReoptNode::nchilds, SCIP_ReoptNode::nconss, NULL, LogicOrData::nvars, SCIP_ReoptNode::nvars, SCIP_ReoptTree::openids, SCIP_ReoptNode::parentID, permuteRandom(), REOPT_CONSTYPE_STRBRANCHED, reoptAddChild(), reoptMoveIDs(), reoptnodeCheckMemory(), SCIP_ReoptTree::reoptnodes, SCIP_ReoptTree::reoptnodessize, reoptnodeUpdateDualConss(), SCIP_Reopt::reopttree, reopttreeCheckMemory(), SCIP_ReoptNode::reopttype, SCIP_ALLOC, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIP_REOPTTYPE_LOGICORNODE, SCIP_REOPTTYPE_STRBRANCHED, SCIP_REOPTTYPE_TRANSIT, SCIPnodeSetReopttype(), SCIPqueueRemove(), SCIPsetIsFeasEQ(), SCIPtreeGetRootNode(), LogicOrData::vals, SCIP_ReoptNode::varbounds, SCIP_ReoptNode::varboundtypes, LogicOrData::vars, SCIP_ReoptNode::vars, LogicOrData::varssize, and SCIP_ReoptNode::varssize.

Referenced by SCIPsplitReoptRoot().

SCIP_RETCODE SCIPreoptApplyCompression	(	SCIP_REOPT *	reopt,
		SCIP_SET *	set,
		BMS_BLKMEM *	blkmem,
		SCIP_REOPTNODE **	representatives,
		int	nrepresentatives,
		SCIP_Bool *	success
	)

reset the complete tree and set the given search frontier

Parameters

reopt	reoptimization data structure
set	global SCIP settings
blkmem	block memory
representatives	array of representatives
nrepresentatives	number of representatives
success	pointer to store if the method was successful

Definition at line 5320 of file reopt.c.

References SCIP_ReoptNode::conss, LogicOrData::constype, createReoptnode(), FALSE, SCIP_ReoptNode::nchilds, SCIP_ReoptNode::nconss, SCIP_ReoptTree::nreoptnodes, NULL, LogicOrData::nvars, SCIP_ReoptNode::nvars, SCIP_ReoptTree::openids, SCIP_ReoptNode::parentID, reoptAddChild(), SCIP_ReoptTree::reoptnodes, reoptResetTree(), SCIP_Reopt::reopttree, SCIP_ReoptNode::reopttype, SCIP_CALL, SCIP_OKAY, SCIP_REOPTTYPE_LEAF, SCIP_REOPTTYPE_LOGICORNODE, SCIP_REOPTTYPE_TRANSIT, SCIPdebugMessage, SCIPqueueRemove(), SCIPreoptnodeAddBndchg(), SCIPreoptnodeAddCons(), TRUE, LogicOrData::vals, SCIP_ReoptNode::varbounds, SCIP_ReoptNode::varboundtypes, LogicOrData::vars, SCIP_ReoptNode::vars, and SCIP_ReoptNode::varssize.

Referenced by SCIPsetReoptCompression().

SCIP_RETCODE SCIPreoptSaveOpenNodes	(	SCIP_REOPT *	reopt,
		SCIP_SET *	set,
		BMS_BLKMEM *	blkmem,
		SCIP_NODE **	leaves,
		int	nleaves,
		SCIP_NODE **	childs,
		int	nchilds,
		SCIP_NODE **	siblings,
		int	nsiblings
	)

add all unprocessed nodes to the reoptimization tree

Parameters

reopt	reoptimization data structure
set	global SCIP settings
blkmem	block memory
leaves	array of open leave nodes
nleaves	number of open leave nodes
childs	array of open children nodes
nchilds	number of open leave nodes
siblings	array of open sibling nodes
nsiblings	number of open leave nodes

Definition at line 5271 of file reopt.c.

References addNode(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_REOPTTYPE_PRUNED, SCIPdebugMessage, and SCIPnodeGetLowerbound().

Referenced by SCIPsolve().

void SCIPreoptnodeInit	(	SCIP_REOPTNODE *	reoptnode,
		SCIP_SET *	set
	)

initialize an empty node

Parameters

reoptnode	node of the reopttree
set	global SCIP settings

Definition at line 6295 of file reopt.c.

References SCIP_ReoptNode::afterdualvarbounds, SCIP_ReoptNode::afterdualvarboundtypes, SCIP_ReoptNode::afterdualvars, SCIP_ReoptNode::afterdualvarssize, SCIP_ReoptNode::allocchildmem, SCIP_ReoptNode::childids, SCIP_ReoptNode::conss, SCIP_ReoptNode::consssize, SCIP_ReoptNode::dualconscur, SCIP_ReoptNode::dualconsnex, SCIP_ReoptNode::dualfixing, FALSE, SCIP_ReoptNode::lowerbound, SCIP_ReoptNode::nafterdualvars, SCIP_ReoptNode::nchilds, SCIP_ReoptNode::nconss, NULL, SCIP_ReoptNode::nvars, SCIP_ReoptNode::parentID, SCIP_ReoptNode::reopttype, SCIP_REOPTTYPE_NONE, SCIPsetInfinity(), SCIP_ReoptNode::varbounds, SCIP_ReoptNode::varboundtypes, SCIP_ReoptNode::vars, and SCIP_ReoptNode::varssize.

Referenced by SCIPinitRepresentation().

SCIP_RETCODE SCIPreoptnodeReset	(	SCIP_REOPT *	reopt,
		SCIP_SET *	set,
		BMS_BLKMEM *	blkmem,
		SCIP_REOPTNODE *	reoptnode
	)

reset the given reoptimization node

Parameters

reopt	reoptimization data structure
set	global SCIP settings
blkmem	block memory
reoptnode	reoptimization node

Definition at line 6328 of file reopt.c.

References NULL, reoptnodeReset(), SCIP_CALL, and SCIP_OKAY.

Referenced by SCIPresetRepresentation().

SCIP_RETCODE SCIPreoptnodeDelete	(	SCIP_REOPTNODE **	reoptnode,
		BMS_BLKMEM *	blkmem
	)

delete the given reoptimization node

Parameters

reoptnode	pointer of reoptnode
blkmem	block memory

Definition at line 6346 of file reopt.c.

References NULL, reoptnodeDelete(), SCIP_CALL, and SCIP_OKAY.

Referenced by SCIPdeleteReoptnode(), and SCIPfreeRepresentation().

SCIP_RETCODE SCIPreoptnodeAddBndchg	(	SCIP_REOPTNODE *	reoptnode,
		BMS_BLKMEM *	blkmem,
		SCIP_VAR *	var,
		SCIP_Real	val,
		SCIP_BOUNDTYPE	boundtype
	)

add a variable to a given reoptnode

Parameters

reoptnode	node of the reopttree
blkmem	block memory
var	variable to add
val	value of the variable
boundtype	boundtype of the variable

Definition at line 6360 of file reopt.c.

References NULL, SCIP_ReoptNode::nvars, reoptnodeCheckMemory(), SCIP_CALL, SCIP_OKAY, SCIP_ReoptNode::varbounds, SCIP_ReoptNode::varboundtypes, and SCIP_ReoptNode::vars.

Referenced by SCIPaddReoptnodeBndchg(), SCIPreoptApplyCompression(), and SCIPreoptnodeAddCons().

SCIP_RETCODE SCIPreoptnodeAddCons	(	SCIP_REOPTNODE *	reoptnode,
		BMS_BLKMEM *	blkmem,
		SCIP_VAR **	consvars,
		SCIP_Real *	consvals,
		int	nvars,
		REOPT_CONSTYPE	constype
	)

add a constraint to a given reoptnode

Parameters

reoptnode	node of the reopttree
blkmem	block memory
consvars	variables which are part of the constraint
consvals	values of the variables
nvars	number of variables
constype	type of the constraint

Definition at line 6387 of file reopt.c.

References BMSallocBlockMemory, BMSduplicateBlockMemoryArray, SCIP_ReoptNode::conss, LogicOrData::constype, SCIP_ReoptNode::nconss, NULL, LogicOrData::nvars, reoptnodeCheckMemory(), SCIP_ALLOC, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPreoptnodeAddBndchg(), LogicOrData::vals, LogicOrData::vars, and LogicOrData::varssize.

Referenced by SCIPaddReoptnodeCons(), and SCIPreoptApplyCompression().

void SCIPreoptnodeGetPath	(	SCIP_REOPT *	reopt,
		SCIP_REOPTNODE *	reoptnode,
		SCIP_VAR **	vars,
		SCIP_Real *	vals,
		SCIP_BOUNDTYPE *	boundtypes,
		int	varssize,
		int *	nbndchgs,
		int *	nbndchgsafterdual
	)

return the branching path of the given node in the reoptimization tree

return the branching path stored of the given node in the reoptimization tree

Parameters

reopt	reoptimization data structure
reoptnode	node of the reoptimization tree
vars	array for variables
vals	array for values
boundtypes	array for bound types
varssize	size of arrays vars, vals, and boundtypes
nbndchgs	pointer to store the number of bound changes
nbndchgsafterdual	pointer to store the number of bound changes applied after the first dual reduction at the given node

Definition at line 5664 of file reopt.c.

References SCIP_ReoptNode::afterdualvarbounds, SCIP_ReoptNode::afterdualvarboundtypes, SCIP_ReoptNode::afterdualvars, SCIP_ReoptNode::nafterdualvars, NULL, SCIP_ReoptNode::nvars, SCIP_ReoptNode::parentID, SCIP_ReoptTree::reoptnodes, SCIP_Reopt::reopttree, SCIPreoptnodeGetPath(), SCIP_ReoptNode::varbounds, SCIP_ReoptNode::varboundtypes, and SCIP_ReoptNode::vars.

Referenced by SCIPgetReoptnodePath(), and SCIPreoptnodeGetPath().

SCIP

Detailed Description

Functions

Function Documentation