pricer_coloring.c
Go to the documentation of this file.
23 * the current LP solution. This is done by computing a maximum weighted stable set in the current
28 * The pricer first tries to compute such a stable set using a a greedy-method. If it fails, the tclique-algorithm is
29 * used on the complementary graph. This is a branch-and-bound based algorithm for maximal cliques,
30 * included in SCIP. In this case, not only the best solution is added to the LP, but also all other
31 * stable sets found during the branch-and-bound process that could improve the current LP solution
35 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
50 #define PRICER_DELAY TRUE /* only call pricer if all problem variables have non-negative reduced costs */
80 int oldmaxvarsround; /* maximal number of variables created each round, old value before parameter was changed */
83 SCIP_Real scalefactor; /* the factor used for scaling the rational values to integers for the tclique-weights */
85 SCIP_Bool onlybest; /* determines whether the maxvarsround variables with the best reduced costs should be added
87 SCIP_Bool usegreedy; /* determines whether a greedy method is used for finding variables with neg. reduced costs */
88 SCIP_Bool usetclique; /* determines whether the tclique method is used for finding improving variables */
89 int** improvingstablesets; /* array to store the maxvarsround stable sets with the most negative reduced costs */
91 int* nstablesetnodes; /* array which stores the lengths of the stable sets in improvingstablesets */
92 int actindex; /* the index at which the current stable set was inserted into improvingstablesets */
93 SCIP_NODE* bbnode; /* the current B&B-tree node, used for limiting the number of pricing rounds */
95 int maxroundsroot; /* maximum number of pricing rounds in the root, -1 for infinity, attention: positive value may lead to a non-optimal solution */
96 int maxroundsnode; /* maximum number of pricing rounds in the B&B-nodes, -1 for infinity, attention: positive value may lead to a non-optimal solution */
97 int maxtcliquenodes; /* maximum number of nodes used in the tclique algorithm for solving the stable set problem */
160 /** computes a stable set with a greedy-method. attention: the weight of the maximum stable set is not computed! */
167 int* nmaxstablesetnodes /**< pointer to store number of nodes in the maximum weight stableset */
193 /* value = degree of the node + weight of the node * number of nodes, therefore the yet colored nodes
233 /** checks, whether the given scalar scales the given value to an integral number with error in the given bounds */
238 SCIP_Real mindelta, /**< minimal relative allowed difference of scaled coefficient s*c and integral i */
239 SCIP_Real maxdelta /**< maximal relative allowed difference of scaled coefficient s*c and integral i */
256 /** get integral number with error in the bounds which corresponds to given value scaled by a given scalar;
263 SCIP_Real mindelta, /**< minimal relative allowed difference of scaled coefficient s*c and integral i */
264 SCIP_Real maxdelta /**< maximal relative allowed difference of scaled coefficient s*c and integral i */
289 /** generates improving variables using a stable set found by the algorithm for maximum weight clique,
311 /* if the stable set was already created in a former pricing round, we don't have to add it a second time */
315 /* compute the index, at which the new stable set will be stored in the improvingstablesets-array */
387 /** solving process initialization method of variable pricer (called when branch and bound process is about to begin) */
413 /** solving process deinitialization method of variable pricer (called before branch and bound process data is freed) */
429 SCIPfreeBlockMemoryArray(scip, &(pricerdata->improvingstablesets[i]), pricerdata->improvingstablesetssize);
451 int* sortednodes; /* array of the nodes, sorted in specific way, atm by decreasing dual-solution*/
567 if ( SCIPisFeasGT(scip, maxstablesetweightreal, 1.0) && COLORprobStableSetIsNew(scip, maxstablesetnodes, nmaxstablesetnodes) )
633 SCIP_CALL( SCIPcalcIntegralScalar(pricerdata->pi, nnodes, -MINDELTA, MAXDELTA, MAXDNOM, MAXSCALE,
640 tcliqueChangeWeight(cgraph, i, getIntegralVal(pricerdata->pi[i], pricerdata->scalefactor, -MINDELTA, MAXDELTA)); /*lint !e712 !e747*/
654 tcliqueMaxClique(NULL, NULL, NULL, NULL, cgraph, tcliqueNewsolPricer, (TCLIQUE_DATA*)pricerdata, maxstablesetnodes,
656 (int)getIntegralVal(pricerdata->scalefactor, 1.0, -MINDELTA, MAXDELTA), pricerdata->maxtcliquenodes, 0, INT_MAX, -1,
660 /* if only the best vaiable should be priced per round, take the one which is given as return value from
661 tcliqueMaxClique and put it into improvingstablesets array so that it will be inserted into the LP */
838 if ( pricerdata->maxvarsround == pricerdata->oldmaxvarsround && pricerdata->nstablesetnodes != NULL )
847 SCIPfreeBlockMemoryArray(scip, &(pricerdata->improvingstablesets[i]), pricerdata->improvingstablesetssize);
849 SCIPfreeBlockMemoryArray(scip, &(pricerdata->improvingstablesets), pricerdata->oldmaxvarsround);
854 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(pricerdata->nstablesetnodes), pricerdata->maxvarsround) );
855 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(pricerdata->improvingstablesets), pricerdata->maxvarsround) );
859 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(pricerdata->improvingstablesets[i]), pricerdata->improvingstablesetssize) ); /*lint !e866*/
862 SCIPdebugMessage("maxvarsround changed from %d to %d\n", pricerdata->oldmaxvarsround, pricerdata->maxvarsround);
891 SCIP_CALL( SCIPincludePricerBasic(scip, &pricer, PRICER_NAME, PRICER_DESC, PRICER_PRIORITY, PRICER_DELAY,
904 &pricerdata->maxvarsround, TRUE, DEFAULT_MAXVARSROUND, -1, INT_MAX, paramChgdMaxvarsround, (SCIP_PARAMDATA*)pricerdata) );
914 "should a greedy method be used to compute improving stable sets before potential use of tclique",
919 "should the best variables be addded to the problem instead of adding the first found variables?",
static SCIP_Bool hasUncoloredNode(TCLIQUE_GRAPH *graph, SCIP_Bool *colored)
Definition: pricer_coloring.c:109
Definition: type_result.h:33
Definition: struct_scip.h:59
SCIP_Real SCIPgetDualsolSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9317
static SCIP_RETCODE sortNodes(SCIP *scip, SCIP_Real *weights, int nnodes, int *sortednodes)
Definition: pricer_coloring.c:132
static SCIP_DECL_PRICERCOPY(pricerCopyColoring)
Definition: pricer_coloring.c:354
Definition: type_result.h:49
static SCIP_Bool isIntegralScalar(SCIP_Real val, SCIP_Real scalar, SCIP_Real mindelta, SCIP_Real maxdelta)
Definition: pricer_coloring.c:235
SCIP_RETCODE SCIPaddCoefSetppc(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_setppc.c:9226
Definition: struct_var.h:198
SCIP_RETCODE SCIPsetPricerFree(SCIP *scip, SCIP_PRICER *pricer, SCIP_DECL_PRICERFREE((*pricerfree)))
Definition: scip_pricer.c:190
Definition: type_var.h:53
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)
Definition: scip_param.c:48
file reader for vertex coloring instances
void COLORprobGetStableSets(SCIP *scip, int ***stablesets, int **nelements, int *nstablesets)
Definition: probdata_coloring.c:1042
Definition: tclique.h:57
constraint handler for storing the graph at each node of the tree
SCIP_RETCODE SCIPchgVarUbLazy(SCIP *scip, SCIP_VAR *var, SCIP_Real lazyub)
Definition: scip_var.c:5150
static SCIP_DECL_PRICERFARKAS(pricerFarkasColoring)
Definition: pricer_coloring.c:733
Definition: struct_pricer.h:37
Definition: struct_tree.h:132
SCIP_RETCODE SCIPaddPricedVar(SCIP *scip, SCIP_VAR *var, SCIP_Real score)
Definition: scip_prob.c:1731
static SCIP_RETCODE greedyStableSet(SCIP *scip, TCLIQUE_GRAPH *graph, SCIP_Bool *colored, int *maxstablesetnodes, int *nmaxstablesetnodes)
Definition: pricer_coloring.c:162
SCIP_RETCODE SCIPsetPricerCopy(SCIP *scip, SCIP_PRICER *pricer, SCIP_DECL_PRICERCOPY((*pricercopy)))
Definition: scip_pricer.c:166
Definition: cons_sos1.c:233
static SCIP_Longint getIntegralVal(SCIP_Real val, SCIP_Real scalar, SCIP_Real mindelta, SCIP_Real maxdelta)
Definition: pricer_coloring.c:260
SCIP_EXPORT void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
Definition: struct_cons.h:37
SCIP_RETCODE COLORprobAddVarForStableSet(SCIP *scip, int setindex, SCIP_VAR *var)
Definition: probdata_coloring.c:823
SCIP_RETCODE COLORprobAddNewStableSet(SCIP *scip, int *stablesetnodes, int nstablesetnodes, int *setindex)
Definition: probdata_coloring.c:969
variable pricer for the vertex coloring problem
static SCIP_DECL_PARAMCHGD(paramChgdMaxvarsround)
Definition: pricer_coloring.c:822
SCIP_RETCODE SCIPsetPricerExitsol(SCIP *scip, SCIP_PRICER *pricer, SCIP_DECL_PRICEREXITSOL((*pricerexitsol)))
Definition: scip_pricer.c:286
Definition: type_retcode.h:33
static SCIP_DECL_PRICERREDCOST(pricerRedcostColoring)
Definition: pricer_coloring.c:443
SCIP_RETCODE SCIPsetPricerInitsol(SCIP *scip, SCIP_PRICER *pricer, SCIP_DECL_PRICERINITSOL((*pricerinitsol)))
Definition: scip_pricer.c:262
SCIP_VAR * COLORprobGetVarForStableSet(SCIP *scip, int setindex)
Definition: probdata_coloring.c:847
Definition: type_lp.h:34
SCIP_Bool COLORprobStableSetIsNew(SCIP *scip, int *stablesetnodes, int nstablesetnodes)
Definition: probdata_coloring.c:936
SCIP_CONS ** COLORprobGetConstraints(SCIP *scip)
Definition: probdata_coloring.c:1181
void SCIPpricerSetData(SCIP_PRICER *pricer, SCIP_PRICERDATA *pricerdata)
Definition: pricer.c:511
static SCIP_DECL_PRICERINITSOL(pricerInitsolColoring)
Definition: pricer_coloring.c:389
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)
Definition: scip_var.c:105
static SCIP_DECL_PRICERFREE(pricerFreeColoring)
Definition: pricer_coloring.c:366
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)
Definition: scip_pricer.c:118
TCLIQUE_GRAPH * COLORconsGetComplementaryGraph(SCIP *scip)
Definition: cons_storeGraph.c:910
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:812
SCIP_EXPORT void tcliqueChangeWeight(TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight)
Definition: tclique_graph.c:353
SCIP_EXPORT 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)
Definition: tclique_branch.c:1001
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)
Definition: scip_param.c:74
TCLIQUE_GRAPH * COLORconsGetCurrentGraph(SCIP *scip)
Definition: cons_storeGraph.c:882
SCIP_EXPORT void SCIPsortDownInt(int *intarray, int len)
Definition: objbenders.h:33
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)
Definition: misc.c:9444
SCIP_RETCODE SCIPincludePricerColoring(SCIP *scip)
Definition: pricer_coloring.c:875
SCIP_EXPORT int * tcliqueGetDegrees(TCLIQUE_GRAPH *tcliquegraph)
Definition: tclique_graph.c:786
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:497
static SCIP_DECL_PRICEREXITSOL(pricerExitsolColoring)
Definition: pricer_coloring.c:415