57#define PRICER_NAME "coloring"
58#define PRICER_DESC "pricer for coloring"
59#define PRICER_PRIORITY 5000000
60#define PRICER_DELAY TRUE
63#define MAXDNOM 10000LL
69#define DEFAULT_MAXVARSROUND 1
70#define DEFAULT_USETCLIQUE TRUE
71#define DEFAULT_USEGREEDY TRUE
72#define DEFAULT_ONLYBEST FALSE
73#define DEFAULT_MAXROUNDSROOT -1
74#define DEFAULT_MAXROUNDSNODE -1
75#define DEFAULT_MAXTCLIQUENODES INT_MAX
91 SCIP_Real scalefactor;
97 int** improvingstablesets;
98 int improvingstablesetssize;
106 SCIP_Real lowerbound;
127 for (
i = 0;
i < tcliqueGetNNodes(graph);
i++)
158 values[
i] = weights[
i];
174 int* maxstablesetnodes,
175 int* nmaxstablesetnodes
192 nnodes = tcliqueGetNNodes(graph);
193 *nmaxstablesetnodes = 0;
206 values[
i] = ( colored[
i] ==
TRUE ? degrees[
i] : degrees[
i]+
nnodes );
213 maxstablesetnodes[0] = sortednodes[0];
214 (*nmaxstablesetnodes) = 1;
219 for ( j = 0; j < (*nmaxstablesetnodes); j++ )
221 if ( tcliqueIsEdge(graph, sortednodes[
i], maxstablesetnodes[j]) )
227 if ( indnode ==
TRUE )
230 maxstablesetnodes[*nmaxstablesetnodes] = sortednodes[
i];
231 (*nmaxstablesetnodes) = (*nmaxstablesetnodes)+1;
248 SCIP_Real maxsum = 0.0;
250 SCIP_Bool scalesuccess;
255 maxsum += pricerdata->pi[
i];
262 maxscale = (INT_MAX -
nnodes - 1) / maxsum;
265 &pricerdata->scalefactor, &scalesuccess) );
268 if ( ! scalesuccess )
269 pricerdata->scalefactor = maxscale;
278 SCIP_Real scalefactor,
287 scaledval = val * scalefactor;
289 upval =
EPSCEIL(scaledval, 0.0);
315 assert(pricerdata->nstablesetsfound >= 0);
316 assert(pricerdata->scalefactor > 0);
319 *stopsolving =
FALSE;
326 pricerdata->actindex = (pricerdata->actindex+1)%(pricerdata->maxvarsround);
329 pricerdata->nstablesetnodes[pricerdata->actindex] = ncliquenodes;
330 for (
i = 0;
i < ncliquenodes;
i++ )
331 pricerdata->improvingstablesets[pricerdata->actindex][
i] = cliquenodes[
i];
337 if ( ! pricerdata->onlybest && pricerdata->actindex+1 >= pricerdata->maxvarsround )
371 if ( pricerdata !=
NULL )
398 pricerdata->bbnode =
NULL;
422 for (
i = 0;
i < pricerdata->maxvarsround;
i++ )
447 SCIP_Real maxstablesetweightreal;
450 int* maxstablesetnodes;
451 int nmaxstablesetnodes;
454 SCIP_Real maxredcost;
472 if ( pricerdata->noderounds > 0 )
473 pricerdata->noderounds--;
477 if ( pricerdata->bbnode ==
NULL )
479 pricerdata->noderounds = pricerdata->maxroundsroot;
484 pricerdata->noderounds = pricerdata->maxroundsnode;
490 if ( pricerdata->noderounds == 0 )
496 *lowerbound = pricerdata->lowerbound;
507 nnodes = tcliqueGetNNodes(graph);
519 pricerdata->nstablesetsfound = 0;
521 if ( pricerdata->usegreedy )
530 maxstablesetnodes[0] = sortednodes[0];
531 nmaxstablesetnodes = 1;
532 maxstablesetweightreal = pricerdata->pi[sortednodes[0]];
538 for ( j = 0; j < nmaxstablesetnodes; j++ )
540 if ( tcliqueIsEdge(graph, sortednodes[
i], maxstablesetnodes[j]) )
549 maxstablesetnodes[nmaxstablesetnodes] = sortednodes[
i];
550 nmaxstablesetnodes = nmaxstablesetnodes+1;
551 maxstablesetweightreal = maxstablesetweightreal + pricerdata->pi[sortednodes[
i]];
556 SCIPdebugMessage(
"value of the greedy-heuristik: %f \n", maxstablesetweightreal);
563 pricerdata->nstablesetnodes[pricerdata->nstablesetsfound] = nmaxstablesetnodes;
564 for (
i = 0;
i < nmaxstablesetnodes;
i++ )
566 pricerdata->improvingstablesets[pricerdata->nstablesetsfound][
i] = maxstablesetnodes[
i];
568 pricerdata->nstablesetsfound += 1;
580 for (
i = 0;
i < nmaxstablesetnodes;
i++ )
590 SCIPdebugMessage(
"%d vars created via greedy\n", pricerdata->nstablesetsfound);
596 if ( pricerdata->nstablesetsfound == 0 && pricerdata->usetclique )
612 pricerdata->pi[
i] =
MAX( MIN(dualsol, 1.0), 0.0);
622 pricerdata->actindex = -1;
623 for (
i = 0;
i < pricerdata->maxvarsround;
i++ )
624 pricerdata->nstablesetnodes[
i] = 0;
628 &(nmaxstablesetnodes), &maxstablesetweight, 0,
635 if ( pricerdata->onlybest && pricerdata->maxvarsround == 1 )
637 pricerdata->nstablesetnodes[0] = nmaxstablesetnodes;
638 for (
i = 0;
i < nmaxstablesetnodes;
i++ )
639 pricerdata->improvingstablesets[0][
i] = maxstablesetnodes[
i];
645 for (
i = 0;
i < pricerdata->maxvarsround;
i++ )
647 if ( pricerdata->nstablesetnodes[
i] > 0 )
649 maxstablesetweightreal = 0;
650 for ( j = 0; j < pricerdata->nstablesetnodes[
i]; j++ )
651 maxstablesetweightreal += pricerdata->pi[pricerdata->improvingstablesets[
i][j]];
653 if ( maxredcost < maxstablesetweightreal )
654 maxredcost = maxstablesetweightreal;
662 pricerdata->nstablesetnodes[
i], &setnumber) );
665 if ( setnumber >= 0 )
676 pricerdata->nstablesetsfound += 1;
679 for ( j = 0; j < pricerdata->nstablesetnodes[
i]; j++ )
683 pricerdata->constraints[pricerdata->improvingstablesets[
i][j]],
var) );
694 assert( maxredcost > 0.0 );
711 int* maxstablesetnodes;
712 int nmaxstablesetnodes;
719 int* nstablesetelements;
744 nmaxstablesetnodes = 0;
750 for (
i = 0;
i < nstablesets;
i++ )
756 for ( j = 0; j < nstablesetelements[
i]; j++ )
758 colored[stablesets[
i][j]] =
TRUE;
779 for (
i = 0;
i < nmaxstablesetnodes;
i++ )
784 colored[maxstablesetnodes[
i]] =
TRUE;
806 if( pricerdata->maxvarsround == pricerdata->oldmaxvarsround )
809 if ( pricerdata->maxvarsround <= 1 )
810 pricerdata->maxvarsround = 2;
812 if ( pricerdata->maxvarsround == pricerdata->oldmaxvarsround && pricerdata->nstablesetnodes !=
NULL )
816 if ( pricerdata -> oldmaxvarsround > 0 )
819 for (
i = 0;
i < pricerdata->oldmaxvarsround;
i++ )
831 for (
i = 0;
i < pricerdata->maxvarsround;
i++ )
836 SCIPdebugMessage(
"maxvarsround changed from %d to %d\n", pricerdata->oldmaxvarsround, pricerdata->maxvarsround);
838 pricerdata->oldmaxvarsround = pricerdata->maxvarsround;
857 pricerdata->scip =
scip;
859 pricerdata->maxvarsround = 0;
860 pricerdata->oldmaxvarsround = 0;
866 pricerRedcostColoring, pricerFarkasColoring, pricerdata) );
876 "pricers/coloring/maxvarsround",
877 "maximum number of variables that the coloring variable pricer creates each round",
881 "pricers/coloring/usetclique",
882 "should the tclique-algorithm be used to solve the pricing-problem to optimality? WARNING: computed (optimal) solutions are not necessarily optimal if this is set to FALSE.",
886 "pricers/coloring/usegreedy",
887 "should a greedy method be used to compute improving stable sets before potential use of tclique",
891 "pricers/coloring/onlybest",
892 "should the best variables be addded to the problem instead of adding the first found variables?",
896 "pricers/coloring/maxroundsroot",
897 "maximum number of pricing rounds in the root node (-1: no limit)",
901 "pricers/coloring/maxroundsnode",
902 "maximum number of pricing rounds in each node (except root node)(-1: no limit)",
906 "pricers/coloring/maxtcliquenodes",
907 "maximum number of B&B-nodes used in the tclique-algorithm",
TCLIQUE_GRAPH * COLORconsGetCurrentGraph(SCIP *scip)
TCLIQUE_GRAPH * COLORconsGetComplementaryGraph(SCIP *scip)
constraint handler for storing the graph at each node of the tree
SCIP_RETCODE SCIPaddCoefSetppc(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
SCIP_Real SCIPgetDualsolSetppc(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPaddPricedVar(SCIP *scip, SCIP_VAR *var, SCIP_Real score)
int SCIPgetNVars(SCIP *scip)
SCIP_RETCODE SCIPupdateLocalLowerbound(SCIP *scip, SCIP_Real newbound)
SCIP_RETCODE SCIPcalcIntegralScalar(SCIP_Real *vals, int nvals, SCIP_Real mindelta, SCIP_Real maxdelta, SCIP_Longint maxdnom, SCIP_Real maxscale, SCIP_Real *intscalar, SCIP_Bool *success)
SCIP_Real SCIPrelDiff(SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
SCIP_Real SCIPgetLPObjval(SCIP *scip)
#define SCIPfreeBlockMemoryArray(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 SCIPsetPricerFree(SCIP *scip, SCIP_PRICER *pricer,)
void SCIPpricerSetData(SCIP_PRICER *pricer, SCIP_PRICERDATA *pricerdata)
SCIP_PRICERDATA * SCIPpricerGetData(SCIP_PRICER *pricer)
SCIP_RETCODE SCIPsetPricerCopy(SCIP *scip, SCIP_PRICER *pricer,)
const char * SCIPpricerGetName(SCIP_PRICER *pricer)
SCIP_RETCODE SCIPincludePricerBasic(SCIP *scip, SCIP_PRICER **pricerptr, const char *name, const char *desc, int priority, SCIP_Bool delay, SCIP_DECL_PRICERREDCOST((*pricerredcost)), SCIP_DECL_PRICERFARKAS((*pricerfarkas)), SCIP_PRICERDATA *pricerdata)
SCIP_RETCODE SCIPsetPricerExitsol(SCIP *scip, SCIP_PRICER *pricer,)
SCIP_RETCODE SCIPsetPricerInitsol(SCIP *scip, SCIP_PRICER *pricer,)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
SCIP_NODE * SCIPgetRootNode(SCIP *scip)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
void SCIPvarMarkDeletable(SCIP_VAR *var)
SCIP_RETCODE SCIPcreateVar(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype, SCIP_Bool initial, SCIP_Bool removable, SCIP_DECL_VARDELORIG((*vardelorig)), SCIP_DECL_VARTRANS((*vartrans)), SCIP_DECL_VARDELTRANS((*vardeltrans)), SCIP_DECL_VARCOPY((*varcopy)), SCIP_VARDATA *vardata)
SCIP_RETCODE SCIPchgVarUbLazy(SCIP *scip, SCIP_VAR *var, SCIP_Real lazyub)
SCIP_Bool SCIPvarIsInLP(SCIP_VAR *var)
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
void SCIPsortDownInt(int *intarray, int len)
assert(minobj< SCIPgetCutoffbound(scip))
#define BMSclearMemoryArray(ptr, num)
SCIP_PARAMDATA * SCIPparamGetData(SCIP_PARAM *param)
static SCIP_RETCODE greedyStableSet(SCIP *scip, TCLIQUE_GRAPH *graph, SCIP_Bool *colored, int *maxstablesetnodes, int *nmaxstablesetnodes)
#define DEFAULT_MAXROUNDSROOT
#define DEFAULT_MAXVARSROUND
static SCIP_RETCODE calculateScalingValue(SCIP_PRICERDATA *pricerdata, int nnodes)
#define DEFAULT_USETCLIQUE
static TCLIQUE_WEIGHT getScaledDualWeight(SCIP_Real val, SCIP_Real scalefactor, SCIP_Real mindelta)
SCIP_RETCODE SCIPincludePricerColoring(SCIP *scip)
#define DEFAULT_USEGREEDY
#define DEFAULT_MAXTCLIQUENODES
static SCIP_RETCODE sortNodes(SCIP *scip, SCIP_Real *weights, int nnodes, int *sortednodes)
static SCIP_Bool hasUncoloredNode(TCLIQUE_GRAPH *graph, SCIP_Bool *colored)
#define DEFAULT_MAXROUNDSNODE
variable pricer for the vertex coloring problem
SCIP_CONS ** COLORprobGetConstraints(SCIP *scip)
SCIP_RETCODE COLORprobAddNewStableSet(SCIP *scip, int *stablesetnodes, int nstablesetnodes, int *setindex)
int COLORprobGetNNodes(SCIP *scip)
SCIP_VAR * COLORprobGetVarForStableSet(SCIP *scip, int setindex)
void COLORprobGetStableSets(SCIP *scip, int ***stablesets, int **nelements, int *nstablesets)
SCIP_Bool COLORprobStableSetIsNew(SCIP *scip, int *stablesetnodes, int nstablesetnodes)
SCIP_RETCODE COLORprobAddVarForStableSet(SCIP *scip, int setindex, SCIP_VAR *var)
int COLORprobGetNStableSets(SCIP *scip)
file reader for vertex coloring instances
void tcliqueChangeWeight(TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight)
int * tcliqueGetDegrees(TCLIQUE_GRAPH *tcliquegraph)
enum TCLIQUE_Status TCLIQUE_STATUS
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)
struct TCLIQUE_Graph TCLIQUE_GRAPH
#define TCLIQUE_NEWSOL(x)
struct SCIP_ParamData SCIP_PARAMDATA
#define SCIP_DECL_PARAMCHGD(x)
#define SCIP_DECL_PRICERFREE(x)
#define SCIP_DECL_PRICERREDCOST(x)
#define SCIP_DECL_PRICERFARKAS(x)
#define SCIP_DECL_PRICEREXITSOL(x)
#define SCIP_DECL_PRICERINITSOL(x)
struct SCIP_PricerData SCIP_PRICERDATA
#define SCIP_DECL_PRICERCOPY(x)
enum SCIP_Retcode SCIP_RETCODE
struct SCIP_VarData SCIP_VARDATA