Solving Constraint Integer Programs

Public Variable Graph Methods

Detailed Description

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


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

scipSCIP data structure
vargraphpointer to the variable graph, or NULL to let the function create a local graph
startvarsarray of start variables to calculate distance from
nstartvarsnumber of starting variables, at least 1
distancesarray to keep distance in vargraph from start variables for every variable
maxdistancemaximum distance >= 0 from start variable (INT_MAX for complete BFS)
maxvarsmaximum number of variables to compute distance for
maxbinintvarsmaximum number of binary or integer variables to compute distance for

Definition at line 1491 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(), selectInitialVariable(), 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

scipSCIP data structure
vargraphpointer to the variable graph
relaxdenseconssshould dense constraints (at least as dense as density) be ignored by connectivity graph?
relaxdensitydensity (with respect to number of variables) to relax constraint from graph
nrelaxedconstraintspointer to store the number of constraints that were relaxed, or NULL if not needed

Definition at line 1792 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

scipSCIP data structure
vargraphpointer to the variable graph

Definition at line 1830 of file heur.c.

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

Referenced by determineVariableFixings(), and SCIPvariablegraphBreadthFirst().