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 scip_cut.h 26 * @ingroup PUBLICCOREAPI 27 * @brief public methods for cuts and aggregation rows 28 * @author Tobias Achterberg 29 * @author Timo Berthold 30 * @author Thorsten Koch 31 * @author Alexander Martin 32 * @author Marc Pfetsch 33 * @author Kati Wolter 34 * @author Gregor Hendel 35 * @author Leona Gottwald 36 */ 37 38 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 39 40 #ifndef __SCIP_SCIP_CUT_H__ 41 #define __SCIP_SCIP_CUT_H__ 42 43 44 #include "scip/def.h" 45 #include "scip/type_cutpool.h" 46 #include "scip/type_lp.h" 47 #include "scip/type_result.h" 48 #include "scip/type_retcode.h" 49 #include "scip/type_scip.h" 50 #include "scip/type_sol.h" 51 52 #ifdef __cplusplus 53 extern "C" { 54 #endif 55 56 /**@addtogroup PublicCutMethods 57 * 58 * @{ 59 */ 60 61 /** returns row's cutoff distance in the direction of the given primal solution 62 * 63 * @return the cutoff distance of the cut with respect to the LP solution in the direction of the given primal solution 64 * 65 * @pre This method can be called if @p scip is in one of the following stages: 66 * - \ref SCIP_STAGE_SOLVING 67 */ 68 SCIP_EXPORT 69 SCIP_Real SCIPgetCutLPSolCutoffDistance( 70 SCIP* scip, /**< SCIP data structure */ 71 SCIP_SOL* sol, /**< solution to compute direction for cutoff distance; must not be NULL */ 72 SCIP_ROW* cut /**< separated cut */ 73 ); 74 75 /** returns efficacy of the cut with respect to the given primal solution or the current LP solution: 76 * e = -feasibility/norm 77 * 78 * @return the efficacy of the cut with respect to the given primal solution or the current LP solution: 79 * e = -feasibility/norm 80 * 81 * @pre This method can be called if @p scip is in one of the following stages: 82 * - \ref SCIP_STAGE_SOLVING 83 */ 84 SCIP_EXPORT 85 SCIP_Real SCIPgetCutEfficacy( 86 SCIP* scip, /**< SCIP data structure */ 87 SCIP_SOL* sol, /**< primal CIP solution, or NULL for current LP solution */ 88 SCIP_ROW* cut /**< separated cut */ 89 ); 90 91 /** returns whether the cut's efficacy with respect to the given primal solution or the current LP solution is greater 92 * than the minimal cut efficacy 93 * 94 * @return TRUE if the cut's efficacy with respect to the given primal solution or the current LP solution is greater 95 * than the minimal cut efficacy, otherwise FALSE 96 * 97 * @pre This method can be called if @p scip is in one of the following stages: 98 * - \ref SCIP_STAGE_SOLVING 99 */ 100 SCIP_EXPORT 101 SCIP_Bool SCIPisCutEfficacious( 102 SCIP* scip, /**< SCIP data structure */ 103 SCIP_SOL* sol, /**< primal CIP solution, or NULL for current LP solution */ 104 SCIP_ROW* cut /**< separated cut */ 105 ); 106 107 /** checks, if the given cut's efficacy is larger than the minimal cut efficacy 108 * 109 * @return TRUE if the given cut's efficacy is larger than the minimal cut efficacy, otherwise FALSE 110 */ 111 SCIP_EXPORT 112 SCIP_Bool SCIPisEfficacious( 113 SCIP* scip, /**< SCIP data structure */ 114 SCIP_Real efficacy /**< efficacy of the cut */ 115 ); 116 117 /** calculates the efficacy norm of the given vector, which depends on the "separating/efficacynorm" parameter 118 * 119 * @return the efficacy norm of the given vector, which depends on the "separating/efficacynorm" parameter 120 */ 121 SCIP_EXPORT 122 SCIP_Real SCIPgetVectorEfficacyNorm( 123 SCIP* scip, /**< SCIP data structure */ 124 SCIP_Real* vals, /**< array of values */ 125 int nvals /**< number of values */ 126 ); 127 128 /** indicates whether a cut is applicable 129 * 130 * If the cut has only one variable and this method returns FALSE, it may 131 * still be possible that the cut can be added to the LP (as a row instead 132 * of a boundchange), but it will be a very weak cut. The user is asked 133 * to avoid such cuts. 134 * 135 * @pre This method can be called if @p scip is in one of the following stages: 136 * - \ref SCIP_STAGE_SOLVING 137 * 138 * @return whether the cut is modifiable, not a bound change, or a bound change that changes bounds by at least epsilon 139 */ 140 SCIP_EXPORT 141 SCIP_Bool SCIPisCutApplicable( 142 SCIP* scip, /**< SCIP data structure */ 143 SCIP_ROW* cut /**< separated cut */ 144 ); 145 146 /** adds cut to separation storage 147 * 148 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 149 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 150 * 151 * @pre This method can be called if @p scip is in one of the following stages: 152 * - \ref SCIP_STAGE_SOLVING 153 * 154 * @deprecated Please use SCIPaddRow() instead, or, if the row is a global cut and it might be useful to keep it for future use, 155 * consider adding it to the global cutpool with SCIPaddPoolCut(). 156 */ 157 SCIP_DEPRECATED SCIP_EXPORT 158 SCIP_RETCODE SCIPaddCut( 159 SCIP* scip, /**< SCIP data structure */ 160 SCIP_SOL* sol, /**< primal solution that was separated, or NULL for LP solution */ 161 SCIP_ROW* cut, /**< separated cut */ 162 SCIP_Bool forcecut, /**< should the cut be forced to enter the LP? */ 163 SCIP_Bool* infeasible /**< pointer to store whether cut has been detected to be infeasible for local bounds */ 164 ); 165 166 /** adds row to separation storage 167 * 168 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 169 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 170 * 171 * @pre This method can be called if @p scip is in one of the following stages: 172 * - \ref SCIP_STAGE_SOLVING 173 */ 174 SCIP_EXPORT 175 SCIP_RETCODE SCIPaddRow( 176 SCIP* scip, /**< SCIP data structure */ 177 SCIP_ROW* row, /**< row */ 178 SCIP_Bool forcecut, /**< should the row be forced to enter the LP? */ 179 SCIP_Bool* infeasible /**< pointer to store whether row has been detected to be infeasible for local bounds */ 180 ); 181 182 /** checks if cut is already existing in global cutpool 183 * 184 * @return TRUE is returned if the cut is not already existing in the global cutpool, FALSE otherwise 185 * 186 * @pre This method can be called if @p scip is in one of the following stages: 187 * - \ref SCIP_STAGE_SOLVING 188 */ 189 SCIP_EXPORT 190 SCIP_Bool SCIPisCutNew( 191 SCIP* scip, /**< SCIP data structure */ 192 SCIP_ROW* row /**< cutting plane to add */ 193 ); 194 195 /** if not already existing, adds row to global cut pool 196 * 197 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 198 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 199 * 200 * @pre This method can be called if @p scip is in one of the following stages: 201 * - \ref SCIP_STAGE_SOLVING 202 */ 203 SCIP_EXPORT 204 SCIP_RETCODE SCIPaddPoolCut( 205 SCIP* scip, /**< SCIP data structure */ 206 SCIP_ROW* row /**< cutting plane to add */ 207 ); 208 209 /** removes the row from the global cut pool 210 * 211 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 212 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 213 * 214 * @pre This method can be called if @p scip is in one of the following stages: 215 * - \ref SCIP_STAGE_SOLVING 216 */ 217 SCIP_EXPORT 218 SCIP_RETCODE SCIPdelPoolCut( 219 SCIP* scip, /**< SCIP data structure */ 220 SCIP_ROW* row /**< row to remove */ 221 ); 222 223 /** gets current cuts in the global cut pool 224 * 225 * @return the current cuts in the global cut pool 226 * 227 * @pre This method can be called if @p scip is in one of the following stages: 228 * - \ref SCIP_STAGE_SOLVING 229 * - \ref SCIP_STAGE_SOLVED 230 * - \ref SCIP_STAGE_EXITSOLVE 231 */ 232 SCIP_EXPORT 233 SCIP_CUT** SCIPgetPoolCuts( 234 SCIP* scip /**< SCIP data structure */ 235 ); 236 237 /** gets current number of rows in the global cut pool 238 * 239 * @return the current number of rows in the global cut pool 240 * 241 * @pre This method can be called if @p scip is in one of the following stages: 242 * - \ref SCIP_STAGE_SOLVING 243 * - \ref SCIP_STAGE_SOLVED 244 * - \ref SCIP_STAGE_EXITSOLVE 245 */ 246 SCIP_EXPORT 247 int SCIPgetNPoolCuts( 248 SCIP* scip /**< SCIP data structure */ 249 ); 250 251 /** gets the global cut pool used by SCIP 252 * 253 * @return the global cut pool used by SCIP 254 * 255 * @pre This method can be called if @p scip is in one of the following stages: 256 * - \ref SCIP_STAGE_SOLVING 257 * - \ref SCIP_STAGE_SOLVED 258 * - \ref SCIP_STAGE_EXITSOLVE 259 */ 260 SCIP_EXPORT 261 SCIP_CUTPOOL* SCIPgetGlobalCutpool( 262 SCIP* scip /**< SCIP data structure */ 263 ); 264 265 /** creates a cut pool 266 * 267 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 268 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 269 * 270 * @pre This method can be called if @p scip is in one of the following stages: 271 * - \ref SCIP_STAGE_TRANSFORMING 272 * - \ref SCIP_STAGE_TRANSFORMED 273 * - \ref SCIP_STAGE_INITPRESOLVE 274 * - \ref SCIP_STAGE_PRESOLVING 275 * - \ref SCIP_STAGE_EXITPRESOLVE 276 * - \ref SCIP_STAGE_PRESOLVED 277 * - \ref SCIP_STAGE_INITSOLVE 278 * - \ref SCIP_STAGE_SOLVING 279 */ 280 SCIP_EXPORT 281 SCIP_RETCODE SCIPcreateCutpool( 282 SCIP* scip, /**< SCIP data structure */ 283 SCIP_CUTPOOL** cutpool, /**< pointer to store cut pool */ 284 int agelimit /**< maximum age a cut can reach before it is deleted from the pool */ 285 ); 286 287 /** frees a cut pool 288 * 289 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 290 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 291 * 292 * @pre This method can be called if @p scip is in one of the following stages: 293 * - \ref SCIP_STAGE_TRANSFORMING 294 * - \ref SCIP_STAGE_TRANSFORMED 295 * - \ref SCIP_STAGE_INITPRESOLVE 296 * - \ref SCIP_STAGE_PRESOLVING 297 * - \ref SCIP_STAGE_EXITPRESOLVE 298 * - \ref SCIP_STAGE_PRESOLVED 299 * - \ref SCIP_STAGE_INITSOLVE 300 * - \ref SCIP_STAGE_SOLVING 301 * - \ref SCIP_STAGE_SOLVED 302 * - \ref SCIP_STAGE_EXITSOLVE 303 * - \ref SCIP_STAGE_FREETRANS 304 */ 305 SCIP_EXPORT 306 SCIP_RETCODE SCIPfreeCutpool( 307 SCIP* scip, /**< SCIP data structure */ 308 SCIP_CUTPOOL** cutpool /**< pointer to store cut pool */ 309 ); 310 311 /** if not already existing, adds row to a cut pool and captures it 312 * 313 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 314 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 315 * 316 * @pre This method can be called if @p scip is in one of the following stages: 317 * - \ref SCIP_STAGE_INITSOLVE 318 * - \ref SCIP_STAGE_SOLVING 319 */ 320 SCIP_EXPORT 321 SCIP_RETCODE SCIPaddRowCutpool( 322 SCIP* scip, /**< SCIP data structure */ 323 SCIP_CUTPOOL* cutpool, /**< cut pool */ 324 SCIP_ROW* row /**< cutting plane to add */ 325 ); 326 327 /** adds row to a cut pool and captures it; doesn't check for multiple cuts 328 * 329 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 330 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 331 * 332 * @pre This method can be called if @p scip is in one of the following stages: 333 * - \ref SCIP_STAGE_INITSOLVE 334 * - \ref SCIP_STAGE_SOLVING 335 */ 336 SCIP_EXPORT 337 SCIP_RETCODE SCIPaddNewRowCutpool( 338 SCIP* scip, /**< SCIP data structure */ 339 SCIP_CUTPOOL* cutpool, /**< cut pool */ 340 SCIP_ROW* row /**< cutting plane to add */ 341 ); 342 343 /** removes the LP row from a cut pool 344 * 345 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 346 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 347 * 348 * @pre This method can be called if @p scip is in one of the following stages: 349 * - \ref SCIP_STAGE_INITSOLVE 350 * - \ref SCIP_STAGE_SOLVING 351 * - \ref SCIP_STAGE_SOLVED 352 */ 353 SCIP_EXPORT 354 SCIP_RETCODE SCIPdelRowCutpool( 355 SCIP* scip, /**< SCIP data structure */ 356 SCIP_CUTPOOL* cutpool, /**< cut pool */ 357 SCIP_ROW* row /**< row to remove */ 358 ); 359 360 /** separates cuts from a cut pool 361 * 362 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 363 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 364 * 365 * @pre This method can be called if @p scip is in one of the following stages: 366 * - \ref SCIP_STAGE_SOLVING 367 */ 368 SCIP_EXPORT 369 SCIP_RETCODE SCIPseparateCutpool( 370 SCIP* scip, /**< SCIP data structure */ 371 SCIP_CUTPOOL* cutpool, /**< cut pool */ 372 SCIP_RESULT* result /**< pointer to store the result of the separation call */ 373 ); 374 375 /** separates cuts w.r.t. given solution from a cut pool 376 * 377 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 378 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 379 * 380 * @pre This method can be called if @p scip is in one of the following stages: 381 * - \ref SCIP_STAGE_SOLVING 382 */ 383 SCIP_EXPORT 384 SCIP_RETCODE SCIPseparateSolCutpool( 385 SCIP* scip, /**< SCIP data structure */ 386 SCIP_CUTPOOL* cutpool, /**< cut pool */ 387 SCIP_SOL* sol, /**< solution to be separated */ 388 SCIP_Bool pretendroot, /**< should the cut separators be called as if we are at the root node? */ 389 SCIP_RESULT* result /**< pointer to store the result of the separation call */ 390 ); 391 392 /** if not already existing, adds row to the delayed global cut pool 393 * 394 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 395 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 396 * 397 * @pre This method can be called if @p scip is the stages \ref SCIP_STAGE_SOLVING 398 */ 399 SCIP_EXPORT 400 SCIP_RETCODE SCIPaddDelayedPoolCut( 401 SCIP* scip, /**< SCIP data structure */ 402 SCIP_ROW* row /**< cutting plane to add */ 403 ); 404 405 /** removes the row from the delayed global cut pool 406 * 407 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 408 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 409 * 410 * @pre This method can be called if @p scip is the stages \ref SCIP_STAGE_SOLVING 411 */ 412 SCIP_EXPORT 413 SCIP_RETCODE SCIPdelDelayedPoolCut( 414 SCIP* scip, /**< SCIP data structure */ 415 SCIP_ROW* row /**< cutting plane to add */ 416 ); 417 418 /** gets current cuts in the delayed global cut pool 419 * 420 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 421 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 422 * 423 * @pre This method can be called if @p scip is the stages \ref SCIP_STAGE_SOLVING 424 */ 425 SCIP_EXPORT 426 SCIP_CUT** SCIPgetDelayedPoolCuts( 427 SCIP* scip /**< SCIP data structure */ 428 ); 429 430 /** gets current number of rows in the delayed global cut pool 431 * 432 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 433 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 434 * 435 * @pre This method can be called if @p scip is the stages \ref SCIP_STAGE_SOLVING 436 */ 437 SCIP_EXPORT 438 int SCIPgetNDelayedPoolCuts( 439 SCIP* scip /**< SCIP data structure */ 440 ); 441 442 /** gets the delayed global cut pool used by SCIP 443 * 444 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 445 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 446 * 447 * @pre This method can be called if @p scip is the stages \ref SCIP_STAGE_SOLVING 448 */ 449 SCIP_EXPORT 450 SCIP_CUTPOOL* SCIPgetDelayedGlobalCutpool( 451 SCIP* scip /**< SCIP data structure */ 452 ); 453 454 /** separates the given primal solution or the current LP solution by calling the separators and constraint handlers' 455 * separation methods; 456 * the generated cuts are stored in the separation storage and can be accessed with the methods SCIPgetCuts() and 457 * SCIPgetNCuts(); 458 * after evaluating the cuts, you have to call SCIPclearCuts() in order to remove the cuts from the 459 * separation storage; 460 * it is possible to call SCIPseparateSol() multiple times with different solutions and evaluate the found cuts 461 * afterwards 462 * 463 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 464 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 465 * 466 * @pre This method can be called if @p scip is in one of the following stages: 467 * - \ref SCIP_STAGE_SOLVING 468 */ 469 SCIP_EXPORT 470 SCIP_RETCODE SCIPseparateSol( 471 SCIP* scip, /**< SCIP data structure */ 472 SCIP_SOL* sol, /**< primal solution that should be separated, or NULL for LP solution */ 473 SCIP_Bool pretendroot, /**< should the cut separators be called as if we are at the root node? */ 474 SCIP_Bool allowlocal, /**< should the separator be asked to separate local cuts */ 475 SCIP_Bool onlydelayed, /**< should only separators be called that were delayed in the previous round? */ 476 SCIP_Bool* delayed, /**< pointer to store whether a separator was delayed */ 477 SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */ 478 ); 479 480 /** gets the array of cuts currently stored in the separation storage 481 * 482 * @return the array of cuts currently stored in the separation storage 483 * 484 * @pre This method can be called if @p scip is in one of the following stages: 485 * - \ref SCIP_STAGE_PRESOLVED 486 * - \ref SCIP_STAGE_SOLVING 487 * - \ref SCIP_STAGE_SOLVED 488 */ 489 SCIP_EXPORT 490 SCIP_ROW** SCIPgetCuts( 491 SCIP* scip /**< SCIP data structure */ 492 ); 493 494 /** get current number of cuts in the separation storage 495 * 496 * @return the current number of cuts in the separation storage 497 * 498 * @pre This method can be called if @p scip is in one of the following stages: 499 * - \ref SCIP_STAGE_PRESOLVED 500 * - \ref SCIP_STAGE_SOLVING 501 * - \ref SCIP_STAGE_SOLVED 502 */ 503 SCIP_EXPORT 504 int SCIPgetNCuts( 505 SCIP* scip /**< SCIP data structure */ 506 ); 507 508 /** clears the separation storage 509 * 510 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 511 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 512 * 513 * @pre This method can be called if @p scip is in one of the following stages: 514 * - \ref SCIP_STAGE_SOLVING 515 */ 516 SCIP_EXPORT 517 SCIP_RETCODE SCIPclearCuts( 518 SCIP* scip /**< SCIP data structure */ 519 ); 520 521 /** removes cuts that are inefficacious w.r.t. the current LP solution from separation storage without adding the cuts to the LP 522 * 523 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 524 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 525 * 526 * @pre This method can be called if @p scip is in one of the following stages: 527 * - \ref SCIP_STAGE_SOLVING 528 */ 529 SCIP_EXPORT 530 SCIP_RETCODE SCIPremoveInefficaciousCuts( 531 SCIP* scip /**< SCIP data structure */ 532 ); 533 534 /**@} */ 535 536 #ifdef __cplusplus 537 } 538 #endif 539 540 #endif 541