SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
sepa_mixing.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 sepa_mixing.c
26 * @ingroup DEFPLUGINS_SEPA
27 * @brief mixing/star inequality separator
28 * @author Weikun Chen
29 * @author Marc Pfetsch
30 *
31 * This separator generates cuts based on the mixing set
32 * \f[
33 * X = \{ (x,y) \in \{0,1\}^{N \cup M} \times \mathbb{R} \, : \, y \geq a_i x_i, \, \textrm{for} \, i \in N, \,
34 * y \leq u - a_i x_i, \, \textrm{for} \, i \in M, \, 0 \leq y \leq u \},
35 * \f]
36 * where \f$0 \leq a_i \leq u\f$ for all \f$i\f$. This information can be obtained directly from the variable bounds data
37 * structure. The separator will generate three classes of cuts.
38 *
39 * VLB: Let \f$T\f$ be a subset of \f$N\f$, wlog, \f$T = \{1,\ldots,r\}\f$ with \f$a_1 \leq a_2 \leq \ldots \leq a_r\f$.
40 * Let \f$a_0 = 0\f$. The mixing/star VLB cut is of the form \f$ y \geq \sum_{i=1}^r (a_i - a_{i-1})x_i \f$.
41 *
42 * VUB: Let \f$T\f$ be a subset of \f$M\f$, wlog, \f$T = \{1,\ldots,r\}\f$ with \f$a_1 \leq a_2 \leq \ldots \leq a_r\f$.
43 * Let \f$a_0 = 0\f$. The mixing/star VUB cut is of the form \f$ y \leq u - \sum_{i=1}^r (a_i - a_{i-1})x_i \f$.
44 *
45 * CONFLICT: Consider \f$i \in N\f$ and \f$j \in M\f$ with \f$a_i + a_j > u\f$. The conflict cut is
46 * \f$x_i + x_j \leq 1\f$.
47 *
48 * A small example is described in the following to see the generated cuts.
49 * \f[
50 * Y = \{ (x,y) \in \{0,1\}^{4} \times \mathbb{R} \, : \, y \geq 2x_1, \, y \geq 3x_2, \, y \leq 4 - x_3, \,
51 * y \leq 4 - 2 x_4, \, 0 \leq y \leq 4 \}.
52 * \f]
53 * In this small example, the mixing/star cuts \f$y \geq 2x_1 + x_2\f$ (VLB) and \f$y \leq 4 - x_3 - x_4\f$ (VUB) will be
54 * considered to be generated. Besides the mixing cuts, we also consider the conflict cut \f$x_1 + x_3 \leq 1\f$ (CONFLICT).
55 *
56 *
57 * For an overview see:
58 * Atamturk, A., Nemhauser, G.L. and Savelsbergh, M.W.,@n
59 * The mixed vertex packing problem.@n
60 * Mathematical Programming, 89(1), 35-53, 2000.
61 *
62 * Some remarks:
63 * - Besides the mixing inequality, we also add the conflict inequality.
64 * - Currently, the performance is bad on the neos-565672 instance.
65 * The reason is that, after adding the separator, SCIP spends a lot of time at the stage of cutting plane generation.
66 * - We do not consider sparsity of the cuts as we aim to find a most violated cut.
67 * - Besides the most violated cut we consider, we also add an additional variable to make the cut be the strongest one,
68 * even the additional variable does not contribute any to the violation.
69 *
70 */
71
72/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
73
75#include "scip/pub_implics.h"
76#include "scip/pub_lp.h"
77#include "scip/pub_message.h"
78#include "scip/pub_misc.h"
79#include "scip/pub_sepa.h"
80#include "scip/pub_var.h"
81#include "scip/scip_branch.h"
82#include "scip/scip_cut.h"
83#include "scip/scip_lp.h"
84#include "scip/scip_mem.h"
85#include "scip/scip_message.h"
86#include "scip/scip_numerics.h"
87#include "scip/scip_param.h"
88#include "scip/scip_prob.h"
89#include "scip/scip_sepa.h"
90#include "scip/scip_sol.h"
92#include "scip/scip_var.h"
93#include "scip/sepa_mixing.h"
94#include "scip/scip_tree.h"
95#include "scip/sepa_mixing.h"
96#include <string.h>
97
98
99#define SEPA_NAME "mixing"
100#define SEPA_DESC "mixing inequality separator"
101#define DEFAULT_MAXROUNDS -1 /**< maximal number of mixing separation rounds per node (-1: unlimited) */
102#define DEFAULT_MAXROUNDSROOT -1 /**< maximal number of mixing separation rounds in the root node (-1: unlimited) */
103#define SEPA_PRIORITY -50
104#define SEPA_FREQ 10
105#define SEPA_MAXBOUNDDIST 1.0
106#define SEPA_USESSUBSCIP FALSE /**< does the separator use a secondary SCIP instance? */
107#define SEPA_DELAY FALSE /**< should separation method be delayed, if other separators found cuts? */
108
109#define DEFAULT_USELOCALBOUNDS FALSE /**< should local bounds be used? */
110#define DEFAULT_ISCUTSONINTS FALSE /**< should general/implicit integer variables be used to generate cuts? */
111#define DEFAULT_MAXNUNSUCCESSFUL 10 /**< maximal number of consecutive unsuccessful iterations */
112
113/** separator-specific data for the mixing separator */
114struct SCIP_SepaData
115{
116 SCIP_Bool uselocalbounds; /**< should local bounds be used? */
117 SCIP_Bool iscutsonints; /**< should general/implicit integer variables be used to generate cuts? */
118 int maxrounds; /**< maximal number of mixing separation rounds per node (-1: unlimited) */
119 int maxroundsroot; /**< maximal number of mixing separation rounds in the root node (-1: unlimited) */
120 int nunsuccessful; /**< number of consecutive unsuccessful iterations */
121 int maxnunsuccessful; /**< maximal number of consecutive unsuccessful iterations */
122};
123
124/*
125 * local methods
126 */
127
128/** adds the given cut */
129static
131 SCIP* scip, /**< SCIP data structure */
132 SCIP_SEPA* sepa, /**< separator */
133 SCIP_SOL* sol, /**< the solution that should be separated, or NULL for LP solution */
134 SCIP_Real* cutcoefs, /**< coefficients of active variables in cut */
135 int* cutinds, /**< problem indices of variables in cut */
136 int cutnnz, /**< number of non-zeros in cut */
137 SCIP_Real cutrhs, /**< right hand side of cut */
138 SCIP_Bool cutislocal, /**< Is the cut only locally valid? */
139 SCIP_Bool* cutoff, /**< pointer to store whether a cutoff has been detected */
140 int* ncuts /**< pointer to update number of cuts added */
141 )
142{
144 SCIP_VAR** vars;
145 SCIP_ROW* cut;
146 int v;
147
148 assert(cutcoefs != NULL);
149 assert(cutinds != NULL);
150 assert(ncuts != NULL);
151 assert(cutoff != NULL);
152
153 *cutoff = FALSE;
154
155 /* get active problem variables */
157
158 /* construct cut name */
160
161 /* create empty cut */
163 cutislocal, FALSE, TRUE) );
164
165 /* cache the row extension and only flush them if the cut gets added */
167
168 /* collect all non-zero coefficients */
169 for( v = 0; v < cutnnz; ++v )
170 {
172 }
173
174 /* flush all changes before adding the cut */
176
178 {
179 /* set cut rank */
181
182#ifdef SCIP_DEBUG
183 SCIPdebugMsg(scip, "-> found cut (eff: %f): ", SCIPgetCutEfficacy(scip, sol, cut));
185#endif
186
187 if( cutislocal )
188 {
189 /* local cuts are added to the sepastore */
191 }
192 else
193 {
195 }
196 (*ncuts)++;
197 }
198
199 /* release the row */
201
202 return SCIP_OKAY;
203}
204
205/** searches and adds mixing cuts that are violated by the given solution value array
206 *
207 * This function implements a separation heuristic that runs in linear time in comparison to the quadratic exact
208 * algorithm in Atamturk et al.:
209 * - Lower and upper bounds are considered separately. Then possible conflict cuts.
210 * - Variable lower/upper bounds data are collected, i.e., the corresponding binary variables and coefficients.
211 * - These lists are sorted non-increasingly according to the solution values.
212 * - Then binary variables are added in turn as long as their coefficients increase in order to make the coefficients
213 * nonnegative. This clearly makes the cuts heuristic, since it is order dependent, but also sparser.
214 * - The procedure stops as soon as it reaches 0 solution values.
215 * - If the cut is efficious it is added.
216 *
217 * @todo Check whether one wants to sort according to the quotient of solution values and coefficients to increase the
218 * chance of having smaller coefficients in the front.
219 */
220static
222 SCIP* scip, /**< SCIP data structure */
223 SCIP_SEPA* sepa, /**< separator */
224 SCIP_SOL* sol, /**< the solution that should be separated, or NULL for LP solution */
225 SCIP_Bool* cutoff, /**< whether a cutoff has been detected */
226 int* ncuts /**< pointer to store the number of generated cuts */
227 )
228{
230 SCIP_VAR* var;
231 SCIP_VAR** vars;
232 SCIP_Real* vlbmixcoefs;
233 SCIP_Real* vlbmixsols;
234 SCIP_Real* vubmixcoefs;
235 SCIP_Real* vubmixsols;
236 SCIP_Real* cutcoefs;
237 SCIP_Real cutrhs;
238 int* vlbmixinds;
239 int* vubmixinds;
240 int* cutinds;
241 int* vlbmixsigns;
242 int* vubmixsigns;
243 int firstvar;
244 int nmaxvars;
245 int nvars;
246 int i;
247 int k;
248
249 assert(sepa != NULL);
250 assert(cutoff != NULL);
251 assert(ncuts != NULL);
252
253 *cutoff = FALSE;
254 *ncuts = 0;
255
256 /* exit if there are no binary variables - ignore integer variables that have 0/1 bounds */
258 if( nmaxvars <= 0 )
259 return SCIP_OKAY;
260
262 assert(sepadata != NULL);
263
264 /* get the index of the first considered variable */
265 if( sepadata->iscutsonints )
266 {
267 /* generate cuts based on all nonbinary variabels */
269 }
270 else
271 {
272 /* only generate cuts based on continuous variables */
274 }
276 if( firstvar == nvars )
277 return SCIP_OKAY;
278
280
281 /* allocate temporary memory */
292
293 for( i = firstvar; i < nvars; i++ )
294 {
296 SCIP_Real* vlbcoefs;
297 SCIP_Real* vlbconsts;
299 SCIP_Real* vubcoefs;
300 SCIP_Real* vubconsts;
301 SCIP_Real maxabscoef;
302 SCIP_Real activity;
303 SCIP_Real lastcoef;
304 SCIP_Real varsolval;
305 SCIP_Real lb = SCIP_INVALID;
306 SCIP_Real ub = SCIP_INVALID;
307 SCIP_Bool islocallb = FALSE; /* Is it a local lower bound or global lower bound? */
308 SCIP_Bool islocalub = FALSE; /* Is it a local upper bound or global upper bound? */
309 SCIP_Bool cutislocal; /* Is it a local cut or global cut? */
310 int vlbmixsize = 0;
311 int vubmixsize = 0;
312 int cutnnz = 0;
313 int maxabsind;
314 int maxabssign;
315 int nvlb;
316 int nvub;
317 int j;
318
319 var = vars[i];
321
322 if( SCIPvarGetProbindex(var) < 0 )
323 continue;
324
327
328 if( nvlb == 0 && nvub == 0 )
329 continue;
330
331 /* skip lower bound if the LP solution value is equal to the upper bound of the continuous variable */
334 goto VUB;
335
336 if( nvlb == 0 )
337 goto VUB;
338
339 /* get variable lower variable bounds information */
343
344 maxabscoef = 0.0;
345 maxabsind = -1;
346 maxabssign = 0;
347
349 if( sepadata->uselocalbounds && SCIPisLT(scip, lb, SCIPvarGetLbLocal(var)) )
350 {
351 /* this is a lcoal cut */
352 islocallb = TRUE;
354 }
355
356#ifdef SCIP_DEBUG
357 for( j = 0; j < nvlb; j++ )
358 {
359 SCIP_Real tmplb;
360
362 {
363 tmplb = (vlbcoefs[j] > 0) ? vlbconsts[j] : (vlbconsts[j] + vlbcoefs[j]);
364 assert( SCIPisFeasLE(scip, tmplb, lb) );
365 }
366 }
367#endif
368
370
371 /* extract the useful variable bounds information (binary and nonredundant) */
372 for( j = 0; j < nvlb; j++ )
373 {
374 /* consider only active and binary variables */
376 {
377 SCIP_Real maxactivity;
378 SCIP_Real coef;
379
380 maxactivity = (vlbcoefs[j] > 0) ? (vlbconsts[j] + vlbcoefs[j]) : vlbconsts[j];
381
382 /* skip redundant variable bound constraints */
383 if( SCIPisFeasLE(scip, maxactivity, lb) )
384 continue;
385
386 if( vlbcoefs[j] > 0 )
387 {
388 coef = maxactivity - lb;
390 }
391 else
392 {
393 coef = lb - maxactivity;
395 }
397
401
402 /* update the maximal coefficient if needed */
404 {
408 }
409
410 ++vlbmixsize;
411
412 /* stop if size is exceeded; possibly ignore redundant variable bounds */
413 if( vlbmixsize >= nmaxvars )
414 break;
415 }
416 }
418
419 /* stop if no variable lower bounds information exists */
420 if( vlbmixsize == 0 )
421 goto VUB;
422
423 /* stop if the current solution value of the transformed continuous variable is larger than the maximal coefficient */
425 goto VUB;
426
427 /* sort the solution values in non-increasing order */
429
430 /* add the continuous variable */
431 cutcoefs[cutnnz] = -1;
433 cutrhs = -lb;
434 cutnnz++;
435
436 activity = -(varsolval - lb);
437 lastcoef = 0.0;
438
439 /* loop over the variables and add the variable to the cut if its coefficient is larger than that of the last variable */
440 for( j = 0; j < vlbmixsize; j++ )
441 {
442 SCIP_Real solval;
443
444 solval = vlbmixsols[j];
445
446 /* stop if we can not find a violated cut or we reached 0 solution values */
447 if( activity + solval * (maxabscoef - lastcoef) < 0.0 || SCIPisFeasZero(scip, solval) )
448 break;
449 else
450 {
451 /* skip if we have already added a variable with bigger coefficient */
453 continue;
454 else
455 {
456 activity += (vlbmixcoefs[j] - lastcoef) * solval;
457 if( vlbmixsigns[j] )
458 {
461 }
462 else
466 }
467 }
468 }
469
470 /* add the variable with maximal coefficient to make sure the cut is strong enough */
472 {
473 /* do not update activity: either the corresponding solval is 0.0 or the cut will not become efficious */
474 if( maxabssign )
475 {
478 }
479 else
482 }
483 assert( cutnnz <= nmaxvars + 1 );
484
485 /* add the cut if the violtion is good enough and the number of nonzero coefficients is larger than 2 */
486 if( SCIPisEfficacious(scip, activity) && cutnnz > 2 )
487 {
489 }
490
491 VUB:
492 if( nvub == 0 )
493 goto CONFLICT;
494
495 /* get variable upper bounds information */
499
500 maxabscoef = 0.0;
501 maxabsind = -1;
502 maxabssign = 0;
503
504 /* stop if the lower bound is equal to the solution value of the continuous variable */
506 goto CONFLICT;
507
509 if( sepadata->uselocalbounds && SCIPisGT(scip, ub, SCIPvarGetUbLocal(var)) )
510 {
511 /* this is a lcoal cut */
512 islocalub = TRUE;
514 }
515
516#ifdef SCIP_DEBUG
517 for( j = 0; j < nvub; j++ )
518 {
519 SCIP_Real tmpub;
520
522 {
523 tmpub = (vubcoefs[j] < 0) ? vubconsts[j] : (vubconsts[j] + vubcoefs[j]);
524 assert( SCIPisFeasGE(scip, tmpub, ub) );
525 }
526 }
527#endif
528
530
531 /* extract the useful variable bounds information (binary and nonredundant) */
532 for( j = 0; j < nvub; j++ )
533 {
534 /* consider only active and binary variables */
536 {
537 SCIP_Real minactivity;
538 SCIP_Real coef;
539
540 minactivity = (vubcoefs[j] < 0) ? (vubconsts[j] + vubcoefs[j]) : vubconsts[j];
541
542 /* skip redundant variable bound constraints */
543 if( SCIPisFeasLE(scip, ub, minactivity) )
544 continue;
545
546 if( vubcoefs[j] > 0 )
547 {
548 coef = ub - minactivity;
550 }
551 else
552 {
553 coef = minactivity - ub;
555 }
556
560
561 /* update the maximal coefficient if needed */
563 {
567 }
568
569 ++vubmixsize;
570
571 /* stop if size is exceeded; possibly ignore redundant variable bounds */
572 if( vubmixsize >= nmaxvars )
573 break;
574 }
575 }
577
578 /* stop if no variable upper bounds information exists */
579 if( vubmixsize == 0 )
580 goto CONFLICT;
581
582 /* stop if the current solution value of transformed continuous variable is larger than the maximal coefficient */
584 goto CONFLICT;
585
586 /* sort the solution values in non-increasing order */
588
589 /* add the continuous variables */
590 cutnnz = 0;
591 cutcoefs[cutnnz] = 1;
593 cutrhs = ub;
594 cutnnz++;
595
596 activity = varsolval - ub;
597 lastcoef = 0.0;
598
599 for( j = 0; j < vubmixsize; j++ )
600 {
601 SCIP_Real solval;
602
603 solval = vubmixsols[j];
604
605 /* stop if we can not find a violated cut or we reached 0 solution values */
606 if( activity + solval * (maxabscoef - lastcoef) < 0.0 || SCIPisFeasZero(scip, solval) )
607 break;
608 else
609 {
610 /* skip if we have already added a variable with bigger coefficient */
612 continue;
613 else
614 {
615 activity += (vubmixcoefs[j] - lastcoef) * solval;
616 if( vubmixsigns[j] )
617 {
620 }
621 else
625 }
626 }
627 }
628
629 /* add the variable with maximal coefficient if needed */
631 {
632 /* do not update activity: either the corresponding solval is 0.0 or the cut will not become efficious */
633 if( maxabssign )
634 {
637 }
638 else
641 }
642 assert( cutnnz <= nmaxvars + 1 );
643
644 /* add the cut if the violtion is good enough and the number of nonzero coefficients is larger than 2 */
645 if( SCIPisEfficacious(scip, activity) && cutnnz > 2 )
646 {
648 }
649
650 CONFLICT:
651 /* combine the variable lower bounds information and upper bounds information together to generate cuts */
652 /* stop if no useful variable lower (or upper) bounds information exists */
653 if( vlbmixsize == 0 || vubmixsize == 0 )
654 continue;
655
656 assert( lb != SCIP_INVALID ); /*lint !e777*/
657 assert( ub != SCIP_INVALID ); /*lint !e777*/
658
660 for( j = 0; j < vlbmixsize; j++ )
661 {
662 SCIP_Real solval;
663
664 solval = vlbmixsols[j];
665
666 /* stop if no violated cut exists */
667 if( ! SCIPisEfficacious(scip, solval + vubmixsols[0] - 1.0) )
668 break;
669
670 for( k = 0; k < vubmixsize; k++ )
671 {
672 /* only consider the inequality if its violation is good enough */
673 if( SCIPisEfficacious(scip, solval + vubmixsols[k] - 1.0) )
674 {
675 SCIP_Real tmp;
676
677 tmp = lb + vlbmixcoefs[j] + vubmixcoefs[k] - ub;
678
679 /* add the cut if it is valid */
681 {
682 cutnnz = 2;
683 cutrhs = 1.0;
684 cutcoefs[0] = vlbmixsigns[j] ? -1.0 : 1.0;
685 cutcoefs[1] = vubmixsigns[k] ? -1.0 : 1.0;
686 cutinds[0] = vlbmixinds[j];
687 cutinds[1] = vubmixinds[k];
688 cutrhs = vlbmixsigns[j] ? (cutrhs - 1.0) : cutrhs;
689 cutrhs = vubmixsigns[k] ? (cutrhs - 1.0) : cutrhs;
691 }
692 }
693 else
694 break;
695 }
696 }
697 }
698
699 /* free temporary memory */
710
711 return SCIP_OKAY;
712}
713
714
715/*
716 * Callback methods of separator
717 */
718
719/** copy method for separator plugins (called when SCIP copies plugins) */
720static
722{ /*lint --e{715}*/
723 assert(scip != NULL);
724 assert(sepa != NULL);
726
727 /* call inclusion method of separator */
729
730 return SCIP_OKAY;
731}
732
733/** destructor of separator to free user data (called when SCIP is exiting) */
734static
736{ /*lint --e{715}*/
738
739 assert(scip != NULL);
740 assert(sepa != NULL);
742
743 /* get separation data and free it */
745 assert(sepadata != NULL);
747
748 /* reset data pointer to NULL */
749 SCIPsepaSetData(sepa, NULL);
750
751 return SCIP_OKAY;
752}
753
754
755/** LP solution separation method of separator */
756static
758{ /*lint --e{715}*/
760 SCIP_Bool cutoff;
761 int nbinvars;
762 int nvars;
763 int ncuts;
764 int ncalls;
765
766 assert(sepa != NULL);
767 assert(scip != NULL);
768 assert(result != NULL);
769
773 assert(sepadata != NULL);
774
775 /* only call the mixing cut separator a given number of times at each node */
776 if( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot)
777 || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
778 return SCIP_OKAY;
779
780 /* gets numver of active problem variables and number of binary variables */
782
783 /* if all the active problem variables are binary, stop */
784 if( nvars == nbinvars )
785 return SCIP_OKAY;
786
787 /* call the cut separation */
788 SCIP_CALL( separateCuts(scip, sepa, NULL, &cutoff, &ncuts) );
789
790 /* adjust result code */
791 if( cutoff )
793 else if( ncuts > 0 )
794 {
795 SCIPdebugMsg(scip, "mixing separator generated %d cuts.\n", ncuts);
797 }
798 else
800
801 return SCIP_OKAY;
802}
803
804/** arbitrary primal solution separation method of separator */
805static
807{ /*lint --e{715}*/
809 SCIP_Bool cutoff;
810 int nbinvars;
811 int nvars;
812 int ncuts;
813 int ncalls;
814
815 assert(sepa != NULL);
816 assert(scip != NULL);
817 assert(result != NULL);
818
821 assert(sepadata != NULL);
822
823 /* do not run if we have reached the maximal number of consecutive unsuccessful calls */
824 if( sepadata->nunsuccessful >= sepadata->maxnunsuccessful )
825 return SCIP_OKAY;
826
827 /* only call the mixing cut separator a given number of times at each node */
829 if( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot)
830 || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
831 return SCIP_OKAY;
832
833 /* gets numver of active problem variables and number of binary variables */
836
837 /* if all the active problem variables are binary, stop */
838 if( nvars == nbinvars )
839 return SCIP_OKAY;
840
841 /* call the cut separation */
842 SCIP_CALL( separateCuts(scip, sepa, sol, &cutoff, &ncuts) );
843
844 /* adjust result code */
845 if( cutoff )
846 {
847 sepadata->nunsuccessful = 0;
849 }
850 else if( ncuts > 0 )
851 {
852 SCIPdebugMsg(scip, "mixing separator generated %d cuts.\n", ncuts);
853 sepadata->nunsuccessful = 0;
855 }
856 else
857 {
858 ++sepadata->nunsuccessful;
860 }
861
862 return SCIP_OKAY;
863}
864
865
866/*
867 * separator specific interface methods
868 */
869
870/** creates the mixing separator and includes it in SCIP */
872 SCIP* scip /**< SCIP data structure */
873 )
874{
876 SCIP_SEPA* sepa;
877
878 /* create mixing separator data */
880 assert(sepadata != NULL);
881 sepadata->nunsuccessful = 0;
882
883 /* include separator */
887 sepadata) );
888 assert(sepa != NULL);
889
890 /* set non-NULL pointers to callback methods */
893
894 /* add separator parameters */
895 SCIP_CALL( SCIPaddBoolParam(scip, "separating/mixing/uselocalbounds",
896 "Should local bounds be used?",
897 &sepadata->uselocalbounds, TRUE, DEFAULT_USELOCALBOUNDS, NULL, NULL) );
898
899 SCIP_CALL( SCIPaddBoolParam(scip, "separating/mixing/iscutsonints",
900 "Should general integer variables be used to generate cuts?",
901 &sepadata->iscutsonints, TRUE, DEFAULT_ISCUTSONINTS, NULL, NULL) );
902
903 SCIP_CALL( SCIPaddIntParam(scip, "separating/mixing/maxrounds",
904 "maximal number of mixing separation rounds per node (-1: unlimited)",
905 &sepadata->maxrounds, FALSE, DEFAULT_MAXROUNDS, -1, INT_MAX, NULL, NULL) );
906
907 SCIP_CALL( SCIPaddIntParam(scip, "separating/mixing/maxroundsroot",
908 "maximal number of mixing separation rounds in the root node (-1: unlimited)",
909 &sepadata->maxroundsroot, FALSE, DEFAULT_MAXROUNDSROOT, -1, INT_MAX, NULL, NULL) );
910
911 SCIP_CALL( SCIPaddIntParam(scip, "separating/mixing/maxnunsuccessful",
912 "maximal number of consecutive unsuccessful iterations",
913 &sepadata->maxnunsuccessful, FALSE, DEFAULT_MAXNUNSUCCESSFUL, -1, INT_MAX, NULL, NULL) );
914
915 return SCIP_OKAY;
916}
#define NULL
Definition def.h:267
#define SCIP_MAXSTRLEN
Definition def.h:288
#define SCIP_INVALID
Definition def.h:193
#define TRUE
Definition def.h:93
#define FALSE
Definition def.h:94
#define SCIP_LONGINT_FORMAT
Definition def.h:165
#define REALABS(x)
Definition def.h:197
#define SCIP_CALL(x)
Definition def.h:374
int SCIPgetNIntVars(SCIP *scip)
Definition scip_prob.c:2082
int SCIPgetNImplVars(SCIP *scip)
Definition scip_prob.c:2127
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition scip_prob.c:1866
int SCIPgetNVars(SCIP *scip)
Definition scip_prob.c:1992
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition scip_prob.c:1947
int SCIPgetNBinVars(SCIP *scip)
Definition scip_prob.c:2037
#define SCIPdebugMsg
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition scip_param.c:83
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition scip_param.c:57
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_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition scip_cut.c:117
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
Definition scip_cut.c:135
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition scip_cut.c:250
#define SCIPallocBufferArray(scip, ptr, num)
Definition scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition scip_mem.h:136
#define SCIPfreeBlockMemory(scip, ptr)
Definition scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition scip_mem.h:89
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition scip_lp.c:1635
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition scip_lp.c:1658
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition scip_lp.c:1701
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition scip_lp.c:2212
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition scip_lp.c:1562
SCIP_RETCODE SCIPcreateEmptyRowSepa(SCIP *scip, SCIP_ROW **row, SCIP_SEPA *sepa, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition scip_lp.c:1453
void SCIProwChgRank(SCIP_ROW *row, int rank)
Definition lp.c:17534
SCIP_RETCODE SCIPincludeSepaBasic(SCIP *scip, SCIP_SEPA **sepa, const char *name, const char *desc, int priority, int freq, SCIP_Real maxbounddist, SCIP_Bool usessubscip, SCIP_Bool delay, SCIP_DECL_SEPAEXECLP((*sepaexeclp)), SCIP_DECL_SEPAEXECSOL((*sepaexecsol)), SCIP_SEPADATA *sepadata)
Definition scip_sepa.c:109
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa,)
Definition scip_sepa.c:167
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
Definition sepa.c:743
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
Definition sepa.c:880
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
Definition sepa.c:633
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
Definition sepa.c:643
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa,)
Definition scip_sepa.c:151
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition scip_sol.c:1217
SCIP_Longint SCIPgetNLPs(SCIP *scip)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPvarGetNVlbs(SCIP_VAR *var)
Definition var.c:18270
SCIP_Real * SCIPvarGetVlbCoefs(SCIP_VAR *var)
Definition var.c:18292
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition var.c:17599
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition var.c:18144
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition var.c:17584
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition var.c:18088
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition var.c:17768
SCIP_Real * SCIPvarGetVlbConstants(SCIP_VAR *var)
Definition var.c:18302
int SCIPvarGetNVubs(SCIP_VAR *var)
Definition var.c:18312
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition var.c:18134
SCIP_VAR ** SCIPvarGetVlbVars(SCIP_VAR *var)
Definition var.c:18282
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition var.c:18078
SCIP_Real * SCIPvarGetVubConstants(SCIP_VAR *var)
Definition var.c:18344
SCIP_VAR ** SCIPvarGetVubVars(SCIP_VAR *var)
Definition var.c:18324
SCIP_Real * SCIPvarGetVubCoefs(SCIP_VAR *var)
Definition var.c:18334
SCIP_RETCODE SCIPincludeSepaMixing(SCIP *scip)
void SCIPsortDownRealRealIntInt(SCIP_Real *realarray1, SCIP_Real *realarray2, int *intarray1, int *intarray2, int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition misc.c:10877
return SCIP_OKAY
SCIP_Longint ncalls
int depth
SCIP_Bool cutoff
static SCIP_SOL * sol
assert(minobj< SCIPgetCutoffbound(scip))
int nvars
SCIP_VAR * var
static SCIP_VAR ** vars
int nbinvars
memory allocation routines
public methods for implications, variable bounds, and cliques
public methods for LP management
public methods for message output
public data structures and miscellaneous methods
public methods for separators
public methods for problem variables
public methods for branching rule plugins and branching
public methods for cuts and aggregation rows
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for separator plugins
public methods for solutions
public methods for querying solving statistics
public methods for the branch-and-bound tree
public methods for SCIP variables
#define SEPA_PRIORITY
#define SEPA_DELAY
static SCIP_RETCODE addCut(SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_Real *cutcoefs, int *cutinds, int cutnnz, SCIP_Real cutrhs, SCIP_Bool cutislocal, SCIP_Bool *cutoff, int *ncuts)
#define SEPA_DESC
#define DEFAULT_MAXNUNSUCCESSFUL
#define DEFAULT_MAXROUNDSROOT
#define SEPA_USESSUBSCIP
static SCIP_RETCODE separateCuts(SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_Bool *cutoff, int *ncuts)
#define DEFAULT_USELOCALBOUNDS
#define SEPA_MAXBOUNDDIST
#define SEPA_FREQ
#define SEPA_NAME
Definition sepa_mixing.c:99
#define DEFAULT_ISCUTSONINTS
#define DEFAULT_MAXROUNDS
mixing cuts separator
@ SCIP_DIDNOTRUN
Definition type_result.h:42
@ SCIP_CUTOFF
Definition type_result.h:48
@ SCIP_DIDNOTFIND
Definition type_result.h:44
@ SCIP_SEPARATED
Definition type_result.h:49
enum SCIP_Retcode SCIP_RETCODE
struct SCIP_SepaData SCIP_SEPADATA
Definition type_sepa.h:52
#define SCIP_DECL_SEPAEXECSOL(x)
Definition type_sepa.h:166
#define SCIP_DECL_SEPAEXECLP(x)
Definition type_sepa.h:136
#define SCIP_DECL_SEPAFREE(x)
Definition type_sepa.h:69
#define SCIP_DECL_SEPACOPY(x)
Definition type_sepa.h:61
@ SCIP_VARTYPE_BINARY
Definition type_var.h:62