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-2020 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 scipopt.org. */
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 */
80  SCIP_CONSHDLR* conshdlr /**< constaint handler for store-graph constraints */
81  );
82 
83 
84 /** returns the store graph constraint of the current node, needs only the pointer to scip */
86  SCIP* scip /**< SCIP data structure */
87  );
88 
89 
90 /** returns array of representatives of all nodes */
92  SCIP* scip /**< SCIP data structure */
93  );
94 
95 
96 /** returns the current graph */
98  SCIP* scip /**< SCIP data structure */
99  );
100 
101 
102 /** returns the complementary graph */
104  SCIP* scip /**< SCIP data structure */
105  );
106 
107 
108 /** returns representative of the union which contains a given node */
110  SCIP* scip, /**< SCIP data structure */
111  int node /**< the node, for wich the representative is searched */
112  );
113 
114 
115 /** returns array of all unions, a union is saved in the array at the position of its representative */
116 void COLORconsGetUnions(
117  SCIP* scip, /**< SCIP data structure */
118  int*** unions, /**< output: array containing array which contains nodes in the union */
119  int** lengths /**< output: lengths of the unions */
120  );
121 
122 
123 /** returns the union which has a given node as representative */
124 void COLORconsGetUnion(
125  SCIP* scip, /**< SCIP data structure */
126  int** unionSet, /**< output: array containig nodes in the union */
127  int* length, /**< output: length of the union */
128  int node /**< the node, whose union we want to get */
129  );
130 
131 
132 /** creates the handler for graph storing constraints and includes it in SCIP */
134  SCIP* scip /**< SCIP data structure */
135  );
136 
137 /** creates and captures a storeGraph constraint, uses knowledge of the B&B-father*/
139  SCIP* scip, /**< SCIP data structure */
140  SCIP_CONS** cons, /**< pointer to hold the created constraint */
141  const char* name, /**< name of constraint */
142  SCIP_CONS* fatherconstraint, /**< constraint in B&B-father */
143  COLOR_CONSTYPE type, /**< type of the constraint: ROOT for root-constraint, else SAME or DIFFER */
144  int node1, /**< the first node of the constraint or -1 if root-constraint */
145  int node2, /**< the second node of the constraint or -1 if root-constraint */
146  SCIP_NODE* stickingnode /**< the B&B-tree node at which the constraint will be sticking */
147  );
148 
149 
150 /** returns the stack and the number of elements on it */
151 void COLORconsGetStack(
152  SCIP* scip, /**< SCIP data structure */
153  SCIP_CONS*** stack, /**< return value: pointer to the stack */
154  int* nstackelements /**< return value: pointer to int, for number of elements on the stack */
155  );
156 
157 #ifdef __cplusplus
158 }
159 #endif
160 
161 #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:54
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.