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
46extern "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 */
64SCIP_EXPORT
65SCIP_RETCODE SCIPcomputeOrbitsSym(
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 */
89SCIP_EXPORT
90SCIP_RETCODE SCIPcomputeOrbitsFilterSym(
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 */
122SCIP_EXPORT
123SCIP_RETCODE SCIPcomputeOrbitsComponentsSym(
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 */
146SCIP_EXPORT
147SCIP_RETCODE SCIPcomputeOrbitVar(
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 */
165SCIP_EXPORT
166SCIP_RETCODE SCIPisInvolutionPerm(
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 */
176SCIP_EXPORT
177SCIP_RETCODE SCIPdetermineNVarsAffectedSym(
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 */
187SCIP_EXPORT
188SCIP_RETCODE SCIPcomputeComponentsSym(
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 */
214SCIP_EXPORT
215SCIP_RETCODE SCIPextendSubOrbitope(
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 */
230SCIP_EXPORT
231SCIP_RETCODE SCIPgenerateOrbitopeVarsMatrix(
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 */
250SCIP_EXPORT
251SCIP_RETCODE SCIPisPackingPartitioningOrbitope(
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 */
269SCIP_EXPORT
270SCIP_RETCODE SCIPdetectSingleOrDoubleLexMatrices(
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 */
288SCIP_Bool SCIPsymEQ(
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 */
296SCIP_Bool SCIPsymLE(
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 */
304SCIP_Bool SCIPsymGE(
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 */
312SCIP_Bool SCIPsymLT(
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 */
320SCIP_Bool SCIPsymGT(
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
def.h
common defines and data types used in all packages of SCIP
SCIP_Shortbool
#define SCIP_Shortbool
Definition: def.h:99
SCIP_Bool
#define SCIP_Bool
Definition: def.h:91
SCIP_Real
#define SCIP_Real
Definition: def.h:173
SCIPdetermineNVarsAffectedSym
SCIP_RETCODE SCIPdetermineNVarsAffectedSym(SCIP *scip, int **perms, int nperms, SCIP_VAR **permvars, int npermvars, int *nvarsaffected)
Definition: symmetry.c:593
SCIPcomputeComponentsSym
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
SCIPcomputeOrbitVar
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
SCIPisInvolutionPerm
SCIP_RETCODE SCIPisInvolutionPerm(int *perm, SCIP_VAR **vars, int nvars, int *ntwocyclesperm, int *nbincyclesperm, SCIP_Bool earlytermination)
Definition: symmetry.c:542
SCIPsymGE
SCIP_Bool SCIPsymGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: symmetry.c:2283
SCIPcomputeOrbitsComponentsSym
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
SCIPsymEQ
SCIP_Bool SCIPsymEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: symmetry.c:2211
SCIPcomputeOrbitsSym
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
SCIPsymLT
SCIP_Bool SCIPsymLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: symmetry.c:2321
SCIPsymGT
SCIP_Bool SCIPsymGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: symmetry.c:2359
SCIPsymLE
SCIP_Bool SCIPsymLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: symmetry.c:2245
SCIPdetectSingleOrDoubleLexMatrices
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:2051
SCIPgenerateOrbitopeVarsMatrix
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
SCIPisPackingPartitioningOrbitope
SCIP_RETCODE SCIPisPackingPartitioningOrbitope(SCIP *scip, SCIP_VAR ***vars, int nrows, int ncols, SCIP_Bool **pprows, int *npprows, SCIP_ORBITOPETYPE *type)
Definition: symmetry.c:1178
SCIPcomputeOrbitsFilterSym
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
SCIPextendSubOrbitope
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
pub_misc.h
public data structures and miscellaneous methods
SCIP_Var
Definition: struct_var.h:208
type_retcode.h
type definitions for return codes for SCIP methods
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
type_scip.h
type definitions for SCIP's main datastructure
type_symmetry.h
type definitions for symmetry computations
SYM_SYMTYPE
enum SYM_Symtype SYM_SYMTYPE
Definition: type_symmetry.h:64
SCIP_ORBITOPETYPE
enum SCIP_OrbitopeType SCIP_ORBITOPETYPE
Definition: type_symmetry.h:141
type_var.h
type definitions for problem variables