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
propagateRootRedcostBinvar(SCIP * scip,SCIP_PROPDATA * propdata,SCIP_VAR * var,SCIP_COL * col,SCIP_Real cutoffbound,int * nchgbds)108 SCIP_RETCODE propagateRootRedcostBinvar(
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
propagateRedcostBinvar(SCIP * scip,SCIP_PROPDATA * propdata,SCIP_VAR * var,SCIP_COL * col,SCIP_Real requiredredcost,int * nchgbds,SCIP_Bool * cutoff)232 SCIP_RETCODE propagateRedcostBinvar(
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
propagateRedcostVar(SCIP * scip,SCIP_VAR * var,SCIP_COL * col,SCIP_Real lpobjval,SCIP_Real cutoffbound,int * nchgbds)366 SCIP_RETCODE propagateRedcostVar(
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
SCIP_DECL_PROPCOPY(propCopyRedcost)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 */
524 SCIP_CALL( SCIPincludePropRedcost(scip) );
525
526 return SCIP_OKAY;
527 }
528
529 /** destructor of propagator to free user data (called when SCIP is exiting) */
530 /**! [SnippetPropFreeRedcost] */
531 static
SCIP_DECL_PROPFREE(propFreeRedcost)532 SCIP_DECL_PROPFREE(propFreeRedcost)
533 { /*lint --e{715}*/
534 SCIP_PROPDATA* propdata;
535
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
SCIP_DECL_PROPINITSOL(propInitsolRedcost)550 SCIP_DECL_PROPINITSOL(propInitsolRedcost)
551 {
552 SCIP_PROPDATA* propdata;
553
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
SCIP_DECL_PROPEXEC(propExecRedcost)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 */
598 if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
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",
696 SCIPnodeGetNumber(SCIPgetCurrentNode(scip)));
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 */
SCIPincludePropRedcost(SCIP * scip)717 SCIP_RETCODE SCIPincludePropRedcost(
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 */
728 SCIP_CALL( SCIPincludePropBasic(scip, &prop, PROP_NAME, PROP_DESC, PROP_PRIORITY, PROP_FREQ, PROP_DELAY, PROP_TIMING,
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 */
739 SCIP_CALL( SCIPaddBoolParam(scip,
740 "propagating/" PROP_NAME "/continuous",
741 "should reduced cost fixing be also applied to continuous variables?",
742 &propdata->continuous, FALSE, DEFAULT_CONTINUOUS, NULL, NULL) );
743 SCIP_CALL( SCIPaddBoolParam(scip,
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) );
747 SCIP_CALL( SCIPaddBoolParam(scip,
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 /**@} */
756