59 SCIP_Real** solclustering,
68 for(
i = 0;
i < nbins; ++
i )
72 for( j = 0; j < ncluster; ++j )
77 sum += solclustering[
i][j];
91 SCIP_Real** clustering,
106 assert(nbins > 0 && ncluster > 0);
110 for (
c = 0;
c < ncluster; ++
c )
113 for (
i = 0;
i < nbins; ++
i )
115 if(
NULL != binvars[
i][
c] )
135 for(
i = 0;
i < nbins; ++
i )
137 for( j = 0; j <
i; ++j )
139 if(
NULL == edgevars[
i][j] ||
NULL == edgevars[j][
i])
145 var = edgevars[
i][j][0];
156 var = edgevars[
i][j][1];
166 var = edgevars[j][
i][1];
186 assert(k < ncluster && k >= 0);
189 return (k+1) % ncluster;
198 assert(k < ncluster && k >= 0);
218 int nbins = probdata->nbins;
219 int ncluster = probdata->ncluster;
226 for(
i = 0;
i < nbins; ++
i )
231 for(
i = 0;
i < nbins; ++
i )
233 for(
c = 0;
c < ncluster; ++
c )
246 for(
i = 0;
i < nbins; ++
i )
250 for( j = 0; j < nbins; ++j )
252 if(
i == j || (
SCIPisZero(
scip, (probdata->cmatrix[
i][j] - probdata->cmatrix[j][
i]))
253 &&
SCIPisZero(
scip, (probdata->cmatrix[
i][j] + probdata->cmatrix[j][
i]) )) )
260 for( edgetype = 0; edgetype < 3; ++edgetype )
262 if( edgetype == 0 &&
i < j )
289 int nbins = probdata->nbins;
290 int ncluster = probdata->ncluster;
294 probdata->scale = scale;
299 for(
i = 0;
i < nbins; ++
i )
302 SCIP_CALL(
SCIPcreateConsSetpart(
scip, &temp, consname, 0,
NULL,
TRUE,
TRUE,
TRUE,
TRUE,
TRUE,
FALSE,
FALSE,
305 for ( c1 = 0; c1 < ncluster; ++c1 )
314 SCIPinfoMessage(
scip,
NULL,
"Using edge-representation with simplified structure. Fixed amount of cluster. \n");
315 for(
i = 0;
i < nbins; ++
i )
317 for( j = 0; j <
i; ++j )
319 if( probdata->edgevars[
i][j] ==
NULL )
324 (probdata->cmatrix[
i][j] + probdata->cmatrix[j][
i]) * scale) );
331 for( c1 = 0; c1 < ncluster; ++c1 )
346 for( c2 = 0; c2 < ncluster; ++c2 )
353 if( c2 == c1 + 1 || ( c2 == 0 && c1 == ncluster -1) )
354 var = probdata->edgevars[
i][j][1];
355 else if( c2 == c1 - 1 || ( c1 == 0 && c2 == ncluster -1) )
356 var = probdata->edgevars[j][
i][1];
358 var = probdata->edgevars[
i][j][2];
377 for(
i = 0;
i < nbins; ++
i )
379 for( j = 0; j <
i; ++j )
381 if(
NULL == probdata->edgevars[
i][j] )
387 for( c1 = 0; c1 < 3; ++c1 )
399 for( c1 = 0; c1 < ncluster; ++c1 )
404 for(
i = 0;
i < nbins; ++
i )
428 int nbins = probdata->nbins;
429 int ncluster = probdata->ncluster;
435 probdata->scale = scale;
440 for(
i = 0;
i < nbins; ++
i )
443 SCIP_CALL(
SCIPcreateConsSetpart(
scip, &temp, consname, 0,
NULL,
TRUE,
TRUE,
TRUE,
TRUE,
TRUE,
446 for ( c1 = 0; c1 < ncluster; ++c1 )
457 "Using edge-representation with simplified structure. No variable amount of cluster. \n");
459 for(
i = 0;
i < nbins; ++
i )
461 for( j = 0; j <
i; ++j )
463 if(
NULL == probdata->edgevars[
i][j] )
473 (probdata->cmatrix[
i][j] + probdata->cmatrix[j][
i]) * scale) );
477 (probdata->cmatrix[
i][j] - probdata->cmatrix[j][
i])) );
479 (probdata->cmatrix[j][
i] - probdata->cmatrix[
i][j])) );
482 for( c1 = 0; c1 < ncluster; ++c1 )
547 (probdata->cmatrix[
i][j] - probdata->cmatrix[j][
i])
548 - (probdata->cmatrix[
i][j] + probdata->cmatrix[j][
i]) * scale) );
550 (probdata->cmatrix[j][
i] - probdata->cmatrix[
i][j])
551 - (probdata->cmatrix[
i][j] + probdata->cmatrix[j][
i]) * scale) );
556 for( c1 = 0; c1 < ncluster; ++c1 )
591 for(
i = 0;
i < nbins; ++
i )
593 for( j = 0; j <
i; ++j )
595 if(
NULL == probdata->edgevars[
i][j] || (
SCIPisZero(
scip, (probdata->cmatrix[
i][j] - probdata->cmatrix[j][
i]))
596 &&
SCIPisZero(
scip, (probdata->cmatrix[
i][j] + probdata->cmatrix[j][
i]) * scale) ) )
602 for( c1 = 0; c1 < 2; ++c1 )
615 for( c1 = 0; c1 < ncluster; ++c1 )
620 for(
i = 0;
i < nbins; ++
i )
644 SCIP_Real* quadcoefs;
653 int nbins = probdata->nbins;
654 int ncluster = probdata->ncluster;
657 probdata->scale = scale;
668 for(
i = 0;
i < nbins; ++
i )
673 for(
i = 0;
i < nbins; ++
i )
675 for(
c = 0;
c < ncluster; ++
c )
688 for(
i = 0;
i < 2 * ncluster; ++
i )
702 for(
i = 0;
i < nbins; ++
i )
706 for( j = 0; j < nbins; ++j )
707 probdata->edgevars[
i][j] =
NULL;
715 for(
i = 0;
i < nbins; ++
i )
718 SCIP_CALL(
SCIPcreateConsSetpart(
scip, &temp, consname, 0,
NULL,
TRUE,
TRUE,
TRUE,
TRUE,
TRUE,
721 for ( c1 = 0; c1 < ncluster; ++c1 )
731 for( c1 = 0; c1 < ncluster; ++c1 )
736 for(
i = 0;
i < nbins; ++
i )
745 for(
c = 0;
c < ncluster; ++
c)
751 for(
i = 0;
i < nbins; ++
i )
753 for( j = 0; j < nbins; ++j )
757 quadvars1[nquadterms] = probdata->binvars[
i][
c];
758 quadvars2[nquadterms] = probdata->binvars[j][
phi(
c,ncluster)];
759 quadcoefs[nquadterms] = probdata->cmatrix[j][
i] - probdata->cmatrix[
i][j];
768 quadvars2, quadcoefs, -
SCIPinfinity(
scip), 0.0,
TRUE,
TRUE,
TRUE,
TRUE,
TRUE,
FALSE,
FALSE,
FALSE,
FALSE) );
773 for(
c = 0;
c < ncluster; ++
c )
778 for(
i = 0;
i < nbins; ++
i)
780 for( j = 0; j < nbins; ++j )
784 quadvars1[nquadterms] = probdata->binvars[
i][
c];
785 quadvars2[nquadterms] = probdata->binvars[j][
c];
786 quadcoefs[nquadterms] = -scale * (probdata->cmatrix[
i][j] + probdata->cmatrix[j][
i]);
795 quadvars2, quadcoefs, -
SCIPinfinity(
scip), 0.0,
TRUE,
TRUE,
TRUE,
TRUE,
TRUE,
FALSE,
FALSE,
FALSE,
FALSE) );
800 for (
i = 0;
i < 2*ncluster;
i++ )
827 SCIP_Real sign[3][3];
829 int nbins = probdata->nbins;
836 probdata->scale = scale;
838 for(
i = 0;
i < 3; ++
i )
840 for( j = 0; j < 3; ++j )
852 "Using edge-representation with simplified structure. No variable amount of cluster. \n");
854 for(
i = 0;
i < nbins; ++
i )
856 for( j = 0; j < nbins; ++j )
880 for( k = 0; k < nbins; ++k )
882 if(
i == k ||
i == j || k == j )
887 for( l = 0; l < 3; l++ )
960 int nbins = sourcedata->nbins;
961 int ncluster = sourcedata->ncluster;
970 (*targetdata)->nbins = sourcedata->nbins;
971 (*targetdata)->ncluster = sourcedata->ncluster;
972 (*targetdata)->model_variant = sourcedata->model_variant;
973 (*targetdata)->scale = sourcedata->scale;
977 for(
i = 0;
i < nbins; ++
i )
982 for (
i = 0;
i < nbins; ++
i )
984 for ( j = 0; j < nbins; ++j )
986 (*targetdata)->cmatrix[
i][j] = sourcedata->cmatrix[
i][j];
994 for(
i = 0;
i < nbins; ++
i )
997 for( j = 0; j < nbins; ++j )
999 if( sourcedata->edgevars[
i][j] ==
NULL ||
i == j)
1002 for( edgetype = 0; edgetype < 3; ++edgetype )
1004 if( edgetype == 0 &&
i < j )
1006 if( sourcedata->edgevars[
i][j][edgetype] !=
NULL )
1009 &((*targetdata)->edgevars[
i][j][edgetype])) );
1012 ((*targetdata)->edgevars[
i][j][edgetype]) =
NULL;
1017 for(
i = 0;
i < nbins; ++
i )
1021 for(
c = 0;
c < ncluster; ++
c )
1023 if( sourcedata->binvars[
i][
c] !=
NULL )
1028 (*targetdata)->binvars[
i][
c] =
NULL;
1052 for (
c = 0;
c < (*probdata)->nbins; ++
c )
1054 for (
i = 0;
i < (*probdata)->ncluster; ++
i )
1056 if( (*probdata)->binvars[
c][
i] !=
NULL )
1065 for (
i = 0;
i < (*probdata)->nbins; ++
i )
1067 for( j = 0; j < (*probdata)->nbins; ++j )
1069 if( (*probdata)->edgevars[
i][j] !=
NULL && j !=
i )
1071 for ( edgetype = 0; edgetype < 3; ++edgetype )
1073 if( edgetype == 0 &&
i < j )
1076 if( (*probdata)->edgevars[
i][j][edgetype] !=
NULL )
1095 for (
i = 0;
i < (*probdata)->nbins; ++
i )
1121 for (
i = 0;
i < (*probdata)->nbins; ++
i )
1123 for (
c = 0;
c < (*probdata)->ncluster; ++
c )
1125 if( (*probdata)->binvars[
i][
c] !=
NULL )
1134 for (
i = 0;
i < (*probdata)->nbins; ++
i )
1136 for( j = 0; j < (*probdata)->nbins; ++j )
1138 if( (*probdata)->edgevars[
i][j] !=
NULL && j !=
i )
1140 for ( edgetype = 0; edgetype < 3; ++edgetype )
1142 if( 0 == edgetype && j >
i )
1145 if( (*probdata)->edgevars[
i][j][edgetype] !=
NULL )
1164 for (
i = 0;
i < (*probdata)->nbins; ++
i )
1196 nbins = sourcedata->nbins;
1197 ncluster = sourcedata->ncluster;
1200 (*targetdata)->nbins = nbins;
1201 (*targetdata)->ncluster = ncluster;
1202 (*targetdata)->model_variant = sourcedata->model_variant;
1203 (*targetdata)->scale = sourcedata->scale;
1207 for(
i = 0;
i < nbins; ++
i )
1212 for (
i = 0;
i < nbins; ++
i )
1214 for ( j = 0; j < nbins; ++j )
1216 (*targetdata)->cmatrix[
i][j] = sourcedata->cmatrix[
i][j];
1224 for(
i = 0;
i < nbins; ++
i )
1228 for( j = 0; j < nbins; ++j )
1230 if( (sourcedata)->edgevars[
i][j] ==
NULL || j ==
i )
1235 for( edgetype = 0; edgetype < 3; ++edgetype )
1237 if( edgetype == 0 && j >
i )
1240 if( sourcedata->edgevars[
i][j][edgetype] !=
NULL )
1247 varmap, consmap, global, &success) );
1250 assert((*targetdata)->edgevars[
i][j][edgetype] !=
NULL);
1255 (*targetdata)->edgevars[
i][j][edgetype] =
NULL;
1258 (*targetdata)->edgevars[
i][j][edgetype] =
NULL;
1263 for(
i = 0;
i < nbins; ++
i )
1267 for(
c = 0;
c < ncluster; ++
c )
1269 if( sourcedata->binvars[
i][
c] !=
NULL )
1276 varmap, consmap, global, &success) );
1284 (*targetdata)->binvars[
i][
c] =
NULL;
1287 (*targetdata)->binvars[
i][
c] =
NULL;
1317 assert(ncluster <= nbins);
1328 for (
i = 0;
i < nbins; ++
i )
1331 for( j = 0; j < nbins; ++j )
1333 probdata->cmatrix[
i][j] = cmatrix[
i][j];
1340 probdata->nbins=nbins;
1341 probdata->ncluster=ncluster;
1394 return probdata->cmatrix;
1410 return probdata->nbins;
1426 return probdata->ncluster;
1443 return probdata->binvars;
1459 return probdata->scale;
1476 return probdata->edgevars;
1490 assert(edgevars[state1][state2][direction] !=
NULL);
1492 return edgevars[state1][state2][direction];
1508 for(
i = 0;
i < nstates; ++
i )
1512 for( j = 0; j < nstates; ++j )
1518 if( edgevars[states[
i]][states[j]] ==
NULL )
1541 return probdata->edgegraph;
1555 SCIP_Real objvalue = 0;
1557 SCIP_Real coherence = 0;
1572 for( c1 = 0; c1 < probdata->ncluster; ++c1 )
1576 for(
i = 0;
i < probdata->nbins; ++
i )
1578 for( j = 0; j < probdata->nbins; ++j )
1590 objvalue += probdata->scale * value;
1593 for( c1 = 0; c1 < probdata->ncluster; ++c1 )
1595 for( c2 = 0; c2 < probdata->ncluster; ++c2 )
1599 for(
i = 0;
i < probdata->nbins; ++
i )
1601 for( j = 0; j < probdata->nbins; ++j )
1609 c3 = (c1 + 1) % probdata->ncluster;
1612 for(
i = 0;
i < probdata->nbins; ++
i )
1614 for( j = 0; j < probdata->nbins; ++j )
1616 value+= (probdata->cmatrix[
i][j] - probdata->cmatrix[j][
i])
1622 " Net flow from %d to %d : %f \n", c1,
phi(c1, probdata->ncluster), value);
Constraint handler for linear constraints in their most general form, .
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
constraint handler for nonlinear constraints specified by algebraic expressions
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
SCIP_RETCODE SCIPcreateConsBasicLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs)
SCIP_RETCODE SCIPaddCoefSetppc(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, 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 SCIPcreateConsSetpart(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 SCIPcreateConsBasicLogicor(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars)
SCIP_RETCODE SCIPcreateConsQuadraticNonlinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nlinvars, SCIP_VAR **linvars, SCIP_Real *lincoefs, int nquadterms, SCIP_VAR **quadvars1, SCIP_VAR **quadvars2, SCIP_Real *quadcoefs, SCIP_Real lhs, SCIP_Real rhs, 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_RETCODE SCIPaddCoefLogicor(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
SCIP_RETCODE SCIPgetVarCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR *sourcevar, SCIP_VAR **targetvar, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, SCIP_Bool *success)
void SCIPdigraphFreeComponents(SCIP_DIGRAPH *digraph)
SCIP_RETCODE SCIPcopyDigraph(SCIP *scip, SCIP_DIGRAPH **targetdigraph, SCIP_DIGRAPH *sourcedigraph)
SCIP_RETCODE SCIPdigraphAddArc(SCIP_DIGRAPH *digraph, int startnode, int endnode, void *data)
void SCIPdigraphFree(SCIP_DIGRAPH **digraph)
SCIP_RETCODE SCIPcreateDigraph(SCIP *scip, SCIP_DIGRAPH **digraph, int nnodes)
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
SCIP_RETCODE SCIPsetProbTrans(SCIP *scip,)
SCIP_RETCODE SCIPsetProbCopy(SCIP *scip,)
SCIP_RETCODE SCIPsetProbDeltrans(SCIP *scip,)
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
SCIP_PROBDATA * SCIPgetProbData(SCIP *scip)
SCIP_RETCODE SCIPsetObjsense(SCIP *scip, SCIP_OBJSENSE objsense)
SCIP_RETCODE SCIPaddOrigObjoffset(SCIP *scip, SCIP_Real addval)
SCIP_RETCODE SCIPcreateProbBasic(SCIP *scip, const char *name)
SCIP_RETCODE SCIPsetProbDelorig(SCIP *scip,)
SCIP_RETCODE SCIPsetProbData(SCIP *scip, SCIP_PROBDATA *probdata)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
SCIP_RETCODE SCIPgetCharParam(SCIP *scip, const char *name, char *value)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
#define SCIPallocClearBlockMemoryArray(scip, ptr, num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
SCIP_Bool SCIPvarIsTransformed(SCIP_VAR *var)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
SCIP_RETCODE SCIPtransformVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
SCIP_RETCODE SCIPcreateVarBasic(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype)
SCIP_VAR * SCIPvarGetTransVar(SCIP_VAR *var)
SCIP_RETCODE SCIPchgVarObj(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
SCIP_RETCODE SCIPgetTransformedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
int SCIPsnprintf(char *t, int len, const char *s,...)
assert(minobj< SCIPgetCutoffbound(scip))
SCIP_Bool edgesExist(SCIP_VAR ****edgevars, int *states, int nstates)
SCIP_RETCODE assignVars(SCIP *scip, SCIP_SOL *sol, SCIP_Real **clustering, int nbins, int ncluster)
static SCIP_RETCODE createProbOnlyEdge(SCIP *scip, SCIP_PROBDATA *probdata)
static SCIP_RETCODE createVariables(SCIP *scip, SCIP_PROBDATA *probdata)
SCIP_VAR * getEdgevar(SCIP_VAR ****edgevars, int state1, int state2, int direction)
SCIP_VAR **** SCIPcycGetEdgevars(SCIP *scip)
SCIP_RETCODE SCIPcycPrintSolutionValues(SCIP *scip, SCIP_SOL *sol)
static SCIP_RETCODE createProbQP(SCIP *scip, SCIP_PROBDATA *probdata)
int SCIPcycGetNBins(SCIP *scip)
int phiinv(int k, int ncluster)
static SCIP_RETCODE createProbSimplified(SCIP *scip, SCIP_PROBDATA *probdata)
SCIP_Real SCIPcycGetScale(SCIP *scip)
int SCIPcycGetNCluster(SCIP *scip)
static SCIP_RETCODE createProbSimplifiedTest(SCIP *scip, SCIP_PROBDATA *probdata)
SCIP_VAR *** SCIPcycGetBinvars(SCIP *scip)
SCIP_DIGRAPH * SCIPcycGetEdgeGraph(SCIP *scip)
SCIP_Real ** SCIPcycGetCmatrix(SCIP *scip)
SCIP_Bool isPartition(SCIP *scip, SCIP_Real **solclustering, int nbins, int ncluster)
SCIP_RETCODE SCIPcreateProbCyc(SCIP *scip, const char *name, int nbins, int ncluster, SCIP_Real **cmatrix)
int phi(int k, int ncluster)
problem data for cycle clustering problem
#define SCIP_DECL_PROBCOPY(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
@ SCIP_VARTYPE_CONTINUOUS
@ SCIP_VARSTATUS_MULTAGGR
internal methods for problem variables