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 solve.h 26 * @ingroup INTERNALAPI 27 * @brief internal methods for main solving loop and node processing 28 * @author Tobias Achterberg 29 */ 30 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #ifndef __SCIP_SOLVE_H__ 34 #define __SCIP_SOLVE_H__ 35 36 37 #include "blockmemshell/memory.h" 38 #include "scip/def.h" 39 #include "scip/type_conflict.h" 40 #include "scip/type_conflictstore.h" 41 #include "scip/type_cutpool.h" 42 #include "scip/type_event.h" 43 #include "scip/type_lp.h" 44 #include "scip/type_mem.h" 45 #include "scip/type_message.h" 46 #include "scip/type_pricestore.h" 47 #include "scip/type_primal.h" 48 #include "scip/type_prob.h" 49 #include "scip/type_reopt.h" 50 #include "scip/type_retcode.h" 51 #include "scip/type_sepastore.h" 52 #include "scip/type_set.h" 53 #include "scip/type_stat.h" 54 #include "scip/type_tree.h" 55 56 #ifdef __cplusplus 57 extern "C" { 58 #endif 59 60 /** returns whether the solving process will be / was stopped before proving optimality; 61 * if the solving process was stopped, stores the reason as status in stat 62 */ 63 SCIP_EXPORT 64 SCIP_Bool SCIPsolveIsStopped( 65 SCIP_SET* set, /**< global SCIP settings */ 66 SCIP_STAT* stat, /**< dynamic problem statistics */ 67 SCIP_Bool checknodelimits /**< should the node limits be involved in the check? */ 68 ); 69 70 /** applies domain propagation on current node and flushes the conflict store afterwards */ 71 SCIP_RETCODE SCIPpropagateDomains( 72 BMS_BLKMEM* blkmem, /**< block memory buffers */ 73 SCIP_SET* set, /**< global SCIP settings */ 74 SCIP_STAT* stat, /**< dynamic problem statistics */ 75 SCIP_PROB* transprob, /**< transformed problem */ 76 SCIP_PROB* origprob, /**< original problem */ 77 SCIP_TREE* tree, /**< branch and bound tree */ 78 SCIP_REOPT* reopt, /**< reoptimization data structure */ 79 SCIP_LP* lp, /**< LP data */ 80 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 81 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 82 SCIP_CONFLICT* conflict, /**< conflict analysis data */ 83 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 84 int depth, /**< depth level to use for propagator frequency checks */ 85 int maxrounds, /**< maximal number of propagation rounds (-1: no limit, 0: parameter settings) */ 86 SCIP_PROPTIMING timingmask, /**< timing mask to decide which propagators are executed */ 87 SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */ 88 ); 89 90 /** puts all constraints with initial flag TRUE into the LP */ 91 SCIP_RETCODE SCIPinitConssLP( 92 BMS_BLKMEM* blkmem, /**< block memory buffers */ 93 SCIP_SET* set, /**< global SCIP settings */ 94 SCIP_SEPASTORE* sepastore, /**< separation storage */ 95 SCIP_CUTPOOL* cutpool, /**< global cutpool */ 96 SCIP_STAT* stat, /**< dynamic problem statistics */ 97 SCIP_PROB* transprob, /**< transformed problem */ 98 SCIP_PROB* origprob, /**< original problem */ 99 SCIP_TREE* tree, /**< branch and bound tree */ 100 SCIP_REOPT* reopt, /**< reoptimization data structure */ 101 SCIP_LP* lp, /**< LP data */ 102 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 103 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 104 SCIP_EVENTFILTER* eventfilter, /**< global event filter */ 105 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 106 SCIP_Bool root, /**< is this the initial root LP? */ 107 SCIP_Bool firstsubtreeinit, /**< is this the first call in the current subtree after jumping through the tree? */ 108 SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */ 109 ); 110 111 /** constructs the LP of the current node, but does not load the LP state and warmstart information */ 112 SCIP_RETCODE SCIPconstructCurrentLP( 113 BMS_BLKMEM* blkmem, /**< block memory buffers */ 114 SCIP_SET* set, /**< global SCIP settings */ 115 SCIP_STAT* stat, /**< dynamic problem statistics */ 116 SCIP_PROB* transprob, /**< transformed problem */ 117 SCIP_PROB* origprob, /**< original problem */ 118 SCIP_TREE* tree, /**< branch and bound tree */ 119 SCIP_REOPT* reopt, /**< reoptimization data structure */ 120 SCIP_LP* lp, /**< LP data */ 121 SCIP_PRICESTORE* pricestore, /**< pricing storage */ 122 SCIP_SEPASTORE* sepastore, /**< separation storage */ 123 SCIP_CUTPOOL* cutpool, /**< global cutpool */ 124 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 125 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 126 SCIP_EVENTFILTER* eventfilter, /**< global event filter */ 127 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 128 SCIP_Bool newinitconss, /**< do we have to add new initial constraints? */ 129 SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */ 130 ); 131 132 /** calls primal heuristics */ 133 SCIP_RETCODE SCIPprimalHeuristics( 134 SCIP_SET* set, /**< global SCIP settings */ 135 SCIP_STAT* stat, /**< dynamic problem statistics */ 136 SCIP_PROB* prob, /**< transformed problem after presolve */ 137 SCIP_PRIMAL* primal, /**< primal data */ 138 SCIP_TREE* tree, /**< branch and bound tree */ 139 SCIP_LP* lp, /**< LP data */ 140 SCIP_NODE* nextnode, /**< next node that will be processed, or NULL if no more nodes left 141 * (only needed when calling after node heuristics) */ 142 SCIP_HEURTIMING heurtiming, /**< current point in the node solving process */ 143 SCIP_Bool nodeinfeasible, /**< was the current node already detected to be infeasible? */ 144 SCIP_Bool* foundsol, /**< pointer to store whether a solution has been found */ 145 SCIP_Bool* unbounded /**< pointer to store whether an unbounded ray was found in the LP */ 146 ); 147 148 /** applies one round of separation on the given primal solution or on the LP solution */ 149 SCIP_RETCODE SCIPseparationRound( 150 BMS_BLKMEM* blkmem, /**< block memory buffers */ 151 SCIP_SET* set, /**< global SCIP settings */ 152 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 153 SCIP_STAT* stat, /**< dynamic problem statistics */ 154 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 155 SCIP_EVENTFILTER* eventfilter, /**< global event filter */ 156 SCIP_PROB* prob, /**< transformed problem after presolve */ 157 SCIP_PRIMAL* primal, /**< primal data */ 158 SCIP_TREE* tree, /**< branch and bound tree */ 159 SCIP_LP* lp, /**< LP data */ 160 SCIP_SEPASTORE* sepastore, /**< separation storage */ 161 SCIP_SOL* sol, /**< primal solution that should be separated, or NULL for LP solution */ 162 int actdepth, /**< current depth in the tree */ 163 SCIP_Bool allowlocal, /**< should the separator be asked to separate local cuts */ 164 SCIP_Bool onlydelayed, /**< should only delayed separators be called? */ 165 SCIP_Bool* delayed, /**< pointer to store whether a separator was delayed */ 166 SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */ 167 ); 168 169 /** solves the current LP completely with pricing in new variables */ 170 SCIP_RETCODE SCIPpriceLoop( 171 BMS_BLKMEM* blkmem, /**< block memory buffers */ 172 SCIP_SET* set, /**< global SCIP settings */ 173 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 174 SCIP_STAT* stat, /**< dynamic problem statistics */ 175 SCIP_PROB* transprob, /**< transformed problem */ 176 SCIP_PROB* origprob, /**< original problem */ 177 SCIP_PRIMAL* primal, /**< primal data */ 178 SCIP_TREE* tree, /**< branch and bound tree */ 179 SCIP_REOPT* reopt, /**< reoptimization data structure */ 180 SCIP_LP* lp, /**< LP data */ 181 SCIP_PRICESTORE* pricestore, /**< pricing storage */ 182 SCIP_SEPASTORE* sepastore, /**< separation storage */ 183 SCIP_CUTPOOL* cutpool, /**< global cutpool */ 184 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 185 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 186 SCIP_EVENTFILTER* eventfilter, /**< global event filter */ 187 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 188 SCIP_Bool pretendroot, /**< should the pricers be called as if we are at the root node? */ 189 SCIP_Bool displayinfo, /**< should info lines be displayed after each pricing round? */ 190 int maxpricerounds, /**< maximal number of pricing rounds (-1: no limit); 191 * a finite limit means that the LP might not be solved to optimality! */ 192 int* npricedcolvars, /**< pointer to store number of column variables after problem vars were priced */ 193 SCIP_Bool* mustsepa, /**< pointer to store TRUE if a separation round should follow */ 194 SCIP_Bool* lperror, /**< pointer to store whether an unresolved error in LP solving occured */ 195 SCIP_Bool* aborted /**< pointer to store whether the pricing was aborted and the lower bound must 196 * not be used */ 197 ); 198 199 /** main solving loop */ 200 SCIP_RETCODE SCIPsolveCIP( 201 BMS_BLKMEM* blkmem, /**< block memory buffers */ 202 SCIP_SET* set, /**< global SCIP settings */ 203 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 204 SCIP_STAT* stat, /**< dynamic problem statistics */ 205 SCIP_MEM* mem, /**< block memory pools */ 206 SCIP_PROB* origprob, /**< original problem */ 207 SCIP_PROB* transprob, /**< transformed problem after presolve */ 208 SCIP_PRIMAL* primal, /**< primal data */ 209 SCIP_TREE* tree, /**< branch and bound tree */ 210 SCIP_REOPT* reopt, /**< reoptimization data structure */ 211 SCIP_LP* lp, /**< LP data */ 212 SCIP_RELAXATION* relaxation, /**< global relaxation data */ 213 SCIP_PRICESTORE* pricestore, /**< pricing storage */ 214 SCIP_SEPASTORE* sepastore, /**< separation storage */ 215 SCIP_CUTPOOL* cutpool, /**< global cut pool */ 216 SCIP_CUTPOOL* delayedcutpool, /**< global delayed cut pool */ 217 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 218 SCIP_CONFLICT* conflict, /**< conflict analysis data */ 219 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */ 220 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */ 221 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 222 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */ 223 SCIP_Bool* restart /**< should solving process be started again with presolving? */ 224 ); 225 226 #ifdef __cplusplus 227 } 228 #endif 229 230 #endif 231