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