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-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 symmetry.h
26  * @ingroup PUBLICCOREAPI
27  * @brief methods for handling symmetries
28  * @author Christopher Hojny
29  * @author Marc Pfetsch
30  */
31 
32 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33 
34 #ifndef __SCIP_SYMMETRY_H__
35 #define __SCIP_SYMMETRY_H__
36 
37 #include "scip/def.h"
38 #include "scip/pub_misc.h"
39 #include "scip/type_retcode.h"
40 #include "scip/type_scip.h"
41 #include "scip/type_var.h"
42 #include <symmetry/type_symmetry.h>
43 
44 #ifdef __cplusplus
45 extern "C" {
46 #endif
47 
48 
49 /**@addtogroup PublicSymmetryMethods
50  *
51  * @{
52  */
53 
54 
55 /** compute non-trivial orbits of symmetry group
56  *
57  * The non-tivial orbits of the group action are stored in the array orbits of length npermvars. This array contains
58  * the indices of variables from the permvars array such that variables that are contained in the same orbit appear
59  * consecutively in the orbits array. The variables of the i-th orbit have indices
60  * orbits[orbitbegins[i]], ... , orbits[orbitbegins[i + 1] - 1].
61  * Note that the description of the orbits ends at orbitbegins[norbits] - 1.
62  */
63 SCIP_EXPORT
65  SCIP* scip, /**< SCIP instance */
66  SCIP_VAR** permvars, /**< variables considered in a permutation array */
67  int npermvars, /**< length of a permutation array */
68  int** perms, /**< matrix containing in each row a permutation of the symmetry group */
69  int nperms, /**< number of permutations encoded in perms */
70  int* orbits, /**< array of non-trivial orbits */
71  int* orbitbegins, /**< array containing begin positions of new orbits in orbits array */
72  int* norbits /**< pointer to number of orbits currently stored in orbits */
73  );
74 
75 
76 /** compute non-trivial orbits of symmetry group using filtered generators
77  *
78  * The non-trivial orbits of the group action are stored in the array orbits of length npermvars. This array contains
79  * the indices of variables from the permvars array such that variables that are contained in the same orbit appear
80  * consecutively in the orbits array. The variables of the i-th orbit have indices
81  * orbits[orbitbegins[i]], ... , orbits[orbitbegins[i + 1] - 1].
82  * Note that the description of the orbits ends at orbitbegins[norbits] - 1.
83  *
84  * Only permutations that are not inactive (as marked by @p inactiveperms) are used. Thus, one can use this array to
85  * filter out permutations.
86  */
87 SCIP_EXPORT
89  SCIP* scip, /**< SCIP instance */
90  int npermvars, /**< length of a permutation array */
91  int** permstrans, /**< transposed matrix containing in each column a
92  * permutation of the symmetry group */
93  int nperms, /**< number of permutations encoded in perms */
94  SCIP_Shortbool* inactiveperms, /**< array to store whether permutations are inactive */
95  int* orbits, /**< array of non-trivial orbits */
96  int* orbitbegins, /**< array containing begin positions of new orbits in orbits array */
97  int* norbits, /**< pointer to number of orbits currently stored in orbits */
98  int* components, /**< array containing the indices of permutations sorted by components */
99  int* componentbegins, /**< array containing in i-th position the first position of
100  * component i in components array */
101  int* vartocomponent, /**< array containing for each permvar the index of the component it is
102  * contained in (-1 if not affected) */
103  unsigned* componentblocked, /**< array to store which symmetry methods have been used on a component
104  * using the same bitset information as for misc/usesymmetry */
105  int ncomponents, /**< number of components of symmetry group */
106  int nmovedpermvars /**< number of variables moved by any permutation in a symmetry component
107  * that is handled by orbital fixing */
108  );
109 
110 /** compute non-trivial orbits of symmetry group
111  *
112  * The non-tivial orbits of the group action are stored in the array orbits of length npermvars. This array contains
113  * the indices of variables from the permvars array such that variables that are contained in the same orbit appear
114  * consecutively in the orbits array. The variables of the i-th orbit have indices
115  * orbits[orbitbegins[i]], ... , orbits[orbitbegins[i + 1] - 1].
116  * Note that the description of the orbits ends at orbitbegins[norbits] - 1.
117  *
118  * This function is adapted from SCIPcomputeOrbitsFilterSym().
119  */
120 SCIP_EXPORT
122  SCIP* scip, /**< SCIP instance */
123  int npermvars, /**< length of a permutation array */
124  int** permstrans, /**< transposed matrix containing in each column a permutation of the symmetry group */
125  int nperms, /**< number of permutations encoded in perms */
126  int* components, /**< array containing the indices of permutations sorted by components */
127  int* componentbegins, /**< array containing in i-th position the first position of component i in components array */
128  int* vartocomponent, /**< array containing for each permvar the index of the component it is
129  * contained in (-1 if not affected) */
130  int ncomponents, /**< number of components of symmetry group */
131  int* orbits, /**< array of non-trivial orbits */
132  int* orbitbegins, /**< array containing begin positions of new orbits in orbits array */
133  int* norbits, /**< pointer to number of orbits currently stored in orbits */
134  int* varorbitmap /**< array for storing the orbits for each variable */
135  );
136 
137 /** Compute orbit of a given variable and store it in @p orbit. The first entry of the orbit will
138  * be the given variable index and the rest is filled with the remaining variables excluding
139  * the ones specified in @p ignoredvars.
140  *
141  * @pre orbit is an initialized array of size propdata->npermvars
142  * @pre at least one of @p perms and @p permstrans should not be NULL
143  */
144 SCIP_EXPORT
146  SCIP* scip, /**< SCIP instance */
147  int npermvars, /**< number of variables in permvars */
148  int** perms, /**< the generators of the permutation group (or NULL) */
149  int** permstrans, /**< the transposed matrix of generators (or NULL) */
150  int* components, /**< the components of the permutation group */
151  int* componentbegins, /**< array containing the starting index of each component */
152  SCIP_Shortbool* ignoredvars, /**< array indicating which variables should be ignored */
153  SCIP_Shortbool* varfound, /**< bitmap to mark which variables have been added (or NULL) */
154  int varidx, /**< index of variable for which the orbit is requested */
155  int component, /**< component that var is in */
156  int * orbit, /**< array in which the orbit should be stored */
157  int* orbitsize /**< buffer to store the size of the orbit */
158  );
159 
160 /** Checks whether a permutation is a composition of 2-cycles and in this case determine the number of overall
161  * 2-cycles and binary 2-cycles. It is a composition of 2-cycles iff @p ntwocyclesperm > 0 upon termination.
162  */
163 SCIP_EXPORT
165  int* perm, /**< permutation */
166  SCIP_VAR** vars, /**< array of variables perm is acting on */
167  int nvars, /**< number of variables */
168  int* ntwocyclesperm, /**< pointer to store number of 2-cycles */
169  int* nbincyclesperm, /**< pointer to store number of binary cycles */
170  SCIP_Bool earlytermination /**< whether we terminate early if not all affected variables are binary */
171  );
172 
173 /** determine number of variables affected by symmetry group */
174 SCIP_EXPORT
176  SCIP* scip, /**< SCIP instance */
177  int** perms, /**< permutations */
178  int nperms, /**< number of permutations in perms */
179  SCIP_VAR** permvars, /**< variables corresponding to permutations */
180  int npermvars, /**< number of permvars in perms */
181  int* nvarsaffected /**< pointer to store number of all affected variables */
182  );
183 
184 /** compute components of symmetry group */
185 SCIP_EXPORT
187  SCIP* scip, /**< SCIP instance */
188  int** perms, /**< permutation generators as
189  * (either nperms x npermvars or npermvars x nperms) matrix */
190  int nperms, /**< number of permutations */
191  SCIP_VAR** permvars, /**< variables on which permutations act */
192  int npermvars, /**< number of variables for permutations */
193  SCIP_Bool transposed, /**< transposed permutation generators as (npermvars x nperms) matrix */
194  int** components, /**< array containing the indices of permutations sorted by components */
195  int** componentbegins, /**< array containing in i-th position the first position of
196  * component i in components array */
197  int** vartocomponent, /**< array containing for each permvar the index of the component it is
198  * contained in (-1 if not affected) */
199  unsigned** componentblocked, /**< array to store which symmetry methods have been used on a component
200  * using the same bitset information as for misc/usesymmetry */
201  int* ncomponents /**< pointer to store number of components of symmetry group */
202  );
203 
204 /** Given a matrix with nrows and \#perms + 1 columns whose first nfilledcols columns contain entries of variables, this routine
205  * checks whether the 2-cycles of perm intersect each row of column coltoextend in exactly one position. In this case,
206  * we add one column to the suborbitope of the first nfilledcols columns.
207  *
208  * @pre Every non-trivial cycle of perm is a 2-cycle.
209  * @pre perm has nrows many 2-cycles
210  */
211 SCIP_EXPORT
213  int** suborbitope, /**< matrix containing suborbitope entries */
214  int nrows, /**< number of rows of suborbitope */
215  int nfilledcols, /**< number of columns of suborbitope which are filled with entries */
216  int coltoextend, /**< index of column that should be extended by perm */
217  int* perm, /**< permutation */
218  SCIP_Bool leftextension, /**< whether we extend the suborbitope to the left */
219  int** nusedelems, /**< pointer to array storing how often an element was used in the orbitope */
220  SCIP_VAR** permvars, /**< permutation vars array */
221  SCIP_Shortbool* rowisbinary, /**< array encoding whether variables in an orbitope row are binary */
222  SCIP_Bool* success, /**< pointer to store whether extension was successful */
223  SCIP_Bool* infeasible /**< pointer to store if the number of intersecting cycles is too small */
224  );
225 
226 /** generate variable matrix for orbitope constraint handler */
227 SCIP_EXPORT
229  SCIP* scip, /**< SCIP instance */
230  SCIP_VAR**** vars, /**< pointer to matrix of orbitope variables */
231  int nrows, /**< number of rows of orbitope */
232  int ncols, /**< number of columns of orbitope */
233  SCIP_VAR** permvars, /**< superset of variables that are contained in orbitope */
234  int npermvars, /**< number of variables in permvars array */
235  int** orbitopevaridx, /**< permuted index table of variables in permvars that are contained in orbitope */
236  int* columnorder, /**< permutation to reorder column of orbitopevaridx */
237  int* nusedelems, /**< array storing how often an element was used in the orbitope */
238  SCIP_Shortbool* rowisbinary, /**< array encoding whether a row contains only binary variables */
239  SCIP_Bool* infeasible, /**< pointer to store whether the potential orbitope is not an orbitope */
240  SCIP_Bool storelexorder, /**< whether the lexicographic order induced by the orbitope shall be stored */
241  int** lexorder, /**< pointer to array storing the lexorder (or NULL) */
242  int* nvarsorder, /**< pointer to store number of variables in lexorder (or NULL) */
243  int* maxnvarsorder /**< pointer to store maximum number of variables in lexorder (or NULL) */
244  );
245 
246 /** checks whether an orbitope is a packing or partitioning orbitope */
248  SCIP* scip, /**< SCIP data structure */
249  SCIP_VAR*** vars, /**< variable matrix of orbitope constraint */
250  int nrows, /**< pointer to number of rows of variable matrix */
251  int ncols, /**< number of columns of variable matrix */
252  SCIP_Bool** pprows, /**< pointer to store which rows are are contained in
253  * packing/partitioning constraints or NULL if not needed */
254  int* npprows, /**< pointer to store how many rows are contained
255  * in packing/partitioning constraints or NULL if not needed */
256  SCIP_ORBITOPETYPE* type /**< pointer to store type of orbitope constraint after strengthening */
257  );
258 
259 /** @} */
260 
261 #ifdef __cplusplus
262 }
263 #endif
264 
265 #endif
SCIP_RETCODE SCIPcomputeComponentsSym(SCIP *scip, int **perms, int nperms, SCIP_VAR **permvars, int npermvars, SCIP_Bool transposed, int **components, int **componentbegins, int **vartocomponent, unsigned **componentblocked, int *ncomponents)
Definition: symmetry.c:766
enum SCIP_OrbitopeType SCIP_ORBITOPETYPE
SCIP_RETCODE SCIPcomputeOrbitsSym(SCIP *scip, SCIP_VAR **permvars, int npermvars, int **perms, int nperms, int *orbits, int *orbitbegins, int *norbits)
Definition: symmetry.c:49
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, unsigned *componentblocked, int ncomponents, int nmovedpermvars)
Definition: symmetry.c:163
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
type definitions for return codes for SCIP methods
type definitions for SCIP&#39;s main datastructure
SCIP_RETCODE SCIPisPackingPartitioningOrbitope(SCIP *scip, SCIP_VAR ***vars, int nrows, int ncols, SCIP_Bool **pprows, int *npprows, SCIP_ORBITOPETYPE *type)
Definition: symmetry.c:1161
#define SCIP_Shortbool
Definition: def.h:101
type definitions for problem variables
public data structures and miscellaneous methods
SCIP_RETCODE SCIPdetermineNVarsAffectedSym(SCIP *scip, int **perms, int nperms, SCIP_VAR **permvars, int npermvars, int *nvarsaffected)
Definition: symmetry.c:584
#define SCIP_Bool
Definition: def.h:93
SCIP_RETCODE SCIPisInvolutionPerm(int *perm, SCIP_VAR **vars, int nvars, int *ntwocyclesperm, int *nbincyclesperm, SCIP_Bool earlytermination)
Definition: symmetry.c:533
SCIP_RETCODE SCIPgenerateOrbitopeVarsMatrix(SCIP *scip, SCIP_VAR ****vars, int nrows, int ncols, SCIP_VAR **permvars, int npermvars, int **orbitopevaridx, int *columnorder, int *nusedelems, SCIP_Shortbool *rowisbinary, SCIP_Bool *infeasible, SCIP_Bool storelexorder, int **lexorder, int *nvarsorder, int *maxnvarsorder)
Definition: symmetry.c:970
SCIP_RETCODE SCIPextendSubOrbitope(int **suborbitope, int nrows, int nfilledcols, int coltoextend, int *perm, SCIP_Bool leftextension, int **nusedelems, SCIP_VAR **permvars, SCIP_Shortbool *rowisbinary, SCIP_Bool *success, SCIP_Bool *infeasible)
Definition: symmetry.c:636
type definitions for symmetry computations
SCIP_RETCODE SCIPcomputeOrbitVar(SCIP *scip, int npermvars, int **perms, int **permstrans, int *components, int *componentbegins, SCIP_Shortbool *ignoredvars, SCIP_Shortbool *varfound, int varidx, int component, int *orbit, int *orbitsize)
Definition: symmetry.c:311
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:411
common defines and data types used in all packages of SCIP