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