Scippy

SCIP

Solving Constraint Integer Programs

cons_storeGraph.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2019 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file cons_storeGraph.h
17  * @brief constraint handler for storing the graph at each node of the tree
18  * @author Gerald Gamrath
19  *
20  * This file implements the constraints that are used for the branching in the coloring algorithm.
21  *
22  * For each node in the branch-and-bound tree, a constraint of this type is created, which stores
23  * all restrictions related to that branch-and-bound node.
24  *
25  * First of all, it stores the type of the constraint ("same" or "differ", the root has type root)
26  * and the two nodes in the graph on which this restriction is applied. When the branch-and-bound
27  * node corresponding to the constraint is examined for the first time, the constraint creates a
28  * graph that takes into account all the restrictions, which are active at this node.
29  * At the root, this is the original (preprocessed) graph. At any other branch-and-bound node, it
30  * takes the graph of the constraint related to the branch-and-bound father of the current node and
31  * modifies it so that all restrictions up to this node are respected. Since the graph in the
32  * branch-and-bound father respects all restrictions on the path to that node, only the last
33  * requirement, the one saved at the current branch-and-bound node, must be added.
34  * This is done as follows: Adding a DIFFER(v,w) constraint is easy, since it suffices to add
35  * an edge between v and w. For a SAME(v,w) constraint, the original idea is to collapse the nodes v
36  * and w into one single vertex. Since this is not possible in the tclique-graph data structure, we
37  * introduce new edges in the graph, so that v and w have the same neighborhood. Hence, in the
38  * pricing routine, each new stable set will either contain both nodes or none of them, since we
39  * create (inclusion-) maximal sets.
40  *
41  * This does of course not hold for sets created in a higher level of the branch-and-bound tree or
42  * in another subtree. In order to forbid all of these sets, which do not fulfill the current
43  * restrictions, a propagation is started when the node is entered the first time and repeated
44  * later, if the node is reentered after the creation of new variables in another subtree. The
45  * propagation simply fixes to 0 all variables representing a stable set that does not
46  * fulfill the restriction at the current node.
47  *
48  * The information about all fusions of nodes (caused by the SAME() operation) is stored, so that the nodes
49  * constituting a union can be accessed easily. Each union has a representative and a set of nodes, whereas
50  * each node knows the representative of the union it belongs to. At the beginning, each node forms its own
51  * union and therefore each node also represents this union, consisting of only this node. Later on, some
52  * nodes represent unions of several nodes, while other nodes are part of a union which they do not represent,
53  * so they have another node as representative. The representatives of the nodes are returned by the methods
54  * COLORconsGetRepresentative() / COLORconsGetRepresentatives(), the union represented by a node is returned
55  * by COLORconsGetUnion(), the array of unions, indexed by the representing node, is returned by
56  * COLORconsGetUnions().
57  */
58 
59 #ifndef CONSSTOREGRAPH_H
60 #define CONSSTOREGRAPH_H
61 
62 #include "scip/scip.h"
63 #include "tclique/tclique.h"
64 
65 #ifdef __cplusplus
66 extern "C" {
67 #endif
68 
69 /* type of storeGraph constraint: differ, same or root */
71 {
72  COLOR_CONSTYPE_DIFFER = 0, /* constraint representing the branching decision differ(i,j) */
73  COLOR_CONSTYPE_SAME = 1, /* constraint representing the branching decision same(i,j) */
74  COLOR_CONSTYPE_ROOT = 2 /* constraint created for the root, is created automatically */
75 };
77 
78 /** returns the store graph constraint of the current node, needs the pointer to the constraint handler */
79 extern
81  SCIP_CONSHDLR* conshdlr /**< constaint handler for store-graph constraints */
82  );
83 
84 
85 /** returns the store graph constraint of the current node, needs only the pointer to scip */
86 extern
88  SCIP* scip /**< SCIP data structure */
89  );
90 
91 
92 /** returns array of representatives of all nodes */
93 extern
95  SCIP* scip /**< SCIP data structure */
96  );
97 
98 
99 /** returns the current graph */
100 extern
102  SCIP* scip /**< SCIP data structure */
103  );
104 
105 
106 /** returns the complementary graph */
108  SCIP* scip /**< SCIP data structure */
109  );
110 
111 
112 /** returns representative of the union which contains a given node */
113 extern
115  SCIP* scip, /**< SCIP data structure */
116  int node /**< the node, for wich the representative is searched */
117  );
118 
119 
120 /** returns array of all unions, a union is saved in the array at the position of its representative */
121 extern
122 void COLORconsGetUnions(
123  SCIP* scip, /**< SCIP data structure */
124  int*** unions, /**< output: array containing array which contains nodes in the union */
125  int** lengths /**< output: lengths of the unions */
126  );
127 
128 
129 /** returns the union which has a given node as representative */
130 extern
131 void COLORconsGetUnion(
132  SCIP* scip, /**< SCIP data structure */
133  int** unionSet, /**< output: array containig nodes in the union */
134  int* length, /**< output: length of the union */
135  int node /**< the node, whose union we want to get */
136  );
137 
138 
139 /** creates the handler for graph storing constraints and includes it in SCIP */
140 extern
142  SCIP* scip /**< SCIP data structure */
143  );
144 
145 /** creates and captures a storeGraph constraint, uses knowledge of the B&B-father*/
146 extern
148  SCIP* scip, /**< SCIP data structure */
149  SCIP_CONS** cons, /**< pointer to hold the created constraint */
150  const char* name, /**< name of constraint */
151  SCIP_CONS* fatherconstraint, /**< constraint in B&B-father */
152  COLOR_CONSTYPE type, /**< type of the constraint: ROOT for root-constraint, else SAME or DIFFER */
153  int node1, /**< the first node of the constraint or -1 if root-constraint */
154  int node2, /**< the second node of the constraint or -1 if root-constraint */
155  SCIP_NODE* stickingnode /**< the B&B-tree node at which the constraint will be sticking */
156  );
157 
158 
159 /** returns the stack and the number of elements on it */
160 extern
161 void COLORconsGetStack(
162  SCIP* scip, /**< SCIP data structure */
163  SCIP_CONS*** stack, /**< return value: pointer to the stack */
164  int* nstackelements /**< return value: pointer to int, for number of elements on the stack */
165  );
166 
167 #ifdef __cplusplus
168 }
169 #endif
170 
171 #endif
void COLORconsGetStack(SCIP *scip, SCIP_CONS ***stack, int *nstackelements)
SCIP_CONS * COLORconsGetActiveStoreGraphCons(SCIP *scip)
SCIP_RETCODE COLORincludeConshdlrStoreGraph(SCIP *scip)
struct TCLIQUE_Graph TCLIQUE_GRAPH
Definition: tclique.h:40
SCIP_CONS * COLORconsGetActiveStoreGraphConsFromHandler(SCIP_CONSHDLR *conshdlr)
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
int COLORconsGetRepresentative(SCIP *scip, int node)
tclique user interface
COLOR_ConsType
void COLORconsGetUnion(SCIP *scip, int **unionSet, int *length, int node)
SCIP_RETCODE COLORcreateConsStoreGraph(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONS *fatherconstraint, COLOR_CONSTYPE type, int node1, int node2, SCIP_NODE *stickingnode)
TCLIQUE_GRAPH * COLORconsGetComplementaryGraph(SCIP *scip)
enum COLOR_ConsType COLOR_CONSTYPE
int * COLORconsGetRepresentatives(SCIP *scip)
void COLORconsGetUnions(SCIP *scip, int ***unions, int **lengths)
TCLIQUE_GRAPH * COLORconsGetCurrentGraph(SCIP *scip)
SCIP callable library.