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 scip_reopt.h 26 * @ingroup PUBLICCOREAPI 27 * @brief public methods for reoptimization 28 * @author Tobias Achterberg 29 * @author Timo Berthold 30 * @author Thorsten Koch 31 * @author Alexander Martin 32 * @author Marc Pfetsch 33 * @author Kati Wolter 34 * @author Gregor Hendel 35 * @author Leona Gottwald 36 */ 37 38 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 39 40 #ifndef __SCIP_SCIP_REOPT_H__ 41 #define __SCIP_SCIP_REOPT_H__ 42 43 44 #include "scip/def.h" 45 #include "scip/type_lp.h" 46 #include "scip/type_reopt.h" 47 #include "scip/type_retcode.h" 48 #include "scip/type_scip.h" 49 #include "scip/type_tree.h" 50 #include "scip/type_var.h" 51 52 #ifdef __cplusplus 53 extern "C" { 54 #endif 55 56 /**@addtogroup PublicReoptimizationMethods 57 * 58 * @{ 59 */ 60 61 /** return the ids of child nodes stored in the reoptimization tree 62 * 63 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 64 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 65 * 66 * @pre This method can be called if @p scip is in one of the following stages: 67 * - \ref SCIP_STAGE_PRESOLVED 68 * - \ref SCIP_STAGE_SOLVING 69 * - \ref SCIP_STAGE_SOLVED 70 */ 71 SCIP_EXPORT 72 SCIP_RETCODE SCIPgetReoptChildIDs( 73 SCIP* scip, /**< SCIP data structure */ 74 SCIP_NODE* node, /**< node of the search tree */ 75 unsigned int* ids, /**< array to store the ids of child nodes */ 76 int mem, /**< allocated memory */ 77 int* nids /**< number of child nodes */ 78 ); 79 80 /** return the ids of all leave nodes store in the reoptimization tree induced by the given node 81 * 82 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 83 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 84 * 85 * @pre This method can be called if @p scip is in one of the following stages: 86 * - \ref SCIP_STAGE_PRESOLVED 87 * - \ref SCIP_STAGE_SOLVING 88 * - \ref SCIP_STAGE_SOLVED 89 */ 90 SCIP_EXPORT 91 SCIP_RETCODE SCIPgetReoptLeaveIDs( 92 SCIP* scip, /**< SCIP data strcuture */ 93 SCIP_NODE* node, /**< node of the search tree */ 94 unsigned int* ids, /**< array of ids */ 95 int mem, /**< allocated memory */ 96 int* nids /**< number of child nodes */ 97 ); 98 99 /** returns the number of nodes in the reoptimization tree induced by @p node; if @p node == NULL, the method 100 * returns the number of nodes of the whole reoptimization tree. 101 */ 102 SCIP_EXPORT 103 int SCIPgetNReoptnodes( 104 SCIP* scip, /**< SCIP data structure */ 105 SCIP_NODE* node /**< node of the search tree */ 106 ); 107 108 /** returns the number of leave nodes of the subtree induced by @p node; if @p node == NULL, the method 109 * returns the number of leaf nodes of the whole reoptimization tree. 110 */ 111 SCIP_EXPORT 112 int SCIPgetNReoptLeaves( 113 SCIP* scip, /**< SCIP data structure */ 114 SCIP_NODE* node /**< node of the search tree */ 115 ); 116 117 /** gets the node of the reoptimization tree corresponding to the unique @p id */ 118 SCIP_REOPTNODE* SCIPgetReoptnode( 119 SCIP* scip, /**< SCIP data structure */ 120 unsigned int id /**< unique id */ 121 ); 122 123 /** add a variable bound change to a given reoptnode 124 * 125 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 126 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 127 * 128 * @pre This method can be called if @p scip is in one of the following stages: 129 * - \ref SCIP_STAGE_PRESOLVED 130 * - \ref SCIP_STAGE_SOLVING 131 * - \ref SCIP_STAGE_SOLVED 132 */ 133 SCIP_EXPORT 134 SCIP_RETCODE SCIPaddReoptnodeBndchg( 135 SCIP* scip, /**< SCIP data structure */ 136 SCIP_REOPTNODE* reoptnode, /**< node of the reoptimization tree */ 137 SCIP_VAR* var, /**< variable pointer */ 138 SCIP_Real bound, /**< variable bound to add */ 139 SCIP_BOUNDTYPE boundtype /**< bound type of the variable value */ 140 ); 141 142 /** set the @p representation as the new search frontier 143 * 144 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 145 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 146 * 147 * @pre This method can be called if @p scip is in one of the following stages: 148 * - \ref SCIP_STAGE_PRESOLVED 149 */ 150 SCIP_EXPORT 151 SCIP_RETCODE SCIPsetReoptCompression( 152 SCIP* scip, /**< SCIP data structure */ 153 SCIP_REOPTNODE** representation, /**< array of representatives */ 154 int nrepresentatives, /**< number of representatives */ 155 SCIP_Bool* success /**< pointer to store the result */ 156 ); 157 158 /** add stored constraint to a reoptimization node 159 * 160 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 161 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 162 * 163 * @pre This method can be called if @p scip is in one of the following stages: 164 * - \ref SCIP_STAGE_PRESOLVED 165 */ 166 SCIP_EXPORT 167 SCIP_RETCODE SCIPaddReoptnodeCons( 168 SCIP* scip, /**< SCIP data structure */ 169 SCIP_REOPTNODE* reoptnode, /**< node of the reoptimization tree */ 170 SCIP_VAR** vars, /**< array of variables */ 171 SCIP_Real* vals, /**< array of variable bounds */ 172 SCIP_BOUNDTYPE* boundtypes, /**< array of variable boundtypes */ 173 SCIP_Real lhs, /**< lhs of the constraint */ 174 SCIP_Real rhs, /**< rhs of the constraint */ 175 int nvars, /**< number of variables */ 176 REOPT_CONSTYPE constype, /**< type of the constraint */ 177 SCIP_Bool linear /**< the given constraint has a linear representation */ 178 ); 179 180 /** return the branching path stored in the reoptree at ID id */ 181 SCIP_EXPORT 182 void SCIPgetReoptnodePath( 183 SCIP* scip, /**< SCIP data structure */ 184 SCIP_REOPTNODE* reoptnode, /**< node of the reoptimization tree */ 185 SCIP_VAR** vars, /**< array of variables */ 186 SCIP_Real* vals, /**< array of variable bounds */ 187 SCIP_BOUNDTYPE* boundtypes, /**< array of bound types */ 188 int mem, /**< allocated memory */ 189 int* nvars, /**< number of variables */ 190 int* nafterdualvars /**< number of variables directly after the first based on dual information */ 191 ); 192 193 /** initialize a set of empty reoptimization nodes 194 * 195 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 196 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 197 * 198 * @pre This method can be called if @p scip is in one of the following stages: 199 * - \ref SCIP_STAGE_PRESOLVED 200 */ 201 SCIP_EXPORT 202 SCIP_RETCODE SCIPinitRepresentation( 203 SCIP* scip, /**< SCIP data structure */ 204 SCIP_REOPTNODE** representatives, /**< array of representatives */ 205 int nrepresentatives /**< number of representatives */ 206 ); 207 208 /** reset a set of initialized reoptimization nodes 209 * 210 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 211 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 212 * 213 * @pre This method can be called if @p scip is in one of the following stages: 214 * - \ref SCIP_STAGE_PRESOLVED 215 */ 216 SCIP_RETCODE SCIPresetRepresentation( 217 SCIP* scip, /**< SCIP data structure */ 218 SCIP_REOPTNODE** representatives, /**< array of representatives */ 219 int nrepresentatives /**< number of representatives */ 220 ); 221 222 /** free a set of initialized reoptimization nodes 223 * 224 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 225 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 226 * 227 * @pre This method can be called if @p scip is in one of the following stages: 228 * - \ref SCIP_STAGE_PRESOLVED 229 */ 230 SCIP_EXPORT 231 SCIP_RETCODE SCIPfreeRepresentation( 232 SCIP* scip, /**< SCIP data structure */ 233 SCIP_REOPTNODE** representatives, /**< array of representatives */ 234 int nrepresentatives /**< number of representatives */ 235 ); 236 237 /** reactivate the given @p reoptnode and split them into several nodes if necessary 238 * 239 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 240 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 241 * 242 * @pre This method can be called if @p scip is in one of the following stages: 243 * - \ref SCIP_STAGE_SOLVING 244 * - \ref SCIP_STAGE_SOLVED 245 */ 246 SCIP_EXPORT 247 SCIP_RETCODE SCIPapplyReopt( 248 SCIP* scip, /**< SCIP data structure */ 249 SCIP_REOPTNODE* reoptnode, /**< node to reactivate */ 250 unsigned int id, /**< unique id of the reoptimization node */ 251 SCIP_Real estimate, /**< estimate of the child nodes that should be created */ 252 SCIP_NODE** childnodes, /**< array to store the created child nodes */ 253 int* ncreatedchilds, /**< pointer to store number of created child nodes */ 254 int* naddedconss, /**< pointer to store number of generated constraints */ 255 int childnodessize, /**< available size of childnodes array */ 256 SCIP_Bool* success /**< pointer store the result*/ 257 ); 258 259 /** remove the stored information about bound changes based in dual information 260 * 261 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 262 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 263 * 264 * @pre This method can be called if @p scip is in one of the following stages: 265 * - \ref SCIP_STAGE_SOLVING 266 * - \ref SCIP_STAGE_SOLVED 267 */ 268 SCIP_EXPORT 269 SCIP_RETCODE SCIPresetReoptnodeDualcons( 270 SCIP* scip, /**< SCIP data structure */ 271 SCIP_NODE* node /**< node of the search tree */ 272 ); 273 274 /** splits the root into several nodes and moves the child nodes of the root to one of the created nodes 275 * 276 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 277 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 278 * 279 * @pre This method can be called if @p scip is in one of the following stages: 280 * - \ref SCIP_STAGE_TRANSFORMED 281 * - \ref SCIP_STAGE_SOLVING 282 */ 283 SCIP_EXPORT 284 SCIP_RETCODE SCIPsplitReoptRoot( 285 SCIP* scip, /**< SCIP data structure */ 286 int* ncreatedchilds, /**< pointer to store the number of created nodes */ 287 int* naddedconss /**< pointer to store the number added constraints */ 288 ); 289 290 /** returns if a node should be reoptimized */ 291 SCIP_EXPORT 292 SCIP_Bool SCIPreoptimizeNode( 293 SCIP* scip, /**< SCIP data structure */ 294 SCIP_NODE* node /**< node of the search tree */ 295 ); 296 297 /** deletes the given reoptimization node 298 * 299 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 300 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 301 * 302 * @pre This method can be called if @p scip is in one of the following stages: 303 * - \ref SCIP_STAGE_SOLVING 304 */ 305 SCIP_EXPORT 306 SCIP_RETCODE SCIPdeleteReoptnode( 307 SCIP* scip, /**< SCIP data structure */ 308 SCIP_REOPTNODE** reoptnode /**< node of the reoptimization tree */ 309 ); 310 311 /** return the similarity between two objective functions */ 312 SCIP_EXPORT 313 SCIP_Real SCIPgetReoptSimilarity( 314 SCIP* scip, /**< SCIP data structure */ 315 int run1, /**< number of run */ 316 int run2 /**< number of run */ 317 ); 318 319 /** check the changes of the variable coefficient in the objective function */ 320 SCIP_EXPORT 321 void SCIPgetVarCoefChg( 322 SCIP* scip, /**< SCIP data structure */ 323 int varidx, /**< index of variable */ 324 SCIP_Bool* negated, /**< coefficient changed the sign */ 325 SCIP_Bool* entering, /**< coefficient gets non-zero coefficient */ 326 SCIP_Bool* leaving /**< coefficient gets zero coefficient */ 327 ); 328 329 /** @} */ 330 331 #ifdef __cplusplus 332 } 333 #endif 334 335 #endif 336