probdata_coloring.c
Go to the documentation of this file.
22 * The problem data contains the original graph, preprocessing information, the preprocessed graph,
27 * Additionally, it also deletes nodes that have a dominated neighborhood. For further information,
30 * The deleted nodes and the relation between the nodes of the original graph and the nodes of the
34 * Each variable has a pointer of type SCIP_VARDATA* that is used in this case to store an integer
35 * representing the number of the stable set. With the aid of this, the corresponding stable set can
36 * be found in the array returned by COLORprobGetStableSets(). This array contains all stable sets
38 * done by calling COLORprobStableSetIsNew(). All sets are sorted decreasingly with respect to the
42 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
64 int* new2oldnode; /* new2oldnode[i] = j iff node i in the (preprocessed) graph corresponds to node j in the old graph*/
94 SCIP_Bool dominates; /* is the neighbourhood of one node dominated by the neigbourhood of another one?*/
106 int nnodesdeleteddegreethisround; /* the number of nodes deleted due to low degree in the current round */
107 int nnodesdeletedneighbourthisround; /* the number of nodes deleted due to neighborhood in the current round */
213 /* node will be in the new graph, because degree is not low enough for deletion or it is in the maxClique */
221 /* at least one node was deleted, create new graph (tclique doesn't support deletion of nodes) */
281 /* set the corresponding old node to -1 for all nodes not in the current graph (only for bug-finding) */
299 assert(!COLORprobIsNodeInArray(probdata->new2oldnode[i], probdata->deletednodes, ndeletednodes));
356 /* at least one node was deleted, create new graph (tclique doesn't support deletion of nodes) */
418 /* set the corresponding old node to -1 for all nodes not in the current graph (only for bug-finding) */
477 (*targetdata)->nstablesets = sourcedata->nstablesets; /* copy number of sets saved in array sets */
481 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*targetdata)->stablesets), sourcedata->maxstablesets) );
482 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*targetdata)->stablesetlengths), sourcedata->maxstablesets) );
483 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*targetdata)->stablesetvars), sourcedata->maxstablesets) );
484 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*targetdata)->deletednodes), tcliqueGetNNodes(sourcedata->oldgraph)) );
485 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*targetdata)->new2oldnode), tcliqueGetNNodes(sourcedata->oldgraph)) );
498 SCIP_CALL( SCIPtransformVar(scip, sourcedata->stablesetvars[i], &((*targetdata)->stablesetvars[i])) );
499 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*targetdata)->stablesets[i]), sourcedata->stablesetlengths[i]) ); /*lint !e866*/
508 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*targetdata)->constraints, (*targetdata)->constraintssize) );
510 SCIP_CALL( SCIPtransformConss(scip, tcliqueGetNNodes(sourcedata->graph), sourcedata->constraints,
567 SCIPfreeBlockMemoryArray(scip, &((*probdata)->stablesets[i]), (*probdata)->stablesetlengths[i]); /*lint !e866*/
571 SCIPfreeBlockMemoryArray(scip, &((*probdata)->new2oldnode), tcliqueGetNNodes((*probdata)->oldgraph));
572 SCIPfreeBlockMemoryArray(scip, &((*probdata)->deletednodes), tcliqueGetNNodes((*probdata)->oldgraph));
590 SCIPfreeBlockMemoryArray(scip, &((*probdata)->new2oldnode), tcliqueGetNNodes((*probdata)->oldgraph));
591 SCIPfreeBlockMemoryArray(scip, &((*probdata)->deletednodes), tcliqueGetNNodes((*probdata)->oldgraph));
595 SCIPfreeBlockMemoryArray(scip, &((*probdata)->stablesets[i]), (*probdata)->stablesetlengths[i]); /*lint !e866*/
642 SCIPdebugMessage("remove variable %s [%d] from list of stable sets\n", SCIPvarGetName(var), idx);
647 SCIPfreeBlockMemoryArray(scip, &(probdata->stablesets[idx]), probdata->stablesetlengths[idx]); /*lint !e866*/
726 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(probdata->constraints), probdata->constraintssize) );
741 SCIP_CALL( SCIPcreateProb(scip, name, probdelorigColoring, probtransColoring, probdeltransColoring,
836 /* catch variable deleted event on the variable to update the stablesetvars array in the problem data */
837 SCIP_CALL( SCIPcatchVarEvent(scip, var, SCIP_EVENTTYPE_VARDELETED, SCIPfindEventhdlr(scip, EVENTHDLR_NAME),
901 /** checks whether the first set is equal to the second set, both sets have to be sorted in a decreasing way */
933 /** checks whether the given stable set is new returns TRUE if the stable is new, FALSE if it is equal to an already
998 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(probdata->stablesets), probdata->maxstablesets, newsize) );
999 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(probdata->stablesetlengths), probdata->maxstablesets, newsize) );
1000 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(probdata->stablesetvars), probdata->maxstablesets, newsize) );
1006 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(probdata->stablesets[probdata->nstablesets]), nstablesetnodes) ); /*lint !e866*/
1122 /** returns the array of nodes deleted during preprocessing, length = COLORprobGetOriginalNNodes(), filled with -1 at the end */
1137 /** returns the array in which for every node in the preprocessed graph, the related node in the original graph is saved */
1153 /** returns the node in the preprocessed graph, that belongs to the given node, returns -1 if node was deleted */
1316 SCIP_CALL( SCIPcreateConsSetcover(scip, &constraints[i], consname, 0, NULL, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE) );
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:90
Definition: struct_scip.h:59
int COLORprobGetOriginalNNodes(SCIP *scip)
Definition: probdata_coloring.c:1077
TCLIQUE_Bool tcliqueCreate(TCLIQUE_GRAPH **tcliquegraph)
Definition: tclique_graph.c:176
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:345
problem data for vertex coloring algorithm
TCLIQUE_Bool tcliqueAddNode(TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight)
Definition: tclique_graph.c:331
SCIP_RETCODE SCIPcreateProb(SCIP *scip, const char *name, SCIP_DECL_PROBDELORIG((*probdelorig)), SCIP_DECL_PROBTRANS((*probtrans)), SCIP_DECL_PROBDELTRANS((*probdeltrans)), SCIP_DECL_PROBINITSOL((*probinitsol)), SCIP_DECL_PROBEXITSOL((*probexitsol)), SCIP_DECL_PROBCOPY((*probcopy)), SCIP_PROBDATA *probdata)
Definition: scip_prob.c:108
SCIP_RETCODE SCIPcreateConsSetcover(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: cons_setppc.c:9317
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip_event.c:95
Definition: struct_var.h:198
SCIP_RETCODE SCIPtransformConss(SCIP *scip, int nconss, SCIP_CONS **conss, SCIP_CONS **transconss)
Definition: scip_cons.c:1562
void COLORprobGetStableSets(SCIP *scip, int ***stablesets, int **nelements, int *nstablesets)
Definition: probdata_coloring.c:1042
SCIP_EVENTHDLR * SCIPfindEventhdlr(SCIP *scip, const char *name)
Definition: scip_event.c:225
void COLORprobPrintStableSet(SCIP *scip, int setnumber)
Definition: probdata_coloring.c:795
Definition: tclique.h:57
int COLORprobGetNewNodeForOriginalNode(SCIP *scip, int node)
Definition: probdata_coloring.c:1154
int * COLORprobGetOriginalNodesForNewNodes(SCIP *scip)
Definition: probdata_coloring.c:1138
SCIP_CONS * COLORprobGetConstraint(SCIP *scip, int node)
Definition: probdata_coloring.c:1196
TCLIQUE_Bool tcliqueAddEdge(TCLIQUE_GRAPH *tcliquegraph, int node1, int node2)
Definition: tclique_graph.c:371
Definition: struct_cons.h:37
void COLORprobGetStableSet(SCIP *scip, int setindex, int **stableset, int *nelements)
Definition: probdata_coloring.c:1023
void tcliqueChangeWeight(TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight)
Definition: tclique_graph.c:353
int * tcliqueGetDegrees(TCLIQUE_GRAPH *tcliquegraph)
Definition: tclique_graph.c:770
SCIP_RETCODE COLORprobAddVarForStableSet(SCIP *scip, int setindex, SCIP_VAR *var)
Definition: probdata_coloring.c:823
SCIP_RETCODE COLORprobAddNewStableSet(SCIP *scip, int *stablesetnodes, int nstablesetnodes, int *setindex)
Definition: probdata_coloring.c:969
SCIP_Bool COLORprobStableSetsAreEqual(SCIP *scip, int *set1, int nset1nodes, int *set2, int nset2nodes)
Definition: probdata_coloring.c:902
TCLIQUE_GRAPH * COLORprobGetOriginalGraph(SCIP *scip)
Definition: probdata_coloring.c:1108
Definition: type_retcode.h:33
void tcliqueMaxClique(TCLIQUE_GETNNODES((*getnnodes)), TCLIQUE_GETWEIGHTS((*getweights)), TCLIQUE_ISEDGE((*isedge)), TCLIQUE_SELECTADJNODES((*selectadjnodes)), TCLIQUE_GRAPH *tcliquegraph, TCLIQUE_NEWSOL((*newsol)), TCLIQUE_DATA *tcliquedata, int *maxcliquenodes, int *nmaxcliquenodes, TCLIQUE_WEIGHT *maxcliqueweight, TCLIQUE_WEIGHT maxfirstnodeweight, TCLIQUE_WEIGHT minweight, int maxntreenodes, int backtrackfreq, int maxnzeroextensions, int fixednode, int *ntreenodes, TCLIQUE_STATUS *status)
Definition: tclique_branch.c:1001
SCIP_VAR * COLORprobGetVarForStableSet(SCIP *scip, int setindex)
Definition: probdata_coloring.c:847
Definition: type_retcode.h:34
SCIP_Bool COLORprobStableSetIsNew(SCIP *scip, int *stablesetnodes, int nstablesetnodes)
Definition: probdata_coloring.c:936
SCIP_CONS ** COLORprobGetConstraints(SCIP *scip)
Definition: probdata_coloring.c:1181
SCIP_Bool COLORprobIsNodeInStableSet(SCIP *scip, int setindex, int node)
Definition: probdata_coloring.c:864
int * tcliqueGetLastAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
Definition: tclique_graph.c:816
SCIP_RETCODE COLORprobGetComplementaryGraph(SCIP *scip, TCLIQUE_GRAPH *graph, TCLIQUE_GRAPH *cgraph)
Definition: probdata_coloring.c:1213
int * COLORprobGetDeletedNodes(SCIP *scip)
Definition: probdata_coloring.c:1123
int * tcliqueGetFirstAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
Definition: tclique_graph.c:792
static SCIP_DECL_PROBDELORIG(probdelorigColoring)
Definition: probdata_coloring.c:583
static SCIP_DECL_EVENTEXEC(eventExecProbdatavardeleted)
Definition: probdata_coloring.c:626
SCIP_RETCODE SCIPcreateProbColoring(SCIP *scip, const char *name, int nnodes, int nedges, int **edges)
Definition: probdata_coloring.c:671
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
void SCIPsortDownInt(int *intarray, int len)
SCIP_Bool COLORprobIsNodeInArray(int node, int *arraynodes, int narraynodes)
Definition: probdata_coloring.c:1325
void COLORprobPrintStableSets(SCIP *scip)
Definition: probdata_coloring.c:768
SCIP_Bool COLORprobEqualSortedArrays(int *array1nodes, int narray1nodes, int *array2nodes, int narray2nodes)
Definition: probdata_coloring.c:1346
SCIP_RETCODE SCIPtransformVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition: scip_var.c:1346
SCIP_RETCODE COLORprobSetUpArrayOfCons(SCIP *scip)
Definition: probdata_coloring.c:1296
static SCIP_DECL_PROBDELTRANS(probdeltransColoring)
Definition: probdata_coloring.c:550
SCIPallocBlockMemory(scip, subsol))
Definition: objbenders.h:33