Public Variable Graph Methods

Detailed Description

methods to create a variable graph and perform breadth-first search

Functions
SCIP_RETCODE	SCIPvariablegraphBreadthFirst (SCIP *scip, SCIP_VGRAPH *vargraph, SCIP_VAR **startvars, int nstartvars, int *distances, int maxdistance, int maxvars, int maxbinintvars)
SCIP_RETCODE	SCIPvariableGraphCreate (SCIP *scip, SCIP_VGRAPH **vargraph, SCIP_Bool relaxdenseconss, SCIP_Real relaxdensity, int *nrelaxedconstraints)
void	SCIPvariableGraphFree (SCIP *scip, SCIP_VGRAPH **vargraph)

Function Documentation

SCIPvariablegraphBreadthFirst()

SCIP_RETCODE SCIPvariablegraphBreadthFirst	(	SCIP *	scip,
		SCIP_VGRAPH *	vargraph,
		SCIP_VAR **	startvars,
		int	nstartvars,
		int *	distances,
		int	maxdistance,
		int	maxvars,
		int	maxbinintvars
	)

Perform breadth-first (BFS) search on the variable constraint graph.

The result of the algorithm is that the distances array contains the correct distances for every variable from the start variables. The distance of a variable can then be accessed through its problem index (calling SCIPvarGetProbindex()). Hence, The method assumes that the length of distances is at least SCIPgetNVars(). Variables that are not connected through constraints to the start variables have a distance of -1.

Limits can be provided to further restrict the breadth-first search. If a distance limit is given, the search will be performed until the first variable at this distance is popped from the queue, i.e., all variables with a distance < maxdistance have been labeled by the search. If a variable limit is given, the search stops after it completes the distance level at which the limit was reached. Hence, more variables may be actually labeled. The start variables are accounted for those variable limits.

If no variable variable constraint graph is provided, the method will create one and free it at the end This is useful for a single use of the variable constraint graph. For several consecutive uses, it is advised to create a variable constraint graph via SCIPvariableGraphCreate().

Parameters

scip	SCIP data structure
vargraph	pointer to the variable graph, or NULL to let the function create a local graph
startvars	array of start variables to calculate distance from
nstartvars	number of starting variables, at least 1
distances	array to keep distance in vargraph from start variables for every variable
maxdistance	maximum distance >= 0 from start variable (INT_MAX for complete BFS)
maxvars	maximum number of variables to compute distance for
maxbinintvars	maximum number of binary or integer variables to compute distance for

Definition at line 1690 of file heur.c.

References FALSE, NULL, SCIP_VGraph::nvarconss, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPfreeBufferArray, SCIPgetConsNVars(), SCIPgetConsVars(), SCIPgetVarsData(), SCIPhashtableExists(), SCIPhashtableInsert(), SCIPhashtableRemoveAll(), SCIPvarGetProbindex(), SCIPvariableGraphCreate(), SCIPvariableGraphFree(), SCIPvarIsActive(), TRUE, SCIP_VGraph::varconss, and SCIP_VGraph::visitedconss.

Referenced by alnsFixMoreVariables(), alnsUnfixVariables(), determineVariableFixings(), LNSFixMoreVariables(), LNSUnfixVariables(), selectInitialVariableDecomposition(), selectInitialVariableRandomly(), and selectNextVariable().

SCIPvariableGraphCreate()

SCIP_RETCODE SCIPvariableGraphCreate	(	SCIP *	scip,
		SCIP_VGRAPH **	vargraph,
		SCIP_Bool	relaxdenseconss,
		SCIP_Real	relaxdensity,
		int *	nrelaxedconstraints
	)

initialization method of variable graph data structure

Parameters

scip	SCIP data structure
vargraph	pointer to the variable graph
relaxdenseconss	should dense constraints (at least as dense as density) be ignored by connectivity graph?
relaxdensity	density (with respect to number of variables) to relax constraint from graph
nrelaxedconstraints	pointer to store the number of constraints that were relaxed, or NULL if not needed

Definition at line 1996 of file heur.c.

References fillVariableGraph(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocClearBlockMemoryArray, SCIPblkmem(), SCIPgetNConss(), SCIPgetNVars(), and SCIPhashtableCreate().

Referenced by determineVariableFixings(), and SCIPvariablegraphBreadthFirst().

SCIPvariableGraphFree()

void SCIPvariableGraphFree	(	SCIP *	scip,
		SCIP_VGRAPH **	vargraph
	)

deinitialization method of variable graph data structure

Parameters

scip	SCIP data structure
vargraph	pointer to the variable graph

Definition at line 2034 of file heur.c.

References NULL, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SCIPgetNVars(), and SCIPhashtableFree().

Referenced by determineVariableFixings(), and SCIPvariablegraphBreadthFirst().