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-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.h
26  * @ingroup PUBLICCOREAPI
27  * @brief methods for handling symmetries
28  * @author Jasper van Doornmalen
29  * @author Christopher Hojny
30  * @author Marc Pfetsch
31  */
32 
33 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
34 
35 #ifndef __SCIP_SYMMETRY_H__
36 #define __SCIP_SYMMETRY_H__
37 
38 #include "scip/def.h"
39 #include "scip/pub_misc.h"
40 #include "scip/type_retcode.h"
41 #include "scip/type_scip.h"
42 #include "scip/type_var.h"
43 #include <symmetry/type_symmetry.h>
44 
45 #ifdef __cplusplus
46 extern "C" {
47 #endif
48 
49 
50 /**@addtogroup PublicSymmetryMethods
51  *
52  * @{
53  */
54 
55 
56 /** compute non-trivial orbits of symmetry group
57  *
58  * The non-trivial orbits of the group action are stored in the array orbits of length npermvars. This array contains
59  * the indices of variables from the permvars array such that variables that are contained in the same orbit appear
60  * consecutively in the orbits array. The variables of the i-th orbit have indices
61  * orbits[orbitbegins[i]], ... , orbits[orbitbegins[i + 1] - 1].
62  * Note that the description of the orbits ends at orbitbegins[norbits] - 1.
63  */
64 SCIP_EXPORT
66  SCIP* scip, /**< SCIP instance */
67  SCIP_Bool issigned, /**< whether orbits for signed permutations shall be computed */
68  SCIP_VAR** permvars, /**< variables considered in a permutation array */
69  int npermvars, /**< length of a permutation array */
70  int** perms, /**< matrix containing in each row a permutation of the symmetry group */
71  int nperms, /**< number of permutations encoded in perms */
72  int* orbits, /**< array of non-trivial orbits */
73  int* orbitbegins, /**< array containing begin positions of new orbits in orbits array */
74  int* norbits /**< pointer to number of orbits currently stored in orbits */
75  );
76 
77 
78 /** compute non-trivial orbits of symmetry group using filtered generators
79  *
80  * The non-trivial orbits of the group action are stored in the array orbits of length npermvars. This array contains
81  * the indices of variables from the permvars array such that variables that are contained in the same orbit appear
82  * consecutively in the orbits array. The variables of the i-th orbit have indices
83  * orbits[orbitbegins[i]], ... , orbits[orbitbegins[i + 1] - 1].
84  * Note that the description of the orbits ends at orbitbegins[norbits] - 1.
85  *
86  * Only permutations that are not inactive (as marked by @p inactiveperms) are used. Thus, one can use this array to
87  * filter out permutations.
88  */
89 SCIP_EXPORT
91  SCIP* scip, /**< SCIP instance */
92  int npermvars, /**< length of a permutation array */
93  int** permstrans, /**< transposed matrix containing in each column a
94  * permutation of the symmetry group */
95  int nperms, /**< number of permutations encoded in perms */
96  SCIP_Shortbool* inactiveperms, /**< array to store whether permutations are inactive */
97  int* orbits, /**< array of non-trivial orbits */
98  int* orbitbegins, /**< array containing begin positions of new orbits in orbits array */
99  int* norbits, /**< pointer to number of orbits currently stored in orbits */
100  int* components, /**< array containing the indices of permutations sorted by components */
101  int* componentbegins, /**< array containing in i-th position the first position of
102  * component i in components array */
103  int* vartocomponent, /**< array containing for each permvar the index of the component it is
104  * contained in (-1 if not affected) */
105  unsigned* componentblocked, /**< array to store which symmetry methods have been used on a component
106  * using the same bitset information as for misc/usesymmetry */
107  int ncomponents, /**< number of components of symmetry group */
108  int nmovedpermvars /**< number of variables moved by any permutation in a symmetry component
109  * that is handled by orbital fixing */
110  );
111 
112 /** compute non-trivial orbits of symmetry group
113  *
114  * The non-trivial orbits of the group action are stored in the array orbits of length npermvars. This array contains
115  * the indices of variables from the permvars array such that variables that are contained in the same orbit appear
116  * consecutively in the orbits array. The variables of the i-th orbit have indices
117  * orbits[orbitbegins[i]], ... , orbits[orbitbegins[i + 1] - 1].
118  * Note that the description of the orbits ends at orbitbegins[norbits] - 1.
119  *
120  * This function is adapted from SCIPcomputeOrbitsFilterSym().
121  */
122 SCIP_EXPORT
124  SCIP* scip, /**< SCIP instance */
125  int npermvars, /**< length of a permutation array */
126  int** permstrans, /**< transposed matrix containing in each column a permutation of the symmetry group */
127  int nperms, /**< number of permutations encoded in perms */
128  int* components, /**< array containing the indices of permutations sorted by components */
129  int* componentbegins, /**< array containing in i-th position the first position of component i in components array */
130  int* vartocomponent, /**< array containing for each permvar the index of the component it is
131  * contained in (-1 if not affected) */
132  int ncomponents, /**< number of components of symmetry group */
133  int* orbits, /**< array of non-trivial orbits */
134  int* orbitbegins, /**< array containing begin positions of new orbits in orbits array */
135  int* norbits, /**< pointer to number of orbits currently stored in orbits */
136  int* varorbitmap /**< array for storing the orbits for each variable */
137  );
138 
139 /** Compute orbit of a given variable and store it in @p orbit. The first entry of the orbit will
140  * be the given variable index and the rest is filled with the remaining variables excluding
141  * the ones specified in @p ignoredvars.
142  *
143  * @pre orbit is an initialized array of size propdata->npermvars
144  * @pre at least one of @p perms and @p permstrans should not be NULL
145  */
146 SCIP_EXPORT
148  SCIP* scip, /**< SCIP instance */
149  int npermvars, /**< number of variables in permvars */
150  int** perms, /**< the generators of the permutation group (or NULL) */
151  int** permstrans, /**< the transposed matrix of generators (or NULL) */
152  int* components, /**< the components of the permutation group */
153  int* componentbegins, /**< array containing the starting index of each component */
154  SCIP_Shortbool* ignoredvars, /**< array indicating which variables should be ignored */
155  SCIP_Shortbool* varfound, /**< bitmap to mark which variables have been added (or NULL) */
156  int varidx, /**< index of variable for which the orbit is requested */
157  int component, /**< component that var is in */
158  int * orbit, /**< array in which the orbit should be stored */
159  int* orbitsize /**< buffer to store the size of the orbit */
160  );
161 
162 /** Checks whether a permutation is a composition of 2-cycles and in this case determine the number of overall
163  * 2-cycles and binary 2-cycles. It is a composition of 2-cycles iff @p ntwocyclesperm > 0 upon termination.
164  */
165 SCIP_EXPORT
167  int* perm, /**< permutation */
168  SCIP_VAR** vars, /**< array of variables perm is acting on */
169  int nvars, /**< number of variables */
170  int* ntwocyclesperm, /**< pointer to store number of 2-cycles */
171  int* nbincyclesperm, /**< pointer to store number of binary cycles */
172  SCIP_Bool earlytermination /**< whether we terminate early if not all affected variables are binary */
173  );
174 
175 /** determine number of variables affected by symmetry group */
176 SCIP_EXPORT
178  SCIP* scip, /**< SCIP instance */
179  int** perms, /**< permutations */
180  int nperms, /**< number of permutations in perms */
181  SCIP_VAR** permvars, /**< variables corresponding to permutations */
182  int npermvars, /**< number of permvars in perms */
183  int* nvarsaffected /**< pointer to store number of all affected variables */
184  );
185 
186 /** compute components of symmetry group */
187 SCIP_EXPORT
189  SCIP* scip, /**< SCIP instance */
190  SYM_SYMTYPE symtype, /**< type of symmetries in perms */
191  int** perms, /**< permutation generators as
192  * (either nperms x npermvars or npermvars x nperms) matrix */
193  int nperms, /**< number of permutations */
194  SCIP_VAR** permvars, /**< variables on which permutations act */
195  int npermvars, /**< number of variables for permutations */
196  SCIP_Bool transposed, /**< transposed permutation generators as (npermvars x nperms) matrix */
197  int** components, /**< array containing the indices of permutations sorted by components */
198  int** componentbegins, /**< array containing in i-th position the first position of
199  * component i in components array */
200  int** vartocomponent, /**< array containing for each permvar the index of the component it is
201  * contained in (-1 if not affected) */
202  unsigned** componentblocked, /**< array to store which symmetry methods have been used on a component
203  * using the same bitset information as for misc/usesymmetry */
204  int* ncomponents /**< pointer to store number of components of symmetry group */
205  );
206 
207 /** Given a matrix with nrows and \#perms + 1 columns whose first nfilledcols columns contain entries of variables, this routine
208  * checks whether the 2-cycles of perm intersect each row of column coltoextend in exactly one position. In this case,
209  * we add one column to the suborbitope of the first nfilledcols columns.
210  *
211  * @pre Every non-trivial cycle of perm is a 2-cycle.
212  * @pre perm has nrows many 2-cycles
213  */
214 SCIP_EXPORT
216  int** suborbitope, /**< matrix containing suborbitope entries */
217  int nrows, /**< number of rows of suborbitope */
218  int nfilledcols, /**< number of columns of suborbitope which are filled with entries */
219  int coltoextend, /**< index of column that should be extended by perm */
220  int* perm, /**< permutation */
221  SCIP_Bool leftextension, /**< whether we extend the suborbitope to the left */
222  int** nusedelems, /**< pointer to array storing how often an element was used in the orbitope */
223  SCIP_VAR** permvars, /**< permutation vars array */
224  SCIP_Shortbool* rowisbinary, /**< array encoding whether variables in an orbitope row are binary */
225  SCIP_Bool* success, /**< pointer to store whether extension was successful */
226  SCIP_Bool* infeasible /**< pointer to store if the number of intersecting cycles is too small */
227  );
228 
229 /** generate variable matrix for orbitope constraint handler */
230 SCIP_EXPORT
232  SCIP* scip, /**< SCIP instance */
233  SCIP_VAR**** vars, /**< pointer to matrix of orbitope variables */
234  int nrows, /**< number of rows of orbitope */
235  int ncols, /**< number of columns of orbitope */
236  SCIP_VAR** permvars, /**< superset of variables that are contained in orbitope */
237  int npermvars, /**< number of variables in permvars array */
238  int** orbitopevaridx, /**< permuted index table of variables in permvars that are contained in orbitope */
239  int* columnorder, /**< permutation to reorder column of orbitopevaridx */
240  int* nusedelems, /**< array storing how often an element was used in the orbitope */
241  SCIP_Shortbool* rowisbinary, /**< array encoding whether a row contains only binary variables */
242  SCIP_Bool* infeasible, /**< pointer to store whether the potential orbitope is not an orbitope */
243  SCIP_Bool storelexorder, /**< whether the lexicographic order induced by the orbitope shall be stored */
244  int** lexorder, /**< pointer to array storing the lexorder (or NULL) */
245  int* nvarsorder, /**< pointer to store number of variables in lexorder (or NULL) */
246  int* maxnvarsorder /**< pointer to store maximum number of variables in lexorder (or NULL) */
247  );
248 
249 /** checks whether an orbitope is a packing or partitioning orbitope */
250 SCIP_EXPORT
252  SCIP* scip, /**< SCIP data structure */
253  SCIP_VAR*** vars, /**< variable matrix of orbitope constraint */
254  int nrows, /**< pointer to number of rows of variable matrix */
255  int ncols, /**< number of columns of variable matrix */
256  SCIP_Bool** pprows, /**< pointer to store which rows are are contained in
257  * packing/partitioning constraints or NULL if not needed */
258  int* npprows, /**< pointer to store how many rows are contained
259  * in packing/partitioning constraints or NULL if not needed */
260  SCIP_ORBITOPETYPE* type /**< pointer to store type of orbitope constraint after strengthening */
261  );
262 
263 /** detects whether permutations define single or double lex matrices
264  *
265  * A single lex matrix is a matrix whose columns can be partitioned into blocks such that the
266  * columns within each block can be permuted arbitrarily. A double lex matrix is a single lex
267  * matrix such that also blocks of rows have the aforementioned property.
268  */
269 SCIP_EXPORT
271  SCIP* scip, /**< SCIP pointer */
272  SCIP_Bool detectsinglelex, /**< whether single lex matrices shall be detected */
273  int** perms, /**< array of permutations */
274  int nperms, /**< number of permutations in perms */
275  int permlen, /**< number of variables in a permutation */
276  SCIP_Bool* success, /**< pointer to store whether structure could be detected */
277  SCIP_Bool* isorbitope, /**< pointer to store whether detected matrix is orbitopal */
278  int*** lexmatrix, /**< pointer to store single or double lex matrix */
279  int* nrows, /**< pointer to store number of rows of lexmatrix */
280  int* ncols, /**< pointer to store number of columns of lexmatrix */
281  int** lexrowsbegin, /**< pointer to store array indicating begin of new row-lexmatrix */
282  int** lexcolsbegin, /**< pointer to store array indicating begin of new col-lexmatrix */
283  int* nrowmatrices, /**< pointer to store number of single lex row matrices in rows */
284  int* ncolmatrices /**< pointer to store number of single lex column matrices in rows */
285  );
286 
287 /** helper function to test if val1 = val2 while permitting infinity-values */
289  SCIP* scip, /**< SCIP data structure */
290  SCIP_Real val1, /**< left-hand side value */
291  SCIP_Real val2 /**< right-hand side value */
292  );
293 
294 
295 /** helper function to test if val1 <= val2 while permitting infinity-values */
297  SCIP* scip, /**< SCIP data structure */
298  SCIP_Real val1, /**< left-hand side value */
299  SCIP_Real val2 /**< right-hand side value */
300  );
301 
302 
303 /** helper function to test if val1 >= val2 while permitting infinity-values */
305  SCIP* scip, /**< SCIP data structure */
306  SCIP_Real val1, /**< left-hand side value */
307  SCIP_Real val2 /**< right-hand side value */
308  );
309 
310 
311 /** helper function to test if val1 < val2 while permitting infinity-values */
313  SCIP* scip, /**< SCIP data structure */
314  SCIP_Real val1, /**< left-hand side value */
315  SCIP_Real val2 /**< right-hand side value */
316  );
317 
318 
319 /** helper function to test if val1 > val2 while permitting infinity-values */
321  SCIP* scip, /**< SCIP data structure */
322  SCIP_Real val1, /**< left-hand side value */
323  SCIP_Real val2 /**< right-hand side value */
324  );
325 
326 /** @} */
327 
328 #ifdef __cplusplus
329 }
330 #endif
331 
332 #endif
enum SCIP_OrbitopeType SCIP_ORBITOPETYPE
SCIP_Bool SCIPsymEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: symmetry.c:2192
SCIP_RETCODE SCIPcomputeOrbitsSym(SCIP *scip, SCIP_Bool issigned, SCIP_VAR **permvars, int npermvars, int **perms, int nperms, int *orbits, int *orbitbegins, int *norbits)
Definition: symmetry.c:52
SCIP_Bool SCIPsymLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: symmetry.c:2302
SCIP_RETCODE SCIPcomputeComponentsSym(SCIP *scip, SYM_SYMTYPE symtype, 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:775
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:172
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:1178
#define SCIP_Shortbool
Definition: def.h:99
SCIP_RETCODE SCIPdetectSingleOrDoubleLexMatrices(SCIP *scip, SCIP_Bool detectsinglelex, int **perms, int nperms, int permlen, SCIP_Bool *success, SCIP_Bool *isorbitope, int ***lexmatrix, int *nrows, int *ncols, int **lexrowsbegin, int **lexcolsbegin, int *nrowmatrices, int *ncolmatrices)
Definition: symmetry.c:2024
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:593
#define SCIP_Bool
Definition: def.h:91
SCIP_RETCODE SCIPisInvolutionPerm(int *perm, SCIP_VAR **vars, int nvars, int *ntwocyclesperm, int *nbincyclesperm, SCIP_Bool earlytermination)
Definition: symmetry.c:542
SCIP_Bool SCIPsymGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: symmetry.c:2264
enum SYM_Symtype SYM_SYMTYPE
Definition: type_symmetry.h:60
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:987
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:645
SCIP_Bool SCIPsymGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: symmetry.c:2340
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:320
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:420
#define SCIP_Real
Definition: def.h:173
SCIP_Bool SCIPsymLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: symmetry.c:2226
common defines and data types used in all packages of SCIP