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 */
94struct 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 */
114struct 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*/
127static
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 */
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) */
209static
210SCIP_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) */
232static
233SCIP_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) );
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) */
257static
258SCIP_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 */
281static
282SCIP_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 */
345static
346SCIP_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 */
361static
362SCIP_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 */
377static
378SCIP_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 */
393static
394SCIP_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 */
408static
409SCIP_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 */
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 */
645static
646SCIP_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 */
679static
680SCIP_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 {
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 {
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) );
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 */
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 */
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 */
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 */
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
Constraint handler for linear constraints in their most general form, .
#define CONSHDLR_NEEDSCONS
int * COLORconsGetRepresentatives(SCIP *scip)
#define CONSHDLR_CHECKPRIORITY
#define CONSHDLR_DESC
TCLIQUE_GRAPH * COLORconsGetCurrentGraph(SCIP *scip)
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_CONSPROP(consPropStoreGraph)
#define CONSHDLR_PROP_TIMING
static SCIP_DECL_CONSENFOPS(consEnfopsStoreGraph)
static SCIP_DECL_CONSLOCK(consLockStoreGraph)
void COLORconsGetUnions(SCIP *scip, int ***unions, int **lengths)
static SCIP_DECL_CONSEXITSOL(consExitsolStoreGraph)
void COLORconsGetUnion(SCIP *scip, int **nodesinunion, int *nnodesinunion, int node)
static SCIP_DECL_CONSFREE(consFreeStoreGraph)
SCIP_CONS * COLORconsGetActiveStoreGraphConsFromHandler(SCIP_CONSHDLR *conshdlr)
int COLORconsGetRepresentative(SCIP *scip, int node)
static SCIP_DECL_CONSDELETE(consDeleteStoreGraph)
static SCIP_DECL_CONSACTIVE(consActiveStoreGraph)
#define CONSHDLR_PROPFREQ
#define CONSHDLR_EAGERFREQ
static SCIP_DECL_CONSCHECK(consCheckStoreGraph)
#define CONSHDLR_ENFOPRIORITY
TCLIQUE_GRAPH * COLORconsGetComplementaryGraph(SCIP *scip)
SCIP_RETCODE COLORincludeConshdlrStoreGraph(SCIP *scip)
static SCIP_DECL_CONSINITSOL(consInitsolStoreGraph)
static SCIP_DECL_CONSDEACTIVE(consDeactiveStoreGraph)
static SCIP_DECL_CONSENFOLP(consEnfolpStoreGraph)
#define CONSHDLR_NAME
SCIP_CONS * COLORconsGetActiveStoreGraphCons(SCIP *scip)
#define CONSHDLR_DELAYPROP
static SCIP_RETCODE createConsStoreGraphAtRoot(SCIP *scip, SCIP_CONS **cons, const char *name, TCLIQUE_GRAPH *graph)
void COLORconsGetStack(SCIP *scip, SCIP_CONS ***stack, int *nstackelements)
constraint handler for storing the graph at each node of the tree
@ COLOR_CONSTYPE_ROOT
@ COLOR_CONSTYPE_DIFFER
@ COLOR_CONSTYPE_SAME
enum COLOR_ConsType COLOR_CONSTYPE
#define NULL
Definition: def.h:267
#define SCIP_Bool
Definition: def.h:91
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define SCIP_CALL(x)
Definition: def.h:374
#define nnodes
Definition: gastrans.c:74
int SCIPgetNTotalVars(SCIP *scip)
Definition: scip_prob.c:2569
SCIP_RETCODE SCIPdelConsLocal(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:3474
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
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
SCIP_RETCODE SCIPsetConshdlrDeactive(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDEACTIVE((*consdeactive)))
Definition: scip_cons.c:693
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
Definition: scip_cons.c:578
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:372
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4197
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:941
SCIP_RETCODE SCIPsetConshdlrExitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITSOL((*consexitsol)))
Definition: scip_cons.c:468
SCIP_RETCODE SCIPsetConshdlrInitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITSOL((*consinitsol)))
Definition: scip_cons.c:444
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4217
SCIP_RETCODE SCIPsetConshdlrActive(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSACTIVE((*consactive)))
Definition: scip_cons.c:670
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
Definition: cons.c:8244
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
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8214
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1174
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:139
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPrepropagateNode(SCIP *scip, SCIP_NODE *node)
Definition: scip_tree.c:477
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18144
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4766
SCIP_VAR * COLORprobGetVarForStableSet(SCIP *scip, int setindex)
void COLORprobGetStableSets(SCIP *scip, int ***stablesets, int **nelements, int *nstablesets)
SCIP_CONS * COLORprobGetConstraint(SCIP *scip, int node)
TCLIQUE_GRAPH * COLORprobGetGraph(SCIP *scip)
SCIP_RETCODE COLORprobGetComplementaryGraph(SCIP *scip, TCLIQUE_GRAPH *graph, TCLIQUE_GRAPH *cgraph)
SCIP_Bool COLORprobIsNodeInStableSet(SCIP *scip, int setindex, int node)
problem data for vertex coloring algorithm
#define SCIPerrorMessage
Definition: pub_message.h:64
#define SCIPdebugMessage
Definition: pub_message.h:96
file reader for vertex coloring instances
unsigned int stickingatnode
Definition: struct_cons.h:79
tclique user interface
int * tcliqueGetLastAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
void tcliqueFree(TCLIQUE_GRAPH **tcliquegraph)
int * tcliqueGetFirstAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
TCLIQUE_Bool tcliqueFlush(TCLIQUE_GRAPH *tcliquegraph)
struct TCLIQUE_Graph TCLIQUE_GRAPH
Definition: tclique.h:49
TCLIQUE_Bool tcliqueCreate(TCLIQUE_GRAPH **tcliquegraph)
TCLIQUE_Bool tcliqueAddNode(TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight)
TCLIQUE_Bool tcliqueAddEdge(TCLIQUE_GRAPH *tcliquegraph, int node1, int node2)
type definitions for constraints and constraint handlers
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition: type_cons.h:64
struct SCIP_ConsData SCIP_CONSDATA
Definition: type_cons.h:65
@ SCIP_FEASIBLE
Definition: type_result.h:45
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_PLUGINNOTFOUND
Definition: type_retcode.h:54
@ SCIP_OKAY
Definition: type_retcode.h:42
@ SCIP_ERROR
Definition: type_retcode.h:43
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63