Scippy

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