cons_storeGraph.c
Go to the documentation of this file.
29 * This file implements the constraints that are used for the branching in the coloring algorithm.
34 * First of all, it stores the type of the constraint ("same" or "differ", the root has type root)
39 * takes the graph of the constraint related to the branch-and-bound parent node of the current node and
44 * an edge between v and w. For a SAME(v,w) constraint, the original idea is to collapse the nodes v
45 * and w into one single vertex. Since this is not possible in the tclique-graph data structure, we
50 * This does of course not hold for sets created in a higher level of the branch-and-bound tree or
57 * The information about all fusions of nodes (caused by the SAME() operation) is stored, so that the nodes
58 * constituting a union can be accessed easily. Each union has a representative and a set of nodes, whereas
59 * each node knows the representative of the union it belongs to. At the beginning, each node forms its own
60 * union and therefore each node also represents this union, consisting of only this node. Later on, some
61 * nodes represent unions of several nodes, while other nodes are part of a union which they do not represent,
62 * so they have another node as representative. The representatives of the nodes are returned by the methods
63 * COLORconsGetRepresentative() / COLORconsGetRepresentatives(), the union represented by a node is returned
82#define CONSHDLR_ENFOPRIORITY 0 /**< priority of the constraint handler for constraint enforcing */
83#define CONSHDLR_CHECKPRIORITY 2000000 /**< priority of the constraint handler for checking feasibility */
84#define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
85#define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
87#define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
88#define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
99 int* representativeofnode; /* r...[i] = j if node j is representative of the union containing node i */
100 int** unionofnode; /* for all represantatives of a union an array with all the union's members */
104 COLOR_CONSTYPE type; /* type of the branching operation: COLOR_CONSTYPE_DIFFER oder COLOR_CONSTYPE_SAME */
105 int propagatedvars; /* number of Vars that existed, the last time, the related node was propagated,
188 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, FALSE, FALSE, FALSE, FALSE, FALSE,
201/** We do not want to copy store graph constraints into subSCIPs since they just store information about
208/** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
231/** solving process initialization method of constraint handler (called when branch and bound process is about to begin) */
256/** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
268 assert(conshdlrData->nstack == 1); /* at this point the stack should only have the root-constraint on it */
293 SCIPdebugMessage("Deleting store graph constraint: <%s(%d,%d)>.\n", SCIPconsGetName(cons), (*consdata)->node1+1, (*consdata)->node2+1);
300 SCIPfreeBlockMemoryArray(scip, &((*consdata)->unionofnode[i]), (*consdata)->nnodesinunion[i]); /*lint !e866*/
303 SCIPfreeBlockMemoryArray(scip, &((*consdata)->unionofnode), tcliqueGetNNodes((*consdata)->graph));
304 SCIPfreeBlockMemoryArray(scip, &((*consdata)->nnodesinunion), tcliqueGetNNodes((*consdata)->graph));
305 SCIPfreeBlockMemoryArray(scip, &((*consdata)->representativeofnode), tcliqueGetNNodes((*consdata)->graph));
316 SCIPfreeBlockMemoryArray(scip, &((*consdata)->unionofnode[i]), (*consdata)->nnodesinunion[i]); /*lint !e866*/
320 SCIPfreeBlockMemoryArray(scip, &((*consdata)->unionofnode), tcliqueGetNNodes((*consdata)->graph));
321 SCIPfreeBlockMemoryArray(scip, &((*consdata)->nnodesinunion), tcliqueGetNNodes((*consdata)->graph));
322 SCIPfreeBlockMemoryArray(scip, &((*consdata)->representativeofnode), tcliqueGetNNodes((*consdata)->graph));
434 SCIPdebugMessage("Activating store graph constraint: <%s(%d,%d)> [stack size: %d].\n", SCIPconsGetName(cons),
442 SCIPdebugMessage("reallocating Memory for stack! %d --> %d\n", conshdlrData->maxstacksize, newsize);
444 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(conshdlrData->stack), conshdlrData->maxstacksize, newsize) ); /*lint !e715 !e647*/
471 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(consdata->unionofnode[i]), consdata->nnodesinunion[i]) ); /*lint !e866*/
523 for ( i = 0; i < consdata->nnodesinunion[consdata->representativeofnode[consdata->node2]]; i++ )
525 for ( j = 0; j < consdata->nnodesinunion[consdata->representativeofnode[consdata->node1]]; j++ )
527 if( !tcliqueAddEdge(consdata->graph, consdata->unionofnode[consdata->representativeofnode[consdata->node1]][j],
543 /* type == COLOR_CONSTYPE_SAME --> insert edge (node2, i) - if not yet existing - if there exists an edge (node1, i) and vice versa */
604 (consdata->nnodesinunion[consdata->node1]) + (consdata->nnodesinunion[consdata->node2])) ); /*lint !e866*/
617 /* the constraint associated to node2 can be removed from this branch-and-bound node and its subtree */
633 if ( (consdata->type != COLOR_CONSTYPE_ROOT) && (consdata->propagatedvars < SCIPgetNTotalVars(scip)) )
667 SCIPdebugMessage("Deactivating store graph constraint: <%s(%d,%d)> [stack size: %d].\n", SCIPconsGetName(cons), (consdata->node1+1), (consdata->node2+1), conshdlrData->nstack-1);
706 SCIPdebugMessage( "Starting propagation of store graph constraint <%s(%d,%d)> .\n", SCIPconsGetName(cons), (consdata->node1+1), (consdata->node2+1));
708 /* propagation for differ: set upper bound to 0 for all stable sets, which contain both nodes */
715 if ( COLORprobIsNodeInStableSet(scip, i, consdata->node1) && COLORprobIsNodeInStableSet(scip, i, consdata->node2) )
725 /* propagation for same: set upper bound to 0 for all stable sets, which do not contain both nodes */
732 if ( (COLORprobIsNodeInStableSet(scip, i, consdata->node1) || COLORprobIsNodeInStableSet(scip, i, consdata->node2))
733 && !(COLORprobIsNodeInStableSet(scip, i, consdata->node1) && COLORprobIsNodeInStableSet(scip, i, consdata->node2)) )
743 SCIPdebugMessage( "Finished propagation of store graph constraint <%s(%d,%d)>, %d vars fixed.\n", SCIPconsGetName(cons), (consdata->node1+1), (consdata->node2+1), propcount);
785 SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropStoreGraph, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP,
797 COLOR_CONSTYPE type, /**< type of the constraint: COLOR_CONSTYPE_SAME or COLOR_CONSTYPE_DIFFER */
829 SCIPdebugMessage("Creating store graph constraint: <%s(%d,%d)>. \n", name, (node1+1), (node2+1));
841 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, FALSE, FALSE, FALSE, FALSE, TRUE,
852/** returns the store graph constraint of the current node, needs the pointer to the constraint handler */
1012/** returns the array of all unions, a union is saved in the array at the position of its representative */
Constraint handler for linear constraints in their most general form, .
int * COLORconsGetRepresentatives(SCIP *scip)
Definition: cons_storeGraph.c:952
TCLIQUE_GRAPH * COLORconsGetCurrentGraph(SCIP *scip)
Definition: cons_storeGraph.c:893
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:792
static SCIP_DECL_CONSENFOPS(consEnfopsStoreGraph)
Definition: cons_storeGraph.c:362
void COLORconsGetUnions(SCIP *scip, int ***unions, int **lengths)
Definition: cons_storeGraph.c:1013
static SCIP_DECL_CONSEXITSOL(consExitsolStoreGraph)
Definition: cons_storeGraph.c:258
void COLORconsGetUnion(SCIP *scip, int **nodesinunion, int *nnodesinunion, int node)
Definition: cons_storeGraph.c:1045
SCIP_CONS * COLORconsGetActiveStoreGraphConsFromHandler(SCIP_CONSHDLR *conshdlr)
Definition: cons_storeGraph.c:853
int COLORconsGetRepresentative(SCIP *scip, int node)
Definition: cons_storeGraph.c:980
static SCIP_DECL_CONSDELETE(consDeleteStoreGraph)
Definition: cons_storeGraph.c:282
static SCIP_DECL_CONSACTIVE(consActiveStoreGraph)
Definition: cons_storeGraph.c:409
TCLIQUE_GRAPH * COLORconsGetComplementaryGraph(SCIP *scip)
Definition: cons_storeGraph.c:921
SCIP_RETCODE COLORincludeConshdlrStoreGraph(SCIP *scip)
Definition: cons_storeGraph.c:757
static SCIP_DECL_CONSINITSOL(consInitsolStoreGraph)
Definition: cons_storeGraph.c:233
static SCIP_DECL_CONSDEACTIVE(consDeactiveStoreGraph)
Definition: cons_storeGraph.c:646
static SCIP_DECL_CONSENFOLP(consEnfolpStoreGraph)
Definition: cons_storeGraph.c:346
SCIP_CONS * COLORconsGetActiveStoreGraphCons(SCIP *scip)
Definition: cons_storeGraph.c:869
static SCIP_RETCODE createConsStoreGraphAtRoot(SCIP *scip, SCIP_CONS **cons, const char *name, TCLIQUE_GRAPH *graph)
Definition: cons_storeGraph.c:128
void COLORconsGetStack(SCIP *scip, SCIP_CONS ***stack, int *nstackelements)
Definition: cons_storeGraph.c:1076
constraint handler for storing the graph at each node of the tree
SCIP_RETCODE SCIPdelConsLocal(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:3474
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)
Definition: scip_cons.c:281
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:181
SCIP_RETCODE SCIPsetConshdlrDeactive(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDEACTIVE((*consdeactive)))
Definition: scip_cons.c:693
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
Definition: scip_cons.c:578
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:372
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:941
SCIP_RETCODE SCIPsetConshdlrExitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITSOL((*consexitsol)))
Definition: scip_cons.c:468
SCIP_RETCODE SCIPsetConshdlrInitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITSOL((*consinitsol)))
Definition: scip_cons.c:444
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4217
SCIP_RETCODE SCIPsetConshdlrActive(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSACTIVE((*consactive)))
Definition: scip_cons.c:670
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:998
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1174
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
SCIP_RETCODE SCIPrepropagateNode(SCIP *scip, SCIP_NODE *node)
Definition: scip_tree.c:477
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4766
Definition: objbenders.h:44
SCIP_VAR * COLORprobGetVarForStableSet(SCIP *scip, int setindex)
Definition: probdata_coloring.c:856
void COLORprobGetStableSets(SCIP *scip, int ***stablesets, int **nelements, int *nstablesets)
Definition: probdata_coloring.c:1051
SCIP_CONS * COLORprobGetConstraint(SCIP *scip, int node)
Definition: probdata_coloring.c:1205
SCIP_RETCODE COLORprobGetComplementaryGraph(SCIP *scip, TCLIQUE_GRAPH *graph, TCLIQUE_GRAPH *cgraph)
Definition: probdata_coloring.c:1222
SCIP_Bool COLORprobIsNodeInStableSet(SCIP *scip, int setindex, int node)
Definition: probdata_coloring.c:873
problem data for vertex coloring algorithm
file reader for vertex coloring instances
Definition: struct_cons.h:47
Definition: struct_cons.h:127
Definition: struct_tree.h:142
Definition: struct_var.h:208
Definition: struct_scip.h:70
tclique user interface
int * tcliqueGetLastAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
Definition: tclique_graph.c:829
int * tcliqueGetFirstAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
Definition: tclique_graph.c:805
TCLIQUE_Bool tcliqueCreate(TCLIQUE_GRAPH **tcliquegraph)
Definition: tclique_graph.c:185
TCLIQUE_Bool tcliqueAddNode(TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight)
Definition: tclique_graph.c:340
TCLIQUE_Bool tcliqueAddEdge(TCLIQUE_GRAPH *tcliquegraph, int node1, int node2)
Definition: tclique_graph.c:380
type definitions for constraints and constraint handlers