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