Scippy

SCIP

Solving Constraint Integer Programs

scip_cut.c
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the program and library */
4/* SCIP --- Solving Constraint Integer Programs */
5/* */
6/* Copyright (c) 2002-2024 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.c
26 * @ingroup OTHER_CFILES
27 * @brief public methods for cuts and aggregation rows
28 * @author Tobias Achterberg
29 * @author Timo Berthold
30 * @author Gerald Gamrath
31 * @author Leona Gottwald
32 * @author Stefan Heinz
33 * @author Gregor Hendel
34 * @author Thorsten Koch
35 * @author Alexander Martin
36 * @author Marc Pfetsch
37 * @author Michael Winkler
38 * @author Kati Wolter
39 *
40 * @todo check all SCIP_STAGE_* switches, and include the new stages TRANSFORMED and INITSOLVE
41 */
42
43/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
44
45#include "scip/cutpool.h"
46#include "scip/debug.h"
47#include "scip/lp.h"
48#include "scip/prob.h"
49#include "scip/pub_cutpool.h"
50#include "scip/pub_lp.h"
51#include "scip/pub_message.h"
52#include "scip/scip_conflict.h"
53#include "scip/scip_cut.h"
54#include "scip/scip_numerics.h"
55#include "scip/scip_tree.h"
56#include "scip/sepastore.h"
57#include "scip/set.h"
58#include "scip/solve.h"
59#include "scip/struct_lp.h"
60#include "scip/struct_mem.h"
61#include "scip/struct_scip.h"
62#include "scip/struct_set.h"
63#include "scip/tree.h"
64
65/** returns row's cutoff distance in the direction of the given primal solution
66 *
67 * @return the cutoff distance of the cut with respect to the LP solution in the direction of the given primal solution
68 *
69 * @pre This method can be called if @p scip is in one of the following stages:
70 * - \ref SCIP_STAGE_SOLVING
71 */
73 SCIP* scip, /**< SCIP data structure */
74 SCIP_SOL* sol, /**< solution to compute direction for cutoff distance; must not be NULL */
75 SCIP_ROW* cut /**< separated cut */
76 )
77{
78 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetCutLPSolCutoffDistance", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
79
80 assert(sol != NULL);
81
82 return SCIProwGetLPSolCutoffDistance(cut, scip->set, scip->stat, sol, scip->lp);
83}
84
85/** returns efficacy of the cut with respect to the given primal solution or the current LP solution:
86 * e = -feasibility/norm
87 *
88 * @return the efficacy of the cut with respect to the given primal solution or the current LP solution:
89 * e = -feasibility/norm
90 *
91 * @pre This method can be called if @p scip is in one of the following stages:
92 * - \ref SCIP_STAGE_SOLVING
93 */
95 SCIP* scip, /**< SCIP data structure */
96 SCIP_SOL* sol, /**< primal CIP solution, or NULL for current LP solution */
97 SCIP_ROW* cut /**< separated cut */
98 )
99{
101
102 if( sol == NULL )
103 return SCIProwGetLPEfficacy(cut, scip->set, scip->stat, scip->lp);
104 else
105 return SCIProwGetSolEfficacy(cut, scip->set, scip->stat, sol);
106}
107
108/** returns whether the cut's efficacy with respect to the given primal solution or the current LP solution is greater
109 * than the minimal cut efficacy
110 *
111 * @return TRUE if the cut's efficacy with respect to the given primal solution or the current LP solution is greater
112 * than the minimal cut efficacy, otherwise FALSE
113 *
114 * @pre This method can be called if @p scip is in one of the following stages:
115 * - \ref SCIP_STAGE_SOLVING
116 */
118 SCIP* scip, /**< SCIP data structure */
119 SCIP_SOL* sol, /**< primal CIP solution, or NULL for current LP solution */
120 SCIP_ROW* cut /**< separated cut */
121 )
122{
124
125 if( sol == NULL )
126 return SCIProwIsLPEfficacious(cut, scip->set, scip->stat, scip->lp, (SCIPtreeGetCurrentDepth(scip->tree) == 0));
127 else
128 return SCIProwIsSolEfficacious(cut, scip->set, scip->stat, sol, (SCIPtreeGetCurrentDepth(scip->tree) == 0));
129}
130
131/** checks, if the given cut's efficacy is larger than the minimal cut efficacy
132 *
133 * @return TRUE if the given cut's efficacy is larger than the minimal cut efficacy, otherwise FALSE
134 */
136 SCIP* scip, /**< SCIP data structure */
137 SCIP_Real efficacy /**< efficacy of the cut */
138 )
139{
140 assert(scip != NULL);
141
142 return SCIPsetIsEfficacious(scip->set, (SCIPtreeGetCurrentDepth(scip->tree) == 0), efficacy);
143}
144
145/** calculates the efficacy norm of the given vector, which depends on the "separating/efficacynorm" parameter
146 *
147 * @return the efficacy norm of the given vector, which depends on the "separating/efficacynorm" parameter
148 */
150 SCIP* scip, /**< SCIP data structure */
151 SCIP_Real* vals, /**< array of values */
152 int nvals /**< number of values */
153 )
154{
155 SCIP_Real norm;
156 int i;
157
158 assert(scip != NULL);
159 assert(scip->set != NULL);
160
161 norm = 0.0;
162 switch( scip->set->sepa_efficacynorm )
163 {
164 case 'e':
165 for( i = 0; i < nvals; ++i )
166 norm += SQR(vals[i]);
167 norm = sqrt(norm);
168 break;
169 case 'm':
170 for( i = 0; i < nvals; ++i )
171 {
172 SCIP_Real absval;
173
174 absval = REALABS(vals[i]);
175 norm = MAX(norm, absval);
176 }
177 break;
178 case 's':
179 for( i = 0; i < nvals; ++i )
180 norm += REALABS(vals[i]);
181 break;
182 case 'd':
183 for( i = 0; i < nvals; ++i )
184 {
185 if( !SCIPisZero(scip, vals[i]) )
186 {
187 norm = 1.0;
188 break;
189 }
190 }
191 break;
192 default:
193 SCIPerrorMessage("invalid efficacy norm parameter '%c'\n", scip->set->sepa_efficacynorm);
194 assert(FALSE); /*lint !e506*/
195 }
196
197 return norm;
198}
199
200/** indicates whether a cut is applicable, i.e., will modify the LP when applied
201 *
202 * @pre This method can be called if @p scip is in one of the following stages:
203 * - \ref SCIP_STAGE_SOLVING
204 *
205 * @return whether the cut is modifiable, not a bound change, or a bound change that changes bounds by at least epsilon
206 */
208 SCIP* scip, /**< SCIP data structure */
209 SCIP_ROW* cut /**< separated cut */
210 )
211{
213
214 return SCIPsepastoreIsCutApplicable(scip->set, cut);
215}
216
217/** adds cut to separation storage
218 *
219 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
220 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
221 *
222 * @pre This method can be called if @p scip is in one of the following stages:
223 * - \ref SCIP_STAGE_SOLVING
224 *
225 * @deprecated Please use SCIPaddRow() instead, or, if the row is a global cut, add it only to the global cutpool.
226 */
228 SCIP* scip, /**< SCIP data structure */
229 SCIP_SOL* sol, /**< primal solution that was separated, or NULL for LP solution */
230 SCIP_ROW* cut, /**< separated cut */
231 SCIP_Bool forcecut, /**< should the cut be forced to enter the LP? */
232 SCIP_Bool* infeasible /**< pointer to store whether cut has been detected to be infeasible for local bounds */
233 )
234{
236
237 SCIP_UNUSED(sol);
238
239 return SCIPaddRow(scip, cut, forcecut, infeasible);
240}
241
242/** adds row to separation storage
243 *
244 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
245 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
246 *
247 * @pre This method can be called if @p scip is in one of the following stages:
248 * - \ref SCIP_STAGE_SOLVING
249 */
251 SCIP* scip, /**< SCIP data structure */
252 SCIP_ROW* row, /**< row */
253 SCIP_Bool forcecut, /**< should the row be forced to enter the LP? */
254 SCIP_Bool* infeasible /**< pointer to store whether row has been detected to be infeasible for local bounds */
255 )
256{
258
259 assert(SCIPtreeGetCurrentNode(scip->tree) != NULL);
260
261 SCIP_CALL( SCIPsepastoreAddCut(scip->sepastore, scip->mem->probmem, scip->set, scip->stat, scip->eventqueue,
262 scip->eventfilter, scip->lp, row, forcecut, (SCIPtreeGetCurrentDepth(scip->tree) == 0), infeasible) );
263
264 /* possibly run conflict analysis */
265 if ( *infeasible && SCIPprobAllColsInLP(scip->transprob, scip->set, scip->lp) && SCIPisConflictAnalysisApplicable(scip) )
266 {
267 SCIP_Real act;
268 SCIP_VAR* var;
269 SCIP_Real val;
270 int ncols;
271 int j;
272
273 /* initialize conflict analysis */
275
276 if ( ! SCIPisInfinity(scip, -row->lhs) )
277 {
278 act = SCIProwGetMaxActivity(row, scip->set, scip->stat);
279 if ( SCIPisLT(scip, act, row->lhs) )
280 {
281 ncols = SCIProwGetNNonz(row);
282 for (j = 0; j < ncols; ++j)
283 {
284 val = row->vals[j];
285 if ( ! SCIPisZero(scip, val) )
286 {
287 var = SCIPcolGetVar(row->cols[j]);
288 assert( var != NULL );
289
290 if ( val > 0.0 )
291 {
293 }
294 else
295 {
297 }
298 }
299 }
300 }
301 }
302 else if ( ! SCIPisInfinity(scip, row->rhs) )
303 {
304 act = SCIProwGetMinActivity(row, scip->set, scip->stat);
305 if ( SCIPisGT(scip, act, row->rhs) )
306 {
307 ncols = SCIProwGetNNonz(row);
308 for (j = 0; j < ncols; ++j)
309 {
310 val = row->vals[j];
311 if ( ! SCIPisZero(scip, val) )
312 {
313 var = SCIPcolGetVar(row->cols[j]);
314 assert( var != NULL );
315
316 if ( val > 0.0 )
317 {
319 }
320 else
321 {
323 }
324 }
325 }
326 }
327 }
328
329 /* analyze the conflict */
331 }
332
333 return SCIP_OKAY;
334}
335
336/** checks if cut is already existing in global cutpool
337 *
338 * @return TRUE is returned if the cut is not already existing in the global cutpool, FALSE otherwise
339 *
340 * @pre This method can be called if @p scip is in one of the following stages:
341 * - \ref SCIP_STAGE_SOLVING
342 */
344 SCIP* scip, /**< SCIP data structure */
345 SCIP_ROW* row /**< cutting plane to add */
346 )
347{
349
350 return SCIPcutpoolIsCutNew(scip->cutpool, scip->set, row);
351}
352
353/** if not already existing, adds row to global cut pool
354 *
355 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
356 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
357 *
358 * @pre This method can be called if @p scip is in one of the following stages:
359 * - \ref SCIP_STAGE_SOLVING
360 */
362 SCIP* scip, /**< SCIP data structure */
363 SCIP_ROW* row /**< row to remove */
364 )
365{
367
368 SCIP_CALL( SCIPcutpoolAddRow(scip->cutpool, scip->mem->probmem, scip->set, scip->stat, scip->lp, row) );
369
370 return SCIP_OKAY;
371}
372
373/** removes the row from the global cut pool
374 *
375 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
376 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
377 *
378 * @pre This method can be called if @p scip is in one of the following stages:
379 * - \ref SCIP_STAGE_SOLVING
380 */
382 SCIP* scip, /**< SCIP data structure */
383 SCIP_ROW* row /**< cutting plane to add */
384 )
385{
387
388 SCIP_CALL( SCIPcutpoolDelRow(scip->cutpool, scip->mem->probmem, scip->set, scip->stat, scip->lp, row) );
389
390 return SCIP_OKAY;
391}
392
393/** gets current cuts in the global cut pool
394 *
395 * @return the current cuts in the global cut pool
396 *
397 * @pre This method can be called if @p scip is in one of the following stages:
398 * - \ref SCIP_STAGE_SOLVING
399 * - \ref SCIP_STAGE_SOLVED
400 * - \ref SCIP_STAGE_EXITSOLVE
401 */
403 SCIP* scip /**< SCIP data structure */
404 )
405{
407
408 return SCIPcutpoolGetCuts(scip->cutpool);
409}
410
411/** gets current number of rows in the global cut pool
412 *
413 * @return the current number of rows in the global cut pool
414 *
415 * @pre This method can be called if @p scip is in one of the following stages:
416 * - \ref SCIP_STAGE_SOLVING
417 * - \ref SCIP_STAGE_SOLVED
418 * - \ref SCIP_STAGE_EXITSOLVE
419 */
421 SCIP* scip /**< SCIP data structure */
422 )
423{
425
426 return SCIPcutpoolGetNCuts(scip->cutpool);
427}
428
429/** gets the global cut pool used by SCIP
430 *
431 * @return the global cut pool used by SCIP
432 *
433 * @pre This method can be called if @p scip is in one of the following stages:
434 * - \ref SCIP_STAGE_SOLVING
435 * - \ref SCIP_STAGE_SOLVED
436 * - \ref SCIP_STAGE_EXITSOLVE
437 */
439 SCIP* scip /**< SCIP data structure */
440 )
441{
443
444 return scip->cutpool;
445}
446
447/** creates a cut pool
448 *
449 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
450 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
451 *
452 * @pre This method can be called if @p scip is in one of the following stages:
453 * - \ref SCIP_STAGE_TRANSFORMING
454 * - \ref SCIP_STAGE_TRANSFORMED
455 * - \ref SCIP_STAGE_INITPRESOLVE
456 * - \ref SCIP_STAGE_PRESOLVING
457 * - \ref SCIP_STAGE_EXITPRESOLVE
458 * - \ref SCIP_STAGE_PRESOLVED
459 * - \ref SCIP_STAGE_INITSOLVE
460 * - \ref SCIP_STAGE_SOLVING
461 */
463 SCIP* scip, /**< SCIP data structure */
464 SCIP_CUTPOOL** cutpool, /**< pointer to store cut pool */
465 int agelimit /**< maximum age a cut can reach before it is deleted from the pool */
466 )
467{
468 SCIP_CALL( SCIPcheckStage(scip, "SCIPcreateCutpool", FALSE, FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE) );
469
470 SCIP_CALL( SCIPcutpoolCreate(cutpool, scip->mem->probmem, scip->set, agelimit, FALSE) );
471
472 return SCIP_OKAY;
473}
474
475/** frees a cut pool
476 *
477 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
478 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
479 *
480 * @pre This method can be called if @p scip is in one of the following stages:
481 * - \ref SCIP_STAGE_TRANSFORMING
482 * - \ref SCIP_STAGE_TRANSFORMED
483 * - \ref SCIP_STAGE_INITPRESOLVE
484 * - \ref SCIP_STAGE_PRESOLVING
485 * - \ref SCIP_STAGE_EXITPRESOLVE
486 * - \ref SCIP_STAGE_PRESOLVED
487 * - \ref SCIP_STAGE_INITSOLVE
488 * - \ref SCIP_STAGE_SOLVING
489 * - \ref SCIP_STAGE_SOLVED
490 * - \ref SCIP_STAGE_EXITSOLVE
491 * - \ref SCIP_STAGE_FREETRANS
492 */
494 SCIP* scip, /**< SCIP data structure */
495 SCIP_CUTPOOL** cutpool /**< pointer to store cut pool */
496 )
497{
498 SCIP_CALL( SCIPcheckStage(scip, "SCIPfreeCutpool", FALSE, FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE) );
499
500 SCIP_CALL( SCIPcutpoolFree(cutpool, scip->mem->probmem, scip->set, scip->lp) );
501
502 return SCIP_OKAY;
503}
504
505/** if not already existing, adds row to a cut pool and captures it
506 *
507 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
508 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
509 *
510 * @pre This method can be called if @p scip is in one of the following stages:
511 * - \ref SCIP_STAGE_INITSOLVE
512 * - \ref SCIP_STAGE_SOLVING
513 */
515 SCIP* scip, /**< SCIP data structure */
516 SCIP_CUTPOOL* cutpool, /**< cut pool */
517 SCIP_ROW* row /**< cutting plane to add */
518 )
519{
521
522 SCIP_CALL( SCIPcutpoolAddRow(cutpool, scip->mem->probmem, scip->set, scip->stat, scip->lp, row) );
523
524 return SCIP_OKAY;
525}
526
527/** adds row to a cut pool and captures it; doesn't check for multiple cuts
528 *
529 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
530 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
531 *
532 * @pre This method can be called if @p scip is in one of the following stages:
533 * - \ref SCIP_STAGE_INITSOLVE
534 * - \ref SCIP_STAGE_SOLVING
535 */
537 SCIP* scip, /**< SCIP data structure */
538 SCIP_CUTPOOL* cutpool, /**< cut pool */
539 SCIP_ROW* row /**< cutting plane to add */
540 )
541{
542 SCIP_CALL( SCIPcheckStage(scip, "SCIPaddNewRowCutpool", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE) );
543
544 SCIP_CALL( SCIPcutpoolAddNewRow(cutpool, scip->mem->probmem, scip->set, scip->stat, scip->lp, row) );
545
546 return SCIP_OKAY;
547}
548
549/** removes the LP row from a cut pool
550 *
551 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
552 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
553 *
554 * @pre This method can be called if @p scip is in one of the following stages:
555 * - \ref SCIP_STAGE_INITSOLVE
556 * - \ref SCIP_STAGE_SOLVING
557 * - \ref SCIP_STAGE_SOLVED
558 */
560 SCIP* scip, /**< SCIP data structure */
561 SCIP_CUTPOOL* cutpool, /**< cut pool */
562 SCIP_ROW* row /**< row to remove */
563 )
564{
566
567 SCIP_CALL( SCIPcutpoolDelRow(cutpool, scip->mem->probmem, scip->set, scip->stat, scip->lp, row) );
568
569 return SCIP_OKAY;
570}
571
572/** separates cuts from a cut pool
573 *
574 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
575 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
576 *
577 * @pre This method can be called if @p scip is in one of the following stages:
578 * - \ref SCIP_STAGE_SOLVING
579 */
581 SCIP* scip, /**< SCIP data structure */
582 SCIP_CUTPOOL* cutpool, /**< cut pool */
583 SCIP_RESULT* result /**< pointer to store the result of the separation call */
584 )
585{
587
588 assert(SCIPtreeGetCurrentNode(scip->tree) != NULL);
589
590 if( !SCIPtreeHasCurrentNodeLP(scip->tree) )
591 {
592 SCIPerrorMessage("cannot add cuts, because node LP is not processed\n");
593 return SCIP_INVALIDCALL;
594 }
595
596 SCIP_CALL( SCIPcutpoolSeparate(cutpool, scip->mem->probmem, scip->set, scip->stat, scip->eventqueue, scip->eventfilter,
597 scip->lp, scip->sepastore, NULL, FALSE, (SCIPtreeGetCurrentDepth(scip->tree) == 0), result) );
598
599 return SCIP_OKAY;
600}
601
602/** separates cuts w.r.t. given solution from a cut pool
603 *
604 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
605 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
606 *
607 * @pre This method can be called if @p scip is in one of the following stages:
608 * - \ref SCIP_STAGE_SOLVING
609 */
611 SCIP* scip, /**< SCIP data structure */
612 SCIP_CUTPOOL* cutpool, /**< cut pool */
613 SCIP_SOL* sol, /**< solution to be separated */
614 SCIP_Bool pretendroot, /**< should the cut separators be called as if we are at the root node? */
615 SCIP_RESULT* result /**< pointer to store the result of the separation call */
616 )
617{
618 SCIP_CALL( SCIPcheckStage(scip, "SCIPseparateSolCutpool", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
619
620 assert(SCIPtreeGetCurrentNode(scip->tree) != NULL);
621
622 if( !SCIPtreeHasCurrentNodeLP(scip->tree) )
623 {
624 SCIPerrorMessage("cannot add cuts, because node LP is not processed\n");
625 return SCIP_INVALIDCALL;
626 }
627
628 SCIP_CALL( SCIPcutpoolSeparate(cutpool, scip->mem->probmem, scip->set, scip->stat, scip->eventqueue, scip->eventfilter,
629 scip->lp, scip->sepastore, sol, FALSE, pretendroot, result) );
630
631 return SCIP_OKAY;
632}
633
634/** if not already existing, adds row to delayed global cut pool
635 *
636 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
637 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
638 *
639 * @pre This method can be called if @p scip is the stages \ref SCIP_STAGE_SOLVING
640 */
642 SCIP* scip, /**< SCIP data structure */
643 SCIP_ROW* row /**< cutting plane to add */
644 )
645{
646 SCIP_CALL( SCIPcheckStage(scip, "SCIPaddDelayedPoolCut", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
647
648 SCIP_CALL( SCIPcutpoolAddRow(scip->delayedcutpool, scip->mem->probmem, scip->set, scip->stat, scip->lp, row) );
649
650 return SCIP_OKAY;
651}
652
653/** removes the row from the delayed global cut pool
654 *
655 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
656 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
657 *
658 * @pre This method can be called if @p scip is the stages \ref SCIP_STAGE_SOLVING
659 */
661 SCIP* scip, /**< SCIP data structure */
662 SCIP_ROW* row /**< cutting plane to add */
663 )
664{
665 SCIP_CALL( SCIPcheckStage(scip, "SCIPdelDelayedPoolCut", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
666
667 SCIP_CALL( SCIPcutpoolDelRow(scip->delayedcutpool, scip->mem->probmem, scip->set, scip->stat, scip->lp, row) );
668
669 return SCIP_OKAY;
670}
671
672/** gets current cuts in the delayed global cut pool
673 *
674 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
675 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
676 *
677 * @pre This method can be called if @p scip is the stages \ref SCIP_STAGE_SOLVING
678 */
680 SCIP* scip /**< SCIP data structure */
681 )
682{
684
685 return SCIPcutpoolGetCuts(scip->delayedcutpool);
686}
687
688/** gets current number of rows in the delayed global cut pool
689 *
690 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
691 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
692 *
693 * @pre This method can be called if @p scip is the stages \ref SCIP_STAGE_SOLVING
694 */
696 SCIP* scip /**< SCIP data structure */
697 )
698{
699 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNDelayedPoolCuts", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, FALSE, FALSE) );
700
701 return SCIPcutpoolGetNCuts(scip->delayedcutpool);
702}
703
704/** gets the delayed global cut pool used by SCIP
705 *
706 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
707 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
708 *
709 * @pre This method can be called if @p scip is the stages \ref SCIP_STAGE_SOLVING
710 */
712 SCIP* scip /**< SCIP data structure */
713 )
714{
715 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetDelayedGlobalCutpool", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, FALSE, FALSE) );
716
717 return scip->delayedcutpool;
718}
719
720/** separates the given primal solution or the current LP solution by calling the separators and constraint handlers'
721 * separation methods;
722 * the generated cuts are stored in the separation storage and can be accessed with the methods SCIPgetCuts() and
723 * SCIPgetNCuts();
724 * after evaluating the cuts, you have to call SCIPclearCuts() in order to remove the cuts from the
725 * separation storage;
726 * it is possible to call SCIPseparateSol() multiple times with different solutions and evaluate the found cuts
727 * afterwards
728 *
729 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
730 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
731 *
732 * @pre This method can be called if @p scip is in one of the following stages:
733 * - \ref SCIP_STAGE_SOLVING
734 */
736 SCIP* scip, /**< SCIP data structure */
737 SCIP_SOL* sol, /**< primal solution that should be separated, or NULL for LP solution */
738 SCIP_Bool pretendroot, /**< should the cut separators be called as if we are at the root node? */
739 SCIP_Bool allowlocal, /**< should the separator be asked to separate local cuts */
740 SCIP_Bool onlydelayed, /**< should only separators be called that were delayed in the previous round? */
741 SCIP_Bool* delayed, /**< pointer to store whether a separator was delayed */
742 SCIP_Bool* cutoff /**< pointer to store whether the node can be cut off */
743 )
744{
745 int actdepth;
746
748
749 /* get current depth */
750 actdepth = (pretendroot ? 0 : SCIPtreeGetCurrentDepth(scip->tree));
751
752 /* apply separation round */
753 SCIP_CALL( SCIPseparationRound(scip->mem->probmem, scip->set, scip->messagehdlr, scip->stat, scip->eventqueue,
754 scip->eventfilter, scip->transprob, scip->primal, scip->tree, scip->lp, scip->sepastore,
755 sol, actdepth, allowlocal, onlydelayed, delayed, cutoff) );
756
757 return SCIP_OKAY;
758}
759
760/** gets the array of cuts currently stored in the separation storage
761 *
762 * @return the array of cuts currently stored in the separation storage
763 *
764 * @pre This method can be called if @p scip is in one of the following stages:
765 * - \ref SCIP_STAGE_PRESOLVED
766 * - \ref SCIP_STAGE_SOLVING
767 * - \ref SCIP_STAGE_SOLVED
768 */
770 SCIP* scip /**< SCIP data structure */
771 )
772{
774
775 return SCIPsepastoreGetCuts(scip->sepastore);
776}
777
778/** get current number of cuts in the separation storage
779 *
780 * @return the current number of cuts in the separation storage
781 *
782 * @pre This method can be called if @p scip is in one of the following stages:
783 * - \ref SCIP_STAGE_PRESOLVED
784 * - \ref SCIP_STAGE_SOLVING
785 * - \ref SCIP_STAGE_SOLVED
786 */
788 SCIP* scip /**< SCIP data structure */
789 )
790{
792
793 return SCIPsepastoreGetNCuts(scip->sepastore);
794}
795
796/** clears the separation storage
797 *
798 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
799 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
800 *
801 * @pre This method can be called if @p scip is in one of the following stages:
802 * - \ref SCIP_STAGE_SOLVING
803 */
805 SCIP* scip /**< SCIP data structure */
806 )
807{
809
810 SCIP_CALL( SCIPsepastoreClearCuts(scip->sepastore, scip->mem->probmem, scip->set, scip->eventqueue, scip->eventfilter, scip->lp) );
811
812 return SCIP_OKAY;
813}
814
815/** removes cuts that are inefficacious w.r.t. the current LP solution from separation storage without adding the cuts to the LP
816 *
817 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
818 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
819 *
820 * @pre This method can be called if @p scip is in one of the following stages:
821 * - \ref SCIP_STAGE_SOLVING
822 */
824 SCIP* scip /**< SCIP data structure */
825 )
826{
827 SCIP_Bool isroot = FALSE;
828
829 SCIP_CALL( SCIPcheckStage(scip, "SCIPremoveInefficaciousCuts", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
830
831 if( SCIPtreeGetCurrentDepth(scip->tree) == 0 )
832 isroot = TRUE;
833
834 SCIP_CALL( SCIPsepastoreRemoveInefficaciousCuts(scip->sepastore, scip->mem->probmem, scip->set, scip->stat,
835 scip->eventqueue, scip->eventfilter, scip->lp, isroot, SCIP_EFFICIACYCHOICE_LP) );
836
837 return SCIP_OKAY;
838}
SCIP_RETCODE SCIPcutpoolSeparate(SCIP_CUTPOOL *cutpool, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_LP *lp, SCIP_SEPASTORE *sepastore, SCIP_SOL *sol, SCIP_Bool cutpoolisdelayed, SCIP_Bool root, SCIP_RESULT *result)
Definition: cutpool.c:835
SCIP_RETCODE SCIPcutpoolDelRow(SCIP_CUTPOOL *cutpool, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_LP *lp, SCIP_ROW *row)
Definition: cutpool.c:806
SCIP_RETCODE SCIPcutpoolCreate(SCIP_CUTPOOL **cutpool, BMS_BLKMEM *blkmem, SCIP_SET *set, int agelimit, SCIP_Bool globalcutpool)
Definition: cutpool.c:427
SCIP_RETCODE SCIPcutpoolAddRow(SCIP_CUTPOOL *cutpool, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_LP *lp, SCIP_ROW *row)
Definition: cutpool.c:656
SCIP_RETCODE SCIPcutpoolAddNewRow(SCIP_CUTPOOL *cutpool, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_LP *lp, SCIP_ROW *row)
Definition: cutpool.c:733
SCIP_RETCODE SCIPcutpoolFree(SCIP_CUTPOOL **cutpool, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_LP *lp)
Definition: cutpool.c:468
SCIP_Bool SCIPcutpoolIsCutNew(SCIP_CUTPOOL *cutpool, SCIP_SET *set, SCIP_ROW *row)
Definition: cutpool.c:593
internal methods for storing cuts in a cut pool
SCIP_RETCODE SCIPcheckStage(SCIP *scip, const char *method, SCIP_Bool init, SCIP_Bool problem, SCIP_Bool transforming, SCIP_Bool transformed, SCIP_Bool initpresolve, SCIP_Bool presolving, SCIP_Bool exitpresolve, SCIP_Bool presolved, SCIP_Bool initsolve, SCIP_Bool solving, SCIP_Bool solved, SCIP_Bool exitsolve, SCIP_Bool freetrans, SCIP_Bool freescip)
Definition: debug.c:2208
methods for debugging
#define NULL
Definition: def.h:267
#define SCIP_UNUSED(x)
Definition: def.h:428
#define SCIP_Bool
Definition: def.h:91
#define SCIP_Real
Definition: def.h:173
#define SQR(x)
Definition: def.h:214
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define MAX(x, y)
Definition: def.h:239
#define SCIP_CALL_ABORT(x)
Definition: def.h:353
#define REALABS(x)
Definition: def.h:197
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:17042
SCIP_RETCODE SCIPaddConflictLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
SCIP_RETCODE SCIPaddConflictUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
SCIP_RETCODE SCIPanalyzeConflict(SCIP *scip, int validdepth, SCIP_Bool *success)
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
SCIP_RETCODE SCIPseparateSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool pretendroot, SCIP_Bool allowlocal, SCIP_Bool onlydelayed, SCIP_Bool *delayed, SCIP_Bool *cutoff)
Definition: scip_cut.c:735
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
Definition: scip_cut.c:361
SCIP_Real SCIPgetCutEfficacy(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip_cut.c:94
SCIP_CUT ** SCIPcutpoolGetCuts(SCIP_CUTPOOL *cutpool)
Definition: cutpool.c:1075
SCIP_RETCODE SCIPdelDelayedPoolCut(SCIP *scip, SCIP_ROW *row)
Definition: scip_cut.c:660
SCIP_Real SCIPgetCutLPSolCutoffDistance(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip_cut.c:72
SCIP_RETCODE SCIPdelRowCutpool(SCIP *scip, SCIP_CUTPOOL *cutpool, SCIP_ROW *row)
Definition: scip_cut.c:559
SCIP_RETCODE SCIPremoveInefficaciousCuts(SCIP *scip)
Definition: scip_cut.c:823
SCIP_RETCODE SCIPseparateCutpool(SCIP *scip, SCIP_CUTPOOL *cutpool, SCIP_RESULT *result)
Definition: scip_cut.c:580
SCIP_RETCODE SCIPaddCut(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:227
SCIP_CUT ** SCIPgetDelayedPoolCuts(SCIP *scip)
Definition: scip_cut.c:679
SCIP_RETCODE SCIPaddRowCutpool(SCIP *scip, SCIP_CUTPOOL *cutpool, SCIP_ROW *row)
Definition: scip_cut.c:514
SCIP_Bool SCIPisCutNew(SCIP *scip, SCIP_ROW *row)
Definition: scip_cut.c:343
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip_cut.c:117
SCIP_CUTPOOL * SCIPgetGlobalCutpool(SCIP *scip)
Definition: scip_cut.c:438
SCIP_RETCODE SCIPseparateSolCutpool(SCIP *scip, SCIP_CUTPOOL *cutpool, SCIP_SOL *sol, SCIP_Bool pretendroot, SCIP_RESULT *result)
Definition: scip_cut.c:610
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
Definition: scip_cut.c:135
SCIP_Bool SCIPisCutApplicable(SCIP *scip, SCIP_ROW *cut)
Definition: scip_cut.c:207
SCIP_CUTPOOL * SCIPgetDelayedGlobalCutpool(SCIP *scip)
Definition: scip_cut.c:711
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:250
int SCIPgetNPoolCuts(SCIP *scip)
Definition: scip_cut.c:420
int SCIPcutpoolGetNCuts(SCIP_CUTPOOL *cutpool)
Definition: cutpool.c:1085
SCIP_ROW ** SCIPgetCuts(SCIP *scip)
Definition: scip_cut.c:769
SCIP_CUT ** SCIPgetPoolCuts(SCIP *scip)
Definition: scip_cut.c:402
SCIP_RETCODE SCIPclearCuts(SCIP *scip)
Definition: scip_cut.c:804
SCIP_RETCODE SCIPcreateCutpool(SCIP *scip, SCIP_CUTPOOL **cutpool, int agelimit)
Definition: scip_cut.c:462
SCIP_Real SCIPgetVectorEfficacyNorm(SCIP *scip, SCIP_Real *vals, int nvals)
Definition: scip_cut.c:149
int SCIPgetNDelayedPoolCuts(SCIP *scip)
Definition: scip_cut.c:695
int SCIPgetNCuts(SCIP *scip)
Definition: scip_cut.c:787
SCIP_RETCODE SCIPdelPoolCut(SCIP *scip, SCIP_ROW *row)
Definition: scip_cut.c:381
SCIP_RETCODE SCIPfreeCutpool(SCIP *scip, SCIP_CUTPOOL **cutpool)
Definition: scip_cut.c:493
SCIP_RETCODE SCIPaddNewRowCutpool(SCIP *scip, SCIP_CUTPOOL *cutpool, SCIP_ROW *row)
Definition: scip_cut.c:536
SCIP_RETCODE SCIPaddDelayedPoolCut(SCIP *scip, SCIP_ROW *row)
Definition: scip_cut.c:641
int SCIProwGetNNonz(SCIP_ROW *row)
Definition: lp.c:17213
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:670
SCIP_Real SCIProwGetMaxActivity(SCIP_ROW *row, SCIP_SET *set, SCIP_STAT *stat)
Definition: lp.c:6619
SCIP_Bool SCIProwIsLPEfficacious(SCIP_ROW *row, SCIP_SET *set, SCIP_STAT *stat, SCIP_LP *lp, SCIP_Bool root)
Definition: lp.c:6849
SCIP_Real SCIProwGetSolEfficacy(SCIP_ROW *row, SCIP_SET *set, SCIP_STAT *stat, SCIP_SOL *sol)
Definition: lp.c:6865
SCIP_Real SCIProwGetLPSolCutoffDistance(SCIP_ROW *row, SCIP_SET *set, SCIP_STAT *stat, SCIP_SOL *sol, SCIP_LP *lp)
Definition: lp.c:6751
SCIP_Real SCIProwGetLPEfficacy(SCIP_ROW *row, SCIP_SET *set, SCIP_STAT *stat, SCIP_LP *lp)
Definition: lp.c:6808
SCIP_Bool SCIProwIsSolEfficacious(SCIP_ROW *row, SCIP_SET *set, SCIP_STAT *stat, SCIP_SOL *sol, SCIP_Bool root)
Definition: lp.c:6908
SCIP_Real SCIProwGetMinActivity(SCIP_ROW *row, SCIP_SET *set, SCIP_STAT *stat)
Definition: lp.c:6598
internal methods for LP management
SCIP_Bool SCIPprobAllColsInLP(SCIP_PROB *prob, SCIP_SET *set, SCIP_LP *lp)
Definition: prob.c:2350
internal methods for storing and manipulating the main problem
public methods for storing cuts in a cut pool
public methods for LP management
public methods for message output
#define SCIPerrorMessage
Definition: pub_message.h:64
public methods for conflict handler plugins and conflict analysis
public methods for cuts and aggregation rows
public methods for numerical tolerances
public methods for the branch-and-bound tree
SCIP_RETCODE SCIPsepastoreClearCuts(SCIP_SEPASTORE *sepastore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_LP *lp)
Definition: sepastore.c:1027
int SCIPsepastoreGetNCuts(SCIP_SEPASTORE *sepastore)
Definition: sepastore.c:1149
SCIP_RETCODE SCIPsepastoreAddCut(SCIP_SEPASTORE *sepastore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_LP *lp, SCIP_ROW *cut, SCIP_Bool forcecut, SCIP_Bool root, SCIP_Bool *infeasible)
Definition: sepastore.c:428
SCIP_RETCODE SCIPsepastoreRemoveInefficaciousCuts(SCIP_SEPASTORE *sepastore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_LP *lp, SCIP_Bool root, SCIP_EFFICIACYCHOICE efficiacychoice)
Definition: sepastore.c:1073
SCIP_ROW ** SCIPsepastoreGetCuts(SCIP_SEPASTORE *sepastore)
Definition: sepastore.c:1139
SCIP_Bool SCIPsepastoreIsCutApplicable(SCIP_SET *set, SCIP_ROW *cut)
Definition: sepastore.c:1130
internal methods for storing separated cuts
SCIP_Bool SCIPsetIsEfficacious(SCIP_SET *set, SCIP_Bool root, SCIP_Real efficacy)
Definition: set.c:7061
internal methods for global SCIP settings
SCIP_RETCODE SCIPseparationRound(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_PROB *prob, SCIP_PRIMAL *primal, SCIP_TREE *tree, SCIP_LP *lp, SCIP_SEPASTORE *sepastore, SCIP_SOL *sol, int actdepth, SCIP_Bool allowlocal, SCIP_Bool onlydelayed, SCIP_Bool *delayed, SCIP_Bool *cutoff)
Definition: solve.c:2042
internal methods for main solving loop and node processing
SCIP_Real rhs
Definition: struct_lp.h:205
SCIP_Real * vals
Definition: struct_lp.h:229
SCIP_Real lhs
Definition: struct_lp.h:204
SCIP_COL ** cols
Definition: struct_lp.h:227
data structures for LP management
datastructures for block memory pools and memory buffers
SCIP main data structure.
datastructures for global SCIP settings
SCIP_NODE * SCIPtreeGetCurrentNode(SCIP_TREE *tree)
Definition: tree.c:8435
SCIP_Bool SCIPtreeHasCurrentNodeLP(SCIP_TREE *tree)
Definition: tree.c:8469
int SCIPtreeGetCurrentDepth(SCIP_TREE *tree)
Definition: tree.c:8452
internal methods for branch and bound tree
@ SCIP_CONFTYPE_PROPAGATION
Definition: type_conflict.h:60
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
@ SCIP_OKAY
Definition: type_retcode.h:42
@ SCIP_INVALIDCALL
Definition: type_retcode.h:51
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_EFFICIACYCHOICE_LP