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
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"
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{
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{
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
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{
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{
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{
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 */
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
328 SCIP_CALL( SCIPnodeAddBoundchg(SCIPtreeGetCurrentNode(scip->tree), scip->mem->probmem, scip->set, scip->stat,
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{
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 */
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
372 SCIP_CALL( SCIPnodeAddBoundchg(SCIPtreeGetCurrentNode(scip->tree), scip->mem->probmem, scip->set, scip->stat,
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
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
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 {
449 SCIP_CALL( SCIPnodeAddBoundchg(SCIPtreeGetCurrentNode(scip->tree), scip->mem->probmem, scip->set, scip->stat,
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 {
455 SCIP_CALL( SCIPnodeAddBoundchg(SCIPtreeGetCurrentNode(scip->tree), scip->mem->probmem, scip->set, scip->stat,
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 {
510 }
511
513 node->data.probingnode->origobjvals[node->data.probingnode->nchgdobjs] = oldobj;
514 ++node->data.probingnode->nchgdobjs;
515 ++scip->tree->probingsumchgdobjs;
516
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
699 SCIP_CALL( SCIPnodePropagateImplics(SCIPtreeGetCurrentNode(scip->tree), scip->mem->probmem, scip->set, scip->stat,
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 */
706static
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);
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
789 (SCIPlpGetSolstat(scip->lp) == SCIP_LPSOLSTAT_OPTIMAL && !scip->tree->probingobjchanged
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{
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
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 */
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}
SCIP_Real * r
Definition: circlepacking.c:59
internal methods for conflict analysis
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 SCIPconshdlrGetDiveBoundChanges(SCIP_CONSHDLR *conshdlr, SCIP_SET *set, SCIP_DIVESET *diveset, SCIP_SOL *sol, SCIP_Bool *success, SCIP_Bool *infeasible)
Definition: cons.c:3529
internal methods for constraints and constraint handlers
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
methods for debugging
#define NULL
Definition: def.h:267
#define SCIP_Longint
Definition: def.h:158
#define SCIP_INVALID
Definition: def.h:193
#define SCIP_Bool
Definition: def.h:91
#define MIN(x, y)
Definition: def.h:243
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define SCIP_CALL_ABORT(x)
Definition: def.h:353
#define SCIPABORT()
Definition: def.h:346
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:380
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2082
int SCIPgetNImplVars(SCIP *scip)
Definition: scip_prob.c:2127
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1992
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1947
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2037
#define SCIPdebugMsg
Definition: scip_message.h:78
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:120
void SCIPswapPointers(void **pointer1, void **pointer2)
Definition: misc.c:10396
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip_lp.c:247
#define SCIPreallocMemoryArray(scip, ptr, newnum)
Definition: scip_mem.h:70
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:64
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
SCIP_NODETYPE SCIPnodeGetType(SCIP_NODE *node)
Definition: tree.c:7483
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7503
SCIP_RETCODE SCIPaddRowProbing(SCIP *scip, SCIP_ROW *row)
Definition: scip_probing.c:908
void SCIPclearDiveBoundChanges(SCIP *scip)
int SCIPgetProbingDepth(SCIP *scip)
Definition: scip_probing.c:198
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)
SCIP_RETCODE SCIPapplyCutsProbing(SCIP *scip, SCIP_Bool *cutoff)
Definition: scip_probing.c:948
void SCIPgetDiveBoundChangeData(SCIP *scip, SCIP_VAR ***variables, SCIP_BRANCHDIR **directions, SCIP_Real **values, int *ndivebdchgs, SCIP_Bool preferred)
SCIP_RETCODE SCIPgetDiveBoundChanges(SCIP *scip, SCIP_DIVESET *diveset, SCIP_SOL *sol, SCIP_Bool *success, SCIP_Bool *infeasible)
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)
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:345
SCIP_RETCODE SCIPsetProbingLPState(SCIP *scip, SCIP_LPISTATE **lpistate, SCIP_LPINORMS **lpinorms, SCIP_Bool primalfeas, SCIP_Bool dualfeas)
Definition: scip_probing.c:877
char * SCIPsnprintfProbingStats(SCIP *scip, char *strbuf, int len)
SCIP_Bool SCIPisObjChangedProbing(SCIP *scip)
Definition: scip_probing.c:552
SCIP_RETCODE SCIPsolveProbingRelax(SCIP *scip, SCIP_Bool *cutoff)
Definition: scip_probing.c:977
SCIP_RETCODE SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:301
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip_probing.c:580
SCIP_RETCODE SCIPchgVarObjProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition: scip_probing.c:474
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
Definition: scip_probing.c:225
void SCIPupdateDivesetLPStats(SCIP *scip, SCIP_DIVESET *diveset, SCIP_Longint niterstoadd, SCIP_DIVECONTEXT divecontext)
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:97
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip_probing.c:119
SCIP_Real SCIPgetVarObjProbing(SCIP *scip, SCIP_VAR *var)
Definition: scip_probing.c:388
SCIP_RETCODE SCIPaddDiveBoundChange(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR dir, SCIP_Real value, SCIP_Bool preferred)
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
Definition: scip_probing.c:165
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip_probing.c:820
SCIP_RETCODE SCIPpropagateProbingImplications(SCIP *scip, SCIP_Bool *cutoff)
Definition: scip_probing.c:686
SCIP_RETCODE SCIPfixVarProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval)
Definition: scip_probing.c:418
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip_probing.c:260
SCIP_RETCODE SCIPsolveProbingLPWithPricing(SCIP *scip, SCIP_Bool pretendroot, SCIP_Bool displayinfo, int maxpricerounds, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip_probing.c:844
const char * SCIPrelaxGetName(SCIP_RELAX *relax)
Definition: relax.c:542
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:670
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18144
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17926
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18134
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10877
void SCIPdivesetUpdateLPStats(SCIP_DIVESET *diveset, SCIP_STAT *stat, SCIP_Longint niterstoadd, SCIP_DIVECONTEXT divecontext)
Definition: heur.c:787
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
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
internal methods for primal heuristics
SCIP_Bool SCIPlpDivingObjChanged(SCIP_LP *lp)
Definition: lp.c:17857
SCIP_LPSOLSTAT SCIPlpGetSolstat(SCIP_LP *lp)
Definition: lp.c:13103
void SCIPlpSetIsRelax(SCIP_LP *lp, SCIP_Bool relax)
Definition: lp.c:17784
void SCIPlpMarkDivingObjChanged(SCIP_LP *lp)
Definition: lp.c:17867
SCIP_Bool SCIPlpDiving(SCIP_LP *lp)
Definition: lp.c:17847
void SCIPlpUnmarkDivingObjChanged(SCIP_LP *lp)
Definition: lp.c:17878
SCIP_RETCODE SCIPlpSetCutoffbound(SCIP_LP *lp, SCIP_SET *set, SCIP_PROB *prob, SCIP_Real cutoffbound)
Definition: lp.c:10201
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_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
internal methods for LP management
memory allocation routines
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:130
SCIP_Bool SCIPprobAllColsInLP(SCIP_PROB *prob, SCIP_SET *set, SCIP_LP *lp)
Definition: prob.c:2350
internal methods for storing and manipulating the main problem
public methods for message output
#define SCIPerrorMessage
Definition: pub_message.h:64
public data structures and miscellaneous methods
public methods for relaxation handlers
public methods for branch and bound tree
public methods for problem variables
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
internal methods for relaxators
general public methods
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for global and local (sub)problems
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
public methods for the probing mode
public methods for querying solving statistics
public methods for the branch-and-bound tree
int SCIPsepastoreGetNCuts(SCIP_SEPASTORE *sepastore)
Definition: sepastore.c:1149
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
internal methods for storing separated cuts
void SCIPsetSortRelaxs(SCIP_SET *set)
Definition: set.c:4196
SCIP_Bool SCIPsetIsEQ(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6221
SCIP_Real SCIPsetInfinity(SCIP_SET *set)
Definition: set.c:6064
SCIP_Bool SCIPsetIsLT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6239
SCIP_Bool SCIPsetIsGT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6275
internal methods for global SCIP settings
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_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 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
void SCIPstatEnableVarHistory(SCIP_STAT *stat)
Definition: stat.c:166
void SCIPstatDisableVarHistory(SCIP_STAT *stat)
Definition: stat.c:156
internal methods for problem statistics
SCIP_PROBINGNODE * probingnode
Definition: struct_tree.h:148
union SCIP_Node::@19 data
SCIP_VAR ** origobjvars
Definition: struct_tree.h:63
SCIP_Real * origobjvals
Definition: struct_tree.h:64
SCIP_Real unchangedobj
Definition: struct_var.h:210
data structures for LP management
datastructures for block memory pools and memory buffers
SCIP main data structure.
datastructures for global SCIP settings
datastructures for problem statistics
data structures for branch and bound tree
datastructures for problem variables
Definition: heur_padm.c:135
SCIP_Bool SCIPtreeIsFocusNodeLPConstructed(SCIP_TREE *tree)
Definition: tree.c:8415
SCIP_Bool SCIPtreeProbing(SCIP_TREE *tree)
Definition: tree.c:8334
SCIP_Bool SCIPtreeProbingObjChanged(SCIP_TREE *tree)
Definition: tree.c:8513
int SCIPtreeGetProbingDepth(SCIP_TREE *tree)
Definition: tree.c:8480
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:6483
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:6573
SCIP_NODE * SCIPtreeGetCurrentNode(SCIP_TREE *tree)
Definition: tree.c:8435
void SCIPtreeMarkProbingObjChanged(SCIP_TREE *tree)
Definition: tree.c:8524
SCIP_RETCODE SCIPtreeAddDiveBoundChange(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_VAR *var, SCIP_BRANCHDIR dir, SCIP_Real value, SCIP_Bool preferred)
Definition: tree.c:6322
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:2487
SCIP_RETCODE SCIPtreeLoadProbingLPState(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_PROB *prob, SCIP_EVENTQUEUE *eventqueue, SCIP_LP *lp)
Definition: tree.c:6627
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:2097
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:6918
void SCIPtreeGetDiveBoundChangeData(SCIP_TREE *tree, SCIP_VAR ***variables, SCIP_BRANCHDIR **directions, SCIP_Real **values, int *ndivebdchgs, SCIP_Bool preferred)
Definition: tree.c:6354
int SCIPtreeGetCurrentDepth(SCIP_TREE *tree)
Definition: tree.c:8452
SCIP_RETCODE SCIPtreeCreateProbingNode(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_LP *lp)
Definition: tree.c:6548
SCIP_RETCODE SCIPtreeMarkProbingNodeHasLP(SCIP_TREE *tree, BMS_BLKMEM *blkmem, SCIP_LP *lp)
Definition: tree.c:6709
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:6884
void SCIPtreeClearDiveBoundChanges(SCIP_TREE *tree)
Definition: tree.c:6377
internal methods for branch and bound tree
enum SCIP_DiveContext SCIP_DIVECONTEXT
Definition: type_heur.h:73
unsigned int SCIP_DIVETYPE
Definition: type_heur.h:63
enum SCIP_BranchDir SCIP_BRANCHDIR
Definition: type_history.h:48
@ SCIP_BOUNDTYPE_UPPER
Definition: type_lp.h:57
@ SCIP_BOUNDTYPE_LOWER
Definition: type_lp.h:56
@ SCIP_LPSOLSTAT_NOTSOLVED
Definition: type_lp.h:42
@ SCIP_LPSOLSTAT_OPTIMAL
Definition: type_lp.h:43
@ SCIP_LPSOLSTAT_INFEASIBLE
Definition: type_lp.h:44
@ SCIP_LPSOLSTAT_OBJLIMIT
Definition: type_lp.h:46
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_CUTOFF
Definition: type_result.h:48
@ SCIP_REDUCEDDOM
Definition: type_result.h:51
@ SCIP_CONSADDED
Definition: type_result.h:52
@ SCIP_SUSPENDED
Definition: type_result.h:57
@ SCIP_SEPARATED
Definition: type_result.h:49
@ SCIP_SUCCESS
Definition: type_result.h:58
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
@ SCIP_INVALIDRESULT
Definition: type_retcode.h:53
@ SCIP_INVALIDDATA
Definition: type_retcode.h:52
@ SCIP_OKAY
Definition: type_retcode.h:42
@ SCIP_INVALIDCALL
Definition: type_retcode.h:51
@ SCIP_MAXDEPTHLEVEL
Definition: type_retcode.h:59
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_EFFICIACYCHOICE_LP
@ SCIP_STAGE_SOLVING
Definition: type_set.h:53
#define SCIP_PROPTIMING_ALWAYS
Definition: type_timing.h:72
@ SCIP_NODETYPE_PROBINGNODE
Definition: type_tree.h:42
SCIP_Real SCIPvarGetObjLP(SCIP_VAR *var)
Definition: var.c:12886
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:6264
void SCIPvarAdjustLb(SCIP_VAR *var, SCIP_SET *set, SCIP_Real *lb)
Definition: var.c:6517
void SCIPvarAdjustUb(SCIP_VAR *var, SCIP_SET *set, SCIP_Real *ub)
Definition: var.c:6534
internal methods for problem variables