54#define EVENTHDLR_NAME "probdatavardeleted"
55#define EVENTHDLR_DESC "event handler for variable deleted event"
65 int* stablesetlengths;
115 int nnodesdeleteddegreethisround;
116 int nnodesdeletedneighbourthisround;
127 printf(
"\npreprocessing...\n");
138 if( !
tcliqueAddNode(currgraph, tcliqueGetNNodes(probdata->oldgraph)-1, 0) )
144 for (
i = 0;
i < tcliqueGetNNodes(probdata->oldgraph);
i++ )
149 while ( firstedge <= lastedge )
151 if ( *firstedge >
i )
169 currnnodes = tcliqueGetNNodes(probdata->oldgraph);
178 for (
i = 0;
i < currnnodes;
i++ )
183 probdata->new2oldnode[
i] =
i;
188 &nmaxcliquenodes, &maxcliqueweight, 0, 0, 50000, 0, INT_MAX, -1,
NULL, &status);
190 printf(
"size of the maximum clique: %d%c \n", nmaxcliquenodes, opt);
193 nnodesdeleteddegreethisround = 1;
194 nnodesdeletedneighbourthisround = 1;
198 while ( (nnodesdeleteddegreethisround > 0) || (nnodesdeletedneighbourthisround > 0) )
201 nnodesdeleteddegreethisround = 0;
202 nnodesdeletedneighbourthisround = 0;
206 while ( changed ==
TRUE )
211 for (
i = 0;
i < currnnodes;
i++)
214 if ( (degrees[
i] < nmaxcliquenodes )
217 probdata->deletednodes[ndeletednodes] = probdata->new2oldnode[
i];
219 nnodesdeleteddegreethisround++;
225 newnodes[actnewnode] = probdata->new2oldnode[
i];
251 for (
i = 0;
i < actnewnode;
i++ )
256 while ( firstedge <= lastedge )
260 for ( j =
i+1; j < actnewnode; j++ )
262 if ( *firstedge == newnodes[j] )
284 currnnodes = tcliqueGetNNodes(currgraph);
286 for (
i = 0;
i < actnewnode;
i++ )
288 probdata->new2oldnode[
i] = newnodes[
i];
293 probdata->new2oldnode[
i] = -1;
301 while ( changed ==
TRUE )
306 for (
i = 0;
i < currnnodes;
i++ )
314 for ( j = 0; j < currnnodes; j++ )
318 if ( (j !=
i) && !tcliqueIsEdge(currgraph,
i, j)
327 while ( firstedge <= lastedge )
330 if ( !tcliqueIsEdge(currgraph, j, *firstedge) )
339 probdata->deletednodes[ndeletednodes] = probdata->new2oldnode[
i];
342 nnodesdeletedneighbourthisround++;
350 if ( ndeletednodes == 0 || probdata->deletednodes[ndeletednodes-1] != probdata->new2oldnode[
i])
352 newnodes[actnewnode] = probdata->new2oldnode[
i];
360 newnodes[actnewnode] = probdata->new2oldnode[
i];
386 for (
i = 0;
i < actnewnode;
i++ )
391 while ( firstedge <= lastedge )
395 for ( j =
i+1; j < actnewnode; j++ )
397 if ( *firstedge == newnodes[j] )
419 currnnodes = tcliqueGetNNodes(currgraph);
422 for (
i = 0;
i < actnewnode;
i++ )
424 probdata->new2oldnode[
i] = newnodes[
i];
430 probdata->new2oldnode[
i] = -1;
435 printf(
"Round %d of preprocessing:\n", myround);
436 printf(
" deleted low degree vertices: %d\n", nnodesdeleteddegreethisround);
437 printf(
" deleted almost cliques: %d\n", nnodesdeletedneighbourthisround);
443 probdata->deletednodes[
i] = -1;
446 printf(
"preprocessing overall deleted vertices: %d\n\n", ndeletednodes);
448 probdata->graph = currgraph;
485 (*targetdata)->maxstablesets = sourcedata->maxstablesets;
486 (*targetdata)->nstablesets = sourcedata->nstablesets;
487 (*targetdata)->oldgraph = sourcedata->oldgraph;
496 for (
i = 0;
i < tcliqueGetNNodes(sourcedata->oldgraph);
i++ )
498 (*targetdata)->deletednodes[
i] = sourcedata->deletednodes[
i];
499 (*targetdata)->new2oldnode[
i] = sourcedata->new2oldnode[
i];
503 for (
i = 0;
i < sourcedata->nstablesets;
i++ )
506 (*targetdata)->stablesetlengths[
i] = sourcedata->stablesetlengths[
i];
509 for ( j = 0; j <sourcedata->stablesetlengths[
i]; j++ )
511 (*targetdata)->stablesets[
i][j] = sourcedata->stablesets[
i][j];
516 (*targetdata)->constraintssize = tcliqueGetNNodes(sourcedata->graph);
520 (*targetdata)->constraints) );
522 if( !
tcliqueAddNode((*targetdata)->graph, tcliqueGetNNodes(sourcedata->graph)-1, 0) )
528 for (
i = 0;
i < tcliqueGetNNodes(sourcedata->graph);
i++ )
533 while ( firstedge <= lastedge )
535 if ( *firstedge >
i )
567 for (
i = 0;
i < tcliqueGetNNodes((*probdata)->graph);
i++)
574 for (
i = (*probdata)->nstablesets-1;
i >= 0;
i-- )
602 for (
i = (*probdata)->nstablesets-1;
i >= 0;
i-- )
612 for (
i = 0;
i < tcliqueGetNNodes((*probdata)->graph);
i++ )
653 assert(probdata->stablesetvars[idx] ==
var);
660 for( ; idx < probdata->nstablesets - 1; idx++)
662 probdata->stablesets[idx] = probdata->stablesets[idx + 1];
663 probdata->stablesetlengths[idx] = probdata->stablesetlengths[idx + 1];
664 probdata->stablesetvars[idx] = probdata->stablesetvars[idx + 1];
668 probdata->nstablesets--;
694 printf(
"Creating problem: %s \n", name);
715 for (
i = 0;
i < nedges;
i++ )
734 probdata->constraintssize =
nnodes;
742 probdata->maxstablesets = 2;
743 probdata->nstablesets = 0;
747 eventExecProbdatavardeleted,
NULL) );
772 return probdata->nstablesets;
789 for (
i = 0;
i < probdata->nstablesets;
i++ )
791 printf(
"Set %d: ",
i);
792 for ( j = 0; j < probdata->stablesetlengths[
i]; j++ )
794 printf(
"%d, ", probdata->stablesets[
i][j]+1);
818 printf(
"Set %d: ",
i);
819 for ( j = 0; j < probdata->stablesetlengths[
i]; j++ )
821 printf(
"%d, ", probdata->stablesets[
i][j]+1);
823 if ( probdata->stablesetvars[
i] !=
NULL )
843 assert((setindex >= 0) && (setindex < probdata->nstablesets));
849 probdata->stablesetvars[setindex] =
var;
866 assert ( (setindex >= 0) && (setindex < probdata->nstablesets));
868 return probdata->stablesetvars[setindex];
889 u = probdata->stablesetlengths[setindex]-1;
893 if ( probdata->stablesets[setindex][m] == node )
897 if ( probdata->stablesets[setindex][m] > node )
901 if ( probdata->stablesets[setindex][m] < node )
924 assert(nset1nodes > 0 && nset2nodes > 0);
926 if ( nset1nodes != nset2nodes )
930 for (
i = 0;
i < nset1nodes;
i++ )
932 if ( set1[
i] != set2[
i] )
965 probdata->stablesets[
i],
966 probdata->stablesetlengths[
i]) )
996 for (
i = 0;
i < nstablesetnodes-2;
i++ )
998 assert(stablesetnodes[
i]>stablesetnodes[
i+1]);
1003 if ( (probdata->nstablesets + 1) > probdata->maxstablesets)
1006 assert(newsize > probdata->nstablesets + 1);
1010 SCIPdebugMessage(
"Set-array resized: %d --> %d\n", probdata->maxstablesets, newsize);
1011 probdata->maxstablesets = newsize;
1016 probdata->stablesetlengths[probdata->nstablesets] = nstablesetnodes;
1017 probdata->stablesetvars[probdata->nstablesets] =
NULL;
1018 for (
i = 0;
i < nstablesetnodes;
i++ )
1020 assert(stablesetnodes[
i] >= 0);
1021 probdata->stablesets[probdata->nstablesets][
i] = stablesetnodes[
i];
1023 *setindex = probdata->nstablesets;
1025 probdata->nstablesets++;
1045 *stableset = probdata->stablesets[setindex];
1046 *nelements = probdata->stablesetlengths[setindex];
1064 *stablesets = probdata->stablesets;
1065 *nelements = probdata->stablesetlengths;
1066 *nstablesets = probdata->nstablesets;
1081 return tcliqueGetNNodes(probdata->graph);
1096 return tcliqueGetNNodes(probdata->oldgraph);
1112 return probdata->graph;
1127 return probdata->oldgraph;
1142 return probdata->deletednodes;
1157 return probdata->new2oldnode;
1179 if ( probdata->new2oldnode[
i] == node )
1181 if ( probdata->new2oldnode[
i] == -1 )
1200 return probdata->constraints;
1215 assert(node >= 0 && node < tcliqueGetNNodes(probdata->graph));
1217 return probdata->constraints[node];
1239 nnodes = tcliqueGetNNodes(graph);
1255 for ( j = 0; j < *firstedge && j <
i; j++ )
1263 while ( firstedge < lastedge )
1265 for ( j = *firstedge+1; j < *(firstedge+1) && j <
i; j++ )
1295 assert((tcliqueIsEdge(graph,
i, j) && !tcliqueIsEdge(cgraph,
i, j))
1296 || (!tcliqueIsEdge(graph,
i, j) && tcliqueIsEdge(cgraph,
i, j)));
1325 SCIP_CALL(
SCIPcreateConsSetcover(
scip, &constraints[
i], consname, 0,
NULL,
TRUE,
TRUE,
TRUE,
TRUE,
TRUE,
FALSE,
TRUE,
TRUE,
FALSE,
FALSE) );
1344 for (
i = 0;
i < narraynodes;
i++ )
1346 if ( arraynodes[
i] == node )
1365 assert(narray1nodes > 0);
1367 assert(narray2nodes > 0);
1369 if ( narray1nodes != narray2nodes )
1373 for (
i = 0;
i < narray1nodes;
i++ )
1375 if ( array1nodes[
i] != array2nodes[
i] )
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)
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
SCIP_PROBDATA * SCIPgetProbData(SCIP *scip)
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)
SCIP_RETCODE SCIPtransformConss(SCIP *scip, int nconss, SCIP_CONS **conss, SCIP_CONS **transconss)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
SCIP_EVENTHDLR * SCIPfindEventhdlr(SCIP *scip, const char *name)
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
SCIP_VAR * SCIPeventGetVar(SCIP_EVENT *event)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
void SCIPvarSetData(SCIP_VAR *var, SCIP_VARDATA *vardata)
SCIP_VARDATA * SCIPvarGetData(SCIP_VAR *var)
SCIP_RETCODE SCIPtransformVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
SCIP_Bool SCIPvarIsInLP(SCIP_VAR *var)
void SCIPsortDownInt(int *intarray, int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
assert(minobj< SCIPgetCutoffbound(scip))
SCIP_RETCODE SCIPcreateProbColoring(SCIP *scip, const char *name, int nnodes, int nedges, int **edges)
void COLORprobPrintStableSets(SCIP *scip)
void COLORprobGetStableSet(SCIP *scip, int setindex, int **stableset, int *nelements)
static SCIP_RETCODE preprocessGraph(SCIP *scip)
SCIP_Bool COLORprobIsNodeInArray(int node, int *arraynodes, int narraynodes)
int COLORprobGetNewNodeForOriginalNode(SCIP *scip, int node)
TCLIQUE_GRAPH * COLORprobGetOriginalGraph(SCIP *scip)
SCIP_CONS ** COLORprobGetConstraints(SCIP *scip)
SCIP_RETCODE COLORprobAddNewStableSet(SCIP *scip, int *stablesetnodes, int nstablesetnodes, int *setindex)
int * COLORprobGetOriginalNodesForNewNodes(SCIP *scip)
SCIP_RETCODE COLORprobSetUpArrayOfCons(SCIP *scip)
int COLORprobGetNNodes(SCIP *scip)
int COLORprobGetOriginalNNodes(SCIP *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)
void COLORprobPrintStableSet(SCIP *scip, int setnumber)
SCIP_Bool COLORprobStableSetIsNew(SCIP *scip, int *stablesetnodes, int nstablesetnodes)
SCIP_Bool COLORprobStableSetsAreEqual(SCIP *scip, int *set1, int nset1nodes, int *set2, int nset2nodes)
SCIP_Bool COLORprobEqualSortedArrays(int *array1nodes, int narray1nodes, int *array2nodes, int narray2nodes)
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)
SCIP_RETCODE COLORprobAddVarForStableSet(SCIP *scip, int setindex, SCIP_VAR *var)
int COLORprobGetNStableSets(SCIP *scip)
int * COLORprobGetDeletedNodes(SCIP *scip)
problem data for vertex coloring algorithm
int * tcliqueGetLastAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
void tcliqueChangeWeight(TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight)
int * tcliqueGetDegrees(TCLIQUE_GRAPH *tcliquegraph)
void tcliqueFree(TCLIQUE_GRAPH **tcliquegraph)
enum TCLIQUE_Status TCLIQUE_STATUS
int * tcliqueGetFirstAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
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)
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)
struct SCIP_EventData SCIP_EVENTDATA
#define SCIP_EVENTTYPE_VARDELETED
#define SCIP_DECL_EVENTEXEC(x)
#define SCIP_DECL_PROBDELTRANS(x)
struct SCIP_ProbData SCIP_PROBDATA
#define SCIP_DECL_PROBDELORIG(x)
#define SCIP_DECL_PROBTRANS(x)
enum SCIP_Retcode SCIP_RETCODE
struct SCIP_VarData SCIP_VARDATA