Scippy

SCIP

Solving Constraint Integer Programs

prop_redcost.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-2014 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_redcost.c
17  * @brief propagator using the LP reduced cost and the cutoff bound
18  * @author Tobias Achterberg
19  * @author Stefan Heinz
20  * @author Matthias Miltenberger
21  * @author Michael Winkler
22  *
23  * This propagator uses the reduced cost of an optimal solved LP relaxation to propagate the variables against the
24  * cutoff bound.
25  */
26 
27 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
28 
29 #include <assert.h>
30 #include <string.h>
31 
32 #include "scip/prop_redcost.h"
33 
34 
35 /**@name Propagator properties
36  *
37  * @{
38  */
39 
40 #define PROP_NAME "redcost"
41 #define PROP_DESC "reduced cost strengthening propagator"
42 #define PROP_TIMING SCIP_PROPTIMING_DURINGLPLOOP | SCIP_PROPTIMING_AFTERLPLOOP
43 #define PROP_PRIORITY +1000000 /**< propagator priority */
44 #define PROP_FREQ 1 /**< propagator frequency */
45 #define PROP_DELAY FALSE /**< should propagation method be delayed, if other propagators found reductions? */
46 
47 /**@} */
48 
49 
50 /**@name Default parameter values
51  *
52  * @{
53  */
54 
55 #define DEFAULT_CONTINUOUS FALSE /**< should reduced cost fixing be also applied to continuous variables? */
56 #define DEFAULT_USEIMPLICS TRUE /**< should implications be used to strength the reduced cost for binary variables? */
57 
58 /**@} */
59 
60 
61 /*
62  * Data structures
63  */
64 
65 
66 /** propagator data */
67 struct SCIP_PropData
68 {
69  SCIP_Bool continuous; /**< should reduced cost fixing be also applied to continuous variables? */
70  SCIP_Real maxredcost; /**< maximum reduced cost of a single binary variable */
71  SCIP_Bool usefullimplics; /**< are the implied reduced cost usefull */
72  SCIP_Bool useimplics; /**< should implications be used to strength the reduced cost for binary variables? */
73 };
74 
75 
76 /**@name Local methods
77  *
78  * @{
79  */
80 
81 /** propagate the given binary variable/column using the root reduced cost stored in the SCIP internal data structers
82  * and check if the implictions can be useful. Deppending on that implictions are used or not used during the search to
83  * strength the reduced costs.
84  */
85 static
86 SCIP_RETCODE propagateRootRedcostBinvar(
87  SCIP* scip, /**< SCIP data structure */
88  SCIP_PROPDATA* propdata, /**< propagator data structure */
89  SCIP_VAR* var, /**< variable to use for propagation */
90  SCIP_COL* col, /**< LP column of the variable */
91  SCIP_Real cutoffbound, /**< the current cutoff bound */
92  int* nchgbds /**< pointer to count the number of bound changes */
93  )
94 {
95  SCIP_Real rootredcost;
96  SCIP_Real rootsol;
97  SCIP_Real rootlpobjval;
98 
99  assert(SCIPgetDepth(scip) == 0);
100 
101  /* skip binary variable if it is locally fixed */
102  if( SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5 )
103  return SCIP_OKAY;
104 
105  rootredcost = SCIPvarGetBestRootRedcost(var);
106  rootsol = SCIPvarGetBestRootSol(var);
107  rootlpobjval = SCIPvarGetBestRootLPObjval(var);
108 
109  if( SCIPisFeasZero(scip, rootredcost) )
110  return SCIP_OKAY;
111 
112  assert(rootlpobjval != SCIP_INVALID); /*lint !e777*/
113 
114  if( rootsol > 0.5 )
115  {
116  assert(!SCIPisFeasPositive(scip, rootredcost));
117 
118  /* update maximum reduced cost of a single binary variable */
119  propdata->maxredcost = MAX(propdata->maxredcost, -rootredcost);
120 
121  if( rootlpobjval - rootredcost > cutoffbound )
122  {
123  SCIPdebugMessage("globally fix binary variable <%s> to 1.0\n", SCIPvarGetName(var));
124 
125  SCIP_CALL( SCIPchgVarLb(scip, var, 1.0) );
126  (*nchgbds)++;
127  return SCIP_OKAY;
128  }
129  }
130  else
131  {
132  assert(!SCIPisFeasNegative(scip, rootredcost));
133 
134  /* update maximum reduced cost of a single binary variable */
135  propdata->maxredcost = MAX(propdata->maxredcost, rootredcost);
136 
137  if( rootlpobjval + rootredcost > cutoffbound )
138  {
139  SCIPdebugMessage("globally fix binary variable <%s> to 0.0\n", SCIPvarGetName(var));
140 
141  SCIP_CALL( SCIPchgVarUb(scip, var, 0.0) );
142  (*nchgbds)++;
143  return SCIP_OKAY;
144  }
145  }
146 
147  /* evaluate if the implications are useful; the implications are seen to be useful if they provide an increase for
148  * the root reduced costs
149  */
150  if( !propdata->usefullimplics )
151  {
152  SCIP_Real lbredcost;
153  SCIP_Real ubredcost;
154 
155  lbredcost = SCIPgetVarImplRedcost(scip, var, FALSE);
156  assert(!SCIPisFeasPositive(scip, lbredcost));
157 
158  ubredcost = SCIPgetVarImplRedcost(scip, var, TRUE);
159  assert(!SCIPisFeasNegative(scip, ubredcost));
160 
161  switch( SCIPcolGetBasisStatus(col) )
162  {
163  case SCIP_BASESTAT_LOWER:
164  ubredcost -= SCIPgetVarRedcost(scip, var);
165  assert(!SCIPisFeasNegative(scip, ubredcost));
166  break;
167 
168  case SCIP_BASESTAT_UPPER:
169  lbredcost -= SCIPgetVarRedcost(scip, var);
170  assert(!SCIPisFeasPositive(scip, lbredcost));
171  break;
172 
173  case SCIP_BASESTAT_BASIC:
174  case SCIP_BASESTAT_ZERO:
175  default:
176  break;
177  }
178 
179  propdata->usefullimplics = (lbredcost < 0.0) || (ubredcost > 0.0);
180  }
181 
182  return SCIP_OKAY;
183 }
184 
185 /** propagate the given binary variable/column using the reduced cost */
186 static
187 SCIP_RETCODE propagateRedcostBinvar(
188  SCIP* scip, /**< SCIP data structure */
189  SCIP_PROPDATA* propdata, /**< propagator data structure */
190  SCIP_VAR* var, /**< variable to use for propagation */
191  SCIP_COL* col, /**< LP column of the variable */
192  SCIP_Real requiredredcost, /**< required reduset cost to be able to fix a binary variable */
193  int* nchgbds, /**< pointer to count the number of bound changes */
194  SCIP_Bool* cutoff /**< pointer to store if an cutoff was detected */
195  )
196 {
197  SCIP_Real lbredcost;
198  SCIP_Real ubredcost;
199  SCIP_Real redcost;
200 
201  /* skip binary variable if it is locally fixed */
202  if( SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5 )
203  return SCIP_OKAY;
204 
205  /* first use the redcost cost to fix the binary variable */
206  switch( SCIPcolGetBasisStatus(col) )
207  {
208  case SCIP_BASESTAT_LOWER:
209  redcost = SCIPgetVarRedcost(scip, var);
210  assert(!SCIPisFeasNegative(scip, redcost));
211 
212  if( redcost > requiredredcost )
213  {
214  SCIPdebugMessage("variable <%s>: fixed 0.0 (requiredredcost <%g>, redcost <%g>)\n",
215  SCIPvarGetName(var), requiredredcost, redcost);
216 
217  SCIP_CALL( SCIPchgVarUb(scip, var, 0.0) );
218  (*nchgbds)++;
219  return SCIP_OKAY;
220  }
221  break;
222 
223  case SCIP_BASESTAT_UPPER:
224  redcost = SCIPgetVarRedcost(scip, var);
225  assert(!SCIPisFeasPositive(scip, redcost));
226 
227  if( -redcost > requiredredcost )
228  {
229  SCIPdebugMessage("variable <%s>: fixed 1.0 (requiredredcost <%g>, redcost <%g>)\n",
230  SCIPvarGetName(var), requiredredcost, redcost);
231 
232  SCIP_CALL( SCIPchgVarLb(scip, var, 1.0) );
233  (*nchgbds)++;
234  return SCIP_OKAY;
235  }
236  break;
237 
238  case SCIP_BASESTAT_BASIC:
239  return SCIP_OKAY;
240 
241  case SCIP_BASESTAT_ZERO:
242  assert(SCIPisFeasZero(scip, SCIPgetColRedcost(scip, col)));
243  return SCIP_OKAY;
244 
245  default:
246  SCIPerrorMessage("invalid basis state\n");
247  return SCIP_INVALIDDATA;
248  }
249 
250  /* second, if the implications should be used and if the implications are seen to be promising used the implied
251  * reduced costs to fix the binary variable
252  */
253  if( propdata->useimplics && propdata->usefullimplics )
254  {
255  /* collect implied reduced costs if the variable would be fixed to its lower bound */
256  lbredcost = SCIPgetVarImplRedcost(scip, var, FALSE);
257  assert(!SCIPisFeasPositive(scip, lbredcost) || SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) );
258 
259  /* collect implied reduced costs if the variable would be fixed to its upper bound */
260  ubredcost = SCIPgetVarImplRedcost(scip, var, TRUE);
261  assert(!SCIPisFeasNegative(scip, ubredcost) || SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) );
262 
263  if( -lbredcost > requiredredcost && ubredcost > requiredredcost )
264  {
265  SCIPdebugMessage("variable <%s>: cutoff (requiredredcost <%g>, lbredcost <%g>, ubredcost <%g>)\n",
266  SCIPvarGetName(var), requiredredcost, lbredcost, ubredcost);
267 
268  (*cutoff) = TRUE;
269  }
270  else if( -lbredcost > requiredredcost )
271  {
272  SCIPdebugMessage("variable <%s>: fixed 1.0 (requiredredcost <%g>, redcost <%g>, lbredcost <%g>)\n",
273  SCIPvarGetName(var), requiredredcost, redcost, lbredcost);
274 
275  SCIP_CALL( SCIPchgVarLb(scip, var, 1.0) );
276  (*nchgbds)++;
277  }
278  else if( ubredcost > requiredredcost )
279  {
280  SCIPdebugMessage("variable <%s>: fixed 0.0 (requiredredcost <%g>, redcost <%g>, ubredcost <%g>)\n",
281  SCIPvarGetName(var), requiredredcost, redcost, ubredcost);
282 
283  SCIP_CALL( SCIPchgVarUb(scip, var, 0.0) );
284  (*nchgbds)++;
285  }
286 
287  /* update maximum reduced cost of a single binary variable */
288  propdata->maxredcost = MAX3(propdata->maxredcost, -lbredcost, ubredcost);
289  }
290 
291  return SCIP_OKAY;
292 }
293 
294 /** propagate the given none binary variable/column using the reduced cost */
295 static
296 SCIP_RETCODE propagateRedcostVar(
297  SCIP* scip, /**< SCIP data structure */
298  SCIP_VAR* var, /**< variable to use for propagation */
299  SCIP_COL* col, /**< LP column of the variable */
300  SCIP_Real lpobjval, /**< objective value of the current LP */
301  SCIP_Real cutoffbound, /**< the current cutoff bound */
302  int* nchgbds /**< pointer to count the number of bound changes */
303  )
304 {
305  SCIP_Real redcost;
306 
307  switch( SCIPcolGetBasisStatus(col) )
308  {
309  case SCIP_BASESTAT_LOWER:
310  redcost = SCIPgetColRedcost(scip, col);
311 
312  assert(!SCIPisFeasNegative(scip, redcost) || SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) );
313  if( SCIPisFeasPositive(scip, redcost) )
314  {
315  SCIP_Real oldlb;
316  SCIP_Real oldub;
317 
318  oldlb = SCIPvarGetLbLocal(var);
319  oldub = SCIPvarGetUbLocal(var);
320  assert(SCIPisEQ(scip, oldlb, SCIPcolGetLb(col)));
321  assert(SCIPisEQ(scip, oldub, SCIPcolGetUb(col)));
322 
323  if( SCIPisFeasLT(scip, oldlb, oldub) )
324  {
325  SCIP_Real newub;
326  SCIP_Bool strengthen;
327 
328  /* calculate reduced cost based bound */
329  newub = (cutoffbound - lpobjval) / redcost + oldlb;
330 
331  /* check, if new bound is good enough:
332  * - integer variables: take all possible strengthenings
333  * - continuous variables: strengthening must cut part of the variable's dynamic range, and
334  * at least 20% of the current domain
335  */
336  if( SCIPvarIsIntegral(var) )
337  {
338  newub = SCIPadjustedVarUb(scip, var, newub);
339  strengthen = (newub < oldub - 0.5);
340  }
341  else
342  strengthen = (newub < SCIPcolGetMaxPrimsol(col) && newub <= 0.2 * oldlb + 0.8 * oldub);
343 
344  if( strengthen )
345  {
346  /* strengthen upper bound */
347  SCIPdebugMessage("redcost strengthening upper bound: <%s> [%g,%g] -> [%g,%g] (ub=%g, lb=%g, redcost=%g)\n",
348  SCIPvarGetName(var), oldlb, oldub, oldlb, newub, cutoffbound, lpobjval, redcost);
349  SCIP_CALL( SCIPchgVarUb(scip, var, newub) );
350  (*nchgbds)++;
351  }
352  }
353  }
354  break;
355 
356  case SCIP_BASESTAT_BASIC:
357  break;
358 
359  case SCIP_BASESTAT_UPPER:
360  redcost = SCIPgetColRedcost(scip, col);
361 
362  assert(!SCIPisFeasPositive(scip, redcost) || SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) );
363  if( SCIPisFeasNegative(scip, redcost) )
364  {
365  SCIP_Real oldlb;
366  SCIP_Real oldub;
367 
368  oldlb = SCIPvarGetLbLocal(var);
369  oldub = SCIPvarGetUbLocal(var);
370  assert(SCIPisEQ(scip, oldlb, SCIPcolGetLb(col)));
371  assert(SCIPisEQ(scip, oldub, SCIPcolGetUb(col)));
372 
373  if( SCIPisFeasLT(scip, oldlb, oldub) )
374  {
375  SCIP_Real newlb;
376  SCIP_Bool strengthen;
377 
378  /* calculate reduced cost based bound */
379  newlb = (cutoffbound - lpobjval) / redcost + oldub;
380 
381  /* check, if new bound is good enough:
382  * - integer variables: take all possible strengthenings
383  * - continuous variables: strengthening must cut part of the variable's dynamic range, and
384  * at least 20% of the current domain
385  */
386  if( SCIPvarIsIntegral(var) )
387  {
388  newlb = SCIPadjustedVarLb(scip, var, newlb);
389  strengthen = (newlb > oldlb + 0.5);
390  }
391  else
392  strengthen = (newlb > SCIPcolGetMinPrimsol(col) && newlb >= 0.8 * oldlb + 0.2 * oldub);
393 
394  /* check, if new bound is good enough: at least 20% strengthening for continuous variables */
395  if( strengthen )
396  {
397  /* strengthen lower bound */
398  SCIPdebugMessage("redcost strengthening lower bound: <%s> [%g,%g] -> [%g,%g] (ub=%g, lb=%g, redcost=%g)\n",
399  SCIPvarGetName(var), oldlb, oldub, newlb, oldub, cutoffbound, lpobjval, redcost);
400  SCIP_CALL( SCIPchgVarLb(scip, var, newlb) );
401  (*nchgbds)++;
402  }
403  }
404  }
405  break;
406 
407  case SCIP_BASESTAT_ZERO:
408  assert(SCIPisFeasZero(scip, SCIPgetColRedcost(scip, col)));
409  break;
410 
411  default:
412  SCIPerrorMessage("invalid basis state\n");
413  return SCIP_INVALIDDATA;
414  }
415 
416  return SCIP_OKAY;
417 }
418 
419 /**@} */
420 
421 /**@name Callback methods of propagator
422  *
423  * @{
424  */
425 
426 /** copy method for propagator plugins (called when SCIP copies plugins) */
427 static
428 SCIP_DECL_PROPCOPY(propCopyRedcost)
429 { /*lint --e{715}*/
430  assert(scip != NULL);
431  assert(prop != NULL);
432  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
433 
434  /* call inclusion method of constraint handler */
435  SCIP_CALL( SCIPincludePropRedcost(scip) );
436 
437  return SCIP_OKAY;
438 }
439 
440 /** destructor of propagator to free user data (called when SCIP is exiting) */
441 static
442 SCIP_DECL_PROPFREE(propFreeRedcost)
443 { /*lint --e{715}*/
444  SCIP_PROPDATA* propdata;
445 
446  /* free propagator data */
447  propdata = SCIPpropGetData(prop);
448  assert(propdata != NULL);
449 
450  SCIPfreeMemory(scip, &propdata);
451 
452  SCIPpropSetData(prop, NULL);
453 
454  return SCIP_OKAY;
455 }
456 
457 /** solving process initialization method of propagator (called when branch and bound process is about to begin) */
458 static
459 SCIP_DECL_PROPINITSOL(propInitsolRedcost)
460 {
461  SCIP_PROPDATA* propdata;
462 
463  propdata = SCIPpropGetData(prop);
464  assert(propdata != NULL);
465 
466  propdata->usefullimplics = FALSE;
467  propdata->maxredcost = 0.0;
468 
469  return SCIP_OKAY;
470 }
471 
472 /** reduced cost propagation method for an LP solution */
473 static
474 SCIP_DECL_PROPEXEC(propExecRedcost)
475 { /*lint --e{715}*/
476  SCIP_PROPDATA* propdata;
477  SCIP_COL** cols;
478  SCIP_Real requiredredcost;
479  SCIP_Real cutoffbound;
480  SCIP_Real lpobjval;
481  SCIP_Bool propbinvars;
482  SCIP_Bool cutoff;
483  int nchgbds;
484  int ncols;
485  int c;
486 
487  *result = SCIP_DIDNOTRUN;
488 
489  /* in case we have a zero objective function, we skip the reduced cost propagator */
490  if( SCIPgetNObjVars(scip) == 0 )
491  return SCIP_OKAY;
492 
493  /* propagator can only be applied during solving stage */
494  if( SCIPgetStage(scip) < SCIP_STAGE_SOLVING )
495  return SCIP_OKAY;
496 
497  /* we cannot apply reduced cost fixing, if we want to solve exactly */
498  /**@todo implement reduced cost fixing with interval arithmetics */
499  if( SCIPisExactSolve(scip) )
500  return SCIP_OKAY;
501 
502  /* only call propagator, if the current node has an LP */
503  if( !SCIPhasCurrentNodeLP(scip) )
504  return SCIP_OKAY;
505 
506  /* only call propagator, if an optimal LP solution is at hand */
507  if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
508  return SCIP_OKAY;
509 
510  /* only call propagator, if the current LP is a valid relaxation */
511  if( !SCIPisLPRelax(scip) )
512  return SCIP_OKAY;
513 
514  /* we cannot apply reduced cost strengthening, if no simplex basis is available */
515  if( !SCIPisLPSolBasic(scip) )
516  return SCIP_OKAY;
517 
518  /* get current cutoff bound */
519  cutoffbound = SCIPgetCutoffbound(scip);
520 
521  /* reduced cost strengthening can only be applied, if we have a finite cutoff */
522  if( SCIPisInfinity(scip, cutoffbound) )
523  return SCIP_OKAY;
524 
525  /* get LP columns */
526  cols = SCIPgetLPCols(scip);
527  ncols = SCIPgetNLPCols(scip);
528 
529  /* do nothing if the LP has no columns (is empty) */
530  if( ncols == 0 )
531  return SCIP_OKAY;
532 
533  /* get propagator data */
534  propdata = SCIPpropGetData(prop);
535  assert(propdata != NULL);
536 
537  /* chack if all integral variables are fixed and the continuous variables should not be propagated */
538  if( !propdata->continuous && SCIPgetNPseudoBranchCands(scip) == 0 )
539  return SCIP_OKAY;
540 
541  /* get LP objective value */
542  lpobjval = SCIPgetLPObjval(scip);
543 
544  /* check if binary variables should be propagated */
545  propbinvars = (SCIPgetDepth(scip) == 0) || (cutoffbound - lpobjval < 5 * propdata->maxredcost);
546 
547  /* skip the propagator if the problem has only binary variables and those should not be propagated */
548  if( !propbinvars && SCIPgetNVars(scip) == SCIPgetNBinVars(scip) )
549  return SCIP_OKAY;
550 
551  *result = SCIP_DIDNOTFIND;
552  cutoff = FALSE;
553  nchgbds = 0;
554 
555  /* compute the required reduced cost which are needed for a binary variable to be fixed */
556  requiredredcost = cutoffbound - lpobjval;
557 
558  SCIPdebugMessage("lpobjval <%g>, cutoffbound <%g>, max reduced <%g>, propgate binary %u, use implics %u\n",
559  lpobjval, cutoffbound, propdata->maxredcost, propbinvars, propdata->usefullimplics);
560 
561  /* check reduced costs for non-basic columns */
562  for( c = 0; c < ncols && !cutoff; ++c )
563  {
564  SCIP_VAR* var;
565 
566  var = SCIPcolGetVar(cols[c]);
567 
568  /* skip continuous variables in case the corresponding parameter is set */
569  if( !propdata->continuous && !SCIPvarIsIntegral(var) )
570  continue;
571 
572  if( SCIPvarIsBinary(var) )
573  {
574  if( propbinvars )
575  {
576  if( SCIPgetDepth(scip) == 0 )
577  {
578  SCIP_CALL( propagateRootRedcostBinvar(scip, propdata, var, cols[c], cutoffbound, &nchgbds) );
579  }
580  else
581  {
582  SCIP_CALL( propagateRedcostBinvar(scip, propdata, var, cols[c], requiredredcost, &nchgbds, &cutoff) );
583  }
584  }
585  }
586  else
587  {
588  SCIP_CALL( propagateRedcostVar(scip, var, cols[c], lpobjval, cutoffbound, &nchgbds) );
589  }
590  }
591 
592  if( cutoff )
593  {
594  *result = SCIP_CUTOFF;
595 
596  SCIPdebugMessage("node %"SCIP_LONGINT_FORMAT": detected cutoff\n",
597  SCIPnodeGetNumber(SCIPgetCurrentNode(scip)));
598  }
599  else if( nchgbds > 0 )
600  {
601  *result = SCIP_REDUCEDDOM;
602 
603  SCIPdebugMessage("node %"SCIP_LONGINT_FORMAT": %d bound changes (max redcost <%g>)\n",
604  SCIPnodeGetNumber(SCIPgetCurrentNode(scip)) , nchgbds, propdata->maxredcost);
605  }
606 
607  return SCIP_OKAY;
608 }
609 
610 /**@} */
611 
612 /**@name Interface methods
613  *
614  * @{
615  */
616 
617 /** creates the redcost propagator and includes it in SCIP */
618 SCIP_RETCODE SCIPincludePropRedcost(
619  SCIP* scip /**< SCIP data structure */
620  )
621 {
622  SCIP_PROPDATA* propdata;
623  SCIP_PROP* prop;
624 
625  /* create redcost propagator data */
626  SCIP_CALL( SCIPallocMemory(scip, &propdata) );
627 
628  /* include propagator */
629  SCIP_CALL( SCIPincludePropBasic(scip, &prop, PROP_NAME, PROP_DESC, PROP_PRIORITY, PROP_FREQ, PROP_DELAY, PROP_TIMING,
630  propExecRedcost, propdata) );
631 
632  assert(prop != NULL);
633 
634  /* set optional callbacks via setter functions */
635  SCIP_CALL( SCIPsetPropCopy(scip, prop, propCopyRedcost) );
636  SCIP_CALL( SCIPsetPropInitsol(scip, prop, propInitsolRedcost) );
637  SCIP_CALL( SCIPsetPropFree(scip, prop, propFreeRedcost) );
638 
639  /* add redcost propagator parameters */
640  SCIP_CALL( SCIPaddBoolParam(scip,
641  "propagating/"PROP_NAME"/continuous",
642  "should reduced cost fixing be also applied to continuous variables?",
643  &propdata->continuous, FALSE, DEFAULT_CONTINUOUS, NULL, NULL) );
644  SCIP_CALL( SCIPaddBoolParam(scip,
645  "propagating/"PROP_NAME"/useimplics",
646  "should implications be used to strength the reduced cost for binary variables?",
647  &propdata->useimplics, FALSE, DEFAULT_USEIMPLICS, NULL, NULL) );
648 
649  return SCIP_OKAY;
650 }
651 
652 /**@} */
653