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 primal.h 17 * @ingroup INTERNALAPI 18 * @brief internal methods for collecting primal CIP solutions and primal informations 19 * @author Tobias Achterberg 20 */ 21 22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 23 24 #ifndef __SCIP_PRIMAL_H__ 25 #define __SCIP_PRIMAL_H__ 26 27 28 #include "scip/def.h" 29 #include "blockmemshell/memory.h" 30 #include "scip/type_retcode.h" 31 #include "scip/type_set.h" 32 #include "scip/type_event.h" 33 #include "scip/type_lp.h" 34 #include "scip/type_var.h" 35 #include "scip/type_prob.h" 36 #include "scip/type_sol.h" 37 #include "scip/type_primal.h" 38 #include "scip/type_tree.h" 39 #include "scip/type_reopt.h" 40 #include "scip/type_heur.h" 41 42 #include "scip/struct_primal.h" 43 44 #ifdef __cplusplus 45 extern "C" { 46 #endif 47 48 /** creates primal data */ 49 SCIP_RETCODE SCIPprimalCreate( 50 SCIP_PRIMAL** primal /**< pointer to primal data */ 51 ); 52 53 /** frees primal data */ 54 SCIP_RETCODE SCIPprimalFree( 55 SCIP_PRIMAL** primal, /**< pointer to primal data */ 56 BMS_BLKMEM* blkmem /**< block memory */ 57 ); 58 59 /** clears primal data */ 60 SCIP_RETCODE SCIPprimalClear( 61 SCIP_PRIMAL** primal, /**< pointer to primal data */ 62 BMS_BLKMEM* blkmem /**< block memory */ 63 ); 64 65 /** sets the cutoff bound in primal data and in LP solver */ 66 SCIP_RETCODE SCIPprimalSetCutoffbound( 67 SCIP_PRIMAL* primal, /**< primal data */ 68 BMS_BLKMEM* blkmem, /**< block memory */ 69 SCIP_SET* set, /**< global SCIP settings */ 70 SCIP_STAT* stat, /**< problem statistics data */ 71 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 72 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 73 SCIP_PROB* transprob, /**< tranformed problem data */ 74 SCIP_PROB* origprob, /**< original problem data */ 75 SCIP_TREE* tree, /**< branch and bound tree */ 76 SCIP_REOPT* reopt, /**< reoptimization data structure */ 77 SCIP_LP* lp, /**< current LP data */ 78 SCIP_Real cutoffbound, /**< new cutoff bound */ 79 SCIP_Bool useforobjlimit /**< should the cutoff bound be used to update the objective limit, if 80 * better? */ 81 ); 82 83 /** sets upper bound in primal data and in LP solver */ 84 SCIP_RETCODE SCIPprimalSetUpperbound( 85 SCIP_PRIMAL* primal, /**< primal data */ 86 BMS_BLKMEM* blkmem, /**< block memory */ 87 SCIP_SET* set, /**< global SCIP settings */ 88 SCIP_STAT* stat, /**< problem statistics data */ 89 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 90 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 91 SCIP_PROB* prob, /**< transformed problem after presolve */ 92 SCIP_TREE* tree, /**< branch and bound tree */ 93 SCIP_REOPT* reopt, /**< reoptimization data structure */ 94 SCIP_LP* lp, /**< current LP data */ 95 SCIP_Real upperbound /**< new upper bound */ 96 ); 97 98 /** updates upper bound and cutoff bound in primal data after a tightening of the problem's objective limit */ 99 SCIP_RETCODE SCIPprimalUpdateObjlimit( 100 SCIP_PRIMAL* primal, /**< primal data */ 101 BMS_BLKMEM* blkmem, /**< block memory */ 102 SCIP_SET* set, /**< global SCIP settings */ 103 SCIP_STAT* stat, /**< problem statistics data */ 104 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 105 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 106 SCIP_PROB* transprob, /**< tranformed problem data */ 107 SCIP_PROB* origprob, /**< original problem data */ 108 SCIP_TREE* tree, /**< branch and bound tree */ 109 SCIP_REOPT* reopt, /**< reoptimization data structure */ 110 SCIP_LP* lp /**< current LP data */ 111 ); 112 113 /** recalculates upper bound and cutoff bound in primal data after a change of the problem's objective offset */ 114 SCIP_RETCODE SCIPprimalUpdateObjoffset( 115 SCIP_PRIMAL* primal, /**< primal data */ 116 BMS_BLKMEM* blkmem, /**< block memory */ 117 SCIP_SET* set, /**< global SCIP settings */ 118 SCIP_STAT* stat, /**< problem statistics data */ 119 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 120 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 121 SCIP_PROB* transprob, /**< tranformed problem data */ 122 SCIP_PROB* origprob, /**< original problem data */ 123 SCIP_TREE* tree, /**< branch and bound tree */ 124 SCIP_REOPT* reopt, /**< reoptimization data structure */ 125 SCIP_LP* lp /**< current LP data */ 126 ); 127 128 /** adds additional objective offset in origanal space to all existing solution (in original space) */ 129 void SCIPprimalAddOrigObjoffset( 130 SCIP_PRIMAL* primal, /**< primal data */ 131 SCIP_SET* set, /**< global SCIP settings */ 132 SCIP_Real addval /**< additional objective offset in original space */ 133 ); 134 135 /** returns whether the current primal bound is justified with a feasible primal solution; if not, the primal bound 136 * was set from the user as objective limit 137 */ 138 SCIP_Bool SCIPprimalUpperboundIsSol( 139 SCIP_PRIMAL* primal, /**< primal data */ 140 SCIP_SET* set, /**< global SCIP settings */ 141 SCIP_PROB* transprob, /**< tranformed problem data */ 142 SCIP_PROB* origprob /**< original problem data */ 143 ); 144 145 /** returns the primal ray thats proves unboundedness */ 146 SCIP_SOL* SCIPprimalGetRay( 147 SCIP_PRIMAL* primal /**< primal data */ 148 ); 149 150 /** update the primal ray thats proves unboundedness */ 151 SCIP_RETCODE SCIPprimalUpdateRay( 152 SCIP_PRIMAL* primal, /**< primal data */ 153 SCIP_SET* set, /**< global SCIP settings */ 154 SCIP_STAT* stat, /**< dynamic SCIP statistics */ 155 SCIP_SOL* primalray, /**< the new primal ray */ 156 BMS_BLKMEM* blkmem /**< block memory */ 157 ); 158 159 /** adds primal solution to solution storage by copying it */ 160 SCIP_RETCODE SCIPprimalAddSol( 161 SCIP_PRIMAL* primal, /**< primal data */ 162 BMS_BLKMEM* blkmem, /**< block memory */ 163 SCIP_SET* set, /**< global SCIP settings */ 164 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 165 SCIP_STAT* stat, /**< problem statistics data */ 166 SCIP_PROB* origprob, /**< original problem */ 167 SCIP_PROB* transprob, /**< transformed problem after presolve */ 168 SCIP_TREE* tree, /**< branch and bound tree */ 169 SCIP_REOPT* reopt, /**< reoptimization data structure */ 170 SCIP_LP* lp, /**< current LP data */ 171 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 172 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 173 SCIP_SOL* sol, /**< primal CIP solution */ 174 SCIP_Bool* stored /**< stores whether given solution was good enough to keep */ 175 ); 176 177 /** adds primal solution to solution storage, frees the solution afterwards */ 178 SCIP_RETCODE SCIPprimalAddSolFree( 179 SCIP_PRIMAL* primal, /**< primal data */ 180 BMS_BLKMEM* blkmem, /**< block memory */ 181 SCIP_SET* set, /**< global SCIP settings */ 182 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 183 SCIP_STAT* stat, /**< problem statistics data */ 184 SCIP_PROB* origprob, /**< original problem */ 185 SCIP_PROB* transprob, /**< transformed problem after presolve */ 186 SCIP_TREE* tree, /**< branch and bound tree */ 187 SCIP_REOPT* reopt, /**< reoptimization data structure */ 188 SCIP_LP* lp, /**< current LP data */ 189 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 190 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 191 SCIP_SOL** sol, /**< pointer to primal CIP solution; is cleared in function call */ 192 SCIP_Bool* stored /**< stores whether given solution was good enough to keep */ 193 ); 194 195 /** adds primal solution to solution candidate storage of original problem space */ 196 SCIP_RETCODE SCIPprimalAddOrigSol( 197 SCIP_PRIMAL* primal, /**< primal data */ 198 BMS_BLKMEM* blkmem, /**< block memory */ 199 SCIP_SET* set, /**< global SCIP settings */ 200 SCIP_STAT* stat, /**< problem statistics data */ 201 SCIP_PROB* prob, /**< original problem data */ 202 SCIP_SOL* sol, /**< primal CIP solution; is cleared in function call */ 203 SCIP_Bool* stored /**< stores whether given solution was good enough to keep */ 204 ); 205 206 /** adds primal solution to solution candidate storage of original problem space, frees the solution afterwards */ 207 SCIP_RETCODE SCIPprimalAddOrigSolFree( 208 SCIP_PRIMAL* primal, /**< primal data */ 209 BMS_BLKMEM* blkmem, /**< block memory */ 210 SCIP_SET* set, /**< global SCIP settings */ 211 SCIP_STAT* stat, /**< problem statistics data */ 212 SCIP_PROB* prob, /**< original problem data */ 213 SCIP_SOL** sol, /**< pointer to primal CIP solution; is cleared in function call */ 214 SCIP_Bool* stored /**< stores whether given solution was good enough to keep */ 215 ); 216 217 /** adds current LP/pseudo solution to solution storage */ 218 SCIP_RETCODE SCIPprimalAddCurrentSol( 219 SCIP_PRIMAL* primal, /**< primal data */ 220 BMS_BLKMEM* blkmem, /**< block memory */ 221 SCIP_SET* set, /**< global SCIP settings */ 222 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 223 SCIP_STAT* stat, /**< problem statistics data */ 224 SCIP_PROB* origprob, /**< original problem */ 225 SCIP_PROB* transprob, /**< transformed problem after presolve */ 226 SCIP_TREE* tree, /**< branch and bound tree */ 227 SCIP_REOPT* reopt, /**< reoptimization data structure */ 228 SCIP_LP* lp, /**< current LP data */ 229 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 230 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 231 SCIP_HEUR* heur, /**< heuristic that found the solution (or NULL if it's from the tree) */ 232 SCIP_Bool* stored /**< stores whether given solution was good enough to keep */ 233 ); 234 235 /** checks primal solution; if feasible, adds it to storage by copying it */ 236 SCIP_RETCODE SCIPprimalTrySol( 237 SCIP_PRIMAL* primal, /**< primal data */ 238 BMS_BLKMEM* blkmem, /**< block memory */ 239 SCIP_SET* set, /**< global SCIP settings */ 240 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 241 SCIP_STAT* stat, /**< problem statistics data */ 242 SCIP_PROB* origprob, /**< original problem */ 243 SCIP_PROB* transprob, /**< transformed problem after presolve */ 244 SCIP_TREE* tree, /**< branch and bound tree */ 245 SCIP_REOPT* reopt, /**< reoptimization data structure */ 246 SCIP_LP* lp, /**< current LP data */ 247 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 248 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 249 SCIP_SOL* sol, /**< primal CIP solution */ 250 SCIP_Bool printreason, /**< Should all reasons of violations be printed? */ 251 SCIP_Bool completely, /**< Should all violations be checked? */ 252 SCIP_Bool checkbounds, /**< Should the bounds of the variables be checked? */ 253 SCIP_Bool checkintegrality, /**< Has integrality to be checked? */ 254 SCIP_Bool checklprows, /**< Do constraints represented by rows in the current LP have to be checked? */ 255 SCIP_Bool* stored /**< stores whether given solution was feasible and good enough to keep */ 256 ); 257 258 /** checks primal solution; if feasible, adds it to storage; solution is freed afterwards */ 259 SCIP_RETCODE SCIPprimalTrySolFree( 260 SCIP_PRIMAL* primal, /**< primal data */ 261 BMS_BLKMEM* blkmem, /**< block memory */ 262 SCIP_SET* set, /**< global SCIP settings */ 263 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 264 SCIP_STAT* stat, /**< problem statistics data */ 265 SCIP_PROB* origprob, /**< original problem */ 266 SCIP_PROB* transprob, /**< transformed problem after presolve */ 267 SCIP_TREE* tree, /**< branch and bound tree */ 268 SCIP_REOPT* reopt, /**< reoptimization data structure */ 269 SCIP_LP* lp, /**< current LP data */ 270 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 271 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 272 SCIP_SOL** sol, /**< pointer to primal CIP solution; is cleared in function call */ 273 SCIP_Bool printreason, /**< Should all reasons of violations be printed? */ 274 SCIP_Bool completely, /**< Should all violations be checked? */ 275 SCIP_Bool checkbounds, /**< Should the bounds of the variables be checked? */ 276 SCIP_Bool checkintegrality, /**< Has integrality to be checked? */ 277 SCIP_Bool checklprows, /**< Do constraints represented by rows in the current LP have to be checked? */ 278 SCIP_Bool* stored /**< stores whether solution was feasible and good enough to keep */ 279 ); 280 281 /** checks current LP/pseudo solution; if feasible, adds it to storage */ 282 SCIP_RETCODE SCIPprimalTryCurrentSol( 283 SCIP_PRIMAL* primal, /**< primal data */ 284 BMS_BLKMEM* blkmem, /**< block memory */ 285 SCIP_SET* set, /**< global SCIP settings */ 286 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 287 SCIP_STAT* stat, /**< problem statistics data */ 288 SCIP_PROB* origprob, /**< original problem */ 289 SCIP_PROB* transprob, /**< transformed problem after presolve */ 290 SCIP_TREE* tree, /**< branch and bound tree */ 291 SCIP_REOPT* reopt, /**< reoptimization data structure */ 292 SCIP_LP* lp, /**< current LP data */ 293 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 294 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 295 SCIP_HEUR* heur, /**< heuristic that found the solution (or NULL if it's from the tree) */ 296 SCIP_Bool printreason, /**< Should all reasons of violations be printed? */ 297 SCIP_Bool completely, /**< Should all violations be checked? */ 298 SCIP_Bool checkintegrality, /**< Has integrality to be checked? */ 299 SCIP_Bool checklprows, /**< Do constraints represented by rows in the current LP have to be checked? */ 300 SCIP_Bool* stored /**< stores whether given solution was good enough to keep */ 301 ); 302 303 /** inserts solution into the global array of all existing primal solutions */ 304 SCIP_RETCODE SCIPprimalSolCreated( 305 SCIP_PRIMAL* primal, /**< primal data */ 306 SCIP_SET* set, /**< global SCIP settings */ 307 SCIP_SOL* sol /**< primal CIP solution */ 308 ); 309 310 /** removes solution from the global array of all existing primal solutions */ 311 void SCIPprimalSolFreed( 312 SCIP_PRIMAL* primal, /**< primal data */ 313 SCIP_SOL* sol /**< primal CIP solution */ 314 ); 315 316 /** updates all existing primal solutions after a change in a variable's objective value */ 317 void SCIPprimalUpdateVarObj( 318 SCIP_PRIMAL* primal, /**< primal data */ 319 SCIP_VAR* var, /**< problem variable */ 320 SCIP_Real oldobj, /**< old objective value */ 321 SCIP_Real newobj /**< new objective value */ 322 ); 323 324 /** retransforms all existing solutions to original problem space 325 * 326 * @note as a side effect, the objective value of the solutions can change (numerical errors) 327 * so we update the objective cutoff value and upper bound accordingly 328 */ 329 SCIP_RETCODE SCIPprimalRetransformSolutions( 330 SCIP_PRIMAL* primal, /**< primal data */ 331 BMS_BLKMEM* blkmem, /**< block memory */ 332 SCIP_SET* set, /**< global SCIP settings */ 333 SCIP_STAT* stat, /**< problem statistics data */ 334 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 335 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 336 SCIP_PROB* origprob, /**< original problem */ 337 SCIP_PROB* transprob, /**< transformed problem */ 338 SCIP_TREE* tree, /**< branch and bound tree */ 339 SCIP_REOPT* reopt, /**< reoptimization data structure */ 340 SCIP_LP* lp /**< current LP data */ 341 ); 342 343 /** tries to transform original solution to the transformed problem space */ 344 SCIP_RETCODE SCIPprimalTransformSol( 345 SCIP_PRIMAL* primal, /**< primal data */ 346 SCIP_SOL* sol, /**< primal solution */ 347 BMS_BLKMEM* blkmem, /**< block memory */ 348 SCIP_SET* set, /**< global SCIP settings */ 349 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 350 SCIP_STAT* stat, /**< problem statistics data */ 351 SCIP_PROB* origprob, /**< original problem */ 352 SCIP_PROB* transprob, /**< transformed problem after presolve */ 353 SCIP_TREE* tree, /**< branch and bound tree */ 354 SCIP_REOPT* reopt, /**< reoptimization data structure */ 355 SCIP_LP* lp, /**< current LP data */ 356 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 357 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 358 SCIP_Real* solvals, /**< array for internal use to store solution values, or NULL; 359 * if the method is called multiple times in a row, an array with size >= 360 * number of active variables should be given for performance reasons */ 361 SCIP_Bool* solvalset, /**< array for internal use to store which solution values were set, or NULL; 362 * if the method is called multiple times in a row, an array with size >= 363 * number of active variables should be given for performance reasons */ 364 int solvalssize, /**< size of solvals and solvalset arrays, should be >= number of active 365 * variables */ 366 SCIP_Bool* added /**< pointer to store whether the solution was added */ 367 ); 368 369 /** is the updating of violations enabled for this problem? */ 370 SCIP_Bool SCIPprimalUpdateViolations( 371 SCIP_PRIMAL* primal /**< problem data */ 372 ); 373 374 /** set whether the updating of violations is turned on */ 375 void SCIPprimalSetUpdateViolations( 376 SCIP_PRIMAL* primal, /**< problem data */ 377 SCIP_Bool updateviolations /**< TRUE to enable violation updates, FALSE otherwise */ 378 ); 379 380 #ifdef __cplusplus 381 } 382 #endif 383 384 #endif 385