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 type_benders.h 26 * @ingroup TYPEDEFINITIONS 27 * @brief type definitions for Benders' decomposition methods 28 * @author Stephen J. Maher 29 */ 30 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #ifndef __SCIP_TYPE_BENDERS_H__ 34 #define __SCIP_TYPE_BENDERS_H__ 35 36 #include "scip/def.h" 37 #include "scip/type_retcode.h" 38 #include "scip/type_scip.h" 39 40 #ifdef __cplusplus 41 extern "C" { 42 #endif 43 44 enum SCIP_BendersEnfoType 45 { 46 SCIP_BENDERSENFOTYPE_LP = 1, /**< the Benders' subproblems are solved during the enforcement of an LP solution */ 47 SCIP_BENDERSENFOTYPE_RELAX = 2, /**< the Benders' subproblems are solved during the enforcement of a relaxation solution */ 48 SCIP_BENDERSENFOTYPE_PSEUDO = 3, /**< the Benders' subproblems are solved during the enforcement of a pseudo solution */ 49 SCIP_BENDERSENFOTYPE_CHECK = 4 /**< the Benders' subproblems are solved during the checking of a solution for feasibility */ 50 }; 51 typedef enum SCIP_BendersEnfoType SCIP_BENDERSENFOTYPE; /**< indicates the callback in cons_benders and cons_benderslp that triggered the subproblem solve */ 52 53 enum SCIP_BendersSolveLoop 54 { 55 SCIP_BENDERSSOLVELOOP_CONVEX = 0, /**< the relaxation is solved in this iteration of the loop */ 56 SCIP_BENDERSSOLVELOOP_CIP = 1, /**< the CIP is solved in this iteration of the loop */ 57 SCIP_BENDERSSOLVELOOP_USERCONVEX = 2, /**< the user defined solve function is called */ 58 SCIP_BENDERSSOLVELOOP_USERCIP = 3 /**< the user defined solve function is called */ 59 }; 60 typedef enum SCIP_BendersSolveLoop SCIP_BENDERSSOLVELOOP; /**< identifies the type of problem solved in each solve loop */ 61 62 enum SCIP_BendersSubStatus 63 { 64 SCIP_BENDERSSUBSTATUS_UNKNOWN = 0, /**< the subsystem status is unknown */ 65 SCIP_BENDERSSUBSTATUS_OPTIMAL = 1, /**< the subsystem is solved to be optimal */ 66 SCIP_BENDERSSUBSTATUS_AUXVIOL = 2, /**< the subproblem is optimal, but the auxiliary variable is violated */ 67 SCIP_BENDERSSUBSTATUS_INFEAS = 3 /**< the subproblem is solved to be infeasible */ 68 }; 69 typedef enum SCIP_BendersSubStatus SCIP_BENDERSSUBSTATUS; 70 71 enum SCIP_BendersSubType 72 { 73 SCIP_BENDERSSUBTYPE_CONVEXCONT = 0, /**< the subproblem has convex constraints and continuous variables */ 74 SCIP_BENDERSSUBTYPE_CONVEXDIS = 1, /**< the subproblem has convex constraints and discrete variables */ 75 SCIP_BENDERSSUBTYPE_NONCONVEXCONT = 2, /**< the subproblem has non-convex constraints and continuous variables */ 76 SCIP_BENDERSSUBTYPE_NONCONVEXDIS = 3, /**< the subproblem has non-convex constraints and discrete variables */ 77 SCIP_BENDERSSUBTYPE_UNKNOWN = 4, /**< the default type before the type is known */ 78 }; 79 typedef enum SCIP_BendersSubType SCIP_BENDERSSUBTYPE; 80 81 typedef struct SCIP_Benders SCIP_BENDERS; /**< Benders' decomposition data */ 82 typedef struct SCIP_BendersData SCIP_BENDERSDATA; /**< locally defined Benders' decomposition data */ 83 typedef struct SCIP_SubproblemSolveStat SCIP_SUBPROBLEMSOLVESTAT; /**< the solving statistics of the subproblems */ 84 85 86 /** copy method for Benders' decomposition plugins (called when SCIP copies plugins). If there is an active Benders' 87 * decomposition, all copies are not valid. As such, there is no valid parameter that is passed to the callback 88 * function 89 * 90 * input: 91 * - scip : SCIP main data structure 92 * - benders : the Benders' decomposition itself 93 * - threadsafe : must the Benders' decomposition copy be thread safe 94 */ 95 #define SCIP_DECL_BENDERSCOPY(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders, SCIP_Bool threadsafe) 96 97 /** destructor of Benders' decomposition to free user data (called when SCIP is exiting) 98 * 99 * input: 100 * - scip : SCIP main data structure 101 * - benders : the Benders' decomposition itself 102 */ 103 #define SCIP_DECL_BENDERSFREE(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders) 104 105 /** initialization method of Benders' decomposition (called after problem was transformed and the Benders' decomposition 106 * is active) 107 * 108 * input: 109 * - scip : SCIP main data structure 110 * - benders : the Benders' decomposition itself 111 */ 112 #define SCIP_DECL_BENDERSINIT(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders) 113 114 /** deinitialization method of Benders' decomposition (called before transformed problem is freed and the Benders' 115 * decomposition is active) 116 * 117 * input: 118 * - scip : SCIP main data structure 119 * - benders : the Benders' decomposition itself 120 */ 121 #define SCIP_DECL_BENDERSEXIT(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders) 122 123 /** presolving initialization method of the Benders' decomposition (called when presolving is about to begin) 124 * 125 * This function is called immediately after the auxiliary variables are created in the master problem. The callback 126 * provides the user an opportunity to add variable data to the auxiliary variables. 127 * 128 * input: 129 * - scip : SCIP main data structure 130 * - benders : the Benders' decomposition itself 131 */ 132 #define SCIP_DECL_BENDERSINITPRE(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders) 133 134 /** presolving deinitialization method of the Benders' decomposition (called after presolving has been finished) 135 * 136 * input: 137 * - scip : SCIP main data structure 138 * - benders : the Benders' decomposition itself 139 */ 140 #define SCIP_DECL_BENDERSEXITPRE(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders) 141 142 /** solving process initialization method of Benders' decomposition (called when branch and bound process is about to begin) 143 * 144 * This method is called when the presolving was finished and the branch and bound process is about to begin. 145 * The Benders' decomposition may use this call to initialize its branch and bound specific data. 146 * 147 * input: 148 * - scip : SCIP main data structure 149 * - benders : the Benders' decomposition itself 150 */ 151 #define SCIP_DECL_BENDERSINITSOL(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders) 152 153 /** solving process deinitialization method of Benders' decomposition (called before branch and bound process data is freed) 154 * 155 * This method is called before the branch and bound process is freed. 156 * The Benders' decomposition should use this call to clean up its branch and bound data. 157 * 158 * input: 159 * - scip : SCIP main data structure 160 * - benders : the Benders' decomposition itself 161 */ 162 #define SCIP_DECL_BENDERSEXITSOL(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders) 163 164 /** the method for creating the Benders' decomposition subproblem. This method is called during the initialisation stage 165 * (after the master problem was transformed). 166 * 167 * @note When the create subproblem callback is invoked, the mapping between the master problem and subproblem 168 * variables must be available. The create subproblem callback is invoked immediately after BENDERSINIT. So, it is 169 * possible to construct the variable mapping within the BENDERSINIT callback. 170 * 171 * This method must register the SCIP instance for the subproblem with the Benders' decomposition core by calling 172 * SCIPaddBendersSubproblem. Typically, the user must create the SCIP instances for the subproblems. These can be 173 * created within a reader or probdata and then registered with the Benders' decomposition core during the call of this 174 * callback. If there are any settings required for solving the subproblems, then they should be set here. However, 175 * some settings will be overridden by the standard solving method included in the Benders' decomposition framework. 176 * If a special solving method is desired, the user can implement the bendersSolvesubXyz callback. In this latter case, 177 * it is possible to provide a NULL pointer to SCIPaddBendersSubproblem. This will ensure that no internal solving 178 * methods available within the Benders' decomposition core are invoked during the solving process. 179 * 180 * If the user defines a subproblem solving method, then in BENDERSCREATESUB, the user must explicitly specify the 181 * subproblem type. This is necessary because the dual solutions from convex problems can be used to generate cuts. 182 * The classical Benders' optimality and feasibility cuts require that the subproblems are convex. The subproblem type 183 * is specified by calling SCIPbendersSetSubproblemType. The available subproblem types are defined in 184 * SCIP_BENDERSSUBTYPE. 185 * 186 * If the user does NOT implement a subproblem solving method, then the convexity of the problem is determined 187 * internally. 188 * 189 * input: 190 * - scip : SCIP main data structure 191 * - benders : the Benders' decomposition data structure 192 * - probnumber : the subproblem problem number 193 */ 194 #define SCIP_DECL_BENDERSCREATESUB(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders, int probnumber) 195 196 /** called before the subproblem solving loop for Benders' decomposition. The pre subproblem solve function gives the 197 * user an oppportunity to perform any global set up for the Benders' decomposition. 198 * 199 * input: 200 * - scip : SCIP main data structure 201 * - benders : the Benders' decomposition data structure 202 * - sol : the solution that will be checked in the subproblem. Can be NULL. 203 * - type : the enforcement type that called the Benders' decomposition solve. 204 * - checkint : should the integer subproblems be checked. 205 * - infeasible : flag to return whether the master problem in infeasible with respect to the added cuts 206 * - auxviol : set to TRUE only if the solution is feasible but the aux vars are violated 207 * - skipsolve : flag to return whether the current subproblem solving loop should be skipped 208 * - result : a result to be returned to the Benders' constraint handler if the solve is skipped. If the 209 * solve is not skipped, then the returned result is ignored. 210 * 211 * possible return values for *result (if more than one applies, the first in the list should be used): 212 * - SCIP_DIDNOTRUN : the subproblem was not solved in this iteration. Other decompositions will be checked. 213 * - SCIP_CONSADDED : a constraint has been added to the master problem. No other decompositions will be checked. 214 * - SCIP_SEPARATED : a cut has been added to the master problem. No other decompositions will be checked. 215 * - SCIP_FEASIBLE : feasibility of the solution is reported to SCIP. Other decompositions will be checked. 216 * - SCIP_INFEASIBLE : infeasibility of the solution is reported to SCIP. No other decompositions will be checked. 217 */ 218 #define SCIP_DECL_BENDERSPRESUBSOLVE(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders, SCIP_SOL* sol,\ 219 SCIP_BENDERSENFOTYPE type, SCIP_Bool checkint, SCIP_Bool* infeasible, SCIP_Bool* auxviol, SCIP_Bool* skipsolve,\ 220 SCIP_RESULT* result) 221 222 /** the solving method for a convex Benders' decomposition subproblem. This call back is provided to solve problems 223 * for which the dual soluitons are used to generate Benders' decomposition cuts. In the classical Benders' 224 * decomposition implementation, this would be an LP. However, it can be any convex problem where the dual solutions 225 * are given by a single vector of reals. 226 * 227 * In the Benders' decomposition subproblem solving process, there are two solving loops. The first is where the convex 228 * subproblems, and the convex relaxations of subproblems, are solved. If no cuts are generated after this solving 229 * loop, then the second loop solves subproblems defined as CIPs. This callback is executed during the FIRST solving 230 * loop only. 231 * 232 * In the classical Benders' decomposition implementation, if the subproblems are all LPs the only the 233 * BENDERSSOLVESUBCONVEX need to be implemented. If the subproblems are MIPs, then it is useful to only implement a 234 * single SCIP instance for the subproblem and then change the variable types of the appropriate variables to 235 * CONTINUOUS for the CONVEX subproblem solve and to INTEGER for the CIP subproblem solve. 236 * 237 * The solving methods are separated so that they can be called in parallel. 238 * 239 * NOTE: The solving methods must be thread safe. 240 * 241 * This method is called from within the execution method. 242 * 243 * input: 244 * - scip : SCIP main data structure 245 * - benders : the Benders' decomposition data structure 246 * - sol : the solution that will be checked in the subproblem. Can be NULL. 247 * - probnumber : the subproblem problem number 248 * - onlyconvexcheck : flag to indicate that only the convex relaxations will be checked in this solving loop. This is 249 * a feature of the Large Neighbourhood Benders' Search 250 * - objective : variable to return the objective function value of the subproblem 251 * - result : the result from solving the subproblem 252 * 253 * possible return values for *result (if more than one applies, the first in the list should be used): 254 * - SCIP_DIDNOTRUN : the subproblem was not solved in this iteration 255 * - SCIP_FEASIBLE : the subproblem is solved and is feasible 256 * - SCIP_INFEASIBLE : the subproblem is solved and is infeasible 257 * - SCIP_UNBOUNDED : the subproblem is solved and is unbounded 258 */ 259 #define SCIP_DECL_BENDERSSOLVESUBCONVEX(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders, SCIP_SOL* sol,\ 260 int probnumber, SCIP_Bool onlyconvexcheck, SCIP_Real* objective, SCIP_RESULT* result) 261 262 /** the solving method for a Benders' decomposition subproblem as a CIP. This call back is provided to solve problems 263 * for which the dual solutions are not well defined. In this case, the cuts are typically generated from the primal 264 * solution to the CIP. In the classical Benders' decomposition implementation, this would be a MIP. However, it can 265 * be any CIP. 266 * 267 * In the Benders' decomposition subproblem solving process, there are two solving loops. The first is where the convex 268 * subproblems, and the convex relaxations of subproblems, are solved. If no cuts are generated after this solving 269 * loop, then the second loop solves subproblems defined as CIPs. This callback is executed during the SECOND solving 270 * loop only. 271 * 272 * The solving methods are separated so that they can be called in parallel. 273 * 274 * NOTE: The solving methods must be thread safe. 275 * 276 * This method is called from within the execution method. 277 * 278 * input: 279 * - scip : SCIP main data structure 280 * - benders : the Benders' decomposition data structure 281 * - sol : the solution that will be checked in the subproblem. Can be NULL. 282 * - probnumber : the subproblem problem number 283 * - objective : variable to return the objective function value of the subproblem 284 * - result : the result from solving the subproblem 285 * 286 * possible return values for *result (if more than one applies, the first in the list should be used): 287 * - SCIP_DIDNOTRUN : the subproblem was not solved in this iteration 288 * - SCIP_FEASIBLE : the subproblem is solved and is feasible 289 * - SCIP_INFEASIBLE : the subproblem is solved and is infeasible 290 * - SCIP_UNBOUNDED : the subproblem is solved and is unbounded 291 */ 292 #define SCIP_DECL_BENDERSSOLVESUB(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders, SCIP_SOL* sol, int probnumber,\ 293 SCIP_Real* objective, SCIP_RESULT* result) 294 295 /** the post-solve method for Benders' decomposition. The post-solve method is called after the subproblems have 296 * been solved but before they have been freed. After the solving of the Benders' decomposition subproblems, the 297 * subproblem solving data is freed in the SCIP_DECL_BENDERSFREESUB callback. However, it is not necessary to implement 298 * SCIP_DECL_BENDERSFREESUB. 299 * 300 * If SCIP_DECL_BENDERSFREESUB is not implemented, then the Benders' decomposition framework will perform a default 301 * freeing of the subproblems. If a subproblem is an LP, then they will be in probing mode for the subproblem 302 * solve. So the freeing process involves ending the probing mode. If the subproblem is a MIP, then the subproblem is 303 * solved by calling SCIPsolve. As such, the transformed problem must be freed after each subproblem solve. 304 * 305 * This callback provides the opportunity for the user to clean up any data structures that should not exist beyond the current 306 * iteration. 307 * The user has full access to the master and subproblems in this callback. So it is possible to construct solution for 308 * the master problem in the method. 309 * Additionally, if there are any subproblems that are infeasibility and this can not be resolved, then the it is 310 * possible to merge these subproblems into the master problem. The subproblem indices are given in the mergecands 311 * array. The merging can be perform by a user defined function or by calling SCIPmergeBendersSubproblemIntoMaster. If a 312 * subproblem was merged into the master problem, then the merged flag must be set to TRUE. 313 * 314 * input: 315 * - scip : SCIP main data structure 316 * - benders : the Benders' decomposition data structure 317 * - sol : the solution that was checked by solving the subproblems. Can be NULL. 318 * - type : the enforcement type that called the Benders' decomposition solve. 319 * - mergecands : the subproblems that are candidates for merging into the master problem, the first 320 * npriomergecands are the priority candidates (they should be merged). The remaining 321 * (nmergecands - npriomergecands) are subproblems that could be merged if desired. 322 * - npriomergecands : the number of priority merge candidates. 323 * - nmergecands : the total number of subproblems that are candidates for merging into the master problem 324 * - checkint : should the integer subproblems be checked. 325 * - infeasible : indicates whether at least one subproblem is infeasible 326 * - merged : flag to indicate whether a subproblem was merged into the master problem. 327 */ 328 #define SCIP_DECL_BENDERSPOSTSOLVE(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders, SCIP_SOL* sol,\ 329 SCIP_BENDERSENFOTYPE type, int* mergecands, int npriomergecands, int nmergecands, SCIP_Bool checkint,\ 330 SCIP_Bool infeasible, SCIP_Bool* merged) 331 332 /** frees the subproblem so that it can be resolved in the next iteration. As stated above, it is not necessary to 333 * implement this callback. If the callback is implemented, the subproblems should be freed by calling 334 * SCIPfreeTransform(). However, if the subproblems are LPs, then it could be more efficient to put the subproblem 335 * into probing mode prior to solving and then exiting the probing mode during the callback. To put the subproblem into 336 * probing mode, the subproblem must be in SCIP_STAGE_SOLVING. This can be achieved by using eventhandlers. 337 * 338 * If SCIP_DECL_BENDERSFREESUB is not implemented, then the Benders' decomposition framework will perform a default 339 * freeing of the subproblems. If a subproblem is an LP, then they will be in probing mode for the subproblem 340 * solve. So the freeing process involves ending the probing mode. If the subproblem is a MIP, then the subproblem is 341 * solved by calling SCIPsolve. As such, the transformed problem must be freed after each subproblem solve. 342 * 343 * NOTE: The freeing methods must be thread safe. 344 * 345 * input: 346 * - scip : SCIP main data structure 347 * - benders : the Benders' decomposition data structure 348 * - probnumber : the subproblem problem number 349 */ 350 #define SCIP_DECL_BENDERSFREESUB(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders, int probnumber) 351 352 /** the variable mapping from the subproblem to the master problem. It is neccessary to have a mapping between every 353 * master problem variable and its counterpart in the subproblem. This mapping must go both ways: from master to sub 354 * and sub to master. 355 * 356 * This method is called when generating the cuts. The cuts are generated by using the solution to the subproblem to 357 * eliminate a solution to the master problem. 358 * 359 * input: 360 * - scip : SCIP main data structure 361 * - benders : the Benders' decomposition structure 362 * - var : the variable for which the corresponding variable in the master or subproblem is required 363 * - mappedvar : pointer to store the variable that is mapped to var 364 * - probnumber : the number of the subproblem that the desired variable belongs to, -1 for the master problem 365 */ 366 #define SCIP_DECL_BENDERSGETVAR(x) SCIP_RETCODE x (SCIP* scip, SCIP_BENDERS* benders, SCIP_VAR* var,\ 367 SCIP_VAR** mappedvar, int probnumber) 368 369 #ifdef __cplusplus 370 } 371 #endif 372 373 #endif 374