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