# SCIP

Solving Constraint Integer Programs

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-2023 Zuse Institute Berlin (ZIB) */
7 /* */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
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
74 #include "blockmemshell/memory.h"
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"
91 #include "scip/scip_solvingstats.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/implied 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 */
115 {
116  SCIP_Bool uselocalbounds; /**< should local bounds be used? */
117  SCIP_Bool iscutsonints; /**< should general/implied 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 */
129 static
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 {
143  char cutname[SCIP_MAXSTRLEN];
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 */
156  vars = SCIPgetVars(scip);
157
158  /* construct cut name */
159  (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "mix%" SCIP_LONGINT_FORMAT "_x%d", SCIPgetNLPs(scip), *ncuts);
160
161  /* create empty cut */
162  SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, cutname, -SCIPinfinity(scip), cutrhs,
163  cutislocal, FALSE, TRUE) );
164
165  /* cache the row extension and only flush them if the cut gets added */
166  SCIP_CALL( SCIPcacheRowExtensions(scip, cut) );
167
168  /* collect all non-zero coefficients */
169  for( v = 0; v < cutnnz; ++v )
170  {
171  SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[cutinds[v]], cutcoefs[v]) );
172  }
173
174  /* flush all changes before adding the cut */
175  SCIP_CALL( SCIPflushRowExtensions(scip, cut) );
176
177  if( SCIPisCutEfficacious(scip, sol, cut) )
178  {
179  /* set cut rank */
180  SCIProwChgRank(cut, 1);
181
182 #ifdef SCIP_DEBUG
183  SCIPdebugMsg(scip, "-> found cut (eff: %f): ", SCIPgetCutEfficacy(scip, sol, cut));
184  SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
185 #endif
186
187  if( cutislocal )
188  {
189  /* local cuts are added to the sepastore */
190  SCIP_CALL( SCIPaddRow(scip, cut, FALSE, cutoff) );
191  }
192  else
193  {
195  }
196  (*ncuts)++;
197  }
198
199  /* release the row */
200  SCIP_CALL( SCIPreleaseRow(scip, &cut) );
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  */
220 static
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 */
257  nmaxvars = SCIPgetNBinVars(scip);
258  if( nmaxvars <= 0 )
259  return SCIP_OKAY;
260
263
264  /* get the index of the first considered variable */
266  {
267  /* generate cuts based on all nonbinary variabels */
268  firstvar = SCIPgetNBinVars(scip);
269  }
270  else
271  {
272  /* only generate cuts based on continuous variables */
273  firstvar = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip) + SCIPgetNImplVars(scip);
274  }
275  nvars = SCIPgetNVars(scip);
276  if( firstvar == nvars )
277  return SCIP_OKAY;
278
279  vars = SCIPgetVars(scip);
280
281  /* allocate temporary memory */
282  SCIP_CALL( SCIPallocBufferArray(scip, &vlbmixcoefs, nmaxvars) );
283  SCIP_CALL( SCIPallocBufferArray(scip, &vlbmixsols, nmaxvars) );
284  SCIP_CALL( SCIPallocBufferArray(scip, &vlbmixinds, nmaxvars) );
285  SCIP_CALL( SCIPallocBufferArray(scip, &vlbmixsigns, nmaxvars) );
286  SCIP_CALL( SCIPallocBufferArray(scip, &vubmixcoefs, nmaxvars) );
287  SCIP_CALL( SCIPallocBufferArray(scip, &vubmixsols, nmaxvars) );
288  SCIP_CALL( SCIPallocBufferArray(scip, &vubmixinds, nmaxvars) );
289  SCIP_CALL( SCIPallocBufferArray(scip, &vubmixsigns, nmaxvars) );
290  SCIP_CALL( SCIPallocBufferArray(scip, &cutcoefs, nmaxvars + 1) );
291  SCIP_CALL( SCIPallocBufferArray(scip, &cutinds, nmaxvars + 1) );
292
293  for( i = firstvar; i < nvars; i++ )
294  {
295  SCIP_VAR** vlbvars;
296  SCIP_Real* vlbcoefs;
297  SCIP_Real* vlbconsts;
298  SCIP_VAR** vubvars;
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];
320  assert( SCIPvarGetType(var) != SCIP_VARTYPE_BINARY );
321
322  if( SCIPvarGetProbindex(var) < 0 )
323  continue;
324
325  nvlb = SCIPvarGetNVlbs(var);
326  nvub = SCIPvarGetNVubs(var);
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 */
332  varsolval = SCIPgetSolVal(scip, sol, var);
333  if( SCIPisFeasEQ(scip, SCIPvarGetUbLocal(var), varsolval) )
334  goto VUB;
335
336  if( nvlb == 0 )
337  goto VUB;
338
339  /* get variable lower variable bounds information */
340  vlbvars = SCIPvarGetVlbVars(var);
341  vlbcoefs = SCIPvarGetVlbCoefs(var);
342  vlbconsts = SCIPvarGetVlbConstants(var);
343
344  maxabscoef = 0.0;
345  maxabsind = -1;
346  maxabssign = 0;
347
348  lb = SCIPvarGetLbGlobal(var);
349  if( sepadata->uselocalbounds && SCIPisLT(scip, lb, SCIPvarGetLbLocal(var)) )
350  {
351  /* this is a lcoal cut */
352  islocallb = TRUE;
353  lb = SCIPvarGetLbLocal(var);
354  }
355
356 #ifdef SCIP_DEBUG
357  for( j = 0; j < nvlb; j++ )
358  {
359  SCIP_Real tmplb;
360
361  if( SCIPvarIsBinary(vlbvars[j]) && SCIPvarGetProbindex(vlbvars[j]) >= 0 )
362  {
363  tmplb = (vlbcoefs[j] > 0) ? vlbconsts[j] : (vlbconsts[j] + vlbcoefs[j]);
364  assert( SCIPisFeasLE(scip, tmplb, lb) );
365  }
366  }
367 #endif
368
369  assert( SCIPisFeasLE(scip, lb, SCIPvarGetUbLocal(var)) );
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 */
375  if( SCIPvarIsBinary(vlbvars[j]) && SCIPvarGetProbindex(vlbvars[j]) >= 0 )
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;
389  vlbmixsigns[vlbmixsize] = 0;
390  }
391  else
392  {
393  coef = lb - maxactivity;
394  vlbmixsigns[vlbmixsize] = 1;
395  }
396  assert(vlbmixsize <= nvars);
397
398  vlbmixcoefs[vlbmixsize] = REALABS(coef);
399  vlbmixinds[vlbmixsize] = SCIPvarGetProbindex(vlbvars[j]);
400  vlbmixsols[vlbmixsize] = (! vlbmixsigns[vlbmixsize]) ? SCIPgetSolVal(scip, sol, vlbvars[j]) : (1.0 - SCIPgetSolVal(scip, sol, vlbvars[j]));
401
402  /* update the maximal coefficient if needed */
403  if( maxabscoef < vlbmixcoefs[vlbmixsize] )
404  {
405  maxabscoef = vlbmixcoefs[vlbmixsize];
406  maxabsind = vlbmixinds[vlbmixsize];
407  maxabssign = vlbmixsigns[vlbmixsize];
408  }
409
410  ++vlbmixsize;
411
412  /* stop if size is exceeded; possibly ignore redundant variable bounds */
413  if( vlbmixsize >= nmaxvars )
414  break;
415  }
416  }
417  assert( vlbmixsize <= nmaxvars );
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 */
424  if( SCIPisFeasGT(scip, varsolval - lb, maxabscoef) )
425  goto VUB;
426
427  /* sort the solution values in non-increasing order */
428  SCIPsortDownRealRealIntInt(vlbmixsols, vlbmixcoefs, vlbmixinds, vlbmixsigns, vlbmixsize);
429
430  /* add the continuous variable */
431  cutcoefs[cutnnz] = -1;
432  cutinds[cutnnz] = SCIPvarGetProbindex(var);
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 */
452  if( SCIPisLE(scip, vlbmixcoefs[j], lastcoef) )
453  continue;
454  else
455  {
456  activity += (vlbmixcoefs[j] - lastcoef) * solval;
457  if( vlbmixsigns[j] )
458  {
459  cutcoefs[cutnnz] = lastcoef - vlbmixcoefs[j];
460  cutrhs -= vlbmixcoefs[j] - lastcoef;
461  }
462  else
463  cutcoefs[cutnnz] = vlbmixcoefs[j] - lastcoef;
464  cutinds[cutnnz++] = vlbmixinds[j];
465  lastcoef = vlbmixcoefs[j];
466  }
467  }
468  }
469
470  /* add the variable with maximal coefficient to make sure the cut is strong enough */
471  if( SCIPisGT(scip, maxabscoef, lastcoef) )
472  {
473  /* do not update activity: either the corresponding solval is 0.0 or the cut will not become efficious */
474  if( maxabssign )
475  {
476  cutcoefs[cutnnz] = lastcoef - maxabscoef;
477  cutrhs -= maxabscoef - lastcoef;
478  }
479  else
480  cutcoefs[cutnnz] = maxabscoef - lastcoef;
481  cutinds[cutnnz++] = maxabsind;
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  {
488  SCIP_CALL( addCut(scip, sepa, sol, cutcoefs, cutinds, cutnnz, cutrhs, islocallb, cutoff, ncuts) );
489  }
490
491  VUB:
492  if( nvub == 0 )
493  goto CONFLICT;
494
495  /* get variable upper bounds information */
496  vubvars = SCIPvarGetVubVars(var);
497  vubcoefs = SCIPvarGetVubCoefs(var);
498  vubconsts = SCIPvarGetVubConstants(var);
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 */
505  if( SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), varsolval) )
506  goto CONFLICT;
507
508  ub = SCIPvarGetUbGlobal(var);
509  if( sepadata->uselocalbounds && SCIPisGT(scip, ub, SCIPvarGetUbLocal(var)) )
510  {
511  /* this is a lcoal cut */
512  islocalub = TRUE;
513  ub = SCIPvarGetUbLocal(var);
514  }
515
516 #ifdef SCIP_DEBUG
517  for( j = 0; j < nvub; j++ )
518  {
519  SCIP_Real tmpub;
520
521  if( SCIPvarIsBinary(vubvars[j]) && SCIPvarGetProbindex(vubvars[j]) >= 0 )
522  {
523  tmpub = (vubcoefs[j] < 0) ? vubconsts[j] : (vubconsts[j] + vubcoefs[j]);
524  assert( SCIPisFeasGE(scip, tmpub, ub) );
525  }
526  }
527 #endif
528
529  assert( SCIPisFeasLE(scip, SCIPvarGetLbLocal(var), ub) );
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 */
535  if( SCIPvarIsBinary(vubvars[j]) && SCIPvarGetProbindex(vubvars[j]) >= 0 )
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;
549  vubmixsigns[vubmixsize] = 1;
550  }
551  else
552  {
553  coef = minactivity - ub;
554  vubmixsigns[vubmixsize] = 0;
555  }
556
557  vubmixcoefs[vubmixsize] = REALABS(coef);
558  vubmixinds[vubmixsize] = SCIPvarGetProbindex(vubvars[j]);
559  vubmixsols[vubmixsize] = (! vubmixsigns[vubmixsize]) ? SCIPgetSolVal(scip, sol, vubvars[j]): (1.0 - SCIPgetSolVal(scip, sol, vubvars[j]));
560
561  /* update the maximal coefficient if needed */
562  if( maxabscoef < vubmixcoefs[vubmixsize] )
563  {
564  maxabscoef = vubmixcoefs[vubmixsize];
565  maxabsind = vubmixinds[vubmixsize];
566  maxabssign = vubmixsigns[vubmixsize];
567  }
568
569  ++vubmixsize;
570
571  /* stop if size is exceeded; possibly ignore redundant variable bounds */
572  if( vubmixsize >= nmaxvars )
573  break;
574  }
575  }
576  assert( vubmixsize <= nmaxvars );
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 */
583  if( SCIPisFeasGT(scip, ub - varsolval, maxabscoef) )
584  goto CONFLICT;
585
586  /* sort the solution values in non-increasing order */
587  SCIPsortDownRealRealIntInt(vubmixsols, vubmixcoefs, vubmixinds, vubmixsigns, vubmixsize);
588
589  /* add the continuous variables */
590  cutnnz = 0;
591  cutcoefs[cutnnz] = 1;
592  cutinds[cutnnz] = SCIPvarGetProbindex(var);
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 */
611  if( SCIPisLE(scip, vubmixcoefs[j], lastcoef) )
612  continue;
613  else
614  {
615  activity += (vubmixcoefs[j] - lastcoef) * solval;
616  if( vubmixsigns[j] )
617  {
618  cutcoefs[cutnnz] = lastcoef - vubmixcoefs[j];
619  cutrhs -= vubmixcoefs[j] - lastcoef;
620  }
621  else
622  cutcoefs[cutnnz] = vubmixcoefs[j] - lastcoef;
623  cutinds[cutnnz++] = vubmixinds[j];
624  lastcoef = vubmixcoefs[j];
625  }
626  }
627  }
628
629  /* add the variable with maximal coefficient if needed */
630  if( SCIPisGT(scip, maxabscoef, lastcoef) )
631  {
632  /* do not update activity: either the corresponding solval is 0.0 or the cut will not become efficious */
633  if( maxabssign )
634  {
635  cutcoefs[cutnnz] = lastcoef - maxabscoef;
636  cutrhs -= maxabscoef - lastcoef;
637  }
638  else
639  cutcoefs[cutnnz] = maxabscoef - lastcoef;
640  cutinds[cutnnz++] = maxabsind;
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  {
647  SCIP_CALL( addCut(scip, sepa, sol, cutcoefs, cutinds, cutnnz, cutrhs, islocalub, cutoff, ncuts) );
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
659  cutislocal = islocallb || islocalub;
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 */
680  if( SCIPisEfficacious(scip, tmp) )
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;
690  SCIP_CALL( addCut(scip, sepa, sol, cutcoefs, cutinds, cutnnz, cutrhs, cutislocal, cutoff, ncuts) );
691  }
692  }
693  else
694  break;
695  }
696  }
697  }
698
699  /* free temporary memory */
700  SCIPfreeBufferArray(scip, &cutinds);
701  SCIPfreeBufferArray(scip, &cutcoefs);
702  SCIPfreeBufferArray(scip, &vubmixsigns);
703  SCIPfreeBufferArray(scip, &vubmixinds);
704  SCIPfreeBufferArray(scip, &vubmixsols);
705  SCIPfreeBufferArray(scip, &vubmixcoefs);
706  SCIPfreeBufferArray(scip, &vlbmixsigns);
707  SCIPfreeBufferArray(scip, &vlbmixinds);
708  SCIPfreeBufferArray(scip, &vlbmixsols);
709  SCIPfreeBufferArray(scip, &vlbmixcoefs);
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) */
720 static
721 SCIP_DECL_SEPACOPY(sepaCopyMixing)
722 { /*lint --e{715}*/
723  assert(scip != NULL);
724  assert(sepa != NULL);
725  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
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) */
734 static
735 SCIP_DECL_SEPAFREE(sepaFreeMixing)
736 { /*lint --e{715}*/
738
739  assert(scip != NULL);
740  assert(sepa != NULL);
741  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
742
743  /* get separation data and free it */
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 */
756 static
757 SCIP_DECL_SEPAEXECLP(sepaExeclpMixing)
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
770  *result = SCIP_DIDNOTRUN;
771  ncalls = SCIPsepaGetNCallsAtNode(sepa);
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 */
781  SCIP_CALL( SCIPgetVarsData(scip, NULL, &nvars, &nbinvars, NULL, NULL, NULL) );
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 )
792  *result = SCIP_CUTOFF;
793  else if( ncuts > 0 )
794  {
795  SCIPdebugMsg(scip, "mixing separator generated %d cuts.\n", ncuts);
796  *result = SCIP_SEPARATED;
797  }
798  else
799  *result = SCIP_DIDNOTFIND;
800
801  return SCIP_OKAY;
802 }
803
804 /** arbitrary primal solution separation method of separator */
805 static
806 SCIP_DECL_SEPAEXECSOL(sepaExecSolMixing)
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
819  *result = SCIP_DIDNOTRUN;
822
823  /* do not run if we have reached the maximal number of consecutive unsuccessful calls */
825  return SCIP_OKAY;
826
827  /* only call the mixing cut separator a given number of times at each node */
828  ncalls = SCIPsepaGetNCallsAtNode(sepa);
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 */
834  nvars = SCIPgetNVars(scip);
835  nbinvars = SCIPgetNBinVars(scip);
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  {
848  *result = SCIP_CUTOFF;
849  }
850  else if( ncuts > 0 )
851  {
852  SCIPdebugMsg(scip, "mixing separator generated %d cuts.\n", ncuts);
854  *result = SCIP_SEPARATED;
855  }
856  else
857  {
859  *result = SCIP_DIDNOTFIND;
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 */
882
883  /* include separator */
886  sepaExeclpMixing, sepaExecSolMixing,
888  assert(sepa != NULL);
889
890  /* set non-NULL pointers to callback methods */
891  SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyMixing) );
892  SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeMixing) );
893
894  /* add separator parameters */
896  "Should local bounds be used?",
897  &sepadata->uselocalbounds, TRUE, DEFAULT_USELOCALBOUNDS, NULL, NULL) );
898
900  "Should general integer variables be used to generate cuts?",
901  &sepadata->iscutsonints, TRUE, DEFAULT_ISCUTSONINTS, NULL, NULL) );
902
904  "maximal number of mixing separation rounds per node (-1: unlimited)",
905  &sepadata->maxrounds, FALSE, DEFAULT_MAXROUNDS, -1, INT_MAX, NULL, NULL) );
906
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
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 DEFAULT_MAXROUNDSROOT
Definition: sepa_mixing.c:102
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2090
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_Real * SCIPvarGetVlbCoefs(SCIP_VAR *var)
Definition: var.c:18137
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1635
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for SCIP parameter handling
mixing cuts separator
public methods for memory management
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1658
int SCIPvarGetNVlbs(SCIP_VAR *var)
Definition: var.c:18115
public methods for implications, variable bounds, and cliques
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17923
#define SCIP_MAXSTRLEN
Definition: def.h:302
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1698
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17979
void SCIPsortDownRealRealIntInt(SCIP_Real *realarray1, SCIP_Real *realarray2, int *intarray1, int *intarray2, int len)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17444
SCIP_RETCODE SCIPincludeSepaMixing(SCIP *scip)
Definition: sepa_mixing.c:871
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1874
#define FALSE
Definition: def.h:96
static SCIP_DECL_SEPAFREE(sepaFreeMixing)
Definition: sepa_mixing.c:735
#define DEFAULT_MAXNUNSUCCESSFUL
Definition: sepa_mixing.c:111
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10788
#define TRUE
Definition: def.h:95
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
Definition: sepa.c:743
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
int SCIPvarGetNVubs(SCIP_VAR *var)
Definition: var.c:18157
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17613
public methods for problem variables
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
SCIP_VAR ** SCIPvarGetVlbVars(SCIP_VAR *var)
Definition: var.c:18127
#define SEPA_FREQ
Definition: sepa_mixing.c:104
#define SEPA_MAXBOUNDDIST
Definition: sepa_mixing.c:105
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
public methods for SCIP variables
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
Definition: scip_sepa.c:151
#define SCIPdebugMsg
Definition: scip_message.h:78
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
public methods for separator plugins
public methods for numerical tolerances
Definition: sepa.c:633
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)
Definition: sepa_mixing.c:130
public methods for querying solving statistics
public methods for the branch-and-bound tree
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17933
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip_cut.c:117
#define SEPA_PRIORITY
Definition: sepa_mixing.c:103
#define SEPA_NAME
Definition: sepa_mixing.c:99
#define SEPA_DESC
Definition: sepa_mixing.c:100
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
Definition: sepa.c:880
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
Definition: scip_cut.c:135
SCIP_Real * SCIPvarGetVubConstants(SCIP_VAR *var)
Definition: var.c:18189
Definition: sepa.c:643
#define NULL
Definition: lpi_spx1.cpp:164
#define REALABS(x)
Definition: def.h:210
#define SCIP_CALL(x)
Definition: def.h:394
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real * SCIPvarGetVlbConstants(SCIP_VAR *var)
Definition: var.c:18147
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define DEFAULT_USELOCALBOUNDS
Definition: sepa_mixing.c:109
SCIP_Real * SCIPvarGetVubCoefs(SCIP_VAR *var)
Definition: var.c:18179
static SCIP_DECL_SEPAEXECLP(sepaExeclpMixing)
Definition: sepa_mixing.c:757
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:250
#define DEFAULT_MAXROUNDS
Definition: sepa_mixing.c:101
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
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
public data structures and miscellaneous methods
static SCIP_DECL_SEPACOPY(sepaCopyMixing)
Definition: sepa_mixing.c:721
#define SCIP_Bool
Definition: def.h:93
int SCIPgetNImplVars(SCIP *scip)
Definition: scip_prob.c:2135
#define SEPA_DELAY
Definition: sepa_mixing.c:107
Definition: scip_cut.c:361
public methods for LP management
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
SCIP_Real SCIPgetCutEfficacy(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip_cut.c:94
public methods for cuts and aggregation rows
#define DEFAULT_ISCUTSONINTS
Definition: sepa_mixing.c:110
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2045
public methods for the LP relaxation, rows and columns
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:2000
static SCIP_RETCODE separateCuts(SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_Bool *cutoff, int *ncuts)
Definition: sepa_mixing.c:221
public methods for branching rule plugins and branching
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1562
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
Definition: scip_sepa.c:167
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for solutions
void SCIProwChgRank(SCIP_ROW *row, int rank)
Definition: lp.c:17537
public methods for message output
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1955
#define SCIP_Real
Definition: def.h:186
public methods for message handling
static SCIP_DECL_SEPAEXECSOL(sepaExecSolMixing)
Definition: sepa_mixing.c:806
#define SCIP_INVALID
Definition: def.h:206
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2209
SCIP_VAR ** SCIPvarGetVubVars(SCIP_VAR *var)
Definition: var.c:18169
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17429
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17989
public methods for separators
SCIP_Longint SCIPgetNLPs(SCIP *scip)
public methods for global and local (sub)problems
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1361
#define SEPA_USESSUBSCIP
Definition: sepa_mixing.c:106