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 cons_orbitope.h 26 * @ingroup CONSHDLRS 27 * @brief constraint handler for (partitioning/packing/full) orbitope constraints w.r.t. the full symmetric group 28 * @author Timo Berthold 29 * @author Marc Pfetsch 30 * @author Christopher Hojny 31 */ 32 33 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 34 35 #ifndef __SCIP_CONS_ORBITOPE_H__ 36 #define __SCIP_CONS_ORBITOPE_H__ 37 38 #include "scip/def.h" 39 #include "scip/type_cons.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 /** creates the handler for orbitope constraints and includes it in SCIP 50 * 51 * @ingroup ConshdlrIncludes 52 */ 53 SCIP_EXPORT 54 SCIP_RETCODE SCIPincludeConshdlrOrbitope( 55 SCIP* scip /**< SCIP data structure */ 56 ); 57 58 /**@addtogroup CONSHDLRS 59 * 60 * @{ 61 * 62 * @name Orbitope Constraints 63 * 64 * @{ 65 * 66 * This constraint handler can be used to handle symmetries in certain 0/1-programs. The principle 67 * structure is that some variables can be ordered in matrix form, such that permuting columns does 68 * not change the validity and objective function value of a solution. That is, the symmetry group 69 * of the program contains the full symmetric group obtained by permuting the columns of this 70 * matrix. These symmetries can be handled by so-called full orbitopes. 71 * 72 * Moreover, if the variables in each row are contained in set packing or partitioning 73 * constraint, these symmetries can be handled by specialized packing or partitioning orbitopes. 74 * 75 * In more mathematical terms the structure has to be as follows: There are 0/1-variables 76 * \f$x_{ij}\f$, \f$i \in \{1, \dots, p\}\f$, \f$j \in \{1, \dots, q\}\f$. The variables may be coupled 77 * through set packing or partitioning constraints: 78 * \f[ 79 * \sum_{j = 1}^q x_{ij} \leq 1 \quad \mbox{or} \quad \sum_{j = 1}^q x_{ij} = 1 \quad \mbox{for all }i = 1, \ldots, p. 80 * \f] 81 * Permuting columns of \f$x\f$ does not change the validity and objective function value of any feasible solution. 82 * 83 * We distinguish whether an orbitope is a model constraint or not. If it is a model constraint, then 84 * its information are copied to subSCIPs. Otherwise, the constraint was added just for the purpose of 85 * symmetry handling and we do not copy its information to subSCIPs. 86 */ 87 88 /** creates and captures a orbitope constraint 89 * 90 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 91 */ 92 SCIP_EXPORT 93 SCIP_RETCODE SCIPcreateConsOrbitope( 94 SCIP* scip, /**< SCIP data structure */ 95 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 96 const char* name, /**< name of constraint */ 97 SCIP_VAR*** vars, /**< matrix of variables on which the symmetry acts */ 98 SCIP_ORBITOPETYPE orbitopetype, /**< type of orbitope constraint */ 99 int nspcons, /**< number of set partitioning/packing constraints <=> p */ 100 int nblocks, /**< number of symmetric variable blocks <=> q */ 101 SCIP_Bool usedynamicprop, /**< whether dynamic propagation should be used */ 102 SCIP_Bool mayinteract, /**< whether symmetries corresponding to orbitope might interact 103 * with symmetries handled by other routines */ 104 SCIP_Bool resolveprop, /**< should propagation be resolved? */ 105 SCIP_Bool ismodelcons, /**< whether the orbitope is a model constraint */ 106 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP? 107 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */ 108 SCIP_Bool separate, /**< should the constraint be separated during LP processing? 109 * Usually set to TRUE. */ 110 SCIP_Bool enforce, /**< should the constraint be enforced during node processing? 111 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 112 SCIP_Bool check, /**< should the constraint be checked for feasibility? 113 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 114 SCIP_Bool propagate, /**< should the constraint be propagated during node processing? 115 * Usually set to TRUE. */ 116 SCIP_Bool local, /**< is constraint only valid locally? 117 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */ 118 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)? 119 * Usually set to FALSE. In column generation applications, set to TRUE if pricing 120 * adds coefficients to this constraint. */ 121 SCIP_Bool dynamic, /**< is constraint subject to aging? 122 * Usually set to FALSE. Set to TRUE for own cuts which 123 * are separated as constraints. */ 124 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup? 125 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */ 126 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even 127 * if it may be moved to a more global node? 128 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */ 129 ); 130 131 /** creates and captures an orbitope constraint 132 * in its most basic variant, i. e., with all constraint flags set to their default values, which can be set 133 * afterwards using SCIPsetConsFLAGNAME() in scip.h 134 * 135 * @see SCIPcreateConsOrbitope() for the default constraint flag configuration 136 * 137 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 138 */ 139 SCIP_EXPORT 140 SCIP_RETCODE SCIPcreateConsBasicOrbitope( 141 SCIP* scip, /**< SCIP data structure */ 142 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 143 const char* name, /**< name of constraint */ 144 SCIP_VAR*** vars, /**< matrix of variables on which the symmetry acts */ 145 SCIP_ORBITOPETYPE orbitopetype, /**< type of orbitope constraint */ 146 int nspcons, /**< number of set partitioning/packing constraints <=> p */ 147 int nblocks, /**< number of symmetric variable blocks <=> q */ 148 SCIP_Bool usedynamicprop, /**< whether dynamic propagation should be used */ 149 SCIP_Bool resolveprop, /**< should propagation be resolved? */ 150 SCIP_Bool ismodelcons, /**< whether the orbitope is a model constraint */ 151 SCIP_Bool mayinteract /**< whether symmetries corresponding to orbitope might interact 152 * with symmetries handled by other routines */ 153 ); 154 155 /** @} */ 156 157 /** @} */ 158 159 #ifdef __cplusplus 160 } 161 #endif 162 163 #endif 164