Scippy

SCIP

Solving Constraint Integer Programs

scip_probing.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-2022 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  */
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  */
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 */
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  */
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  */
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  */
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  */
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 */
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  */
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  }
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 
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  */
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  }
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 
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  */
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  */
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  }
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  {
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  {
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  */
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);
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 
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  */
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  */
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 
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 
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  */
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 
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
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->transprob, 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
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  */
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  */
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  */
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  */
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  */
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  */
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 */
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 */
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 */
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 */
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  */
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 */
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  */
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  */
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  */
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 
1316 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
SCIP_STAT * stat
Definition: struct_scip.h:70
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2081
SCIP_RETCODE SCIPtreeAddDiveBoundChange(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_VAR *var, SCIP_BRANCHDIR dir, SCIP_Real value, SCIP_Bool preferred)
Definition: tree.c:6265
SCIP_RETCODE SCIPconflictAnalyzeLP(SCIP_CONFLICT *conflict, SCIP_CONFLICTSTORE *conflictstore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, SCIP_Bool *success)
Definition: conflict.c:8667
SCIP_RETCODE SCIPtreeEndProbing(SCIP_TREE *tree, SCIP_REOPT *reopt, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_LP *lp, SCIP_RELAXATION *relaxation, SCIP_PRIMAL *primal, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_CLIQUETABLE *cliquetable)
Definition: tree.c:6859
SCIP_RETCODE SCIPtreeSetProbingLPState(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_LP *lp, SCIP_LPISTATE **lpistate, SCIP_LPINORMS **lpinorms, SCIP_Bool primalfeas, SCIP_Bool dualfeas)
Definition: tree.c:6515
void SCIPstatEnableVarHistory(SCIP_STAT *stat)
Definition: stat.c:157
SCIP_Bool SCIPlpDiving(SCIP_LP *lp)
Definition: lp.c:17813
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:356
SCIP_Real * origobjvals
Definition: struct_tree.h:55
void SCIPlpSetIsRelax(SCIP_LP *lp, SCIP_Bool relax)
Definition: lp.c:17750
public methods for branch and bound tree
SCIP_RETCODE SCIPdivesetGetScore(SCIP_DIVESET *diveset, SCIP_SET *set, SCIP_DIVETYPE divetype, SCIP_VAR *divecand, SCIP_Real divecandsol, SCIP_Real divecandfrac, SCIP_Real *candscore, SCIP_Bool *roundup)
Definition: heur.c:822
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
Definition: scip_probing.c:216
void SCIPdivesetUpdateStats(SCIP_DIVESET *diveset, SCIP_STAT *stat, int depth, int nprobingnodes, int nbacktracks, SCIP_Longint nsolsfound, SCIP_Longint nbestsolsfound, SCIP_Longint nconflictsfound, SCIP_Bool leavesol, SCIP_DIVECONTEXT divecontext)
Definition: heur.c:193
internal methods for branch and bound tree
SCIP_RETCODE SCIPpropagateDomains(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_CONFLICT *conflict, SCIP_CLIQUETABLE *cliquetable, int depth, int maxproprounds, SCIP_PROPTIMING timingmask, SCIP_Bool *cutoff)
Definition: solve.c:635
SCIP_CONFLICT * conflict
Definition: struct_scip.h:87
public methods for memory management
int SCIPgetProbingDepth(SCIP *scip)
Definition: scip_probing.c:189
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_RETCODE SCIPapplyCutsProbing(SCIP *scip, SCIP_Bool *cutoff)
Definition: scip_probing.c:938
int SCIPtreeGetProbingDepth(SCIP_TREE *tree)
Definition: tree.c:8422
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17966
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:55
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPtreeLoadProbingLPState(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_PROB *prob, SCIP_EVENTQUEUE *eventqueue, SCIP_LP *lp)
Definition: tree.c:6569
SCIP_EVENTQUEUE * eventqueue
Definition: struct_scip.h:80
SCIP_PROBINGNODE * probingnode
Definition: struct_tree.h:139
SCIP_PRIMAL * primal
Definition: struct_scip.h:85
void SCIPstatDisableVarHistory(SCIP_STAT *stat)
Definition: stat.c:147
SCIP_RETCODE SCIPtreeBacktrackProbing(SCIP_TREE *tree, SCIP_REOPT *reopt, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_LP *lp, SCIP_PRIMAL *primal, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_CLIQUETABLE *cliquetable, int probingdepth)
Definition: tree.c:6825
SCIP_Real SCIPsetInfinity(SCIP_SET *set)
Definition: set.c:6071
void SCIPgetDiveBoundChangeData(SCIP *scip, SCIP_VAR ***variables, SCIP_BRANCHDIR **directions, SCIP_Real **values, int *ndivebdchgs, SCIP_Bool preferred)
void SCIPswapPointers(void **pointer1, void **pointer2)
Definition: misc.c:10291
SCIP_BRANCHCAND * branchcand
Definition: struct_scip.h:81
#define FALSE
Definition: def.h:87
SCIP_RETCODE SCIPpropagateProbingImplications(SCIP *scip, SCIP_Bool *cutoff)
Definition: scip_probing.c:677
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10755
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
int SCIPtreeGetCurrentDepth(SCIP_TREE *tree)
Definition: tree.c:8394
public methods for problem variables
SCIP_RETCODE SCIPaddDiveBoundChange(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR dir, SCIP_Real value, SCIP_Bool preferred)
SCIP_RETCODE SCIPlpSolveAndEval(SCIP_LP *lp, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_PROB *prob, SCIP_Longint itlim, SCIP_Bool limitresolveiters, SCIP_Bool aging, SCIP_Bool keepsol, SCIP_Bool *lperror)
Definition: lp.c:12404
SCIP_RETCODE SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:292
unsigned int SCIP_DIVETYPE
Definition: type_heur.h:54
SCIP_Bool probingsolvedlp
Definition: struct_tree.h:234
SCIP_PROB * transprob
Definition: struct_scip.h:89
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7444
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
void SCIPvarAdjustLb(SCIP_VAR *var, SCIP_SET *set, SCIP_Real *lb)
Definition: var.c:6513
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:111
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_LPSOLSTAT SCIPlpGetSolstat(SCIP_LP *lp)
Definition: lp.c:13083
internal methods for LP management
SCIP_PROB * origprob
Definition: struct_scip.h:71
SCIP_Bool SCIPtreeIsFocusNodeLPConstructed(SCIP_TREE *tree)
Definition: tree.c:8357
public methods for numerical tolerances
public methods for querying solving statistics
SCIP_PRICESTORE * pricestore
Definition: struct_scip.h:92
public methods for the branch-and-bound tree
enum SCIP_BranchDir SCIP_BRANCHDIR
Definition: type_history.h:39
void SCIPclearDiveBoundChanges(SCIP *scip)
SCIP_Bool SCIPsetIsLT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6246
SCIP_Real SCIPvarGetObjLP(SCIP_VAR *var)
Definition: var.c:12885
SCIP_MEM * mem
Definition: struct_scip.h:62
SCIP_Bool SCIPtreeProbing(SCIP_TREE *tree)
Definition: tree.c:8276
SCIP_RETCODE SCIPsolveProbingRelax(SCIP *scip, SCIP_Bool *cutoff)
Definition: scip_probing.c:967
SCIP_RETCODE SCIPconshdlrGetDiveBoundChanges(SCIP_CONSHDLR *conshdlr, SCIP_SET *set, SCIP_DIVESET *diveset, SCIP_SOL *sol, SCIP_Bool *success, SCIP_Bool *infeasible)
Definition: cons.c:3507
SCIP_Bool probingobjchanged
Definition: struct_tree.h:236
SCIP_CONSHDLR ** conshdlrs_enfo
Definition: struct_set.h:74
internal methods for storing and manipulating the main problem
#define SCIPerrorMessage
Definition: pub_message.h:55
SCIP_EVENTFILTER * eventfilter
Definition: struct_scip.h:79
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip_probing.c:571
SCIP_RETCODE SCIPvarChgObj(SCIP_VAR *var, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_PROB *prob, SCIP_PRIMAL *primal, SCIP_LP *lp, SCIP_EVENTQUEUE *eventqueue, SCIP_Real newobj)
Definition: var.c:6260
SCIP_RETCODE SCIPfixVarProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval)
Definition: scip_probing.c:409
SCIP_RETCODE SCIPcheckStage(SCIP *scip, const char *method, SCIP_Bool init, SCIP_Bool problem, SCIP_Bool transforming, SCIP_Bool transformed, SCIP_Bool initpresolve, SCIP_Bool presolving, SCIP_Bool exitpresolve, SCIP_Bool presolved, SCIP_Bool initsolve, SCIP_Bool solving, SCIP_Bool solved, SCIP_Bool exitsolve, SCIP_Bool freetrans, SCIP_Bool freescip)
Definition: debug.c:2177
static SCIP_RETCODE pricing(SCIP *scip, SCIP_PRICER *pricer, SCIP_Real *lowerbound, SCIP_Bool farkas)
Definition: pricer_stp.c:176
SCIP_CONFLICTSTORE * conflictstore
Definition: struct_scip.h:95
int SCIPsepastoreGetNCuts(SCIP_SEPASTORE *sepastore)
Definition: sepastore.c:1140
#define SCIPreallocMemoryArray(scip, ptr, newnum)
Definition: scip_mem.h:61
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip_probing.c:251
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17251
SCIP_REOPT * reopt
Definition: struct_scip.h:76
char * SCIPsnprintfProbingStats(SCIP *scip, char *strbuf, int len)
SCIP_Real cutoffbound
Definition: struct_lp.h:275
SCIP_RETCODE SCIPlpAddRow(SCIP_LP *lp, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_ROW *row, int depth)
Definition: lp.c:9504
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_Bool SCIPisObjChangedProbing(SCIP *scip)
Definition: scip_probing.c:543
data structures for branch and bound tree
SCIP_Real unchangedobj
Definition: struct_var.h:201
#define SCIP_PROPTIMING_ALWAYS
Definition: type_timing.h:64
const char * SCIPrelaxGetName(SCIP_RELAX *relax)
Definition: relax.c:533
SCIP_Real SCIPgetVarObjProbing(SCIP *scip, SCIP_VAR *var)
Definition: scip_probing.c:379
internal methods for global SCIP settings
#define SCIP_CALL(x)
Definition: def.h:384
SCIP main data structure.
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip_probing.c:810
void SCIPlpMarkDivingObjChanged(SCIP_LP *lp)
Definition: lp.c:17833
internal methods for relaxators
SCIP_Bool SCIPsetIsEQ(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6228
internal methods for storing separated cuts
SCIP_Longint nprobboundchgs
Definition: struct_stat.h:108
void SCIPsetSortRelaxs(SCIP_SET *set)
Definition: set.c:4217
SCIP_CUTPOOL * cutpool
Definition: struct_scip.h:96
void SCIPtreeClearDiveBoundChanges(SCIP_TREE *tree)
Definition: tree.c:6320
SCIP_CLIQUETABLE * cliquetable
Definition: struct_scip.h:88
void 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)
internal methods for problem variables
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
SCIP_SEPASTORE * sepastore
Definition: struct_scip.h:93
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:84
int SCIPgetNImplVars(SCIP *scip)
Definition: scip_prob.c:2126
SCIP_VAR ** origobjvars
Definition: struct_tree.h:54
SCIP_RETCODE SCIPtreeStartProbing(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_LP *lp, SCIP_RELAXATION *relaxation, SCIP_PROB *transprob, SCIP_Bool strongbranching)
Definition: tree.c:6425
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:661
void SCIPtreeGetDiveBoundChangeData(SCIP_TREE *tree, SCIP_VAR ***variables, SCIP_BRANCHDIR **directions, SCIP_Real **values, int *ndivebdchgs, SCIP_Bool preferred)
Definition: tree.c:6297
SCIP_Bool SCIPlpDivingObjChanged(SCIP_LP *lp)
Definition: lp.c:17823
int probingsumchgdobjs
Definition: struct_tree.h:225
SCIP_RETCODE SCIPgetDiveBoundChanges(SCIP *scip, SCIP_DIVESET *diveset, SCIP_SOL *sol, SCIP_Bool *success, SCIP_Bool *infeasible)
methods for debugging
datastructures for block memory pools and memory buffers
SCIP_Bool SCIPprobAllColsInLP(SCIP_PROB *prob, SCIP_SET *set, SCIP_LP *lp)
Definition: prob.c:2300
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17758
datastructures for problem statistics
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
static SCIP_RETCODE solveProbingLP(SCIP *scip, int itlim, SCIP_Bool pricing, SCIP_Bool pretendroot, SCIP_Bool displayinfo, int maxpricerounds, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip_probing.c:698
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2036
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:88
public methods for the LP relaxation, rows and columns
SCIP_RETCODE SCIPrelaxExec(SCIP_RELAX *relax, SCIP_SET *set, SCIP_TREE *tree, SCIP_STAT *stat, int depth, SCIP_Real *lowerbound, SCIP_RESULT *result)
Definition: relax.c:344
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1991
SCIP_Real * r
Definition: circlepacking.c:50
union SCIP_Node::@18 data
SCIP_Bool misc_exactsolve
Definition: struct_set.h:384
void SCIPupdateDivesetLPStats(SCIP *scip, SCIP_DIVESET *diveset, SCIP_Longint niterstoadd, SCIP_DIVECONTEXT divecontext)
general public methods
SCIP_Bool SCIPtreeProbingObjChanged(SCIP_TREE *tree)
Definition: tree.c:8455
enum SCIP_DiveContext SCIP_DIVECONTEXT
Definition: type_heur.h:63
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip_lp.c:238
BMS_BLKMEM * probmem
Definition: struct_mem.h:40
SCIP_RETCODE SCIPsolveProbingLPWithPricing(SCIP *scip, SCIP_Bool pretendroot, SCIP_Bool displayinfo, int maxpricerounds, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip_probing.c:834
internal methods for conflict analysis
SCIP_RETCODE SCIPlpSetCutoffbound(SCIP_LP *lp, SCIP_SET *set, SCIP_PROB *prob, SCIP_Real cutoffbound)
Definition: lp.c:10196
SCIP_RETCODE SCIPpriceLoop(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_PRIMAL *primal, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_PRICESTORE *pricestore, SCIP_SEPASTORE *sepastore, SCIP_CUTPOOL *cutpool, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_CLIQUETABLE *cliquetable, SCIP_Bool pretendroot, SCIP_Bool displayinfo, int maxpricerounds, int *npricedcolvars, SCIP_Bool *mustsepa, SCIP_Bool *lperror, SCIP_Bool *aborted)
Definition: solve.c:2004
internal methods for main solving loop and node processing
SCIP_RETCODE SCIPnodeAddBoundchg(SCIP_NODE *node, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, SCIP_VAR *var, SCIP_Real newbound, SCIP_BOUNDTYPE boundtype, SCIP_Bool probingchange)
Definition: tree.c:2078
public methods for the probing mode
SCIP_RETCODE SCIPtreeMarkProbingNodeHasLP(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_LP *lp)
Definition: tree.c:6651
SCIP_NODE * SCIPtreeGetCurrentNode(SCIP_TREE *tree)
Definition: tree.c:8377
SCIP_SET * set
Definition: struct_scip.h:63
SCIP_RETCODE SCIPsepastoreApplyCuts(SCIP_SEPASTORE *sepastore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_CLIQUETABLE *cliquetable, SCIP_Bool root, SCIP_EFFICIACYCHOICE efficiacychoice, SCIP_Bool *cutoff)
Definition: sepastore.c:912
SCIP_RETCODE SCIPaddRowProbing(SCIP *scip, SCIP_ROW *row)
Definition: scip_probing.c:898
public methods for message output
data structures for LP management
SCIP_Bool SCIPsetIsGT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6282
datastructures for problem variables
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1946
SCIP_MESSAGEHDLR * messagehdlr
Definition: struct_scip.h:66
void SCIPdivesetUpdateLPStats(SCIP_DIVESET *diveset, SCIP_STAT *stat, SCIP_Longint niterstoadd, SCIP_DIVECONTEXT divecontext)
Definition: heur.c:776
SCIP_NODETYPE SCIPnodeGetType(SCIP_NODE *node)
Definition: tree.c:7424
#define SCIP_Real
Definition: def.h:177
internal methods for problem statistics
public methods for relaxation handlers
public methods for message handling
#define SCIP_INVALID
Definition: def.h:197
internal methods for constraints and constraint handlers
#define SCIP_Longint
Definition: def.h:162
SCIP_RETCODE SCIPsetProbingLPState(SCIP *scip, SCIP_LPISTATE **lpistate, SCIP_LPINORMS **lpinorms, SCIP_Bool primalfeas, SCIP_Bool dualfeas)
Definition: scip_probing.c:867
SCIP_TREE * tree
Definition: struct_scip.h:86
SCIP_RELAXATION * relaxation
Definition: struct_scip.h:84
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17976
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
Definition: scip_probing.c:156
SCIP_RETCODE SCIPgetDivesetScore(SCIP *scip, SCIP_DIVESET *diveset, SCIP_DIVETYPE divetype, SCIP_VAR *divecand, SCIP_Real divecandsol, SCIP_Real divecandfrac, SCIP_Real *candscore, SCIP_Bool *roundup)
void SCIPvarAdjustUb(SCIP_VAR *var, SCIP_SET *set, SCIP_Real *ub)
Definition: var.c:6530
int nconshdlrs
Definition: struct_set.h:111
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip_probing.c:110
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:123
#define SCIP_CALL_ABORT(x)
Definition: def.h:363
internal methods for primal heuristics
SCIP_RETCODE SCIPnodePropagateImplics(SCIP_NODE *node, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, SCIP_Bool *cutoff)
Definition: tree.c:2468
SCIP_LP * lp
Definition: struct_scip.h:82
SCIP_SEPASTORE * sepastoreprobing
Definition: struct_scip.h:94
#define SCIPABORT()
Definition: def.h:356
public methods for global and local (sub)problems
SCIP_Longint nprobholechgs
Definition: struct_stat.h:109
SCIP_RETCODE SCIPinitConssLP(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_SEPASTORE *sepastore, SCIP_CUTPOOL *cutpool, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_CLIQUETABLE *cliquetable, SCIP_Bool root, SCIP_Bool firstsubtreeinit, SCIP_Bool *cutoff)
Definition: solve.c:1099
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:336
datastructures for global SCIP settings
SCIP_RETCODE SCIPtreeCreateProbingNode(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_LP *lp)
Definition: tree.c:6490
void SCIPlpUnmarkDivingObjChanged(SCIP_LP *lp)
Definition: lp.c:17844
void SCIPtreeMarkProbingObjChanged(SCIP_TREE *tree)
Definition: tree.c:8466
memory allocation routines
SCIP_RETCODE SCIPchgVarObjProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition: scip_probing.c:465