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