Scippy

SCIP

Solving Constraint Integer Programs

symmetry_graph.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-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 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"
41
42#ifdef __cplusplus
43extern "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 */
56SCIP_EXPORT
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 */
70SCIP_EXPORT
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 */
77SCIP_EXPORT
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 */
93SCIP_EXPORT
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 */
113SCIP_EXPORT
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 */
129SCIP_EXPORT
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 */
138SCIP_EXPORT
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 */
147SCIP_EXPORT
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 */
158SCIP_EXPORT
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 */
166SCIP_EXPORT
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 */
174SCIP_EXPORT
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 */
182SCIP_EXPORT
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 */
190SCIP_EXPORT
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 */
201SCIP_EXPORT
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 */
216SCIP_EXPORT
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 */
228SCIP_EXPORT
230 SYM_GRAPH* graph /**< symmetry detection graph */
231 );
232
233/** returns the variables in a symmetry detection graph */
234SCIP_EXPORT
236 SYM_GRAPH* graph /**< symmetry detection graph */
237 );
238
239/** returns the number of variables in a symmetry detection graph */
240SCIP_EXPORT
242 SYM_GRAPH* graph /**< symmetry detection graph */
243 );
244
245/** returns the number of constraint nodes in a symmetry detection graph */
246SCIP_EXPORT
248 SYM_GRAPH* graph /**< symmetry detection graph */
249 );
250
251/** returns the number of non-variable nodes in a graph */
252SCIP_EXPORT
254 SYM_GRAPH* graph /**< symmetry detection graph */
255 );
256
257/** returns the number of edges in a graph */
258SCIP_EXPORT
260 SYM_GRAPH* graph /**< symmetry detection graph */
261 );
262
263/** return the first node index of an edge */
264SCIP_EXPORT
266 SYM_GRAPH* graph, /**< symmetry detection graph */
267 int edgeidx /**< index of edge */
268 );
269
270/** return the second node index of an edge */
271SCIP_EXPORT
273 SYM_GRAPH* graph, /**< symmetry detection graph */
274 int edgeidx /**< index of edge */
275 );
276
277/** returns the color of a variable node */
278SCIP_EXPORT
280 SYM_GRAPH* graph, /**< symmetry detection graph */
281 int nodeidx /**< index of variable node */
282 );
283
284/** returns the type of a node */
285SCIP_EXPORT
287 SYM_GRAPH* graph, /**< symmetry detection graph */
288 int nodeidx /**< index of node */
289 );
290
291/** returns the color of a non-variable node */
292SCIP_EXPORT
294 SYM_GRAPH* graph, /**< symmetry detection graph */
295 int nodeidx /**< index of node */
296 );
297
298/** returns whether an edge is colored */
299SCIP_EXPORT
301 SYM_GRAPH* graph, /**< symmetry detection graph */
302 int edgeidx /**< index of edge */
303 );
304
305/** returns color of an edge */
306SCIP_EXPORT
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 */
313SCIP_EXPORT
315 SYM_GRAPH* graph /**< symmetry detection graph */
316 );
317
318/** returns whether the graph has a unique edge type */
319SCIP_EXPORT
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 */
328SCIP_EXPORT
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 */
338SCIP_EXPORT
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 */
348SCIP_EXPORT
350 SCIP* scip, /**< SCIP data structure */
351 SYM_GRAPH* graph /**< symmetry detection graph */
352 );
353
354/** frees consnodeperm array for symmetry detection graph */
355SCIP_EXPORT
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 */
369SCIP_EXPORT
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 */
381SCIP_EXPORT
383 SCIP* scip, /**< SCIP data structure */
384 SYM_EXPRDATA** symdata /**< symmetry information of an expression */
385 );
386
387/** returns number of coefficients from exprdata */
388SCIP_EXPORT
390 SYM_EXPRDATA* symdata /**< symmetry information of an expression */
391 );
392
393/** returns number of coefficients form exprdata */
394SCIP_EXPORT
396 SYM_EXPRDATA* symdata /**< symmetry information of an expression */
397 );
398
399/** gets coefficient of expression from parent expression */
400SCIP_EXPORT
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
common defines and data types used in all packages of SCIP
#define SCIP_Bool
Definition: def.h:91
#define SCIP_Real
Definition: def.h:173
SYM_NODETYPE SCIPgetSymgraphNodeType(SYM_GRAPH *graph, int nodeidx)
SCIP_RETCODE SCIPaddSymgraphEdge(SCIP *scip, SYM_GRAPH *graph, int first, int second, SCIP_Bool hasval, SCIP_Real val)
SCIP_RETCODE SCIPfreeSymgraph(SCIP *scip, SYM_GRAPH **graph)
int SCIPgetSymgraphEdgeFirst(SYM_GRAPH *graph, int edgeidx)
SCIP_RETCODE SCIPaddSymgraphOpnode(SCIP *scip, SYM_GRAPH *graph, int op, int *nodeidx)
int * SCIPgetSymgraphConsnodeperm(SCIP *scip, SYM_GRAPH *graph)
SCIP_RETCODE SCIPgetSymActiveVariables(SCIP *scip, SYM_SYMTYPE symtype, SCIP_VAR ***vars, SCIP_Real **scalars, int *nvars, SCIP_Real *constant, SCIP_Bool transformed)
SCIP_Bool SCIPhasGraphUniqueEdgetype(SYM_GRAPH *graph)
int SCIPgetSymgraphVarnodeColor(SYM_GRAPH *graph, int nodeidx)
SCIP_RETCODE SCIPaddSymgraphValnode(SCIP *scip, SYM_GRAPH *graph, SCIP_Real val, int *nodeidx)
SCIP_RETCODE SCIPcreateSymgraph(SCIP *scip, SYM_SYMTYPE symtype, SYM_GRAPH **graph, SCIP_VAR **symvars, int nsymvars, int nopnodes, int nvalnodes, int nconsnodes, int nedges)
int SCIPgetSymgraphNEdges(SYM_GRAPH *graph)
int SCIPgetSymgraphVarnodeidx(SCIP *scip, SYM_GRAPH *graph, SCIP_VAR *var)
SCIP_RETCODE SCIPcomputeSymgraphColors(SCIP *scip, SYM_GRAPH *graph, SYM_SPEC fixedtype)
SYM_SYMTYPE SCIPgetSymgraphSymtype(SYM_GRAPH *graph)
SCIP_RETCODE SCIPallocateSymgraphConsnodeperm(SCIP *scip, SYM_GRAPH *graph)
SCIP_RETCODE SCIPaddSymgraphConsnode(SCIP *scip, SYM_GRAPH *graph, SCIP_CONS *cons, SCIP_Real lhs, SCIP_Real rhs, int *nodeidx)
SCIP_RETCODE SCIPcreateSymgraphConsnodeperm(SCIP *scip, SYM_GRAPH *graph)
int SCIPgetSymgraphEdgeSecond(SYM_GRAPH *graph, int edgeidx)
int SCIPgetSymgraphNConsnodes(SYM_GRAPH *graph)
SCIP_RETCODE SCIPaddSymgraphVarAggregation(SCIP *scip, SYM_GRAPH *graph, int rootidx, SCIP_VAR **vars, SCIP_Real *vals, int nvars, SCIP_Real constant)
int SCIPgetSymExprdataNConstants(SYM_EXPRDATA *symdata)
SCIP_RETCODE SCIPupdateSymgraphRhs(SYM_GRAPH *graph, int nodeidx, SCIP_Real newrhs)
SCIP_RETCODE SCIPfreeSymgraphConsnodeperm(SCIP *scip, SYM_GRAPH *graph)
SCIP_RETCODE SCIPupdateSymgraphLhs(SYM_GRAPH *graph, int nodeidx, SCIP_Real newlhs)
int SCIPgetSymgraphNVars(SYM_GRAPH *graph)
int SCIPgetSymgraphNegatedVarnodeidx(SCIP *scip, SYM_GRAPH *graph, SCIP_VAR *var)
SCIP_Bool SCIPisSymgraphEdgeColored(SYM_GRAPH *graph, int edgeidx)
SCIP_RETCODE SCIPfreeSymDataExpr(SCIP *scip, SYM_EXPRDATA **symdata)
SCIP_VAR ** SCIPgetSymgraphVars(SYM_GRAPH *graph)
int SCIPgetSymgraphNodeColor(SYM_GRAPH *graph, int nodeidx)
int SCIPgetSymgraphEdgeColor(SYM_GRAPH *graph, int edgeidx)
SCIP_RETCODE SCIPextendPermsymDetectionGraphLinear(SCIP *scip, SYM_GRAPH *graph, SCIP_VAR **vars, SCIP_Real *vals, int nvars, SCIP_CONS *cons, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool *success)
int SCIPgetSymgraphNNodes(SYM_GRAPH *graph)
SCIP_Real * SCIPgetSymExprdataConstants(SYM_EXPRDATA *symdata)
SCIP_RETCODE SCIPcopySymgraph(SCIP *scip, SYM_GRAPH **graph, SYM_GRAPH *origgraph, int *perm, SYM_SPEC fixedtype)
SCIP_RETCODE SCIPfixSymgraphVarnode(SYM_GRAPH *graph, SCIP_VAR *var)
int SCIPgetSymgraphNVarcolors(SYM_GRAPH *graph)
SCIP_RETCODE SCIPgetCoefSymData(SCIP *scip, SCIP_EXPR *expr, SCIP_EXPR *parentexpr, SCIP_Real *coef, SCIP_Bool *success)
static const SCIP_Real scalars[]
Definition: lp.c:5743
type definitions for return codes for SCIP methods
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
type definitions for SCIP's main datastructure
type definitions for symmetry computations
enum SYM_Symtype SYM_SYMTYPE
Definition: type_symmetry.h:64
enum SYM_Nodetype SYM_NODETYPE
Definition: type_symmetry.h:74
uint32_t SYM_SPEC
Definition: type_symmetry.h:47
type definitions for problem variables