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 cons_benderslp.c 26 * @ingroup DEFPLUGINS_CONS 27 * @brief constraint handler for benderslp decomposition 28 * @author Stephen J. Maher 29 * 30 * Two constraint handlers are implemented for the generation of Benders' decomposition cuts. When included in a 31 * problem, the Benders' decomposition constraint handlers generate cuts during the enforcement of LP and relaxation 32 * solutions. Additionally, Benders' decomposition cuts can be generated when checking the feasibility of solutions with 33 * respect to the subproblem constraints. 34 * 35 * This constraint handler has an enforcement priority that is greater than the integer constraint handler. This means 36 * that all LP solutions will be first checked for feasibility with respect to the Benders' decomposition second stage 37 * constraints before performing an integrality check. This is part of a multi-phase approach for solving mixed integer 38 * programs by Benders' decomposition. 39 * 40 * A parameter is available to control the depth at which the non-integer LP solution are enforced by solving the 41 * Benders' decomposition subproblems. This parameter is set to 0 by default, indicating that non-integer LP solutions 42 * are enforced only at the root node. 43 */ 44 45 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 46 47 #include <assert.h> 48 49 #include "scip/scip.h" 50 #include "scip/cons_benderslp.h" 51 #include "scip/cons_benders.h" 52 53 54 /* fundamental constraint handler properties */ 55 #define CONSHDLR_NAME "benderslp" 56 #define CONSHDLR_DESC "constraint handler for Benders' Decomposition to separate LP solutions" 57 #define CONSHDLR_ENFOPRIORITY 10000000 /**< priority of the constraint handler for constraint enforcing */ 58 #define CONSHDLR_CHECKPRIORITY 10000000 /**< priority of the constraint handler for checking feasibility */ 59 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation, 60 * propagation and enforcement, -1 for no eager evaluations, 0 for first only */ 61 #define CONSHDLR_NEEDSCONS FALSE /**< should the constraint handler be skipped, if no constraints are available? */ 62 63 64 #define DEFAULT_CONSBENDERSLP_MAXDEPTH 0/**< depth at which Benders' decomposition cuts are generated from the LP 65 * solution (-1: always, 0: only at root) */ 66 #define DEFAULT_CONSBENDERSLP_FREQ 0/**< the depth frequency for generating LP cuts after the max depth is reached (0: never, 1: all nodes, ...) */ 67 #define DEFAULT_CONSBENDERSLP_STALLLIMIT 100/**< the number of nodes processed without a dual bound improvement before enforcing the LP relaxation, 0: no stall count applied */ 68 #define DEFAULT_CONSBENDERSLP_ITERLIMIT 100 /**< after the root node, only iterlimit fractional LP solutions are used at each node to generate Benders' decomposition cuts. */ 69 #define DEFAULT_ACTIVE FALSE /**< is the constraint handler active? */ 70 71 /* 72 * Data structures 73 */ 74 75 /** constraint handler data */ 76 struct SCIP_ConshdlrData 77 { 78 /* parameters for controlling the two-phase method for Benders' decomposition */ 79 int maxdepth; /**< the maximum depth at which Benders' cuts are generated from the LP */ 80 int freq; /**< the depth frequency of generating LP cuts after the max depth is reached */ 81 SCIP_Bool active; /**< is the constraint handler active? */ 82 83 /* variable used to control the behaviour of the two-phase method for Benders' decomposition */ 84 SCIP_Longint ncallsnode; /**< the number of calls at the current node */ 85 SCIP_NODE* currnode; /**< the current node */ 86 SCIP_Real prevbound; /**< the previous dual bound */ 87 int iterlimit; /**< the iteration limit for the first phase of the two-phase method at a node lower than the root. */ 88 int stallcount; /**< the number of nodes processed since the last lower bound increase */ 89 int stalllimit; /**< the number of nodes processed without bound improvement before enforcing the LP relaxation */ 90 }; 91 92 93 /* 94 * Local methods 95 */ 96 97 98 /* 99 * Callback methods of constraint handler 100 */ 101 102 /** copy method for constraint handler plugins (called when SCIP copies plugins) */ 103 static 104 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyBenderslp) 105 { /*lint --e{715}*/ 106 assert(scip != NULL); 107 108 SCIP_CALL( SCIPincludeConshdlrBenderslp(scip) ); 109 110 *valid = TRUE; 111 112 return SCIP_OKAY; 113 } 114 115 116 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */ 117 static 118 SCIP_DECL_CONSFREE(consFreeBenderslp) 119 { /*lint --e{715}*/ 120 SCIP_CONSHDLRDATA* conshdlrdata; 121 122 assert(scip != NULL); 123 assert(conshdlr != NULL); 124 125 conshdlrdata = SCIPconshdlrGetData(conshdlr); 126 assert(conshdlrdata != NULL); 127 128 /* freeing the constraint handler data */ 129 SCIPfreeMemory(scip, &conshdlrdata); 130 131 return SCIP_OKAY; 132 } 133 134 135 136 /** constraint enforcing method of constraint handler for LP solutions */ 137 static 138 SCIP_DECL_CONSENFOLP(consEnfolpBenderslp) 139 { /*lint --e{715}*/ 140 SCIP_CONSHDLRDATA* conshdlrdata; 141 142 assert(conshdlr != NULL); 143 144 conshdlrdata = SCIPconshdlrGetData(conshdlr); 145 146 /* updating the stall count. If the bound has improved since the last call, then the stall count is set to zero */ 147 conshdlrdata->stallcount++; 148 if( SCIPisLT(scip, conshdlrdata->prevbound, SCIPgetLowerbound(scip)) ) 149 conshdlrdata->stallcount = 0; 150 151 conshdlrdata->prevbound = SCIPgetLowerbound(scip); 152 conshdlrdata->ncallsnode++; 153 154 /* if a new node is being processed, then the iteration counts are reset. */ 155 if( conshdlrdata->currnode != SCIPgetCurrentNode(scip) ) 156 { 157 conshdlrdata->currnode = SCIPgetCurrentNode(scip); 158 conshdlrdata->ncallsnode = 0; 159 } 160 161 /* the result is initially set to FEASIBLE. If the two-phase method is not executed, then the result will remain as 162 * FEASIBLE. The actual feasibility of the Benders' decomposition subproblems is checked in cons_benders. 163 */ 164 (*result) = SCIP_FEASIBLE; 165 166 /* only check the Benders' decomposition subproblems for fractional LP solutions if the two-phase method is activated */ 167 if( !conshdlrdata->active ) 168 return SCIP_OKAY; 169 170 /* checking whether the two-phase method is performed. 171 * - If a maxdepth is specified 172 * - current depth is checked 173 * - the frequency is checked, if a frequency is specified 174 * - the stalllimit is checked if a stalllimit is specified. 175 */ 176 if( conshdlrdata->maxdepth >= 0 && SCIPgetDepth(scip) > conshdlrdata->maxdepth 177 && (conshdlrdata->freq == 0 || SCIPgetDepth(scip) % conshdlrdata->freq != 0) 178 && (conshdlrdata->stalllimit == 0 || conshdlrdata->stallcount < conshdlrdata->stalllimit) ) 179 return SCIP_OKAY; 180 181 /* if an iteration limit is specified, then this is imposed at nodes after the root node */ 182 if( SCIPgetDepth(scip) > 0 && conshdlrdata->ncallsnode >= conshdlrdata->iterlimit ) 183 return SCIP_OKAY; 184 185 /* the two phase method is only performed at the root node for sub-SCIPs */ 186 if( SCIPgetSubscipDepth(scip) > 0 && SCIPgetDepth(scip) > 0 ) 187 return SCIP_OKAY; 188 189 /* checking the Benders' decomposition subproblems for feasibility. */ 190 SCIP_CALL( SCIPconsBendersEnforceSolution(scip, NULL, conshdlr, result, SCIP_BENDERSENFOTYPE_LP, FALSE) ); 191 192 /* if the stalllimit is exceeded and the subproblem were checked, then the stall count is reset to zero */ 193 if( conshdlrdata->stallcount >= conshdlrdata->stalllimit ) 194 conshdlrdata->stallcount = 0; 195 196 return SCIP_OKAY; 197 } 198 199 200 /** constraint enforcing method of constraint handler for relaxation solutions */ 201 static 202 SCIP_DECL_CONSENFORELAX(consEnforelaxBenderslp) 203 { /*lint --e{715}*/ 204 SCIP_CONSHDLRDATA* conshdlrdata; 205 206 assert(conshdlr != NULL); 207 208 conshdlrdata = SCIPconshdlrGetData(conshdlr); 209 210 if( !conshdlrdata->active || (conshdlrdata->maxdepth >= 0 && SCIPgetDepth(scip) > conshdlrdata->maxdepth) ) 211 (*result) = SCIP_FEASIBLE; 212 else 213 SCIP_CALL( SCIPconsBendersEnforceSolution(scip, sol, conshdlr, result, SCIP_BENDERSENFOTYPE_RELAX, FALSE) ); 214 215 return SCIP_OKAY; 216 } 217 218 219 /** constraint enforcing method of constraint handler for pseudo solutions */ 220 static 221 SCIP_DECL_CONSENFOPS(consEnfopsBenderslp) 222 { /*lint --e{715}*/ 223 SCIP_CONSHDLRDATA* conshdlrdata; 224 225 assert(conshdlr != NULL); 226 227 conshdlrdata = SCIPconshdlrGetData(conshdlr); 228 229 if( !conshdlrdata->active || (conshdlrdata->maxdepth >= 0 && SCIPgetDepth(scip) > conshdlrdata->maxdepth) ) 230 (*result) = SCIP_FEASIBLE; 231 else 232 SCIP_CALL( SCIPconsBendersEnforceSolution(scip, NULL, conshdlr, result, SCIP_BENDERSENFOTYPE_PSEUDO, FALSE) ); 233 234 return SCIP_OKAY; 235 } 236 237 238 /** feasibility check method of constraint handler for integral solutions. 239 * The feasibility check for Benders' decomposition is performed in cons_benders. As such, it is redundant to perform 240 * the feasibility check here. As such, the solution is flagged as feasible, which will then be corrected in 241 * cons_benders if the solution is infeasible with respect to the second stage constraints 242 */ 243 static 244 SCIP_DECL_CONSCHECK(consCheckBenderslp) 245 { /*lint --e{715}*/ 246 (*result) = SCIP_FEASIBLE; 247 248 return SCIP_OKAY; 249 } 250 251 252 /** variable rounding lock method of constraint handler */ 253 static 254 SCIP_DECL_CONSLOCK(consLockBenderslp) 255 { /*lint --e{715}*/ 256 return SCIP_OKAY; 257 } 258 259 260 261 /* 262 * constraint specific interface methods 263 */ 264 265 /** creates the handler for executing the Benders' decomposition subproblem solve on fractional LP solution and 266 * includes it in SCIP */ 267 SCIP_RETCODE SCIPincludeConshdlrBenderslp( 268 SCIP* scip /**< SCIP data structure */ 269 ) 270 { 271 SCIP_CONSHDLRDATA* conshdlrdata = NULL; 272 SCIP_CONSHDLR* conshdlr; 273 274 /* create benderslp constraint handler data */ 275 SCIP_CALL( SCIPallocMemory(scip, &conshdlrdata) ); 276 BMSclearMemory(conshdlrdata); 277 conshdlrdata->prevbound = -SCIPinfinity(scip); 278 279 conshdlr = NULL; 280 281 /* include constraint handler */ 282 SCIP_CALL( SCIPincludeConshdlrBasic(scip, &conshdlr, CONSHDLR_NAME, CONSHDLR_DESC, 283 CONSHDLR_ENFOPRIORITY, CONSHDLR_CHECKPRIORITY, CONSHDLR_EAGERFREQ, CONSHDLR_NEEDSCONS, 284 consEnfolpBenderslp, consEnfopsBenderslp, consCheckBenderslp, consLockBenderslp, 285 conshdlrdata) ); 286 assert(conshdlr != NULL); 287 288 /* set non-fundamental callbacks via specific setter functions */ 289 SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyBenderslp, NULL) ); 290 SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeBenderslp) ); 291 SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxBenderslp) ); 292 293 /* add Benders' decomposition LP constraint handler parameters */ 294 SCIP_CALL( SCIPaddIntParam(scip, 295 "constraints/" CONSHDLR_NAME "/maxdepth", 296 "depth at which Benders' decomposition cuts are generated from the LP solution (-1: always, 0: only at root)", 297 &conshdlrdata->maxdepth, TRUE, DEFAULT_CONSBENDERSLP_MAXDEPTH, -1, SCIP_MAXTREEDEPTH, NULL, NULL) ); 298 299 SCIP_CALL( SCIPaddIntParam(scip, 300 "constraints/" CONSHDLR_NAME "/depthfreq", 301 "the depth frequency for generating LP cuts after the max depth is reached (0: never, 1: all nodes, ...)", 302 &conshdlrdata->freq, TRUE, DEFAULT_CONSBENDERSLP_FREQ, 0, SCIP_MAXTREEDEPTH, NULL, NULL) ); 303 304 SCIP_CALL( SCIPaddIntParam(scip, 305 "constraints/" CONSHDLR_NAME "/stalllimit", 306 "the number of nodes processed without a dual bound improvement before enforcing the LP relaxation, 0: no stall count applied", 307 &conshdlrdata->stalllimit, TRUE, DEFAULT_CONSBENDERSLP_STALLLIMIT, 0, INT_MAX, NULL, NULL) ); 308 309 SCIP_CALL( SCIPaddIntParam(scip, 310 "constraints/" CONSHDLR_NAME "/iterlimit", 311 "after the root node, only iterlimit fractional LP solutions are used at each node to generate Benders' decomposition cuts.", 312 &conshdlrdata->iterlimit, TRUE, DEFAULT_CONSBENDERSLP_ITERLIMIT, 0, INT_MAX, NULL, NULL) ); 313 314 SCIP_CALL( SCIPaddBoolParam(scip, 315 "constraints/" CONSHDLR_NAME "/active", "is the Benders' decomposition LP cut constraint handler active?", 316 &conshdlrdata->active, FALSE, DEFAULT_ACTIVE, NULL, NULL)); 317 318 conshdlrdata->stallcount = 0; 319 return SCIP_OKAY; 320 } 321