cons_storeGraph.c
Go to the documentation of this file.
20 * This file implements the constraints that are used for the branching in the coloring algorithm.
25 * First of all, it stores the type of the constraint ("same" or "differ", the root has type root)
30 * takes the graph of the constraint related to the branch-and-bound parent node of the current node and
35 * an edge between v and w. For a SAME(v,w) constraint, the original idea is to collapse the nodes v
36 * and w into one single vertex. Since this is not possible in the tclique-graph data structure, we
41 * This does of course not hold for sets created in a higher level of the branch-and-bound tree or
48 * The information about all fusions of nodes (caused by the SAME() operation) is stored, so that the nodes
49 * constituting a union can be accessed easily. Each union has a representative and a set of nodes, whereas
50 * each node knows the representative of the union it belongs to. At the beginning, each node forms its own
51 * union and therefore each node also represents this union, consisting of only this node. Later on, some
52 * nodes represent unions of several nodes, while other nodes are part of a union which they do not represent,
53 * so they have another node as representative. The representatives of the nodes are returned by the methods
54 * COLORconsGetRepresentative() / COLORconsGetRepresentatives(), the union represented by a node is returned
73 #define CONSHDLR_ENFOPRIORITY 0 /**< priority of the constraint handler for constraint enforcing */
74 #define CONSHDLR_CHECKPRIORITY 2000000 /**< priority of the constraint handler for checking feasibility */
75 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
76 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
78 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
79 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
90 int* representativeofnode; /* r...[i] = j if node j is representative of the union containing node i */
91 int** unionofnode; /* for all represantatives of a union an array with all the union's members */
95 COLOR_CONSTYPE type; /* type of the branching operation: COLOR_CONSTYPE_DIFFER oder COLOR_CONSTYPE_SAME */
96 int propagatedvars; /* number of Vars that existed, the last time, the related node was propagated,
179 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, FALSE, FALSE, FALSE, FALSE, FALSE,
192 /** We do not want to copy store graph constraints into subSCIPs since they just store information about
199 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
202 {
222 /** solving process initialization method of constraint handler (called when branch and bound process is about to begin) */
225 {
247 /** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
250 {
259 assert(conshdlrData->nstack == 1); /* at this point the stack should only have the root-constraint on it */
274 {
284 SCIPdebugMessage("Deleting store graph constraint: <%s(%d,%d)>.\n", SCIPconsGetName(cons), (*consdata)->node1+1, (*consdata)->node2+1);
291 SCIPfreeBlockMemoryArray(scip, &((*consdata)->unionofnode[i]), (*consdata)->nnodesinunion[i]); /*lint !e866*/
294 SCIPfreeBlockMemoryArray(scip, &((*consdata)->unionofnode), tcliqueGetNNodes((*consdata)->graph));
295 SCIPfreeBlockMemoryArray(scip, &((*consdata)->nnodesinunion), tcliqueGetNNodes((*consdata)->graph));
296 SCIPfreeBlockMemoryArray(scip, &((*consdata)->representativeofnode), tcliqueGetNNodes((*consdata)->graph));
307 SCIPfreeBlockMemoryArray(scip, &((*consdata)->unionofnode[i]), (*consdata)->nnodesinunion[i]); /*lint !e866*/
311 SCIPfreeBlockMemoryArray(scip, &((*consdata)->unionofnode), tcliqueGetNNodes((*consdata)->graph));
312 SCIPfreeBlockMemoryArray(scip, &((*consdata)->nnodesinunion), tcliqueGetNNodes((*consdata)->graph));
313 SCIPfreeBlockMemoryArray(scip, &((*consdata)->representativeofnode), tcliqueGetNNodes((*consdata)->graph));
338 {
354 {
370 {
386 {
401 {
425 SCIPdebugMessage("Activating store graph constraint: <%s(%d,%d)> [stack size: %d].\n", SCIPconsGetName(cons),
433 SCIPdebugMessage("reallocating Memory for stack! %d --> %d\n", conshdlrData->maxstacksize, newsize);
435 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(conshdlrData->stack), conshdlrData->maxstacksize, newsize) ); /*lint !e715 !e647*/
462 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(consdata->unionofnode[i]), consdata->nnodesinunion[i]) ); /*lint !e866*/
514 for ( i = 0; i < consdata->nnodesinunion[consdata->representativeofnode[consdata->node2]]; i++ )
516 for ( j = 0; j < consdata->nnodesinunion[consdata->representativeofnode[consdata->node1]]; j++ )
518 if( !tcliqueAddEdge(consdata->graph, consdata->unionofnode[consdata->representativeofnode[consdata->node1]][j],
534 /* type == COLOR_CONSTYPE_SAME --> insert edge (node2, i) - if not yet existing - if there exists an edge (node1, i) and vice versa */
595 (consdata->nnodesinunion[consdata->node1]) + (consdata->nnodesinunion[consdata->node2])) ); /*lint !e866*/
621 if ( (consdata->type != COLOR_CONSTYPE_ROOT) && (consdata->propagatedvars < SCIPgetNTotalVars(scip)) )
635 {
655 SCIPdebugMessage("Deactivating store graph constraint: <%s(%d,%d)> [stack size: %d].\n", SCIPconsGetName(cons), (consdata->node1+1), (consdata->node2+1), conshdlrData->nstack-1);
669 {
694 SCIPdebugMessage( "Starting propagation of store graph constraint <%s(%d,%d)> .\n", SCIPconsGetName(cons), (consdata->node1+1), (consdata->node2+1));
696 /* propagation for differ: set upper bound to 0 for all stable sets, which contain both nodes */
703 if ( COLORprobIsNodeInStableSet(scip, i, consdata->node1) && COLORprobIsNodeInStableSet(scip, i, consdata->node2) )
713 /* propagation for same: set upper bound to 0 for all stable sets, which do not contain both nodes */
720 if ( (COLORprobIsNodeInStableSet(scip, i, consdata->node1) || COLORprobIsNodeInStableSet(scip, i, consdata->node2))
721 && !(COLORprobIsNodeInStableSet(scip, i, consdata->node1) && COLORprobIsNodeInStableSet(scip, i, consdata->node2)) )
731 SCIPdebugMessage( "Finished propagation of store graph constraint <%s(%d,%d)>, %d vars fixed.\n", SCIPconsGetName(cons), (consdata->node1+1), (consdata->node2+1), propcount);
773 SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropStoreGraph, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP,
785 COLOR_CONSTYPE type, /**< type of the constraint: COLOR_CONSTYPE_SAME or COLOR_CONSTYPE_DIFFER */
817 SCIPdebugMessage("Creating store graph constraint: <%s(%d,%d)>. \n", name, (node1+1), (node2+1));
829 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, FALSE, FALSE, FALSE, FALSE, TRUE,
840 /** returns the store graph constraint of the current node, needs the pointer to the constraint handler */
1000 /** returns the array of all unions, a union is saved in the array at the position of its representative */
SCIP_CONS * COLORconsGetActiveStoreGraphConsFromHandler(SCIP_CONSHDLR *conshdlr)
Definition: cons_storeGraph.c:842
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:86
Definition: cons_storeGraph.h:73
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:877
void COLORconsGetStack(SCIP *scip, SCIP_CONS ***stack, int *nstackelements)
Definition: cons_storeGraph.c:1065
SCIP_RETCODE SCIPsetConshdlrExitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITSOL((*consexitsol)))
Definition: scip_cons.c:453
SCIP_EXPORT TCLIQUE_Bool tcliqueFlush(TCLIQUE_GRAPH *tcliquegraph)
Definition: tclique_graph.c:408
Definition: struct_scip.h:59
SCIP_RETCODE SCIPcreateCons(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONSHDLR *conshdlr, SCIP_CONSDATA *consdata, 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: scip_cons.c:934
SCIP_EXPORT TCLIQUE_Bool tcliqueAddEdge(TCLIQUE_GRAPH *tcliquegraph, int node1, int node2)
Definition: tclique_graph.c:371
problem data for vertex coloring algorithm
SCIP_RETCODE SCIPincludeConshdlrBasic(SCIP *scip, SCIP_CONSHDLR **conshdlrptr, const char *name, const char *desc, int enfopriority, int chckpriority, int eagerfreq, SCIP_Bool needscons, SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_CONSHDLRDATA *conshdlrdata)
Definition: scip_cons.c:166
SCIP_RETCODE SCIPsetConshdlrActive(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSACTIVE((*consactive)))
Definition: scip_cons.c:655
SCIP_CONS * COLORconsGetActiveStoreGraphCons(SCIP *scip)
Definition: cons_storeGraph.c:858
SCIP_RETCODE COLORincludeConshdlrStoreGraph(SCIP *scip)
Definition: cons_storeGraph.c:746
static SCIP_RETCODE createConsStoreGraphAtRoot(SCIP *scip, SCIP_CONS **cons, const char *name, TCLIQUE_GRAPH *graph)
Definition: cons_storeGraph.c:120
Definition: struct_var.h:198
static SCIP_DECL_CONSEXITSOL(consExitsolStoreGraph)
Definition: cons_storeGraph.c:250
SCIP_EXPORT int * tcliqueGetFirstAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
Definition: tclique_graph.c:792
Definition: cons_storeGraph.h:72
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
Definition: scip_cons.c:563
file reader for vertex coloring instances
void COLORprobGetStableSets(SCIP *scip, int ***stablesets, int **nelements, int *nstablesets)
Definition: probdata_coloring.c:1042
tclique user interface
constraint handler for storing the graph at each node of the tree
static SCIP_DECL_CONSDELETE(consDeleteStoreGraph)
Definition: cons_storeGraph.c:274
Definition: struct_tree.h:132
SCIP_EXPORT TCLIQUE_Bool tcliqueAddNode(TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight)
Definition: tclique_graph.c:331
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:357
Definition: type_result.h:35
Definition: struct_cons.h:37
int COLORconsGetRepresentative(SCIP *scip, int node)
Definition: cons_storeGraph.c:969
Definition: struct_cons.h:117
SCIP_RETCODE SCIPsetConshdlrInitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITSOL((*consinitsol)))
Definition: scip_cons.c:429
Definition: type_result.h:36
Definition: type_retcode.h:33
SCIP_VAR * COLORprobGetVarForStableSet(SCIP *scip, int setindex)
Definition: probdata_coloring.c:847
Definition: type_retcode.h:34
void COLORconsGetUnion(SCIP *scip, int **nodesinunion, int *nnodesinunion, int node)
Definition: cons_storeGraph.c:1034
SCIP_EXPORT void tcliqueFree(TCLIQUE_GRAPH **tcliquegraph)
Definition: tclique_graph.c:202
SCIP_Bool COLORprobIsNodeInStableSet(SCIP *scip, int setindex, int node)
Definition: probdata_coloring.c:864
SCIP_RETCODE COLORprobGetComplementaryGraph(SCIP *scip, TCLIQUE_GRAPH *graph, TCLIQUE_GRAPH *cgraph)
Definition: probdata_coloring.c:1213
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4187
static SCIP_DECL_CONSDEACTIVE(consDeactiveStoreGraph)
Definition: cons_storeGraph.c:635
static SCIP_DECL_CONSENFOLP(consEnfolpStoreGraph)
Definition: cons_storeGraph.c:338
static SCIP_DECL_CONSINITSOL(consInitsolStoreGraph)
Definition: cons_storeGraph.c:225
int * COLORconsGetRepresentatives(SCIP *scip)
Definition: cons_storeGraph.c:941
Constraint handler for linear constraints in their most general form, .
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4767
TCLIQUE_GRAPH * COLORconsGetComplementaryGraph(SCIP *scip)
Definition: cons_storeGraph.c:910
SCIP_RETCODE SCIPsetConshdlrDeactive(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDEACTIVE((*consdeactive)))
Definition: scip_cons.c:678
static SCIP_DECL_CONSENFOPS(consEnfopsStoreGraph)
Definition: cons_storeGraph.c:354
SCIP_RETCODE SCIPrepropagateNode(SCIP *scip, SCIP_NODE *node)
Definition: scip_tree.c:445
Definition: type_retcode.h:45
SCIP_RETCODE COLORcreateConsStoreGraph(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONS *fatherconstraint, COLOR_CONSTYPE type, int node1, int node2, SCIP_NODE *stickingnode)
Definition: cons_storeGraph.c:781
Definition: cons_storeGraph.h:74
void COLORconsGetUnions(SCIP *scip, int ***unions, int **lengths)
Definition: cons_storeGraph.c:1002
TCLIQUE_GRAPH * COLORconsGetCurrentGraph(SCIP *scip)
Definition: cons_storeGraph.c:882
SCIP_EXPORT int * tcliqueGetLastAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
Definition: tclique_graph.c:816
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
Definition: objbenders.h:33
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)
Definition: scip_cons.c:266
static SCIP_DECL_CONSACTIVE(consActiveStoreGraph)
Definition: cons_storeGraph.c:401
SCIP_EXPORT TCLIQUE_Bool tcliqueCreate(TCLIQUE_GRAPH **tcliquegraph)
Definition: tclique_graph.c:176
type definitions for constraints and constraint handlers