SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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"
43
44#ifdef __cplusplus
45extern "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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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
common defines and data types used in all packages of SCIP
#define SCIP_Shortbool
Definition def.h:101
SCIP_RETCODE SCIPdetermineNVarsAffectedSym(SCIP *scip, int **perms, int nperms, SCIP_VAR **permvars, int npermvars, int *nvarsaffected)
Definition symmetry.c:584
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
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 SCIPisInvolutionPerm(int *perm, SCIP_VAR **vars, int nvars, int *ntwocyclesperm, int *nbincyclesperm, SCIP_Bool earlytermination)
Definition symmetry.c:533
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 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
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 SCIPisPackingPartitioningOrbitope(SCIP *scip, SCIP_VAR ***vars, int nrows, int ncols, SCIP_Bool **pprows, int *npprows, SCIP_ORBITOPETYPE *type)
Definition symmetry.c:1161
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
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
int nvars
static SCIP_VAR ** vars
public data structures and miscellaneous methods
type definitions for return codes for SCIP methods
enum SCIP_Retcode SCIP_RETCODE
type definitions for SCIP's main datastructure
type definitions for symmetry computations
enum SCIP_OrbitopeType SCIP_ORBITOPETYPE
type definitions for problem variables