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