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