Scippy

SCIP

Solving Constraint Integer Programs

prop_rootredcost.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-2017 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 email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file prop_rootredcost.c
17  * @brief reduced cost strengthening using root node reduced costs and the cutoff bound
18  * @author Tobias Achterberg
19  * @author Stefan Heinz
20  *
21  * This propagator uses the root reduced cost to (globally) propagate against the cutoff bound. The propagator checks if
22  * the variables with non-zero root reduced cost can exceed the cutoff bound. If this is the case the corresponding
23  * bound can be tightened.
24  *
25  * The propagate is performed during the search any time a new cutoff bound (primal solution) is found.
26  *
27  * @todo do not sort the variables; just store the cutoff bound which leads to a fixing. If that appears loop over all
28  * variables and fix and store the next cutoff bound which leads to an fixing
29  * @todo resolve the root LP in case of repropagation and update root reduced costs use root LP counter to check if new
30  * best root combinations might be available
31  */
32 
33 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
34 
35 #include <assert.h>
36 #include <string.h>
37 
38 #include "scip/prop_rootredcost.h"
39 
40 /**@name Propagator properties
41  *
42  * @{
43  */
44 
45 #define PROP_NAME "rootredcost"
46 #define PROP_DESC "reduced cost strengthening using root node reduced costs and the cutoff bound"
47 #define PROP_TIMING SCIP_PROPTIMING_BEFORELP | SCIP_PROPTIMING_AFTERLPLOOP
48 #define PROP_PRIORITY +10000000 /**< propagator priority */
49 #define PROP_FREQ 1 /**< propagator frequency */
50 #define PROP_DELAY FALSE /**< should propagation method be delayed, if other propagators found reductions? */
51 
52 /**@} */
53 
54 /**@name Default parameter values
55  *
56  * @{
57  */
58 #define DEFAULT_ONLYBINARY FALSE /**< should only binary variables be propagated? */
59 #define DEFAULT_FORCE FALSE /**< should the propagator be forced even if active pricer are present? Note that
60  * the reductions are always valid, but installing an upper bound on priced
61  * variables may lead to problems in pricing (existing variables at their upper
62  * bound may be priced again since they may have negative reduced costs) */
63 
64 /**@} */
65 
66 
67 /*
68  * Data structures
69  */
70 
71 /** propagator data */
72 struct SCIP_PropData
73 {
74  SCIP_VAR** redcostvars; /**< variables with non-zero root reduced cost */
75  SCIP_Real lastcutoffbound; /**< cutoff bound for which the root reduced costs were already processed */
76  int nredcostvars; /**< number of variables with non-zero root reduced cost */
77  int nredcostbinvars; /**< number of binary variables with non-zero root reduced cost */
78  int glbfirstnonfixed; /**< index of first globally non-fixed binary variable */
79  SCIP_Bool initialized; /**< is the propagator data initialized */
80  SCIP_Bool onlybinary; /**< should only binary variables be propagated? */
81  SCIP_Bool force; /**< should the propagator be forced even if active pricer are present? */
82 };
83 
84 
85 /**@name Local methods
86  *
87  * @{
88  */
89 
90 /** reset structure memember of propagator data structure */
91 static
92 void propdataReset(
93  SCIP* scip, /**< SCIP data structure */
94  SCIP_PROPDATA* propdata /**< propagator data to reset */
95  )
96 {
97  propdata->redcostvars = NULL;
98  propdata->lastcutoffbound = SCIP_INVALID;
99  propdata->nredcostvars = 0;
100  propdata->nredcostbinvars = 0;
101  propdata->glbfirstnonfixed = 0;
102  propdata->initialized = FALSE;
103 }
104 
105 /** compare variables with non-zero reduced cost w.r.t.
106  * (i) the cutoff bound which would lead to a fixing
107  * (ii) variable problem index;
108  */
109 static
110 SCIP_DECL_SORTPTRCOMP(varCompRedcost)
111 {
112  SCIP_VAR* var1 = (SCIP_VAR*)elem1;
113  SCIP_VAR* var2 = (SCIP_VAR*)elem2;
114  SCIP_Real key1;
115  SCIP_Real key2;
116 
117  assert(SCIPvarIsBinary(var1));
118  assert(SCIPvarGetBestRootRedcost(var1) != 0.0);
119 
120  assert(SCIPvarIsBinary(var2));
121  assert(SCIPvarGetBestRootRedcost(var2) != 0.0);
122 
123  /* collect sorting key for both variables */
126 
127  if( key1 < key2 )
128  return -1;
129  else if( key1 > key2 )
130  return +1;
131 
132  /* second criteria use the problem index
133  *
134  * @note The problem index is unique. That means the resulting sorting is unique.
135  */
136  return SCIPvarCompare(var1, var2);
137 }
138 
139 /** create propagator data structure */
140 static
142  SCIP* scip, /**< SCIP data structure */
143  SCIP_PROPDATA** propdata /**< pointer to store the created propagator data */
144  )
145 {
146  SCIP_CALL( SCIPallocBlockMemory(scip, propdata) );
147 
148  propdataReset(scip, *propdata);
149 
150  return SCIP_OKAY;
151 }
152 
153 /** counts the number of variables with non-zero root reduced cost */
154 static
156  SCIP* scip, /**< SCIP data structure */
157  SCIP_VAR** vars, /**< variable array */
158  int nvars /**< number of variables */
159  )
160 {
161  int count;
162  int v;
163 
164  count = 0;
165 
166  /* count number of variables with non-zero root reduced cost */
167  for( v = 0; v < nvars; ++v )
168  {
169  SCIP_Real redcost;
170 
171  assert(vars[v] != NULL);
172 
173  redcost = SCIPvarGetBestRootRedcost(vars[v]);
174  if( !SCIPisDualfeasZero(scip, redcost) )
175  count++;
176  }
177 
178  return count;
179 }
180 
181 /** free propagator data */
182 static
184  SCIP* scip, /**< SCIP data structure */
185  SCIP_PROPDATA* propdata /**< propagator data */
186  )
187 {
188  int v;
189 
190  /* release all variables */
191  for( v = 0; v < propdata->nredcostvars; ++v )
192  {
193  SCIP_CALL( SCIPreleaseVar(scip, &propdata->redcostvars[v]) );
194  }
195 
196  /* free memory for non-zero reduced cost variables */
197  SCIPfreeBlockMemoryArrayNull(scip, &propdata->redcostvars, propdata->nredcostvars);
198 
199  propdataReset(scip, propdata);
200 
201  return SCIP_OKAY;
202 }
203 
204 /** initializate the propagator */
205 static
207  SCIP* scip, /**< SCIP data structure */
208  SCIP_PROPDATA* propdata /**< propagator data */
209  )
210 {
211  SCIP_VAR** vars;
212  int nvars;
213  int nbinvars;
214  int nredcostvars;
215  int nredcostbinvars;
216  int v;
217 
218  assert(scip != NULL);
219  assert(propdata != NULL);
220 
221  /* check if the propagator data structure is already initialized */
222  if( propdata->initialized )
223  return SCIP_OKAY;
224 
225  /* get problem variables */
226  vars = SCIPgetVars(scip);
227  nvars = SCIPgetNVars(scip);
228  nbinvars = SCIPgetNBinVars(scip);
229 
230  /* count binary variables with non-zero root reduced cost */
231  nredcostbinvars = countNonZeroRootRedcostVars(scip, vars, nbinvars);
232  SCIPdebugMsg(scip, "There are %d (poor) binary variables with non-zero root reduced cost <%s>.\n", nredcostbinvars, SCIPgetProbName(scip));
233 
234  /* count non-binary variables with non-zero root reduced cost */
235  nredcostvars = countNonZeroRootRedcostVars(scip, &vars[nbinvars], nvars - nbinvars);
236 
237  nredcostvars += nredcostbinvars;
238 
239  /* collect the variables with non-zero reduced costs */
240  if( nredcostvars > 0 )
241  {
242  int k;
243 
244  k = 0;
245  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->redcostvars, nredcostvars) );
246 
247  SCIPdebugMsg(scip, "Store non-zero root reduced cost variables at address <%p>.\n", (void*)propdata->redcostvars);
248 
249  for( v = 0; v < nvars; ++v )
250  {
251  SCIP_Real redcost;
252  SCIP_VAR* var;
253 
254  var = vars[v];
255  redcost = SCIPvarGetBestRootRedcost(var);
256 
257  if( SCIPisDualfeasZero(scip, redcost) )
258  continue;
259 
260  assert(k < nredcostvars);
261 
262  /* check if one of the non-binary variables is implicit binary */
263  if( k >= nredcostbinvars && SCIPvarIsBinary(var) )
264  {
265  /* move the first non-binary variable to end of the array */
266  propdata->redcostvars[k] = propdata->redcostvars[nredcostbinvars];
267 
268  /* place the binary variable at the end of the binary section */
269  propdata->redcostvars[nredcostbinvars] = var;
270  nredcostbinvars++;
271  }
272  else
273  propdata->redcostvars[k] = var;
274 
275  /* captures the variable */
276  SCIP_CALL( SCIPcaptureVar(scip, var) ) ;
277 
278  k++;
279 
280  /* check if already visited all variable with non-zero redcostective coefficient */
281  if( k == nredcostvars )
282  break;
283  }
284 
285  /* sort binary variables with respect to their cutoff bound which would lead to an fixing; this order can be used
286  * to efficiently propagate the binary variables
287  */
288  SCIPsortDownPtr((void**)propdata->redcostvars, varCompRedcost, nredcostbinvars);
289 
290  assert(k == nredcostvars);
291 
292  SCIPdebugMsg(scip, "variables with non-zero redcostective coefficient: %d binaries, %d non-binaries\n", nredcostbinvars, nredcostvars - nredcostbinvars);
293  }
294 
295  propdata->nredcostvars = nredcostvars;
296  propdata->nredcostbinvars = nredcostbinvars;
297  propdata->glbfirstnonfixed = 0;
298  propdata->lastcutoffbound = SCIPinfinity(scip);
299  propdata->initialized = TRUE;
300 
301  return SCIP_OKAY;
302 }
303 
304 /** propagates the root reduced cost against the cutoff bound for the given variable */
305 static
307  SCIP* scip, /**< SCIP data structure */
308  SCIP_VAR* var, /**< variable to propagate */
309  SCIP_Real cutoffbound, /**< cutoff bound to use */
310  SCIP_Bool* infeasible, /**< pointer to store whether the new domain is empty */
311  SCIP_Bool* tightened /**< pointer to store if the bound was tightened */
312  )
313 {
314  SCIP_Real rootsol;
315  SCIP_Real rootredcost;
316  SCIP_Real rootlpobjval;
317  SCIP_Real newbd;
318 
319  rootredcost = SCIPvarGetBestRootRedcost(var);
320  assert(rootredcost != SCIP_INVALID); /*lint !e777*/
321 
322  /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
323  * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
324  * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
325  * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect.
326  */
327  assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasZero(scip, rootredcost));
328 
329  rootsol = SCIPvarGetBestRootSol(var);
330  rootlpobjval = SCIPvarGetBestRootLPObjval(var);
331 
332  /* calculate reduced cost based bound */
333  newbd = rootsol + (cutoffbound - rootlpobjval) / rootredcost;
334 
335  if( SCIPisDualfeasPositive(scip, rootredcost) )
336  {
337  assert(SCIPisFeasLE(scip, rootsol, SCIPvarGetLbGlobal(var))); /* lb might have been increased in the meantime */
338 
339  /* strengthen upper bound */
340  SCIP_CALL( SCIPtightenVarUbGlobal(scip, var, newbd, FALSE, infeasible, tightened) );
341  }
342  else
343  {
344  assert(!SCIPisLPDualReliable(scip) || SCIPisDualfeasNegative(scip, rootredcost));
345  assert(SCIPisFeasGE(scip, rootsol, SCIPvarGetUbGlobal(var))); /* ub might have been decreased in the meantime */
346 
347  /* strengthen lower bound */
348  SCIP_CALL( SCIPtightenVarLbGlobal(scip, var, newbd, FALSE, infeasible, tightened) );
349  }
350 
351  return SCIP_OKAY;
352 }
353 
354 /** propagate binary variables with non-zero root reduced cost */
355 static
357  SCIP* scip, /**< SCIP data structure */
358  SCIP_PROPDATA* propdata, /**< propagator data structure */
359  SCIP_Real cutoffbound, /**< cutoff bound to use */
360  int* nchgbds, /**< pointer to store the number of bound changes */
361  SCIP_Bool* cutoff /**< pointer to store if a cutoff was detected */
362  )
363 {
364  SCIP_VAR** redcostvars;
365  int v;
366 
367  assert(!(*cutoff));
368 
369  /* the binary variables are stored in the beginning of the variable array; these variables are sorted w.r.t. cutoff
370  * bound which would lead to a fixing; that give us an abort criteria (see below)
371  */
372  redcostvars = propdata->redcostvars;
373  assert(redcostvars != NULL);
374 
375 #ifndef NDEBUG
376  /* check that the binary variables are correctly sorted
377  *
378  * @note In case the assertion fails it indicates that a new LP root solving arose after we initialized the
379  * propagator; The new LP solution destroyed the sorting of the binary variables since the reduced cost of the
380  * variables changed. This could lead to potentially missing a domain reductions. Currently, it is not possible to
381  * check if a new root LP was solved, changing the root reduced costs. This case, however, should not happen in the
382  * current SCIP version.
383  */
384  for( v = 1; v < propdata->nredcostbinvars; ++v )
385  assert(varCompRedcost(redcostvars[v-1], redcostvars[v]) == 1);
386 
387  /* check that the variables before glbfirstnonfixed are globally fixed */
388  for( v = 0; v < propdata->glbfirstnonfixed; ++v )
389  {
390  SCIP_VAR* var;
391 
392  var = redcostvars[v];
393  assert(var != NULL);
394 
395  assert(SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5);
396  }
397 #endif
398 
399  /* propagate binary variables */
400  for( v = propdata->glbfirstnonfixed; v < propdata->nredcostbinvars; ++v )
401  {
402  SCIP_VAR* var;
403  SCIP_Bool tightened;
404 
405  var = redcostvars[v];
406  assert(var != NULL);
407 
408  /* check if the variables is already globally fixed; if so continue with the next potential candidate */
409  if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5)
410  continue;
411 
412  /* try to tighten the variable bound */
413  SCIP_CALL( propagateRootRedcostVar(scip, var, cutoffbound, cutoff, &tightened) );
414 
415  if( tightened )
416  {
417  /* @note The variable might not be globally fixed right away since this would destroy the local internal data
418  * structure of a search node; the bound change is in that case pending; hence we cannot assert that the
419  * variable is globally fixed
420  */
421  assert(!(*cutoff));
422 
423  SCIPdebugMsg(scip, "globally fixed binary variable <%s> [%g,%g] bestroot sol <%g>, redcost <%g>, lpobj <%g>\n",
426 
427  (*nchgbds)++;
428  }
429  else
430  {
431  assert(!tightened);
432 
433  /* The binary variables are sorted in non-increasing manner w.r.t. their cutoff bound which would lead to a
434  * global fixing; That is, abs(rootredcost) + rootlpobjval. Depending on the sign of the reduced cost the
435  * following two cases can arise for binary variables which are not fixed globally yet:
436  *
437  * - redcost > 0 --> newub = 0.0 + (cutoffbound - lpobjval) / redcost --> newub = 0 <=> cutoffbound < redcost + lpobjval = sorting key
438  * - redcost < 0 --> newlb = 1.0 + (cutoffbound - lpobjval) / redcost --> newlb = 1 <=> cutoffbound < -redcost + lpobjval = sorting key
439  *
440  * Due to the order of the binary variables it follows if one binary variable cannot be fixed anymore all the
441  * remaining once can also not be fixed since these have only an smaller or equal cutoff bound which would lead
442  * to global fixing. Hence, we can break that loop.
443  *
444  * Note that variables with non-zero reduced cost are sitting at one of their bound. That is the lower one if
445  * the reduced cost are positive and the upper bound if the reduced cost are negative. For binary variables
446  * that is 0 for the lower bound and 1 for the upper bound.
447  */
448  SCIPdebugMsg(scip, "interrupt propagation for binary variables after %d from %d binary variables\n",
449  v, propdata->nredcostbinvars);
450 
451  if( *cutoff )
452  {
453  SCIPdebugMsg(scip, "detected cutoff: binary variable <%s> [%g,%g], redcost <%g>, rootsol <%g>, rootlpobjval <%g>\n",
456  }
457 
458  break;
459  }
460  }
461  /* store the index of the variable which is not globally fixed */
462  propdata->glbfirstnonfixed = v;
463 
464 #if 0 /* due to numerics it might be that the abort criteria did not work correctly, because the sorting mechanism may
465  * have evaluated variables with a really small difference in their reduced cost values but with really huge
466  * lpobjval as the same
467  */
468 #ifndef NDEBUG
469  /* check that the abort criteria works; that means none of the remaining binary variables can be fixed */
470  for( ; v < propdata->nredcostbinvars && !(*cutoff); ++v )
471  {
472  SCIP_VAR* var;
473  SCIP_Bool tightened;
474 
475  var = redcostvars[v];
476  assert(var != NULL);
477 
478  /* check if the variables is already globally fixed; if so continue with the potential candidate */
479  if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5)
480  continue;
481 
482  /* try to tighten the variable bound */
483  SCIP_CALL( propagateRootRedcostVar(scip, var, cutoffbound, cutoff, &tightened) );
484  assert(!tightened);
485  assert(!(*cutoff));
486  }
487 #endif
488 #endif
489 
490  return SCIP_OKAY;
491 }
492 
493 /**@} */
494 
495 
496 /**@name Callback methods of propagator
497  *
498  * @{
499  */
500 
501 /** copy method for propagator plugins (called when SCIP copies plugins) */
502 static
503 SCIP_DECL_PROPCOPY(propCopyRootredcost)
504 { /*lint --e{715}*/
505  assert(scip != NULL);
506  assert(prop != NULL);
507  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
508 
509  /* call inclusion method of propagator */
511 
512  return SCIP_OKAY;
513 }
514 
515 /** destructor of propagator to free user data (called when SCIP is exiting) */
516 static
517 SCIP_DECL_PROPFREE(propFreeRootredcost)
518 { /*lint --e{715}*/
519  SCIP_PROPDATA* propdata;
521  /* free propagator data */
522  propdata = SCIPpropGetData(prop);
523  assert(propdata != NULL);
524  assert(propdata->redcostvars == NULL);
525 
526  SCIPfreeBlockMemory(scip, &propdata);
527  SCIPpropSetData(prop, NULL);
528 
529  return SCIP_OKAY;
530 }
531 
532 /** solving process deinitialization method of propagator (called before branch and bound process data is freed) */
533 static
534 SCIP_DECL_PROPEXITSOL(propExitsolRootredcost)
535 { /*lint --e{715}*/
536  SCIP_PROPDATA* propdata;
538  propdata = SCIPpropGetData(prop);
539  assert(propdata != NULL);
540 
541  /* reset propagator data structure */
542  SCIP_CALL( propdataExit(scip, propdata) );
543 
544  return SCIP_OKAY;
545 }
546 
547 /** execution method of propagator */
548 static
549 SCIP_DECL_PROPEXEC(propExecRootredcost)
550 { /*lint --e{715}*/
551  SCIP_PROPDATA* propdata;
552  SCIP_VAR** redcostvars;
553  SCIP_Real cutoffbound;
554  SCIP_Real lpobjval;
555  SCIP_Bool cutoff;
556  int nredcostvars;
557  int nchgbds;
558  int v;
559 
560  *result = SCIP_DIDNOTRUN;
561 
562  /* in case we have a zero objective fucntion, we skip the root reduced cost propagator */
563  if( SCIPgetNObjVars(scip) == 0 )
564  return SCIP_OKAY;
565 
566  /* propagator can only be applied during solving stage */
567  if( SCIPgetStage(scip) != SCIP_STAGE_SOLVING )
568  return SCIP_OKAY;
569 
570  /* the propagator should run in all nodes except the root node; for the root node the redcost propagator does
571  * the job already
572  */
573  if( SCIPgetDepth(scip) < 1 )
574  return SCIP_OKAY;
575 
576  /* first check root LP objective value if it exists */
577  lpobjval = SCIPgetLPRootObjval(scip);
578  if( lpobjval == SCIP_INVALID ) /*lint !e777*/
579  return SCIP_OKAY;
580 
581  /* do not run in probing mode since this propagator changes global variable bounds */
582  if( SCIPinProbing(scip) )
583  return SCIP_OKAY;
584 
585  /* do not run if propagation w.r.t. objective is not allowed */
586  if( !SCIPallowObjProp(scip) )
587  return SCIP_OKAY;
588 
589  /* get propagator data */
590  propdata = SCIPpropGetData(prop);
591  assert(propdata != NULL);
592 
593  /* do nothing if active pricer are present and force flag is not TRUE */
594  if( !propdata->force && SCIPgetNActivePricers(scip) > 0 )
595  return SCIP_OKAY;
596 
597  /* get current cutoff bound */
598  cutoffbound = SCIPgetCutoffbound(scip);
599 
600  /* reduced cost strengthening can only be applied, if we have a finite upper bound on the LP value */
601  if( SCIPisInfinity(scip, cutoffbound) )
602  return SCIP_OKAY;
603 
604  /* initialize propagator data structure */
605  SCIP_CALL( propdataInit(scip, propdata) );
606  assert(cutoffbound <= propdata->lastcutoffbound);
607 
608  if( cutoffbound == propdata->lastcutoffbound ) /*lint !e777*/
609  return SCIP_OKAY;
610 
611  /* get variables */
612  redcostvars = propdata->redcostvars;
613  nredcostvars = propdata->nredcostvars;
614 
615  /* since no variables has non-zero reduced cost do nothing */
616  if( nredcostvars == 0 )
617  return SCIP_OKAY;
618 
619  /* store cutoff bound to remember later that for that particular cutoff bound the propagation was already
620  * preformed
621  */
622  propdata->lastcutoffbound = cutoffbound;
623 
624  SCIPdebugMsg(scip, "searching for root reduced cost fixings\n");
625  SCIPdebugMsg(scip, "-> cutoffbound <%g>\n", cutoffbound);
626  SCIPdebugMsg(scip, "-> LP objective value <%g>\n", lpobjval);
627 
628  *result = SCIP_DIDNOTFIND;
629  nchgbds = 0;
630  cutoff = FALSE;
631 
632  /* propagate the binary variables with non-zero root reduced cost */
633  SCIP_CALL( propagateBinaryBestRootRedcost(scip, propdata, cutoffbound, &nchgbds, &cutoff) );
634 
635  if( !propdata->onlybinary )
636  {
637  /* check reduced costs for non-binary variables that were columns of the root LP */
638  for( v = propdata->nredcostbinvars; v < nredcostvars && !cutoff; ++v )
639  {
640  SCIP_VAR* var;
641  SCIP_Bool tightened;
642 
643  var = redcostvars[v];
644  assert(var != NULL);
645 
646  /* try to tighten the variable bound */
647  SCIP_CALL( propagateRootRedcostVar(scip, var, cutoffbound, &cutoff, &tightened) );
648 
649  if( tightened )
650  nchgbds++;
651  }
652  }
653 
654  /* evaluate propagation results */
655  if( cutoff )
656  {
657  /* we are done with solving since the cutoff is w.r.t. a global bound change; cutoff root node */
658  SCIP_CALL( SCIPcutoffNode(scip, SCIPgetRootNode(scip)) );
659  (*result) = SCIP_CUTOFF;
660  }
661  else if( nchgbds > 0 )
662  (*result) = SCIP_REDUCEDDOM;
663 
664  SCIPdebugMsg(scip, "tightened %d variable domains (%u cutoff)\n", nchgbds, cutoff);
665 
666  return SCIP_OKAY;
667 }
668 
669 /**@} */
670 
671 /**@name Interface methods
672  *
673  * @{
674  */
675 
676 /** creates the root node reduced cost strengthening propagator and includes it in SCIP */
678  SCIP* scip /**< SCIP data structure */
679  )
680 {
681  SCIP_PROPDATA* propdata;
682  SCIP_PROP* prop;
683 
684  /* create rootredcost propagator data */
685  SCIP_CALL( propdataCreate(scip, &propdata) );
686 
687  /* include propagator */
689  propExecRootredcost, propdata) );
690 
691  assert(prop != NULL);
692 
693  /* set optional callbacks via setter functions */
694  SCIP_CALL( SCIPsetPropCopy(scip, prop, propCopyRootredcost) );
695  SCIP_CALL( SCIPsetPropFree(scip, prop, propFreeRootredcost) );
696  SCIP_CALL( SCIPsetPropExitsol(scip, prop, propExitsolRootredcost) );
697 
699  "propagating/" PROP_NAME "/onlybinary",
700  "should only binary variables be propagated?",
701  &propdata->onlybinary, TRUE, DEFAULT_ONLYBINARY, NULL, NULL) );
703  "propagating/" PROP_NAME "/force",
704  "should the propagator be forced even if active pricer are present?",
705  &propdata->force, TRUE, DEFAULT_FORCE, NULL, NULL) );
706 
707  return SCIP_OKAY;
708 }
709 
710 /**@} */
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip.h:22587
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip.c:821
#define DEFAULT_FORCE
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
Definition: scip.c:43447
static SCIP_DECL_PROPEXITSOL(propExitsolRootredcost)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17276
static int countNonZeroRootRedcostVars(SCIP *scip, SCIP_VAR **vars, int nvars)
reduced cost strengthening using root node reduced costs and the cutoff bound
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip.c:18760
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16842
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47344
#define DEFAULT_ONLYBINARY
#define FALSE
Definition: def.h:64
static SCIP_RETCODE propdataInit(SCIP *scip, SCIP_PROPDATA *propdata)
int SCIPgetNActivePricers(SCIP *scip)
Definition: scip.c:5718
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
Definition: scip.c:41741
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:47022
#define TRUE
Definition: def.h:63
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_Bool SCIPisDualfeasZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:47530
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:22602
SCIP_Bool SCIPisLPDualReliable(SCIP *scip)
Definition: scip.c:29326
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:22585
SCIP_NODE * SCIPgetRootNode(SCIP *scip)
Definition: scip.c:41417
#define SCIPdebugMsg
Definition: scip.h:455
const char * SCIPgetProbName(SCIP *scip)
Definition: scip.c:10885
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17286
SCIP_Real SCIPvarGetBestRootLPObjval(SCIP_VAR *var)
Definition: var.c:13222
SCIP_RETCODE SCIPincludePropRootredcost(SCIP *scip)
void SCIPsortDownPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16662
static SCIP_DECL_PROPCOPY(propCopyRootredcost)
SCIP_RETCODE SCIPtightenVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:23536
#define REALABS(x)
Definition: def.h:173
#define PROP_NAME
#define SCIP_CALL(x)
Definition: def.h:350
static SCIP_RETCODE propdataExit(SCIP *scip, SCIP_PROPDATA *propdata)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47318
SCIP_Bool SCIPisDualfeasNegative(SCIP *scip, SCIP_Real val)
Definition: scip.c:47554
static SCIP_RETCODE propagateBinaryBestRootRedcost(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Real cutoffbound, int *nchgbds, SCIP_Bool *cutoff)
static SCIP_RETCODE propagateRootRedcostVar(SCIP *scip, SCIP_VAR *var, SCIP_Real cutoffbound, SCIP_Bool *infeasible, SCIP_Bool *tightened)
#define SCIP_Bool
Definition: def.h:61
int SCIPgetDepth(SCIP *scip)
Definition: scip.c:43039
static SCIP_DECL_SORTPTRCOMP(varCompRedcost)
int SCIPvarCompare(SCIP_VAR *var1, SCIP_VAR *var2)
Definition: var.c:11353
SCIP_RETCODE SCIPsetPropCopy(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPCOPY((*propcopy)))
Definition: scip.c:7695
SCIP_Real SCIPvarGetBestRootRedcost(SCIP_VAR *var)
Definition: var.c:13188
int SCIPgetNObjVars(SCIP *scip)
Definition: scip.c:12034
static SCIP_DECL_PROPFREE(propFreeRootredcost)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:47033
#define PROP_FREQ
SCIP_RETCODE SCIPsetPropExitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXITSOL((*propexitsol)))
Definition: scip.c:7775
int SCIPgetNBinVars(SCIP *scip)
Definition: scip.c:11851
static void propdataReset(SCIP *scip, SCIP_PROPDATA *propdata)
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip.c:35830
const char * SCIPpropGetName(SCIP_PROP *prop)
Definition: prop.c:887
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11806
#define PROP_DESC
SCIP_Bool SCIPisDualfeasPositive(SCIP *scip, SCIP_Real val)
Definition: scip.c:47542
#define PROP_DELAY
static SCIP_DECL_PROPEXEC(propExecRootredcost)
SCIP_Real SCIPvarGetBestRootSol(SCIP_VAR *var)
Definition: var.c:13122
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip.c:11761
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:18726
#define SCIP_Real
Definition: def.h:149
struct SCIP_PropData SCIP_PROPDATA
Definition: type_prop.h:38
#define SCIP_INVALID
Definition: def.h:169
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPFREE((*propfree)))
Definition: scip.c:7711
#define PROP_PRIORITY
SCIP_PROPDATA * SCIPpropGetData(SCIP_PROP *prop)
Definition: prop.c:735
void SCIPpropSetData(SCIP_PROP *prop, SCIP_PROPDATA *propdata)
Definition: prop.c:745
SCIP_Real SCIPgetLPRootObjval(SCIP *scip)
Definition: scip.c:29491
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip.h:22605
SCIP_RETCODE SCIPtightenVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:23656
static SCIP_RETCODE propdataCreate(SCIP *scip, SCIP_PROPDATA **propdata)
#define PROP_TIMING
SCIP_Bool SCIPallowObjProp(SCIP *scip)
Definition: scip.c:25889
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.c:4239
SCIP_RETCODE SCIPincludePropBasic(SCIP *scip, SCIP_PROP **propptr, const char *name, const char *desc, int priority, int freq, SCIP_Bool delay, SCIP_PROPTIMING timingmask, SCIP_DECL_PROPEXEC((*propexec)), SCIP_PROPDATA *propdata)
Definition: scip.c:7658