pricer_coloring.c
Go to the documentation of this file.
24 * the current LP solution. This is done by computing a maximum weighted stable set in the current
29 * The pricer first tries to compute such a stable set using a a greedy-method. If it fails, the tclique-algorithm is
30 * used on the complementary graph. This is a branch-and-bound based algorithm for maximal cliques,
31 * included in SCIP. In this case, not only the best solution is added to the LP, but also all other
32 * stable sets found during the branch-and-bound process that could improve the current LP solution
36 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
51 #define PRICER_DELAY TRUE /* only call pricer if all problem variables have non-negative reduced costs */
79 int oldmaxvarsround; /* maximal number of variables created each round, old value before parameter was changed */
82 SCIP_Real scalefactor; /* the factor used for scaling the rational values to integers for the tclique-weights */
84 SCIP_Bool onlybest; /* determines whether the maxvarsround variables with the best reduced costs should be added
86 SCIP_Bool usegreedy; /* determines whether a greedy method is used for finding variables with neg. reduced costs */
87 SCIP_Bool usetclique; /* determines whether the tclique method is used for finding improving variables */
88 int** improvingstablesets; /* array to store the maxvarsround stable sets with the most negative reduced costs */
90 int* nstablesetnodes; /* array which stores the lengths of the stable sets in improvingstablesets */
91 int actindex; /* the index at which the current stable set was inserted into improvingstablesets */
92 SCIP_NODE* bbnode; /* the current B&B-tree node, used for limiting the number of pricing rounds */
94 int maxroundsroot; /* maximum number of pricing rounds in the root, -1 for infinity, attention: positive value may lead to a non-optimal solution */
95 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 */
96 int maxtcliquenodes; /* maximum number of nodes used in the tclique algorithm for solving the stable set problem */
159 /** computes a stable set with a greedy-method. attention: the weight of the maximum stable set is not computed! */
166 int* nmaxstablesetnodes /**< pointer to store number of nodes in the maximum weight stableset */
192 /* value = degree of the node + weight of the node * number of nodes, therefore the yet colored nodes
232 /** Calculates a good scalar value to use in order to scale the dual weights to integer values without large loss of precision */
248 /* Calculate largest possible scalar value so that this sum is still representable using the type of TCLIQUE_WEIGHT (int).
255 SCIP_CALL( SCIPcalcIntegralScalar(pricerdata->pi, nnodes, -MINDELTA, MAXDELTA, MAXDNOM, maxscale,
258 /* if no nice denominator can be found, use the largest possible scaling value to reduce numerical issues */
290 /** generates improving variables using a stable set found by the algorithm for maximum weight clique,
312 /* if the stable set was already created in a former pricing round, we don't have to add it a second time */
316 /* compute the index, at which the new stable set will be stored in the improvingstablesets-array */
373 /** solving process initialization method of variable pricer (called when branch and bound process is about to begin) */
399 /** solving process deinitialization method of variable pricer (called before branch and bound process data is freed) */
415 SCIPfreeBlockMemoryArray(scip, &(pricerdata->improvingstablesets[i]), pricerdata->improvingstablesetssize);
437 int* sortednodes; /* array of the nodes, sorted in specific way, atm by decreasing dual-solution*/
549 if ( SCIPisFeasGT(scip, maxstablesetweightreal, 1.0) && COLORprobStableSetIsNew(scip, maxstablesetnodes, nmaxstablesetnodes) )
610 tcliqueChangeWeight(cgraph, i, getScaledDualWeight(pricerdata->pi[i], pricerdata->scalefactor, -MINDELTA)); /*lint !e712 !e747*/
618 tcliqueMaxClique(NULL, NULL, NULL, NULL, cgraph, tcliqueNewsolPricer, (TCLIQUE_DATA*)pricerdata, maxstablesetnodes,
620 getScaledDualWeight(1.0, pricerdata->scalefactor, -MINDELTA), pricerdata->maxtcliquenodes, 0, INT_MAX, -1,
624 /* if only the best variable should be priced per round, take the one which is given as return value from
625 * tcliqueMaxClique and put it into improvingstablesets array so that it will be inserted into the LP */
686 pricerdata->lowerbound = MAX(pricerdata->lowerbound, SCIPgetLPObjval(scip) / maxredcost); /*lint !e666*/
803 if ( pricerdata->maxvarsround == pricerdata->oldmaxvarsround && pricerdata->nstablesetnodes != NULL )
812 SCIPfreeBlockMemoryArray(scip, &(pricerdata->improvingstablesets[i]), pricerdata->improvingstablesetssize);
814 SCIPfreeBlockMemoryArray(scip, &(pricerdata->improvingstablesets), pricerdata->oldmaxvarsround);
819 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(pricerdata->nstablesetnodes), pricerdata->maxvarsround) );
820 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(pricerdata->improvingstablesets), pricerdata->maxvarsround) );
824 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(pricerdata->improvingstablesets[i]), pricerdata->improvingstablesetssize) ); /*lint !e866*/
827 SCIPdebugMessage("maxvarsround changed from %d to %d\n", pricerdata->oldmaxvarsround, pricerdata->maxvarsround);
856 SCIP_CALL( SCIPincludePricerBasic(scip, &pricer, PRICER_NAME, PRICER_DESC, PRICER_PRIORITY, PRICER_DELAY,
869 &pricerdata->maxvarsround, TRUE, DEFAULT_MAXVARSROUND, -1, INT_MAX, paramChgdMaxvarsround, (SCIP_PARAMDATA*)pricerdata) );
873 "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.",
878 "should a greedy method be used to compute improving stable sets before potential use of tclique",
883 "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:108
Definition: type_result.h:33
void SCIPpricerSetData(SCIP_PRICER *pricer, SCIP_PRICERDATA *pricerdata)
Definition: pricer.c:511
SCIP_RETCODE SCIPaddCoefSetppc(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_setppc.c:9372
Definition: struct_scip.h:59
static SCIP_RETCODE sortNodes(SCIP *scip, SCIP_Real *weights, int nnodes, int *sortednodes)
Definition: pricer_coloring.c:131
static SCIP_DECL_PRICERCOPY(pricerCopyColoring)
Definition: pricer_coloring.c:340
static SCIP_RETCODE calculateScalingValue(SCIP_PRICERDATA *pricerdata, int nnodes)
Definition: pricer_coloring.c:234
Definition: type_result.h:49
Definition: struct_var.h:198
SCIP_RETCODE SCIPchgVarUbLazy(SCIP *scip, SCIP_VAR *var, SCIP_Real lazyub)
Definition: scip_var.c:5161
Definition: type_var.h:53
static TCLIQUE_WEIGHT getScaledDualWeight(SCIP_Real val, SCIP_Real scalefactor, SCIP_Real mindelta)
Definition: pricer_coloring.c:267
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
SCIP_RETCODE SCIPsetPricerExitsol(SCIP *scip, SCIP_PRICER *pricer, SCIP_DECL_PRICEREXITSOL((*pricerexitsol)))
Definition: scip_pricer.c:286
constraint handler for storing the graph at each node of the tree
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
static SCIP_DECL_PRICERFARKAS(pricerFarkasColoring)
Definition: pricer_coloring.c:698
Definition: struct_pricer.h:37
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
Definition: struct_tree.h:132
static SCIP_RETCODE greedyStableSet(SCIP *scip, TCLIQUE_GRAPH *graph, SCIP_Bool *colored, int *maxstablesetnodes, int *nmaxstablesetnodes)
Definition: pricer_coloring.c:161
Definition: cons_sos1.c:233
Definition: struct_cons.h:37
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
SCIP_Real SCIPgetDualsolSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9463
void tcliqueChangeWeight(TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight)
Definition: tclique_graph.c:353
int * tcliqueGetDegrees(TCLIQUE_GRAPH *tcliquegraph)
Definition: tclique_graph.c:770
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:787
Definition: type_retcode.h:33
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
static SCIP_DECL_PRICERREDCOST(pricerRedcostColoring)
Definition: pricer_coloring.c:429
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:812
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
static SCIP_DECL_PRICERINITSOL(pricerInitsolColoring)
Definition: pricer_coloring.c:375
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:478
SCIP_RETCODE SCIPsetPricerFree(SCIP *scip, SCIP_PRICER *pricer, SCIP_DECL_PRICERFREE((*pricerfree)))
Definition: scip_pricer.c:190
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:352
SCIP_RETCODE SCIPsetPricerInitsol(SCIP *scip, SCIP_PRICER *pricer, SCIP_DECL_PRICERINITSOL((*pricerinitsol)))
Definition: scip_pricer.c:262
SCIP_RETCODE SCIPupdateLocalLowerbound(SCIP *scip, SCIP_Real newbound)
Definition: scip_prob.c:3695
SCIP_RETCODE SCIPaddPricedVar(SCIP *scip, SCIP_VAR *var, SCIP_Real score)
Definition: scip_prob.c:1732
TCLIQUE_GRAPH * COLORconsGetComplementaryGraph(SCIP *scip)
Definition: cons_storeGraph.c:913
void SCIPsortDownInt(int *intarray, int len)
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:9458
SCIP_RETCODE SCIPsetPricerCopy(SCIP *scip, SCIP_PRICER *pricer, SCIP_DECL_PRICERCOPY((*pricercopy)))
Definition: scip_pricer.c:166
Definition: tclique.h:56
TCLIQUE_GRAPH * COLORconsGetCurrentGraph(SCIP *scip)
Definition: cons_storeGraph.c:885
SCIPallocBlockMemory(scip, subsol))
Definition: objbenders.h:33
SCIP_RETCODE SCIPincludePricerColoring(SCIP *scip)
Definition: pricer_coloring.c:840
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
static SCIP_DECL_PRICEREXITSOL(pricerExitsolColoring)
Definition: pricer_coloring.c:401