Scippy

SCIP

Solving Constraint Integer Programs

cons_storeGraph.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 cons_storeGraph.c
26  * @brief constraint handler for storing the graph at each node of the tree
27  * @author Gerald Gamrath
28  *
29  * This file implements the constraints that are used for the branching in the coloring algorithm.
30  *
31  * For each node in the branch-and-bound tree, a constraint of this type is created, which stores
32  * all restrictions related to that branch-and-bound node.
33  *
34  * First of all, it stores the type of the constraint ("same" or "differ", the root has type root)
35  * and the two nodes in the graph on which this restriction is applied. When the branch-and-bound
36  * node corresponding to the constraint is examined for the first time, the constraint creates a
37  * graph that takes into account all the restrictions, which are active at this node.
38  * At the root, this is the original (preprocessed) graph. At any other branch-and-bound node, it
39  * takes the graph of the constraint related to the branch-and-bound parent node of the current node and
40  * modifies it so that all restrictions up to this node are respected. Since the graph in the
41  * branch-and-bound parent respects all restrictions on the path to that node, only the last
42  * requirement, the one saved at the current branch-and-bound node, must be added.
43  * This is done as follows: Adding a DIFFER(v,w) constraint is easy, since it suffices to add
44  * an edge between v and w. For a SAME(v,w) constraint, the original idea is to collapse the nodes v
45  * and w into one single vertex. Since this is not possible in the tclique-graph data structure, we
46  * introduce new edges in the graph, so that v and w have the same neighborhood. Hence, in the
47  * pricing routine, each new stable set will either contain both nodes or none of them, since we
48  * create (inclusion-) maximal sets.
49  *
50  * This does of course not hold for sets created in a higher level of the branch-and-bound tree or
51  * in another subtree. In order to forbid all of these sets, which do not fulfill the current
52  * restrictions, a propagation is started when the node is entered the first time and repeated
53  * later, if the node is reentered after the creation of new variables in another subtree. The
54  * propagation simply fixes all variables to 0 which represent a stable set that does not
55  * fulfill the restriction at the current node.
56  *
57  * The information about all fusions of nodes (caused by the SAME() operation) is stored, so that the nodes
58  * constituting a union can be accessed easily. Each union has a representative and a set of nodes, whereas
59  * each node knows the representative of the union it belongs to. At the beginning, each node forms its own
60  * union and therefore each node also represents this union, consisting of only this node. Later on, some
61  * nodes represent unions of several nodes, while other nodes are part of a union which they do not represent,
62  * so they have another node as representative. The representatives of the nodes are returned by the methods
63  * COLORconsGetRepresentative() / COLORconsGetRepresentatives(), the union represented by a node is returned
64  * by COLORconsGetUnion(), the array of unions, indexed by the representing node, is returned by
65  * COLORconsGetUnions().
66  */
67 
68 #include <assert.h>
69 #include <string.h>
70 
71 #include "scip/type_cons.h"
72 #include "cons_storeGraph.h"
73 #include "probdata_coloring.h"
74 #include "tclique/tclique.h"
75 #include "reader_col.h"
76 #include "scip/cons_linear.h"
77 
78 
79 /* constraint handler properties */
80 #define CONSHDLR_NAME "storeGraph"
81 #define CONSHDLR_DESC "storing graph at nodes of the tree constraint handler"
82 #define CONSHDLR_ENFOPRIORITY 0 /**< priority of the constraint handler for constraint enforcing */
83 #define CONSHDLR_CHECKPRIORITY 2000000 /**< priority of the constraint handler for checking feasibility */
84 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
85 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
86  * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
87 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
88 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
89 
90 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
91 
92 
93 /** constraint data for storing graph constraints */
94 struct SCIP_ConsData
95 {
96  TCLIQUE_GRAPH* graph; /* the current graph in the B&B-node belonging to this constraint */
97  TCLIQUE_GRAPH* cgraph; /* the complementary graph of the current graph */
98  SCIP_CONS* fathercons; /* the constraint sticking at the B&B-node's father */
99  int* representativeofnode; /* r...[i] = j if node j is representative of the union containing node i */
100  int** unionofnode; /* for all represantatives of a union an array with all the union's members */
101  int* nnodesinunion; /* value at position i = #elements in unionofnode[i] */
102  int node1; /* first node for DIFFER / SAME */
103  int node2; /* second node for DIFFER / SAME */
104  COLOR_CONSTYPE type; /* type of the branching operation: COLOR_CONSTYPE_DIFFER oder COLOR_CONSTYPE_SAME */
105  int propagatedvars; /* number of Vars that existed, the last time, the related node was propagated,
106  used to determine whether the constraint should be repropagated*/
107  SCIP_Bool created; /* flag for saving the creation status of the graph saved in the cons,
108  at the beginning false, after the first activation set to true */
109  SCIP_NODE* stickingatnode; /* the node in the B&B-tree at which the cons is sticking */
110 };
111 
112 
113 /** constraint handler data */
114 struct SCIP_ConshdlrData
115 {
116  SCIP_CONS** stack; /**< stack for storing active constraints */
117  int nstack; /**< number of elements on the stack */
118  int maxstacksize; /**< maximum size of the stack */
119 };
120 
121 
122 /*
123  * Local methods
124  */
125 
126 /** creates and captures the storeGraph constraint for the root node*/
127 static
129  SCIP* scip, /**< SCIP data structure */
130  SCIP_CONS** cons, /**< pointer to hold the created constraint */
131  const char* name, /**< name of constraint */
132  TCLIQUE_GRAPH* graph /**< the original graph */
133  )
134 {
135  SCIP_CONSHDLR* conshdlr;
136  SCIP_CONSDATA* consdata;
137  int i;
138  int nnodes;
139 
140  assert(scip != NULL);
141  assert(graph != NULL);
142  nnodes = tcliqueGetNNodes(graph);
143  /* find the storeGraph constraint handler */
144  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
145  if ( conshdlr == NULL )
146  {
147  SCIPerrorMessage("storeGraph constraint handler not found\n");
148  return SCIP_PLUGINNOTFOUND;
149  }
150 
151  SCIPdebugMessage("Creating graph storage constraint at root node.\n");
152 
153  /* create constraint data */
154  SCIP_CALL( SCIPallocBlockMemory(scip, &consdata) );
155  consdata->graph = graph;
156  consdata->node1 = -1;
157  consdata->node2 = -1;
158  consdata->type = COLOR_CONSTYPE_ROOT;
159  consdata->fathercons = NULL;
160  consdata->propagatedvars = 0;
161  consdata->stickingatnode = NULL;
162  consdata->created = TRUE;
163 
164  /* allocate memory for the arrays and fill them */
165  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(consdata->representativeofnode), nnodes) );
166  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(consdata->nnodesinunion), nnodes) );
167  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(consdata->unionofnode), nnodes) );
168  for ( i = 0; i < nnodes; i++ )
169  {
170  consdata->representativeofnode[i] = i;
171  consdata->nnodesinunion[i] = 1;
172  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(consdata->unionofnode[i]), 1) ); /*lint !e866*/
173  consdata->unionofnode[i][0] = i;
174  }
175 
176  /* create the complementary graph */
177  if( !tcliqueCreate(&(consdata->cgraph)) )
178  {
179  SCIPerrorMessage("could not flush the clique graph\n");
180  return SCIP_ERROR;
181  }
182 
183  assert(consdata->cgraph != NULL);
184 
185  SCIP_CALL( COLORprobGetComplementaryGraph(scip, graph, consdata->cgraph) );
186 
187  /* create constraint */
188  SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, FALSE, FALSE, FALSE, FALSE, FALSE,
189  TRUE, FALSE, TRUE, FALSE, FALSE));
190 
191  return SCIP_OKAY;
192 }
193 
194 
195 /*
196  * Callback methods
197  */
198 
199 #ifdef SCIP_DISABLED_CODE
200 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
201 /** We do not want to copy store graph constraints into subSCIPs since they just store information about
202  * branching decisions and are used to enforce those.
203  * However, in subSCIPs, we only want to solve the current MIP with a branch-and-cut approach.
204  */
205 #define conshdlrCopyStoreGraph NULL
206 #endif
207 
208 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
209 static
210 SCIP_DECL_CONSFREE(consFreeStoreGraph)
211 {
212  SCIP_CONSHDLRDATA* conshdlrData;
213 
214  assert(scip != NULL);
215  assert(conshdlr != NULL);
216  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
217 
218  conshdlrData = SCIPconshdlrGetData(conshdlr);
219  assert(conshdlrData != NULL);
220 
221  SCIPdebugMessage("freeing store graph constraint handler\n");
222 
223  /* free constraint handler storage */
224  assert(conshdlrData->stack == NULL);
225  SCIPfreeBlockMemory(scip, &conshdlrData);
226 
227  return SCIP_OKAY;
228 }
229 
230 
231 /** solving process initialization method of constraint handler (called when branch and bound process is about to begin) */
232 static
233 SCIP_DECL_CONSINITSOL(consInitsolStoreGraph)
234 {
235  SCIP_CONSHDLRDATA* conshdlrData;
236  SCIP_CONS* cons;
237  assert(scip != NULL);
238  assert(conshdlr != NULL);
239  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
240 
241  conshdlrData = SCIPconshdlrGetData(conshdlr);
242  assert(conshdlrData != NULL);
243 
244  /* prepare stack */
245  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &conshdlrData->stack, conshdlrData->maxstacksize) );
246  SCIP_CALL( createConsStoreGraphAtRoot(scip, &cons, "root", COLORprobGetGraph(scip)) );
247 
248  /* release constraints */
249  conshdlrData->stack[0] = cons;
250  conshdlrData->nstack = 1;
251 
252  return SCIP_OKAY;
253 }/*lint !e715*/
254 
255 
256 /** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
257 static
258 SCIP_DECL_CONSEXITSOL(consExitsolStoreGraph)
259 {
260  SCIP_CONSHDLRDATA* conshdlrData;
261 
262  assert(scip != NULL);
263  assert(conshdlr != NULL);
264  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
265 
266  conshdlrData = SCIPconshdlrGetData(conshdlr);
267  assert(conshdlrData != NULL);
268  assert(conshdlrData->nstack == 1); /* at this point the stack should only have the root-constraint on it */
269  SCIP_CALL( SCIPreleaseCons(scip, &(conshdlrData->stack[0])) );
270  conshdlrData->stack[0] = NULL;
271  SCIPdebugMessage("exiting store graph constraint handler\n");
272 
273  /* free stack */
274  SCIPfreeBlockMemoryArray(scip, &conshdlrData->stack, conshdlrData->maxstacksize);
275 
276  return SCIP_OKAY;
277 }/*lint !e715*/
278 
279 
280 /** frees specific constraint data */
281 static
282 SCIP_DECL_CONSDELETE(consDeleteStoreGraph)
283 {
284  int i;
285 
286  assert(scip != NULL);
287  assert(conshdlr != NULL);
288  assert(cons != NULL);
289  assert(consdata != NULL);
290  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
291  assert(*consdata != NULL);
292 
293  SCIPdebugMessage("Deleting store graph constraint: <%s(%d,%d)>.\n", SCIPconsGetName(cons), (*consdata)->node1+1, (*consdata)->node2+1);
294 
295  /* free constraint data */
296  if ( (*consdata)->type == COLOR_CONSTYPE_ROOT )
297  {
298  for ( i = tcliqueGetNNodes((*consdata)->graph)-1; i >= 0; i-- )
299  {
300  SCIPfreeBlockMemoryArray(scip, &((*consdata)->unionofnode[i]), (*consdata)->nnodesinunion[i]); /*lint !e866*/
301  assert((*consdata)->nnodesinunion[i] == 1);
302  }
303  SCIPfreeBlockMemoryArray(scip, &((*consdata)->unionofnode), tcliqueGetNNodes((*consdata)->graph));
304  SCIPfreeBlockMemoryArray(scip, &((*consdata)->nnodesinunion), tcliqueGetNNodes((*consdata)->graph));
305  SCIPfreeBlockMemoryArray(scip, &((*consdata)->representativeofnode), tcliqueGetNNodes((*consdata)->graph));
306  tcliqueFree(&((*consdata)->cgraph));
307  }
308  else
309  {
310  if ((*consdata)->created)
311  {
312  for ( i = tcliqueGetNNodes((*consdata)->graph)-1; i >= 0; i-- )
313  {
314  if ( (*consdata)->nnodesinunion[i] > 0 )
315  {
316  SCIPfreeBlockMemoryArray(scip, &((*consdata)->unionofnode[i]), (*consdata)->nnodesinunion[i]); /*lint !e866*/
317  (*consdata)->unionofnode[i] = NULL;
318  }
319  }
320  SCIPfreeBlockMemoryArray(scip, &((*consdata)->unionofnode), tcliqueGetNNodes((*consdata)->graph));
321  SCIPfreeBlockMemoryArray(scip, &((*consdata)->nnodesinunion), tcliqueGetNNodes((*consdata)->graph));
322  SCIPfreeBlockMemoryArray(scip, &((*consdata)->representativeofnode), tcliqueGetNNodes((*consdata)->graph));
323 
324  (*consdata)->unionofnode = NULL;
325  (*consdata)->representativeofnode = NULL;
326  (*consdata)->nnodesinunion = NULL;
327 
328  if ((*consdata)->graph != NULL)
329  {
330  tcliqueFree(&((*consdata)->graph));
331  }
332  if ((*consdata)->cgraph != NULL)
333  {
334  tcliqueFree(&((*consdata)->cgraph));
335  }
336  }
337  }
338  SCIPfreeBlockMemory(scip, consdata);
339 
340  return SCIP_OKAY;
341 }
342 
343 
344 /** constraint enforcing method of constraint handler for LP solutions */
345 static
346 SCIP_DECL_CONSENFOLP(consEnfolpStoreGraph)
347 {
348  assert(scip != NULL);
349  assert(conshdlr != NULL);
350  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
351  assert(result != NULL);
352 
353  /* do nothing */
354  *result = SCIP_FEASIBLE;
355 
356  return SCIP_OKAY;
357 }/*lint !e715*/
358 
359 
360 /** constraint enforcing method of constraint handler for pseudo solutions */
361 static
362 SCIP_DECL_CONSENFOPS(consEnfopsStoreGraph)
363 {
364  assert(scip != NULL);
365  assert(conshdlr != NULL);
366  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
367  assert(result != NULL);
368 
369  /* do nothing */
370  *result = SCIP_FEASIBLE;
371 
372  return SCIP_OKAY;
373 }/*lint !e715*/
374 
375 
376 /** feasibility check method of constraint handler for integral solutions */
377 static
378 SCIP_DECL_CONSCHECK(consCheckStoreGraph)
379 {
380  assert(scip != NULL);
381  assert(conshdlr != NULL);
382  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
383  assert(result != NULL);
384 
385  /* do nothing */
386  *result = SCIP_FEASIBLE;
387 
388  return SCIP_OKAY;
389 }/*lint !e715*/
390 
391 
392 /** variable rounding lock method of constraint handler */
393 static
394 SCIP_DECL_CONSLOCK(consLockStoreGraph)
395 {
396  assert(scip != NULL);
397  assert(conshdlr != NULL);
398  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
399  assert(cons != NULL);
400 
401  SCIPdebugMessage("Locking method for store graph constraint: <%s>.\n", SCIPconsGetName(cons));
402 
403  return SCIP_OKAY;
404 }/*lint !e715*/
405 
406 
407 /** constraint activation notification method of constraint handler */
408 static
409 SCIP_DECL_CONSACTIVE(consActiveStoreGraph)
410 {
411  SCIP_CONSHDLRDATA* conshdlrData;
412  SCIP_CONSDATA* consdata;
413  SCIP_CONSDATA* olddata;
414  TCLIQUE_GRAPH* fathergraph;
415  int i;
416  int j;
417  int* firstedge;
418  int* lastedge;
419  int inserted;
420  int nnodes;
421 
422  assert(conshdlr != NULL);
423  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
424  assert(cons != NULL);
425 
426  conshdlrData = SCIPconshdlrGetData(conshdlr);
427  assert(conshdlrData != NULL);
428  assert(conshdlrData->stack != NULL);
429 
430  consdata = SCIPconsGetData(cons);
431  assert(consdata != NULL);
432  assert((consdata->type == COLOR_CONSTYPE_ROOT) || (consdata->fathercons != NULL));
433 
434  SCIPdebugMessage("Activating store graph constraint: <%s(%d,%d)> [stack size: %d].\n", SCIPconsGetName(cons),
435  (consdata->node1+1), (consdata->node2+1), conshdlrData->nstack+1);
436 
437  /* put constraint on the stack */
438  if ( conshdlrData->nstack >= conshdlrData->maxstacksize )
439  {
440  int newsize = SCIPcalcMemGrowSize(scip, conshdlrData->nstack + 1);
441 
442  SCIPdebugMessage("reallocating Memory for stack! %d --> %d\n", conshdlrData->maxstacksize, newsize);
443 
444  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(conshdlrData->stack), conshdlrData->maxstacksize, newsize) ); /*lint !e715 !e647*/
445  conshdlrData->maxstacksize = newsize;
446  }
447  conshdlrData->stack[conshdlrData->nstack] = cons;
448  ++(conshdlrData->nstack);
449 
450  /* if the current graph was not yet created, create it now */
451  if ( consdata->created == FALSE )
452  {
453  consdata->created = TRUE;
454  olddata = SCIPconsGetData(consdata->fathercons);
455  assert((consdata->type == COLOR_CONSTYPE_ROOT)
456  || (consdata->node1 == olddata->representativeofnode[consdata->node1]
457  && consdata->node2 == olddata->representativeofnode[consdata->node2]));
458  nnodes = tcliqueGetNNodes(olddata->graph);
459  fathergraph = olddata->graph;
460 
461  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(consdata->representativeofnode), nnodes) );
462  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(consdata->nnodesinunion), nnodes) );
463  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(consdata->unionofnode), nnodes) );
464 
465  for ( i = 0; i < nnodes; i++ )
466  {
467  consdata->representativeofnode[i] = olddata->representativeofnode[i];
468  consdata->nnodesinunion[i] = olddata->nnodesinunion[i];
469  if ( consdata->nnodesinunion[i] > 0 )
470  {
471  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(consdata->unionofnode[i]), consdata->nnodesinunion[i]) ); /*lint !e866*/
472  for ( j = 0; j < consdata->nnodesinunion[i]; j++ )
473  {
474  consdata->unionofnode[i][j] = olddata->unionofnode[i][j];
475  }
476  }
477  }
478 
479  /* copy the graph */
480  if( !tcliqueCreate(&(consdata->graph)) )
481  {
482  SCIPerrorMessage("could not flush the clique graph\n");
483  return SCIP_ERROR;
484  }
485 
486  if( !tcliqueAddNode((consdata)->graph, nnodes-1, 0) )
487  {
488  SCIPerrorMessage("could not add a node to the clique graph\n");
489  return SCIP_ERROR;
490  }
491 
492  for ( i = 0; i < nnodes; i++ )
493  {
494  /* get adjacent nodes for node i and add them to new graph*/
495  firstedge = tcliqueGetFirstAdjedge(fathergraph, i);
496  lastedge = tcliqueGetLastAdjedge(fathergraph, i);
497  while ( firstedge <= lastedge )
498  {
499  if ( *firstedge > i )
500  {
501  if( !tcliqueAddEdge(consdata->graph, i, *firstedge) )
502  {
503  SCIPerrorMessage("could not add an edge to the clique graph\n");
504  return SCIP_ERROR;
505  }
506  }
507  firstedge++;
508  }
509  }
510 
511  if( !tcliqueFlush(consdata->graph) )
512  {
513  SCIPerrorMessage("could not flush the clique graph\n");
514  return SCIP_ERROR;
515  }
516 
517  assert(consdata->representativeofnode[consdata->node2] == consdata->node2);
518  assert(consdata->representativeofnode[consdata->node1] == consdata->node1);
519 
520  /* type == COLOR_CONSTYPE_DIFFER --> insert edge between node1 and node2 */
521  if (consdata->type == COLOR_CONSTYPE_DIFFER)
522  {
523  for ( i = 0; i < consdata->nnodesinunion[consdata->representativeofnode[consdata->node2]]; i++ )
524  {
525  for ( j = 0; j < consdata->nnodesinunion[consdata->representativeofnode[consdata->node1]]; j++ )
526  {
527  if( !tcliqueAddEdge(consdata->graph, consdata->unionofnode[consdata->representativeofnode[consdata->node1]][j],
528  consdata->unionofnode[consdata->representativeofnode[consdata->node2]][i])
529  )
530  {
531  SCIPerrorMessage("could not add an edge to the clique graph\n");
532  return SCIP_ERROR;
533  }
534  }
535  }
536 
537  if( !tcliqueFlush(consdata->graph) )
538  {
539  SCIPerrorMessage("could not flush the clique graph\n");
540  return SCIP_ERROR;
541  }
542  }
543  /* type == COLOR_CONSTYPE_SAME --> insert edge (node2, i) - if not yet existing - if there exists an edge (node1, i) and vice versa */
544  else
545  {
546  assert(consdata->type == COLOR_CONSTYPE_SAME);
547  inserted = 0;
548 
549  /* add edges from all nodes of union2 to all nodes adjacent to union1 */
550  for ( i = 0; i < consdata->nnodesinunion[consdata->node2]; i++ )
551  {
552  /* set representative of nodes in the union of node2 */
553  consdata->representativeofnode[consdata->unionofnode[consdata->node2][i]] = consdata->node1;
554 
555  /* insert edges to all nodes adjacent to node1 */
556  firstedge = tcliqueGetFirstAdjedge(fathergraph, consdata->node1);
557  lastedge = tcliqueGetLastAdjedge(fathergraph, consdata->node1);
558  while ( firstedge <= lastedge )
559  {
560  if ( !tcliqueIsEdge(fathergraph, *firstedge, consdata->node2) )
561  {
562  if( !tcliqueAddEdge(consdata->graph, consdata->unionofnode[consdata->node2][i], *firstedge) )
563  {
564  SCIPerrorMessage("could not add an edge to the clique graph\n");
565  return SCIP_ERROR;
566  }
567  inserted++;
568  }
569  firstedge++;
570  }
571  }
572  /* add edges from all nodes of union1 to all nodes adjacent to union2 */
573  for ( i = 0; i < consdata->nnodesinunion[consdata->node1]; i++ )
574  {
575  /* insert edges to all nodes adjacent to node2 */
576  firstedge = tcliqueGetFirstAdjedge(fathergraph, consdata->node2);
577  lastedge = tcliqueGetLastAdjedge(fathergraph, consdata->node2);
578  while ( firstedge <= lastedge )
579  {
580  if ( !tcliqueIsEdge(fathergraph, *firstedge, consdata->node1) )
581  {
582  if( ! tcliqueAddEdge(consdata->graph, consdata->unionofnode[consdata->node1][i], *firstedge) )
583  {
584  SCIPerrorMessage("could not add an edge to the clique graph\n");
585  return SCIP_ERROR;
586  }
587  inserted++;
588  }
589  firstedge++;
590  }
591  }
592  if ( inserted > 0 )
593  {
594  if( !tcliqueFlush(consdata->graph) )
595  {
596  SCIPerrorMessage("could not flush the clique graph\n");
597  return SCIP_ERROR;
598  }
599  }
600 
601  /* update union represented by node1 */
602  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(consdata->unionofnode[consdata->node1]),
603  consdata->nnodesinunion[consdata->node1],
604  (consdata->nnodesinunion[consdata->node1]) + (consdata->nnodesinunion[consdata->node2])) ); /*lint !e866*/
605  for ( i = 0; i < consdata->nnodesinunion[consdata->node2]; i ++ )
606  {
607  consdata->unionofnode[consdata->node1][consdata->nnodesinunion[consdata->node1]+i]
608  = consdata->unionofnode[consdata->node2][i];
609  }
610  SCIPfreeBlockMemoryArray(scip, &(consdata->unionofnode[consdata->node2]),
611  consdata->nnodesinunion[consdata->node2]); /*lint !e866*/
612  consdata->nnodesinunion[consdata->node1] =
613  (consdata->nnodesinunion[consdata->node1]) + (consdata->nnodesinunion[consdata->node2]);
614  consdata->nnodesinunion[consdata->node2] = 0;
615  consdata->unionofnode[consdata->node2] = NULL;
616 
617  /* the constraint associated to node2 can be removed from this branch-and-bound node and its subtree */
618  SCIP_CALL( SCIPdelConsLocal(scip, COLORprobGetConstraint(scip, consdata->node2)));
619  }
620 
621  /* create the complementary graph */
622  if( !tcliqueCreate(&(consdata->cgraph)) )
623  {
624  SCIPerrorMessage("could not flush the clique graph\n");
625  return SCIP_ERROR;
626  }
627  assert(consdata->cgraph != NULL);
628  SCIP_CALL( COLORprobGetComplementaryGraph(scip, consdata->graph, consdata->cgraph) );
629  }
630  /* if new variables where created after the last propagation of this cons, repropagate it */
631  else
632  {
633  if ( (consdata->type != COLOR_CONSTYPE_ROOT) && (consdata->propagatedvars < SCIPgetNTotalVars(scip)) )
634  {
635  SCIP_CALL( SCIPrepropagateNode(scip, consdata->stickingatnode) );
636  }
637  }
638 
639  return SCIP_OKAY;
640 }
641 
642 
643 
644 /** constraint deactivation notification method of constraint handler */
645 static
646 SCIP_DECL_CONSDEACTIVE(consDeactiveStoreGraph)
647 {
648  SCIP_CONSHDLRDATA* conshdlrData;
649 #ifdef SCIP_DEBUG
650  SCIP_CONSDATA* consdata;
651 #endif
652 
653  assert(scip != NULL);
654  assert(conshdlr != NULL);
655  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
656  assert(cons != NULL);
657 
658  conshdlrData = SCIPconshdlrGetData(conshdlr);
659  assert(conshdlrData != NULL);
660  assert(conshdlrData->stack != NULL);
661  assert(conshdlrData->nstack > 0);
662  assert(cons == conshdlrData->stack[conshdlrData->nstack-1]);
663 
664 #ifdef SCIP_DEBUG
665  consdata = SCIPconsGetData(cons);
666 
667  SCIPdebugMessage("Deactivating store graph constraint: <%s(%d,%d)> [stack size: %d].\n", SCIPconsGetName(cons), (consdata->node1+1), (consdata->node2+1), conshdlrData->nstack-1);
668 #endif
669 
670  /* remove constraint from the stack */
671  --conshdlrData->nstack;
672 
673  return SCIP_OKAY;
674 }
675 
676 
677 
678 /** domain propagation method of constraint handler */
679 static
680 SCIP_DECL_CONSPROP(consPropStoreGraph)
681 {
682  SCIP_CONSHDLRDATA* conshdlrData;
683  SCIP_CONS* cons;
684  SCIP_CONSDATA* consdata;
685  SCIP_VAR* var;
686  int** sets;
687  int* nsetelements;
688  int nsets;
689  int i;
690  int propcount;
691 
692  assert(conshdlr != NULL);
693  conshdlrData = SCIPconshdlrGetData(conshdlr);
694  assert(conshdlrData != NULL);
695  assert(conshdlrData->stack != NULL);
696 
697  /* get all stable sets */
698  COLORprobGetStableSets(scip, &sets, &nsetelements, &nsets);
699  *result = SCIP_DIDNOTFIND;
700  propcount = 0;
701 
702  /* the constraint data of the cons related to the current node */
703  cons = conshdlrData->stack[conshdlrData->nstack-1];
704  consdata = SCIPconsGetData(cons);
705 
706  SCIPdebugMessage( "Starting propagation of store graph constraint <%s(%d,%d)> .\n", SCIPconsGetName(cons), (consdata->node1+1), (consdata->node2+1));
707 
708  /* propagation for differ: set upper bound to 0 for all stable sets, which contain both nodes */
709  if (consdata->type == COLOR_CONSTYPE_DIFFER)
710  {
711  for ( i = 0; i < nsets; i++ )
712  {
714  {
715  if ( COLORprobIsNodeInStableSet(scip, i, consdata->node1) && COLORprobIsNodeInStableSet(scip, i, consdata->node2) )
716  {
717  var = COLORprobGetVarForStableSet(scip, i);
718  SCIP_CALL( SCIPchgVarUb(scip, var, 0.0) );
719  propcount++;
720  }
721  }
722  }
723  }
724 
725  /* propagation for same: set upper bound to 0 for all stable sets, which do not contain both nodes */
726  if ( consdata->type == COLOR_CONSTYPE_SAME )
727  {
728  for ( i = 0; i < nsets; i++ )
729  {
731  {
732  if ( (COLORprobIsNodeInStableSet(scip, i, consdata->node1) || COLORprobIsNodeInStableSet(scip, i, consdata->node2))
733  && !(COLORprobIsNodeInStableSet(scip, i, consdata->node1) && COLORprobIsNodeInStableSet(scip, i, consdata->node2)) )
734  {
735  var = COLORprobGetVarForStableSet(scip, i);
736  SCIP_CALL( SCIPchgVarUb(scip, var, 0.0) );
737  propcount++;
738  }
739  }
740  }
741  }
742 
743  SCIPdebugMessage( "Finished propagation of store graph constraint <%s(%d,%d)>, %d vars fixed.\n", SCIPconsGetName(cons), (consdata->node1+1), (consdata->node2+1), propcount);
744 
746  consdata->propagatedvars = SCIPgetNTotalVars(scip);
747 
748  return SCIP_OKAY;
749 }/*lint !e715*/
750 
751 /*
752  * interface methods
753  */
754 
755 
756 /** creates the handler for storeGraph constraints and includes it in SCIP */
758  SCIP* scip /**< SCIP data structure */
759  )
760 {
761  SCIP_CONSHDLRDATA* conshdlrData;
762  SCIP_CONSHDLR* conshdlr;
763 
764  SCIPdebugMessage("Including graph storage constraint handler.\n");
765 
766  SCIP_CALL( SCIPallocBlockMemory(scip, &conshdlrData) );
767  conshdlrData->stack = NULL;
768  conshdlrData->nstack = 0;
769  conshdlrData->maxstacksize = 25;
770 
771  conshdlr = NULL;
772  /* include constraint handler */
775  consEnfolpStoreGraph, consEnfopsStoreGraph, consCheckStoreGraph, consLockStoreGraph,
776  conshdlrData) );
777  assert(conshdlr != NULL);
778 
779  SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteStoreGraph) );
780  SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeStoreGraph) );
781  SCIP_CALL( SCIPsetConshdlrInitsol(scip, conshdlr, consInitsolStoreGraph) );
782  SCIP_CALL( SCIPsetConshdlrExitsol(scip, conshdlr, consExitsolStoreGraph) );
783  SCIP_CALL( SCIPsetConshdlrActive(scip, conshdlr, consActiveStoreGraph) );
784  SCIP_CALL( SCIPsetConshdlrDeactive(scip, conshdlr, consDeactiveStoreGraph) );
785  SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropStoreGraph, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP,
787 
788  return SCIP_OKAY;
789 }
790 
791 /** creates and captures a storeGraph constraint, uses knowledge of the B&B-father*/
793  SCIP* scip, /**< SCIP data structure */
794  SCIP_CONS** cons, /**< pointer to hold the created constraint */
795  const char* name, /**< name of constraint */
796  SCIP_CONS* fatherconstraint, /**< constraint in B&B-father */
797  COLOR_CONSTYPE type, /**< type of the constraint: COLOR_CONSTYPE_SAME or COLOR_CONSTYPE_DIFFER */
798  int node1, /**< the first node of the constraint */
799  int node2, /**< the second node of the constraint */
800  SCIP_NODE* stickingnode /**< the B&B-tree node at which the constraint will be sticking */
801  )
802 {
803  SCIP_CONSHDLR* conshdlr;
804  SCIP_CONSDATA* consdata;
805  int temp;
806 
807  assert(scip != NULL);
808  assert(fatherconstraint != NULL);
809  assert(type == COLOR_CONSTYPE_SAME || type == COLOR_CONSTYPE_DIFFER);
810  assert(stickingnode != NULL);
811 
812  /* find the storeGraph constraint handler */
813  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
814  if ( conshdlr == NULL )
815  {
816  SCIPerrorMessage("storeGraph constraint handler not found\n");
817  return SCIP_PLUGINNOTFOUND;
818  }
819 
820  /* create constraint data */
821  SCIP_CALL( SCIPallocBlockMemory(scip, &consdata) );
822 
823  if ( node1 > node2 )
824  {
825  temp = node1;
826  node1 = node2;
827  node2 = temp;
828  }
829  SCIPdebugMessage("Creating store graph constraint: <%s(%d,%d)>. \n", name, (node1+1), (node2+1));
830 
831  consdata->node1 = node1;
832  consdata->node2 = node2;
833  consdata->type = type;
834  consdata->fathercons = fatherconstraint;
835  consdata->propagatedvars = 0;
836  consdata->stickingatnode = stickingnode;
837  consdata->created = FALSE;
838 
839 
840  /* create constraint */
841  SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, FALSE, FALSE, FALSE, FALSE, TRUE,
842  TRUE, FALSE, TRUE, FALSE, TRUE) );
843 
844  return SCIP_OKAY;
845 }
846 
847 
848 
849 
850 /* ----------------------------------- external methods -------------------------- */
851 
852 /** returns the store graph constraint of the current node, needs the pointer to the constraint handler */
854  SCIP_CONSHDLR* conshdlr /**< constaint handler for store-graph constraints */
855  )
856 {
857  SCIP_CONSHDLRDATA* conshdlrData;
858 
859  assert(conshdlr != NULL);
860  conshdlrData = SCIPconshdlrGetData(conshdlr);
861  assert(conshdlrData != NULL);
862  assert(conshdlrData->stack != NULL);
863 
864  return conshdlrData->stack[conshdlrData->nstack-1];
865 }
866 
867 
868 /** returns the store graph constraint of the current node, only needs the pointer to scip */
870  SCIP* scip /**< SCIP data structure */
871  )
872 {
873  SCIP_CONSHDLR* conshdlr;
874  SCIP_CONSHDLRDATA* conshdlrData;
875 
876  assert(scip != NULL);
877  conshdlr = SCIPfindConshdlr(scip, "storeGraph");
878  if ( conshdlr == NULL )
879  {
880  SCIPerrorMessage("storeGraph constraint handler not found\n");
881  return NULL;
882  }
883  conshdlrData = SCIPconshdlrGetData(conshdlr);
884  assert(conshdlrData != NULL);
885  assert(conshdlrData->stack != NULL);
886  assert(conshdlrData->nstack > 0);
887 
888  return conshdlrData->stack[conshdlrData->nstack-1];
889 }
890 
891 
892 /** returns the current graph */
894  SCIP* scip /**< SCIP data structure */
895  )
896 {
897  SCIP_CONSHDLR* conshdlr;
898  SCIP_CONS* cons;
899  SCIP_CONSDATA* consdata;
900  SCIP_CONSHDLRDATA* conshdlrData;
901 
902  assert(scip != NULL);
903  conshdlr = SCIPfindConshdlr(scip, "storeGraph");
904  if ( conshdlr == NULL )
905  {
906  SCIPerrorMessage("storeGraph constraint handler not found\n");
907  return NULL;
908  }
909  conshdlrData = SCIPconshdlrGetData(conshdlr);
910  assert(conshdlrData != NULL);
911  assert(conshdlrData->stack != NULL);
912  cons = conshdlrData->stack[conshdlrData->nstack-1];
913  assert(cons != NULL);
914 
915  consdata = SCIPconsGetData(cons);
916  return consdata->graph;
917 }
918 
919 
920 /** returns the complementary graph */
922  SCIP* scip /**< SCIP data structure */
923  )
924 {
925  SCIP_CONSHDLR* conshdlr;
926  SCIP_CONS* cons;
927  SCIP_CONSDATA* consdata;
928  SCIP_CONSHDLRDATA* conshdlrData;
929 
930  assert(scip != NULL);
931 
932  conshdlr = SCIPfindConshdlr(scip, "storeGraph");
933  if ( conshdlr == NULL )
934  {
935  SCIPerrorMessage("storeGraph constraint handler not found\n");
936  return NULL;
937  }
938 
939  conshdlrData = SCIPconshdlrGetData(conshdlr);
940  assert(conshdlrData != NULL);
941  assert(conshdlrData->stack != NULL);
942 
943  cons = conshdlrData->stack[conshdlrData->nstack-1];
944  assert(cons != NULL);
945 
946  consdata = SCIPconsGetData(cons);
947  return consdata->cgraph;
948 }
949 
950 
951 /** returns array of representatives of all nodes */
953  SCIP* scip /**< SCIP data structure */
954  )
955 {
956  SCIP_CONSHDLR* conshdlr;
957  SCIP_CONSHDLRDATA* conshdlrData;
958  SCIP_CONS* cons;
959  SCIP_CONSDATA* consdata;
960 
961  assert(scip != NULL);
962 
963  conshdlr = SCIPfindConshdlr(scip, "storeGraph");
964  if ( conshdlr == NULL )
965  {
966  SCIPerrorMessage("storeGraph constraint handler not found\n");
967  return NULL;
968  }
969 
970  conshdlrData = SCIPconshdlrGetData(conshdlr);
971  assert(conshdlrData != NULL);
972  assert(conshdlrData->stack != NULL);
973 
974  cons = conshdlrData->stack[conshdlrData->nstack-1];
975  consdata = SCIPconsGetData(cons);
976  return consdata->representativeofnode;
977 }
978 
979 /** returns the representative of the union which contains a given node */
981  SCIP* scip, /**< SCIP data structure */
982  int node /**< the node, for wich the representative is searched */
983  )
984 {
985  SCIP_CONSHDLR* conshdlr;
986  SCIP_CONSHDLRDATA* conshdlrData;
987  SCIP_CONS* cons;
988  SCIP_CONSDATA* consdata;
989 
990  assert(scip != NULL);
991 
992  conshdlr = SCIPfindConshdlr(scip, "storeGraph");
993  if ( conshdlr == NULL )
994  {
995  SCIPerrorMessage("storeGraph constraint handler not found\n");
996  return -1;
997  }
998 
999  conshdlrData = SCIPconshdlrGetData(conshdlr);
1000  assert(conshdlrData != NULL);
1001  assert(conshdlrData->stack != NULL);
1002 
1003  cons = conshdlrData->stack[conshdlrData->nstack-1];
1004  consdata = SCIPconsGetData(cons);
1005  assert(consdata != NULL);
1006 
1007  assert(node >= 0 && node < tcliqueGetNNodes(consdata->graph));
1008 
1009  return consdata->representativeofnode[node];
1010 }
1011 
1012 /** returns the array of all unions, a union is saved in the array at the position of its representative */
1013 void COLORconsGetUnions(
1014  SCIP* scip, /**< SCIP data structure */
1015  int*** unions, /**< output: array containing array which contains nodes in the union */
1016  int** lengths /**< output: lengths of the unions */
1017  )
1018 {
1019  SCIP_CONSHDLR* conshdlr;
1020  SCIP_CONSHDLRDATA* conshdlrData;
1021  SCIP_CONS* cons;
1022  SCIP_CONSDATA* consdata;
1023 
1024  assert(scip != NULL);
1025  conshdlr = SCIPfindConshdlr(scip, "storeGraph");
1026  if ( conshdlr == NULL )
1027  {
1028  SCIPerrorMessage("storeGraph constraint handler not found\n");
1029  return;
1030  }
1031 
1032  conshdlrData = SCIPconshdlrGetData(conshdlr);
1033  assert(conshdlrData != NULL);
1034  assert(conshdlrData->stack != NULL);
1035 
1036  cons = conshdlrData->stack[conshdlrData->nstack-1];
1037  consdata = SCIPconsGetData(cons);
1038  assert(consdata != NULL);
1039 
1040  *unions = consdata->unionofnode;
1041  *lengths = consdata->nnodesinunion;
1042 }
1043 
1044 /** returns the union which has a given node as representative */
1045 void COLORconsGetUnion(
1046  SCIP* scip, /**< SCIP data structure */
1047  int** nodesinunion, /**< output: array containig nodes in the union */
1048  int* nnodesinunion, /**< output: length of the union */
1049  int node /**< the node, whose union we want to get */
1050  )
1051 {
1052  SCIP_CONSHDLR* conshdlr;
1053  SCIP_CONSHDLRDATA* conshdlrData;
1054  SCIP_CONS* cons;
1055  SCIP_CONSDATA* consdata;
1056 
1057  assert(scip != NULL);
1058  conshdlr = SCIPfindConshdlr(scip, "storeGraph");
1059  if ( conshdlr == NULL )
1060  {
1061  SCIPerrorMessage("storeGraph constraint handler not found\n");
1062  return;
1063  }
1064  conshdlrData = SCIPconshdlrGetData(conshdlr);
1065  assert(conshdlrData != NULL);
1066  assert(conshdlrData->stack != NULL);
1067  cons = conshdlrData->stack[conshdlrData->nstack-1];
1068  consdata = SCIPconsGetData(cons);
1069  assert(consdata != NULL);
1070 
1071  *nodesinunion = consdata->unionofnode[node];
1072  *nnodesinunion = consdata->nnodesinunion[node];
1073 }
1074 
1075 /** returns the stack and the number of elements on it */
1076 void COLORconsGetStack(
1077  SCIP* scip, /**< SCIP data structure */
1078  SCIP_CONS*** stack, /**< return value: pointer to the stack */
1079  int* nstackelements /**< return value: pointer to int, for number of elements on the stack */
1080  )
1081 {
1082  SCIP_CONSHDLR* conshdlr;
1083  SCIP_CONSHDLRDATA* conshdlrData;
1084 
1085  assert(scip != NULL);
1086  conshdlr = SCIPfindConshdlr(scip, "storeGraph");
1087  if ( conshdlr == NULL )
1088  {
1089  SCIPerrorMessage("storeGraph constraint handler not found\n");
1090  return;
1091  }
1092  conshdlrData = SCIPconshdlrGetData(conshdlr);
1093  assert(conshdlrData != NULL);
1094  assert(conshdlrData != NULL);
1095  assert(conshdlrData->stack != NULL);
1096 
1097  *stack = conshdlrData->stack;
1098  *nstackelements = conshdlrData->nstack;
1099 }
1100 
1101 
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
#define CONSHDLR_PROPFREQ
SCIP_CONS * COLORconsGetActiveStoreGraphConsFromHandler(SCIP_CONSHDLR *conshdlr)
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
Definition: scip_cons.c:578
#define NULL
Definition: def.h:267
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
void tcliqueFree(TCLIQUE_GRAPH **tcliquegraph)
void COLORconsGetStack(SCIP *scip, SCIP_CONS ***stack, int *nstackelements)
TCLIQUE_Bool tcliqueCreate(TCLIQUE_GRAPH **tcliquegraph)
struct TCLIQUE_Graph TCLIQUE_GRAPH
Definition: tclique.h:49
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:941
problem data for vertex coloring algorithm
TCLIQUE_Bool tcliqueAddNode(TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:139
SCIP_CONS * COLORconsGetActiveStoreGraphCons(SCIP *scip)
SCIP_RETCODE SCIPsetConshdlrDeactive(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDEACTIVE((*consdeactive)))
Definition: scip_cons.c:693
SCIP_RETCODE COLORincludeConshdlrStoreGraph(SCIP *scip)
static SCIP_RETCODE createConsStoreGraphAtRoot(SCIP *scip, SCIP_CONS **cons, const char *name, TCLIQUE_GRAPH *graph)
#define CONSHDLR_NAME
static SCIP_DECL_CONSEXITSOL(consExitsolStoreGraph)
#define CONSHDLR_EAGERFREQ
#define FALSE
Definition: def.h:94
SCIP_RETCODE SCIPincludeConshdlrBasic(SCIP *scip, SCIP_CONSHDLR **conshdlrptr, const char *name, const char *desc, int enfopriority, int chckpriority, int eagerfreq, SCIP_Bool needscons, SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_CONSHDLRDATA *conshdlrdata)
Definition: scip_cons.c:181
#define TRUE
Definition: def.h:93
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
file reader for vertex coloring instances
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
void COLORprobGetStableSets(SCIP *scip, int ***stablesets, int **nelements, int *nstablesets)
#define SCIPdebugMessage
Definition: pub_message.h:96
tclique user interface
constraint handler for storing the graph at each node of the tree
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
static SCIP_DECL_CONSDELETE(consDeleteStoreGraph)
#define CONSHDLR_ENFOPRIORITY
#define CONSHDLR_PROP_TIMING
SCIP_RETCODE SCIPcreateCons(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONSHDLR *conshdlr, SCIP_CONSDATA *consdata, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: scip_cons.c:998
SCIP_RETCODE SCIPrepropagateNode(SCIP *scip, SCIP_NODE *node)
Definition: scip_tree.c:477
unsigned int stickingatnode
Definition: struct_cons.h:79
SCIP_RETCODE SCIPsetConshdlrInitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITSOL((*consinitsol)))
Definition: scip_cons.c:444
SCIP_CONS * COLORprobGetConstraint(SCIP *scip, int node)
TCLIQUE_GRAPH * COLORprobGetGraph(SCIP *scip)
static SCIP_DECL_CONSCHECK(consCheckStoreGraph)
TCLIQUE_Bool tcliqueAddEdge(TCLIQUE_GRAPH *tcliquegraph, int node1, int node2)
#define SCIPerrorMessage
Definition: pub_message.h:64
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4199
int COLORconsGetRepresentative(SCIP *scip, int node)
SCIP_RETCODE SCIPdelConsLocal(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:3474
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8216
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4768
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:372
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4219
#define SCIP_CALL(x)
Definition: def.h:380
int SCIPgetNTotalVars(SCIP *scip)
Definition: scip_prob.c:2569
#define CONSHDLR_NEEDSCONS
SCIP_VAR * COLORprobGetVarForStableSet(SCIP *scip, int setindex)
static SCIP_DECL_CONSLOCK(consLockStoreGraph)
struct SCIP_ConsData SCIP_CONSDATA
Definition: type_cons.h:65
void COLORconsGetUnion(SCIP *scip, int **nodesinunion, int *nnodesinunion, int node)
#define SCIP_Bool
Definition: def.h:91
SCIP_Bool COLORprobIsNodeInStableSet(SCIP *scip, int setindex, int node)
int * tcliqueGetLastAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
SCIP_RETCODE COLORprobGetComplementaryGraph(SCIP *scip, TCLIQUE_GRAPH *graph, TCLIQUE_GRAPH *cgraph)
static SCIP_DECL_CONSDEACTIVE(consDeactiveStoreGraph)
static SCIP_DECL_CONSENFOLP(consEnfolpStoreGraph)
int * tcliqueGetFirstAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
static SCIP_DECL_CONSINITSOL(consInitsolStoreGraph)
int * COLORconsGetRepresentatives(SCIP *scip)
Constraint handler for linear constraints in their most general form, .
#define CONSHDLR_CHECKPRIORITY
#define CONSHDLR_DELAYPROP
TCLIQUE_GRAPH * COLORconsGetComplementaryGraph(SCIP *scip)
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
Definition: cons.c:8246
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1174
static SCIP_DECL_CONSENFOPS(consEnfopsStoreGraph)
enum COLOR_ConsType COLOR_CONSTYPE
static SCIP_DECL_CONSPROP(consPropStoreGraph)
#define CONSHDLR_DESC
SCIP_RETCODE COLORcreateConsStoreGraph(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONS *fatherconstraint, COLOR_CONSTYPE type, int node1, int node2, SCIP_NODE *stickingnode)
static SCIP_DECL_CONSFREE(consFreeStoreGraph)
TCLIQUE_Bool tcliqueFlush(TCLIQUE_GRAPH *tcliquegraph)
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition: type_cons.h:64
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18145
#define nnodes
Definition: gastrans.c:74
void COLORconsGetUnions(SCIP *scip, int ***unions, int **lengths)
TCLIQUE_GRAPH * COLORconsGetCurrentGraph(SCIP *scip)
SCIP_RETCODE SCIPsetConshdlrActive(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSACTIVE((*consactive)))
Definition: scip_cons.c:670
SCIP_RETCODE SCIPsetConshdlrExitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITSOL((*consexitsol)))
Definition: scip_cons.c:468
static SCIP_DECL_CONSACTIVE(consActiveStoreGraph)
type definitions for constraints and constraint handlers
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)
Definition: scip_cons.c:281