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-2023 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.h
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 father 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 father 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 to 0 all variables representing 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 #ifndef CONSSTOREGRAPH_H
69 #define CONSSTOREGRAPH_H
70 
71 #include "scip/scip.h"
72 #include "tclique/tclique.h"
73 
74 #ifdef __cplusplus
75 extern "C" {
76 #endif
77 
78 /* type of storeGraph constraint: differ, same or root */
80 {
81  COLOR_CONSTYPE_DIFFER = 0, /* constraint representing the branching decision differ(i,j) */
82  COLOR_CONSTYPE_SAME = 1, /* constraint representing the branching decision same(i,j) */
83  COLOR_CONSTYPE_ROOT = 2 /* constraint created for the root, is created automatically */
84 };
86 
87 /** returns the store graph constraint of the current node, needs the pointer to the constraint handler */
89  SCIP_CONSHDLR* conshdlr /**< constaint handler for store-graph constraints */
90  );
91 
92 
93 /** returns the store graph constraint of the current node, needs only the pointer to scip */
95  SCIP* scip /**< SCIP data structure */
96  );
97 
98 
99 /** returns array of representatives of all nodes */
101  SCIP* scip /**< SCIP data structure */
102  );
103 
104 
105 /** returns the current graph */
107  SCIP* scip /**< SCIP data structure */
108  );
109 
110 
111 /** returns the complementary graph */
113  SCIP* scip /**< SCIP data structure */
114  );
115 
116 
117 /** returns representative of the union which contains a given node */
119  SCIP* scip, /**< SCIP data structure */
120  int node /**< the node, for wich the representative is searched */
121  );
122 
123 
124 /** returns array of all unions, a union is saved in the array at the position of its representative */
125 void COLORconsGetUnions(
126  SCIP* scip, /**< SCIP data structure */
127  int*** unions, /**< output: array containing array which contains nodes in the union */
128  int** lengths /**< output: lengths of the unions */
129  );
130 
131 
132 /** returns the union which has a given node as representative */
133 void COLORconsGetUnion(
134  SCIP* scip, /**< SCIP data structure */
135  int** unionSet, /**< output: array containig nodes in the union */
136  int* length, /**< output: length of the union */
137  int node /**< the node, whose union we want to get */
138  );
139 
140 
141 /** creates the handler for graph storing constraints and includes it in SCIP */
143  SCIP* scip /**< SCIP data structure */
144  );
145 
146 /** creates and captures a storeGraph constraint, uses knowledge of the B&B-father*/
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 void COLORconsGetStack(
161  SCIP* scip, /**< SCIP data structure */
162  SCIP_CONS*** stack, /**< return value: pointer to the stack */
163  int* nstackelements /**< return value: pointer to int, for number of elements on the stack */
164  );
165 
166 #ifdef __cplusplus
167 }
168 #endif
169 
170 #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:49
SCIP_CONS * COLORconsGetActiveStoreGraphConsFromHandler(SCIP_CONSHDLR *conshdlr)
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
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.