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