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 useful */
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 structures
87  * and check if the implications can be useful. Depending on that implications 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  /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
122  * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
123  * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
124  * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect.
125  */
126  assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasPositive(scip, rootredcost));
127 
128  /* update maximum reduced cost of a single binary variable */
129  propdata->maxredcost = MAX(propdata->maxredcost, -rootredcost);
130 
131  if( rootlpobjval - rootredcost > cutoffbound )
132  {
133  SCIPdebugMsg(scip, "globally fix binary variable <%s> to 1.0\n", SCIPvarGetName(var));
134 
135  SCIP_CALL( SCIPchgVarLb(scip, var, 1.0) );
136  (*nchgbds)++;
137  return SCIP_OKAY;
138  }
139  }
140  else
141  {
142  /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
143  * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
144  * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
145  * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect.
146  */
147  assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasNegative(scip, rootredcost));
148 
149  /* update maximum reduced cost of a single binary variable */
150  propdata->maxredcost = MAX(propdata->maxredcost, rootredcost);
151 
152  if( rootlpobjval + rootredcost > cutoffbound )
153  {
154  SCIPdebugMsg(scip, "globally fix binary variable <%s> to 0.0\n", SCIPvarGetName(var));
155 
156  SCIP_CALL( SCIPchgVarUb(scip, var, 0.0) );
157  (*nchgbds)++;
158  return SCIP_OKAY;
159  }
160  }
161 
162  /* evaluate if the implications are useful; the implications are seen to be useful if they provide an increase for
163  * the root reduced costs
164  */
165  if( !propdata->usefullimplics )
166  {
167  SCIP_Real lbredcost;
168  SCIP_Real ubredcost;
169 
170  lbredcost = SCIPgetVarImplRedcost(scip, var, FALSE);
171  assert(!SCIPisDualfeasPositive(scip, lbredcost));
172 
173  ubredcost = SCIPgetVarImplRedcost(scip, var, TRUE);
174  assert(!SCIPisDualfeasNegative(scip, ubredcost));
175 
176  switch( SCIPcolGetBasisStatus(col) )
177  {
178  case SCIP_BASESTAT_LOWER:
179  ubredcost -= SCIPgetVarRedcost(scip, var);
180 
181  /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
182  * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
183  * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
184  * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect.
185  */
186  assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasNegative(scip, ubredcost));
187  break;
188 
189  case SCIP_BASESTAT_UPPER:
190  lbredcost -= SCIPgetVarRedcost(scip, var);
191 
192  /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
193  * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
194  * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
195  * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect.
196  */
197  assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasPositive(scip, lbredcost));
198  break;
199 
200  case SCIP_BASESTAT_BASIC:
201  case SCIP_BASESTAT_ZERO:
202  default:
203  break;
204  }
205 
206  propdata->usefullimplics = (lbredcost < 0.0) || (ubredcost > 0.0);
207  }
208 
209  return SCIP_OKAY;
210 }
211 
212 /** propagate the given binary variable/column using the reduced cost */
213 static
215  SCIP* scip, /**< SCIP data structure */
216  SCIP_PROPDATA* propdata, /**< propagator data structure */
217  SCIP_VAR* var, /**< variable to use for propagation */
218  SCIP_COL* col, /**< LP column of the variable */
219  SCIP_Real requiredredcost, /**< required reduset cost to be able to fix a binary variable */
220  int* nchgbds, /**< pointer to count the number of bound changes */
221  SCIP_Bool* cutoff /**< pointer to store if an cutoff was detected */
222  )
223 {
224  SCIP_Real lbredcost;
225  SCIP_Real ubredcost;
226  SCIP_Real redcost;
227 
228  /* skip binary variable if it is locally fixed */
229  if( SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5 )
230  return SCIP_OKAY;
231 
232  /* first use the redcost cost to fix the binary variable */
233  switch( SCIPcolGetBasisStatus(col) )
234  {
235  case SCIP_BASESTAT_LOWER:
236  redcost = SCIPgetVarRedcost(scip, var);
237 
238  /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
239  * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
240  * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
241  * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect.
242  */
243  assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasNegative(scip, redcost));
244 
245  if( redcost > requiredredcost )
246  {
247  SCIPdebugMsg(scip, "variable <%s>: fixed 0.0 (requiredredcost <%g>, redcost <%g>)\n",
248  SCIPvarGetName(var), requiredredcost, redcost);
249 
250  SCIP_CALL( SCIPchgVarUb(scip, var, 0.0) );
251  (*nchgbds)++;
252  return SCIP_OKAY;
253  }
254  break;
255 
256  case SCIP_BASESTAT_UPPER:
257  redcost = SCIPgetVarRedcost(scip, var);
258 
259  /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
260  * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
261  * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
262  * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect.
263  */
264  assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasPositive(scip, redcost));
265 
266  if( -redcost > requiredredcost )
267  {
268  SCIPdebugMsg(scip, "variable <%s>: fixed 1.0 (requiredredcost <%g>, redcost <%g>)\n",
269  SCIPvarGetName(var), requiredredcost, redcost);
270 
271  SCIP_CALL( SCIPchgVarLb(scip, var, 1.0) );
272  (*nchgbds)++;
273  return SCIP_OKAY;
274  }
275  break;
276 
277  case SCIP_BASESTAT_BASIC:
278  return SCIP_OKAY;
279 
280  case SCIP_BASESTAT_ZERO:
281  /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
282  * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
283  * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
284  * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect.
285  */
286  assert(!SCIPisLPDualReliable(scip) || SCIPisDualfeasZero(scip, SCIPgetColRedcost(scip, col)));
287  return SCIP_OKAY;
288 
289  default:
290  SCIPerrorMessage("invalid basis state\n");
291  return SCIP_INVALIDDATA;
292  }
293 
294  /* second, if the implications should be used and if the implications are seen to be promising use the implied
295  * reduced costs to fix the binary variable
296  */
297  if( propdata->useimplics && propdata->usefullimplics )
298  {
299  /* collect implied reduced costs if the variable would be fixed to its lower bound */
300  lbredcost = SCIPgetVarImplRedcost(scip, var, FALSE);
301 
302  /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
303  * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
304  * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
305  * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect.
306  */
307  assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasPositive(scip, lbredcost)
308  || SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) );
309 
310  /* collect implied reduced costs if the variable would be fixed to its upper bound */
311  ubredcost = SCIPgetVarImplRedcost(scip, var, TRUE);
312  assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasNegative(scip, ubredcost)
313  || SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) );
314 
315  if( -lbredcost > requiredredcost && ubredcost > requiredredcost )
316  {
317  SCIPdebugMsg(scip, "variable <%s>: cutoff (requiredredcost <%g>, lbredcost <%g>, ubredcost <%g>)\n",
318  SCIPvarGetName(var), requiredredcost, lbredcost, ubredcost);
319 
320  (*cutoff) = TRUE;
321  }
322  else if( -lbredcost > requiredredcost )
323  {
324  SCIPdebugMsg(scip, "variable <%s>: fixed 1.0 (requiredredcost <%g>, redcost <%g>, lbredcost <%g>)\n",
325  SCIPvarGetName(var), requiredredcost, redcost, lbredcost);
326 
327  SCIP_CALL( SCIPchgVarLb(scip, var, 1.0) );
328  (*nchgbds)++;
329  }
330  else if( ubredcost > requiredredcost )
331  {
332  SCIPdebugMsg(scip, "variable <%s>: fixed 0.0 (requiredredcost <%g>, redcost <%g>, ubredcost <%g>)\n",
333  SCIPvarGetName(var), requiredredcost, redcost, ubredcost);
334 
335  SCIP_CALL( SCIPchgVarUb(scip, var, 0.0) );
336  (*nchgbds)++;
337  }
338 
339  /* update maximum reduced cost of a single binary variable */
340  propdata->maxredcost = MAX3(propdata->maxredcost, -lbredcost, ubredcost);
341  }
342 
343  return SCIP_OKAY;
344 }
345 
346 /** propagate the given none binary variable/column using the reduced cost */
347 static
349  SCIP* scip, /**< SCIP data structure */
350  SCIP_VAR* var, /**< variable to use for propagation */
351  SCIP_COL* col, /**< LP column of the variable */
352  SCIP_Real lpobjval, /**< objective value of the current LP */
353  SCIP_Real cutoffbound, /**< the current cutoff bound */
354  int* nchgbds /**< pointer to count the number of bound changes */
355  )
356 {
357  SCIP_Real redcost;
358 
359  switch( SCIPcolGetBasisStatus(col) )
360  {
361  case SCIP_BASESTAT_LOWER:
362  redcost = SCIPgetColRedcost(scip, col);
363 
364  /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
365  * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
366  * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
367  * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect.
368  */
369  assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasNegative(scip, redcost)
370  || SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) );
371 
372  if( SCIPisDualfeasPositive(scip, redcost) )
373  {
374  SCIP_Real oldlb;
375  SCIP_Real oldub;
376 
377  oldlb = SCIPvarGetLbLocal(var);
378  oldub = SCIPvarGetUbLocal(var);
379  assert(SCIPisEQ(scip, oldlb, SCIPcolGetLb(col)));
380  assert(SCIPisEQ(scip, oldub, SCIPcolGetUb(col)));
381 
382  if( SCIPisFeasLT(scip, oldlb, oldub) )
383  {
384  SCIP_Real newub;
385  SCIP_Bool strengthen;
386 
387  /* calculate reduced cost based bound */
388  newub = (cutoffbound - lpobjval) / redcost + oldlb;
389 
390  /* check, if new bound is good enough:
391  * - integer variables: take all possible strengthenings
392  * - continuous variables: strengthening must cut part of the variable's dynamic range, and
393  * at least 20% of the current domain
394  */
395  if( SCIPvarIsIntegral(var) )
396  {
397  newub = SCIPadjustedVarUb(scip, var, newub);
398  strengthen = (newub < oldub - 0.5);
399  }
400  else
401  strengthen = (newub < SCIPcolGetMaxPrimsol(col) && newub <= 0.2 * oldlb + 0.8 * oldub);
402 
403  if( strengthen )
404  {
405  /* strengthen upper bound */
406  SCIPdebugMsg(scip, "redcost strengthening upper bound: <%s> [%g,%g] -> [%g,%g] (ub=%g, lb=%g, redcost=%g)\n",
407  SCIPvarGetName(var), oldlb, oldub, oldlb, newub, cutoffbound, lpobjval, redcost);
408  SCIP_CALL( SCIPchgVarUb(scip, var, newub) );
409  (*nchgbds)++;
410  }
411  }
412  }
413  break;
414 
415  case SCIP_BASESTAT_BASIC:
416  break;
417 
418  case SCIP_BASESTAT_UPPER:
419  redcost = SCIPgetColRedcost(scip, col);
420 
421  /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
422  * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
423  * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
424  * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect.
425  */
426  assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasPositive(scip, redcost)
427  || SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) );
428 
429  if( SCIPisDualfeasNegative(scip, redcost) )
430  {
431  SCIP_Real oldlb;
432  SCIP_Real oldub;
433 
434  oldlb = SCIPvarGetLbLocal(var);
435  oldub = SCIPvarGetUbLocal(var);
436  assert(SCIPisEQ(scip, oldlb, SCIPcolGetLb(col)));
437  assert(SCIPisEQ(scip, oldub, SCIPcolGetUb(col)));
438 
439  if( SCIPisFeasLT(scip, oldlb, oldub) )
440  {
441  SCIP_Real newlb;
442  SCIP_Bool strengthen;
443 
444  /* calculate reduced cost based bound */
445  newlb = (cutoffbound - lpobjval) / redcost + oldub;
446 
447  /* check, if new bound is good enough:
448  * - integer variables: take all possible strengthenings
449  * - continuous variables: strengthening must cut part of the variable's dynamic range, and
450  * at least 20% of the current domain
451  */
452  if( SCIPvarIsIntegral(var) )
453  {
454  newlb = SCIPadjustedVarLb(scip, var, newlb);
455  strengthen = (newlb > oldlb + 0.5);
456  }
457  else
458  strengthen = (newlb > SCIPcolGetMinPrimsol(col) && newlb >= 0.8 * oldlb + 0.2 * oldub);
459 
460  /* check, if new bound is good enough: at least 20% strengthening for continuous variables */
461  if( strengthen )
462  {
463  /* strengthen lower bound */
464  SCIPdebugMsg(scip, "redcost strengthening lower bound: <%s> [%g,%g] -> [%g,%g] (ub=%g, lb=%g, redcost=%g)\n",
465  SCIPvarGetName(var), oldlb, oldub, newlb, oldub, cutoffbound, lpobjval, redcost);
466  SCIP_CALL( SCIPchgVarLb(scip, var, newlb) );
467  (*nchgbds)++;
468  }
469  }
470  }
471  break;
472 
473  case SCIP_BASESTAT_ZERO:
474  /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
475  * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
476  * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
477  * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect.
478  */
479  assert(!SCIPisLPDualReliable(scip) || SCIPisDualfeasZero(scip, SCIPgetColRedcost(scip, col)));
480  break;
481 
482  default:
483  SCIPerrorMessage("invalid basis state\n");
484  return SCIP_INVALIDDATA;
485  }
486 
487  return SCIP_OKAY;
488 }
489 
490 /**@} */
491 
492 /**@name Callback methods of propagator
493  *
494  * @{
495  */
496 
497 /** copy method for propagator plugins (called when SCIP copies plugins) */
498 static
499 SCIP_DECL_PROPCOPY(propCopyRedcost)
500 { /*lint --e{715}*/
501  assert(scip != NULL);
502  assert(prop != NULL);
503  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
504 
505  /* call inclusion method of constraint handler */
507 
508  return SCIP_OKAY;
509 }
510 
511 /** destructor of propagator to free user data (called when SCIP is exiting) */
512 /**! [SnippetPropFreeRedcost] */
513 static
514 SCIP_DECL_PROPFREE(propFreeRedcost)
515 { /*lint --e{715}*/
516  SCIP_PROPDATA* propdata;
518  /* free propagator data */
519  propdata = SCIPpropGetData(prop);
520  assert(propdata != NULL);
521 
522  SCIPfreeBlockMemory(scip, &propdata);
523 
524  SCIPpropSetData(prop, NULL);
525 
526  return SCIP_OKAY;
527 }
528 /**! [SnippetPropFreeRedcost] */
529 
530 /** solving process initialization method of propagator (called when branch and bound process is about to begin) */
531 static
532 SCIP_DECL_PROPINITSOL(propInitsolRedcost)
533 {
534  SCIP_PROPDATA* propdata;
536  propdata = SCIPpropGetData(prop);
537  assert(propdata != NULL);
538 
539  propdata->usefullimplics = FALSE;
540  propdata->maxredcost = 0.0;
541 
542  return SCIP_OKAY;
543 }
544 
545 /** reduced cost propagation method for an LP solution */
546 static
547 SCIP_DECL_PROPEXEC(propExecRedcost)
548 { /*lint --e{715}*/
549  SCIP_PROPDATA* propdata;
550  SCIP_COL** cols;
551  SCIP_Real requiredredcost;
552  SCIP_Real cutoffbound;
553  SCIP_Real lpobjval;
554  SCIP_Bool propbinvars;
555  SCIP_Bool cutoff;
556  int nchgbds;
557  int ncols;
558  int c;
559 
560  *result = SCIP_DIDNOTRUN;
561 
562  /* in case we have a zero objective function, we skip the reduced cost propagator */
563  if( SCIPgetNObjVars(scip) == 0 )
564  return SCIP_OKAY;
565 
566  /* propagator can only be applied during solving stage */
567  if( SCIPgetStage(scip) < SCIP_STAGE_SOLVING )
568  return SCIP_OKAY;
569 
570  /* we cannot apply reduced cost fixing, if we want to solve exactly */
571  /**@todo implement reduced cost fixing with interval arithmetics */
572  if( SCIPisExactSolve(scip) )
573  return SCIP_OKAY;
574 
575  /* only call propagator, if the current node has an LP */
576  if( !SCIPhasCurrentNodeLP(scip) )
577  return SCIP_OKAY;
578 
579  /* only call propagator, if an optimal LP solution is at hand */
581  return SCIP_OKAY;
582 
583  /* only call propagator, if the current LP is a valid relaxation */
584  if( !SCIPisLPRelax(scip) )
585  return SCIP_OKAY;
586 
587  /* we cannot apply reduced cost strengthening, if no simplex basis is available */
588  if( !SCIPisLPSolBasic(scip) )
589  return SCIP_OKAY;
590 
591  /* do not run if propagation w.r.t. objective is not allowed */
592  if( !SCIPallowObjProp(scip) )
593  return SCIP_OKAY;
594 
595  /* get current cutoff bound */
596  cutoffbound = SCIPgetCutoffbound(scip);
597 
598  /* reduced cost strengthening can only be applied, if we have a finite cutoff */
599  if( SCIPisInfinity(scip, cutoffbound) )
600  return SCIP_OKAY;
601 
602  /* get LP columns */
603  cols = SCIPgetLPCols(scip);
604  ncols = SCIPgetNLPCols(scip);
605 
606  /* do nothing if the LP has no columns (is empty) */
607  if( ncols == 0 )
608  return SCIP_OKAY;
609 
610  /* get propagator data */
611  propdata = SCIPpropGetData(prop);
612  assert(propdata != NULL);
613 
614  /* do nothing if active pricer are present and force flag is not TRUE */
615  if( !propdata->force && SCIPgetNActivePricers(scip) > 0 )
616  return SCIP_OKAY;
617 
618  /* check if all integral variables are fixed and the continuous variables should not be propagated */
619  if( !propdata->continuous && SCIPgetNPseudoBranchCands(scip) == 0 )
620  return SCIP_OKAY;
621 
622  /* get LP objective value */
623  lpobjval = SCIPgetLPObjval(scip);
624 
625  /* check if binary variables should be propagated */
626  propbinvars = (SCIPgetDepth(scip) == 0) || (cutoffbound - lpobjval < 5 * propdata->maxredcost);
627 
628  /* skip the propagator if the problem has only binary variables and those should not be propagated */
629  if( !propbinvars && SCIPgetNVars(scip) == SCIPgetNBinVars(scip) )
630  return SCIP_OKAY;
631 
632  *result = SCIP_DIDNOTFIND;
633  cutoff = FALSE;
634  nchgbds = 0;
635 
636  /* compute the required reduced cost which are needed for a binary variable to be fixed */
637  requiredredcost = cutoffbound - lpobjval;
638 
639  SCIPdebugMsg(scip, "lpobjval <%g>, cutoffbound <%g>, max reduced <%g>, propgate binary %u, use implics %u\n",
640  lpobjval, cutoffbound, propdata->maxredcost, propbinvars, propdata->usefullimplics);
641 
642  /* check reduced costs for non-basic columns */
643  for( c = 0; c < ncols && !cutoff; ++c )
644  {
645  SCIP_VAR* var;
646 
647  var = SCIPcolGetVar(cols[c]);
648 
649  /* skip continuous variables in case the corresponding parameter is set */
650  if( !propdata->continuous && !SCIPvarIsIntegral(var) )
651  continue;
652 
653  if( SCIPvarIsBinary(var) )
654  {
655  if( propbinvars )
656  {
657  if( SCIPgetDepth(scip) == 0 )
658  {
659  SCIP_CALL( propagateRootRedcostBinvar(scip, propdata, var, cols[c], cutoffbound, &nchgbds) );
660  }
661  else
662  {
663  SCIP_CALL( propagateRedcostBinvar(scip, propdata, var, cols[c], requiredredcost, &nchgbds, &cutoff) );
664  }
665  }
666  }
667  else
668  {
669  SCIP_CALL( propagateRedcostVar(scip, var, cols[c], lpobjval, cutoffbound, &nchgbds) );
670  }
671  }
672 
673  if( cutoff )
674  {
675  *result = SCIP_CUTOFF;
676 
677  SCIPdebugMsg(scip, "node %" SCIP_LONGINT_FORMAT ": detected cutoff\n",
679  }
680  else if( nchgbds > 0 )
681  {
682  *result = SCIP_REDUCEDDOM;
683 
684  SCIPdebugMsg(scip, "node %" SCIP_LONGINT_FORMAT ": %d bound changes (max redcost <%g>)\n",
685  SCIPnodeGetNumber(SCIPgetCurrentNode(scip)) , nchgbds, propdata->maxredcost);
686  }
687 
688  return SCIP_OKAY;
689 }
690 
691 /**@} */
692 
693 /**@name Interface methods
694  *
695  * @{
696  */
697 
698 /** creates the redcost propagator and includes it in SCIP */
700  SCIP* scip /**< SCIP data structure */
701  )
702 {
703  SCIP_PROPDATA* propdata;
704  SCIP_PROP* prop;
705 
706  /* create redcost propagator data */
707  SCIP_CALL( SCIPallocBlockMemory(scip, &propdata) );
708 
709  /* include propagator */
711  propExecRedcost, propdata) );
712 
713  assert(prop != NULL);
714 
715  /* set optional callbacks via setter functions */
716  SCIP_CALL( SCIPsetPropCopy(scip, prop, propCopyRedcost) );
717  SCIP_CALL( SCIPsetPropInitsol(scip, prop, propInitsolRedcost) );
718  SCIP_CALL( SCIPsetPropFree(scip, prop, propFreeRedcost) );
719 
720  /* add redcost propagator parameters */
722  "propagating/" PROP_NAME "/continuous",
723  "should reduced cost fixing be also applied to continuous variables?",
724  &propdata->continuous, FALSE, DEFAULT_CONTINUOUS, NULL, NULL) );
726  "propagating/" PROP_NAME "/useimplics",
727  "should implications be used to strength the reduced cost for binary variables?",
728  &propdata->useimplics, FALSE, DEFAULT_USEIMPLICS, NULL, NULL) );
730  "propagating/" PROP_NAME "/force",
731  "should the propagator be forced even if active pricer are present?",
732  &propdata->force, TRUE, DEFAULT_FORCE, NULL, NULL) );
733 
734  return SCIP_OKAY;
735 }
736 
737 /**@} */
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:217
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47292
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip.c:41398
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip.c:821
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47305
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
Definition: scip.c:43447
SCIP_BASESTAT SCIPcolGetBasisStatus(SCIP_COL *col)
Definition: lp.c:16240
SCIP_Real SCIPgetVarRedcost(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:19375
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17332
SCIP_Real SCIPgetColRedcost(SCIP *scip, SCIP_COL *col)
Definition: scip.c:30194
int SCIPgetNPseudoBranchCands(SCIP *scip)
Definition: scip.c:37359
#define PROP_DELAY
Definition: prop_redcost.c:45
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16842
#define FALSE
Definition: def.h:64
SCIP_Real SCIPadjustedVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real ub)
Definition: scip.c:21979
SCIP_Real SCIPcolGetUb(SCIP_COL *col)
Definition: lp.c:16182
#define DEFAULT_CONTINUOUS
Definition: prop_redcost.c:55
int SCIPgetNActivePricers(SCIP *scip)
Definition: scip.c:5718
#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:550
SCIP_Bool SCIPisDualfeasZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:47530
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:22602
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:22010
SCIP_Bool SCIPisLPDualReliable(SCIP *scip)
Definition: scip.c:29326
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46957
SCIP_Real SCIPadjustedVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real lb)
Definition: scip.c:21947
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:22585
static SCIP_RETCODE propagateRedcostVar(SCIP *scip, SCIP_VAR *var, SCIP_COL *col, SCIP_Real lpobjval, SCIP_Real cutoffbound, int *nchgbds)
Definition: prop_redcost.c:351
#define SCIPdebugMsg
Definition: scip.h:455
#define DEFAULT_USEIMPLICS
Definition: prop_redcost.c:56
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7340
SCIP_Bool SCIPisLPRelax(SCIP *scip)
Definition: scip.c:29344
static SCIP_DECL_PROPFREE(propFreeRedcost)
Definition: prop_redcost.c:517
#define PROP_PRIORITY
Definition: prop_redcost.c:43
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition: scip.c:29731
SCIP_Real SCIPvarGetBestRootLPObjval(SCIP_VAR *var)
Definition: var.c:13222
#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:502
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:22100
SCIP_Real SCIPcolGetLb(SCIP_COL *col)
Definition: lp.c:16172
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16662
#define SCIP_CALL(x)
Definition: def.h:350
SCIP_Bool SCIPisDualfeasNegative(SCIP *scip, SCIP_Real val)
Definition: scip.c:47554
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip.c:29202
#define PROP_NAME
Definition: prop_redcost.c:40
#define SCIP_Bool
Definition: def.h:61
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:29287
int SCIPgetDepth(SCIP *scip)
Definition: scip.c:43039
#define MAX(x, y)
Definition: tclique_def.h:75
SCIP_RETCODE SCIPsetPropCopy(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPCOPY((*propcopy)))
Definition: scip.c:7695
SCIP_Real SCIPvarGetBestRootRedcost(SCIP_VAR *var)
Definition: var.c:13188
SCIP_COL ** SCIPgetLPCols(SCIP *scip)
Definition: scip.c:29591
int SCIPgetNObjVars(SCIP *scip)
Definition: scip.c:12034
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:47033
int SCIPgetNBinVars(SCIP *scip)
Definition: scip.c:11851
const char * SCIPpropGetName(SCIP_PROP *prop)
Definition: prop.c:887
SCIP_Real SCIPcolGetMinPrimsol(SCIP_COL *col)
Definition: lp.c:16218
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11806
SCIP_Bool SCIPisDualfeasPositive(SCIP *scip, SCIP_Real val)
Definition: scip.c:47542
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip.c:29366
SCIP_Real SCIPgetVarImplRedcost(SCIP *scip, SCIP_VAR *var, SCIP_Bool varfixing)
Definition: scip.c:19420
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:16251
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:13122
SCIP_RETCODE SCIPsetPropInitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINITSOL((*propinitsol)))
Definition: scip.c:7759
#define SCIP_Real
Definition: def.h:149
struct SCIP_PropData SCIP_PROPDATA
Definition: type_prop.h:38
#define SCIP_INVALID
Definition: def.h:169
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPFREE((*propfree)))
Definition: scip.c:7711
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:29612
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17342
SCIP_RETCODE SCIPincludePropRedcost(SCIP *scip)
Definition: prop_redcost.c:702
#define DEFAULT_FORCE
Definition: prop_redcost.c:57
SCIP_Real SCIPcolGetMaxPrimsol(SCIP_COL *col)
Definition: lp.c:16228
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:16853
SCIP_Bool SCIPisExactSolve(SCIP *scip)
Definition: scip.c:1032
static SCIP_DECL_PROPINITSOL(propInitsolRedcost)
Definition: prop_redcost.c:535
#define PROP_TIMING
Definition: prop_redcost.c:42
SCIP_Bool SCIPallowObjProp(SCIP *scip)
Definition: scip.c:25889
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:4239
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:7658