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