Scippy

SCIP

Solving Constraint Integer Programs

symmetry.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-2021 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 symmetry.h
17  * @ingroup PUBLICCOREAPI
18  * @brief methods for handling symmetries
19  * @author Christopher Hojny
20  * @author Marc Pfetsch
21  */
22 
23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
24 
25 #ifndef __SCIP_SYMMETRY_H__
26 #define __SCIP_SYMMETRY_H__
27 
28 #include "scip/def.h"
29 #include "scip/type_retcode.h"
30 #include "scip/type_scip.h"
31 #include "scip/type_var.h"
32 
33 #ifdef __cplusplus
34 extern "C" {
35 #endif
36 
37 /**@addtogroup PublicSymmetryMethods
38  *
39  * @{
40  */
41 
42 
43 /** compute non-trivial orbits of symmetry group
44  *
45  * The non-tivial orbits of the group action are stored in the array orbits of length npermvars. This array contains
46  * the indices of variables from the permvars array such that variables that are contained in the same orbit appear
47  * consecutively in the orbits array. The variables of the i-th orbit have indices
48  * orbits[orbitbegins[i]], ... , orbits[orbitbegins[i + 1] - 1].
49  * Note that the description of the orbits ends at orbitbegins[norbits] - 1.
50  */
53  SCIP* scip, /**< SCIP instance */
54  SCIP_VAR** permvars, /**< variables considered in a permutation array */
55  int npermvars, /**< length of a permutation array */
56  int** perms, /**< matrix containing in each row a permutation of the symmetry group */
57  int nperms, /**< number of permutations encoded in perms */
58  int* orbits, /**< array of non-trivial orbits */
59  int* orbitbegins, /**< array containing begin positions of new orbits in orbits array */
60  int* norbits /**< pointer to number of orbits currently stored in orbits */
61  );
62 
63 
64 /** compute non-trivial orbits of symmetry group using filtered generators
65  *
66  * The non-trivial orbits of the group action are stored in the array orbits of length npermvars. This array contains
67  * the indices of variables from the permvars array such that variables that are contained in the same orbit appear
68  * consecutively in the orbits array. The variables of the i-th orbit have indices
69  * orbits[orbitbegins[i]], ... , orbits[orbitbegins[i + 1] - 1].
70  * Note that the description of the orbits ends at orbitbegins[norbits] - 1.
71  *
72  * Only permutations that are not inactive (as marked by @p inactiveperms) are used. Thus, one can use this array to
73  * filter out permutations.
74  */
77  SCIP* scip, /**< SCIP instance */
78  int npermvars, /**< length of a permutation array */
79  int** permstrans, /**< transposed matrix containing in each column a
80  * permutation of the symmetry group */
81  int nperms, /**< number of permutations encoded in perms */
82  SCIP_Shortbool* inactiveperms, /**< array to store whether permutations are inactive */
83  int* orbits, /**< array of non-trivial orbits */
84  int* orbitbegins, /**< array containing begin positions of new orbits in orbits array */
85  int* norbits, /**< pointer to number of orbits currently stored in orbits */
86  int* components, /**< array containing the indices of permutations sorted by components */
87  int* componentbegins, /**< array containing in i-th position the first position of
88  * component i in components array */
89  int* vartocomponent, /**< array containing for each permvar the index of the component it is
90  * contained in (-1 if not affected) */
91  SCIP_Shortbool* componentblocked, /**< array to store whether a component is blocked to be considered by
92  * further symmetry handling techniques */
93  int ncomponents, /**< number of components of symmetry group */
94  int nmovedpermvars /**< number of variables moved by any permutation in a symmetry component
95  * that is handled by orbital fixing */
96  );
97 
98 /** compute non-trivial orbits of symmetry group
99  *
100  * The non-tivial orbits of the group action are stored in the array orbits of length npermvars. This array contains
101  * the indices of variables from the permvars array such that variables that are contained in the same orbit appear
102  * consecutively in the orbits array. The variables of the i-th orbit have indices
103  * orbits[orbitbegins[i]], ... , orbits[orbitbegins[i + 1] - 1].
104  * Note that the description of the orbits ends at orbitbegins[norbits] - 1.
105  *
106  * This function is adapted from SCIPcomputeOrbitsFilterSym().
107  */
110  SCIP* scip, /**< SCIP instance */
111  int npermvars, /**< length of a permutation array */
112  int** permstrans, /**< transposed matrix containing in each column a permutation of the symmetry group */
113  int nperms, /**< number of permutations encoded in perms */
114  int* components, /**< array containing the indices of permutations sorted by components */
115  int* componentbegins, /**< array containing in i-th position the first position of component i in components array */
116  int* vartocomponent, /**< array containing for each permvar the index of the component it is
117  * contained in (-1 if not affected) */
118  int ncomponents, /**< number of components of symmetry group */
119  int* orbits, /**< array of non-trivial orbits */
120  int* orbitbegins, /**< array containing begin positions of new orbits in orbits array */
121  int* norbits, /**< pointer to number of orbits currently stored in orbits */
122  int* varorbitmap /**< array for storing the orbits for each variable */
123  );
124 
125 /** check whether a permutation is a composition of 2-cycles of binary variables and in this case determine the number of 2-cycles */
128  int* perm, /**< permutation */
129  SCIP_VAR** vars, /**< array of variables perm is acting on */
130  int nvars, /**< number of variables */
131  SCIP_Bool* iscompoftwocycles, /**< pointer to store whether permutation is a composition of 2-cycles */
132  int* ntwocyclesperm, /**< pointer to store number of 2-cycles */
133  SCIP_Bool* allvarsbinary /**< pointer to store whether perm is acting on binary variables only */
134  );
135 
136 /** determine number of variables affected by symmetry group */
139  SCIP* scip, /**< SCIP instance */
140  int** perms, /**< permutations */
141  int nperms, /**< number of permutations in perms */
142  SCIP_VAR** permvars, /**< variables corresponding to permutations */
143  int npermvars, /**< number of permvars in perms */
144  int* nvarsaffected /**< pointer to store number of all affected variables */
145  );
146 
147 /** compute components of symmetry group */
150  SCIP* scip, /**< SCIP instance */
151  int** perms, /**< permutation generators as
152  * (either nperms x npermvars or npermvars x nperms) matrix */
153  int nperms, /**< number of permutations */
154  SCIP_VAR** permvars, /**< variables on which permutations act */
155  int npermvars, /**< number of variables for permutations */
156  SCIP_Bool transposed, /**< transposed permutation generators as (npermvars x nperms) matrix */
157  int** components, /**< array containing the indices of permutations sorted by components */
158  int** componentbegins, /**< array containing in i-th position the first position of
159  * component i in components array */
160  int** vartocomponent, /**< array containing for each permvar the index of the component it is
161  * contained in (-1 if not affected) */
162  SCIP_Shortbool** componentblocked, /**< array to store whether a component is blocked to be considered by
163  * further symmetry handling techniques */
164  int* ncomponents /**< pointer to store number of components of symmetry group */
165  );
166 
167 /** Given a matrix with nrows and \#perms + 1 columns whose first nfilledcols columns contain entries of variables, this routine
168  * checks whether the 2-cycles of perm intersect each row of column coltoextend in exactly one position. In this case,
169  * we add one column to the suborbitope of the first nfilledcols columns.
170  *
171  * @pre Every non-trivial cycle of perm is a 2-cycle.
172  * @pre perm has nrows many 2-cycles
173  */
176  int** suborbitope, /**< matrix containing suborbitope entries */
177  int nrows, /**< number of rows of suborbitope */
178  int nfilledcols, /**< number of columns of suborbitope which are filled with entries */
179  int coltoextend, /**< index of column that should be extended by perm */
180  int* perm, /**< permutation */
181  SCIP_Bool leftextension, /**< whether we extend the suborbitope to the left */
182  int** nusedelems, /**< pointer to array storing how often an element was used in the orbitope */
183  SCIP_Bool* success, /**< pointer to store whether extension was successful */
184  SCIP_Bool* infeasible /**< pointer to store if the number of intersecting cycles is too small */
185  );
186 
187 
188 /** generate variable matrix for orbitope constraint handler */
191  SCIP_VAR**** vars, /**< pointer to matrix of orbitope variables */
192  int nrows, /**< number of rows of orbitope */
193  int ncols, /**< number of columns of orbitope */
194  SCIP_VAR** permvars, /**< superset of variables that are contained in orbitope */
195  int npermvars, /**< number of variables in permvars array */
196  int** orbitopevaridx, /**< permuted index table of variables in permvars that are contained in orbitope */
197  int* columnorder, /**< permutation to reorder column of orbitopevaridx */
198  int* nusedelems, /**< array storing how often an element was used in the orbitope */
199  SCIP_Bool* infeasible /**< pointer to store whether the potential orbitope is not an orbitope */
200  );
201 
202 
203 /** @} */
204 
205 #ifdef __cplusplus
206 }
207 #endif
208 
209 #endif
#define SCIP_EXPORT
Definition: def.h:100
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
type definitions for return codes for SCIP methods
SCIP_EXPORT SCIP_RETCODE SCIPdetermineNVarsAffectedSym(SCIP *scip, int **perms, int nperms, SCIP_VAR **permvars, int npermvars, int *nvarsaffected)
Definition: symmetry.c:478
SCIP_EXPORT SCIP_RETCODE SCIPcomputeOrbitsFilterSym(SCIP *scip, int npermvars, int **permstrans, int nperms, SCIP_Shortbool *inactiveperms, int *orbits, int *orbitbegins, int *norbits, int *components, int *componentbegins, int *vartocomponent, SCIP_Shortbool *componentblocked, int ncomponents, int nmovedpermvars)
Definition: symmetry.c:152
SCIP_EXPORT SCIP_RETCODE SCIPcomputeOrbitsSym(SCIP *scip, SCIP_VAR **permvars, int npermvars, int **perms, int nperms, int *orbits, int *orbitbegins, int *norbits)
Definition: symmetry.c:38
type definitions for SCIP&#39;s main datastructure
SCIP_EXPORT SCIP_RETCODE SCIPgenerateOrbitopeVarsMatrix(SCIP_VAR ****vars, int nrows, int ncols, SCIP_VAR **permvars, int npermvars, int **orbitopevaridx, int *columnorder, int *nusedelems, SCIP_Bool *infeasible)
Definition: symmetry.c:852
SCIP_EXPORT SCIP_RETCODE SCIPgetPropertiesPerm(int *perm, SCIP_VAR **vars, int nvars, SCIP_Bool *iscompoftwocycles, int *ntwocyclesperm, SCIP_Bool *allvarsbinary)
Definition: symmetry.c:424
#define SCIP_Shortbool
Definition: def.h:78
type definitions for problem variables
#define SCIP_Bool
Definition: def.h:70
SCIP_EXPORT SCIP_RETCODE SCIPextendSubOrbitope(int **suborbitope, int nrows, int nfilledcols, int coltoextend, int *perm, SCIP_Bool leftextension, int **nusedelems, SCIP_Bool *success, SCIP_Bool *infeasible)
Definition: symmetry.c:530
SCIP_EXPORT SCIP_RETCODE SCIPcomputeOrbitsComponentsSym(SCIP *scip, int npermvars, int **permstrans, int nperms, int *components, int *componentbegins, int *vartocomponent, int ncomponents, int *orbits, int *orbitbegins, int *norbits, int *varorbitmap)
Definition: symmetry.c:304
SCIP_EXPORT SCIP_RETCODE SCIPcomputeComponentsSym(SCIP *scip, int **perms, int nperms, SCIP_VAR **permvars, int npermvars, SCIP_Bool transposed, int **components, int **componentbegins, int **vartocomponent, SCIP_Shortbool **componentblocked, int *ncomponents)
Definition: symmetry.c:651
common defines and data types used in all packages of SCIP