80#define CONSHDLR_NAME "storeGraph"
81#define CONSHDLR_DESC "storing graph at nodes of the tree constraint handler"
82#define CONSHDLR_ENFOPRIORITY 0
83#define CONSHDLR_CHECKPRIORITY 2000000
84#define CONSHDLR_PROPFREQ 1
85#define CONSHDLR_EAGERFREQ 100
87#define CONSHDLR_DELAYPROP FALSE
88#define CONSHDLR_NEEDSCONS TRUE
90#define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
99 int* representativeofnode;
114struct SCIP_ConshdlrData
142 nnodes = tcliqueGetNNodes(graph);
145 if ( conshdlr ==
NULL )
155 consdata->graph = graph;
156 consdata->node1 = -1;
157 consdata->node2 = -1;
159 consdata->fathercons =
NULL;
160 consdata->propagatedvars = 0;
161 consdata->stickingatnode =
NULL;
162 consdata->created =
TRUE;
170 consdata->representativeofnode[
i] =
i;
171 consdata->nnodesinunion[
i] = 1;
173 consdata->unionofnode[
i][0] =
i;
188 SCIP_CALL(
SCIPcreateCons(
scip, cons, name, conshdlr, consdata,
FALSE,
FALSE,
FALSE,
FALSE,
FALSE,
199#ifdef SCIP_DISABLED_CODE
205#define conshdlrCopyStoreGraph NULL
249 conshdlrData->stack[0] = cons;
250 conshdlrData->nstack = 1;
268 assert(conshdlrData->nstack == 1);
270 conshdlrData->stack[0] =
NULL;
298 for (
i = tcliqueGetNNodes((*consdata)->graph)-1;
i >= 0;
i-- )
301 assert((*consdata)->nnodesinunion[
i] == 1);
310 if ((*consdata)->created)
312 for (
i = tcliqueGetNNodes((*consdata)->graph)-1;
i >= 0;
i-- )
314 if ( (*consdata)->nnodesinunion[
i] > 0 )
317 (*consdata)->unionofnode[
i] =
NULL;
324 (*consdata)->unionofnode =
NULL;
325 (*consdata)->representativeofnode =
NULL;
326 (*consdata)->nnodesinunion =
NULL;
328 if ((*consdata)->graph !=
NULL)
332 if ((*consdata)->cgraph !=
NULL)
435 (consdata->node1+1), (consdata->node2+1), conshdlrData->nstack+1);
438 if ( conshdlrData->nstack >= conshdlrData->maxstacksize )
442 SCIPdebugMessage(
"reallocating Memory for stack! %d --> %d\n", conshdlrData->maxstacksize, newsize);
445 conshdlrData->maxstacksize = newsize;
447 conshdlrData->stack[conshdlrData->nstack] = cons;
448 ++(conshdlrData->nstack);
451 if ( consdata->created ==
FALSE )
453 consdata->created =
TRUE;
456 || (consdata->node1 == olddata->representativeofnode[consdata->node1]
457 && consdata->node2 == olddata->representativeofnode[consdata->node2]));
458 nnodes = tcliqueGetNNodes(olddata->graph);
459 fathergraph = olddata->graph;
467 consdata->representativeofnode[
i] = olddata->representativeofnode[
i];
468 consdata->nnodesinunion[
i] = olddata->nnodesinunion[
i];
469 if ( consdata->nnodesinunion[
i] > 0 )
472 for ( j = 0; j < consdata->nnodesinunion[
i]; j++ )
474 consdata->unionofnode[
i][j] = olddata->unionofnode[
i][j];
497 while ( firstedge <= lastedge )
499 if ( *firstedge >
i )
517 assert(consdata->representativeofnode[consdata->node2] == consdata->node2);
518 assert(consdata->representativeofnode[consdata->node1] == consdata->node1);
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],
528 consdata->unionofnode[consdata->representativeofnode[consdata->node2]][
i])
550 for (
i = 0;
i < consdata->nnodesinunion[consdata->node2];
i++ )
553 consdata->representativeofnode[consdata->unionofnode[consdata->node2][
i]] = consdata->node1;
558 while ( firstedge <= lastedge )
560 if ( !tcliqueIsEdge(fathergraph, *firstedge, consdata->node2) )
562 if( !
tcliqueAddEdge(consdata->graph, consdata->unionofnode[consdata->node2][
i], *firstedge) )
573 for (
i = 0;
i < consdata->nnodesinunion[consdata->node1];
i++ )
578 while ( firstedge <= lastedge )
580 if ( !tcliqueIsEdge(fathergraph, *firstedge, consdata->node1) )
582 if( !
tcliqueAddEdge(consdata->graph, consdata->unionofnode[consdata->node1][
i], *firstedge) )
603 consdata->nnodesinunion[consdata->node1],
604 (consdata->nnodesinunion[consdata->node1]) + (consdata->nnodesinunion[consdata->node2])) );
605 for (
i = 0;
i < consdata->nnodesinunion[consdata->node2];
i ++ )
607 consdata->unionofnode[consdata->node1][consdata->nnodesinunion[consdata->node1]+
i]
608 = consdata->unionofnode[consdata->node2][
i];
611 consdata->nnodesinunion[consdata->node2]);
612 consdata->nnodesinunion[consdata->node1] =
613 (consdata->nnodesinunion[consdata->node1]) + (consdata->nnodesinunion[consdata->node2]);
614 consdata->nnodesinunion[consdata->node2] = 0;
615 consdata->unionofnode[consdata->node2] =
NULL;
661 assert(conshdlrData->nstack > 0);
662 assert(cons == conshdlrData->stack[conshdlrData->nstack-1]);
667 SCIPdebugMessage(
"Deactivating store graph constraint: <%s(%d,%d)> [stack size: %d].\n",
SCIPconsGetName(cons), (consdata->node1+1), (consdata->node2+1), conshdlrData->nstack-1);
671 --conshdlrData->nstack;
703 cons = conshdlrData->stack[conshdlrData->nstack-1];
711 for (
i = 0;
i < nsets;
i++ )
728 for (
i = 0;
i < nsets;
i++ )
743 SCIPdebugMessage(
"Finished propagation of store graph constraint <%s(%d,%d)>, %d vars fixed.\n",
SCIPconsGetName(cons), (consdata->node1+1), (consdata->node2+1), propcount);
767 conshdlrData->stack =
NULL;
768 conshdlrData->nstack = 0;
769 conshdlrData->maxstacksize = 25;
775 consEnfolpStoreGraph, consEnfopsStoreGraph, consCheckStoreGraph, consLockStoreGraph,
814 if ( conshdlr ==
NULL )
829 SCIPdebugMessage(
"Creating store graph constraint: <%s(%d,%d)>. \n", name, (node1+1), (node2+1));
831 consdata->node1 = node1;
832 consdata->node2 = node2;
833 consdata->type = type;
834 consdata->fathercons = fatherconstraint;
835 consdata->propagatedvars = 0;
836 consdata->stickingatnode = stickingnode;
837 consdata->created =
FALSE;
841 SCIP_CALL(
SCIPcreateCons(
scip, cons, name, conshdlr, consdata,
FALSE,
FALSE,
FALSE,
FALSE,
TRUE,
864 return conshdlrData->stack[conshdlrData->nstack-1];
878 if ( conshdlr ==
NULL )
886 assert(conshdlrData->nstack > 0);
888 return conshdlrData->stack[conshdlrData->nstack-1];
904 if ( conshdlr ==
NULL )
912 cons = conshdlrData->stack[conshdlrData->nstack-1];
916 return consdata->graph;
933 if ( conshdlr ==
NULL )
943 cons = conshdlrData->stack[conshdlrData->nstack-1];
947 return consdata->cgraph;
964 if ( conshdlr ==
NULL )
974 cons = conshdlrData->stack[conshdlrData->nstack-1];
976 return consdata->representativeofnode;
993 if ( conshdlr ==
NULL )
1003 cons = conshdlrData->stack[conshdlrData->nstack-1];
1007 assert(node >= 0 && node < tcliqueGetNNodes(consdata->graph));
1009 return consdata->representativeofnode[node];
1026 if ( conshdlr ==
NULL )
1036 cons = conshdlrData->stack[conshdlrData->nstack-1];
1040 *unions = consdata->unionofnode;
1041 *lengths = consdata->nnodesinunion;
1059 if ( conshdlr ==
NULL )
1067 cons = conshdlrData->stack[conshdlrData->nstack-1];
1071 *nodesinunion = consdata->unionofnode[node];
1072 *nnodesinunion = consdata->nnodesinunion[node];
1087 if ( conshdlr ==
NULL )
1097 *stack = conshdlrData->stack;
1098 *nstackelements = conshdlrData->nstack;
#define CONSHDLR_NEEDSCONS
#define CONSHDLR_CHECKPRIORITY
#define CONSHDLR_PROP_TIMING
#define CONSHDLR_PROPFREQ
#define CONSHDLR_EAGERFREQ
#define CONSHDLR_ENFOPRIORITY
#define CONSHDLR_DELAYPROP
Constraint handler for linear constraints in their most general form, .
int * COLORconsGetRepresentatives(SCIP *scip)
TCLIQUE_GRAPH * COLORconsGetCurrentGraph(SCIP *scip)
SCIP_RETCODE COLORcreateConsStoreGraph(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONS *fatherconstraint, COLOR_CONSTYPE type, int node1, int node2, SCIP_NODE *stickingnode)
void COLORconsGetUnions(SCIP *scip, int ***unions, int **lengths)
void COLORconsGetUnion(SCIP *scip, int **nodesinunion, int *nnodesinunion, int node)
SCIP_CONS * COLORconsGetActiveStoreGraphConsFromHandler(SCIP_CONSHDLR *conshdlr)
int COLORconsGetRepresentative(SCIP *scip, int node)
TCLIQUE_GRAPH * COLORconsGetComplementaryGraph(SCIP *scip)
SCIP_RETCODE COLORincludeConshdlrStoreGraph(SCIP *scip)
SCIP_CONS * COLORconsGetActiveStoreGraphCons(SCIP *scip)
static SCIP_RETCODE createConsStoreGraphAtRoot(SCIP *scip, SCIP_CONS **cons, const char *name, TCLIQUE_GRAPH *graph)
void COLORconsGetStack(SCIP *scip, SCIP_CONS ***stack, int *nstackelements)
constraint handler for storing the graph at each node of the tree
enum COLOR_ConsType COLOR_CONSTYPE
int SCIPgetNTotalVars(SCIP *scip)
SCIP_RETCODE SCIPdelConsLocal(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_RETCODE SCIPsetConshdlrActive(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)
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)
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_RETCODE SCIPsetConshdlrInitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_RETCODE SCIPsetConshdlrDeactive(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
SCIP_RETCODE SCIPsetConshdlrExitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
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)
const char * SCIPconsGetName(SCIP_CONS *cons)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPrepropagateNode(SCIP *scip, SCIP_NODE *node)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
assert(minobj< SCIPgetCutoffbound(scip))
SCIP_VAR * COLORprobGetVarForStableSet(SCIP *scip, int setindex)
void COLORprobGetStableSets(SCIP *scip, int ***stablesets, int **nelements, int *nstablesets)
SCIP_CONS * COLORprobGetConstraint(SCIP *scip, int node)
TCLIQUE_GRAPH * COLORprobGetGraph(SCIP *scip)
SCIP_RETCODE COLORprobGetComplementaryGraph(SCIP *scip, TCLIQUE_GRAPH *graph, TCLIQUE_GRAPH *cgraph)
SCIP_Bool COLORprobIsNodeInStableSet(SCIP *scip, int setindex, int node)
problem data for vertex coloring algorithm
file reader for vertex coloring instances
int * tcliqueGetLastAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
void tcliqueFree(TCLIQUE_GRAPH **tcliquegraph)
int * tcliqueGetFirstAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
TCLIQUE_Bool tcliqueFlush(TCLIQUE_GRAPH *tcliquegraph)
struct TCLIQUE_Graph TCLIQUE_GRAPH
TCLIQUE_Bool tcliqueCreate(TCLIQUE_GRAPH **tcliquegraph)
TCLIQUE_Bool tcliqueAddNode(TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight)
TCLIQUE_Bool tcliqueAddEdge(TCLIQUE_GRAPH *tcliquegraph, int node1, int node2)
type definitions for constraints and constraint handlers
#define SCIP_DECL_CONSENFOLP(x)
#define SCIP_DECL_CONSDELETE(x)
struct SCIP_Cons SCIP_CONS
#define SCIP_DECL_CONSINITSOL(x)
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
#define SCIP_DECL_CONSPROP(x)
#define SCIP_DECL_CONSACTIVE(x)
#define SCIP_DECL_CONSENFOPS(x)
#define SCIP_DECL_CONSDEACTIVE(x)
#define SCIP_DECL_CONSLOCK(x)
struct SCIP_Conshdlr SCIP_CONSHDLR
struct SCIP_ConsData SCIP_CONSDATA
#define SCIP_DECL_CONSCHECK(x)
#define SCIP_DECL_CONSEXITSOL(x)
#define SCIP_DECL_CONSFREE(x)
enum SCIP_Retcode SCIP_RETCODE
struct SCIP_Node SCIP_NODE