# SCIP

Solving Constraint Integer Programs

pricer_coloring.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
7 /* fuer Informationstechnik Berlin */
8 /* */
10 /* */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file pricer_coloring.c
17  * @brief variable pricer for the vertex coloring problem
18  * @author Gerald Gamrath
19  *
20  * This file implements the pricer for the coloring algorithm.
21  *
22  * It computes maximal stable sets in the current graph whose corresponding variables can improve
23  * the current LP solution. This is done by computing a maximum weighted stable set in the current
24  * graph with dual-variables of the node constraints as weights. A variable can improve the
25  * solution, if the weight of the corresponding stable set is larger than 1, since it then has
26  * negative reduced costs, which are given by (1 - weight of the set).
27  *
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
32  * are added, limited to a maximal number that can be changed by a parameter.
33  */
34
35 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
36
37 #include <assert.h>
38 #include <string.h>
39
40 #include "pricer_coloring.h"
42 #include "cons_storeGraph.h"
43 #include <stdio.h>
44 #include <stdlib.h>
45
46
47 #define PRICER_NAME "coloring"
48 #define PRICER_DESC "pricer for coloring"
49 #define PRICER_PRIORITY 5000000
50 #define PRICER_DELAY TRUE /* only call pricer if all problem variables have non-negative reduced costs */
51
52 /* defines for rounding for tclique */
53 #define MAXDNOM 1000LL
54 #define MINDELTA 1e-03
55 #define MAXDELTA 1e-09
56 #define MAXSCALE 1000.0
57
58
59 /* default values for parameters */
60 #define DEFAULT_MAXVARSROUND 0
61 #define DEFAULT_USETCLIQUE TRUE
62 #define DEFAULT_USEGREEDY TRUE
63 #define DEFAULT_ONLYBEST TRUE
64 #define DEFAULT_MAXROUNDSROOT -1
65 #define DEFAULT_MAXROUNDSNODE -1
66 #define DEFAULT_MAXTCLIQUENODES INT_MAX
67
68
69
70 /*
71  * Data structures
72  */
73
74
75 /** variable pricer data */
76 struct SCIP_PricerData
77 {
78  SCIP* scip; /* SCIP data structure */
79  int maxvarsround; /* maximal number of variables created each round */
80  int oldmaxvarsround; /* maximal number of variables created each round, old value before parameter was changed */
81  int nstablesetsfound; /* number of improving stable sets found in the current round so far */
82  SCIP_CONS** constraints; /* array containing all node constraints */
83  SCIP_Real scalefactor; /* the factor used for scaling the rational values to integers for the tclique-weights */
84  SCIP_Real* pi; /* array of the dual solutions */
85  SCIP_Bool onlybest; /* determines whether the maxvarsround variables with the best reduced costs should be added
86  (onlybest = true) or the first maxvarsround variables which are found are added (false) */
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 */
90  int improvingstablesetssize; /* size of each improvingstablesets array */
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 */
94  int noderounds; /* the number of remaining pricing rounds at the current node */
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 */
98  SCIP_Real lowerbound; /* lower bound computed by the pricer */
99 };
100
101
102 /*
103  * Local methods
104  */
105
106 /** returns whether the graph has an uncolored node
107  */
108 static
110  TCLIQUE_GRAPH* graph, /**< the graph that should be colored */
111  SCIP_Bool* colored /**< array of booleans, colored[i] == TRUE iff node i is colored */
112  )
113 {
114  int i;
115
116  assert(graph != NULL);
117  assert(colored != NULL);
118
119  for ( i = 0; i < tcliqueGetNNodes(graph); i++)
120  {
121  /* node not yet colored */
122  if (!colored[i])
123  {
124  return TRUE;
125  }
126  }
127  return FALSE;
128 }
129
130 /** sorts the nodes from 0 to nnodes-1 w.r.t. the given weights */
131 static
133  SCIP* scip, /**< SCIP data structure */
134  SCIP_Real* weights, /**< the weights for sorting */
135  int nnodes, /**< the number of nodes */
136  int* sortednodes /**< the array that will be overwritten with the sorted node numbers */
137  )
138 {
139  int i;
140  SCIP_Real* values;
141
142  assert(scip != NULL);
143  assert(weights != NULL);
144
145  /* create array with indices and copy the weights-array */
146  SCIP_CALL( SCIPallocBufferArray(scip, &values, nnodes) );
147  for ( i = 0; i < nnodes; i++)
148  {
149  sortednodes[i] = i;
150  values[i] = weights[i];
151  }
152
153  /* sort the nodes w.r.t. the computed values */
154  SCIPsortDownRealInt(values, sortednodes, nnodes);
155  SCIPfreeBufferArray(scip, &values);
156
157  return SCIP_OKAY;
158 }
159
160 /** computes a stable set with a greedy-method. attention: the weight of the maximum stable set is not computed! */
161 static
163  SCIP* scip, /**< SCIP data structure */
164  TCLIQUE_GRAPH* graph, /**< pointer to graph data structure */
165  SCIP_Bool* colored, /**< array for marking yet colored nodes */
166  int* maxstablesetnodes, /**< pointer to store nodes of the maximum weight stableset */
167  int* nmaxstablesetnodes /**< pointer to store number of nodes in the maximum weight stableset */
168  )
169 {
170  SCIP_Bool indnode;
171  int nnodes;
172  int i;
173  int j;
174  int* degrees;
175  int* sortednodes;
176  SCIP_Real* values; /* values for sorting the nodes: deg(v)+w(v)*nnodes */
177
178  assert(scip != NULL);
179  assert(graph != NULL);
180  assert(maxstablesetnodes != NULL);
181  assert(nmaxstablesetnodes != NULL);
182
183  /* get number of nodes */
184  nnodes = tcliqueGetNNodes(graph);
185  *nmaxstablesetnodes = 0;
186
187  /* get the degrees for the nodes in the graph */
188  degrees = tcliqueGetDegrees(graph);
189  SCIP_CALL( SCIPallocBufferArray(scip, &values, nnodes) );
190  SCIP_CALL( SCIPallocBufferArray(scip, &sortednodes, nnodes) );
191
192  /* set values to the nodes which are used for sorting them */
193  /* value = degree of the node + weight of the node * number of nodes, therefore the yet colored nodes
194  (which have weight 0) have lower values than the not yet colored nodes which have weight 1 */
195  for ( i = 0; i < nnodes; i++ )
196  {
197  sortednodes[i] = i;
198  values[i] = ( colored[i] == TRUE ? degrees[i] : degrees[i]+nnodes );
199  }
200
201  /* sort the nodes w.r.t. the computed values */
202  SCIPsortDownRealInt(values, sortednodes, nnodes);
203
204  /* insert first node */
205  maxstablesetnodes[0] = sortednodes[0];
206  (*nmaxstablesetnodes) = 1;
207  for ( i = 1; i < nnodes; i++)
208  {
209  /* check whether node is independent to nodes in the set */
210  indnode = TRUE;
211  for ( j = 0; j < (*nmaxstablesetnodes); j++ )
212  {
213  if ( tcliqueIsEdge(graph, sortednodes[i], maxstablesetnodes[j]) )
214  {
215  indnode = FALSE;
216  break;
217  }
218  }
219  if ( indnode == TRUE )
220  {
221  /* node is independent, thus add it to the set */
222  maxstablesetnodes[*nmaxstablesetnodes] = sortednodes[i];
223  (*nmaxstablesetnodes) = (*nmaxstablesetnodes)+1;
224  }
225
226  }
227  SCIPfreeBufferArray(scip, &sortednodes);
228  SCIPfreeBufferArray(scip, &values);
229
230  return SCIP_OKAY;
231 }
232
233 /** checks, whether the given scalar scales the given value to an integral number with error in the given bounds */
234 static
236  SCIP_Real val, /**< value that should be scaled to an integral value */
237  SCIP_Real scalar, /**< scalar that should be tried */
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 */
240  )
241 {
242  SCIP_Real sval;
243  SCIP_Real downval;
244  SCIP_Real upval;
245
246  assert(mindelta <= 0.0);
247  assert(maxdelta >= 0.0);
248
249  sval = val * scalar;
250  downval = EPSFLOOR(sval, 0.0); /*lint !e835*/
251  upval = EPSCEIL(sval, 0.0); /*lint !e835*/
252
253  return (SCIPrelDiff(sval, downval) <= maxdelta || SCIPrelDiff(sval, upval) >= mindelta);
254 }
255
256 /** get integral number with error in the bounds which corresponds to given value scaled by a given scalar;
257  * should be used in connection with isIntegralScalar()
258  */
259 static
261  SCIP_Real val, /**< value that should be scaled to an integral value */
262  SCIP_Real scalar, /**< scalar that should be tried */
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 */
265  )
266 {
267  SCIP_Real sval;
268  SCIP_Real downval;
269  SCIP_Real upval;
270  SCIP_Longint intval;
271
272  assert(mindelta <= 0.0);
273  assert(maxdelta >= 0.0);
274
275  sval = val * scalar;
276  downval = EPSFLOOR(sval, 0.0); /*lint !e835*/
277  upval = EPSCEIL(sval, 0.0); /*lint !e835*/
278
279  if( SCIPrelDiff(sval, upval) >= mindelta )
280  intval = (SCIP_Longint) upval;
281  else
282  intval = (SCIP_Longint) downval;
283
284  return intval;
285 }
286
287
288
289 /** generates improving variables using a stable set found by the algorithm for maximum weight clique,
290  * decides whether to stop generating cliques with the algorithm for maximum weight clique
291  */
292 static
293 TCLIQUE_NEWSOL(tcliqueNewsolPricer)
294 {
295  SCIP_PRICERDATA* pricerdata;
296  int i;
297
298  assert(acceptsol != NULL);
299  assert(stopsolving != NULL);
300
301  pricerdata = (SCIP_PRICERDATA*)tcliquedata;
302
303  assert(pricerdata != NULL);
304  assert(pricerdata->scip != NULL);
305  assert(pricerdata->nstablesetsfound >= 0);
306  assert(pricerdata->scalefactor > 0);
307
308  *acceptsol = FALSE;
309  *stopsolving = FALSE;
310
311  /* if the stable set was already created in a former pricing round, we don't have to add it a second time */
312  if ( !COLORprobStableSetIsNew(pricerdata->scip, cliquenodes, ncliquenodes) )
313  return;
314
315  /* compute the index, at which the new stable set will be stored in the improvingstablesets-array */
316  pricerdata->actindex = (pricerdata->actindex+1)%(pricerdata->maxvarsround);
317
318  /* found maxvarsround variables */
319  if ( pricerdata->nstablesetnodes[pricerdata->actindex] == -1 )
320  {
321  /* if we are looking for the best stable sets, continue at the beginning
322  and overwrite the stable set with least improvement */
323  if ( pricerdata->onlybest )
324  {
325  pricerdata->actindex = 0;
326  }
327  /* if we only want to find maxvarsround variables (onlybest = false), we can stop now */
328  else
329  {
330  *stopsolving = TRUE;
331  return;
332  }
333  }
334
335  /* write the new improving stable set into the improvingstablesets-array */
336  pricerdata->nstablesetnodes[pricerdata->actindex] = ncliquenodes;
337  for ( i = 0; i < ncliquenodes; i++ )
338  {
339  pricerdata->improvingstablesets[pricerdata->actindex][i] = cliquenodes[i];
340  }
341
342  /* accept the solution as new incumbent */
343  *acceptsol = TRUE;
344
345 }/*lint !e715*/
346
347
348 /*
349  * Callback methods of variable pricer
350  */
351
352 /** copy method for pricer plugins (called when SCIP copies plugins) */
353 static
354 SCIP_DECL_PRICERCOPY(pricerCopyColoring)
355 { /*lint --e{715}*/
356  assert(scip != NULL);
357  assert(pricer != NULL);
358  assert(strcmp(SCIPpricerGetName(pricer), PRICER_NAME) == 0);
359
360  return SCIP_OKAY;
361 }
362
363
364 /** destructor of variable pricer to free user data (called when SCIP is exiting) */
365 static
366 SCIP_DECL_PRICERFREE(pricerFreeColoring)
367 {
368  SCIP_PRICERDATA* pricerdata;
369
370  assert(scip != NULL);
371
372  /* get pricerdata */
373  pricerdata = SCIPpricerGetData(pricer);
374
375  /* free memory for pricerdata*/
376  if ( pricerdata != NULL )
377  {
378  SCIPfreeBlockMemory(scip, &pricerdata);
379  }
380
381  SCIPpricerSetData(pricer, NULL);
382  return SCIP_OKAY;
383 }
384
385
386
387 /** solving process initialization method of variable pricer (called when branch and bound process is about to begin) */
388 static
389 SCIP_DECL_PRICERINITSOL(pricerInitsolColoring)
390 {
391  SCIP_PRICERDATA* pricerdata;
392
393  assert(scip != NULL);
394  assert(pricer != NULL);
395
396  pricerdata = SCIPpricerGetData(pricer);
397  assert(pricerdata != NULL);
398
399  /* set maximal number of variables to be priced in each round */
400  SCIP_CALL( SCIPsetIntParam(scip, "pricers/coloring/maxvarsround",
401  MAX(5,COLORprobGetNStableSets(scip))*MAX(50,COLORprobGetNNodes(scip))/50) ); /*lint !e666*/
402
403  pricerdata->bbnode = NULL;
404
405  /* allocate memory */
407
408  return SCIP_OKAY;
409 }
410
411
412
413 /** solving process deinitialization method of variable pricer (called before branch and bound process data is freed) */
414 static
415 SCIP_DECL_PRICEREXITSOL(pricerExitsolColoring)
416 {
417  SCIP_PRICERDATA* pricerdata;
418  int i;
419
420  assert(scip != NULL);
421  assert(pricer != NULL);
422
423  pricerdata = SCIPpricerGetData(pricer);
424  assert(pricerdata != NULL);
425
426  /* free memory */
427  for ( i = 0; i < pricerdata->maxvarsround; i++ )
428  {
429  SCIPfreeBlockMemoryArray(scip, &(pricerdata->improvingstablesets[i]), pricerdata->improvingstablesetssize);
430  }
431  SCIPfreeBlockMemoryArray(scip, &(pricerdata->improvingstablesets), pricerdata->maxvarsround);
432  SCIPfreeBlockMemoryArray(scip, &(pricerdata->nstablesetnodes), pricerdata->maxvarsround);
434
435  return SCIP_OKAY;
436 }
437
438
439
440
441 /** reduced cost pricing method of variable pricer for feasible LPs */
442 static
443 SCIP_DECL_PRICERREDCOST(pricerRedcostColoring)
444 {
445  SCIP_PRICERDATA* pricerdata; /* the data of the pricer */
446
447  TCLIQUE_GRAPH* graph; /* the current graph */
448  TCLIQUE_GRAPH* cgraph; /* the complementary graph, used for tclique-algorithm */
449  int nnodes; /* number of nodes in the graph */
450
451  int* sortednodes; /* array of the nodes, sorted in specific way, atm by decreasing dual-solution*/
452  SCIP_Real maxstablesetweightreal;/* weigth of the maximal stable set computed by the greedy */
453  SCIP_Bool indnode; /* boolean for greedy: is node independant? */
454
455  int* maxstablesetnodes; /* pointer to store nodes of the maximum weight clique */
456  int nmaxstablesetnodes; /* number of nodes in the maximum weight clique */
457  TCLIQUE_WEIGHT maxstablesetweight; /* weight of the maximum weight clique */
458  TCLIQUE_STATUS status; /* status of clique-computation */
459  SCIP_Real maxredcost;
460
461  SCIP_VAR* var; /* pointer to the new created variable */
462  int setnumber; /* index of the new created variable */
463
464  /* variables used for scaling the rational dual-solutions to integers */
465  SCIP_Bool scalesuccess;
466  SCIP_Bool weightsIntegral;
467
468  int i;
469  int j;
470
471  assert(scip != NULL);
472  assert(pricer != NULL);
473
474  /* get pricer data */
475  pricerdata = SCIPpricerGetData(pricer);
476  assert(pricerdata != NULL);
477
478  /* count down number of remaining pricing rounds at the current node */
479  if ( pricerdata->bbnode == SCIPgetCurrentNode(scip) )
480  {
481  if ( pricerdata->noderounds > 0 )
482  pricerdata->noderounds--;
483  }
484  else
485  {
486  if ( pricerdata->bbnode == NULL )
487  {
488  pricerdata->noderounds = pricerdata->maxroundsroot;
489  pricerdata->lowerbound = - SCIPinfinity(scip);
490  }
491  else
492  {
493  pricerdata->noderounds = pricerdata->maxroundsnode;
494  pricerdata->lowerbound = - SCIPinfinity(scip);
495  }
496  pricerdata->bbnode = SCIPgetCurrentNode(scip);
497  }
498  /* stop pricing if limit for pricing rounds reached */
499  if ( pricerdata->noderounds == 0 )
500  {
501  SCIPdebugMessage("maxrounds reached, pricing interrupted\n");
502
503  /* set result and lowerbound pointer */
504  *result = SCIP_DIDNOTRUN;
505  *lowerbound = pricerdata->lowerbound;
506
507  return SCIP_OKAY;
508  }
509
510  /* set result pointer */
511  *result = SCIP_SUCCESS;
512
513  /* get graph and number of nodes */
515  assert(graph != NULL);
516  nnodes = tcliqueGetNNodes(graph);
517
519
520  /* get constraints */
521  pricerdata->constraints = COLORprobGetConstraints(scip);
522
523  /* get dual solutions and save them in pi */
524  for ( i = 0; i < nnodes; i++)
525  {
526  pricerdata->pi[i] = SCIPgetDualsolSetppc(scip, pricerdata->constraints[i]);
527  }
528  pricerdata->nstablesetsfound = 0;
529  /* ......greedy-heuristic........ */
530  if ( pricerdata->usegreedy )
531  {
532  SCIP_CALL( SCIPallocBufferArray(scip, &sortednodes, nnodes) );
533  SCIP_CALL( SCIPallocBufferArray(scip, &maxstablesetnodes, nnodes) );
534  SCIP_CALL( sortNodes(scip, pricerdata->pi, nnodes, sortednodes) );
535
536  SCIPdebugMessage("starting greedy...\n");
537
538  /* insert first node */
539  maxstablesetnodes[0] = sortednodes[0];
540  nmaxstablesetnodes = 1;
541  maxstablesetweightreal = pricerdata->pi[sortednodes[0]];
542
543  for ( i = 1; i < nnodes; i++ )
544  {
545  /* test if node is independant to nodes in stable set */
546  indnode = TRUE;
547  for ( j = 0; j < nmaxstablesetnodes; j++ )
548  {
549  if ( tcliqueIsEdge(graph, sortednodes[i], maxstablesetnodes[j]) )
550  {
551  indnode = FALSE;
552  break;
553  }
554  }
555  /* if node is independant to nodes in stable set, insert it into stable set*/
556  if ( indnode )
557  {
558  maxstablesetnodes[nmaxstablesetnodes] = sortednodes[i];
559  nmaxstablesetnodes = nmaxstablesetnodes+1;
560  maxstablesetweightreal = maxstablesetweightreal + pricerdata->pi[sortednodes[i]];
561  }
562  }
563
564
565  SCIPdebugMessage("value of the greedy-heuristik: %f \n", maxstablesetweightreal);
566  setnumber = -1;
567  if ( SCIPisFeasGT(scip, maxstablesetweightreal, 1.0) && COLORprobStableSetIsNew(scip, maxstablesetnodes, nmaxstablesetnodes) )
568  {
569  SCIP_CALL( COLORprobAddNewStableSet(scip, maxstablesetnodes, nmaxstablesetnodes, &setnumber) );
570
571  assert(setnumber >= 0);
572  pricerdata->nstablesetnodes[pricerdata->nstablesetsfound] = nmaxstablesetnodes;
573  for ( i = 0; i < nmaxstablesetnodes; i++ )
574  {
575  pricerdata->improvingstablesets[pricerdata->nstablesetsfound][i] = maxstablesetnodes[i];
576  }
577  pricerdata->nstablesetsfound += 1;
578
579  /* create variable for the stable set and add it to SCIP */
580  SCIP_CALL( SCIPcreateVar(scip, &var, NULL, 0.0, 1.0, 1.0, SCIP_VARTYPE_BINARY,
581  TRUE, TRUE, NULL, NULL, NULL, NULL, (SCIP_VARDATA*)(size_t)setnumber) ); /*lint !e571*/
582
583  SCIP_CALL( COLORprobAddVarForStableSet(scip, setnumber, var) );
585  SCIP_CALL( SCIPaddPricedVar(scip, var, 1.0) );
586  SCIP_CALL( SCIPchgVarUbLazy(scip, var, 1.0) );
587
588  /* add variable to the constraints in which it appears */
589  for ( i = 0; i < nmaxstablesetnodes; i++ )
590  {
591  /* add variable to node constraints of nodes in the set */
592  SCIP_CALL( SCIPaddCoefSetppc(scip, pricerdata->constraints[maxstablesetnodes[i]], var) );
593  }
594  }
595
596  SCIPfreeBufferArray(scip, &maxstablesetnodes);
597  SCIPfreeBufferArray(scip, &sortednodes);
598
599  SCIPdebugMessage("%d vars created via greedy\n", pricerdata->nstablesetsfound);
600  }
601
602
603  /* solve with tclique-algorithm */
604  /* only use tclique if the greedy found no improving stable set */
605  if ( pricerdata->nstablesetsfound == 0 && pricerdata->usetclique )
606  {
607  SCIPdebugMessage("starting tclique algorithm...\n");
608  maxredcost = 0;
609  /* get the complementary graph from the current cons */
611  SCIP_CALL( SCIPallocBufferArray(scip, &maxstablesetnodes, nnodes) );
612  /* get dual solutions and set weight of nodes */
613  weightsIntegral = TRUE;
614  for ( i = 0; i < nnodes; i++ )
615  {
616  pricerdata->pi[i] = SCIPgetDualsolSetppc(scip, pricerdata->constraints[i]);
617
618  if( !isIntegralScalar(pricerdata->pi[i], 1.0, -MINDELTA, MAXDELTA) )
619  {
620  weightsIntegral = FALSE;
621  }
622  }
623  /* are weigths integral? */
624  if( weightsIntegral )
625  {
626  pricerdata->scalefactor = 1.0;
627  scalesuccess = TRUE;
628  }
629  else
630  {
631  /* compute factor, which makes the weights integral */
632  scalesuccess = FALSE;
633  SCIP_CALL( SCIPcalcIntegralScalar(pricerdata->pi, nnodes, -MINDELTA, MAXDELTA, MAXDNOM, MAXSCALE,
634  &(pricerdata->scalefactor), &scalesuccess) );
635  }
636  assert(scalesuccess);
637  /* change the weights for the nodes in the graph to the dual solution value * scalefactor */
638  for ( i = 0; i < nnodes; i++ )
639  {
640  tcliqueChangeWeight(cgraph, i, getIntegralVal(pricerdata->pi[i], pricerdata->scalefactor, -MINDELTA, MAXDELTA)); /*lint !e712 !e747*/
641  }
642  /* clear the improvingstablesets array */
643  pricerdata->actindex = -1;
644  for ( i = 0; i < pricerdata->maxvarsround-pricerdata->nstablesetsfound; i++ )
645  {
646  pricerdata->nstablesetnodes[i] = 0;
647  }
648  for ( ; i < pricerdata->maxvarsround; i++ )
649  {
650  pricerdata->nstablesetnodes[i] = -1;
651  }
652
653  /* compute maximal clique */
654  tcliqueMaxClique(NULL, NULL, NULL, NULL, cgraph, tcliqueNewsolPricer, (TCLIQUE_DATA*)pricerdata, maxstablesetnodes,
655  &(nmaxstablesetnodes), &maxstablesetweight, 0,
656  (int)getIntegralVal(pricerdata->scalefactor, 1.0, -MINDELTA, MAXDELTA), pricerdata->maxtcliquenodes, 0, INT_MAX, -1,
657  NULL, &status);
658  assert(status == TCLIQUE_OPTIMAL);
659
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 */
662  if ( pricerdata->onlybest && pricerdata->maxvarsround == 1 )
663  {
664  pricerdata->nstablesetnodes[0] = nmaxstablesetnodes;
665  for ( i = 0; i < nmaxstablesetnodes; i++ )
666  {
667  pricerdata->improvingstablesets[0][i] = maxstablesetnodes[i];
668  }
669  }
670
671  SCIPfreeBufferArray(scip, &maxstablesetnodes);
672
673  /* insert all variables in the array improvingstablesets into the LP */
674  for ( i = 0; i < pricerdata->maxvarsround; i++ )
675  {
676  if ( pricerdata->nstablesetnodes[i] > 0 )
677  {
678  maxstablesetweightreal = 0;
679  for ( j = 0; j < pricerdata->nstablesetnodes[i]; j++ )
680  {
681  maxstablesetweightreal += pricerdata->pi[pricerdata->improvingstablesets[i][j]];
682  }
683  if ( maxredcost < maxstablesetweightreal )
684  {
685  maxredcost = maxstablesetweightreal;
686  }
687  if ( SCIPisFeasGT(scip, maxstablesetweightreal, 1.0) )
688  {
689  setnumber = -1;
690  /* insert new variable */
692  pricerdata->nstablesetnodes[i], &setnumber) );
693  /* only insert, if there yet is no variable for this stable set */
694  if ( setnumber >= 0 )
695  {
696  /* create variable for the stable set and add it to SCIP */
697  SCIP_CALL( SCIPcreateVar(pricerdata->scip, &var, NULL, 0.0, 1.0, 1.0, SCIP_VARTYPE_BINARY,
698  TRUE, TRUE, NULL, NULL, NULL, NULL, (SCIP_VARDATA*)(size_t)setnumber) ); /*lint !e571*/
699
700  SCIP_CALL( COLORprobAddVarForStableSet(pricerdata->scip, setnumber, var) );
702  SCIP_CALL( SCIPaddPricedVar(pricerdata->scip, var, 1.0) );
703  SCIP_CALL( SCIPchgVarUbLazy(scip, var, 1.0) );
704
705  pricerdata->nstablesetsfound += 1;
706  /* add variable to the constraints in which it appears */
707  for ( j = 0; j < pricerdata->nstablesetnodes[i]; j++ )
708  {
709  /* add variable to node constraints of nodes in the set */
711  pricerdata->constraints[pricerdata->improvingstablesets[i][j]], var) );
712  }
713  }
714  }
715  }
716  }
717  if ( SCIPisFeasGT(scip, maxredcost, 1.0) )
718  {
720  {
721  pricerdata->lowerbound = MAX( pricerdata->lowerbound,
722  (SCIPgetLPObjval(scip) + ((1.0 - maxredcost) * SCIPgetPrimalbound(scip))) ); /*lint !e666*/
723  }
724  }
725  }
726
727  return SCIP_OKAY;
728 }/*lint !e715*/
729
730
731 /** farkas pricing method of variable pricer for infeasible LPs */
732 static
733 SCIP_DECL_PRICERFARKAS(pricerFarkasColoring)
734 {
735  TCLIQUE_GRAPH* graph;
736  int nnodes; /* number of nodes */
737  int* maxstablesetnodes; /* array containig the nodes of the max stable set */
738  int nmaxstablesetnodes; /* number of nodes in stable set */
739  int setnumber; /* number of already found stable sets */
740  SCIP_VAR* var; /* var for the actual stable set */
741  SCIP_CONS** constraints; /* array of added constraints */
742  SCIP_Bool* colored; /* array for marking of yet colored nodes
743  colored_i = true iff node i is already colored */
744  int** stablesets;
745  int* nstablesetelements;
746  int nstablesets;
747  int i;
748  int j;
749  assert(scip != NULL);
750
752  assert(graph != NULL);
753
754  nnodes = COLORprobGetNNodes(scip);
755  assert(nnodes > 0);
756
757  /* get the node-constraits */
758  constraints = COLORprobGetConstraints(scip);
759  assert(constraints != NULL);
760
761  /* get all yet computed stable sets */
762  COLORprobGetStableSets(scip, &stablesets, &nstablesetelements, &nstablesets);
763  assert(stablesets != NULL && nstablesetelements != NULL);
764  assert(nstablesets >= 0);
765  assert(nnodes == tcliqueGetNNodes(graph));
766
767  /* allocate memory for arrays */
768  SCIP_CALL( SCIPallocBufferArray( scip, &colored, nnodes) );
769  SCIP_CALL( SCIPallocBufferArray( scip, &maxstablesetnodes, nnodes) );
770  nmaxstablesetnodes = 0;
771
772  /* fill colored-array with FALSE */
773  BMSclearMemoryArray(colored, nnodes);
774
775  /* go through all stable sets and set colored to true for nodes in them */
776  for ( i = 0; i < nstablesets; i++ )
777  {
781  {
782  for ( j = 0; j < nstablesetelements[i]; j++ )
783  {
784  colored[stablesets[i][j]] = TRUE;
785  }
786  }
787  }
788
789  /* create maximal Stable Sets until all Nodes are covered */
790  while ( hasUncoloredNode(graph, colored) )
791  {
792  SCIP_CALL( greedyStableSet(scip, graph, colored, maxstablesetnodes, &nmaxstablesetnodes) );
793  SCIPsortDownInt(maxstablesetnodes, nmaxstablesetnodes);
794  SCIP_CALL( COLORprobAddNewStableSet(scip, maxstablesetnodes, nmaxstablesetnodes, &setnumber) );
795  assert(setnumber != -1);
796
797  /* create variable for the stable set and add it to SCIP */
798  SCIP_CALL( SCIPcreateVar(scip, &var, NULL, 0.0, 1.0, 1.0, SCIP_VARTYPE_BINARY,
799  TRUE, TRUE, NULL, NULL, NULL, NULL, (SCIP_VARDATA*) (size_t) setnumber) ); /*lint !e571*/
800  SCIP_CALL( COLORprobAddVarForStableSet(scip, setnumber, var) );
802  SCIP_CALL( SCIPaddPricedVar(scip, var, 1.0) );
803  SCIP_CALL( SCIPchgVarUbLazy(scip, var, 1.0) );
804
805  for ( i = 0; i < nmaxstablesetnodes; i++ )
806  {
807  /* add variable to node constraints of nodes in the set */
808  SCIP_CALL( SCIPaddCoefSetppc(scip, constraints[maxstablesetnodes[i]], var) );
809  /* mark node as colored */
810  colored[maxstablesetnodes[i]] = TRUE;
811  }
812  }
813  /* free memory */
814  SCIPfreeBufferArray(scip, &maxstablesetnodes);
815  SCIPfreeBufferArray(scip, &colored);
816
817  return SCIP_OKAY;
818 }/*lint !e715*/
819
820 /** method to call, when the maximal number of variables priced in each round is changed */
821 static
822 SCIP_DECL_PARAMCHGD(paramChgdMaxvarsround)
823 {
824  SCIP_PARAMDATA* paramdata;
825  SCIP_PRICERDATA* pricerdata;
826  int i;
827
828  paramdata = SCIPparamGetData(param);
829  assert(paramdata != NULL);
830  pricerdata = (SCIP_PRICERDATA*) paramdata;
831
832  if( pricerdata->maxvarsround == pricerdata->oldmaxvarsround )
833  return SCIP_OKAY;
834
835  if ( pricerdata->maxvarsround <= 1 )
836  pricerdata->maxvarsround = 2;
837
838  if ( pricerdata->maxvarsround == pricerdata->oldmaxvarsround && pricerdata->nstablesetnodes != NULL )
839  return SCIP_OKAY;
840
841  /* free old memory */
842  if ( pricerdata -> oldmaxvarsround > 0 )
843  {
844  /* free memory */
845  for ( i = 0; i < pricerdata->oldmaxvarsround; i++ )
846  {
847  SCIPfreeBlockMemoryArray(scip, &(pricerdata->improvingstablesets[i]), pricerdata->improvingstablesetssize);
848  }
849  SCIPfreeBlockMemoryArray(scip, &(pricerdata->improvingstablesets), pricerdata->oldmaxvarsround);
850  SCIPfreeBlockMemoryArray(scip, &(pricerdata->nstablesetnodes), pricerdata->oldmaxvarsround);
851  }
852
853  /* allocate memory of the new size */
854  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(pricerdata->nstablesetnodes), pricerdata->maxvarsround) );
855  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(pricerdata->improvingstablesets), pricerdata->maxvarsround) );
856  pricerdata->improvingstablesetssize = COLORprobGetNNodes(scip);
857  for ( i = 0; i < pricerdata->maxvarsround; i++ )
858  {
859  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(pricerdata->improvingstablesets[i]), pricerdata->improvingstablesetssize) ); /*lint !e866*/
860  }
861
862  SCIPdebugMessage("maxvarsround changed from %d to %d\n", pricerdata->oldmaxvarsround, pricerdata->maxvarsround);
863
864  pricerdata->oldmaxvarsround = pricerdata->maxvarsround;
865
866  return SCIP_OKAY;
867 }
868
869
870 /*
871  * variable pricer specific interface methods
872  */
873
874 /** creates the coloring variable pricer and includes it in SCIP */
876  SCIP* scip /**< SCIP data structure */
877  )
878 {
879  SCIP_PRICERDATA* pricerdata;
880  SCIP_PRICER* pricer;
881
882  SCIP_CALL( SCIPallocBlockMemory(scip, &pricerdata) );
883  pricerdata->scip = scip;
884
885  pricerdata->maxvarsround = 0;
886  pricerdata->oldmaxvarsround = 0;
887
888
889  pricer = NULL;
890  /* include variable pricer */
892  pricerRedcostColoring, pricerFarkasColoring, pricerdata) );
893  assert(pricer != NULL);
894
895  /* include non-fundamental callbacks via setter functions */
896  SCIP_CALL( SCIPsetPricerCopy(scip, pricer, pricerCopyColoring) );
897  SCIP_CALL( SCIPsetPricerFree(scip, pricer, pricerFreeColoring) );
898  SCIP_CALL( SCIPsetPricerInitsol(scip, pricer, pricerInitsolColoring) );
899  SCIP_CALL( SCIPsetPricerExitsol(scip, pricer, pricerExitsolColoring) );
900
902  "pricers/coloring/maxvarsround",
903  "maximum number of variables that the coloring variable pricer creates each round",
904  &pricerdata->maxvarsround, TRUE, DEFAULT_MAXVARSROUND, -1, INT_MAX, paramChgdMaxvarsround, (SCIP_PARAMDATA*)pricerdata) );
905
907  "pricers/coloring/usetclique",
908  "should the tclique-algorithm be used to solve the pricing-problem to optimality?\n \
909  WARNING: computed (optimal) solutions are not necessarily optimal if this is set to FALSE",
910  &pricerdata->usetclique, TRUE, DEFAULT_USETCLIQUE, NULL, NULL) );
911
913  "pricers/coloring/usegreedy",
914  "should a greedy method be used to compute improving stable sets before potential use of tclique",
915  &pricerdata->usegreedy, FALSE, DEFAULT_USEGREEDY, NULL, NULL) );
916
918  "pricers/coloring/onlybest",
919  "should the best variables be addded to the problem instead of adding the first found variables?",
920  &pricerdata->onlybest, FALSE, DEFAULT_ONLYBEST, NULL, NULL) );
921
923  "pricers/coloring/maxroundsroot",
924  "maximum number of pricing rounds in the root node (-1: no limit)",
925  &pricerdata->maxroundsroot, TRUE, DEFAULT_MAXROUNDSROOT, -1, INT_MAX, NULL, NULL) );
926
928  "pricers/coloring/maxroundsnode",
929  "maximum number of pricing rounds in each node (except root node)(-1: no limit)",
930  &pricerdata->maxroundsnode, TRUE, DEFAULT_MAXROUNDSNODE, -1, INT_MAX, NULL, NULL) );
931
933  "pricers/coloring/maxtcliquenodes",
934  "maximum number of B&B-nodes used in the tclique-algorithm",
935  &pricerdata->maxtcliquenodes, TRUE, DEFAULT_MAXTCLIQUENODES, 0, INT_MAX, NULL, NULL) );
936
937  return SCIP_OKAY;
938 }
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:97
static SCIP_Bool hasUncoloredNode(TCLIQUE_GRAPH *graph, SCIP_Bool *colored)
#define MAXSCALE
#define NULL
Definition: def.h:253
static TCLIQUE_NEWSOL(tcliqueNewsolPricer)
enum TCLIQUE_Status TCLIQUE_STATUS
Definition: tclique.h:59
#define DEFAULT_MAXROUNDSROOT
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:80
SCIP_EXPORT SCIP_Bool SCIPvarIsInLP(SCIP_VAR *var)
Definition: var.c:17077
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)
struct TCLIQUE_Graph TCLIQUE_GRAPH
Definition: tclique.h:40
static SCIP_DECL_PRICERCOPY(pricerCopyColoring)
SCIP_PARAMDATA * SCIPparamGetData(SCIP_PARAM *param)
Definition: paramset.c:661
#define DEFAULT_MAXVARSROUND
static SCIP_Bool isIntegralScalar(SCIP_Real val, SCIP_Real scalar, SCIP_Real mindelta, SCIP_Real maxdelta)
struct SCIP_ParamData SCIP_PARAMDATA
Definition: type_paramset.h:76
SCIP_RETCODE SCIPaddCoefSetppc(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_setppc.c:9232
#define MAXDNOM
SCIP_EXPORT void SCIPvarMarkDeletable(SCIP_VAR *var)
Definition: var.c:16971
SCIP_RETCODE SCIPsetPricerFree(SCIP *scip, SCIP_PRICER *pricer, SCIP_DECL_PRICERFREE((*pricerfree)))
Definition: scip_pricer.c:189
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:80
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1987
#define FALSE
Definition: def.h:73
#define PRICER_NAME
struct SCIP_VarData SCIP_VARDATA
Definition: type_var.h:107
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#define PRICER_DESC
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:47
file reader for vertex coloring instances
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
void COLORprobGetStableSets(SCIP *scip, int ***stablesets, int **nelements, int *nstablesets)
#define SCIPdebugMessage
Definition: pub_message.h:77
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:5087
static SCIP_DECL_PRICERFARKAS(pricerFarkasColoring)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:158
SCIP_RETCODE SCIPaddPricedVar(SCIP *scip, SCIP_VAR *var, SCIP_Real score)
Definition: scip_prob.c:1732
SCIP * scip
Definition: cons_sos1.c:232
static SCIP_RETCODE greedyStableSet(SCIP *scip, TCLIQUE_GRAPH *graph, SCIP_Bool *colored, int *maxstablesetnodes, int *nmaxstablesetnodes)
SCIP_RETCODE SCIPsetPricerCopy(SCIP *scip, SCIP_PRICER *pricer, SCIP_DECL_PRICERCOPY((*pricercopy)))
Definition: scip_pricer.c:165
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_Real SCIPrelDiff(SCIP_Real val1, SCIP_Real val2)
Definition: misc.c:10571
static SCIP_Longint getIntegralVal(SCIP_Real val, SCIP_Real scalar, SCIP_Real mindelta, SCIP_Real maxdelta)
SCIP_EXPORT void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
#define DEFAULT_MAXROUNDSNODE
#define DEFAULT_USEGREEDY
int COLORprobGetNNodes(SCIP *scip)
SCIP_NODE * SCIPgetRootNode(SCIP *scip)
Definition: scip_tree.c:99
SCIP_RETCODE COLORprobAddVarForStableSet(SCIP *scip, int setindex, SCIP_VAR *var)
SCIP_RETCODE COLORprobAddNewStableSet(SCIP *scip, int *stablesetnodes, int nstablesetnodes, int *setindex)
variable pricer for the vertex coloring problem
static SCIP_DECL_PARAMCHGD(paramChgdMaxvarsround)
SCIP_RETCODE SCIPsetPricerExitsol(SCIP *scip, SCIP_PRICER *pricer, SCIP_DECL_PRICEREXITSOL((*pricerexitsol)))
Definition: scip_pricer.c:285
static SCIP_DECL_PRICERREDCOST(pricerRedcostColoring)
SCIP_RETCODE SCIPsetPricerInitsol(SCIP *scip, SCIP_PRICER *pricer, SCIP_DECL_PRICERINITSOL((*pricerinitsol)))
Definition: scip_pricer.c:261
#define SCIP_CALL(x)
Definition: def.h:365
SCIP_VAR * COLORprobGetVarForStableSet(SCIP *scip, int setindex)
#define MINDELTA
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip_lp.c:237
#define EPSCEIL(x, eps)
Definition: def.h:198
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool COLORprobStableSetIsNew(SCIP *scip, int *stablesetnodes, int nstablesetnodes)
#define SCIP_Bool
Definition: def.h:70
SCIP_CONS ** COLORprobGetConstraints(SCIP *scip)
void SCIPpricerSetData(SCIP_PRICER *pricer, SCIP_PRICERDATA *pricerdata)
Definition: pricer.c:511
int COLORprobGetNStableSets(SCIP *scip)
static SCIP_DECL_PRICERINITSOL(pricerInitsolColoring)
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:104
#define DEFAULT_MAXTCLIQUENODES
const char * SCIPpricerGetName(SCIP_PRICER *pricer)
Definition: pricer.c:588
#define DEFAULT_ONLYBEST
static SCIP_DECL_PRICERFREE(pricerFreeColoring)
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:117
SCIP_EXPORT SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17418
TCLIQUE_GRAPH * COLORconsGetComplementaryGraph(SCIP *scip)
SCIP_PRICERDATA * SCIPpricerGetData(SCIP_PRICER *pricer)
Definition: pricer.c:501
#define MAX(x, y)
Definition: def.h:222
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define DEFAULT_USETCLIQUE
SCIP_EXPORT void tcliqueChangeWeight(TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight)
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)
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:73
#define SCIP_Real
Definition: def.h:164
SCIP_Real SCIPgetPrimalbound(SCIP *scip)
#define SCIP_Longint
Definition: def.h:149
struct SCIP_PricerData SCIP_PRICERDATA
Definition: type_pricer.h:36
#define nnodes
Definition: gastrans.c:65
#define PRICER_PRIORITY
#define EPSFLOOR(x, eps)
Definition: def.h:197
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:120
TCLIQUE_GRAPH * COLORconsGetCurrentGraph(SCIP *scip)
SCIP_EXPORT void SCIPsortDownInt(int *intarray, int len)
int TCLIQUE_WEIGHT
Definition: tclique.h:39
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:9123
SCIP_RETCODE SCIPincludePricerColoring(SCIP *scip)
#define PRICER_DELAY
SCIP_EXPORT int * tcliqueGetDegrees(TCLIQUE_GRAPH *tcliquegraph)
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:496
#define MAXDELTA
static SCIP_DECL_PRICEREXITSOL(pricerExitsolColoring)