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 scip_probing.c
17 * @ingroup OTHER_CFILES
18 * @brief public methods for the probing mode
19 * @author Tobias Achterberg
20 * @author Timo Berthold
21 * @author Gerald Gamrath
22 * @author Leona Gottwald
23 * @author Stefan Heinz
24 * @author Gregor Hendel
25 * @author Thorsten Koch
26 * @author Alexander Martin
27 * @author Marc Pfetsch
28 * @author Michael Winkler
29 * @author Kati Wolter
30 *
31 * @todo check all SCIP_STAGE_* switches, and include the new stages TRANSFORMED and INITSOLVE
32 */
33
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35
36 #include "blockmemshell/memory.h"
37 #include "scip/conflict.h"
38 #include "scip/cons.h"
39 #include "scip/debug.h"
40 #include "scip/heur.h"
41 #include "scip/lp.h"
42 #include "scip/prob.h"
43 #include "scip/pub_message.h"
44 #include "scip/pub_misc.h"
45 #include "scip/pub_relax.h"
46 #include "scip/pub_tree.h"
47 #include "scip/pub_var.h"
48 #include "scip/relax.h"
49 #include "scip/scip_general.h"
50 #include "scip/scip_lp.h"
51 #include "scip/scip_mem.h"
52 #include "scip/scip_message.h"
53 #include "scip/scip_numerics.h"
54 #include "scip/scip_prob.h"
55 #include "scip/scip_probing.h"
56 #include "scip/scip_solvingstats.h"
57 #include "scip/scip_tree.h"
58 #include "scip/sepastore.h"
59 #include "scip/set.h"
60 #include "scip/solve.h"
61 #include "scip/stat.h"
62 #include "scip/struct_lp.h"
63 #include "scip/struct_mem.h"
64 #include "scip/struct_scip.h"
65 #include "scip/struct_set.h"
66 #include "scip/struct_stat.h"
67 #include "scip/struct_tree.h"
68 #include "scip/struct_var.h"
69 #include "scip/tree.h"
70 #include "scip/var.h"
71
72 /** returns whether we are in probing mode; probing mode is activated via SCIPstartProbing() and stopped
73 * via SCIPendProbing()
74 *
75 * @return TRUE, if SCIP is currently in probing mode, otherwise FALSE
76 *
77 * @pre This method can be called if @p scip is in one of the following stages:
78 * - \ref SCIP_STAGE_TRANSFORMED
79 * - \ref SCIP_STAGE_INITPRESOLVE
80 * - \ref SCIP_STAGE_PRESOLVING
81 * - \ref SCIP_STAGE_EXITPRESOLVE
82 * - \ref SCIP_STAGE_PRESOLVED
83 * - \ref SCIP_STAGE_INITSOLVE
84 * - \ref SCIP_STAGE_SOLVING
85 * - \ref SCIP_STAGE_SOLVED
86 * - \ref SCIP_STAGE_EXITSOLVE
87 */
SCIPinProbing(SCIP * scip)88 SCIP_Bool SCIPinProbing(
89 SCIP* scip /**< SCIP data structure */
90 )
91 {
92 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPinProbing", FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE) );
93
94 return SCIPtreeProbing(scip->tree);
95 }
96
97 /** initiates probing, making methods SCIPnewProbingNode(), SCIPbacktrackProbing(), SCIPchgVarLbProbing(),
98 * SCIPchgVarUbProbing(), SCIPfixVarProbing(), SCIPpropagateProbing(), and SCIPsolveProbingLP() available
99 *
100 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
101 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
102 *
103 * @pre This method can be called if @p scip is in one of the following stages:
104 * - \ref SCIP_STAGE_PRESOLVING
105 * - \ref SCIP_STAGE_SOLVING
106 *
107 * @note The collection of variable statistics is turned off during probing. If these statistics should be collected
108 * during probing use the method SCIPenableVarHistory() to turn the collection explicitly on.
109 */
SCIPstartProbing(SCIP * scip)110 SCIP_RETCODE SCIPstartProbing(
111 SCIP* scip /**< SCIP data structure */
112 )
113 {
114 SCIP_CALL( SCIPcheckStage(scip, "SCIPstartProbing", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
115
116 if( SCIPtreeProbing(scip->tree) )
117 {
118 SCIPerrorMessage("already in probing mode\n");
119 return SCIP_INVALIDCALL;
120 }
121
122 if( scip->lp != NULL && SCIPlpDiving(scip->lp) )
123 {
124 SCIPerrorMessage("cannot start probing while in diving mode\n");
125 return SCIP_INVALIDCALL;
126 }
127
128 /* use a different separation storage for probing mode; otherwise SCIP will remove the cuts that are currently in the
129 * separation storage after solving an LP in probing mode
130 */
131 if( scip->sepastore != NULL )
132 {
133 assert(scip->sepastoreprobing != NULL);
134 SCIPswapPointers((void**)&scip->sepastore, (void**)&scip->sepastoreprobing);
135 }
136
137 SCIP_CALL( SCIPtreeStartProbing(scip->tree, scip->mem->probmem, scip->set, scip->lp, scip->relaxation, scip->transprob, FALSE) );
138
139 /* disables the collection of any statistic for a variable */
140 SCIPstatDisableVarHistory(scip->stat);
141
142 return SCIP_OKAY;
143 }
144
145 /** creates a new probing sub node, whose changes can be undone by backtracking to a higher node in the probing path
146 * with a call to SCIPbacktrackProbing();
147 * using a sub node for each set of probing bound changes can improve conflict analysis
148 *
149 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
150 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
151 *
152 * @pre This method can be called if @p scip is in one of the following stages:
153 * - \ref SCIP_STAGE_PRESOLVING
154 * - \ref SCIP_STAGE_SOLVING
155 */
SCIPnewProbingNode(SCIP * scip)156 SCIP_RETCODE SCIPnewProbingNode(
157 SCIP* scip /**< SCIP data structure */
158 )
159 {
160 SCIP_RETCODE retcode;
161
162 SCIP_CALL( SCIPcheckStage(scip, "SCIPnewProbingNode", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
163
164 if( !SCIPtreeProbing(scip->tree) )
165 {
166 SCIPerrorMessage("not in probing mode\n");
167 return SCIP_INVALIDCALL;
168 }
169
170 retcode = SCIPtreeCreateProbingNode(scip->tree, scip->mem->probmem, scip->set, scip->lp);
171
172 if( retcode == SCIP_MAXDEPTHLEVEL )
173 {
174 SCIPwarningMessage(scip, "probing reached maximal depth; it should be stopped\n");
175 }
176 SCIP_CALL( retcode );
177
178 return SCIP_OKAY;
179 }
180
181 /** returns the current probing depth
182 *
183 * @return the probing depth, i.e. the number of probing sub nodes existing in the probing path
184 *
185 * @pre This method can be called if @p scip is in one of the following stages:
186 * - \ref SCIP_STAGE_PRESOLVING
187 * - \ref SCIP_STAGE_SOLVING
188 */
SCIPgetProbingDepth(SCIP * scip)189 int SCIPgetProbingDepth(
190 SCIP* scip /**< SCIP data structure */
191 )
192 {
193 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetProbingDepth", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
194
195 if( !SCIPtreeProbing(scip->tree) )
196 {
197 SCIPerrorMessage("not in probing mode\n");
198 SCIPABORT();
199 return -1; /*lint !e527*/
200 }
201
202 return SCIPtreeGetProbingDepth(scip->tree);
203 }
204
205 /** undoes all changes to the problem applied in probing up to the given probing depth;
206 * the changes of the probing node of the given probing depth are the last ones that remain active;
207 * changes that were applied before calling SCIPnewProbingNode() cannot be undone
208 *
209 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
210 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
211 *
212 * @pre This method can be called if @p scip is in one of the following stages:
213 * - \ref SCIP_STAGE_PRESOLVING
214 * - \ref SCIP_STAGE_SOLVING
215 */
SCIPbacktrackProbing(SCIP * scip,int probingdepth)216 SCIP_RETCODE SCIPbacktrackProbing(
217 SCIP* scip, /**< SCIP data structure */
218 int probingdepth /**< probing depth of the node in the probing path that should be reactivated */
219 )
220 {
221 SCIP_CALL( SCIPcheckStage(scip, "SCIPbacktrackProbing", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
222
223 if( !SCIPtreeProbing(scip->tree) )
224 {
225 SCIPerrorMessage("not in probing mode\n");
226 return SCIP_INVALIDCALL;
227 }
228 if( probingdepth < 0 || probingdepth > SCIPtreeGetProbingDepth(scip->tree) )
229 {
230 SCIPerrorMessage("backtracking probing depth %d out of current probing range [0,%d]\n",
231 probingdepth, SCIPtreeGetProbingDepth(scip->tree));
232 return SCIP_INVALIDDATA;
233 }
234
235 SCIP_CALL( SCIPtreeBacktrackProbing(scip->tree, scip->reopt, scip->mem->probmem, scip->set, scip->stat, scip->transprob,
236 scip->origprob, scip->lp, scip->primal, scip->branchcand, scip->eventqueue, scip->eventfilter,
237 scip->cliquetable, probingdepth) );
238
239 return SCIP_OKAY;
240 }
241
242 /** quits probing and resets bounds and constraints to the focus node's environment
243 *
244 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
245 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
246 *
247 * @pre This method can be called if @p scip is in one of the following stages:
248 * - \ref SCIP_STAGE_PRESOLVING
249 * - \ref SCIP_STAGE_SOLVING
250 */
SCIPendProbing(SCIP * scip)251 SCIP_RETCODE SCIPendProbing(
252 SCIP* scip /**< SCIP data structure */
253 )
254 {
255 SCIP_CALL( SCIPcheckStage(scip, "SCIPendProbing", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
256
257 if( !SCIPtreeProbing(scip->tree) )
258 {
259 SCIPerrorMessage("not in probing mode\n");
260 return SCIP_INVALIDCALL;
261 }
262
263 /* switch back from probing to normal operation mode and restore variables and constraints to focus node */
264 SCIP_CALL( SCIPtreeEndProbing(scip->tree, scip->reopt, scip->mem->probmem, scip->set, scip->messagehdlr, scip->stat,
265 scip->transprob, scip->origprob, scip->lp, scip->relaxation, scip->primal,
266 scip->branchcand, scip->eventqueue, scip->eventfilter, scip->cliquetable) );
267
268 /* enables the collection of statistics for a variable */
269 SCIPstatEnableVarHistory(scip->stat);
270
271 /* switch to the original separation storage */
272 if( scip->sepastore != NULL )
273 {
274 assert(scip->sepastoreprobing != NULL);
275 SCIPswapPointers((void**)&scip->sepastore, (void**)&scip->sepastoreprobing);
276 assert(SCIPsepastoreGetNCuts(scip->sepastoreprobing) == 0);
277 }
278
279 return SCIP_OKAY;
280 }
281
282 /** injects a change of variable's lower bound into current probing node; the same can also be achieved with a call to
283 * SCIPchgVarLb(), but in this case, the bound change would be treated like a deduction instead of a branching decision
284 *
285 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
286 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
287 *
288 * @pre This method can be called if @p scip is in one of the following stages:
289 * - \ref SCIP_STAGE_PRESOLVING
290 * - \ref SCIP_STAGE_SOLVING
291 */
SCIPchgVarLbProbing(SCIP * scip,SCIP_VAR * var,SCIP_Real newbound)292 SCIP_RETCODE SCIPchgVarLbProbing(
293 SCIP* scip, /**< SCIP data structure */
294 SCIP_VAR* var, /**< variable to change the bound for */
295 SCIP_Real newbound /**< new value for bound */
296 )
297 {
298 SCIP_CALL( SCIPcheckStage(scip, "SCIPchgVarLbProbing", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
299
300 if( !SCIPtreeProbing(scip->tree) )
301 {
302 SCIPerrorMessage("not in probing mode\n");
303 return SCIP_INVALIDCALL;
304 }
305 assert(SCIPnodeGetType(SCIPtreeGetCurrentNode(scip->tree)) == SCIP_NODETYPE_PROBINGNODE);
306
307 SCIPvarAdjustLb(var, scip->set, &newbound);
308
309 /* ignore tightenings of lower bounds to +infinity during solving process */
310 if( SCIPisInfinity(scip, newbound) && SCIPgetStage(scip) == SCIP_STAGE_SOLVING )
311 {
312 #ifndef NDEBUG
313 SCIPwarningMessage(scip, "ignore lower bound tightening for %s from %e to +infinity\n", SCIPvarGetName(var),
314 SCIPvarGetLbLocal(var));
315 #endif
316 return SCIP_OKAY;
317 }
318
319 SCIP_CALL( SCIPnodeAddBoundchg(SCIPtreeGetCurrentNode(scip->tree), scip->mem->probmem, scip->set, scip->stat,
320 scip->transprob, scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue, scip->cliquetable,
321 var, newbound, SCIP_BOUNDTYPE_LOWER, TRUE) );
322
323 return SCIP_OKAY;
324 }
325
326 /** injects a change of variable's upper bound into current probing node; the same can also be achieved with a call to
327 * SCIPchgVarUb(), but in this case, the bound change would be treated like a deduction instead of a branching decision
328 *
329 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
330 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
331 *
332 * @pre This method can be called if @p scip is in one of the following stages:
333 * - \ref SCIP_STAGE_PRESOLVING
334 * - \ref SCIP_STAGE_SOLVING
335 */
SCIPchgVarUbProbing(SCIP * scip,SCIP_VAR * var,SCIP_Real newbound)336 SCIP_RETCODE SCIPchgVarUbProbing(
337 SCIP* scip, /**< SCIP data structure */
338 SCIP_VAR* var, /**< variable to change the bound for */
339 SCIP_Real newbound /**< new value for bound */
340 )
341 {
342 SCIP_CALL( SCIPcheckStage(scip, "SCIPchgVarUbProbing", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
343
344 if( !SCIPtreeProbing(scip->tree) )
345 {
346 SCIPerrorMessage("not in probing mode\n");
347 return SCIP_INVALIDCALL;
348 }
349 assert(SCIPnodeGetType(SCIPtreeGetCurrentNode(scip->tree)) == SCIP_NODETYPE_PROBINGNODE);
350
351 SCIPvarAdjustUb(var, scip->set, &newbound);
352
353 /* ignore tightenings of upper bounds to -infinity during solving process */
354 if( SCIPisInfinity(scip, -newbound) && SCIPgetStage(scip) == SCIP_STAGE_SOLVING )
355 {
356 #ifndef NDEBUG
357 SCIPwarningMessage(scip, "ignore upper bound tightening for %s from %e to -infinity\n", SCIPvarGetName(var),
358 SCIPvarGetUbLocal(var));
359 #endif
360 return SCIP_OKAY;
361 }
362
363 SCIP_CALL( SCIPnodeAddBoundchg(SCIPtreeGetCurrentNode(scip->tree), scip->mem->probmem, scip->set, scip->stat,
364 scip->transprob, scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue, scip->cliquetable,
365 var, newbound, SCIP_BOUNDTYPE_UPPER, TRUE) );
366
367 return SCIP_OKAY;
368 }
369
370 /** gets variable's objective value in current probing
371 *
372 * @return the variable's objective value in current probing.
373 *
374 * @pre This method can be called if @p scip is in one of the following stages:
375 * - \ref SCIP_STAGE_SOLVING
376 *
377 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
378 */
SCIPgetVarObjProbing(SCIP * scip,SCIP_VAR * var)379 SCIP_Real SCIPgetVarObjProbing(
380 SCIP* scip, /**< SCIP data structure */
381 SCIP_VAR* var /**< variable to get the bound for */
382 )
383 {
384 assert(scip != NULL);
385 assert(var != NULL);
386
387 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetVarObjProbing", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
388
389 if( !SCIPtreeProbing(scip->tree) )
390 {
391 SCIPerrorMessage("not in probing mode\n");
392 return SCIP_INVALID;
393 }
394
395 return SCIPvarGetObjLP(var);
396 }
397
398 /** injects a change of variable's bounds into current probing node to fix the variable to the specified value;
399 * the same can also be achieved with a call to SCIPfixVar(), but in this case, the bound changes would be treated
400 * like deductions instead of branching decisions
401 *
402 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
403 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
404 *
405 * @pre This method can be called if @p scip is in one of the following stages:
406 * - \ref SCIP_STAGE_PRESOLVING
407 * - \ref SCIP_STAGE_SOLVING
408 */
SCIPfixVarProbing(SCIP * scip,SCIP_VAR * var,SCIP_Real fixedval)409 SCIP_RETCODE SCIPfixVarProbing(
410 SCIP* scip, /**< SCIP data structure */
411 SCIP_VAR* var, /**< variable to change the bound for */
412 SCIP_Real fixedval /**< value to fix variable to */
413 )
414 {
415 SCIP_Real fixlb;
416 SCIP_Real fixub;
417
418 SCIP_CALL( SCIPcheckStage(scip, "SCIPfixVarProbing", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
419
420 if( !SCIPtreeProbing(scip->tree) )
421 {
422 SCIPerrorMessage("not in probing mode\n");
423 return SCIP_INVALIDCALL;
424 }
425 assert(SCIPnodeGetType(SCIPtreeGetCurrentNode(scip->tree)) == SCIP_NODETYPE_PROBINGNODE);
426
427 /* we adjust the fixing value here and compare the old bound with the adjusted values because otherwise,
428 * it might happen that the unadjusted value is better and we add the boundchange,
429 * but within SCIPnodeAddBoundchg() the bounds are adjusted - using the feasibility epsilon for integer variables -
430 * and it is asserted, that the bound is still better than the old one which might then be incorrect.
431 */
432 fixlb = fixedval;
433 fixub = fixedval;
434 SCIPvarAdjustLb(var, scip->set, &fixlb);
435 SCIPvarAdjustUb(var, scip->set, &fixub);
436 assert(SCIPsetIsEQ(scip->set, fixlb, fixub));
437
438 if( SCIPsetIsGT(scip->set, fixlb, SCIPvarGetLbLocal(var)) )
439 {
440 SCIP_CALL( SCIPnodeAddBoundchg(SCIPtreeGetCurrentNode(scip->tree), scip->mem->probmem, scip->set, scip->stat,
441 scip->transprob, scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue,
442 scip->cliquetable, var, fixlb, SCIP_BOUNDTYPE_LOWER, TRUE) );
443 }
444 if( SCIPsetIsLT(scip->set, fixub, SCIPvarGetUbLocal(var)) )
445 {
446 SCIP_CALL( SCIPnodeAddBoundchg(SCIPtreeGetCurrentNode(scip->tree), scip->mem->probmem, scip->set, scip->stat,
447 scip->transprob, scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue, scip->cliquetable,
448 var, fixub, SCIP_BOUNDTYPE_UPPER, TRUE) );
449 }
450
451 return SCIP_OKAY;
452 }
453
454 /** changes (column) variable's objective value during probing mode
455 *
456 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
457 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
458 *
459 * @pre This method can be called if @p scip is in one of the following stages:
460 * - \ref SCIP_STAGE_PRESOLVING
461 * - \ref SCIP_STAGE_SOLVING
462 *
463 * @pre The variable needs to be a column variable.
464 */
SCIPchgVarObjProbing(SCIP * scip,SCIP_VAR * var,SCIP_Real newobj)465 SCIP_RETCODE SCIPchgVarObjProbing(
466 SCIP* scip, /**< SCIP data structure */
467 SCIP_VAR* var, /**< variable to change the objective for */
468 SCIP_Real newobj /**< new objective function value */
469 )
470 {
471 SCIP_NODE* node;
472 SCIP_Real oldobj;
473
474 SCIP_CALL( SCIPcheckStage(scip, "SCIPchgVarObjProbing", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
475
476 if( !SCIPtreeProbing(scip->tree) )
477 {
478 SCIPerrorMessage("not in probing mode\n");
479 return SCIP_INVALIDCALL;
480 }
481
482 /* get current probing node */
483 node = SCIPtreeGetCurrentNode(scip->tree);
484 assert(SCIPnodeGetType(node) == SCIP_NODETYPE_PROBINGNODE);
485
486 /* get old objective function value */
487 oldobj = SCIPvarGetObj(var);
488
489 if( SCIPisEQ(scip, oldobj, newobj) )
490 return SCIP_OKAY;
491
492 if( node->data.probingnode->nchgdobjs == 0 )
493 {
494 SCIP_CALL( SCIPallocMemoryArray(scip, &node->data.probingnode->origobjvars, 1) ); /*lint !e506*/
495 SCIP_CALL( SCIPallocMemoryArray(scip, &node->data.probingnode->origobjvals, 1) ); /*lint !e506*/
496 }
497 else
498 {
499 SCIP_CALL( SCIPreallocMemoryArray(scip, &node->data.probingnode->origobjvars, node->data.probingnode->nchgdobjs + 1) ); /*lint !e776*/
500 SCIP_CALL( SCIPreallocMemoryArray(scip, &node->data.probingnode->origobjvals, node->data.probingnode->nchgdobjs + 1) ); /*lint !e776*/
501 }
502
503 node->data.probingnode->origobjvars[node->data.probingnode->nchgdobjs] = var;
504 node->data.probingnode->origobjvals[node->data.probingnode->nchgdobjs] = oldobj;
505 ++node->data.probingnode->nchgdobjs;
506 ++scip->tree->probingsumchgdobjs;
507
508 assert(SCIPtreeProbingObjChanged(scip->tree) == SCIPlpDivingObjChanged(scip->lp));
509
510 /* inform tree and LP that the objective was changed and invalidate the LP's cutoff bound, since this has nothing to
511 * do with the current objective value anymore; the cutoff bound is reset in SCIPendProbing()
512 */
513 if( !SCIPtreeProbingObjChanged(scip->tree) )
514 {
515 SCIP_CALL( SCIPlpSetCutoffbound(scip->lp, scip->set, scip->transprob, SCIPsetInfinity(scip->set)) );
516
517 SCIPtreeMarkProbingObjChanged(scip->tree);
518 SCIPlpMarkDivingObjChanged(scip->lp);
519 }
520 assert(SCIPisInfinity(scip, scip->lp->cutoffbound));
521
522 /* perform the objective change */
523 SCIP_CALL( SCIPvarChgObj(var, scip->mem->probmem, scip->set, scip->transprob, scip->primal, scip->lp, scip->eventqueue, newobj) );
524
525 return SCIP_OKAY;
526 }
527
528 /** returns whether the objective function has changed during probing mode
529 *
530 * @return \ref TRUE if objective has changed, \ref FALSE otherwise
531 *
532 * @pre This method can be called if @p scip is in one of the following stages:
533 * - \ref SCIP_STAGE_TRANSFORMED
534 * - \ref SCIP_STAGE_INITPRESOLVE
535 * - \ref SCIP_STAGE_PRESOLVING
536 * - \ref SCIP_STAGE_EXITPRESOLVE
537 * - \ref SCIP_STAGE_PRESOLVED
538 * - \ref SCIP_STAGE_INITSOLVE
539 * - \ref SCIP_STAGE_SOLVING
540 * - \ref SCIP_STAGE_SOLVED
541 * - \ref SCIP_STAGE_EXITSOLVE
542 */
SCIPisObjChangedProbing(SCIP * scip)543 SCIP_Bool SCIPisObjChangedProbing(
544 SCIP* scip /**< SCIP data structure */
545 )
546 {
547 assert(scip != NULL);
548
549 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPisObjChangedProbing", FALSE, FALSE, FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE) );
550
551 return scip->tree != NULL && SCIPinProbing(scip) && SCIPtreeProbingObjChanged(scip->tree);
552 }
553
554 /** applies domain propagation on the probing sub problem, that was changed after SCIPstartProbing() was called;
555 * the propagated domains of the variables can be accessed with the usual bound accessing calls SCIPvarGetLbLocal()
556 * and SCIPvarGetUbLocal(); the propagation is only valid locally, i.e. the local bounds as well as the changed
557 * bounds due to SCIPchgVarLbProbing(), SCIPchgVarUbProbing(), and SCIPfixVarProbing() are used for propagation
558 *
559 * @note Conflict analysis can run if the propagation finds infeasibilities. SCIPpropagateProbing can even find
560 * globally valid bound changes. For this reason, the function restores the original objective (i.e. undoes the changes
561 * done by SCIPchgVarObjProbing before performing the propagation, as the propagators don't know that the objective
562 * might have changed. Thus, SCIPpropagateProbing can have an effect on the problem after probing ends.
563 *
564 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
565 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
566 *
567 * @pre This method can be called if @p scip is in one of the following stages:
568 * - \ref SCIP_STAGE_PRESOLVING
569 * - \ref SCIP_STAGE_SOLVING
570 */
SCIPpropagateProbing(SCIP * scip,int maxproprounds,SCIP_Bool * cutoff,SCIP_Longint * ndomredsfound)571 SCIP_RETCODE SCIPpropagateProbing(
572 SCIP* scip, /**< SCIP data structure */
573 int maxproprounds, /**< maximal number of propagation rounds (-1: no limit, 0: parameter settings) */
574 SCIP_Bool* cutoff, /**< pointer to store whether the probing node can be cut off */
575 SCIP_Longint* ndomredsfound /**< pointer to store the number of domain reductions found, or NULL */
576 )
577 {
578 SCIP_VAR** objchgvars;
579 SCIP_Real* objchgvals;
580 SCIP_Bool changedobj;
581 int nobjchg;
582
583 SCIP_CALL( SCIPcheckStage(scip, "SCIPpropagateProbing", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
584
585 if( !SCIPtreeProbing(scip->tree) )
586 {
587 SCIPerrorMessage("not in probing mode\n");
588 return SCIP_INVALIDCALL;
589 }
590
591 objchgvars = NULL;
592 objchgvals = NULL;
593 changedobj = FALSE;
594 nobjchg = 0;
595
596 /* undo objective changes if we want to propagate during probing */
597 if( scip->tree->probingobjchanged )
598 {
599 SCIP_VAR** vars;
600 int nvars;
601 int i;
602
603 vars = SCIPgetVars(scip);
604 nvars = SCIPgetNVars(scip);
605
606 SCIP_CALL( SCIPallocBufferArray(scip, &objchgvals, MIN(nvars, scip->tree->probingsumchgdobjs)) );
607 SCIP_CALL( SCIPallocBufferArray(scip, &objchgvars, MIN(nvars, scip->tree->probingsumchgdobjs)) );
608 nobjchg = 0;
609
610 for( i = 0; i < nvars; ++i )
611 {
612 if( !SCIPisEQ(scip, vars[i]->unchangedobj, SCIPgetVarObjProbing(scip, vars[i])) )
613 {
614 objchgvars[nobjchg] = vars[i];
615 objchgvals[nobjchg] = SCIPgetVarObjProbing(scip, vars[i]);
616 ++nobjchg;
617
618 SCIP_CALL( SCIPvarChgObj(vars[i], scip->mem->probmem, scip->set, scip->transprob, scip->primal, scip->lp,
619 scip->eventqueue, vars[i]->unchangedobj) );
620 }
621 }
622 assert(nobjchg <= scip->tree->probingsumchgdobjs);
623
624 SCIPlpUnmarkDivingObjChanged(scip->lp);
625 scip->tree->probingobjchanged = FALSE;
626 changedobj = TRUE;
627 }
628
629 if( ndomredsfound != NULL )
630 *ndomredsfound = -(scip->stat->nprobboundchgs + scip->stat->nprobholechgs);
631
632 SCIP_CALL( SCIPpropagateDomains(scip->mem->probmem, scip->set, scip->stat, scip->transprob, scip->origprob,
633 scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue, scip->conflict, scip->cliquetable,
634 SCIPgetDepth(scip), maxproprounds, SCIP_PROPTIMING_ALWAYS, cutoff) );
635
636 if( ndomredsfound != NULL )
637 *ndomredsfound += scip->stat->nprobboundchgs + scip->stat->nprobholechgs;
638
639 /* restore old objective function */
640 if( changedobj )
641 {
642 int i;
643
644 assert(objchgvars != NULL);
645 assert(objchgvals != NULL);
646
647 SCIPlpMarkDivingObjChanged(scip->lp);
648 scip->tree->probingobjchanged = TRUE;
649
650 for( i = 0; i < nobjchg; ++i )
651 {
652 SCIP_CALL( SCIPvarChgObj(objchgvars[i], scip->mem->probmem, scip->set, scip->transprob, scip->primal,
653 scip->lp, scip->eventqueue, objchgvals[i]) );
654 }
655
656 SCIPfreeBufferArray(scip, &objchgvars);
657 SCIPfreeBufferArray(scip, &objchgvals);
658 }
659
660 return SCIP_OKAY;
661 }
662
663 /** applies domain propagation on the probing sub problem, that was changed after SCIPstartProbing() was called;
664 * only propagations of the binary variables fixed at the current probing node that are triggered by the implication
665 * graph and the clique table are applied;
666 * the propagated domains of the variables can be accessed with the usual bound accessing calls SCIPvarGetLbLocal()
667 * and SCIPvarGetUbLocal(); the propagation is only valid locally, i.e. the local bounds as well as the changed
668 * bounds due to SCIPchgVarLbProbing(), SCIPchgVarUbProbing(), and SCIPfixVarProbing() are used for propagation
669 *
670 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
671 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
672 *
673 * @pre This method can be called if @p scip is in one of the following stages:
674 * - \ref SCIP_STAGE_PRESOLVING
675 * - \ref SCIP_STAGE_SOLVING
676 */
SCIPpropagateProbingImplications(SCIP * scip,SCIP_Bool * cutoff)677 SCIP_RETCODE SCIPpropagateProbingImplications(
678 SCIP* scip, /**< SCIP data structure */
679 SCIP_Bool* cutoff /**< pointer to store whether the probing node can be cut off */
680 )
681 {
682 SCIP_CALL( SCIPcheckStage(scip, "SCIPpropagateProbingImplications", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
683
684 if( !SCIPtreeProbing(scip->tree) )
685 {
686 SCIPerrorMessage("not in probing mode\n");
687 return SCIP_INVALIDCALL;
688 }
689
690 SCIP_CALL( SCIPnodePropagateImplics(SCIPtreeGetCurrentNode(scip->tree), scip->mem->probmem, scip->set, scip->stat,
691 scip->transprob, scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue, scip->cliquetable, cutoff) );
692
693 return SCIP_OKAY;
694 }
695
696 /** solves the LP at the current probing node (cannot be applied at preprocessing stage) with or without pricing */
697 static
solveProbingLP(SCIP * scip,int itlim,SCIP_Bool pricing,SCIP_Bool pretendroot,SCIP_Bool displayinfo,int maxpricerounds,SCIP_Bool * lperror,SCIP_Bool * cutoff)698 SCIP_RETCODE solveProbingLP(
699 SCIP* scip, /**< SCIP data structure */
700 int itlim, /**< maximal number of LP iterations to perform, or -1 for no limit */
701 SCIP_Bool pricing, /**< should pricing be applied? */
702 SCIP_Bool pretendroot, /**< should the pricers be called as if we are at the root node? */
703 SCIP_Bool displayinfo, /**< should info lines be displayed after each pricing round? */
704 int maxpricerounds, /**< maximal number of pricing rounds (-1: no limit) */
705 SCIP_Bool* lperror, /**< pointer to store whether an unresolved LP error occurred */
706 SCIP_Bool* cutoff /**< pointer to store whether the probing LP was infeasible or the objective
707 * limit was reached (or NULL, if not needed) */
708 )
709 {
710 SCIP_Bool initcutoff;
711
712 assert(lperror != NULL);
713 assert(SCIPtreeIsFocusNodeLPConstructed(scip->tree));
714
715 if( !SCIPtreeProbing(scip->tree) )
716 {
717 SCIPerrorMessage("not in probing mode\n");
718 return SCIP_INVALIDCALL;
719 }
720 assert(SCIPtreeGetCurrentDepth(scip->tree) > 0);
721
722 SCIP_CALL( SCIPinitConssLP(scip->mem->probmem, scip->set, scip->sepastore, scip->cutpool, scip->stat, scip->transprob,
723 scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue, scip->eventfilter,
724 scip->cliquetable, FALSE, FALSE, &initcutoff) );
725
726 if( initcutoff )
727 {
728 if( cutoff != NULL )
729 *cutoff = TRUE;
730
731 return SCIP_OKAY;
732 }
733 else if( cutoff != NULL )
734 *cutoff = FALSE;
735
736 /* load the LP state (if necessary) */
737 SCIP_CALL( SCIPtreeLoadProbingLPState(scip->tree, scip->mem->probmem, scip->set, scip->eventqueue, scip->lp) );
738
739 SCIPlpSetIsRelax(scip->lp, TRUE);
740
741 /* solve probing LP */
742 SCIP_CALL( SCIPlpSolveAndEval(scip->lp, scip->set, scip->messagehdlr, scip->mem->probmem, scip->stat,
743 scip->eventqueue, scip->eventfilter, scip->transprob, (SCIP_Longint)itlim, FALSE, FALSE, FALSE, lperror) );
744
745 assert((*lperror) || SCIPlpGetSolstat(scip->lp) != SCIP_LPSOLSTAT_NOTSOLVED);
746
747 /* mark the probing node to have a solved LP */
748 if( !(*lperror) )
749 {
750 SCIP_CALL( SCIPtreeMarkProbingNodeHasLP(scip->tree, scip->mem->probmem, scip->lp) );
751
752 /* call pricing */
753 if( pricing )
754 {
755 SCIP_Bool mustsepa;
756 int npricedcolvars;
757 SCIP_Bool result;
758
759 mustsepa = FALSE;
760 SCIP_CALL( SCIPpriceLoop(scip->mem->probmem, scip->set, scip->messagehdlr, scip->stat, scip->transprob,
761 scip->origprob, scip->primal, scip->tree, scip->reopt, scip->lp, scip->pricestore, scip->sepastore, scip->cutpool,
762 scip->branchcand, scip->eventqueue, scip->eventfilter, scip->cliquetable, pretendroot, displayinfo,
763 maxpricerounds, &npricedcolvars, &mustsepa, lperror, &result) );
764
765 /* mark the probing node again to update the LP size in the node and the tree path */
766 if( !(*lperror) )
767 {
768 SCIP_CALL( SCIPtreeMarkProbingNodeHasLP(scip->tree, scip->mem->probmem, scip->lp) );
769 }
770 }
771 }
772
773 /* remember that probing might have changed the LPi state; this holds even if solving returned with an LP error */
774 scip->tree->probingsolvedlp = TRUE;
775
776 /* the LP is infeasible or the objective limit was reached */
777 if( !(*lperror) && (SCIPlpGetSolstat(scip->lp) == SCIP_LPSOLSTAT_INFEASIBLE
778 || SCIPlpGetSolstat(scip->lp) == SCIP_LPSOLSTAT_OBJLIMIT ||
779 (SCIPlpGetSolstat(scip->lp) == SCIP_LPSOLSTAT_OPTIMAL
780 && SCIPisGE(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)))) )
781 {
782 /* analyze the infeasible LP (only if all columns are in the LP and no external pricers exist) */
783 if( !scip->set->misc_exactsolve && SCIPprobAllColsInLP(scip->transprob, scip->set, scip->lp) && !scip->tree->probingobjchanged )
784 {
785 SCIP_CALL( SCIPconflictAnalyzeLP(scip->conflict, scip->conflictstore, scip->mem->probmem, scip->set, scip->stat, scip->transprob,
786 scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue, scip->cliquetable, NULL) );
787 }
788
789 if( cutoff != NULL )
790 *cutoff = TRUE;
791 }
792
793 return SCIP_OKAY;
794 }
795
796 /** solves the LP at the current probing node (cannot be applied at preprocessing stage);
797 * no separation or pricing is applied
798 *
799 * The LP has to be constructed before (you can use SCIPisLPConstructed() or SCIPconstructLP()).
800 *
801 * @note if the LP is infeasible or the objective limit is reached, and if all columns are in the LP and no external
802 * pricers exist then conflict analysis will be run. This can have an effect on the problem after probing ends.
803 *
804 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
805 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
806 *
807 * @pre This method can be called if @p scip is in one of the following stages:
808 * - \ref SCIP_STAGE_SOLVING
809 */
SCIPsolveProbingLP(SCIP * scip,int itlim,SCIP_Bool * lperror,SCIP_Bool * cutoff)810 SCIP_RETCODE SCIPsolveProbingLP(
811 SCIP* scip, /**< SCIP data structure */
812 int itlim, /**< maximal number of LP iterations to perform, or -1 for no limit */
813 SCIP_Bool* lperror, /**< pointer to store whether an unresolved LP error occurred */
814 SCIP_Bool* cutoff /**< pointer to store whether the probing LP was infeasible or the objective
815 * limit was reached (or NULL, if not needed) */
816 )
817 {
818 SCIP_CALL( SCIPcheckStage(scip, "SCIPsolveProbingLP", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
819
820 SCIP_CALL( solveProbingLP(scip, itlim, FALSE, FALSE, FALSE, -1, lperror, cutoff) );
821
822 return SCIP_OKAY;
823 }
824
825 /** solves the LP at the current probing node (cannot be applied at preprocessing stage) and applies pricing
826 * until the LP is solved to optimality; no separation is applied
827 *
828 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
829 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
830 *
831 * @pre This method can be called if @p scip is in one of the following stages:
832 * - \ref SCIP_STAGE_SOLVING
833 */
SCIPsolveProbingLPWithPricing(SCIP * scip,SCIP_Bool pretendroot,SCIP_Bool displayinfo,int maxpricerounds,SCIP_Bool * lperror,SCIP_Bool * cutoff)834 SCIP_RETCODE SCIPsolveProbingLPWithPricing(
835 SCIP* scip, /**< SCIP data structure */
836 SCIP_Bool pretendroot, /**< should the pricers be called as if we were at the root node? */
837 SCIP_Bool displayinfo, /**< should info lines be displayed after each pricing round? */
838 int maxpricerounds, /**< maximal number of pricing rounds (-1: no limit);
839 * a finite limit means that the LP might not be solved to optimality! */
840 SCIP_Bool* lperror, /**< pointer to store whether an unresolved LP error occurred */
841 SCIP_Bool* cutoff /**< pointer to store whether the probing LP was infeasible or the objective
842 * limit was reached (or NULL, if not needed) */
843 )
844 {
845 SCIP_CALL( SCIPcheckStage(scip, "SCIPsolveProbingLPWithPricing", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
846
847 SCIP_CALL( solveProbingLP(scip, -1, TRUE, pretendroot, displayinfo, maxpricerounds, lperror, cutoff) );
848
849 return SCIP_OKAY;
850 }
851
852 /** sets the LP state for the current probing node
853 *
854 * @note state and norms are stored at the node and later released by SCIP; therefore, the pointers are set
855 * to NULL by the method
856 *
857 * @note the pointers to state and norms must not be NULL; however, they may point to a NULL pointer if the
858 * respective information should not be set
859 *
860 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
861 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
862 *
863 * @pre This method can be called if @p scip is in one of the following stages:
864 * - \ref SCIP_STAGE_PRESOLVING
865 * - \ref SCIP_STAGE_SOLVING
866 */
SCIPsetProbingLPState(SCIP * scip,SCIP_LPISTATE ** lpistate,SCIP_LPINORMS ** lpinorms,SCIP_Bool primalfeas,SCIP_Bool dualfeas)867 SCIP_RETCODE SCIPsetProbingLPState(
868 SCIP* scip, /**< SCIP data structure */
869 SCIP_LPISTATE** lpistate, /**< pointer to LP state information (like basis information) */
870 SCIP_LPINORMS** lpinorms, /**< pointer to LP pricing norms information */
871 SCIP_Bool primalfeas, /**< primal feasibility when LP state information was stored */
872 SCIP_Bool dualfeas /**< dual feasibility when LP state information was stored */
873 )
874 {
875 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetProbingLPState", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
876
877 if( !SCIPtreeProbing(scip->tree) )
878 {
879 SCIPerrorMessage("not in probing mode\n");
880 return SCIP_INVALIDCALL;
881 }
882
883 SCIP_CALL( SCIPtreeSetProbingLPState(scip->tree, scip->mem->probmem, scip->lp, lpistate, lpinorms, primalfeas, dualfeas) );
884
885 return SCIP_OKAY;
886 }
887
888 /** adds a row to the LP in the current probing node
889 *
890 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
891 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
892 *
893 * @pre This method can be called if @p scip is in one of the following stages:
894 * - \ref SCIP_STAGE_SOLVING
895 *
896 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
897 */
SCIPaddRowProbing(SCIP * scip,SCIP_ROW * row)898 SCIP_RETCODE SCIPaddRowProbing(
899 SCIP* scip, /**< SCIP data structure */
900 SCIP_ROW* row /**< row to be added */
901 )
902 {
903 SCIP_NODE* node;
904 int depth;
905
906 assert(scip != NULL);
907 assert(row != NULL);
908
909 SCIP_CALL( SCIPcheckStage(scip, "SCIPaddRowProbing", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
910
911 if( !SCIPtreeProbing(scip->tree) )
912 {
913 SCIPerrorMessage("not in probing mode\n");
914 return SCIP_INVALIDCALL;
915 }
916
917 /* get depth of current node */
918 node = SCIPtreeGetCurrentNode(scip->tree);
919 assert(node != NULL);
920 depth = SCIPnodeGetDepth(node);
921
922 SCIP_CALL( SCIPlpAddRow(scip->lp, scip->mem->probmem, scip->set, scip->eventqueue, scip->eventfilter, row, depth) );
923
924 return SCIP_OKAY;
925 }
926
927
928 /** applies the cuts in the separation storage to the LP and clears the storage afterwards;
929 * this method can only be applied during probing; the user should resolve the probing LP afterwards
930 * in order to get a new solution
931 *
932 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
933 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
934 *
935 * @pre This method can be called if @p scip is in one of the following stages:
936 * - \ref SCIP_STAGE_SOLVING
937 */
SCIPapplyCutsProbing(SCIP * scip,SCIP_Bool * cutoff)938 SCIP_RETCODE SCIPapplyCutsProbing(
939 SCIP* scip, /**< SCIP data structure */
940 SCIP_Bool* cutoff /**< pointer to store whether an empty domain was created */
941 )
942 {
943 SCIP_CALL( SCIPcheckStage(scip, "SCIPapplyCutsProbing", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
944
945 if( !SCIPtreeProbing(scip->tree) )
946 {
947 SCIPerrorMessage("not in probing mode\n");
948 return SCIP_INVALIDCALL;
949 }
950
951 SCIP_CALL( SCIPsepastoreApplyCuts(scip->sepastore, scip->mem->probmem, scip->set, scip->stat, scip->transprob,
952 scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue, scip->eventfilter,
953 scip->cliquetable, FALSE, SCIP_EFFICIACYCHOICE_LP, cutoff) );
954
955 return SCIP_OKAY;
956 }
957
958 /** solves relaxation(s) at the current probing node (cannot be applied at preprocessing stage);
959 * no separation or pricing is applied
960 *
961 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
962 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
963 *
964 * @pre This method can be called if @p scip is in one of the following stages:
965 * - \ref SCIP_STAGE_SOLVING
966 */
SCIPsolveProbingRelax(SCIP * scip,SCIP_Bool * cutoff)967 SCIP_RETCODE SCIPsolveProbingRelax(
968 SCIP* scip, /**< SCIP data structure */
969 SCIP_Bool* cutoff /**< pointer to store whether a relaxation was infeasible or the objective
970 * limit was reached (or NULL, if not needed) */
971 )
972 {
973 SCIP_SET* set;
974 int r;
975
976 SCIP_CALL( SCIPcheckStage(scip, "SCIPsolveProbingRelax", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
977
978 if ( ! SCIPtreeProbing(scip->tree) )
979 {
980 SCIPerrorMessage("not in probing mode\n");
981 return SCIP_INVALIDCALL;
982 }
983 assert( SCIPtreeGetCurrentDepth(scip->tree) > 0 );
984
985 assert( cutoff != NULL );
986 *cutoff = FALSE;
987
988 set = scip->set;
989
990 /* sort relaxators by priority */
991 SCIPsetSortRelaxs(set);
992
993 /* solve relaxations */
994 for (r = 0; r < set->nrelaxs && !(*cutoff); ++r)
995 {
996 SCIP_RELAX* relax;
997 SCIP_Real lowerbound;
998 SCIP_RESULT result;
999
1000 lowerbound = -SCIPinfinity(scip);
1001
1002 relax = set->relaxs[r];
1003 assert( relax != NULL );
1004
1005 SCIP_CALL( SCIPrelaxExec(relax, set, scip->tree, scip->stat, SCIPtreeGetCurrentDepth(scip->tree), &lowerbound, &result) );
1006
1007 switch( result )
1008 {
1009 case SCIP_CUTOFF:
1010 *cutoff = TRUE;
1011 SCIPdebugMsg(scip, " -> relaxator <%s> detected cutoff\n", SCIPrelaxGetName(relax));
1012 break;
1013
1014 case SCIP_CONSADDED:
1015 case SCIP_REDUCEDDOM:
1016 case SCIP_SEPARATED:
1017 case SCIP_SUSPENDED:
1018 SCIPerrorMessage("The relaxator should not return <%d> within probing mode.\n", result);
1019 break;
1020
1021 case SCIP_SUCCESS:
1022 case SCIP_DIDNOTRUN:
1023 break;
1024
1025 default:
1026 SCIPerrorMessage("Invalid result code <%d> of relaxator <%s>\n", result, SCIPrelaxGetName(relax));
1027 return SCIP_INVALIDRESULT;
1028 } /*lint !e788*/
1029 }
1030
1031 return SCIP_OKAY;
1032 }
1033
1034 /** print statistics of probing */
SCIPsnprintfProbingStats(SCIP * scip,char * strbuf,int len)1035 char* SCIPsnprintfProbingStats(
1036 SCIP* scip, /**< SCIP data structure */
1037 char* strbuf, /**< string buffer */
1038 int len /**< length of string buffer */
1039 )
1040 {
1041 char* ptr = strbuf;
1042 const int nvartypes = 4;
1043
1044 assert(scip != NULL);
1045 assert(strbuf != NULL);
1046
1047 if( SCIPinProbing(scip) )
1048 {
1049 SCIP_VAR** vars;
1050 int nbinvars = SCIPgetNBinVars(scip);
1051 int nintvars = SCIPgetNIntVars(scip);
1052 int nimplvars = SCIPgetNImplVars(scip);
1053 int nvars = SCIPgetNVars(scip);
1054 int vartypeend[] = {
1055 nbinvars,
1056 nbinvars + nintvars,
1057 nbinvars + nintvars + nimplvars,
1058 nvars
1059 };
1060 const char* vartypenames[] = {
1061 "binary",
1062 "integer",
1063 "implicit integer",
1064 "continuous"
1065 };
1066 int nvartypefixed[4];
1067 int nvarsfixed = 0;
1068 int depth;
1069 int probingdepth;
1070 int vartypestart = 0;
1071 int v;
1072 int p;
1073
1074 vars = SCIPgetVars(scip);
1075 BMSclearMemoryArray(nvartypefixed, nvartypes);
1076
1077 /* loop over vartypes and count fixings */
1078 for( p = 0; p < nvartypes; ++p )
1079 {
1080 for( v = vartypestart; v < vartypeend[p]; ++v )
1081 {
1082 if( SCIPisEQ(scip, SCIPvarGetLbLocal(vars[v]), SCIPvarGetUbLocal(vars[v])) )
1083 ++nvartypefixed[p];
1084 }
1085 nvarsfixed += nvartypefixed[p];
1086 vartypestart = vartypeend[p];
1087 }
1088
1089 depth = SCIPgetDepth(scip);
1090 probingdepth = SCIPgetProbingDepth(scip);
1091
1092 ptr += SCIPsnprintf(ptr, len, "Depth: (%d total, %d probing) ", depth, probingdepth);
1093 ptr += SCIPsnprintf(ptr, len, "Fixed/Variables: %d / %d (", nvarsfixed, vartypeend[nvartypes - 1]);
1094
1095 for( p = 0; p < nvartypes; ++p )
1096 {
1097 int ntypevars = vartypeend[p] - (p == 0 ? 0 : vartypeend[p - 1]);
1098 ptr += SCIPsnprintf(ptr, len, "%d / %d %s%s", nvartypefixed[p], ntypevars, vartypenames[p], p < (nvartypes - 1) ? ", " : ")");
1099 }
1100 }
1101 else
1102 {
1103 (void) SCIPsnprintf(strbuf, len, "Not in probing");
1104 }
1105
1106 return strbuf;
1107 }
1108
1109 /** gets the candidate score and preferred rounding direction for a candidate variable */
SCIPgetDivesetScore(SCIP * scip,SCIP_DIVESET * diveset,SCIP_DIVETYPE divetype,SCIP_VAR * divecand,SCIP_Real divecandsol,SCIP_Real divecandfrac,SCIP_Real * candscore,SCIP_Bool * roundup)1110 SCIP_RETCODE SCIPgetDivesetScore(
1111 SCIP* scip, /**< SCIP data structure */
1112 SCIP_DIVESET* diveset, /**< general diving settings */
1113 SCIP_DIVETYPE divetype, /**< represents different methods for a dive set to explore the next children */
1114 SCIP_VAR* divecand, /**< the candidate for which the branching direction is requested */
1115 SCIP_Real divecandsol, /**< LP solution value of the candidate */
1116 SCIP_Real divecandfrac, /**< fractionality of the candidate */
1117 SCIP_Real* candscore, /**< pointer to store the candidate score */
1118 SCIP_Bool* roundup /**< pointer to store whether preferred direction for diving is upwards */
1119 )
1120 {
1121 assert(scip != NULL);
1122 assert(candscore != NULL);
1123 assert(roundup != NULL);
1124 assert(divecand != NULL);
1125
1126 SCIP_CALL( SCIPcheckStage(scip, "SCIPgetDivesetScore", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1127
1128 SCIP_CALL( SCIPdivesetGetScore(diveset, scip->set, divetype, divecand, divecandsol, divecandfrac, candscore,
1129 roundup) );
1130
1131 return SCIP_OKAY;
1132 }
1133
1134 /** update diveset LP statistics, should be called after every LP solved by this diving heuristic */
SCIPupdateDivesetLPStats(SCIP * scip,SCIP_DIVESET * diveset,SCIP_Longint niterstoadd,SCIP_DIVECONTEXT divecontext)1135 void SCIPupdateDivesetLPStats(
1136 SCIP* scip, /**< SCIP data structure */
1137 SCIP_DIVESET* diveset, /**< diving settings */
1138 SCIP_Longint niterstoadd, /**< additional number of LP iterations to be added */
1139 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */
1140 )
1141 {
1142 assert(scip != NULL);
1143 assert(diveset != NULL);
1144
1145 SCIPdivesetUpdateLPStats(diveset, scip->stat, niterstoadd, divecontext);
1146 }
1147
1148 /** update diveset statistics and global diveset statistics */
SCIPupdateDivesetStats(SCIP * scip,SCIP_DIVESET * diveset,int nprobingnodes,int nbacktracks,SCIP_Longint nsolsfound,SCIP_Longint nbestsolsfound,SCIP_Longint nconflictsfound,SCIP_Bool leavewassol,SCIP_DIVECONTEXT divecontext)1149 void SCIPupdateDivesetStats(
1150 SCIP* scip, /**< SCIP data structure */
1151 SCIP_DIVESET* diveset, /**< diveset to be reset */
1152 int nprobingnodes, /**< the number of probing nodes explored this time */
1153 int nbacktracks, /**< the number of backtracks during probing this time */
1154 SCIP_Longint nsolsfound, /**< the number of solutions found */
1155 SCIP_Longint nbestsolsfound, /**< the number of best solutions found */
1156 SCIP_Longint nconflictsfound, /**< number of new conflicts found this time */
1157 SCIP_Bool leavewassol, /**< was a solution found at the leaf? */
1158 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */
1159 )
1160 {
1161 assert(scip != NULL);
1162 assert(diveset != NULL);
1163 assert(SCIPinProbing(scip));
1164
1165 SCIPdivesetUpdateStats(diveset, scip->stat, SCIPgetDepth(scip), nprobingnodes, nbacktracks, nsolsfound,
1166 nbestsolsfound, nconflictsfound, leavewassol, divecontext);
1167 }
1168
1169 /** enforces a probing/diving solution by suggesting bound changes that maximize the score w.r.t. the current diving settings
1170 *
1171 * the process is guided by the enforcement priorities of the constraint handlers and the scoring mechanism provided by
1172 * the dive set.
1173 * Constraint handlers may suggest diving bound changes in decreasing order of their enforcement priority, based on the
1174 * solution values in the solution @p sol and the current local bounds of the variables. A diving bound change
1175 * is a triple (variable,branching direction,value) and is used inside SCIPperformGenericDivingAlgorithm().
1176 *
1177 * After a successful call, SCIP holds two arrays of suggested dive bound changes, one for the preferred child
1178 * and one for the alternative.
1179 *
1180 * @see SCIPgetDiveBoundChangeData() for retrieving the dive bound change suggestions.
1181 *
1182 * The method stops after the first constraint handler was successful
1183 *
1184 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
1185 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
1186 *
1187 * @pre This method can be called if @p scip is in one of the following stages:
1188 * - \ref SCIP_STAGE_SOLVING
1189 *
1190 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
1191 */
SCIPgetDiveBoundChanges(SCIP * scip,SCIP_DIVESET * diveset,SCIP_SOL * sol,SCIP_Bool * success,SCIP_Bool * infeasible)1192 SCIP_RETCODE SCIPgetDiveBoundChanges(
1193 SCIP* scip, /**< SCIP data structure */
1194 SCIP_DIVESET* diveset, /**< diving settings to control scoring */
1195 SCIP_SOL* sol, /**< current solution of diving mode */
1196 SCIP_Bool* success, /**< pointer to store whether constraint handler successfully found a variable */
1197 SCIP_Bool* infeasible /**< pointer to store whether the current node was detected to be infeasible */
1198 )
1199 {
1200 int i;
1201
1202 assert(scip != NULL);
1203 assert(diveset != NULL);
1204 assert(SCIPinProbing(scip));
1205 assert(infeasible != NULL);
1206 assert(success != NULL);
1207
1208 SCIP_CALL( SCIPcheckStage(scip, "SCIPgetDiveBoundChanges", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1209
1210 *success = FALSE;
1211 *infeasible = FALSE;
1212
1213 /* we invalidate the previously stored bound changes */
1214 SCIPclearDiveBoundChanges(scip);
1215
1216 /* loop over constraint handlers until a constraint handler successfully found a variable/value assignment for proceeding
1217 * or a constraint handler detected the infeasibility of the local node
1218 */
1219 for( i = 0; i < scip->set->nconshdlrs && !(*success || *infeasible); ++i )
1220 {
1221 SCIP_CALL( SCIPconshdlrGetDiveBoundChanges(scip->set->conshdlrs_enfo[i], scip->set, diveset, sol,
1222 success, infeasible) );
1223 }
1224
1225 #ifndef NDEBUG
1226 /* check if the constraint handler correctly assigned values to the dive set */
1227 if( *success )
1228 {
1229 SCIP_VAR** bdchgvars;
1230 SCIP_BRANCHDIR* bdchgdirs;
1231 SCIP_Real* values;
1232 int nbdchanges;
1233 SCIPtreeGetDiveBoundChangeData(scip->tree, &bdchgvars, &bdchgdirs, &values, &nbdchanges, TRUE);
1234 assert(nbdchanges > 0);
1235 SCIPtreeGetDiveBoundChangeData(scip->tree, &bdchgvars, &bdchgdirs, &values, &nbdchanges, FALSE);
1236 assert(nbdchanges > 0);
1237 }
1238 #endif
1239
1240 return SCIP_OKAY;
1241 }
1242
1243 /** adds a diving bound change to the diving bound change storage of SCIP together with the information if this is a
1244 * bound change for the preferred direction or not
1245 *
1246 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
1247 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
1248 *
1249 * @pre This method can be called if @p scip is in one of the following stages:
1250 * - \ref SCIP_STAGE_SOLVING
1251 *
1252 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
1253 */
SCIPaddDiveBoundChange(SCIP * scip,SCIP_VAR * var,SCIP_BRANCHDIR dir,SCIP_Real value,SCIP_Bool preferred)1254 SCIP_RETCODE SCIPaddDiveBoundChange(
1255 SCIP* scip, /**< SCIP data structure */
1256 SCIP_VAR* var, /**< variable to apply the bound change to */
1257 SCIP_BRANCHDIR dir, /**< direction of the bound change */
1258 SCIP_Real value, /**< value to adjust this variable bound to */
1259 SCIP_Bool preferred /**< is this a bound change for the preferred child? */
1260 )
1261 {
1262 assert(scip->tree != NULL);
1263 assert(scip->mem->probmem != NULL);
1264 assert(SCIPinProbing(scip));
1265
1266 SCIP_CALL( SCIPcheckStage(scip, "SCIPaddDiveBoundChange", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1267
1268 SCIP_CALL( SCIPtreeAddDiveBoundChange(scip->tree, scip->mem->probmem, var, dir, value, preferred) );
1269
1270 return SCIP_OKAY;
1271 }
1272
1273 /** get the dive bound change data for the preferred or the alternative direction
1274 *
1275 * @pre This method can be called if @p scip is in one of the following stages:
1276 * - \ref SCIP_STAGE_SOLVING
1277 *
1278 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
1279 */
SCIPgetDiveBoundChangeData(SCIP * scip,SCIP_VAR *** variables,SCIP_BRANCHDIR ** directions,SCIP_Real ** values,int * ndivebdchgs,SCIP_Bool preferred)1280 void SCIPgetDiveBoundChangeData(
1281 SCIP* scip, /**< SCIP data structure */
1282 SCIP_VAR*** variables, /**< pointer to store variables for the specified direction */
1283 SCIP_BRANCHDIR** directions, /**< pointer to store the branching directions */
1284 SCIP_Real** values, /**< pointer to store bound change values */
1285 int* ndivebdchgs, /**< pointer to store the number of dive bound changes */
1286 SCIP_Bool preferred /**< should the dive bound changes for the preferred child be output? */
1287 )
1288 {
1289 assert(variables != NULL);
1290 assert(directions != NULL);
1291 assert(values != NULL);
1292 assert(ndivebdchgs != NULL);
1293 assert(SCIPinProbing(scip));
1294
1295 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetDiveBoundChangeData", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1296
1297 SCIPtreeGetDiveBoundChangeData(scip->tree, variables, directions, values, ndivebdchgs, preferred);
1298 }
1299
1300 /** clear the dive bound change data structures
1301 *
1302 * @pre This method can be called if @p scip is in one of the following stages:
1303 * - \ref SCIP_STAGE_SOLVING
1304 *
1305 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
1306 */
SCIPclearDiveBoundChanges(SCIP * scip)1307 void SCIPclearDiveBoundChanges(
1308 SCIP* scip /**< SCIP data structure */
1309 )
1310 {
1311 assert(scip->tree != NULL);
1312
1313 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPclearDiveBoundChanges", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1314
1315 SCIPtreeClearDiveBoundChanges(scip->tree);
1316 }
1317