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  assert(!SCIPisDualfeasZero(scip, rootredcost));
322 
323  rootsol = SCIPvarGetBestRootSol(var);
324  rootlpobjval = SCIPvarGetBestRootLPObjval(var);
325 
326  /* calculate reduced cost based bound */
327  newbd = rootsol + (cutoffbound - rootlpobjval) / rootredcost;
328 
329  if( SCIPisDualfeasPositive(scip, rootredcost) )
330  {
331  assert(SCIPisFeasLE(scip, rootsol, SCIPvarGetLbGlobal(var))); /* lb might have been increased in the meantime */
332 
333  /* strengthen upper bound */
334  SCIP_CALL( SCIPtightenVarUbGlobal(scip, var, newbd, FALSE, infeasible, tightened) );
335  }
336  else
337  {
338  assert(SCIPisDualfeasNegative(scip, rootredcost));
339  assert(SCIPisFeasGE(scip, rootsol, SCIPvarGetUbGlobal(var))); /* ub might have been decreased in the meantime */
340 
341  /* strengthen lower bound */
342  SCIP_CALL( SCIPtightenVarLbGlobal(scip, var, newbd, FALSE, infeasible, tightened) );
343  }
344 
345  return SCIP_OKAY;
346 }
347 
348 /** propagate binary variables with non-zero root reduced cost */
349 static
351  SCIP* scip, /**< SCIP data structure */
352  SCIP_PROPDATA* propdata, /**< propagator data structure */
353  SCIP_Real cutoffbound, /**< cutoff bound to use */
354  int* nchgbds, /**< pointer to store the number of bound changes */
355  SCIP_Bool* cutoff /**< pointer to store if a cutoff was detected */
356  )
357 {
358  SCIP_VAR** redcostvars;
359  int v;
360 
361  assert(!(*cutoff));
362 
363  /* the binary variables are stored in the beginning of the variable array; these variables are sorted w.r.t. cutoff
364  * bound which would lead to a fixing; that give us an abort criteria (see below)
365  */
366  redcostvars = propdata->redcostvars;
367  assert(redcostvars != NULL);
368 
369 #ifndef NDEBUG
370  /* check that the binary variables are correctly sorted
371  *
372  * @note In case the assertion fails it indicates that a new LP root solving arose after we initialized the
373  * propagator; The new LP solution destroyed the sorting of the binary variables since the reduced cost of the
374  * variables changed. This could lead to potentially missing a domain reductions. Currently, it is not possible to
375  * check if a new root LP was solved, changing the root reduced costs. This case, however, should not happen in the
376  * current SCIP version.
377  */
378  for( v = 1; v < propdata->nredcostbinvars; ++v )
379  assert(varCompRedcost(redcostvars[v-1], redcostvars[v]) == 1);
380 
381  /* check that the variables before glbfirstnonfixed are globally fixed */
382  for( v = 0; v < propdata->glbfirstnonfixed; ++v )
383  {
384  SCIP_VAR* var;
385 
386  var = redcostvars[v];
387  assert(var != NULL);
388 
389  assert(SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5);
390  }
391 #endif
392 
393  /* propagate binary variables */
394  for( v = propdata->glbfirstnonfixed; v < propdata->nredcostbinvars; ++v )
395  {
396  SCIP_VAR* var;
397  SCIP_Bool tightened;
398 
399  var = redcostvars[v];
400  assert(var != NULL);
401 
402  /* check if the variables is already globally fixed; if so continue with the next potential candidate */
403  if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5)
404  continue;
405 
406  /* try to tighten the variable bound */
407  SCIP_CALL( propagateRootRedcostVar(scip, var, cutoffbound, cutoff, &tightened) );
408 
409  if( tightened )
410  {
411  /* @note The variable might not be globally fixed right away since this would destroy the local internal data
412  * structure of a search node; the bound change is in that case pending; hence we cannot assert that the
413  * variable is globally fixed
414  */
415  assert(!(*cutoff));
416 
417  SCIPdebugMsg(scip, "globally fixed binary variable <%s> [%g,%g] bestroot sol <%g>, redcost <%g>, lpobj <%g>\n",
420 
421  (*nchgbds)++;
422  }
423  else
424  {
425  assert(!tightened);
426 
427  /* The binary variables are sorted in non-increasing manner w.r.t. their cutoff bound which would lead to a
428  * global fixing; That is, abs(rootredcost) + rootlpobjval. Depending on the sign of the reduced cost the
429  * following two cases can arise for binary variables which are not fixed globally yet:
430  *
431  * - redcost > 0 --> newub = 0.0 + (cutoffbound - lpobjval) / redcost --> newub = 0 <=> cutoffbound < redcost + lpobjval = sorting key
432  * - redcost < 0 --> newlb = 1.0 + (cutoffbound - lpobjval) / redcost --> newlb = 1 <=> cutoffbound < -redcost + lpobjval = sorting key
433  *
434  * Due to the order of the binary variables it follows if one binary variable cannot be fixed anymore all the
435  * remaining once can also not be fixed since these have only an smaller or equal cutoff bound which would lead
436  * to global fixing. Hence, we can break that loop.
437  *
438  * Note that variables with non-zero reduced cost are sitting at one of their bound. That is the lower one if
439  * the reduced cost are positive and the upper bound if the reduced cost are negative. For binary variables
440  * that is 0 for the lower bound and 1 for the upper bound.
441  */
442  SCIPdebugMsg(scip, "interrupt propagation for binary variables after %d from %d binary variables\n",
443  v, propdata->nredcostbinvars);
444 
445  if( *cutoff )
446  {
447  SCIPdebugMsg(scip, "detected cutoff: binary variable <%s> [%g,%g], redcost <%g>, rootsol <%g>, rootlpobjval <%g>\n",
450  }
451 
452  break;
453  }
454  }
455  /* store the index of the variable which is not globally fixed */
456  propdata->glbfirstnonfixed = v;
457 
458 #if 0 /* due to numerics it might be that the abort criteria did not work correctly, because the sorting mechanism may
459  * have evaluated variables with a really small difference in their reduced cost values but with really huge
460  * lpobjval as the same
461  */
462 #ifndef NDEBUG
463  /* check that the abort criteria works; that means none of the remaining binary variables can be fixed */
464  for( ; v < propdata->nredcostbinvars && !(*cutoff); ++v )
465  {
466  SCIP_VAR* var;
467  SCIP_Bool tightened;
468 
469  var = redcostvars[v];
470  assert(var != NULL);
471 
472  /* check if the variables is already globally fixed; if so continue with the potential candidate */
473  if( SCIPvarGetLbGlobal(var) > 0.5 || SCIPvarGetUbGlobal(var) < 0.5)
474  continue;
475 
476  /* try to tighten the variable bound */
477  SCIP_CALL( propagateRootRedcostVar(scip, var, cutoffbound, cutoff, &tightened) );
478  assert(!tightened);
479  assert(!(*cutoff));
480  }
481 #endif
482 #endif
483 
484  return SCIP_OKAY;
485 }
486 
487 /**@} */
488 
489 
490 /**@name Callback methods of propagator
491  *
492  * @{
493  */
494 
495 /** copy method for propagator plugins (called when SCIP copies plugins) */
496 static
497 SCIP_DECL_PROPCOPY(propCopyRootredcost)
498 { /*lint --e{715}*/
499  assert(scip != NULL);
500  assert(prop != NULL);
501  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
502 
503  /* call inclusion method of propagator */
505 
506  return SCIP_OKAY;
507 }
508 
509 /** destructor of propagator to free user data (called when SCIP is exiting) */
510 static
511 SCIP_DECL_PROPFREE(propFreeRootredcost)
512 { /*lint --e{715}*/
513  SCIP_PROPDATA* propdata;
515  /* free propagator data */
516  propdata = SCIPpropGetData(prop);
517  assert(propdata != NULL);
518  assert(propdata->redcostvars == NULL);
519 
520  SCIPfreeBlockMemory(scip, &propdata);
521  SCIPpropSetData(prop, NULL);
522 
523  return SCIP_OKAY;
524 }
525 
526 /** solving process deinitialization method of propagator (called before branch and bound process data is freed) */
527 static
528 SCIP_DECL_PROPEXITSOL(propExitsolRootredcost)
529 { /*lint --e{715}*/
530  SCIP_PROPDATA* propdata;
532  propdata = SCIPpropGetData(prop);
533  assert(propdata != NULL);
534 
535  /* reset propagator data structure */
536  SCIP_CALL( propdataExit(scip, propdata) );
537 
538  return SCIP_OKAY;
539 }
540 
541 /** execution method of propagator */
542 static
543 SCIP_DECL_PROPEXEC(propExecRootredcost)
544 { /*lint --e{715}*/
545  SCIP_PROPDATA* propdata;
546  SCIP_VAR** redcostvars;
547  SCIP_Real cutoffbound;
548  SCIP_Real lpobjval;
549  SCIP_Bool cutoff;
550  int nredcostvars;
551  int nchgbds;
552  int v;
553 
554  *result = SCIP_DIDNOTRUN;
555 
556  /* in case we have a zero objective fucntion, we skip the root reduced cost propagator */
557  if( SCIPgetNObjVars(scip) == 0 )
558  return SCIP_OKAY;
559 
560  /* propagator can only be applied during solving stage */
561  if( SCIPgetStage(scip) != SCIP_STAGE_SOLVING )
562  return SCIP_OKAY;
563 
564  /* the propagator should run in all nodes except the root node; for the root node the redcost propagator does
565  * the job already
566  */
567  if( SCIPgetDepth(scip) < 1 )
568  return SCIP_OKAY;
569 
570  /* first check root LP objective value if it exists */
571  lpobjval = SCIPgetLPRootObjval(scip);
572  if( lpobjval == SCIP_INVALID ) /*lint !e777*/
573  return SCIP_OKAY;
574 
575  /* do not run in probing mode since this propagator changes global variable bounds */
576  if( SCIPinProbing(scip) )
577  return SCIP_OKAY;
578 
579  /* do not run if propagation w.r.t. objective is not allowed */
580  if( !SCIPallowObjProp(scip) )
581  return SCIP_OKAY;
582 
583  /* get propagator data */
584  propdata = SCIPpropGetData(prop);
585  assert(propdata != NULL);
586 
587  /* do nothing if active pricer are present and force flag is not TRUE */
588  if( !propdata->force && SCIPgetNActivePricers(scip) > 0 )
589  return SCIP_OKAY;
590 
591  /* get current cutoff bound */
592  cutoffbound = SCIPgetCutoffbound(scip);
593 
594  /* reduced cost strengthening can only be applied, if we have a finite upper bound on the LP value */
595  if( SCIPisInfinity(scip, cutoffbound) )
596  return SCIP_OKAY;
597 
598  /* initialize propagator data structure */
599  SCIP_CALL( propdataInit(scip, propdata) );
600  assert(cutoffbound <= propdata->lastcutoffbound);
601 
602  if( cutoffbound == propdata->lastcutoffbound ) /*lint !e777*/
603  return SCIP_OKAY;
604 
605  /* get variables */
606  redcostvars = propdata->redcostvars;
607  nredcostvars = propdata->nredcostvars;
608 
609  /* since no variables has non-zero reduced cost do nothing */
610  if( nredcostvars == 0 )
611  return SCIP_OKAY;
612 
613  /* store cutoff bound to remember later that for that particular cutoff bound the propagation was already
614  * preformed
615  */
616  propdata->lastcutoffbound = cutoffbound;
617 
618  SCIPdebugMsg(scip, "searching for root reduced cost fixings\n");
619  SCIPdebugMsg(scip, "-> cutoffbound <%g>\n", cutoffbound);
620  SCIPdebugMsg(scip, "-> LP objective value <%g>\n", lpobjval);
621 
622  *result = SCIP_DIDNOTFIND;
623  nchgbds = 0;
624  cutoff = FALSE;
625 
626  /* propagate the binary variables with non-zero root reduced cost */
627  SCIP_CALL( propagateBinaryBestRootRedcost(scip, propdata, cutoffbound, &nchgbds, &cutoff) );
628 
629  if( !propdata->onlybinary )
630  {
631  /* check reduced costs for non-binary variables that were columns of the root LP */
632  for( v = propdata->nredcostbinvars; v < nredcostvars && !cutoff; ++v )
633  {
634  SCIP_VAR* var;
635  SCIP_Bool tightened;
636 
637  var = redcostvars[v];
638  assert(var != NULL);
639 
640  /* try to tighten the variable bound */
641  SCIP_CALL( propagateRootRedcostVar(scip, var, cutoffbound, &cutoff, &tightened) );
642 
643  if( tightened )
644  nchgbds++;
645  }
646  }
647 
648  /* evaluate propagation results */
649  if( cutoff )
650  {
651  /* we are done with solving since the cutoff is w.r.t. a global bound change; cutoff root node */
652  SCIP_CALL( SCIPcutoffNode(scip, SCIPgetRootNode(scip)) );
653  (*result) = SCIP_CUTOFF;
654  }
655  else if( nchgbds > 0 )
656  (*result) = SCIP_REDUCEDDOM;
657 
658  SCIPdebugMsg(scip, "tightened %d variable domains (%u cutoff)\n", nchgbds, cutoff);
659 
660  return SCIP_OKAY;
661 }
662 
663 /**@} */
664 
665 /**@name Interface methods
666  *
667  * @{
668  */
669 
670 /** creates the root node reduced cost strengthening propagator and includes it in SCIP */
672  SCIP* scip /**< SCIP data structure */
673  )
674 {
675  SCIP_PROPDATA* propdata;
676  SCIP_PROP* prop;
677 
678  /* create rootredcost propagator data */
679  SCIP_CALL( propdataCreate(scip, &propdata) );
680 
681  /* include propagator */
683  propExecRootredcost, propdata) );
684 
685  assert(prop != NULL);
686 
687  /* set optional callbacks via setter functions */
688  SCIP_CALL( SCIPsetPropCopy(scip, prop, propCopyRootredcost) );
689  SCIP_CALL( SCIPsetPropFree(scip, prop, propFreeRootredcost) );
690  SCIP_CALL( SCIPsetPropExitsol(scip, prop, propExitsolRootredcost) );
691 
693  "propagating/" PROP_NAME "/onlybinary",
694  "should only binary variables be propagated?",
695  &propdata->onlybinary, TRUE, DEFAULT_ONLYBINARY, NULL, NULL) );
697  "propagating/" PROP_NAME "/force",
698  "should the propagator be forced even if active pricer are present?",
699  &propdata->force, TRUE, DEFAULT_FORCE, NULL, NULL) );
700 
701  return SCIP_OKAY;
702 }
703 
704 /**@} */
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip.h:21892
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip.c:814
#define DEFAULT_FORCE
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
Definition: scip.c:42499
static SCIP_DECL_PROPEXITSOL(propExitsolRootredcost)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17166
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:18384
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16732
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46138
#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:5655
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
Definition: scip.c:40796
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:45816
#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:46324
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:21907
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:21890
SCIP_NODE * SCIPgetRootNode(SCIP *scip)
Definition: scip.c:40472
#define SCIPdebugMsg
Definition: scip.h:451
const char * SCIPgetProbName(SCIP *scip)
Definition: scip.c:10724
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17176
SCIP_Real SCIPvarGetBestRootLPObjval(SCIP_VAR *var)
Definition: var.c:13118
SCIP_RETCODE SCIPincludePropRootredcost(SCIP *scip)
void SCIPsortDownPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16552
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:23135
#define NULL
Definition: lpi_spx1.cpp:137
#define REALABS(x)
Definition: def.h:159
#define PROP_NAME
#define SCIP_CALL(x)
Definition: def.h:306
static SCIP_RETCODE propdataExit(SCIP *scip, SCIP_PROPDATA *propdata)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46112
SCIP_Bool SCIPisDualfeasNegative(SCIP *scip, SCIP_Real val)
Definition: scip.c:46348
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:42094
static SCIP_DECL_SORTPTRCOMP(varCompRedcost)
int SCIPvarCompare(SCIP_VAR *var1, SCIP_VAR *var2)
Definition: var.c:11249
SCIP_RETCODE SCIPsetPropCopy(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPCOPY((*propcopy)))
Definition: scip.c:7610
SCIP_Real SCIPvarGetBestRootRedcost(SCIP_VAR *var)
Definition: var.c:13084
int SCIPgetNObjVars(SCIP *scip)
Definition: scip.c:11859
static SCIP_DECL_PROPFREE(propFreeRootredcost)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:45827
#define PROP_FREQ
SCIP_RETCODE SCIPsetPropExitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXITSOL((*propexitsol)))
Definition: scip.c:7690
int SCIPgetNBinVars(SCIP *scip)
Definition: scip.c:11676
static void propdataReset(SCIP *scip, SCIP_PROPDATA *propdata)
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip.c:35033
const char * SCIPpropGetName(SCIP_PROP *prop)
Definition: prop.c:887
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11631
#define PROP_DESC
SCIP_Bool SCIPisDualfeasPositive(SCIP *scip, SCIP_Real val)
Definition: scip.c:46336
#define PROP_DELAY
static SCIP_DECL_PROPEXEC(propExecRootredcost)
SCIP_Real SCIPvarGetBestRootSol(SCIP_VAR *var)
Definition: var.c:13018
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip.c:11586
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:18350
#define SCIP_Real
Definition: def.h:135
struct SCIP_PropData SCIP_PROPDATA
Definition: type_prop.h:38
#define SCIP_INVALID
Definition: def.h:155
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPFREE((*propfree)))
Definition: scip.c:7626
#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:29022
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip.h:21910
SCIP_RETCODE SCIPtightenVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:23255
static SCIP_RETCODE propdataCreate(SCIP *scip, SCIP_PROPDATA **propdata)
#define PROP_TIMING
SCIP_Bool SCIPallowObjProp(SCIP *scip)
Definition: scip.c:25457
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:4176
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:7573