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