Scippy

    SCIP

    Solving Constraint Integer Programs

    cons_symresack.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 cons_symresack.h
    26 * @ingroup CONSHDLRS
    27 * @brief constraint handler for symresack constraints
    28 * @author Christopher Hojny
    29 *
    30 */
    31
    32/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
    33
    34#ifndef __SCIP_CONS_SYMRESACK_H__
    35#define __SCIP_CONS_SYMRESACK_H__
    36
    37#include "scip/def.h"
    38#include "scip/type_cons.h"
    39#include "scip/type_retcode.h"
    40#include "scip/type_scip.h"
    41#include "scip/type_var.h"
    42
    43#ifdef __cplusplus
    44extern "C" {
    45#endif
    46
    47
    48
    49/** creates the handler for symresack constraints and includes it in SCIP
    50 *
    51 * @ingroup ConshdlrIncludes
    52 */
    53SCIP_EXPORT
    54SCIP_RETCODE SCIPincludeConshdlrSymresack(
    55 SCIP* scip /**< SCIP data structure */
    56 );
    57
    58/**@addtogroup CONSHDLRS
    59 *
    60 * @{
    61 *
    62 * @name Symresack Constraints
    63 *
    64 * @{
    65 *
    66 * Given a permutation that acts on the order of the variables of a (mixed) 0/1-program
    67 * such that the permutation is a symmetry of the program, this constraint handler can
    68 * be used to handle the symmetries corresponding to the permutation. The symmetries
    69 * are handled by enforcing that a binary solution is lexicographically not smaller than
    70 * its permutation. In a presolving step, we check whether the permutation acts only on
    71 * binary points. Otherwise, we eliminate the non-binary variables from the permutation.
    72 * Furthermore, we delete fixed points from the permutation.
    73 *
    74 * Moreover, the constraint handler checks whether each cycle of the permutation is
    75 * contained in a set packing or partitioning constraint. In this case, the symresack
    76 * is strengthened to a ppsymresack and strong symmetry handling inequalities are added during
    77 * the initialization of the constraint handler.
    78 *
    79 * @pre The permutation is encoded by an array perm for which perm[i] = j if and only if
    80 * the image of i under the permutation is j.
    81 *
    82 * @pre The permutation given to the constraint handler has to be a symmetry of the
    83 * underlying problem. This is NOT checked by the constraint handler.
    84 */
    85
    86/** creates a symmetry breaking constraint
    87 *
    88 * Depending on the given permutation, either an orbisack or symresack constraint
    89 * is created.
    90 */
    91SCIP_EXPORT
    92SCIP_RETCODE SCIPcreateSymbreakCons(
    93 SCIP* scip, /**< SCIP data structure */
    94 SCIP_CONS** cons, /**< pointer to hold the created constraint */
    95 const char* name, /**< name of constraint */
    96 int* perm, /**< permutation */
    97 SCIP_VAR** vars, /**< variables */
    98 int nvars, /**< number of variables in vars array */
    99 SCIP_Bool ismodelcons, /**< whether the added constraint is a model constraint */
    100 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
    101 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
    102 SCIP_Bool separate, /**< should the constraint be separated during LP processing?
    103 * Usually set to TRUE. */
    104 SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
    105 * TRUE for model constraints, FALSE for additional, redundant constraints. */
    106 SCIP_Bool check, /**< should the constraint be checked for feasibility?
    107 * TRUE for model constraints, FALSE for additional, redundant constraints. */
    108 SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
    109 * Usually set to TRUE. */
    110 SCIP_Bool local, /**< is constraint only valid locally?
    111 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
    112 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
    113 * Usually set to FALSE. In column generation applications, set to TRUE if pricing
    114 * adds coefficients to this constraint. */
    115 SCIP_Bool dynamic, /**< is constraint subject to aging?
    116 * Usually set to FALSE. Set to TRUE for own cuts which
    117 * are separated as constraints. */
    118 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
    119 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
    120 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
    121 * if it may be moved to a more global node?
    122 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
    123 );
    124
    125
    126/** creates and captures a symresack constraint
    127 *
    128 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
    129 */
    130SCIP_EXPORT
    131SCIP_RETCODE SCIPcreateConsSymresack(
    132 SCIP* scip, /**< SCIP data structure */
    133 SCIP_CONS** cons, /**< pointer to hold the created constraint */
    134 const char* name, /**< name of constraint */
    135 int* perm, /**< permutation */
    136 SCIP_VAR** vars, /**< variables */
    137 int nvars, /**< number of variables in vars array */
    138 SCIP_Bool ismodelcons, /**< whether the symresack is a model constraint */
    139 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
    140 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
    141 SCIP_Bool separate, /**< should the constraint be separated during LP processing?
    142 * Usually set to TRUE. */
    143 SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
    144 * TRUE for model constraints, FALSE for additional, redundant constraints. */
    145 SCIP_Bool check, /**< should the constraint be checked for feasibility?
    146 * TRUE for model constraints, FALSE for additional, redundant constraints. */
    147 SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
    148 * Usually set to TRUE. */
    149 SCIP_Bool local, /**< is constraint only valid locally?
    150 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
    151 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
    152 * Usually set to FALSE. In column generation applications, set to TRUE if pricing
    153 * adds coefficients to this constraint. */
    154 SCIP_Bool dynamic, /**< is constraint subject to aging?
    155 * Usually set to FALSE. Set to TRUE for own cuts which
    156 * are separated as constraints. */
    157 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
    158 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
    159 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
    160 * if it may be moved to a more global node?
    161 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
    162 );
    163
    164/** creates and captures a symresack constraint
    165 * in its most basic variant, i.e., with all constraint flags set to their default values, which can be set
    166 * afterwards using SCIPsetConsFLAGNAME() in scip.h
    167 *
    168 * @see SCIPcreateConsSymresack() for the default constraint flag configuration
    169 *
    170 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
    171 */
    172SCIP_EXPORT
    173SCIP_RETCODE SCIPcreateConsBasicSymresack(
    174 SCIP* scip, /**< SCIP data structure */
    175 SCIP_CONS** cons, /**< pointer to hold the created constraint */
    176 const char* name, /**< name of constraint */
    177 int* perm, /**< permutation */
    178 SCIP_VAR** vars, /**< variables */
    179 int nvars, /**< number of variables in vars array */
    180 SCIP_Bool ismodelcons /**< whether the symresack is a model constraint */
    181 );
    182
    183/** @} */
    184
    185/** @} */
    186
    187#ifdef __cplusplus
    188}
    189#endif
    190
    191#endif
    def.h
    common defines and data types used in all packages of SCIP
    SCIP_Bool
    #define SCIP_Bool
    Definition: def.h:91
    SCIPcreateSymbreakCons
    SCIP_RETCODE SCIPcreateSymbreakCons(SCIP *scip, SCIP_CONS **cons, const char *name, int *perm, SCIP_VAR **vars, int nvars, SCIP_Bool ismodelcons, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
    Definition: cons_symresack.c:1731
    SCIPcreateConsBasicSymresack
    SCIP_RETCODE SCIPcreateConsBasicSymresack(SCIP *scip, SCIP_CONS **cons, const char *name, int *perm, SCIP_VAR **vars, int nvars, SCIP_Bool ismodelcons)
    Definition: cons_symresack.c:3275
    SCIPcreateConsSymresack
    SCIP_RETCODE SCIPcreateConsSymresack(SCIP *scip, SCIP_CONS **cons, const char *name, int *perm, SCIP_VAR **vars, int nvars, SCIP_Bool ismodelcons, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
    Definition: cons_symresack.c:3210
    SCIPincludeConshdlrSymresack
    SCIP_RETCODE SCIPincludeConshdlrSymresack(SCIP *scip)
    Definition: cons_symresack.c:3147
    separate
    static SCIP_RETCODE separate(SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_RESULT *result)
    Main separation function.
    Definition: sepa_flower.c:1221
    SCIP_Cons
    Definition: struct_cons.h:47
    SCIP_Var
    Definition: struct_var.h:262
    type_cons.h
    type definitions for constraints and constraint handlers
    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_var.h
    type definitions for problem variables