1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright 2002-2023 Zuse Institute Berlin */ 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 symmetry_graph.h 26 * @ingroup PUBLICCOREAPI 27 * @brief methods for dealing with symmetry detection graphs 28 * @author Christopher Hojny 29 */ 30 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #ifndef __SCIP_SYMMETRY_GRAPH_H__ 34 #define __SCIP_SYMMETRY_GRAPH_H__ 35 36 #include "scip/def.h" 37 #include "scip/type_retcode.h" 38 #include "scip/type_scip.h" 39 #include "scip/type_var.h" 40 #include <symmetry/type_symmetry.h> 41 42 #ifdef __cplusplus 43 extern "C" { 44 #endif 45 46 47 /**@addtogroup PublicSymmetryGraphMethods 48 * 49 * @{ 50 */ 51 52 /** creates and initializes a symmetry detection graph with memory for the given number of nodes and edges 53 * 54 * @note at some point, the graph needs to be freed! 55 */ 56 SCIP_EXPORT 57 SCIP_RETCODE SCIPcreateSymgraph( 58 SCIP* scip, /**< SCIP data structure */ 59 SYM_SYMTYPE symtype, /**< type of symmetries encoded in graph */ 60 SYM_GRAPH** graph, /**< pointer to hold symmetry detection graph */ 61 SCIP_VAR** symvars, /**< variables used in symmetry detection */ 62 int nsymvars, /**< number of variables used in symmetry detection */ 63 int nopnodes, /**< number of operator nodes */ 64 int nvalnodes, /**< number of value nodes */ 65 int nconsnodes, /**< number of constraint nodes */ 66 int nedges /**< number of edges */ 67 ); 68 69 /** frees a symmetry detection graph */ 70 SCIP_EXPORT 71 SCIP_RETCODE SCIPfreeSymgraph( 72 SCIP* scip, /**< SCIP data structure */ 73 SYM_GRAPH** graph /**< pointer to symmetry detection graph */ 74 ); 75 76 /** copies an existing graph and changes variable nodes according to a permutation */ 77 SCIP_EXPORT 78 SCIP_RETCODE SCIPcopySymgraph( 79 SCIP* scip, /**< SCIP data structure */ 80 SYM_GRAPH** graph, /**< pointer to hold copy of symmetry detection graph */ 81 SYM_GRAPH* origgraph, /**< graph to be copied */ 82 int* perm, /**< permutation of variables */ 83 SYM_SPEC fixedtype /**< variable types that must be fixed by symmetries */ 84 ); 85 86 /** adds a symmetry detection graph for a linear constraint to existing graph 87 * 88 * For permutation symmetries, a constraint node is added that is connected to all 89 * variable nodes in the constraint. Edges are colored according to the variable coefficients. 90 * For signed permutation symmetries, also edges connecting the constraint node and 91 * the negated variable nodes are added, these edges are colored by the negative coefficients. 92 */ 93 SCIP_EXPORT 94 SCIP_RETCODE SCIPextendPermsymDetectionGraphLinear( 95 SCIP* scip, /**< SCIP data structure */ 96 SYM_GRAPH* graph, /**< symmetry detection graph */ 97 SCIP_VAR** vars, /**< variable array of linear constraint */ 98 SCIP_Real* vals, /**< coefficients of linear constraint */ 99 int nvars, /**< number of variables in linear constraint */ 100 SCIP_CONS* cons, /**< constraint for which we encode symmetries */ 101 SCIP_Real lhs, /**< left-hand side of constraint */ 102 SCIP_Real rhs, /**< right-hand side of constraint */ 103 SCIP_Bool* success /**< pointer to store whether graph could be built */ 104 ); 105 106 /** adds nodes and edges corresponding to the aggregation of a variable to a symmetry detection graph 107 * 108 * For permutation symmetries, the root node is connected with all variable nodes in the aggregation. 109 * Edges are colored according to the variable coefficients. 110 * For signed permutation symmetries, also edges connecting the root node and the negated variable 111 * nodes are added, these edges are colored by the negative coefficients. 112 */ 113 SCIP_EXPORT 114 SCIP_RETCODE SCIPaddSymgraphVarAggegration( 115 SCIP* scip, /**< SCIP data structure */ 116 SYM_GRAPH* graph, /**< symmetry detection graph */ 117 int rootidx, /**< index of root node of the aggregation */ 118 SCIP_VAR** vars, /**< array of variables in aggregation */ 119 SCIP_Real* vals, /**< coefficients of variables */ 120 int nvars, /**< number of variables in aggregation */ 121 SCIP_Real constant /**< constant of aggregation */ 122 ); 123 124 /* 125 * methods for adding and accessing nodes 126 */ 127 128 /** adds an operator node to a symmetry detection graph and returns its node index */ 129 SCIP_EXPORT 130 SCIP_RETCODE SCIPaddSymgraphOpnode( 131 SCIP* scip, /**< SCIP data structure */ 132 SYM_GRAPH* graph, /**< symmetry detection graph */ 133 int op, /**< int associated with operator of node */ 134 int* nodeidx /**< pointer to hold index of created node */ 135 ); 136 137 /** adds a value node to a symmetry detection graph and returns its node index */ 138 SCIP_EXPORT 139 SCIP_RETCODE SCIPaddSymgraphValnode( 140 SCIP* scip, /**< SCIP data structure */ 141 SYM_GRAPH* graph, /**< symmetry detection graph */ 142 SCIP_Real val, /**< value of node */ 143 int* nodeidx /**< pointer to hold index of created node */ 144 ); 145 146 /** adds a constraint node to a symmetry detection graph and returns its node index */ 147 SCIP_EXPORT 148 SCIP_RETCODE SCIPaddSymgraphConsnode( 149 SCIP* scip, /**< SCIP data structure */ 150 SYM_GRAPH* graph, /**< symmetry detection graph */ 151 SCIP_CONS* cons, /**< constraint of node */ 152 SCIP_Real lhs, /**< left-hand side of node */ 153 SCIP_Real rhs, /**< right-hand side of node */ 154 int* nodeidx /**< pointer to hold index of created node */ 155 ); 156 157 /** returns the (hypothetical) node index of a variable */ 158 SCIP_EXPORT 159 int SCIPgetSymgraphVarnodeidx( 160 SCIP* scip, /**< SCIP data structure */ 161 SYM_GRAPH* graph, /**< symmetry detection graph */ 162 SCIP_VAR* var /**< variable */ 163 ); 164 165 /** returns the (hypothetical) node index of a negated variable */ 166 SCIP_EXPORT 167 int SCIPgetSymgraphNegatedVarnodeidx( 168 SCIP* scip, /**< SCIP data structure */ 169 SYM_GRAPH* graph, /**< symmetry detection graph */ 170 SCIP_VAR* var /**< variable */ 171 ); 172 173 /** updates the lhs of a constraint node */ 174 SCIP_EXPORT 175 SCIP_RETCODE SCIPupdateSymgraphLhs( 176 SYM_GRAPH* graph, /**< symmetry detection graph */ 177 int nodeidx, /**< index of constraint node in graph */ 178 SCIP_Real newlhs /**< new left-hand side of node */ 179 ); 180 181 /** updates the rhs of a constraint node */ 182 SCIP_EXPORT 183 SCIP_RETCODE SCIPupdateSymgraphRhs( 184 SYM_GRAPH* graph, /**< symmetry detection graph */ 185 int nodeidx, /**< index of constraint node in graph */ 186 SCIP_Real newrhs /**< new reft-hand side of node */ 187 ); 188 189 /** registers a variable node (corresponding to active variable) to be fixed by symmetry */ 190 SCIP_EXPORT 191 SCIP_RETCODE SCIPfixSymgraphVarnode( 192 SYM_GRAPH* graph, /**< symmetry detection graph */ 193 SCIP_VAR* var /**< active variable that needs to be fixed */ 194 ); 195 196 /* 197 * methods for adding edges 198 */ 199 200 /** adds an edge to a symmetry detection graph */ 201 SCIP_EXPORT 202 SCIP_RETCODE SCIPaddSymgraphEdge( 203 SCIP* scip, /**< SCIP data structure */ 204 SYM_GRAPH* graph, /**< symmetry detection graph */ 205 int first, /**< first node index of edge */ 206 int second, /**< second node index of edge */ 207 SCIP_Bool hasval, /**< whether the edge has a value */ 208 SCIP_Real val /**< value of the edge (is it has a value) */ 209 ); 210 211 /* 212 * methods to compute colors 213 */ 214 215 /** computes colors of nodes and edges */ 216 SCIP_EXPORT 217 SCIP_RETCODE SCIPcomputeSymgraphColors( 218 SCIP* scip, /**< SCIP data structure */ 219 SYM_GRAPH* graph, /**< symmetry detection graph */ 220 SYM_SPEC fixedtype /**< variable types that must be fixed by symmetries */ 221 ); 222 223 /* 224 * general methods 225 */ 226 227 /** returns the type of symmetries encoded in graph */ 228 SCIP_EXPORT 229 SYM_SYMTYPE SCIPgetSymgraphSymtype( 230 SYM_GRAPH* graph /**< symmetry detection graph */ 231 ); 232 233 /** returns the variables in a symmetry detection graph */ 234 SCIP_EXPORT 235 SCIP_VAR** SCIPgetSymgraphVars( 236 SYM_GRAPH* graph /**< symmetry detection graph */ 237 ); 238 239 /** returns the number of variables in a symmetry detection graph */ 240 SCIP_EXPORT 241 int SCIPgetSymgraphNVars( 242 SYM_GRAPH* graph /**< symmetry detection graph */ 243 ); 244 245 /** returns the number of constraint nodes in a symmetry detection graph */ 246 SCIP_EXPORT 247 int SCIPgetSymgraphNConsnodes( 248 SYM_GRAPH* graph /**< symmetry detection graph */ 249 ); 250 251 /** returns the number of non-variable nodes in a graph */ 252 SCIP_EXPORT 253 int SCIPgetSymgraphNNodes( 254 SYM_GRAPH* graph /**< symmetry detection graph */ 255 ); 256 257 /** returns the number of edges in a graph */ 258 SCIP_EXPORT 259 int SCIPgetSymgraphNEdges( 260 SYM_GRAPH* graph /**< symmetry detection graph */ 261 ); 262 263 /** return the first node index of an edge */ 264 SCIP_EXPORT 265 int SCIPgetSymgraphEdgeFirst( 266 SYM_GRAPH* graph, /**< symmetry detection graph */ 267 int edgeidx /**< index of edge */ 268 ); 269 270 /** return the second node index of an edge */ 271 SCIP_EXPORT 272 int SCIPgetSymgraphEdgeSecond( 273 SYM_GRAPH* graph, /**< symmetry detection graph */ 274 int edgeidx /**< index of edge */ 275 ); 276 277 /** returns the color of a variable node */ 278 SCIP_EXPORT 279 int SCIPgetSymgraphVarnodeColor( 280 SYM_GRAPH* graph, /**< symmetry detection graph */ 281 int nodeidx /**< index of variable node */ 282 ); 283 284 /** returns the type of a node */ 285 SCIP_EXPORT 286 SYM_NODETYPE SCIPgetSymgraphNodeType( 287 SYM_GRAPH* graph, /**< symmetry detection graph */ 288 int nodeidx /**< index of node */ 289 ); 290 291 /** returns the color of a non-variable node */ 292 SCIP_EXPORT 293 int SCIPgetSymgraphNodeColor( 294 SYM_GRAPH* graph, /**< symmetry detection graph */ 295 int nodeidx /**< index of node */ 296 ); 297 298 /** returns whether an edge is colored */ 299 SCIP_EXPORT 300 SCIP_Bool SCIPisSymgraphEdgeColored( 301 SYM_GRAPH* graph, /**< symmetry detection graph */ 302 int edgeidx /**< index of edge */ 303 ); 304 305 /** returns color of an edge */ 306 SCIP_EXPORT 307 int SCIPgetSymgraphEdgeColor( 308 SYM_GRAPH* graph, /**< symmetry detection graph */ 309 int edgeidx /**< index of edge */ 310 ); 311 312 /** returns the number of unique variable colors in the graph */ 313 SCIP_EXPORT 314 int SCIPgetSymgraphNVarcolors( 315 SYM_GRAPH* graph /**< symmetry detection graph */ 316 ); 317 318 /** returns whether the graph has a unique edge type */ 319 SCIP_EXPORT 320 SCIP_Bool SCIPhasGraphUniqueEdgetype( 321 SYM_GRAPH* graph /**< symmetry detection graph */ 322 ); 323 324 /** creates consnodeperm array for symmetry detection graph 325 * 326 * @note @p colors of symmetry detection graph must have been computed 327 */ 328 SCIP_EXPORT 329 SCIP_RETCODE SCIPallocateSymgraphConsnodeperm( 330 SCIP* scip, /**< SCIP data structure */ 331 SYM_GRAPH* graph /**< symmetry detection graph */ 332 ); 333 334 /** creates consnodeperm array for symmetry detection graph 335 * 336 * @note @p colors of symmetry detection graph must have been computed 337 */ 338 SCIP_EXPORT 339 SCIP_RETCODE SCIPcreateSymgraphConsnodeperm( 340 SCIP* scip, /**< SCIP data structure */ 341 SYM_GRAPH* graph /**< symmetry detection graph */ 342 ); 343 344 /** returns consnodeperm array for symmetry detection graph 345 * 346 * @note @p colors of symmetry detection graph must have been computed 347 */ 348 SCIP_EXPORT 349 int* SCIPgetSymgraphConsnodeperm( 350 SCIP* scip, /**< SCIP data structure */ 351 SYM_GRAPH* graph /**< symmetry detection graph */ 352 ); 353 354 /** frees consnodeperm array for symmetry detection graph */ 355 SCIP_EXPORT 356 SCIP_RETCODE SCIPfreeSymgraphConsnodeperm( 357 SCIP* scip, /**< SCIP data structure */ 358 SYM_GRAPH* graph /**< symmetry detection graph */ 359 ); 360 361 /** Transforms given variables, scalars, and constant to the corresponding active variables, scalars, and constant. 362 * 363 * For permutation symmetries, active variables as encoded in SCIP are used. For signed permutation symmetries, 364 * active variables are shifted such that their domain is centered at 0 (if both their upper and lower bounds 365 * are finite). 366 * 367 * @note @p constant needs to be initialized! 368 */ 369 SCIP_EXPORT 370 SCIP_RETCODE SCIPgetActiveVariables( 371 SCIP* scip, /**< SCIP data structure */ 372 SYM_SYMTYPE symtype, /**< type of symmetries for which variables are required */ 373 SCIP_VAR*** vars, /**< pointer to vars array to get active variables for */ 374 SCIP_Real** scalars, /**< pointer to scalars a_1, ..., a_n in linear sum a_1*x_1 + ... + a_n*x_n + c */ 375 int* nvars, /**< pointer to number of variables and values in vars and vals array */ 376 SCIP_Real* constant, /**< pointer to constant c in linear sum a_1*x_1 + ... + a_n*x_n + c */ 377 SCIP_Bool transformed /**< transformed constraint? */ 378 ); 379 380 /** frees symmetry information of an expression */ 381 SCIP_EXPORT 382 SCIP_RETCODE SCIPfreeSymDataExpr( 383 SCIP* scip, /**< SCIP data structure */ 384 SYM_EXPRDATA** symdata /**< symmetry information of an expression */ 385 ); 386 387 /** returns number of coefficients from exprdata */ 388 SCIP_EXPORT 389 int SCIPgetSymExprdataNConstants( 390 SYM_EXPRDATA* symdata /**< symmetry information of an expression */ 391 ); 392 393 /** returns number of coefficients form exprdata */ 394 SCIP_EXPORT 395 SCIP_Real* SCIPgetSymExprdataConstants( 396 SYM_EXPRDATA* symdata /**< symmetry information of an expression */ 397 ); 398 399 /** gets coefficient of expression from parent expression */ 400 SCIP_EXPORT 401 SCIP_RETCODE SCIPgetCoefSymData( 402 SCIP* scip, /**< SCIP data structure */ 403 SCIP_EXPR* expr, /**< expression for which coefficient needs to be found */ 404 SCIP_EXPR* parentexpr, /**< parent of expr */ 405 SCIP_Real* coef, /**< buffer to store coefficient */ 406 SCIP_Bool* success /**< whether a coefficient is found */ 407 ); 408 409 410 /** @} */ 411 412 #ifdef __cplusplus 413 } 414 #endif 415 416 #endif 417