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-2021 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 visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file prop_redcost.c
17  * @ingroup DEFPLUGINS_PROP
18  * @brief propagator using the LP reduced cost and the cutoff bound
19  * @author Tobias Achterberg
20  * @author Stefan Heinz
21  * @author Matthias Miltenberger
22  * @author Michael Winkler
23  *
24  * This propagator uses the reduced cost of an optimal solved LP relaxation to propagate the variables against the
25  * cutoff bound.
26  */
27 
28 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
29 
30 #include "lpi/type_lpi.h"
31 #include "scip/prop_redcost.h"
32 #include "scip/pub_lp.h"
33 #include "scip/pub_message.h"
34 #include "scip/pub_prop.h"
35 #include "scip/pub_tree.h"
36 #include "scip/pub_var.h"
37 #include "scip/scip_branch.h"
38 #include "scip/scip_general.h"
39 #include "scip/scip_lp.h"
40 #include "scip/scip_mem.h"
41 #include "scip/scip_message.h"
42 #include "scip/scip_numerics.h"
43 #include "scip/scip_param.h"
44 #include "scip/scip_pricer.h"
45 #include "scip/scip_prob.h"
46 #include "scip/scip_prop.h"
47 #include "scip/scip_solvingstats.h"
48 #include "scip/scip_tree.h"
49 #include "scip/scip_var.h"
50 #include <string.h>
51 
52 /**@name Propagator properties
53  *
54  * @{
55  */
56 
57 #define PROP_NAME "redcost"
58 #define PROP_DESC "reduced cost strengthening propagator"
59 #define PROP_TIMING SCIP_PROPTIMING_DURINGLPLOOP | SCIP_PROPTIMING_AFTERLPLOOP
60 #define PROP_PRIORITY +1000000 /**< propagator priority */
61 #define PROP_FREQ 1 /**< propagator frequency */
62 #define PROP_DELAY FALSE /**< should propagation method be delayed, if other propagators found reductions? */
63 
64 /**@} */
65 
66 
67 /**@name Default parameter values
68  *
69  * @{
70  */
71 
72 #define DEFAULT_CONTINUOUS FALSE /**< should reduced cost fixing be also applied to continuous variables? */
73 #define DEFAULT_USEIMPLICS FALSE /**< should implications be used to strength the reduced cost for binary variables? */
74 #define DEFAULT_FORCE FALSE /**< should the propagator be forced even if active pricer are present? Note that
75  * the reductions are always valid, but installing an upper bound on priced
76  * variables may lead to problems in pricing (existing variables at their upper
77  * bound may be priced again since they may have negative reduced costs) */
78 
79 /**@} */
80 
81 
82 /*
83  * Data structures
84  */
85 
86 
87 /** propagator data */
88 struct SCIP_PropData
89 {
90  SCIP_Bool continuous; /**< should reduced cost fixing be also applied to continuous variables? */
91  SCIP_Real maxredcost; /**< maximum reduced cost of a single binary variable */
92  SCIP_Bool usefullimplics; /**< are the implied reduced cost useful */
93  SCIP_Bool useimplics; /**< should implications be used to strength the reduced cost for binary variables? */
94  SCIP_Bool force; /**< should the propagator be forced even if active pricer are present? */
95 };
96 
97 
98 /**@name Local methods
99  *
100  * @{
101  */
102 
103 /** propagate the given binary variable/column using the root reduced cost stored in the SCIP internal data structures
104  * and check if the implications can be useful. Depending on that implications are used or not used during the search to
105  * strength the reduced costs.
106  */
107 static
109  SCIP* scip, /**< SCIP data structure */
110  SCIP_PROPDATA* propdata, /**< propagator data structure */
111  SCIP_VAR* var, /**< variable to use for propagation */
112  SCIP_COL* col, /**< LP column of the variable */
113  SCIP_Real cutoffbound, /**< the current cutoff bound */
114  int* nchgbds /**< pointer to count the number of bound changes */
115  )
116 {
117  SCIP_Real rootredcost;
118  SCIP_Real rootsol;
119  SCIP_Real rootlpobjval;
120 
121  assert(scip != NULL);
122  assert(SCIPgetDepth(scip) == 0);
123 
124  /* skip binary variable if it is locally fixed */
125  if( SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5 )
126  return SCIP_OKAY;
127 
128  rootredcost = SCIPvarGetBestRootRedcost(var);
129  rootsol = SCIPvarGetBestRootSol(var);
130  rootlpobjval = SCIPvarGetBestRootLPObjval(var);
131 
132  if( SCIPisDualfeasZero(scip, rootredcost) )
133  return SCIP_OKAY;
134 
135  assert(rootlpobjval != SCIP_INVALID); /*lint !e777*/
136 
137  if( rootsol > 0.5 )
138  {
139  /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
140  * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
141  * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
142  * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect.
143  */
144  assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasPositive(scip, rootredcost));
145 
146  /* update maximum reduced cost of a single binary variable */
147  propdata->maxredcost = MAX(propdata->maxredcost, -rootredcost);
148 
149  if( rootlpobjval - rootredcost > cutoffbound )
150  {
151  SCIPdebugMsg(scip, "globally fix binary variable <%s> to 1.0\n", SCIPvarGetName(var));
152 
153  SCIP_CALL( SCIPchgVarLb(scip, var, 1.0) );
154  (*nchgbds)++;
155  return SCIP_OKAY;
156  }
157  }
158  else
159  {
160  /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
161  * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
162  * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
163  * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect.
164  */
165  assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasNegative(scip, rootredcost));
166 
167  /* update maximum reduced cost of a single binary variable */
168  propdata->maxredcost = MAX(propdata->maxredcost, rootredcost);
169 
170  if( rootlpobjval + rootredcost > cutoffbound )
171  {
172  SCIPdebugMsg(scip, "globally fix binary variable <%s> to 0.0\n", SCIPvarGetName(var));
173 
174  SCIP_CALL( SCIPchgVarUb(scip, var, 0.0) );
175  (*nchgbds)++;
176  return SCIP_OKAY;
177  }
178  }
179 
180  /* evaluate if the implications are useful; the implications are seen to be useful if they provide an increase for
181  * the root reduced costs
182  */
183  if( !propdata->usefullimplics )
184  {
185  SCIP_Real lbredcost;
186  SCIP_Real ubredcost;
187 
188  lbredcost = SCIPgetVarImplRedcost(scip, var, FALSE);
189  assert(!SCIPisDualfeasPositive(scip, lbredcost));
190 
191  ubredcost = SCIPgetVarImplRedcost(scip, var, TRUE);
192  assert(!SCIPisDualfeasNegative(scip, ubredcost));
193 
194  switch( SCIPcolGetBasisStatus(col) )
195  {
196  case SCIP_BASESTAT_LOWER:
197  ubredcost -= SCIPgetVarRedcost(scip, var);
198 
199  /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
200  * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
201  * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
202  * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect.
203  */
204  assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasNegative(scip, ubredcost));
205  break;
206 
207  case SCIP_BASESTAT_UPPER:
208  lbredcost -= SCIPgetVarRedcost(scip, var);
209 
210  /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
211  * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
212  * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
213  * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect.
214  */
215  assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasPositive(scip, lbredcost));
216  break;
217 
218  case SCIP_BASESTAT_BASIC:
219  case SCIP_BASESTAT_ZERO:
220  default:
221  break;
222  }
223 
224  propdata->usefullimplics = (lbredcost < 0.0) || (ubredcost > 0.0);
225  }
226 
227  return SCIP_OKAY;
228 }
229 
230 /** propagate the given binary variable/column using the reduced cost */
231 static
233  SCIP* scip, /**< SCIP data structure */
234  SCIP_PROPDATA* propdata, /**< propagator data structure */
235  SCIP_VAR* var, /**< variable to use for propagation */
236  SCIP_COL* col, /**< LP column of the variable */
237  SCIP_Real requiredredcost, /**< required reduset cost to be able to fix a binary variable */
238  int* nchgbds, /**< pointer to count the number of bound changes */
239  SCIP_Bool* cutoff /**< pointer to store if an cutoff was detected */
240  )
241 {
242  SCIP_Real lbredcost;
243  SCIP_Real ubredcost;
244  SCIP_Real redcost;
245 
246  /* skip binary variable if it is locally fixed */
247  if( SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5 )
248  return SCIP_OKAY;
249 
250  /* first use the redcost cost to fix the binary variable */
251  switch( SCIPcolGetBasisStatus(col) )
252  {
253  case SCIP_BASESTAT_LOWER:
254  redcost = SCIPgetVarRedcost(scip, var);
255 
256  /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
257  * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
258  * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
259  * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect.
260  */
261  assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasNegative(scip, redcost));
262 
263  if( redcost > requiredredcost )
264  {
265  SCIPdebugMsg(scip, "variable <%s>: fixed 0.0 (requiredredcost <%g>, redcost <%g>)\n",
266  SCIPvarGetName(var), requiredredcost, redcost);
267 
268  SCIP_CALL( SCIPchgVarUb(scip, var, 0.0) );
269  (*nchgbds)++;
270  return SCIP_OKAY;
271  }
272  break;
273 
274  case SCIP_BASESTAT_UPPER:
275  redcost = SCIPgetVarRedcost(scip, var);
276 
277  /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
278  * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
279  * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
280  * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect.
281  */
282  assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasPositive(scip, redcost));
283 
284  if( -redcost > requiredredcost )
285  {
286  SCIPdebugMsg(scip, "variable <%s>: fixed 1.0 (requiredredcost <%g>, redcost <%g>)\n",
287  SCIPvarGetName(var), requiredredcost, redcost);
288 
289  SCIP_CALL( SCIPchgVarLb(scip, var, 1.0) );
290  (*nchgbds)++;
291  return SCIP_OKAY;
292  }
293  break;
294 
295  case SCIP_BASESTAT_BASIC:
296  return SCIP_OKAY;
297 
298  case SCIP_BASESTAT_ZERO:
299  /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
300  * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
301  * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
302  * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect.
303  */
304  assert(!SCIPisLPDualReliable(scip) || SCIPisDualfeasZero(scip, SCIPgetColRedcost(scip, col)));
305  return SCIP_OKAY;
306 
307  default:
308  SCIPerrorMessage("invalid basis state\n");
309  return SCIP_INVALIDDATA;
310  }
311 
312  /* second, if the implications should be used and if the implications are seen to be promising use the implied
313  * reduced costs to fix the binary variable
314  */
315  if( propdata->useimplics && propdata->usefullimplics )
316  {
317  /* collect implied reduced costs if the variable would be fixed to its lower bound */
318  lbredcost = SCIPgetVarImplRedcost(scip, var, FALSE);
319 
320  /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
321  * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
322  * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
323  * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect.
324  */
325  assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasPositive(scip, lbredcost)
326  || SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) );
327 
328  /* collect implied reduced costs if the variable would be fixed to its upper bound */
329  ubredcost = SCIPgetVarImplRedcost(scip, var, TRUE);
330  assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasNegative(scip, ubredcost)
331  || SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) );
332 
333  if( -lbredcost > requiredredcost && ubredcost > requiredredcost )
334  {
335  SCIPdebugMsg(scip, "variable <%s>: cutoff (requiredredcost <%g>, lbredcost <%g>, ubredcost <%g>)\n",
336  SCIPvarGetName(var), requiredredcost, lbredcost, ubredcost);
337 
338  (*cutoff) = TRUE;
339  }
340  else if( -lbredcost > requiredredcost )
341  {
342  SCIPdebugMsg(scip, "variable <%s>: fixed 1.0 (requiredredcost <%g>, redcost <%g>, lbredcost <%g>)\n",
343  SCIPvarGetName(var), requiredredcost, redcost, lbredcost);
344 
345  SCIP_CALL( SCIPchgVarLb(scip, var, 1.0) );
346  (*nchgbds)++;
347  }
348  else if( ubredcost > requiredredcost )
349  {
350  SCIPdebugMsg(scip, "variable <%s>: fixed 0.0 (requiredredcost <%g>, redcost <%g>, ubredcost <%g>)\n",
351  SCIPvarGetName(var), requiredredcost, redcost, ubredcost);
352 
353  SCIP_CALL( SCIPchgVarUb(scip, var, 0.0) );
354  (*nchgbds)++;
355  }
356 
357  /* update maximum reduced cost of a single binary variable */
358  propdata->maxredcost = MAX3(propdata->maxredcost, -lbredcost, ubredcost);
359  }
360 
361  return SCIP_OKAY;
362 }
363 
364 /** propagate the given none binary variable/column using the reduced cost */
365 static
367  SCIP* scip, /**< SCIP data structure */
368  SCIP_VAR* var, /**< variable to use for propagation */
369  SCIP_COL* col, /**< LP column of the variable */
370  SCIP_Real lpobjval, /**< objective value of the current LP */
371  SCIP_Real cutoffbound, /**< the current cutoff bound */
372  int* nchgbds /**< pointer to count the number of bound changes */
373  )
374 {
375  SCIP_Real redcost;
376 
377  switch( SCIPcolGetBasisStatus(col) )
378  {
379  case SCIP_BASESTAT_LOWER:
380  redcost = SCIPgetColRedcost(scip, col);
381 
382  /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
383  * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
384  * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
385  * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect.
386  */
387  assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasNegative(scip, redcost)
388  || SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) );
389 
390  if( SCIPisDualfeasPositive(scip, redcost) )
391  {
392  SCIP_Real oldlb;
393  SCIP_Real oldub;
394 
395  oldlb = SCIPvarGetLbLocal(var);
396  oldub = SCIPvarGetUbLocal(var);
397  assert(SCIPisEQ(scip, oldlb, SCIPcolGetLb(col)));
398  assert(SCIPisEQ(scip, oldub, SCIPcolGetUb(col)));
399 
400  if( SCIPisFeasLT(scip, oldlb, oldub) )
401  {
402  SCIP_Real newub;
403  SCIP_Bool strengthen;
404 
405  /* calculate reduced cost based bound */
406  newub = (cutoffbound - lpobjval) / redcost + oldlb;
407 
408  /* check, if new bound is good enough:
409  * - integer variables: take all possible strengthenings
410  * - continuous variables: strengthening must cut part of the variable's dynamic range, and
411  * at least 20% of the current domain
412  */
413  if( SCIPvarIsIntegral(var) )
414  {
415  newub = SCIPadjustedVarUb(scip, var, newub);
416  strengthen = (newub < oldub - 0.5);
417  }
418  else
419  strengthen = (newub < SCIPcolGetMaxPrimsol(col) && newub <= 0.2 * oldlb + 0.8 * oldub);
420 
421  if( strengthen )
422  {
423  /* strengthen upper bound */
424  SCIPdebugMsg(scip, "redcost strengthening upper bound: <%s> [%g,%g] -> [%g,%g] (ub=%g, lb=%g, redcost=%g)\n",
425  SCIPvarGetName(var), oldlb, oldub, oldlb, newub, cutoffbound, lpobjval, redcost);
426  SCIP_CALL( SCIPchgVarUb(scip, var, newub) );
427  (*nchgbds)++;
428  }
429  }
430  }
431  break;
432 
433  case SCIP_BASESTAT_BASIC:
434  break;
435 
436  case SCIP_BASESTAT_UPPER:
437  redcost = SCIPgetColRedcost(scip, col);
438 
439  /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
440  * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
441  * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
442  * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect.
443  */
444  assert(!SCIPisLPDualReliable(scip) || !SCIPisDualfeasPositive(scip, redcost)
445  || SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) );
446 
447  if( SCIPisDualfeasNegative(scip, redcost) )
448  {
449  SCIP_Real oldlb;
450  SCIP_Real oldub;
451 
452  oldlb = SCIPvarGetLbLocal(var);
453  oldub = SCIPvarGetUbLocal(var);
454  assert(SCIPisEQ(scip, oldlb, SCIPcolGetLb(col)));
455  assert(SCIPisEQ(scip, oldub, SCIPcolGetUb(col)));
456 
457  if( SCIPisFeasLT(scip, oldlb, oldub) )
458  {
459  SCIP_Real newlb;
460  SCIP_Bool strengthen;
461 
462  /* calculate reduced cost based bound */
463  newlb = (cutoffbound - lpobjval) / redcost + oldub;
464 
465  /* check, if new bound is good enough:
466  * - integer variables: take all possible strengthenings
467  * - continuous variables: strengthening must cut part of the variable's dynamic range, and
468  * at least 20% of the current domain
469  */
470  if( SCIPvarIsIntegral(var) )
471  {
472  newlb = SCIPadjustedVarLb(scip, var, newlb);
473  strengthen = (newlb > oldlb + 0.5);
474  }
475  else
476  strengthen = (newlb > SCIPcolGetMinPrimsol(col) && newlb >= 0.8 * oldlb + 0.2 * oldub);
477 
478  /* check, if new bound is good enough: at least 20% strengthening for continuous variables */
479  if( strengthen )
480  {
481  /* strengthen lower bound */
482  SCIPdebugMsg(scip, "redcost strengthening lower bound: <%s> [%g,%g] -> [%g,%g] (ub=%g, lb=%g, redcost=%g)\n",
483  SCIPvarGetName(var), oldlb, oldub, newlb, oldub, cutoffbound, lpobjval, redcost);
484  SCIP_CALL( SCIPchgVarLb(scip, var, newlb) );
485  (*nchgbds)++;
486  }
487  }
488  }
489  break;
490 
491  case SCIP_BASESTAT_ZERO:
492  /* SCIPisLPDualReliable should always return TRUE if the dual feasibility check is enabled and the LP claims to
493  * have a dual feasible solution. if the check is disabled the dual solution might be incorrect and the assert
494  * might fail. however, if the user decides to disable the dual feasibility check (which also can lead to wrong
495  * cutoffs) we don't want to skip propagating with reduced costs as an unexpected side-effect.
496  */
497  assert(!SCIPisLPDualReliable(scip) || SCIPisDualfeasZero(scip, SCIPgetColRedcost(scip, col)));
498  break;
499 
500  default:
501  SCIPerrorMessage("invalid basis state\n");
502  return SCIP_INVALIDDATA;
503  }
504 
505  return SCIP_OKAY;
506 }
507 
508 /**@} */
509 
510 /**@name Callback methods of propagator
511  *
512  * @{
513  */
514 
515 /** copy method for propagator plugins (called when SCIP copies plugins) */
516 static
517 SCIP_DECL_PROPCOPY(propCopyRedcost)
518 { /*lint --e{715}*/
519  assert(scip != NULL);
520  assert(prop != NULL);
521  assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
522 
523  /* call inclusion method of constraint handler */
525 
526  return SCIP_OKAY;
527 }
528 
529 /** destructor of propagator to free user data (called when SCIP is exiting) */
530 /**! [SnippetPropFreeRedcost] */
531 static
532 SCIP_DECL_PROPFREE(propFreeRedcost)
533 { /*lint --e{715}*/
534  SCIP_PROPDATA* propdata;
536  /* free propagator data */
537  propdata = SCIPpropGetData(prop);
538  assert(propdata != NULL);
539 
540  SCIPfreeBlockMemory(scip, &propdata);
541 
542  SCIPpropSetData(prop, NULL);
543 
544  return SCIP_OKAY;
545 }
546 /**! [SnippetPropFreeRedcost] */
547 
548 /** solving process initialization method of propagator (called when branch and bound process is about to begin) */
549 static
550 SCIP_DECL_PROPINITSOL(propInitsolRedcost)
551 {
552  SCIP_PROPDATA* propdata;
554  propdata = SCIPpropGetData(prop);
555  assert(propdata != NULL);
556 
557  propdata->usefullimplics = FALSE;
558  propdata->maxredcost = 0.0;
559 
560  return SCIP_OKAY;
561 }
562 
563 /** reduced cost propagation method for an LP solution */
564 static
565 SCIP_DECL_PROPEXEC(propExecRedcost)
566 { /*lint --e{715}*/
567  SCIP_PROPDATA* propdata;
568  SCIP_COL** cols;
569  SCIP_Real requiredredcost;
570  SCIP_Real cutoffbound;
571  SCIP_Real lpobjval;
572  SCIP_Bool propbinvars;
573  SCIP_Bool cutoff;
574  int nchgbds;
575  int ncols;
576  int c;
577 
578  *result = SCIP_DIDNOTRUN;
579 
580  /* in case we have a zero objective function, we skip the reduced cost propagator */
581  if( SCIPgetNObjVars(scip) == 0 )
582  return SCIP_OKAY;
583 
584  /* propagator can only be applied during solving stage */
585  if( SCIPgetStage(scip) < SCIP_STAGE_SOLVING )
586  return SCIP_OKAY;
587 
588  /* we cannot apply reduced cost fixing, if we want to solve exactly */
589  /**@todo implement reduced cost fixing with interval arithmetics */
590  if( SCIPisExactSolve(scip) )
591  return SCIP_OKAY;
592 
593  /* only call propagator, if the current node has an LP */
594  if( !SCIPhasCurrentNodeLP(scip) )
595  return SCIP_OKAY;
596 
597  /* only call propagator, if an optimal LP solution is at hand */
599  return SCIP_OKAY;
600 
601  /* only call propagator, if the current LP is a valid relaxation */
602  if( !SCIPisLPRelax(scip) )
603  return SCIP_OKAY;
604 
605  /* we cannot apply reduced cost strengthening, if no simplex basis is available */
606  if( !SCIPisLPSolBasic(scip) )
607  return SCIP_OKAY;
608 
609  /* do not run if propagation w.r.t. objective is not allowed */
610  if( !SCIPallowWeakDualReds(scip) )
611  return SCIP_OKAY;
612 
613  /* get current cutoff bound */
614  cutoffbound = SCIPgetCutoffbound(scip);
615 
616  /* reduced cost strengthening can only be applied, if we have a finite cutoff */
617  if( SCIPisInfinity(scip, cutoffbound) )
618  return SCIP_OKAY;
619 
620  /* get LP columns */
621  cols = SCIPgetLPCols(scip);
622  ncols = SCIPgetNLPCols(scip);
623 
624  /* do nothing if the LP has no columns (is empty) */
625  if( ncols == 0 )
626  return SCIP_OKAY;
627 
628  /* get propagator data */
629  propdata = SCIPpropGetData(prop);
630  assert(propdata != NULL);
631 
632  /* do nothing if active pricer are present and force flag is not TRUE */
633  if( !propdata->force && SCIPgetNActivePricers(scip) > 0 )
634  return SCIP_OKAY;
635 
636  /* check if all integral variables are fixed and the continuous variables should not be propagated */
637  if( !propdata->continuous && SCIPgetNPseudoBranchCands(scip) == 0 )
638  return SCIP_OKAY;
639 
640  /* get LP objective value */
641  lpobjval = SCIPgetLPObjval(scip);
642 
643  /* check if binary variables should be propagated */
644  propbinvars = (SCIPgetDepth(scip) == 0) || (cutoffbound - lpobjval < 5 * propdata->maxredcost);
645 
646  /* skip the propagator if the problem has only binary variables and those should not be propagated */
647  if( !propbinvars && SCIPgetNVars(scip) == SCIPgetNBinVars(scip) )
648  return SCIP_OKAY;
649 
650  *result = SCIP_DIDNOTFIND;
651  cutoff = FALSE;
652  nchgbds = 0;
653 
654  /* compute the required reduced cost which are needed for a binary variable to be fixed */
655  requiredredcost = cutoffbound - lpobjval;
656 
657  SCIPdebugMsg(scip, "lpobjval <%g>, cutoffbound <%g>, max reduced <%g>, propgate binary %u, use implics %u\n",
658  lpobjval, cutoffbound, propdata->maxredcost, propbinvars, propdata->usefullimplics);
659 
660  /* check reduced costs for non-basic columns */
661  for( c = 0; c < ncols && !cutoff; ++c )
662  {
663  SCIP_VAR* var;
664 
665  var = SCIPcolGetVar(cols[c]);
666 
667  /* skip continuous variables in case the corresponding parameter is set */
668  if( !propdata->continuous && !SCIPvarIsIntegral(var) )
669  continue;
670 
671  if( SCIPvarIsBinary(var) )
672  {
673  if( propbinvars )
674  {
675  if( SCIPgetDepth(scip) == 0 )
676  {
677  SCIP_CALL( propagateRootRedcostBinvar(scip, propdata, var, cols[c], cutoffbound, &nchgbds) );
678  }
679  else
680  {
681  SCIP_CALL( propagateRedcostBinvar(scip, propdata, var, cols[c], requiredredcost, &nchgbds, &cutoff) );
682  }
683  }
684  }
685  else
686  {
687  SCIP_CALL( propagateRedcostVar(scip, var, cols[c], lpobjval, cutoffbound, &nchgbds) );
688  }
689  }
690 
691  if( cutoff )
692  {
693  *result = SCIP_CUTOFF;
694 
695  SCIPdebugMsg(scip, "node %" SCIP_LONGINT_FORMAT ": detected cutoff\n",
697  }
698  else if( nchgbds > 0 )
699  {
700  *result = SCIP_REDUCEDDOM;
701 
702  SCIPdebugMsg(scip, "node %" SCIP_LONGINT_FORMAT ": %d bound changes (max redcost <%g>)\n",
703  SCIPnodeGetNumber(SCIPgetCurrentNode(scip)) , nchgbds, propdata->maxredcost);
704  }
705 
706  return SCIP_OKAY;
707 }
708 
709 /**@} */
710 
711 /**@name Interface methods
712  *
713  * @{
714  */
715 
716 /** creates the redcost propagator and includes it in SCIP */
718  SCIP* scip /**< SCIP data structure */
719  )
720 {
721  SCIP_PROPDATA* propdata;
722  SCIP_PROP* prop;
723 
724  /* create redcost propagator data */
725  SCIP_CALL( SCIPallocBlockMemory(scip, &propdata) );
726 
727  /* include propagator */
729  propExecRedcost, propdata) );
730 
731  assert(prop != NULL);
732 
733  /* set optional callbacks via setter functions */
734  SCIP_CALL( SCIPsetPropCopy(scip, prop, propCopyRedcost) );
735  SCIP_CALL( SCIPsetPropInitsol(scip, prop, propInitsolRedcost) );
736  SCIP_CALL( SCIPsetPropFree(scip, prop, propFreeRedcost) );
737 
738  /* add redcost propagator parameters */
740  "propagating/" PROP_NAME "/continuous",
741  "should reduced cost fixing be also applied to continuous variables?",
742  &propdata->continuous, FALSE, DEFAULT_CONTINUOUS, NULL, NULL) );
744  "propagating/" PROP_NAME "/useimplics",
745  "should implications be used to strength the reduced cost for binary variables?",
746  &propdata->useimplics, FALSE, DEFAULT_USEIMPLICS, NULL, NULL) );
748  "propagating/" PROP_NAME "/force",
749  "should the propagator be forced even if active pricer are present?",
750  &propdata->force, TRUE, DEFAULT_FORCE, NULL, NULL) );
751 
752  return SCIP_OKAY;
753 }
754 
755 /**@} */
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPincludePropRedcost(SCIP *scip)
Definition: prop_redcost.c:720
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:235
SCIP_EXPORT SCIP_Real SCIPvarGetBestRootLPObjval(SCIP_VAR *var)
Definition: var.c:13583
public methods for SCIP parameter handling
public methods for branch and bound tree
SCIP_Bool SCIPallowWeakDualReds(SCIP *scip)
Definition: scip_var.c:8617
public methods for memory management
SCIP_Real SCIPgetVarRedcost(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1861
SCIP_EXPORT SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7438
int SCIPgetNLPCols(SCIP *scip)
Definition: scip_lp.c:518
#define PROP_DELAY
Definition: prop_redcost.c:62
SCIP_Real SCIPcolGetMaxPrimsol(SCIP_COL *col)
Definition: lp.c:16883
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:81
SCIP_EXPORT SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17197
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1986
#define FALSE
Definition: def.h:73
#define DEFAULT_CONTINUOUS
Definition: prop_redcost.c:72
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
static SCIP_DECL_PROPEXEC(propExecRedcost)
Definition: prop_redcost.c:568
public methods for problem variables
SCIP_Real SCIPadjustedVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real ub)
Definition: scip_var.c:4639
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:48
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
SCIP_EXPORT SCIP_Real SCIPvarGetBestRootSol(SCIP_VAR *var)
Definition: var.c:13483
void SCIPpropSetData(SCIP_PROP *prop, SCIP_PROPDATA *propdata)
Definition: prop.c:790
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
static SCIP_RETCODE propagateRedcostVar(SCIP *scip, SCIP_VAR *var, SCIP_COL *col, SCIP_Real lpobjval, SCIP_Real cutoffbound, int *nchgbds)
Definition: prop_redcost.c:369
public methods for SCIP variables
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
#define DEFAULT_USEIMPLICS
Definition: prop_redcost.c:73
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:159
SCIP_Real SCIPcolGetLb(SCIP_COL *col)
Definition: lp.c:16827
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:74
SCIP_Bool SCIPisDualfeasNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPsetPropCopy(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPCOPY((*propcopy)))
Definition: scip_prop.c:142
public methods for numerical tolerances
SCIP_Bool SCIPisDualfeasZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPcolGetMinPrimsol(SCIP_COL *col)
Definition: lp.c:16873
public methods for querying solving statistics
SCIP_Bool SCIPisLPRelax(SCIP *scip)
Definition: scip_lp.c:216
public methods for the branch-and-bound tree
int SCIPgetNPseudoBranchCands(SCIP *scip)
Definition: scip_branch.c:749
static SCIP_DECL_PROPFREE(propFreeRedcost)
Definition: prop_redcost.c:535
#define PROP_PRIORITY
Definition: prop_redcost.c:60
SCIP_EXPORT const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17017
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4670
SCIP_EXPORT SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:17208
#define SCIPerrorMessage
Definition: pub_message.h:55
propagator using the LP reduced cost and the cutoff bound
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPgetNObjVars(SCIP *scip)
Definition: scip_prob.c:2214
const char * SCIPpropGetName(SCIP_PROP *prop)
Definition: prop.c:932
static SCIP_DECL_PROPCOPY(propCopyRedcost)
Definition: prop_redcost.c:520
type definitions for specific LP solvers interface
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPFREE((*propfree)))
Definition: scip_prop.c:158
#define NULL
Definition: lpi_spx1.cpp:155
#define SCIP_CALL(x)
Definition: def.h:370
SCIP_Real SCIPcolGetUb(SCIP_COL *col)
Definition: lp.c:16837
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition: scip_lp.c:637
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip_lp.c:238
#define PROP_NAME
Definition: prop_redcost.c:57
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:638
#define SCIP_Bool
Definition: def.h:70
#define MAX(x, y)
Definition: tclique_def.h:83
SCIP_Bool SCIPisDualfeasPositive(SCIP *scip, SCIP_Real val)
public methods for LP management
int SCIPgetNActivePricers(SCIP *scip)
Definition: scip_pricer.c:339
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4760
SCIP_EXPORT SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17723
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:16906
SCIP_Bool SCIPisExactSolve(SCIP *scip)
Definition: scip_general.c:574
public methods for the LP relaxation, rows and columns
public methods for variable pricer plugins
SCIP_EXPORT SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17733
SCIP_PROPDATA * SCIPpropGetData(SCIP_PROP *prop)
Definition: prop.c:780
public methods for branching rule plugins and branching
general public methods
static SCIP_RETCODE propagateRootRedcostBinvar(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR *var, SCIP_COL *col, SCIP_Real cutoffbound, int *nchgbds)
Definition: prop_redcost.c:111
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for message output
#define SCIP_Real
Definition: def.h:163
struct SCIP_PropData SCIP_PROPDATA
Definition: type_prop.h:43
public methods for message handling
#define SCIP_INVALID
Definition: def.h:183
SCIP_Real SCIPgetVarImplRedcost(SCIP *scip, SCIP_VAR *var, SCIP_Bool varfixing)
Definition: scip_var.c:1906
SCIP_Real SCIPgetColRedcost(SCIP *scip, SCIP_COL *col)
Definition: scip_lp.c:1100
#define PROP_DESC
Definition: prop_redcost.c:58
#define PROP_FREQ
Definition: prop_redcost.c:61
public methods for propagator plugins
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2031
SCIP_COL ** SCIPgetLPCols(SCIP *scip)
Definition: scip_lp.c:497
SCIP_BASESTAT SCIPcolGetBasisStatus(SCIP_COL *col)
Definition: lp.c:16895
#define DEFAULT_FORCE
Definition: prop_redcost.c:74
SCIP_Bool SCIPisLPDualReliable(SCIP *scip)
Definition: scip_lp.c:198
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:105
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:356
SCIP_RETCODE SCIPsetPropInitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINITSOL((*propinitsol)))
Definition: scip_prop.c:206
public methods for global and local (sub)problems
SCIP_EXPORT SCIP_Real SCIPvarGetBestRootRedcost(SCIP_VAR *var)
Definition: var.c:13549
SCIP_Real SCIPadjustedVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real lb)
Definition: scip_var.c:4607
static SCIP_DECL_PROPINITSOL(propInitsolRedcost)
Definition: prop_redcost.c:553
#define PROP_TIMING
Definition: prop_redcost.c:59
public methods for propagators