1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file sepa_mixing.c
17 * @ingroup DEFPLUGINS_SEPA
18 * @brief mixing/star inequality separator
19 * @author Weikun Chen
20 * @author Marc Pfetsch
21 *
22 * This separator generates cuts based on the mixing set
23 * \f[
24 * X = \{ (x,y) \in \{0,1\}^{N \cup M} \times \mathbb{R} \, : \, y \geq a_i x_i, \, \textrm{for} \, i \in N, \,
25 * y \leq u - a_i x_i, \, \textrm{for} \, i \in M, \, 0 \leq y \leq u \},
26 * \f]
27 * 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
28 * structure. The separator will generate three classes of cuts.
29 *
30 * 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$.
31 * 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$.
32 *
33 * 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$.
34 * 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$.
35 *
36 * 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
37 * \f$x_i + x_j \leq 1\f$.
38 *
39 * A small example is described in the following to see the generated cuts.
40 * \f[
41 * Y = \{ (x,y) \in \{0,1\}^{4} \times \mathbb{R} \, : \, y \geq 2x_1, \, y \geq 3x_2, \, y \leq 4 - x_3, \,
42 * y \leq 4 - 2 x_4, \, 0 \leq y \leq 4 \}.
43 * \f]
44 * 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
45 * considered to be generated. Besides the mixing cuts, we also consider the conflict cut \f$x_1 + x_3 \leq 1\f$ (CONFLICT).
46 *
47 *
48 * For an overview see:
49 * Atamturk, A., Nemhauser, G.L. and Savelsbergh, M.W.,@n
50 * The mixed vertex packing problem.@n
51 * Mathematical Programming, 89(1), 35-53, 2000.
52 *
53 * Some remarks:
54 * - Besides the mixing inequality, we also add the conflict inequality.
55 * - Currently, the performance is bad on the neos-565672 instance.
56 * The reason is that, after adding the separator, SCIP spends a lot of time at the stage of cutting plane generation.
57 * - We do not consider sparsity of the cuts as we aim to find a most violated cut.
58 * - Besides the most violated cut we consider, we also add an additional variable to make the cut be the strongest one,
59 * even the additional variable does not contribute any to the violation.
60 *
61 */
62
63 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
64
65 #include "blockmemshell/memory.h"
66 #include "scip/pub_implics.h"
67 #include "scip/pub_lp.h"
68 #include "scip/pub_message.h"
69 #include "scip/pub_misc.h"
70 #include "scip/pub_sepa.h"
71 #include "scip/pub_var.h"
72 #include "scip/scip_branch.h"
73 #include "scip/scip_cut.h"
74 #include "scip/scip_lp.h"
75 #include "scip/scip_mem.h"
76 #include "scip/scip_message.h"
77 #include "scip/scip_numerics.h"
78 #include "scip/scip_param.h"
79 #include "scip/scip_prob.h"
80 #include "scip/scip_sepa.h"
81 #include "scip/scip_sol.h"
82 #include "scip/scip_solvingstats.h"
83 #include "scip/scip_var.h"
84 #include "scip/sepa_mixing.h"
85 #include "scip/scip_tree.h"
86 #include "scip/sepa_mixing.h"
87 #include <string.h>
88
89
90 #define SEPA_NAME "mixing"
91 #define SEPA_DESC "mixing inequality separator"
92 #define DEFAULT_MAXROUNDS -1 /**< maximal number of mixing separation rounds per node (-1: unlimited) */
93 #define DEFAULT_MAXROUNDSROOT -1 /**< maximal number of mixing separation rounds in the root node (-1: unlimited) */
94 #define SEPA_PRIORITY -50
95 #define SEPA_FREQ 10
96 #define SEPA_MAXBOUNDDIST 1.0
97 #define SEPA_USESSUBSCIP FALSE /**< does the separator use a secondary SCIP instance? */
98 #define SEPA_DELAY FALSE /**< should separation method be delayed, if other separators found cuts? */
99
100 #define DEFAULT_USELOCALBOUNDS FALSE /**< should local bounds be used? */
101 #define DEFAULT_ISCUTSONINTS FALSE /**< should general/implied integer variables be used to generate cuts? */
102 #define DEFAULT_MAXNUNSUCCESSFUL 10 /**< maximal number of consecutive unsuccessful iterations */
103
104 /** separator-specific data for the mixing separator */
105 struct SCIP_SepaData
106 {
107 SCIP_Bool uselocalbounds; /**< should local bounds be used? */
108 SCIP_Bool iscutsonints; /**< should general/implied integer variables be used to generate cuts? */
109 int maxrounds; /**< maximal number of mixing separation rounds per node (-1: unlimited) */
110 int maxroundsroot; /**< maximal number of mixing separation rounds in the root node (-1: unlimited) */
111 int nunsuccessful; /**< number of consecutive unsuccessful iterations */
112 int maxnunsuccessful; /**< maximal number of consecutive unsuccessful iterations */
113 };
114
115 /*
116 * local methods
117 */
118
119 /** adds the given cut */
120 static
121 SCIP_RETCODE addCut(
122 SCIP* scip, /**< SCIP data structure */
123 SCIP_SEPA* sepa, /**< separator */
124 SCIP_SOL* sol, /**< the solution that should be separated, or NULL for LP solution */
125 SCIP_Real* cutcoefs, /**< coefficients of active variables in cut */
126 int* cutinds, /**< problem indices of variables in cut */
127 int cutnnz, /**< number of non-zeros in cut */
128 SCIP_Real cutrhs, /**< right hand side of cut */
129 SCIP_Bool cutislocal, /**< Is the cut only locally valid? */
130 SCIP_Bool* cutoff, /**< pointer to store whether a cutoff has been detected */
131 int* ncuts /**< pointer to update number of cuts added */
132 )
133 {
134 char cutname[SCIP_MAXSTRLEN];
135 SCIP_VAR** vars;
136 SCIP_ROW* cut;
137 int v;
138
139 assert(cutcoefs != NULL);
140 assert(cutinds != NULL);
141 assert(ncuts != NULL);
142 assert(cutoff != NULL);
143
144 *cutoff = FALSE;
145
146 /* get active problem variables */
147 vars = SCIPgetVars(scip);
148
149 /* construct cut name */
|
(1) Event invalid_type: |
Argument "SCIPgetNLPs(scip)" to format specifier "%d" was expected to have type "int" but has type "long long". [details] |
150 (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "mix%d_x%d", SCIPgetNLPs(scip), *ncuts);
151
152 /* create empty cut */
153 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, cutname, -SCIPinfinity(scip), cutrhs,
154 cutislocal, FALSE, TRUE) );
155
156 /* cache the row extension and only flush them if the cut gets added */
157 SCIP_CALL( SCIPcacheRowExtensions(scip, cut) );
158
159 /* collect all non-zero coefficients */
160 for( v = 0; v < cutnnz; ++v )
161 {
162 SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[cutinds[v]], cutcoefs[v]) );
163 }
164
165 /* flush all changes before adding the cut */
166 SCIP_CALL( SCIPflushRowExtensions(scip, cut) );
167
168 if( SCIPisCutEfficacious(scip, sol, cut) )
169 {
170 /* set cut rank */
171 SCIProwChgRank(cut, 1);
172
173 #ifdef SCIP_DEBUG
174 SCIPdebugMsg(scip, "-> found cut (eff: %f): ", SCIPgetCutEfficacy(scip, sol, cut));
175 SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
176 #endif
177
178 if( cutislocal )
179 {
180 /* local cuts are added to the sepastore */
181 SCIP_CALL( SCIPaddRow(scip, cut, FALSE, cutoff) );
182 }
183 else
184 {
185 SCIP_CALL( SCIPaddPoolCut(scip, cut) );
186 }
187 (*ncuts)++;
188 }
189
190 /* release the row */
191 SCIP_CALL( SCIPreleaseRow(scip, &cut) );
192
193 return SCIP_OKAY;
194 }
195
196 /** searches and adds mixing cuts that are violated by the given solution value array
197 *
198 * This function implements a separation heuristic that runs in linear time in comparison to the quadratic exact
199 * algorithm in Atamturk et al.:
200 * - Lower and upper bounds are considered separately. Then possible conflict cuts.
201 * - Variable lower/upper bounds data are collected, i.e., the corresponding binary variables and coefficients.
202 * - These lists are sorted non-increasingly according to the solution values.
203 * - Then binary variables are added in turn as long as their coefficients increase in order to make the coefficients
204 * nonnegative. This clearly makes the cuts heuristic, since it is order dependent, but also sparser.
205 * - The procedure stops as soon as it reaches 0 solution values.
206 * - If the cut is efficious it is added.
207 *
208 * @todo Check whether one wants to sort according to the quotient of solution values and coefficients to increase the
209 * chance of having smaller coefficients in the front.
210 */
211 static
212 SCIP_RETCODE separateCuts(
213 SCIP* scip, /**< SCIP data structure */
214 SCIP_SEPA* sepa, /**< separator */
215 SCIP_SOL* sol, /**< the solution that should be separated, or NULL for LP solution */
216 SCIP_Bool* cutoff, /**< whether a cutoff has been detected */
217 int* ncuts /**< pointer to store the number of generated cuts */
218 )
219 {
220 SCIP_SEPADATA* sepadata;
221 SCIP_VAR* var;
222 SCIP_VAR** vars;
223 SCIP_Real* vlbmixcoefs;
224 SCIP_Real* vlbmixsols;
225 SCIP_Real* vubmixcoefs;
226 SCIP_Real* vubmixsols;
227 SCIP_Real* cutcoefs;
228 SCIP_Real cutrhs;
229 int* vlbmixinds;
230 int* vubmixinds;
231 int* cutinds;
232 int* vlbmixsigns;
233 int* vubmixsigns;
234 int firstvar;
235 int nmaxvars;
236 int nvars;
237 int i;
238 int k;
239
240 assert(sepa != NULL);
241 assert(cutoff != NULL);
242 assert(ncuts != NULL);
243
244 *cutoff = FALSE;
245 *ncuts = 0;
246
247 /* exit if there are no binary variables - ignore integer variables that have 0/1 bounds */
248 nmaxvars = SCIPgetNBinVars(scip);
249 if( nmaxvars <= 0 )
250 return SCIP_OKAY;
251
252 sepadata = SCIPsepaGetData(sepa);
253 assert(sepadata != NULL);
254
255 /* get the index of the first considered variable */
256 if( sepadata->iscutsonints )
257 {
258 /* generate cuts based on all nonbinary variabels */
259 firstvar = SCIPgetNBinVars(scip);
260 }
261 else
262 {
263 /* only generate cuts based on continuous variables */
264 firstvar = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip) + SCIPgetNImplVars(scip);
265 }
266 nvars = SCIPgetNVars(scip);
267 if( firstvar == nvars )
268 return SCIP_OKAY;
269
270 vars = SCIPgetVars(scip);
271
272 /* allocate temporary memory */
273 SCIP_CALL( SCIPallocBufferArray(scip, &vlbmixcoefs, nmaxvars) );
274 SCIP_CALL( SCIPallocBufferArray(scip, &vlbmixsols, nmaxvars) );
275 SCIP_CALL( SCIPallocBufferArray(scip, &vlbmixinds, nmaxvars) );
276 SCIP_CALL( SCIPallocBufferArray(scip, &vlbmixsigns, nmaxvars) );
277 SCIP_CALL( SCIPallocBufferArray(scip, &vubmixcoefs, nmaxvars) );
278 SCIP_CALL( SCIPallocBufferArray(scip, &vubmixsols, nmaxvars) );
279 SCIP_CALL( SCIPallocBufferArray(scip, &vubmixinds, nmaxvars) );
280 SCIP_CALL( SCIPallocBufferArray(scip, &vubmixsigns, nmaxvars) );
281 SCIP_CALL( SCIPallocBufferArray(scip, &cutcoefs, nmaxvars + 1) );
282 SCIP_CALL( SCIPallocBufferArray(scip, &cutinds, nmaxvars + 1) );
283
284 for( i = firstvar; i < nvars; i++ )
285 {
286 SCIP_VAR** vlbvars;
287 SCIP_Real* vlbcoefs;
288 SCIP_Real* vlbconsts;
289 SCIP_VAR** vubvars;
290 SCIP_Real* vubcoefs;
291 SCIP_Real* vubconsts;
292 SCIP_Real maxabscoef;
293 SCIP_Real activity;
294 SCIP_Real lastcoef;
295 SCIP_Real varsolval;
296 SCIP_Real lb = SCIP_INVALID;
297 SCIP_Real ub = SCIP_INVALID;
298 SCIP_Bool islocallb = FALSE; /* Is it a local lower bound or global lower bound? */
299 SCIP_Bool islocalub = FALSE; /* Is it a local upper bound or global upper bound? */
300 SCIP_Bool cutislocal; /* Is it a local cut or global cut? */
301 int vlbmixsize = 0;
302 int vubmixsize = 0;
303 int cutnnz = 0;
304 int maxabsind;
305 int maxabssign;
306 int nvlb;
307 int nvub;
308 int j;
309
310 var = vars[i];
311 assert( SCIPvarGetType(var) != SCIP_VARTYPE_BINARY );
312
313 if( SCIPvarGetProbindex(var) < 0 )
314 continue;
315
316 nvlb = SCIPvarGetNVlbs(var);
317 nvub = SCIPvarGetNVubs(var);
318
319 if( nvlb == 0 && nvub == 0 )
320 continue;
321
322 /* skip lower bound if the LP solution value is equal to the upper bound of the continuous variable */
323 varsolval = SCIPgetSolVal(scip, sol, var);
324 if( SCIPisFeasEQ(scip, SCIPvarGetUbLocal(var), varsolval) )
325 goto VUB;
326
327 if( nvlb == 0 )
328 goto VUB;
329
330 /* get variable lower variable bounds information */
331 vlbvars = SCIPvarGetVlbVars(var);
332 vlbcoefs = SCIPvarGetVlbCoefs(var);
333 vlbconsts = SCIPvarGetVlbConstants(var);
334
335 maxabscoef = 0.0;
336 maxabsind = -1;
337 maxabssign = 0;
338
339 lb = SCIPvarGetLbGlobal(var);
340 if( sepadata->uselocalbounds && SCIPisLT(scip, lb, SCIPvarGetLbLocal(var)) )
341 {
342 /* this is a lcoal cut */
343 islocallb = TRUE;
344 lb = SCIPvarGetLbLocal(var);
345 }
346
347 #ifdef SCIP_DEBUG
348 for( j = 0; j < nvlb; j++ )
349 {
350 SCIP_Real tmplb;
351
352 if( SCIPvarIsBinary(vlbvars[j]) && SCIPvarGetProbindex(vlbvars[j]) >= 0 )
353 {
354 tmplb = (vlbcoefs[j] > 0) ? vlbconsts[j] : (vlbconsts[j] + vlbcoefs[j]);
355 assert( SCIPisFeasLE(scip, tmplb, lb) );
356 }
357 }
358 #endif
359
360 assert( SCIPisFeasLE(scip, lb, SCIPvarGetUbLocal(var)) );
361
362 /* extract the useful variable bounds information (binary and nonredundant) */
363 for( j = 0; j < nvlb; j++ )
364 {
365 /* consider only active and binary variables */
366 if( SCIPvarIsBinary(vlbvars[j]) && SCIPvarGetProbindex(vlbvars[j]) >= 0 )
367 {
368 SCIP_Real maxactivity;
369 SCIP_Real coef;
370
371 maxactivity = (vlbcoefs[j] > 0) ? (vlbconsts[j] + vlbcoefs[j]) : vlbconsts[j];
372
373 /* skip redundant variable bound constraints */
374 if( SCIPisFeasLE(scip, maxactivity, lb) )
375 continue;
376
377 if( vlbcoefs[j] > 0 )
378 {
379 coef = maxactivity - lb;
380 vlbmixsigns[vlbmixsize] = 0;
381 }
382 else
383 {
384 coef = lb - maxactivity;
385 vlbmixsigns[vlbmixsize] = 1;
386 }
387 assert(vlbmixsize <= nvars);
388
389 vlbmixcoefs[vlbmixsize] = REALABS(coef);
390 vlbmixinds[vlbmixsize] = SCIPvarGetProbindex(vlbvars[j]);
391 vlbmixsols[vlbmixsize] = (! vlbmixsigns[vlbmixsize]) ? SCIPgetSolVal(scip, sol, vlbvars[j]) : (1.0 - SCIPgetSolVal(scip, sol, vlbvars[j]));
392
393 /* update the maximal coefficient if needed */
394 if( maxabscoef < vlbmixcoefs[vlbmixsize] )
395 {
396 maxabscoef = vlbmixcoefs[vlbmixsize];
397 maxabsind = vlbmixinds[vlbmixsize];
398 maxabssign = vlbmixsigns[vlbmixsize];
399 }
400
401 ++vlbmixsize;
402
403 /* stop if size is exceeded; possibly ignore redundant variable bounds */
404 if( vlbmixsize >= nmaxvars )
405 break;
406 }
407 }
408 assert( vlbmixsize <= nmaxvars );
409
410 /* stop if no variable lower bounds information exists */
411 if( vlbmixsize == 0 )
412 goto VUB;
413
414 /* stop if the current solution value of the transformed continuous variable is larger than the maximal coefficient */
415 if( SCIPisFeasGT(scip, varsolval - lb, maxabscoef) )
416 goto VUB;
417
418 /* sort the solution values in non-increasing order */
419 SCIPsortDownRealRealIntInt(vlbmixsols, vlbmixcoefs, vlbmixinds, vlbmixsigns, vlbmixsize);
420
421 /* add the continuous variable */
422 cutcoefs[cutnnz] = -1;
423 cutinds[cutnnz] = SCIPvarGetProbindex(var);
424 cutrhs = -lb;
425 cutnnz++;
426
427 activity = -(varsolval - lb);
428 lastcoef = 0.0;
429
430 /* loop over the variables and add the variable to the cut if its coefficient is larger than that of the last variable */
431 for( j = 0; j < vlbmixsize; j++ )
432 {
433 SCIP_Real solval;
434
435 solval = vlbmixsols[j];
436
437 /* stop if we can not find a violated cut or we reached 0 solution values */
438 if( activity + solval * (maxabscoef - lastcoef) < 0.0 || SCIPisFeasZero(scip, solval) )
439 break;
440 else
441 {
442 /* skip if we have already added a variable with bigger coefficient */
443 if( SCIPisLE(scip, vlbmixcoefs[j], lastcoef) )
444 continue;
445 else
446 {
447 activity += (vlbmixcoefs[j] - lastcoef) * solval;
448 if( vlbmixsigns[j] )
449 {
450 cutcoefs[cutnnz] = lastcoef - vlbmixcoefs[j];
451 cutrhs -= vlbmixcoefs[j] - lastcoef;
452 }
453 else
454 cutcoefs[cutnnz] = vlbmixcoefs[j] - lastcoef;
455 cutinds[cutnnz++] = vlbmixinds[j];
456 lastcoef = vlbmixcoefs[j];
457 }
458 }
459 }
460
461 /* add the variable with maximal coefficient to make sure the cut is strong enough */
462 if( SCIPisGT(scip, maxabscoef, lastcoef) )
463 {
464 /* do not update activity: either the corresponding solval is 0.0 or the cut will not become efficious */
465 if( maxabssign )
466 {
467 cutcoefs[cutnnz] = lastcoef - maxabscoef;
468 cutrhs -= maxabscoef - lastcoef;
469 }
470 else
471 cutcoefs[cutnnz] = maxabscoef - lastcoef;
472 cutinds[cutnnz++] = maxabsind;
473 }
474 assert( cutnnz <= nmaxvars + 1 );
475
476 /* add the cut if the violtion is good enough and the number of nonzero coefficients is larger than 2 */
477 if( SCIPisEfficacious(scip, activity) && cutnnz > 2 )
478 {
479 SCIP_CALL( addCut(scip, sepa, sol, cutcoefs, cutinds, cutnnz, cutrhs, islocallb, cutoff, ncuts) );
480 }
481
482 VUB:
483 if( nvub == 0 )
484 goto CONFLICT;
485
486 /* get variable upper bounds information */
487 vubvars = SCIPvarGetVubVars(var);
488 vubcoefs = SCIPvarGetVubCoefs(var);
489 vubconsts = SCIPvarGetVubConstants(var);
490
491 maxabscoef = 0.0;
492 maxabsind = -1;
493 maxabssign = 0;
494
495 /* stop if the lower bound is equal to the solution value of the continuous variable */
496 if( SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), varsolval) )
497 goto CONFLICT;
498
499 ub = SCIPvarGetUbGlobal(var);
500 if( sepadata->uselocalbounds && SCIPisGT(scip, ub, SCIPvarGetUbLocal(var)) )
501 {
502 /* this is a lcoal cut */
503 islocalub = TRUE;
504 ub = SCIPvarGetUbLocal(var);
505 }
506
507 #ifdef SCIP_DEBUG
508 for( j = 0; j < nvub; j++ )
509 {
510 SCIP_Real tmpub;
511
512 if( SCIPvarIsBinary(vubvars[j]) && SCIPvarGetProbindex(vubvars[j]) >= 0 )
513 {
514 tmpub = (vubcoefs[j] < 0) ? vubconsts[j] : (vubconsts[j] + vubcoefs[j]);
515 assert( SCIPisFeasGE(scip, tmpub, ub) );
516 }
517 }
518 #endif
519
520 assert( SCIPisFeasLE(scip, SCIPvarGetLbLocal(var), ub) );
521
522 /* extract the useful variable bounds information (binary and nonredundant) */
523 for( j = 0; j < nvub; j++ )
524 {
525 /* consider only active and binary variables */
526 if( SCIPvarIsBinary(vubvars[j]) && SCIPvarGetProbindex(vubvars[j]) >= 0 )
527 {
528 SCIP_Real minactivity;
529 SCIP_Real coef;
530
531 minactivity = (vubcoefs[j] < 0) ? (vubconsts[j] + vubcoefs[j]) : vubconsts[j];
532
533 /* skip redundant variable bound constraints */
534 if( SCIPisFeasLE(scip, ub, minactivity) )
535 continue;
536
537 if( vubcoefs[j] > 0 )
538 {
539 coef = ub - minactivity;
540 vubmixsigns[vubmixsize] = 1;
541 }
542 else
543 {
544 coef = minactivity - ub;
545 vubmixsigns[vubmixsize] = 0;
546 }
547
548 vubmixcoefs[vubmixsize] = REALABS(coef);
549 vubmixinds[vubmixsize] = SCIPvarGetProbindex(vubvars[j]);
550 vubmixsols[vubmixsize] = (! vubmixsigns[vubmixsize]) ? SCIPgetSolVal(scip, sol, vubvars[j]): (1.0 - SCIPgetSolVal(scip, sol, vubvars[j]));
551
552 /* update the maximal coefficient if needed */
553 if( maxabscoef < vubmixcoefs[vubmixsize] )
554 {
555 maxabscoef = vubmixcoefs[vubmixsize];
556 maxabsind = vubmixinds[vubmixsize];
557 maxabssign = vubmixsigns[vubmixsize];
558 }
559
560 ++vubmixsize;
561
562 /* stop if size is exceeded; possibly ignore redundant variable bounds */
563 if( vubmixsize >= nmaxvars )
564 break;
565 }
566 }
567 assert( vubmixsize <= nmaxvars );
568
569 /* stop if no variable upper bounds information exists */
570 if( vubmixsize == 0 )
571 goto CONFLICT;
572
573 /* stop if the current solution value of transformed continuous variable is larger than the maximal coefficient */
574 if( SCIPisFeasGT(scip, ub - varsolval, maxabscoef) )
575 goto CONFLICT;
576
577 /* sort the solution values in non-increasing order */
578 SCIPsortDownRealRealIntInt(vubmixsols, vubmixcoefs, vubmixinds, vubmixsigns, vubmixsize);
579
580 /* add the continuous variables */
581 cutnnz = 0;
582 cutcoefs[cutnnz] = 1;
583 cutinds[cutnnz] = SCIPvarGetProbindex(var);
584 cutrhs = ub;
585 cutnnz++;
586
587 activity = varsolval - ub;
588 lastcoef = 0.0;
589
590 for( j = 0; j < vubmixsize; j++ )
591 {
592 SCIP_Real solval;
593
594 solval = vubmixsols[j];
595
596 /* stop if we can not find a violated cut or we reached 0 solution values */
597 if( activity + solval * (maxabscoef - lastcoef) < 0.0 || SCIPisFeasZero(scip, solval) )
598 break;
599 else
600 {
601 /* skip if we have already added a variable with bigger coefficient */
602 if( SCIPisLE(scip, vubmixcoefs[j], lastcoef) )
603 continue;
604 else
605 {
606 activity += (vubmixcoefs[j] - lastcoef) * solval;
607 if( vubmixsigns[j] )
608 {
609 cutcoefs[cutnnz] = lastcoef - vubmixcoefs[j];
610 cutrhs -= vubmixcoefs[j] - lastcoef;
611 }
612 else
613 cutcoefs[cutnnz] = vubmixcoefs[j] - lastcoef;
614 cutinds[cutnnz++] = vubmixinds[j];
615 lastcoef = vubmixcoefs[j];
616 }
617 }
618 }
619
620 /* add the variable with maximal coefficient if needed */
621 if( SCIPisGT(scip, maxabscoef, lastcoef) )
622 {
623 /* do not update activity: either the corresponding solval is 0.0 or the cut will not become efficious */
624 if( maxabssign )
625 {
626 cutcoefs[cutnnz] = lastcoef - maxabscoef;
627 cutrhs -= maxabscoef - lastcoef;
628 }
629 else
630 cutcoefs[cutnnz] = maxabscoef - lastcoef;
631 cutinds[cutnnz++] = maxabsind;
632 }
633 assert( cutnnz <= nmaxvars + 1 );
634
635 /* add the cut if the violtion is good enough and the number of nonzero coefficients is larger than 2 */
636 if( SCIPisEfficacious(scip, activity) && cutnnz > 2 )
637 {
638 SCIP_CALL( addCut(scip, sepa, sol, cutcoefs, cutinds, cutnnz, cutrhs, islocalub, cutoff, ncuts) );
639 }
640
641 CONFLICT:
642 /* combine the variable lower bounds information and upper bounds information together to generate cuts */
643 /* stop if no useful variable lower (or upper) bounds information exists */
644 if( vlbmixsize == 0 || vubmixsize == 0 )
645 continue;
646
647 assert( lb != SCIP_INVALID ); /*lint !e777*/
648 assert( ub != SCIP_INVALID ); /*lint !e777*/
649
650 cutislocal = islocallb || islocalub;
651 for( j = 0; j < vlbmixsize; j++ )
652 {
653 SCIP_Real solval;
654
655 solval = vlbmixsols[j];
656
657 /* stop if no violated cut exists */
658 if( ! SCIPisEfficacious(scip, solval + vubmixsols[0] - 1.0) )
659 break;
660
661 for( k = 0; k < vubmixsize; k++ )
662 {
663 /* only consider the inequality if its violation is good enough */
664 if( SCIPisEfficacious(scip, solval + vubmixsols[k] - 1.0) )
665 {
666 SCIP_Real tmp;
667
668 tmp = lb + vlbmixcoefs[j] + vubmixcoefs[k] - ub;
669
670 /* add the cut if it is valid */
671 if( SCIPisEfficacious(scip, tmp) )
672 {
673 cutnnz = 2;
674 cutrhs = 1.0;
675 cutcoefs[0] = vlbmixsigns[j] ? -1.0 : 1.0;
676 cutcoefs[1] = vubmixsigns[k] ? -1.0 : 1.0;
677 cutinds[0] = vlbmixinds[j];
678 cutinds[1] = vubmixinds[k];
679 cutrhs = vlbmixsigns[j] ? (cutrhs - 1.0) : cutrhs;
680 cutrhs = vubmixsigns[k] ? (cutrhs - 1.0) : cutrhs;
681 SCIP_CALL( addCut(scip, sepa, sol, cutcoefs, cutinds, cutnnz, cutrhs, cutislocal, cutoff, ncuts) );
682 }
683 }
684 else
685 break;
686 }
687 }
688 }
689
690 /* free temporary memory */
691 SCIPfreeBufferArray(scip, &cutinds);
692 SCIPfreeBufferArray(scip, &cutcoefs);
693 SCIPfreeBufferArray(scip, &vubmixsigns);
694 SCIPfreeBufferArray(scip, &vubmixinds);
695 SCIPfreeBufferArray(scip, &vubmixsols);
696 SCIPfreeBufferArray(scip, &vubmixcoefs);
697 SCIPfreeBufferArray(scip, &vlbmixsigns);
698 SCIPfreeBufferArray(scip, &vlbmixinds);
699 SCIPfreeBufferArray(scip, &vlbmixsols);
700 SCIPfreeBufferArray(scip, &vlbmixcoefs);
701
702 return SCIP_OKAY;
703 }
704
705
706 /*
707 * Callback methods of separator
708 */
709
710 /** copy method for separator plugins (called when SCIP copies plugins) */
711 static
712 SCIP_DECL_SEPACOPY(sepaCopyMixing)
713 { /*lint --e{715}*/
714 assert(scip != NULL);
715 assert(sepa != NULL);
716 assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
717
718 /* call inclusion method of separator */
719 SCIP_CALL( SCIPincludeSepaMixing(scip) );
720
721 return SCIP_OKAY;
722 }
723
724 /** destructor of separator to free user data (called when SCIP is exiting) */
725 static
726 SCIP_DECL_SEPAFREE(sepaFreeMixing)
727 { /*lint --e{715}*/
728 SCIP_SEPADATA* sepadata;
729
730 assert(scip != NULL);
731 assert(sepa != NULL);
732 assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
733
734 /* get separation data and free it */
735 sepadata = SCIPsepaGetData(sepa);
736 assert(sepadata != NULL);
737 SCIPfreeBlockMemory(scip, &sepadata);
738
739 /* reset data pointer to NULL */
740 SCIPsepaSetData(sepa, NULL);
741
742 return SCIP_OKAY;
743 }
744
745
746 /** LP solution separation method of separator */
747 static
748 SCIP_DECL_SEPAEXECLP(sepaExeclpMixing)
749 { /*lint --e{715}*/
750 SCIP_SEPADATA* sepadata;
751 SCIP_Bool cutoff;
752 int nbinvars;
753 int nvars;
754 int ncuts;
755 int ncalls;
756
757 assert(sepa != NULL);
758 assert(scip != NULL);
759 assert(result != NULL);
760
761 *result = SCIP_DIDNOTRUN;
762 ncalls = SCIPsepaGetNCallsAtNode(sepa);
763 sepadata = SCIPsepaGetData(sepa);
764 assert(sepadata != NULL);
765
766 /* only call the mixing cut separator a given number of times at each node */
767 if( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot)
768 || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
769 return SCIP_OKAY;
770
771 /* gets numver of active problem variables and number of binary variables */
772 SCIP_CALL( SCIPgetVarsData(scip, NULL, &nvars, &nbinvars, NULL, NULL, NULL) );
773
774 /* if all the active problem variables are binary, stop */
775 if( nvars == nbinvars )
776 return SCIP_OKAY;
777
778 /* call the cut separation */
779 SCIP_CALL( separateCuts(scip, sepa, NULL, &cutoff, &ncuts) );
780
781 /* adjust result code */
782 if( cutoff )
783 *result = SCIP_CUTOFF;
784 else if( ncuts > 0 )
785 {
786 SCIPdebugMsg(scip, "mixing separator generated %d cuts.\n", ncuts);
787 *result = SCIP_SEPARATED;
788 }
789 else
790 *result = SCIP_DIDNOTFIND;
791
792 return SCIP_OKAY;
793 }
794
795 /** arbitrary primal solution separation method of separator */
796 static
797 SCIP_DECL_SEPAEXECSOL(sepaExecSolMixing)
798 { /*lint --e{715}*/
799 SCIP_SEPADATA* sepadata;
800 SCIP_Bool cutoff;
801 int nbinvars;
802 int nvars;
803 int ncuts;
804 int ncalls;
805
806 assert(sepa != NULL);
807 assert(scip != NULL);
808 assert(result != NULL);
809
810 *result = SCIP_DIDNOTRUN;
811 sepadata = SCIPsepaGetData(sepa);
812 assert(sepadata != NULL);
813
814 /* do not run if we have reached the maximal number of consecutive unsuccessful calls */
815 if( sepadata->nunsuccessful >= sepadata->maxnunsuccessful )
816 return SCIP_OKAY;
817
818 /* only call the mixing cut separator a given number of times at each node */
819 ncalls = SCIPsepaGetNCallsAtNode(sepa);
820 if( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot)
821 || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
822 return SCIP_OKAY;
823
824 /* gets numver of active problem variables and number of binary variables */
825 nvars = SCIPgetNVars(scip);
826 nbinvars = SCIPgetNBinVars(scip);
827
828 /* if all the active problem variables are binary, stop */
829 if( nvars == nbinvars )
830 return SCIP_OKAY;
831
832 /* call the cut separation */
833 SCIP_CALL( separateCuts(scip, sepa, sol, &cutoff, &ncuts) );
834
835 /* adjust result code */
836 if( cutoff )
837 {
838 sepadata->nunsuccessful = 0;
839 *result = SCIP_CUTOFF;
840 }
841 else if( ncuts > 0 )
842 {
843 SCIPdebugMsg(scip, "mixing separator generated %d cuts.\n", ncuts);
844 sepadata->nunsuccessful = 0;
845 *result = SCIP_SEPARATED;
846 }
847 else
848 {
849 ++sepadata->nunsuccessful;
850 *result = SCIP_DIDNOTFIND;
851 }
852
853 return SCIP_OKAY;
854 }
855
856
857 /*
858 * separator specific interface methods
859 */
860
861 /** creates the mixing separator and includes it in SCIP */
862 SCIP_RETCODE SCIPincludeSepaMixing(
863 SCIP* scip /**< SCIP data structure */
864 )
865 {
866 SCIP_SEPADATA* sepadata;
867 SCIP_SEPA* sepa;
868
869 /* create mixing separator data */
870 SCIP_CALL( SCIPallocBlockMemory(scip, &sepadata) );
871 assert(sepadata != NULL);
872 sepadata->nunsuccessful = 0;
873
874 /* include separator */
875 SCIP_CALL( SCIPincludeSepaBasic(scip, &sepa, SEPA_NAME, SEPA_DESC, SEPA_PRIORITY, SEPA_FREQ, SEPA_MAXBOUNDDIST,
876 SEPA_USESSUBSCIP, SEPA_DELAY,
877 sepaExeclpMixing, sepaExecSolMixing,
878 sepadata) );
879 assert(sepa != NULL);
880
881 /* set non-NULL pointers to callback methods */
882 SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyMixing) );
883 SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeMixing) );
884
885 /* add separator parameters */
886 SCIP_CALL( SCIPaddBoolParam(scip, "separating/mixing/uselocalbounds",
887 "Should local bounds be used?",
888 &sepadata->uselocalbounds, TRUE, DEFAULT_USELOCALBOUNDS, NULL, NULL) );
889
890 SCIP_CALL( SCIPaddBoolParam(scip, "separating/mixing/iscutsonints",
891 "Should general integer variables be used to generate cuts?",
892 &sepadata->iscutsonints, TRUE, DEFAULT_ISCUTSONINTS, NULL, NULL) );
893
894 SCIP_CALL( SCIPaddIntParam(scip, "separating/mixing/maxrounds",
895 "maximal number of mixing separation rounds per node (-1: unlimited)",
896 &sepadata->maxrounds, FALSE, DEFAULT_MAXROUNDS, -1, INT_MAX, NULL, NULL) );
897
898 SCIP_CALL( SCIPaddIntParam(scip, "separating/mixing/maxroundsroot",
899 "maximal number of mixing separation rounds in the root node (-1: unlimited)",
900 &sepadata->maxroundsroot, FALSE, DEFAULT_MAXROUNDSROOT, -1, INT_MAX, NULL, NULL) );
901
902 SCIP_CALL( SCIPaddIntParam(scip, "separating/mixing/maxnunsuccessful",
903 "maximal number of consecutive unsuccessful iterations",
904 &sepadata->maxnunsuccessful, FALSE, DEFAULT_MAXNUNSUCCESSFUL, -1, INT_MAX, NULL, NULL) );
905
906 return SCIP_OKAY;
907 }
908