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