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 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 65 SCIP_RETCODE SCIPcomputeOrbitsSym( 66 SCIP* scip, /**< SCIP instance */ 67 SCIP_Bool issigend, /**< 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 90 SCIP_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 */ 122 SCIP_EXPORT 123 SCIP_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 */ 146 SCIP_EXPORT 147 SCIP_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 */ 165 SCIP_EXPORT 166 SCIP_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 */ 176 SCIP_EXPORT 177 SCIP_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 */ 187 SCIP_EXPORT 188 SCIP_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 */ 214 SCIP_EXPORT 215 SCIP_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 */ 230 SCIP_EXPORT 231 SCIP_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 */ 250 SCIP_EXPORT 251 SCIP_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 */ 269 SCIP_EXPORT 270 SCIP_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 /** tries to handle variable matrices with lex ordered rows and columns */ 288 SCIP_EXPORT 289 SCIP_RETCODE tryHandleDoubleLexMatrices( 290 SCIP* scip, /**< SCIP pointer */ 291 SCIP_VAR** vars, /**< variables on which permutations act */ 292 int** perms, /**< array of permutations */ 293 int nperms, /**< number of permutations in perms */ 294 int permlen, /**< number of original (non-negated) variables in a permutation */ 295 SCIP_Bool issignedperm, /**< whether permutations are encoded as signed */ 296 SCIP_Bool* success, /**< pointer to store whether symmetries are handled */ 297 int cidx, /**< identifier of component to be handled by double lex matrices */ 298 SCIP_CONS*** genorbconss, /**< pointer to store generated orbitope constraints */ 299 int* ngenorbconss, /**< pointer to store number of generated orbitope constraints */ 300 int* genorbconsssize /**< pointer to store size genorbconss */ 301 ); 302 303 /** helper function to test if val1 = val2 while permitting infinity-values */ 304 SCIP_Bool SCIPEQ( 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 */ 312 SCIP_Bool SCIPLE( 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 */ 320 SCIP_Bool SCIPGE( 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 /** helper function to test if val1 < val2 while permitting infinity-values */ 328 SCIP_Bool SCIPLT( 329 SCIP* scip, /**< SCIP data structure */ 330 SCIP_Real val1, /**< left-hand side value */ 331 SCIP_Real val2 /**< right-hand side value */ 332 ); 333 334 335 /** helper function to test if val1 > val2 while permitting infinity-values */ 336 SCIP_Bool SCIPGT( 337 SCIP* scip, /**< SCIP data structure */ 338 SCIP_Real val1, /**< left-hand side value */ 339 SCIP_Real val2 /**< right-hand side value */ 340 ); 341 342 /** @} */ 343 344 #ifdef __cplusplus 345 } 346 #endif 347 348 #endif 349