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 sepa_closecuts.c 26 * @ingroup DEFPLUGINS_SEPA 27 * @brief closecuts meta separator 28 * @author Marc Pfetsch 29 * 30 * This separator generates a convex combination of the current LP solution and either the best 31 * primal feasible solution or an interior point of the LP relaxation. If the convex combination is 32 * proper, the new point is closer to the convex hull of the feasible points. The separator then 33 * calls all other separators to separate this point. The idea is that in this way possibly "deeper" 34 * cuts are generated. Note, however, that the new point is not a basic solution, i.e., separators 35 * relying basis information, e.g., Gomory cuts, will not work. 36 * 37 * The other cuts are generated via the sepasol() callbacks in constraints handlers or separators. 38 * 39 * This separator stops after a certain number (parameter @p maxunsuccessful) of unsuccessful 40 * calls. It also inhibits the separation of the ordinary LP solution if it already generated enough 41 * (parameter @p sepathreshold) cuts. The convex combination is determined via the parameter @p 42 * sepacombvalue. 43 * 44 * In general, this separator makes sense if it is expected that there will be many separation 45 * rounds and many cuts will be again deleted, because they are not active after a certain number of 46 * rounds. In particular, branch-and-cut algorithms for combinatorial optimization problems form 47 * good candidates. 48 * 49 * The idea seems to be first proposed in the context of the travelling salesman problem, see@par 50 * The Traveling Salesman Problem: A Computational Study@n 51 * David L. Applegate, Robert E. Bixby, Vasek Chvatal & William J. Cook@n 52 * Princeton University Press 2006@n 53 * 54 * for more details. See also@par 55 * Acceleration of cutting-plane and column generation algorithms: Applications to network design.@n 56 * Walid Ben-Ameur, Jose Neto@n 57 * Networks 49(1): 3-17 (2007). 58 */ 59 60 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 61 62 #include "scip/pub_message.h" 63 #include "scip/pub_sepa.h" 64 #include "scip/pub_tree.h" 65 #include "scip/pub_var.h" 66 #include "scip/scip_branch.h" 67 #include "scip/scip_cut.h" 68 #include "scip/scip_general.h" 69 #include "scip/scip_lp.h" 70 #include "scip/scip_mem.h" 71 #include "scip/scip_message.h" 72 #include "scip/scip_numerics.h" 73 #include "scip/scip_param.h" 74 #include "scip/scip_prob.h" 75 #include "scip/scip_sepa.h" 76 #include "scip/scip_sol.h" 77 #include "scip/scip_solvingstats.h" 78 #include "scip/scip_timing.h" 79 #include "scip/scip_tree.h" 80 #include "scip/sepa_closecuts.h" 81 #include <string.h> 82 83 84 85 #define SEPA_NAME "closecuts" 86 #define SEPA_DESC "closecuts meta separator" 87 #define SEPA_PRIORITY 1000000 88 #define SEPA_FREQ -1 89 #define SEPA_MAXBOUNDDIST 1.0 90 #define SEPA_USESSUBSCIP FALSE /**< does the separator use a secondary SCIP instance? */ 91 #define SEPA_DELAY FALSE /**< should separation method be delayed, if other separators found cuts? */ 92 93 94 /* default values for parameters */ 95 #define SCIP_DEFAULT_SEPARELINT TRUE /**< generate close cuts w.r.t. relative interior point (best solution otherwise)? */ 96 #define SCIP_DEFAULT_SEPACOMBVALUE 0.30 /**< convex combination value for close cuts */ 97 #define SCIP_DEFAULT_SEPATHRESHOLD 50 /**< threshold on number of generated cuts below which the ordinary separation is started */ 98 #define SCIP_DEFAULT_INCLOBJCUTOFF FALSE /**< include the objective cutoff when computing the relative interior? */ 99 #define SCIP_DEFAULT_RECOMPUTERELINT FALSE /**< recompute relative interior in each separation call? */ 100 #define SCIP_DEFAULT_MAXUNSUCCESSFUL 0 /**< turn off separation in current node after unsuccessful calls (-1 never turn off) */ 101 #define SCIP_DEFAULT_MAXLPITERFACTOR 10.0 /**< factor for maximal LP iterations in relative interior computation compared to node LP iterations */ 102 103 #define SCIP_MIN_LPITERS 100 /**< minimum number of allowed LP iterations in relative interior computation */ 104 105 106 /** separator data */ 107 struct SCIP_SepaData 108 { 109 SCIP_Bool separelint; /**< generate close cuts w.r.t. relative interior point (best solution otherwise)? */ 110 SCIP_Bool triedRelint; /**< tried to compute relative interior */ 111 SCIP_Real sepacombvalue; /**< convex combination value for close cuts */ 112 int sepathreshold; /**< threshold on number of generated cuts below which the ordinary separation is started */ 113 SCIP_Bool inclobjcutoff; /**< include the objective cutoff when computing the relative interior? */ 114 SCIP_Bool recomputerelint; /**< recompute relative interior in each separation call? */ 115 int maxunsuccessful; /**< turn off separation in current node after unsuccessful calls (-1 never turn off) */ 116 SCIP_SOL* sepasol; /**< solution that can be used for generating close cuts */ 117 SCIP_Longint discardnode; /**< number of node for which separation is discarded */ 118 SCIP_Real maxlpiterfactor; /**< factor for maximal LP iterations in relative interior computation compared to node LP iterations */ 119 int nunsuccessful; /**< number of consecutive unsuccessful calls */ 120 }; 121 122 123 /** generate point for close cut separation 124 * 125 * The constructed point is the convex combination of the point stored in set->closesol and the 126 * current LP solution. The convexity parameter is set->sepa_closecombvalue. If this parameter is 127 * 0, the point coincides with the LP solution. 128 */ 129 static 130 SCIP_RETCODE generateCloseCutPoint( 131 SCIP* scip, /**< SCIP data structure */ 132 SCIP_SEPADATA* sepadata, /**< separator data */ 133 SCIP_SOL** point /**< point to be generated (or NULL if unsuccessful) */ 134 ) 135 { 136 SCIP_VAR** vars; 137 SCIP_VAR* var; 138 SCIP_Real val; 139 SCIP_Real alpha; 140 SCIP_Real onealpha; 141 SCIP_Real lb; 142 SCIP_Real ub; 143 int nvars; 144 int i; 145 146 assert( scip != NULL ); 147 assert( point != NULL ); 148 149 *point = NULL; 150 if ( sepadata->sepasol == NULL ) 151 return SCIP_OKAY; 152 153 alpha = sepadata->sepacombvalue; 154 if ( alpha < 0.001 ) 155 return SCIP_OKAY; 156 onealpha = 1.0 - alpha; 157 158 /* create solution */ 159 SCIP_CALL( SCIPcreateSol(scip, point, NULL) ); 160 161 /* generate convex combination */ 162 vars = SCIPgetVars(scip); 163 nvars = SCIPgetNVars(scip); 164 for (i = 0; i < nvars; ++i) 165 { 166 var = vars[i]; 167 val = alpha * SCIPgetSolVal(scip, sepadata->sepasol, var) + onealpha * SCIPvarGetLPSol(var); 168 169 /* If both the LP relaxation and the base point respect the variable bounds, the computed point will satisfy them 170 * as well. However, variables might be fixed (e.g. by branching) since the time of the computation of the base 171 * point. Thus, we adapt the value to lie inside the bounds in optimized mode. */ 172 lb = SCIPvarGetLbLocal(var); 173 ub = SCIPvarGetUbLocal(var); 174 val = MAX(val, lb); 175 val = MIN(val, ub); 176 177 if ( ! SCIPisZero(scip, val) ) 178 { 179 SCIP_CALL( SCIPsetSolVal(scip, *point, var, val) ); 180 } 181 } 182 183 return SCIP_OKAY; 184 } 185 186 187 /* 188 * Callback methods of separator 189 */ 190 191 192 /** copy method for separator plugins (called when SCIP copies plugins) */ 193 static 194 SCIP_DECL_SEPACOPY(sepaCopyClosecuts) 195 { /*lint --e{715}*/ 196 assert( scip != NULL ); 197 assert( sepa != NULL ); 198 assert( strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0 ); 199 200 /* call inclusion method of constraint handler */ 201 SCIP_CALL( SCIPincludeSepaClosecuts(scip) ); 202 203 return SCIP_OKAY; 204 } 205 206 /** destructor of separator to free user data (called when SCIP is exiting) */ 207 static 208 SCIP_DECL_SEPAFREE(sepaFreeClosecuts) 209 { /*lint --e{715}*/ 210 SCIP_SEPADATA* sepadata; 211 212 assert( sepa != NULL ); 213 assert( strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0 ); 214 215 /* free separator data */ 216 sepadata = SCIPsepaGetData(sepa); 217 assert( sepadata != NULL ); 218 219 SCIPfreeBlockMemory(scip, &sepadata); 220 221 SCIPsepaSetData(sepa, NULL); 222 223 return SCIP_OKAY; 224 } 225 226 227 /** solving process deinitialization method of separator (called before branch and bound process data is freed) */ 228 static 229 SCIP_DECL_SEPAEXITSOL(sepaExitsolClosecuts) 230 { /*lint --e{715}*/ 231 SCIP_SEPADATA* sepadata; 232 233 assert( sepa != NULL ); 234 assert( strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0 ); 235 236 sepadata = SCIPsepaGetData(sepa); 237 assert( sepadata != NULL ); 238 239 if ( sepadata->separelint && sepadata->sepasol != NULL ) 240 { 241 SCIP_CALL( SCIPfreeSol(scip, &sepadata->sepasol) ); 242 sepadata->triedRelint = FALSE; 243 } 244 sepadata->discardnode = -1; 245 sepadata->nunsuccessful = 0; 246 247 return SCIP_OKAY; 248 } 249 250 251 /** LP solution separation method of separator */ 252 static 253 SCIP_DECL_SEPAEXECLP(sepaExeclpClosecuts) 254 { /*lint --e{715}*/ 255 SCIP_SEPADATA* sepadata; 256 SCIP_Longint currentnodenumber; 257 SCIP_SOL* point = NULL; 258 SCIP_Bool isroot; 259 260 assert( sepa != NULL ); 261 assert( strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0 ); 262 assert( result != NULL ); 263 264 *result = SCIP_DIDNOTRUN; 265 266 /* only call separator, if LP has been solved (need LP to compute separation point) */ 267 if ( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL ) 268 return SCIP_OKAY; 269 270 /* only call separator, if there are fractional variables */ 271 if ( SCIPgetNLPBranchCands(scip) == 0 ) 272 return SCIP_OKAY; 273 274 /* exit if we stopped ... */ 275 if ( SCIPisStopped(scip) ) 276 return SCIP_OKAY; 277 278 /* get separation data */ 279 sepadata = SCIPsepaGetData(sepa); 280 assert( sepadata != NULL ); 281 282 /* exit if we already decided to discard the current node */ 283 currentnodenumber = SCIPnodeGetNumber(SCIPgetCurrentNode(scip)); 284 if ( sepadata->discardnode == currentnodenumber ) 285 return SCIP_OKAY; 286 287 SCIPdebugMsg(scip, "Separation method of closecuts separator.\n"); 288 289 /* check whether we have to compute a relative interior point */ 290 if ( sepadata->separelint ) 291 { 292 if ( sepadata->recomputerelint ) 293 { 294 /* check if previous relative interior point should be forgotten, otherwise it is computed only once and the 295 * same point is used for all nodes */ 296 if ( sepadata->sepasol != NULL ) 297 { 298 SCIP_CALL( SCIPfreeSol(scip, &sepadata->sepasol) ); 299 sepadata->triedRelint = FALSE; 300 } 301 } 302 else 303 { 304 /* skip execution, if we unsuccessfully tried to compute a relative interior point */ 305 if ( sepadata->sepasol == NULL && sepadata->triedRelint ) 306 return SCIP_OKAY; 307 } 308 309 /* if relative interior point is not available ... */ 310 if ( sepadata->sepasol == NULL ) 311 { 312 SCIP_Longint nlpiters; 313 SCIP_Real timelimit; 314 int iterlimit; 315 316 /* prepare time limit */ 317 SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) ); 318 if ( ! SCIPisInfinity(scip, timelimit) ) 319 timelimit -= SCIPgetSolvingTime(scip); 320 /* exit if no time left */ 321 if ( timelimit <= 0.0 ) 322 return SCIP_OKAY; 323 324 /* determine iteration limit */ 325 if ( sepadata->maxlpiterfactor < 0.0 || SCIPisInfinity(scip, sepadata->maxlpiterfactor) ) 326 iterlimit = INT_MAX; 327 else 328 { 329 /* determine iteration limit; the number of iterations in the root is only set after its solution, but the 330 * total number of LP iterations is always updated. 331 * here we use SCIPgetDepth instead of the depth argument passed to the callback because if we are not in 332 * the root node but depth is 0 (i.e. if we want us to behave as if we are in the root node regarding 333 * limits) then using the total number of iterations so far is a gross overestimation 334 */ 335 if ( SCIPgetDepth(scip) == 0 ) 336 nlpiters = SCIPgetNLPIterations(scip); 337 else 338 nlpiters = SCIPgetNRootLPIterations(scip); 339 iterlimit = (int)(sepadata->maxlpiterfactor * nlpiters); 340 iterlimit = MAX(iterlimit, SCIP_MIN_LPITERS); 341 assert(iterlimit > 0); 342 } 343 344 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, 0, "Computing relative interior point (time limit: %g, iter limit: %d) ...\n", timelimit, iterlimit); 345 SCIP_CALL( SCIPcomputeLPRelIntPoint(scip, TRUE, sepadata->inclobjcutoff, timelimit, iterlimit, &sepadata->sepasol) ); 346 sepadata->triedRelint = TRUE; 347 } 348 } 349 else 350 { 351 /* get best solution (NULL if not present) */ 352 sepadata->sepasol = SCIPgetBestSol(scip); 353 } 354 355 /* separate close cuts */ 356 if ( sepadata->sepasol != NULL ) 357 { 358 SCIPdebugMsg(scip, "Generating close cuts ... (combination value: %f)\n", sepadata->sepacombvalue); 359 *result = SCIP_DIDNOTFIND; 360 361 /* generate point to be separated */ 362 SCIP_CALL( generateCloseCutPoint(scip, sepadata, &point) ); 363 364 /* apply a separation round to generated point */ 365 if ( point != NULL ) 366 { 367 int noldcuts; 368 SCIP_Bool delayed; 369 SCIP_Bool cutoff; 370 371 noldcuts = SCIPgetNCuts(scip); 372 isroot = (SCIP_Bool) (depth == 0); 373 374 /* separate solution via other separators */ 375 SCIP_CALL( SCIPseparateSol(scip, point, isroot, TRUE, FALSE, &delayed, &cutoff) ); 376 377 SCIP_CALL( SCIPfreeSol(scip, &point) ); 378 assert( point == NULL ); 379 380 /* the cuts might not violated by the current LP if the computed point is strange */ 381 SCIP_CALL( SCIPremoveInefficaciousCuts(scip) ); 382 383 if ( cutoff ) 384 *result = SCIP_CUTOFF; 385 else 386 { 387 if ( SCIPgetNCuts(scip) - noldcuts > sepadata->sepathreshold ) 388 { 389 sepadata->nunsuccessful = 0; 390 *result = SCIP_NEWROUND; 391 } 392 else 393 { 394 if ( SCIPgetNCuts(scip) > noldcuts ) 395 { 396 sepadata->nunsuccessful = 0; 397 *result = SCIP_SEPARATED; 398 } 399 else 400 ++sepadata->nunsuccessful; 401 } 402 } 403 404 SCIPdebugMsg(scip, "Separated close cuts: %d (enoughcuts: %d, unsuccessful: %d).\n", SCIPgetNCuts(scip) - noldcuts, 405 SCIPgetNCuts(scip) - noldcuts > sepadata->sepathreshold, sepadata->nunsuccessful); 406 407 if ( sepadata->maxunsuccessful >= 0 && sepadata->nunsuccessful > sepadata->maxunsuccessful ) 408 { 409 SCIPdebugMsg(scip, "Turn off close cut separation, because of %d unsuccessful calls.\n", sepadata->nunsuccessful); 410 sepadata->discardnode = currentnodenumber; 411 sepadata->nunsuccessful = 0; 412 } 413 } 414 } 415 416 return SCIP_OKAY; 417 } 418 419 420 /* 421 * separator specific interface methods 422 */ 423 424 /** creates the closecuts separator and includes it in SCIP */ 425 SCIP_RETCODE SCIPincludeSepaClosecuts( 426 SCIP* scip /**< SCIP data structure */ 427 ) 428 { 429 SCIP_SEPADATA* sepadata; 430 SCIP_SEPA* sepa; 431 432 /* create closecuts separator data */ 433 SCIP_CALL( SCIPallocBlockMemory(scip, &sepadata) ); 434 sepadata->sepasol = NULL; 435 sepadata->discardnode = -1; 436 sepadata->nunsuccessful = 0; 437 sepadata->triedRelint = FALSE; 438 439 /* include separator */ 440 SCIP_CALL( SCIPincludeSepaBasic(scip, &sepa, SEPA_NAME, SEPA_DESC, SEPA_PRIORITY, SEPA_FREQ, SEPA_MAXBOUNDDIST, SEPA_USESSUBSCIP, SEPA_DELAY, 441 sepaExeclpClosecuts, NULL, sepadata) ); 442 443 assert(sepa != NULL); 444 445 /* set non-NULL pointers to callback methods */ 446 SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyClosecuts) ); 447 SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeClosecuts) ); 448 SCIP_CALL( SCIPsetSepaExitsol(scip, sepa, sepaExitsolClosecuts) ); 449 450 /* add closecuts separator parameters */ 451 SCIP_CALL( SCIPaddBoolParam(scip, 452 "separating/closecuts/separelint", 453 "generate close cuts w.r.t. relative interior point (best solution otherwise)?", 454 &sepadata->separelint, TRUE, SCIP_DEFAULT_SEPARELINT, NULL, NULL) ); 455 456 SCIP_CALL( SCIPaddRealParam(scip, 457 "separating/closecuts/sepacombvalue", 458 "convex combination value for close cuts", 459 &sepadata->sepacombvalue, TRUE, SCIP_DEFAULT_SEPACOMBVALUE, 0.0, 1.0, 460 NULL, NULL) ); 461 462 SCIP_CALL( SCIPaddIntParam(scip, 463 "separating/closecuts/closethres", 464 "threshold on number of generated cuts below which the ordinary separation is started", 465 &sepadata->sepathreshold, TRUE, SCIP_DEFAULT_SEPATHRESHOLD, -1, INT_MAX, NULL, NULL) ); 466 467 SCIP_CALL( SCIPaddBoolParam(scip, 468 "separating/closecuts/inclobjcutoff", 469 "include an objective cutoff when computing the relative interior?", 470 &sepadata->inclobjcutoff, TRUE, SCIP_DEFAULT_INCLOBJCUTOFF, NULL, NULL) ); 471 472 SCIP_CALL( SCIPaddBoolParam(scip, 473 "separating/closecuts/recomputerelint", 474 "recompute relative interior point in each separation call?", 475 &sepadata->recomputerelint, TRUE, SCIP_DEFAULT_RECOMPUTERELINT, NULL, NULL) ); 476 477 SCIP_CALL( SCIPaddIntParam(scip, 478 "separating/closecuts/maxunsuccessful", 479 "turn off separation in current node after unsuccessful calls (-1 never turn off)", 480 &sepadata->maxunsuccessful, TRUE, SCIP_DEFAULT_MAXUNSUCCESSFUL, -1, INT_MAX, NULL, NULL) ); 481 482 SCIP_CALL( SCIPaddRealParam(scip, 483 "separating/closecuts/maxlpiterfactor", 484 "factor for maximal LP iterations in relative interior computation compared to node LP iterations (negative for no limit)", 485 &sepadata->maxlpiterfactor, TRUE, SCIP_DEFAULT_MAXLPITERFACTOR, -1.0, SCIP_REAL_MAX, NULL, NULL) ); 486 487 return SCIP_OKAY; 488 } 489 490 /** sets point to be used as base point for computing the point to be separated 491 * 492 * The point is only stored if separation of relative interior points is used. The solution is copied. 493 */ 494 SCIP_RETCODE SCIPsetBasePointClosecuts( 495 SCIP* scip, /**< SCIP data structure */ 496 SCIP_SOL* sol /**< base point solution */ 497 ) 498 { 499 SCIP_SEPA* sepa; 500 SCIP_SEPADATA* sepadata; 501 502 assert( scip != NULL ); 503 504 /* find separator */ 505 sepa = SCIPfindSepa(scip, SEPA_NAME); 506 if ( sepa == NULL ) 507 { 508 SCIPerrorMessage("Could not find separator <%s>.\n", SEPA_NAME); 509 return SCIP_PLUGINNOTFOUND; 510 } 511 assert( strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0 ); 512 513 /* get sepadata */ 514 sepadata = SCIPsepaGetData(sepa); 515 assert( sepadata != NULL ); 516 517 /* store point if we have to separate relative interior points */ 518 if ( sepadata->separelint ) 519 { 520 /* possibly free solution */ 521 if ( sepadata->sepasol != NULL ) 522 { 523 SCIP_CALL( SCIPfreeSol(scip, &sepadata->sepasol) ); 524 } 525 526 /* copy and store solution */ 527 SCIP_CALL( SCIPcreateSolCopy(scip, &sepadata->sepasol, sol) ); 528 sepadata->triedRelint = TRUE; 529 } 530 531 return SCIP_OKAY; 532 } 533