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-2024 Zuse Institute Berlin (ZIB) */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file 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  /* the LP is a relaxation if and only if the objective has not been changed */
749  SCIPlpSetIsRelax(scip->lp, !scip->tree->probingobjchanged);
750 
751  /* solve probing LP */
752  SCIP_CALL( SCIPlpSolveAndEval(scip->lp, scip->set, scip->messagehdlr, scip->mem->probmem, scip->stat,
753  scip->eventqueue, scip->eventfilter, scip->transprob, (SCIP_Longint)itlim, FALSE, FALSE, FALSE, lperror) );
754 
755  assert((*lperror) || SCIPlpGetSolstat(scip->lp) != SCIP_LPSOLSTAT_NOTSOLVED);
756 
757  /* mark the probing node to have a solved LP */
758  if( !(*lperror) )
759  {
760  SCIP_CALL( SCIPtreeMarkProbingNodeHasLP(scip->tree, scip->mem->probmem, scip->lp) );
761 
762  /* call pricing */
763  if( pricing )
764  {
765  SCIP_Bool mustsepa;
766  int npricedcolvars;
767  SCIP_Bool result;
768 
769  mustsepa = FALSE;
770  SCIP_CALL( SCIPpriceLoop(scip->mem->probmem, scip->set, scip->messagehdlr, scip->stat, scip->transprob,
771  scip->origprob, scip->primal, scip->tree, scip->reopt, scip->lp, scip->pricestore, scip->sepastore, scip->cutpool,
772  scip->branchcand, scip->eventqueue, scip->eventfilter, scip->cliquetable, pretendroot, displayinfo,
773  maxpricerounds, &npricedcolvars, &mustsepa, lperror, &result) );
774 
775  /* mark the probing node again to update the LP size in the node and the tree path */
776  if( !(*lperror) )
777  {
778  SCIP_CALL( SCIPtreeMarkProbingNodeHasLP(scip->tree, scip->mem->probmem, scip->lp) );
779  }
780  }
781  }
782 
783  /* remember that probing might have changed the LPi state; this holds even if solving returned with an LP error */
784  scip->tree->probingsolvedlp = TRUE;
785 
786  /* the LP is infeasible or the objective limit was reached */
787  if( !(*lperror) && (SCIPlpGetSolstat(scip->lp) == SCIP_LPSOLSTAT_INFEASIBLE
790  && SCIPisGE(scip, SCIPgetLPObjval(scip), SCIPgetCutoffbound(scip)))) )
791  {
792  /* analyze the infeasible LP (only if all columns are in the LP and no external pricers exist) */
793  if( !scip->set->misc_exactsolve && SCIPprobAllColsInLP(scip->transprob, scip->set, scip->lp) && !scip->tree->probingobjchanged )
794  {
795  SCIP_CALL( SCIPconflictAnalyzeLP(scip->conflict, scip->conflictstore, scip->mem->probmem, scip->set, scip->stat, scip->transprob,
796  scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue, scip->cliquetable, NULL) );
797  }
798 
799  if( cutoff != NULL )
800  *cutoff = TRUE;
801  }
802 
803  return SCIP_OKAY;
804 }
805 
806 /** solves the LP at the current probing node (cannot be applied at preprocessing stage);
807  * no separation or pricing is applied
808  *
809  * The LP has to be constructed before (you can use SCIPisLPConstructed() or SCIPconstructLP()).
810  *
811  * @note if the LP is infeasible or the objective limit is reached, and if all columns are in the LP and no external
812  * pricers exist then conflict analysis will be run. This can have an effect on the problem after probing ends.
813  *
814  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
815  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
816  *
817  * @pre This method can be called if @p scip is in one of the following stages:
818  * - \ref SCIP_STAGE_SOLVING
819  */
821  SCIP* scip, /**< SCIP data structure */
822  int itlim, /**< maximal number of LP iterations to perform, or -1 for no limit */
823  SCIP_Bool* lperror, /**< pointer to store whether an unresolved LP error occurred */
824  SCIP_Bool* cutoff /**< pointer to store whether the probing LP was infeasible or the objective
825  * limit was reached (or NULL, if not needed) */
826  )
827 {
828  SCIP_CALL( SCIPcheckStage(scip, "SCIPsolveProbingLP", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
829 
830  SCIP_CALL( solveProbingLP(scip, itlim, FALSE, FALSE, FALSE, -1, lperror, cutoff) );
831 
832  return SCIP_OKAY;
833 }
834 
835 /** solves the LP at the current probing node (cannot be applied at preprocessing stage) and applies pricing
836  * until the LP is solved to optimality; no separation is applied
837  *
838  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
839  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
840  *
841  * @pre This method can be called if @p scip is in one of the following stages:
842  * - \ref SCIP_STAGE_SOLVING
843  */
845  SCIP* scip, /**< SCIP data structure */
846  SCIP_Bool pretendroot, /**< should the pricers be called as if we were at the root node? */
847  SCIP_Bool displayinfo, /**< should info lines be displayed after each pricing round? */
848  int maxpricerounds, /**< maximal number of pricing rounds (-1: no limit);
849  * a finite limit means that the LP might not be solved to optimality! */
850  SCIP_Bool* lperror, /**< pointer to store whether an unresolved LP error occurred */
851  SCIP_Bool* cutoff /**< pointer to store whether the probing LP was infeasible or the objective
852  * limit was reached (or NULL, if not needed) */
853  )
854 {
855  SCIP_CALL( SCIPcheckStage(scip, "SCIPsolveProbingLPWithPricing", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
856 
857  SCIP_CALL( solveProbingLP(scip, -1, TRUE, pretendroot, displayinfo, maxpricerounds, lperror, cutoff) );
858 
859  return SCIP_OKAY;
860 }
861 
862 /** sets the LP state for the current probing node
863  *
864  * @note state and norms are stored at the node and later released by SCIP; therefore, the pointers are set
865  * to NULL by the method
866  *
867  * @note the pointers to state and norms must not be NULL; however, they may point to a NULL pointer if the
868  * respective information should not be set
869  *
870  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
871  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
872  *
873  * @pre This method can be called if @p scip is in one of the following stages:
874  * - \ref SCIP_STAGE_PRESOLVING
875  * - \ref SCIP_STAGE_SOLVING
876  */
878  SCIP* scip, /**< SCIP data structure */
879  SCIP_LPISTATE** lpistate, /**< pointer to LP state information (like basis information) */
880  SCIP_LPINORMS** lpinorms, /**< pointer to LP pricing norms information */
881  SCIP_Bool primalfeas, /**< primal feasibility when LP state information was stored */
882  SCIP_Bool dualfeas /**< dual feasibility when LP state information was stored */
883  )
884 {
885  SCIP_CALL( SCIPcheckStage(scip, "SCIPsetProbingLPState", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
886 
887  if( !SCIPtreeProbing(scip->tree) )
888  {
889  SCIPerrorMessage("not in probing mode\n");
890  return SCIP_INVALIDCALL;
891  }
892 
893  SCIP_CALL( SCIPtreeSetProbingLPState(scip->tree, scip->mem->probmem, scip->lp, lpistate, lpinorms, primalfeas, dualfeas) );
894 
895  return SCIP_OKAY;
896 }
897 
898 /** adds a row to the LP in the current probing node
899  *
900  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
901  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
902  *
903  * @pre This method can be called if @p scip is in one of the following stages:
904  * - \ref SCIP_STAGE_SOLVING
905  *
906  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
907  */
909  SCIP* scip, /**< SCIP data structure */
910  SCIP_ROW* row /**< row to be added */
911  )
912 {
913  SCIP_NODE* node;
914  int depth;
915 
916  assert(scip != NULL);
917  assert(row != NULL);
918 
919  SCIP_CALL( SCIPcheckStage(scip, "SCIPaddRowProbing", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
920 
921  if( !SCIPtreeProbing(scip->tree) )
922  {
923  SCIPerrorMessage("not in probing mode\n");
924  return SCIP_INVALIDCALL;
925  }
926 
927  /* get depth of current node */
928  node = SCIPtreeGetCurrentNode(scip->tree);
929  assert(node != NULL);
930  depth = SCIPnodeGetDepth(node);
931 
932  SCIP_CALL( SCIPlpAddRow(scip->lp, scip->mem->probmem, scip->set, scip->eventqueue, scip->eventfilter, row, depth) );
933 
934  return SCIP_OKAY;
935 }
936 
937 
938 /** applies the cuts in the separation storage to the LP and clears the storage afterwards;
939  * this method can only be applied during probing; the user should resolve the probing LP afterwards
940  * in order to get a new solution
941  *
942  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
943  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
944  *
945  * @pre This method can be called if @p scip is in one of the following stages:
946  * - \ref SCIP_STAGE_SOLVING
947  */
949  SCIP* scip, /**< SCIP data structure */
950  SCIP_Bool* cutoff /**< pointer to store whether an empty domain was created */
951  )
952 {
953  SCIP_CALL( SCIPcheckStage(scip, "SCIPapplyCutsProbing", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
954 
955  if( !SCIPtreeProbing(scip->tree) )
956  {
957  SCIPerrorMessage("not in probing mode\n");
958  return SCIP_INVALIDCALL;
959  }
960 
961  SCIP_CALL( SCIPsepastoreApplyCuts(scip->sepastore, scip->mem->probmem, scip->set, scip->stat, scip->transprob,
962  scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue, scip->eventfilter,
963  scip->cliquetable, FALSE, SCIP_EFFICIACYCHOICE_LP, cutoff) );
964 
965  return SCIP_OKAY;
966 }
967 
968 /** solves relaxation(s) at the current probing node (cannot be applied at preprocessing stage);
969  * no separation or pricing is applied
970  *
971  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
972  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
973  *
974  * @pre This method can be called if @p scip is in one of the following stages:
975  * - \ref SCIP_STAGE_SOLVING
976  */
978  SCIP* scip, /**< SCIP data structure */
979  SCIP_Bool* cutoff /**< pointer to store whether a relaxation was infeasible or the objective
980  * limit was reached (or NULL, if not needed) */
981  )
982 {
983  SCIP_SET* set;
984  int r;
985 
986  SCIP_CALL( SCIPcheckStage(scip, "SCIPsolveProbingRelax", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
987 
988  if ( ! SCIPtreeProbing(scip->tree) )
989  {
990  SCIPerrorMessage("not in probing mode\n");
991  return SCIP_INVALIDCALL;
992  }
993  assert( SCIPtreeGetCurrentDepth(scip->tree) > 0 );
994 
995  assert( cutoff != NULL );
996  *cutoff = FALSE;
997 
998  set = scip->set;
999 
1000  /* sort relaxators by priority */
1001  SCIPsetSortRelaxs(set);
1002 
1003  /* solve relaxations */
1004  for (r = 0; r < set->nrelaxs && !(*cutoff); ++r)
1005  {
1006  SCIP_RELAX* relax;
1007  SCIP_Real lowerbound;
1008  SCIP_RESULT result;
1009 
1010  lowerbound = -SCIPinfinity(scip);
1011 
1012  relax = set->relaxs[r];
1013  assert( relax != NULL );
1014 
1015  SCIP_CALL( SCIPrelaxExec(relax, set, scip->tree, scip->stat, SCIPtreeGetCurrentDepth(scip->tree), &lowerbound, &result) );
1016 
1017  switch( result )
1018  {
1019  case SCIP_CUTOFF:
1020  *cutoff = TRUE;
1021  SCIPdebugMsg(scip, " -> relaxator <%s> detected cutoff\n", SCIPrelaxGetName(relax));
1022  break;
1023 
1024  case SCIP_CONSADDED:
1025  case SCIP_REDUCEDDOM:
1026  case SCIP_SEPARATED:
1027  case SCIP_SUSPENDED:
1028  SCIPerrorMessage("The relaxator should not return <%d> within probing mode.\n", result);
1029  break;
1030 
1031  case SCIP_SUCCESS:
1032  case SCIP_DIDNOTRUN:
1033  break;
1034 
1035  default:
1036  SCIPerrorMessage("Invalid result code <%d> of relaxator <%s>\n", result, SCIPrelaxGetName(relax));
1037  return SCIP_INVALIDRESULT;
1038  } /*lint !e788*/
1039  }
1040 
1041  return SCIP_OKAY;
1042 }
1043 
1044 /** print statistics of probing */
1046  SCIP* scip, /**< SCIP data structure */
1047  char* strbuf, /**< string buffer */
1048  int len /**< length of string buffer */
1049  )
1050 {
1051  char* ptr = strbuf;
1052  const int nvartypes = 4;
1053 
1054  assert(scip != NULL);
1055  assert(strbuf != NULL);
1056 
1057  if( SCIPinProbing(scip) )
1058  {
1059  SCIP_VAR** vars;
1060  int nbinvars = SCIPgetNBinVars(scip);
1061  int nintvars = SCIPgetNIntVars(scip);
1062  int nimplvars = SCIPgetNImplVars(scip);
1063  int nvars = SCIPgetNVars(scip);
1064  int vartypeend[] = {
1065  nbinvars,
1066  nbinvars + nintvars,
1067  nbinvars + nintvars + nimplvars,
1068  nvars
1069  };
1070  const char* vartypenames[] = {
1071  "binary",
1072  "integer",
1073  "implicit integer",
1074  "continuous"
1075  };
1076  int nvartypefixed[4];
1077  int nvarsfixed = 0;
1078  int depth;
1079  int probingdepth;
1080  int vartypestart = 0;
1081  int v;
1082  int p;
1083 
1084  vars = SCIPgetVars(scip);
1085  BMSclearMemoryArray(nvartypefixed, nvartypes);
1086 
1087  /* loop over vartypes and count fixings */
1088  for( p = 0; p < nvartypes; ++p )
1089  {
1090  for( v = vartypestart; v < vartypeend[p]; ++v )
1091  {
1092  if( SCIPisEQ(scip, SCIPvarGetLbLocal(vars[v]), SCIPvarGetUbLocal(vars[v])) )
1093  ++nvartypefixed[p];
1094  }
1095  nvarsfixed += nvartypefixed[p];
1096  vartypestart = vartypeend[p];
1097  }
1098 
1099  depth = SCIPgetDepth(scip);
1100  probingdepth = SCIPgetProbingDepth(scip);
1101 
1102  ptr += SCIPsnprintf(ptr, len, "Depth: (%d total, %d probing) ", depth, probingdepth);
1103  ptr += SCIPsnprintf(ptr, len, "Fixed/Variables: %d / %d (", nvarsfixed, vartypeend[nvartypes - 1]);
1104 
1105  for( p = 0; p < nvartypes; ++p )
1106  {
1107  int ntypevars = vartypeend[p] - (p == 0 ? 0 : vartypeend[p - 1]);
1108  ptr += SCIPsnprintf(ptr, len, "%d / %d %s%s", nvartypefixed[p], ntypevars, vartypenames[p], p < (nvartypes - 1) ? ", " : ")");
1109  }
1110  }
1111  else
1112  {
1113  (void) SCIPsnprintf(strbuf, len, "Not in probing");
1114  }
1115 
1116  return strbuf;
1117 }
1118 
1119 /** gets the candidate score and preferred rounding direction for a candidate variable */
1121  SCIP* scip, /**< SCIP data structure */
1122  SCIP_DIVESET* diveset, /**< general diving settings */
1123  SCIP_DIVETYPE divetype, /**< represents different methods for a dive set to explore the next children */
1124  SCIP_VAR* divecand, /**< the candidate for which the branching direction is requested */
1125  SCIP_Real divecandsol, /**< LP solution value of the candidate */
1126  SCIP_Real divecandfrac, /**< fractionality of the candidate */
1127  SCIP_Real* candscore, /**< pointer to store the candidate score */
1128  SCIP_Bool* roundup /**< pointer to store whether preferred direction for diving is upwards */
1129  )
1130 {
1131  assert(scip != NULL);
1132  assert(candscore != NULL);
1133  assert(roundup != NULL);
1134  assert(divecand != NULL);
1135 
1136  SCIP_CALL( SCIPcheckStage(scip, "SCIPgetDivesetScore", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1137 
1138  SCIP_CALL( SCIPdivesetGetScore(diveset, scip->set, divetype, divecand, divecandsol, divecandfrac, candscore,
1139  roundup) );
1140 
1141  return SCIP_OKAY;
1142 }
1143 
1144 /** update diveset LP statistics, should be called after every LP solved by this diving heuristic */
1146  SCIP* scip, /**< SCIP data structure */
1147  SCIP_DIVESET* diveset, /**< diving settings */
1148  SCIP_Longint niterstoadd, /**< additional number of LP iterations to be added */
1149  SCIP_DIVECONTEXT divecontext /**< context for diving statistics */
1150  )
1151 {
1152  assert(scip != NULL);
1153  assert(diveset != NULL);
1154 
1155  SCIPdivesetUpdateLPStats(diveset, scip->stat, niterstoadd, divecontext);
1156 }
1157 
1158 /** update diveset statistics and global diveset statistics */
1160  SCIP* scip, /**< SCIP data structure */
1161  SCIP_DIVESET* diveset, /**< diveset to be reset */
1162  int nprobingnodes, /**< the number of probing nodes explored this time */
1163  int nbacktracks, /**< the number of backtracks during probing this time */
1164  SCIP_Longint nsolsfound, /**< the number of solutions found */
1165  SCIP_Longint nbestsolsfound, /**< the number of best solutions found */
1166  SCIP_Longint nconflictsfound, /**< number of new conflicts found this time */
1167  SCIP_Bool leavewassol, /**< was a solution found at the leaf? */
1168  SCIP_DIVECONTEXT divecontext /**< context for diving statistics */
1169  )
1170 {
1171  assert(scip != NULL);
1172  assert(diveset != NULL);
1173  assert(SCIPinProbing(scip));
1174 
1175  SCIPdivesetUpdateStats(diveset, scip->stat, SCIPgetDepth(scip), nprobingnodes, nbacktracks, nsolsfound,
1176  nbestsolsfound, nconflictsfound, leavewassol, divecontext);
1177 }
1178 
1179 /** enforces a probing/diving solution by suggesting bound changes that maximize the score w.r.t. the current diving settings
1180  *
1181  * the process is guided by the enforcement priorities of the constraint handlers and the scoring mechanism provided by
1182  * the dive set.
1183  * Constraint handlers may suggest diving bound changes in decreasing order of their enforcement priority, based on the
1184  * solution values in the solution @p sol and the current local bounds of the variables. A diving bound change
1185  * is a triple (variable,branching direction,value) and is used inside SCIPperformGenericDivingAlgorithm().
1186  *
1187  * After a successful call, SCIP holds two arrays of suggested dive bound changes, one for the preferred child
1188  * and one for the alternative.
1189  *
1190  * @see SCIPgetDiveBoundChangeData() for retrieving the dive bound change suggestions.
1191  *
1192  * The method stops after the first constraint handler was successful
1193  *
1194  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
1195  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
1196  *
1197  * @pre This method can be called if @p scip is in one of the following stages:
1198  * - \ref SCIP_STAGE_SOLVING
1199  *
1200  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
1201  */
1203  SCIP* scip, /**< SCIP data structure */
1204  SCIP_DIVESET* diveset, /**< diving settings to control scoring */
1205  SCIP_SOL* sol, /**< current solution of diving mode */
1206  SCIP_Bool* success, /**< pointer to store whether constraint handler successfully found a variable */
1207  SCIP_Bool* infeasible /**< pointer to store whether the current node was detected to be infeasible */
1208  )
1209 {
1210  int i;
1211 
1212  assert(scip != NULL);
1213  assert(diveset != NULL);
1214  assert(SCIPinProbing(scip));
1215  assert(infeasible != NULL);
1216  assert(success != NULL);
1217 
1218  SCIP_CALL( SCIPcheckStage(scip, "SCIPgetDiveBoundChanges", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1219 
1220  *success = FALSE;
1221  *infeasible = FALSE;
1222 
1223  /* we invalidate the previously stored bound changes */
1225 
1226  /* loop over constraint handlers until a constraint handler successfully found a variable/value assignment for proceeding
1227  * or a constraint handler detected the infeasibility of the local node
1228  */
1229  for( i = 0; i < scip->set->nconshdlrs && !(*success || *infeasible); ++i )
1230  {
1231  SCIP_CALL( SCIPconshdlrGetDiveBoundChanges(scip->set->conshdlrs_enfo[i], scip->set, diveset, sol,
1232  success, infeasible) );
1233  }
1234 
1235 #ifndef NDEBUG
1236  /* check if the constraint handler correctly assigned values to the dive set */
1237  if( *success )
1238  {
1239  SCIP_VAR** bdchgvars;
1240  SCIP_BRANCHDIR* bdchgdirs;
1241  SCIP_Real* values;
1242  int nbdchanges;
1243  SCIPtreeGetDiveBoundChangeData(scip->tree, &bdchgvars, &bdchgdirs, &values, &nbdchanges, TRUE);
1244  assert(nbdchanges > 0);
1245  SCIPtreeGetDiveBoundChangeData(scip->tree, &bdchgvars, &bdchgdirs, &values, &nbdchanges, FALSE);
1246  assert(nbdchanges > 0);
1247  }
1248 #endif
1249 
1250  return SCIP_OKAY;
1251 }
1252 
1253 /** adds a diving bound change to the diving bound change storage of SCIP together with the information if this is a
1254  * bound change for the preferred direction or not
1255  *
1256  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
1257  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
1258  *
1259  * @pre This method can be called if @p scip is in one of the following stages:
1260  * - \ref SCIP_STAGE_SOLVING
1261  *
1262  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
1263  */
1265  SCIP* scip, /**< SCIP data structure */
1266  SCIP_VAR* var, /**< variable to apply the bound change to */
1267  SCIP_BRANCHDIR dir, /**< direction of the bound change */
1268  SCIP_Real value, /**< value to adjust this variable bound to */
1269  SCIP_Bool preferred /**< is this a bound change for the preferred child? */
1270  )
1271 {
1272  assert(scip->tree != NULL);
1273  assert(scip->mem->probmem != NULL);
1274  assert(SCIPinProbing(scip));
1275 
1276  SCIP_CALL( SCIPcheckStage(scip, "SCIPaddDiveBoundChange", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1277 
1278  SCIP_CALL( SCIPtreeAddDiveBoundChange(scip->tree, scip->mem->probmem, var, dir, value, preferred) );
1279 
1280  return SCIP_OKAY;
1281 }
1282 
1283 /** get the dive bound change data for the preferred or the alternative direction
1284  *
1285  * @pre This method can be called if @p scip is in one of the following stages:
1286  * - \ref SCIP_STAGE_SOLVING
1287  *
1288  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
1289  */
1291  SCIP* scip, /**< SCIP data structure */
1292  SCIP_VAR*** variables, /**< pointer to store variables for the specified direction */
1293  SCIP_BRANCHDIR** directions, /**< pointer to store the branching directions */
1294  SCIP_Real** values, /**< pointer to store bound change values */
1295  int* ndivebdchgs, /**< pointer to store the number of dive bound changes */
1296  SCIP_Bool preferred /**< should the dive bound changes for the preferred child be output? */
1297  )
1298 {
1299  assert(variables != NULL);
1300  assert(directions != NULL);
1301  assert(values != NULL);
1302  assert(ndivebdchgs != NULL);
1303  assert(SCIPinProbing(scip));
1304 
1305  SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetDiveBoundChangeData", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1306 
1307  SCIPtreeGetDiveBoundChangeData(scip->tree, variables, directions, values, ndivebdchgs, preferred);
1308 }
1309 
1310 /** clear the dive bound change data structures
1311  *
1312  * @pre This method can be called if @p scip is in one of the following stages:
1313  * - \ref SCIP_STAGE_SOLVING
1314  *
1315  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
1316  */
1318  SCIP* scip /**< SCIP data structure */
1319  )
1320 {
1321  assert(scip->tree != NULL);
1322 
1323  SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPclearDiveBoundChanges", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1324 
1326 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
SCIP_STAT * stat
Definition: struct_scip.h:80
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2082
SCIP_RETCODE SCIPtreeAddDiveBoundChange(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_VAR *var, SCIP_BRANCHDIR dir, SCIP_Real value, SCIP_Bool preferred)
Definition: tree.c:6321
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)
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:6915
#define NULL
Definition: def.h:267
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:6571
void SCIPstatEnableVarHistory(SCIP_STAT *stat)
Definition: stat.c:166
SCIP_Bool SCIPlpDiving(SCIP_LP *lp)
Definition: lp.c:17847
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:380
SCIP_Real * origobjvals
Definition: struct_tree.h:64
void SCIPlpSetIsRelax(SCIP_LP *lp, SCIP_Bool relax)
Definition: lp.c:17784
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:834
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:203
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:648
SCIP_CONFLICT * conflict
Definition: struct_scip.h:97
public methods for memory management
int SCIPgetProbingDepth(SCIP *scip)
Definition: scip_probing.c:198
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
union SCIP_Node::@19 data
SCIP_RETCODE SCIPapplyCutsProbing(SCIP *scip, SCIP_Bool *cutoff)
Definition: scip_probing.c:948
int SCIPtreeGetProbingDepth(SCIP_TREE *tree)
Definition: tree.c:8478
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18135
#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:6625
SCIP_EVENTQUEUE * eventqueue
Definition: struct_scip.h:90
SCIP_PROBINGNODE * probingnode
Definition: struct_tree.h:148
SCIP_PRIMAL * primal
Definition: struct_scip.h:95
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:6881
SCIP_Real SCIPsetInfinity(SCIP_SET *set)
Definition: set.c:6146
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:10396
SCIP_BRANCHCAND * branchcand
Definition: struct_scip.h:91
#define FALSE
Definition: def.h:94
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:10877
#define TRUE
Definition: def.h:93
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
int SCIPtreeGetCurrentDepth(SCIP_TREE *tree)
Definition: tree.c:8450
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:12413
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:99
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7500
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
void SCIPvarAdjustLb(SCIP_VAR *var, SCIP_SET *set, SCIP_Real *lb)
Definition: var.c:6518
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:13103
internal methods for LP management
SCIP_PROB * origprob
Definition: struct_scip.h:81
SCIP_Bool SCIPtreeIsFocusNodeLPConstructed(SCIP_TREE *tree)
Definition: tree.c:8413
public methods for numerical tolerances
public methods for querying solving statistics
SCIP_PRICESTORE * pricestore
Definition: struct_scip.h:102
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:6321
SCIP_Real SCIPvarGetObjLP(SCIP_VAR *var)
Definition: var.c:12887
SCIP_MEM * mem
Definition: struct_scip.h:72
SCIP_Bool SCIPtreeProbing(SCIP_TREE *tree)
Definition: tree.c:8332
SCIP_RETCODE SCIPsolveProbingRelax(SCIP *scip, SCIP_Bool *cutoff)
Definition: scip_probing.c:977
SCIP_RETCODE SCIPconshdlrGetDiveBoundChanges(SCIP_CONSHDLR *conshdlr, SCIP_SET *set, SCIP_DIVESET *diveset, SCIP_SOL *sol, SCIP_Bool *success, SCIP_Bool *infeasible)
Definition: cons.c:3531
SCIP_Bool probingobjchanged
Definition: struct_tree.h:245
SCIP_CONSHDLR ** conshdlrs_enfo
Definition: struct_set.h:84
internal methods for storing and manipulating the main problem
#define SCIPerrorMessage
Definition: pub_message.h:64
SCIP_EVENTFILTER * eventfilter
Definition: struct_scip.h:89
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:6265
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:2208
SCIP_CONFLICTSTORE * conflictstore
Definition: struct_scip.h:105
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:17420
SCIP_REOPT * reopt
Definition: struct_scip.h:86
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:9509
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:380
SCIP main data structure.
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip_probing.c:820
void SCIPlpMarkDivingObjChanged(SCIP_LP *lp)
Definition: lp.c:17867
internal methods for relaxators
SCIP_Bool SCIPsetIsEQ(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6303
internal methods for storing separated cuts
SCIP_Longint nprobboundchgs
Definition: struct_stat.h:117
void SCIPsetSortRelaxs(SCIP_SET *set)
Definition: set.c:4278
SCIP_CUTPOOL * cutpool
Definition: struct_scip.h:106
void SCIPtreeClearDiveBoundChanges(SCIP_TREE *tree)
Definition: tree.c:6376
SCIP_CLIQUETABLE * cliquetable
Definition: struct_scip.h:98
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:103
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:91
int SCIPgetNImplVars(SCIP *scip)
Definition: scip_prob.c:2127
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:6481
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:6353
SCIP_Bool SCIPlpDivingObjChanged(SCIP_LP *lp)
Definition: lp.c:17857
int probingsumchgdobjs
Definition: struct_tree.h:234
SCIP_RETCODE SCIPgetDiveBoundChanges(SCIP *scip, SCIP_DIVESET *diveset, SCIP_SOL *sol, SCIP_Bool *success, SCIP_Bool *infeasible)
#define MIN(x, y)
Definition: def.h:243
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:2350
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17927
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:2037
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:1992
SCIP_Real * r
Definition: circlepacking.c:59
SCIP_Bool misc_exactsolve
Definition: struct_set.h:395
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:8511
enum SCIP_DiveContext SCIP_DIVECONTEXT
Definition: type_heur.h:73
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:844
internal methods for conflict analysis
SCIP_RETCODE SCIPlpSetCutoffbound(SCIP_LP *lp, SCIP_SET *set, SCIP_PROB *prob, SCIP_Real cutoffbound)
Definition: lp.c:10201
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:2095
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:2133
public methods for the probing mode
SCIP_RETCODE SCIPtreeMarkProbingNodeHasLP(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_LP *lp)
Definition: tree.c:6707
SCIP_NODE * SCIPtreeGetCurrentNode(SCIP_TREE *tree)
Definition: tree.c:8433
SCIP_SET * set
Definition: struct_scip.h:73
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:908
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:6357
datastructures for problem variables
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1947
SCIP_MESSAGEHDLR * messagehdlr
Definition: struct_scip.h:76
void SCIPdivesetUpdateLPStats(SCIP_DIVESET *diveset, SCIP_STAT *stat, SCIP_Longint niterstoadd, SCIP_DIVECONTEXT divecontext)
Definition: heur.c:787
SCIP_NODETYPE SCIPnodeGetType(SCIP_NODE *node)
Definition: tree.c:7480
#define SCIP_Real
Definition: def.h:173
internal methods for problem statistics
public methods for relaxation handlers
public methods for message handling
#define SCIP_INVALID
Definition: def.h:193
internal methods for constraints and constraint handlers
#define SCIP_Longint
Definition: def.h:158
SCIP_RETCODE SCIPsetProbingLPState(SCIP *scip, SCIP_LPISTATE **lpistate, SCIP_LPINORMS **lpinorms, SCIP_Bool primalfeas, SCIP_Bool dualfeas)
Definition: scip_probing.c:877
SCIP_TREE * tree
Definition: struct_scip.h:96
SCIP_RELAXATION * relaxation
Definition: struct_scip.h:94
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18145
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:6535
int nconshdlrs
Definition: struct_set.h:121
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip_probing.c:119
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:130
#define SCIP_CALL_ABORT(x)
Definition: def.h:359
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:2523
SCIP_LP * lp
Definition: struct_scip.h:92
SCIP_SEPASTORE * sepastoreprobing
Definition: struct_scip.h:104
#define SCIPABORT()
Definition: def.h:352
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:1112
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:6546
void SCIPlpUnmarkDivingObjChanged(SCIP_LP *lp)
Definition: lp.c:17878
void SCIPtreeMarkProbingObjChanged(SCIP_TREE *tree)
Definition: tree.c:8522
memory allocation routines
SCIP_RETCODE SCIPchgVarObjProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition: scip_probing.c:474