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 benders.h 26 * @ingroup INTERNALAPI 27 * @brief internal methods for Benders' decomposition 28 * @author Stephen J. Maher 29 */ 30 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #ifndef __SCIP_BENDERS_H__ 34 #define __SCIP_BENDERS_H__ 35 36 #include "blockmemshell/memory.h" 37 #include "scip/def.h" 38 #include "scip/type_benders.h" 39 #include "scip/type_benderscut.h" 40 #include "scip/type_dcmp.h" 41 #include "scip/type_message.h" 42 #include "scip/type_misc.h" 43 #include "scip/type_result.h" 44 #include "scip/type_retcode.h" 45 #include "scip/type_scip.h" 46 #include "scip/type_set.h" 47 #include "scip/type_sol.h" 48 #include "scip/type_stat.h" 49 #include "scip/type_var.h" 50 51 #ifdef __cplusplus 52 extern "C" { 53 #endif 54 55 56 /** copies the given Benders' decomposition to a new scip */ 57 SCIP_RETCODE SCIPbendersCopyInclude( 58 SCIP_BENDERS* benders, /**< Benders' decomposition */ 59 SCIP_SET* sourceset, /**< SCIP_SET of SCIP to copy from */ 60 SCIP_SET* targetset, /**< SCIP_SET of SCIP to copy to */ 61 SCIP_HASHMAP* varmap, /**< a hashmap to store the mapping of source variables corresponding 62 * target variables; must not be NULL */ 63 SCIP_Bool copysubproblems, /**< must the subproblems be copied with the Benders' decomposition copy */ 64 SCIP_Bool* valid /**< was the copying process valid? */ 65 ); 66 67 /** creates a Benders' decomposition */ 68 SCIP_RETCODE SCIPbendersCreate( 69 SCIP_BENDERS** benders, /**< pointer to Benders' decomposition data structure */ 70 SCIP_SET* set, /**< global SCIP settings */ 71 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 72 BMS_BLKMEM* blkmem, /**< block memory for parameter settings */ 73 const char* name, /**< name of Benders' decomposition */ 74 const char* desc, /**< description of Benders' decomposition */ 75 int priority, /**< priority of the Benders' decomposition */ 76 SCIP_Bool cutlp, /**< should Benders' cuts be generated for LP solutions */ 77 SCIP_Bool cutpseudo, /**< should Benders' cuts be generated for pseudo solutions */ 78 SCIP_Bool cutrelax, /**< should Benders' cuts be generated for relaxation solutions */ 79 SCIP_Bool shareauxvars, /**< should this Benders' use the highest priority Benders aux vars */ 80 SCIP_DECL_BENDERSCOPY ((*benderscopy)), /**< copy method of Benders' decomposition or NULL if you don't want to copy your plugin into sub-SCIPs */ 81 SCIP_DECL_BENDERSFREE ((*bendersfree)), /**< destructor of Benders' decomposition */ 82 SCIP_DECL_BENDERSINIT ((*bendersinit)), /**< initialize Benders' decomposition */ 83 SCIP_DECL_BENDERSEXIT ((*bendersexit)), /**< deinitialize Benders' decomposition */ 84 SCIP_DECL_BENDERSINITPRE((*bendersinitpre)),/**< presolving initialization method for Benders' decomposition */ 85 SCIP_DECL_BENDERSEXITPRE((*bendersexitpre)),/**< presolving deinitialization method for Benders' decomposition */ 86 SCIP_DECL_BENDERSINITSOL((*bendersinitsol)),/**< solving process initialization method of Benders' decomposition */ 87 SCIP_DECL_BENDERSEXITSOL((*bendersexitsol)),/**< solving process deinitialization method of Benders' decomposition */ 88 SCIP_DECL_BENDERSGETVAR((*bendersgetvar)),/**< returns the master variable for a given subproblem variable */ 89 SCIP_DECL_BENDERSCREATESUB((*benderscreatesub)),/**< creates a Benders' decomposition subproblem */ 90 SCIP_DECL_BENDERSPRESUBSOLVE((*benderspresubsolve)),/**< called prior to the subproblem solving loop */ 91 SCIP_DECL_BENDERSSOLVESUBCONVEX((*benderssolvesubconvex)),/**< the solving method for convex Benders' decomposition subproblems */ 92 SCIP_DECL_BENDERSSOLVESUB((*benderssolvesub)),/**< the solving method for the Benders' decomposition subproblems */ 93 SCIP_DECL_BENDERSPOSTSOLVE((*benderspostsolve)),/**< called after the subproblems are solved. */ 94 SCIP_DECL_BENDERSFREESUB((*bendersfreesub)),/**< the freeing method for the Benders' decomposition subproblems */ 95 SCIP_BENDERSDATA* bendersdata /**< Benders' decomposition data */ 96 ); 97 98 /** calls destructor and frees memory of Benders' decomposition */ 99 SCIP_RETCODE SCIPbendersFree( 100 SCIP_BENDERS** benders, /**< pointer to Benders' decomposition data structure */ 101 SCIP_SET* set /**< global SCIP settings */ 102 ); 103 104 /** initializes Benders' decomposition */ 105 SCIP_RETCODE SCIPbendersInit( 106 SCIP_BENDERS* benders, /**< Benders' decomposition */ 107 SCIP_SET* set /**< global SCIP settings */ 108 ); 109 110 /** calls exit method of Benders' decomposition */ 111 SCIP_RETCODE SCIPbendersExit( 112 SCIP_BENDERS* benders, /**< Benders' decomposition */ 113 SCIP_SET* set /**< global SCIP settings */ 114 ); 115 116 /** informs the Benders' decomposition that the presolving process is being started */ 117 SCIP_RETCODE SCIPbendersInitpre( 118 SCIP_BENDERS* benders, /**< Benders' decomposition */ 119 SCIP_SET* set, /**< global SCIP settings */ 120 SCIP_STAT* stat /**< dynamic problem statistics */ 121 ); 122 123 /** informs the Benders' decomposition that the presolving process has completed */ 124 SCIP_RETCODE SCIPbendersExitpre( 125 SCIP_BENDERS* benders, /**< Benders' decomposition */ 126 SCIP_SET* set, /**< global SCIP settings */ 127 SCIP_STAT* stat /**< dynamic problem statistics */ 128 ); 129 130 /** informs Benders' decomposition that the branch and bound process is being started */ 131 SCIP_RETCODE SCIPbendersInitsol( 132 SCIP_BENDERS* benders, /**< Benders' decomposition */ 133 SCIP_SET* set /**< global SCIP settings */ 134 ); 135 136 /** informs Benders' decomposition that the branch and bound process data is being freed */ 137 SCIP_RETCODE SCIPbendersExitsol( 138 SCIP_BENDERS* benders, /**< Benders' decomposition */ 139 SCIP_SET* set /**< global SCIP settings */ 140 ); 141 142 /** activates Benders' decomposition such that it is called in LP solving loop */ 143 SCIP_RETCODE SCIPbendersActivate( 144 SCIP_BENDERS* benders, /**< the Benders' decomposition structure */ 145 SCIP_SET* set, /**< global SCIP settings */ 146 int nsubproblems /**< the number subproblems used in this decomposition */ 147 ); 148 149 /** deactivates Benders' decomposition such that it is no longer called in LP solving loop */ 150 SCIP_RETCODE SCIPbendersDeactivate( 151 SCIP_BENDERS* benders, /**< the Benders' decomposition structure */ 152 SCIP_SET* set /**< global SCIP settings */ 153 ); 154 155 /** enables or disables all clocks of Benders' decomposition depending on the value of the flag */ 156 void SCIPbendersEnableOrDisableClocks( 157 SCIP_BENDERS* benders, /**< the Benders' decomposition for which all clocks should be enabled or disabled */ 158 SCIP_Bool enable /**< should the clocks of the Benders' decomposition be enabled? */ 159 ); 160 161 /** solves the subproblem using the current master problem solution. 162 * 163 * The checkint flag indicates whether integer feasibility can be assumed. If it is not assumed, i.e. checkint == 164 * FALSE, then only the convex relaxations of the subproblems are solved. If integer feasibility is assumed, i.e. 165 * checkint == TRUE, then the convex relaxations and the full CIP are solved to generate Benders' cuts and check 166 * solution feasibility. 167 */ 168 SCIP_RETCODE SCIPbendersExec( 169 SCIP_BENDERS* benders, /**< Benders' decomposition */ 170 SCIP_SET* set, /**< global SCIP settings */ 171 SCIP_SOL* sol, /**< primal CIP solution */ 172 SCIP_RESULT* result, /**< result of the pricing process */ 173 SCIP_Bool* infeasible, /**< is the master problem infeasible with respect to the Benders' cuts? */ 174 SCIP_Bool* auxviol, /**< set to TRUE only if the solution is feasible but the aux vars are violated */ 175 SCIP_BENDERSENFOTYPE type, /**< the type of solution being enforced */ 176 SCIP_Bool checkint /**< should the integer solution be checked by the subproblems */ 177 ); 178 179 /** Executes the subproblem solving process. */ 180 SCIP_RETCODE SCIPbendersExecSubproblemSolve( 181 SCIP_BENDERS* benders, /**< Benders' decomposition */ 182 SCIP_SET* set, /**< global SCIP settings */ 183 SCIP_SOL* sol, /**< primal CIP solution */ 184 int probnum, /**< the subproblem number */ 185 SCIP_BENDERSSOLVELOOP solveloop, /**< the solve loop iteration. The first iter is for LP, the second for IP */ 186 SCIP_Bool enhancement, /**< is the solve performed as part of an enhancement? */ 187 SCIP_Bool* solved, /**< flag to indicate whether the subproblem was solved */ 188 SCIP_Bool* infeasible, /**< returns whether the current subproblem is infeasible */ 189 SCIP_BENDERSENFOTYPE type /**< the enforcement type calling this function */ 190 ); 191 192 /** sets up the subproblem using the solution to the master problem */ 193 SCIP_RETCODE SCIPbendersSetupSubproblem( 194 SCIP_BENDERS* benders, /**< Benders' decomposition */ 195 SCIP_SET* set, /**< global SCIP settings */ 196 SCIP_SOL* sol, /**< primal CIP solution */ 197 int probnumber, /**< the subproblem number */ 198 SCIP_BENDERSENFOTYPE type /**< the enforcement type calling this function */ 199 ); 200 201 /** Solve a Benders' decomposition subproblems. This will either call the user defined method or the generic solving 202 * methods. If the generic method is called, then the subproblem must be set up before calling this method. */ 203 SCIP_RETCODE SCIPbendersSolveSubproblem( 204 SCIP_BENDERS* benders, /**< Benders' decomposition */ 205 SCIP_SET* set, /**< global SCIP settings */ 206 SCIP_SOL* sol, /**< primal CIP solution, can be NULL */ 207 int probnumber, /**< the subproblem number */ 208 SCIP_Bool* infeasible, /**< returns whether the current subproblem is infeasible */ 209 SCIP_Bool solvecip, /**< directly solve the CIP subproblem */ 210 SCIP_Real* objective /**< the objective function value of the subproblem, can be NULL */ 211 ); 212 213 /** frees the subproblems */ 214 SCIP_RETCODE SCIPbendersFreeSubproblem( 215 SCIP_BENDERS* benders, /**< Benders' decomposition */ 216 SCIP_SET* set, /**< global SCIP settings */ 217 int probnumber /**< the subproblem number */ 218 ); 219 220 /** compares the subproblem objective value with the auxiliary variable value for optimality */ 221 SCIP_Bool SCIPbendersSubproblemIsOptimal( 222 SCIP_BENDERS* benders, /**< the benders' decomposition structure */ 223 SCIP_SET* set, /**< global SCIP settings */ 224 SCIP_SOL* sol, /**< primal CIP solution */ 225 int probnumber /**< the subproblem number */ 226 ); 227 228 /** returns the value of the auxiliary variable value in a master problem solution */ 229 SCIP_Real SCIPbendersGetAuxiliaryVarVal( 230 SCIP_BENDERS* benders, /**< the benders' decomposition structure */ 231 SCIP_SET* set, /**< global SCIP settings */ 232 SCIP_SOL* sol, /**< primal CIP solution */ 233 int probnumber /**< the subproblem number */ 234 ); 235 236 /** Solves an independent subproblem to identify its lower bound. The lower bound is then used to update the bound on 237 * the auxiliary variable. 238 */ 239 SCIP_RETCODE SCIPbendersComputeSubproblemLowerbound( 240 SCIP_BENDERS* benders, /**< Benders' decomposition */ 241 SCIP_SET* set, /**< global SCIP settings */ 242 int probnumber, /**< the subproblem to be evaluated */ 243 SCIP_Real* lowerbound, /**< the lowerbound for the subproblem */ 244 SCIP_Bool* infeasible /**< was the subproblem found to be infeasible? */ 245 ); 246 247 /** merges a subproblem into the master problem. This process just adds a copy of the subproblem variables and 248 * constraints to the master problem, but keeps the subproblem stored in the Benders' decomposition data structure. 249 * The reason for keeping the subproblem available is for when it is queried for solutions after the problem is solved. 250 * 251 * Once the subproblem is merged into the master problem, then the subproblem is flagged as disabled. This means that 252 * it will not be solved in the subsequent subproblem solving loops. 253 * 254 * The associated auxiliary variables are kept in the master problem. The objective function of the merged subproblem 255 * is added as an underestimator constraint. 256 */ 257 SCIP_RETCODE SCIPbendersMergeSubproblemIntoMaster( 258 SCIP_BENDERS* benders, /**< Benders' decomposition */ 259 SCIP_SET* set, /**< global SCIP settings */ 260 SCIP_HASHMAP* varmap, /**< a hashmap to store the mapping of subproblem variables corresponding 261 * to the newly created master variables, or NULL */ 262 SCIP_HASHMAP* consmap, /**< a hashmap to store the mapping of subproblem constraints to the 263 corresponding newly created constraints, or NULL */ 264 int probnumber /**< the number of the subproblem that will be merged into the master problem*/ 265 ); 266 267 /** Applies a Benders' decomposition to the problem based upon the decomposition selected from the storage */ 268 extern 269 SCIP_RETCODE SCIPbendersApplyDecomposition( 270 SCIP_BENDERS* benders, /**< Benders' decomposition */ 271 SCIP_SET* set, /**< global SCIP settings */ 272 SCIP_DECOMP* decomp /**< the decomposition to apply to the problem */ 273 ); 274 275 /** sets priority of Benders' decomposition */ 276 void SCIPbendersSetPriority( 277 SCIP_BENDERS* benders, /**< Benders' decomposition */ 278 SCIP_SET* set, /**< global SCIP settings */ 279 int priority /**< new priority of the Benders' decomposition */ 280 ); 281 282 /** sets copy callback of Benders' decomposition */ 283 void SCIPbendersSetCopy( 284 SCIP_BENDERS* benders, /**< Benders' decomposition */ 285 SCIP_DECL_BENDERSCOPY ((*benderscopy)) /**< copy callback of Benders' decomposition */ 286 ); 287 288 /** sets destructor callback of Benders' decomposition */ 289 void SCIPbendersSetFree( 290 SCIP_BENDERS* benders, /**< Benders' decomposition */ 291 SCIP_DECL_BENDERSFREE ((*bendersfree)) /**< destructor of Benders' decomposition */ 292 ); 293 294 /** sets initialization callback of Benders' decomposition */ 295 void SCIPbendersSetInit( 296 SCIP_BENDERS* benders, /**< Benders' decomposition */ 297 SCIP_DECL_BENDERSINIT((*bendersinit)) /**< initialize Benders' decomposition */ 298 ); 299 300 /** sets deinitialization callback of Benders' decomposition */ 301 void SCIPbendersSetExit( 302 SCIP_BENDERS* benders, /**< Benders' decomposition */ 303 SCIP_DECL_BENDERSEXIT((*bendersexit)) /**< deinitialize Benders' decomposition */ 304 ); 305 306 /** sets presolving initialization callback of Benders' decomposition */ 307 void SCIPbendersSetInitpre( 308 SCIP_BENDERS* benders, /**< Benders' decomposition */ 309 SCIP_DECL_BENDERSINITPRE((*bendersinitpre))/**< initialize presolving for Benders' decomposition */ 310 ); 311 312 /** sets presolving deinitialization callback of Benders' decomposition */ 313 void SCIPbendersSetExitpre( 314 SCIP_BENDERS* benders, /**< Benders' decomposition */ 315 SCIP_DECL_BENDERSEXITPRE((*bendersexitpre))/**< deinitialize presolving for Benders' decomposition */ 316 ); 317 318 /** sets solving process initialization callback of Benders' decomposition */ 319 void SCIPbendersSetInitsol( 320 SCIP_BENDERS* benders, /**< Benders' decomposition */ 321 SCIP_DECL_BENDERSINITSOL((*bendersinitsol))/**< solving process initialization callback of Benders' decomposition */ 322 ); 323 324 /** sets solving process deinitialization callback of Benders' decomposition */ 325 void SCIPbendersSetExitsol( 326 SCIP_BENDERS* benders, /**< Benders' decomposition */ 327 SCIP_DECL_BENDERSEXITSOL((*bendersexitsol))/**< solving process deinitialization callback of Benders' decomposition */ 328 ); 329 330 /** sets the pre subproblem solve callback of Benders' decomposition */ 331 void SCIPbendersSetPresubsolve( 332 SCIP_BENDERS* benders, /**< Benders' decomposition */ 333 SCIP_DECL_BENDERSPRESUBSOLVE((*benderspresubsolve))/**< called prior to the subproblem solving loop */ 334 ); 335 336 /** sets convex solve callback of Benders' decomposition */ 337 void SCIPbendersSetSolvesubconvex( 338 SCIP_BENDERS* benders, /**< Benders' decomposition */ 339 SCIP_DECL_BENDERSSOLVESUBCONVEX((*benderssolvesubconvex))/**< solving method for the convex Benders' decomposition subproblem */ 340 ); 341 342 /** sets solve callback of Benders' decomposition */ 343 void SCIPbendersSetSolvesub( 344 SCIP_BENDERS* benders, /**< Benders' decomposition */ 345 SCIP_DECL_BENDERSSOLVESUB((*benderssolvesub))/**< solving method for a Benders' decomposition subproblem */ 346 ); 347 348 /** sets post-solve callback of Benders' decomposition */ 349 void SCIPbendersSetPostsolve( 350 SCIP_BENDERS* benders, /**< Benders' decomposition */ 351 SCIP_DECL_BENDERSPOSTSOLVE((*benderspostsolve))/**< solving process deinitialization callback of Benders' decomposition */ 352 ); 353 354 /** sets post-solve callback of Benders' decomposition */ 355 void SCIPbendersSetSubproblemComp( 356 SCIP_BENDERS* benders, /**< Benders' decomposition */ 357 SCIP_DECL_SORTPTRCOMP((*benderssubcomp)) /**< a comparator for defining the solving order of the subproblems */ 358 ); 359 360 /** sets free subproblem callback of Benders' decomposition */ 361 void SCIPbendersSetFreesub( 362 SCIP_BENDERS* benders, /**< Benders' decomposition */ 363 SCIP_DECL_BENDERSFREESUB((*bendersfreesub))/**< the freeing callback for the subproblem */ 364 ); 365 366 /** Returns the corresponding master or subproblem variable for the given variable. 367 * This provides a call back for the variable mapping between the master and subproblems. */ 368 SCIP_RETCODE SCIPbendersGetVar( 369 SCIP_BENDERS* benders, /**< Benders' decomposition */ 370 SCIP_SET* set, /**< global SCIP settings */ 371 SCIP_VAR* var, /**< the variable for which the corresponding variable is desired */ 372 SCIP_VAR** mappedvar, /**< the variable that is mapped to var */ 373 int probnumber /**< the problem number for the desired variable, -1 for the master problem */ 374 ); 375 376 /** adds a subproblem to the Benders' decomposition data */ 377 SCIP_RETCODE SCIPbendersAddSubproblem( 378 SCIP_BENDERS* benders, /**< Benders' decomposition */ 379 SCIP* subproblem /**< subproblem to be added to the data storage */ 380 ); 381 382 /** removes the subproblems from the Benders' decomposition data */ 383 void SCIPbendersRemoveSubproblems( 384 SCIP_BENDERS* benders /**< Benders' decomposition */ 385 ); 386 387 /** Sets whether the subproblem is enabled or disabled. A subproblem is disabled if it has been merged into the master 388 * problem. 389 */ 390 void SCIPbendersSetSubproblemEnabled( 391 SCIP_BENDERS* benders, /**< Benders' decomposition */ 392 int probnumber, /**< the subproblem number */ 393 SCIP_Bool enabled /**< flag to indicate whether the subproblem is enabled */ 394 ); 395 396 /** changes all of the master problem variables in the given subproblem to continuous */ 397 SCIP_RETCODE SCIPbendersChgMastervarsToCont( 398 SCIP_BENDERS* benders, /**< Benders' decomposition */ 399 SCIP_SET* set, /**< global SCIP settings */ 400 int probnumber /**< the subproblem number */ 401 ); 402 403 /** sets a flag to indicate whether the master variables are all set to continuous */ 404 SCIP_RETCODE SCIPbendersSetMastervarsCont( 405 SCIP_BENDERS* benders, /**< Benders' decomposition */ 406 int probnumber, /**< the subproblem number */ 407 SCIP_Bool arecont /**< flag to indicate whether the master problem variables are continuous */ 408 ); 409 410 /** returns whether the master variables are all set to continuous */ 411 SCIP_Bool SCIPbendersGetMastervarsCont( 412 SCIP_BENDERS* benders, /**< Benders' decomposition */ 413 int probnumber /**< the subproblem number */ 414 ); 415 416 /** adds the data for the generated cuts to the Benders' cut storage */ 417 SCIP_RETCODE SCIPbendersStoreCut( 418 SCIP_BENDERS* benders, /**< Benders' decomposition cut */ 419 SCIP_SET* set, /**< global SCIP settings */ 420 SCIP_VAR** vars, /**< the variables that have non-zero coefficients in the cut */ 421 SCIP_Real* vals, /**< the coefficients of the variables in the cut */ 422 SCIP_Real lhs, /**< the left hand side of the cut */ 423 SCIP_Real rhs, /**< the right hand side of the cut */ 424 int nvars /**< the number of variables with non-zero coefficients in the cut */ 425 ); 426 427 /** inserts a Benders' cut algorithm plugin into the Benders' cuts plugin list */ 428 SCIP_RETCODE SCIPbendersIncludeBenderscut( 429 SCIP_BENDERS* benders, /**< Benders' decomposition structure */ 430 SCIP_SET* set, /**< global SCIP settings */ 431 SCIP_BENDERSCUT* benderscut /**< Benders' cut */ 432 ); 433 434 /** sets the Benders' cuts sorted flags in the Benders' decomposition */ 435 void SCIPbendersSetBenderscutsSorted( 436 SCIP_BENDERS* benders, /**< Benders' decomposition structure */ 437 SCIP_Bool sorted /**< the value to set the sorted flag to */ 438 ); 439 440 /** sorts Benders' decomposition cuts by priorities */ 441 void SCIPbendersSortBenderscuts( 442 SCIP_BENDERS* benders /**< Benders' decomposition */ 443 ); 444 445 /** sorts Benders' decomposition cuts by name */ 446 void SCIPbendersSortBenderscutsName( 447 SCIP_BENDERS* benders /**< Benders' decomposition */ 448 ); 449 450 #ifdef __cplusplus 451 } 452 #endif 453 454 #endif 455