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-2019 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 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"
41 #include "reader_col.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 */
691  SCIP_CALL( COLORprobAddNewStableSet(pricerdata->scip, pricerdata->improvingstablesets[i],
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 */
710  SCIP_CALL( SCIPaddCoefSetppc(pricerdata->scip,
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:116
static SCIP_Bool hasUncoloredNode(TCLIQUE_GRAPH *graph, SCIP_Bool *colored)
#define MAXSCALE
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
#define NULL
Definition: def.h:246
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:99
const char * SCIPpricerGetName(SCIP_PRICER *pricer)
Definition: pricer.c:588
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:158
SCIP_RETCODE SCIPaddCoefSetppc(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_setppc.c:9229
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_Real SCIPgetPrimalbound(SCIP *scip)
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
#define MAXDNOM
SCIP_RETCODE SCIPchgVarUbLazy(SCIP *scip, SCIP_VAR *var, SCIP_Real lazyub)
Definition: scip_var.c:5085
#define FALSE
Definition: def.h:72
#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:10561
SCIP_Real SCIPinfinity(SCIP *scip)
#define TRUE
Definition: def.h:71
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_PRICERDATA * SCIPpricerGetData(SCIP_PRICER *pricer)
Definition: pricer.c:501
#define PRICER_DESC
file reader for vertex coloring instances
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:114
void SCIPvarMarkDeletable(SCIP_VAR *var)
Definition: var.c:16963
void COLORprobGetStableSets(SCIP *scip, int ***stablesets, int **nelements, int *nstablesets)
#define SCIPdebugMessage
Definition: pub_message.h:77
SCIP_RETCODE SCIPsetPricerExitsol(SCIP *scip, SCIP_PRICER *pricer, SCIP_DECL_PRICEREXITSOL((*pricerexitsol)))
Definition: scip_pricer.c:365
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:142
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:97
SCIP_NODE * SCIPgetRootNode(SCIP *scip)
Definition: scip_tree.c:177
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:155
SCIP * scip
Definition: cons_sos1.c:232
static SCIP_RETCODE greedyStableSet(SCIP *scip, TCLIQUE_GRAPH *graph, SCIP_Bool *colored, int *maxstablesetnodes, int *nmaxstablesetnodes)
static SCIP_Longint getIntegralVal(SCIP_Real val, SCIP_Real scalar, SCIP_Real mindelta, SCIP_Real maxdelta)
#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:197
SCIP_Real SCIPgetDualsolSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9314
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)
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:358
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:191
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:130
SCIP_Bool COLORprobStableSetIsNew(SCIP *scip, int *stablesetnodes, int nstablesetnodes)
#define SCIP_Bool
Definition: def.h:69
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:226
SCIP_CONS ** COLORprobGetConstraints(SCIP *scip)
SCIP_Bool SCIPvarIsInLP(SCIP_VAR *var)
Definition: var.c:17069
int COLORprobGetNStableSets(SCIP *scip)
static SCIP_DECL_PRICERINITSOL(pricerInitsolColoring)
#define DEFAULT_MAXTCLIQUENODES
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:578
SCIP_RETCODE SCIPsetPricerFree(SCIP *scip, SCIP_PRICER *pricer, SCIP_DECL_PRICERFREE((*pricerfree)))
Definition: scip_pricer.c:269
#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:104
static SCIP_DECL_PRICERFREE(pricerFreeColoring)
SCIP_RETCODE SCIPsetPricerInitsol(SCIP *scip, SCIP_PRICER *pricer, SCIP_DECL_PRICERINITSOL((*pricerinitsol)))
Definition: scip_pricer.c:341
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:2044
SCIP_RETCODE SCIPaddPricedVar(SCIP *scip, SCIP_VAR *var, SCIP_Real score)
Definition: scip_prob.c:1789
TCLIQUE_GRAPH * COLORconsGetComplementaryGraph(SCIP *scip)
#define MAX(x, y)
Definition: def.h:215
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip_lp.c:305
#define DEFAULT_USETCLIQUE
void SCIPsortDownInt(int *intarray, int len)
#define SCIP_Real
Definition: def.h:157
#define SCIP_Longint
Definition: def.h:142
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
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:245
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17410
#define nnodes
Definition: gastrans.c:65
#define PRICER_PRIORITY
#define EPSFLOOR(x, eps)
Definition: def.h:190
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:119
TCLIQUE_GRAPH * COLORconsGetCurrentGraph(SCIP *scip)
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:129
static SCIP_DECL_PRICEREXITSOL(pricerExitsolColoring)