Scippy

SCIP

Solving Constraint Integer Programs

reopt.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 reopt.c
26 * @ingroup OTHER_CFILES
27 * @brief data structures and methods for collecting reoptimization information
28 * @author Jakob Witzig
29 */
30
31/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32#include <assert.h>
33#include <string.h>
34
35#include "scip/def.h"
36#include "scip/mem.h"
37#include "scip/event.h"
38#include "scip/scip.h"
39#include "scip/set.h"
40#include "scip/sol.h"
41#include "scip/var.h"
42#include "scip/lp.h"
43#include "scip/misc.h"
44#include "scip/reopt.h"
45#include "scip/tree.h"
46#include "scip/primal.h"
47#include "scip/sepastore.h"
48#include "scip/cutpool.h"
49#include "scip/prob.h"
50#include "scip/cons.h"
52#include "scip/cons_linear.h"
53#include "scip/cons_logicor.h"
54#include "scip/cons_setppc.h"
55#include "scip/cons_linear.h"
56#include "scip/clock.h"
57#include "scip/history.h"
59
60#define DEFAULT_MEM_VARAFTERDUAL 10
61#define DEFAULT_MEM_VAR 10
62#define DEFAULT_MEM_NODES 1000
63#define DEFAULT_MEM_RUN 200
64#define DEFAULT_MEM_DUALCONS 10
65
66#define DEFAULT_RANDSEED 67
67
68/* event handler properties */
69#define EVENTHDLR_NAME "Reopt"
70#define EVENTHDLR_DESC "node event handler for reoptimization"
71
72/* ---------------- Callback methods of event handler ---------------- */
73
74/** exec the event handler */
75static
76SCIP_DECL_EVENTEXEC(eventExecReopt)
77{ /*lint --e{715}*/
78 SCIP_NODE* eventnode;
79 SCIP_Real oldbound;
80 SCIP_Real newbound;
81
82 assert(scip != NULL);
83 assert(eventhdlr != NULL);
84 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
86
88 return SCIP_OKAY;
89
90 eventnode = SCIPgetCurrentNode(scip);
91 oldbound = SCIPeventGetOldbound(event);
92 newbound = SCIPeventGetNewbound(event);
93
94 /* if we are called from the last node in the tree that is cut off, eventnode will be NULL and we do not have to store the bound changes */
95 if( eventnode == NULL )
96 return SCIP_OKAY;
97
98 /* skip if the node is not the focus node */
100 return SCIP_OKAY;
101
102 SCIPdebugMsg(scip, "catch event for node %lld: <%s>: %g -> %g\n", SCIPnodeGetNumber(eventnode),
104
105 assert(SCIPisFeasLT(scip, newbound, oldbound) || SCIPisFeasGT(scip, newbound, oldbound));
106
107 SCIP_CALL( SCIPaddReoptDualBndchg(scip, eventnode, SCIPeventGetVar(event), newbound, oldbound) );
108
109 return SCIP_OKAY;
110}
111
112/** solving process initialization method of event handler (called when branch and bound process is about to begin) */
113static
114SCIP_DECL_EVENTINITSOL(eventInitsolReopt)
115{
116 SCIP_VAR** vars;
117
118 assert(scip != NULL);
119 assert(eventhdlr != NULL);
120 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
121
123 return SCIP_OKAY;
124
125 vars = SCIPgetVars(scip);
126 for( int varnr = 0; varnr < SCIPgetNVars(scip); ++varnr )
127 {
128 if( SCIPvarGetType(vars[varnr]) != SCIP_VARTYPE_CONTINUOUS )
129 {
131 }
132 }
133
134 return SCIP_OKAY;
135}
136
137/** solving process deinitialization method of event handler (called before branch and bound process data is freed) */
138static
139SCIP_DECL_EVENTEXITSOL(eventExitsolReopt)
140{
141 SCIP_VAR** vars;
142
143 assert(scip != NULL);
144
145 assert(eventhdlr != NULL);
146 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
147
149 return SCIP_OKAY;
150
151 vars = SCIPgetVars(scip);
152
153 for( int varnr = 0; varnr < SCIPgetNVars(scip); ++varnr )
154 {
155 if( SCIPvarGetType(vars[varnr]) == SCIP_VARTYPE_BINARY )
156 {
157 SCIP_CALL(SCIPdropVarEvent(scip, vars[varnr], SCIP_EVENTTYPE_GBDCHANGED , eventhdlr, NULL, -1));
158 }
159 }
160 return SCIP_OKAY;
161}
162
163/* ---------------- Callback methods of reoptimization methods ---------------- */
164
165/*
166 * memory growing methods for dynamically allocated arrays
167 */
168
169/** ensures size for activeconss */
170static
172 SCIP_REOPT* reopt, /**< reoptimization data structure */
173 SCIP_SET* set, /**< global SCIP settings */
174 BMS_BLKMEM* blkmem, /**< block memory */
175 int num /**< minimum number of entries to store */
176 )
177{
178 if( reopt->nmaxactiveconss < num )
179 {
180 int newsize = SCIPsetCalcMemGrowSize(set, num + 1);
181
182 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &reopt->activeconss, reopt->nmaxactiveconss, newsize) );
183 reopt->nmaxactiveconss = newsize;
184 }
185 assert(num <= reopt->nmaxactiveconss);
186
187 return SCIP_OKAY;
188}
189
190/** ensures, that sols[pos] array can store at least num entries */
191static
193 SCIP_REOPT* reopt, /**< reoptimization data structure */
194 SCIP_SET* set, /**< global SCIP settings */
195 BMS_BLKMEM* blkmem, /**< block memory */
196 int num, /**< minimum number of entries to store */
197 int runidx /**< run index for which the memory should checked */
198 )
199{
200 assert(runidx >= 0);
201 assert(runidx <= reopt->runsize);
202
203 if( num > reopt->soltree->solssize[runidx] )
204 {
205 int newsize = SCIPsetCalcMemGrowSize(set, num + 1);
206
207 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &reopt->soltree->sols[runidx],
208 reopt->soltree->solssize[runidx], newsize) ); /*lint !e866 */
209
210 reopt->soltree->solssize[runidx] = newsize;
211 }
212 assert(num <= reopt->soltree->solssize[runidx]);
213
214 return SCIP_OKAY;
215}
216
217/** ensures, that sols array can store at least num entries */
218static
220 SCIP_REOPT* reopt, /**< reoptimization data structure */
221 SCIP_SET* set, /**< gloabl SCIP settings */
222 int num, /**< minimum number of entries to store */
223 BMS_BLKMEM* blkmem /**< block memory */
224 )
225{
226 if( num >= reopt->runsize )
227 {
228 int newsize = SCIPsetCalcMemGrowSize(set, num+1);
229 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &reopt->soltree->sols, reopt->runsize, newsize) );
230 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &reopt->soltree->nsols, reopt->runsize, newsize) );
231 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &reopt->soltree->solssize, reopt->runsize, newsize) );
232 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &reopt->prevbestsols, reopt->runsize, newsize) );
233 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &reopt->varhistory, reopt->runsize, newsize) );
234 SCIP_ALLOC( BMSreallocMemoryArray(&reopt->objs, newsize) );
235
236 for( int s = reopt->runsize; s < newsize; ++s )
237 {
238 reopt->varhistory[s] = NULL;
239 reopt->prevbestsols[s] = NULL;
240 reopt->objs[s] = NULL;
241 reopt->soltree->solssize[s] = 0;
242 reopt->soltree->nsols[s] = 0;
243 reopt->soltree->sols[s] = NULL;
244 }
245
246 reopt->runsize = newsize;
247 }
248 assert(num < reopt->runsize);
249
250 return SCIP_OKAY;
251}
252
253/** check the memory of the reoptimization tree and if necessary reallocate */
254static
256 SCIP_REOPTTREE* reopttree, /**< reoptimization tree */
257 SCIP_SET* set, /**< global SCIP settings */
258 BMS_BLKMEM* blkmem /**< block memory */
259 )
260{
261 assert(reopttree != NULL);
262 assert(blkmem != NULL);
263
264 if( SCIPqueueIsEmpty(reopttree->openids) )
265 {
266 int newsize;
267
268 assert(reopttree->nreoptnodes == (int)(reopttree->reoptnodessize));
269
270 newsize = SCIPsetCalcMemGrowSize(set, (int)reopttree->reoptnodessize+1);
271 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &reopttree->reoptnodes, reopttree->reoptnodessize, newsize) ); /*lint !e647*/
272
273 for( unsigned int id = reopttree->reoptnodessize; id < (unsigned int)newsize; ++id )
274 {
275 SCIP_CALL( SCIPqueueInsertUInt(reopttree->openids, id) );
276 reopttree->reoptnodes[id] = NULL;
277 }
278
279 reopttree->reoptnodessize = (unsigned int)newsize;
280 }
281
282 return SCIP_OKAY;
283}
284
285/** check allocated memory of a node within the reoptimization tree and if necessary reallocate */
286static
288 SCIP_REOPTNODE* reoptnode, /**< node of the reoptimization tree */
289 SCIP_SET* set, /**< global SCIP settings */
290 BMS_BLKMEM* blkmem, /**< block memory */
291 int var_mem, /**< memory for variables */
292 int child_mem, /**< memory for child nodes */
293 int conss_mem /**< memory for constraints */
294 )
295{
296 int newsize;
297
298 assert(reoptnode != NULL);
299 assert(blkmem != NULL);
300 assert(var_mem >= 0);
301 assert(child_mem >= 0);
302 assert(conss_mem >= 0);
303
304 /* check allocated memory for variable and bound information */
305 if( var_mem > 0 )
306 {
307 if( reoptnode->varssize == 0 )
308 {
309 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &reoptnode->vars, var_mem) );
310 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &reoptnode->varbounds, var_mem) );
311 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &reoptnode->varboundtypes, var_mem) );
312 reoptnode->varssize = var_mem;
313 }
314 else if( reoptnode->varssize < var_mem )
315 {
316 newsize = SCIPsetCalcMemGrowSize(set, var_mem+1);
317 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &reoptnode->vars, reoptnode->varssize, newsize) );
318 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &reoptnode->varbounds, reoptnode->varssize, newsize) );
319 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &reoptnode->varboundtypes, reoptnode->varssize, newsize) );
320 reoptnode->varssize = newsize;
321 }
322 }
323
324 /* check allocated memory for child node information */
325 if( child_mem > 0 )
326 {
327 if( reoptnode->allocchildmem == 0 )
328 {
329 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &reoptnode->childids, child_mem) );
330 reoptnode->nchilds = 0;
331 reoptnode->allocchildmem = child_mem;
332 }
333 else if( reoptnode->allocchildmem < child_mem )
334 {
335 newsize = SCIPsetCalcMemGrowSize(set, child_mem+1);
336 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &reoptnode->childids, reoptnode->allocchildmem, newsize) );
337 reoptnode->allocchildmem = newsize;
338 }
339 }
340
341 /* check allocated memory for add constraints */
342 if( conss_mem > 0 )
343 {
344 if( reoptnode->consssize == 0 )
345 {
346 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &reoptnode->conss, conss_mem) );
347 reoptnode->nconss = 0;
348 reoptnode->consssize = conss_mem;
349 }
350 else if( reoptnode->consssize < conss_mem )
351 {
352 newsize = SCIPsetCalcMemGrowSize(set, conss_mem);
353 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &reoptnode->conss, reoptnode->consssize, newsize) );
354 reoptnode->consssize = newsize;
355 }
356 }
357
358 return SCIP_OKAY;
359}
360
361/*
362 * local methods
363 */
364
365/** returns the number of stored solutions in the subtree induced by @p solnode */
366static
368 SCIP_SOLNODE* solnode /**< node within the solution tree */
369 )
370{
371 SCIP_SOLNODE* sibling;
372 int nsols;
373
374 assert(solnode != NULL);
375
376 if( solnode->child == NULL && solnode->sol == NULL )
377 return 0;
378 if( solnode->child == NULL && solnode->sol != NULL )
379 return 1;
380
381 nsols = 0;
382 sibling = solnode->child;
383
384 /* traverse through the list */
385 while( sibling != NULL )
386 {
387 nsols += soltreeNInducedSols(sibling);
388 sibling = sibling->sibling;
389 }
390
391 return nsols;
392}
393
394/** returns the similarity of the objective functions of two given iterations */
395static
397 SCIP_REOPT* reopt, /**< reoptimization data */
398 SCIP_SET* set, /**< global SCIP settings */
399 int obj1_id, /**< id of one objective function */
400 int obj2_id, /**< id of the other objective function */
401 SCIP_VAR** vars, /**< problem variables */
402 int nvars /**< number of problem variables */
403 )
404{
405 SCIP_Real similarity;
406 SCIP_Real norm_obj1;
407 SCIP_Real norm_obj2;
408
409 assert(reopt != NULL);
410 assert(vars != NULL);
411 assert(nvars >= 0);
412
413 similarity = 0.0;
414 norm_obj1 = 0.0;
415 norm_obj2 = 0.0;
416
417 /* calculate similarity */
418 for( int v = 0; v < nvars; ++v )
419 {
420 SCIP_VAR* origvar;
421 SCIP_VAR* transvar;
422 SCIP_Real c1;
423 SCIP_Real c2;
424 SCIP_Real lb;
425 SCIP_Real ub;
426
427 origvar = vars[v];
428
429 /* get the original variable */
430 if( !SCIPvarIsOriginal(origvar) )
431 {
432 SCIP_RETCODE retcode;
433 SCIP_Real constant = 0.0;
434 SCIP_Real scalar = 1.0;
435
436 retcode = SCIPvarGetOrigvarSum(&origvar, &scalar, &constant);
437
438 if( retcode != SCIP_OKAY )
439 return SCIP_INVALID;
440 }
441 assert(origvar != NULL && SCIPvarIsOriginal(origvar));
442
443 /* get the transformed variable, we skip globally fixed variables */
444 transvar = SCIPvarGetTransVar(origvar);
445 assert(transvar != NULL);
446
447 lb = SCIPvarGetLbLocal(transvar);
448 ub = SCIPvarGetUbLocal(transvar);
449
450 if( SCIPsetIsFeasLT(set, lb, ub) )
451 {
452 int probidx;
453
454 probidx = SCIPvarGetIndex(origvar);
455 assert(0 <= probidx && probidx < reopt->nobjvars);
456
457 c1 = reopt->objs[obj1_id][probidx];
458 c2 = reopt->objs[obj2_id][probidx];
459
460 /* vector product */
461 similarity += c1*c2;
462 norm_obj1 += SQR(c1);
463 norm_obj2 += SQR(c2);
464 }
465 }
466
467 /* divide similarity by norms of the objective vectors */
468 norm_obj1 = sqrt(norm_obj1);
469 norm_obj2 = sqrt(norm_obj2);
470
471 if( !SCIPsetIsZero(set, norm_obj1) && !SCIPsetIsZero(set, norm_obj2) )
472 similarity /= (norm_obj1 * norm_obj2);
473
474 /* make sure that we are between -1.0 und +1.0 */
475 similarity = MAX(similarity, -1.0);
476 similarity = MIN(similarity, 1.0);
477
478 return similarity;
479}
480
481/** delete the given reoptimization node */
482static
484 SCIP_REOPTNODE** reoptnode, /**< node of the reoptimization tree */
485 BMS_BLKMEM* blkmem /**< block memory */
486 )
487{
488 assert((*reoptnode) != NULL );
489 assert(blkmem != NULL );
490
491 /* delete data for constraints */
492 if( (*reoptnode)->consssize > 0 )
493 {
494 assert((*reoptnode)->conss != NULL);
495
496 for( int c = 0; c < (*reoptnode)->nconss; ++c )
497 {
498 assert((*reoptnode)->conss[c] != NULL);
499 assert((*reoptnode)->conss[c]->vals != NULL);
500 assert((*reoptnode)->conss[c]->vars != NULL);
501
502 BMSfreeBlockMemoryArrayNull(blkmem, &(*reoptnode)->conss[c]->boundtypes, (*reoptnode)->conss[c]->varssize);
503 BMSfreeBlockMemoryArrayNull(blkmem, &(*reoptnode)->conss[c]->vals, (*reoptnode)->conss[c]->varssize);
504 BMSfreeBlockMemoryArrayNull(blkmem, &(*reoptnode)->conss[c]->vars, (*reoptnode)->conss[c]->varssize);
505 BMSfreeBlockMemory(blkmem, &(*reoptnode)->conss[c]); /*lint !e866*/
506 }
507 BMSfreeBlockMemoryArray(blkmem, &(*reoptnode)->conss, (*reoptnode)->consssize);
508 (*reoptnode)->nconss = 0;
509 (*reoptnode)->consssize = 0;
510 (*reoptnode)->conss = NULL;
511 }
512
513 /* free list of children */
514 if( (*reoptnode)->childids != NULL )
515 {
516 BMSfreeBlockMemoryArray(blkmem, &(*reoptnode)->childids, (*reoptnode)->allocchildmem);
517 (*reoptnode)->nchilds = 0;
518 (*reoptnode)->allocchildmem = 0;
519 (*reoptnode)->childids = NULL;
520 }
521
522 /* delete dual constraint */
523 if( (*reoptnode)->dualredscur != NULL )
524 {
525 assert((*reoptnode)->dualredscur->varssize > 0);
526 BMSfreeBlockMemoryArray(blkmem, &(*reoptnode)->dualredscur->boundtypes, (*reoptnode)->dualredscur->varssize);
527 BMSfreeBlockMemoryArray(blkmem, &(*reoptnode)->dualredscur->vals, (*reoptnode)->dualredscur->varssize);
528 BMSfreeBlockMemoryArray(blkmem, &(*reoptnode)->dualredscur->vars, (*reoptnode)->dualredscur->varssize);
529 BMSfreeBlockMemory(blkmem, &(*reoptnode)->dualredscur);
530 (*reoptnode)->dualredscur = NULL;
531 }
532
533 /* delete dual constraint */
534 if( (*reoptnode)->dualredsnex != NULL )
535 {
536 assert((*reoptnode)->dualredsnex->varssize > 0);
537 BMSfreeBlockMemoryArray(blkmem, &(*reoptnode)->dualredsnex->boundtypes, (*reoptnode)->dualredsnex->varssize);
538 BMSfreeBlockMemoryArray(blkmem, &(*reoptnode)->dualredsnex->vals, (*reoptnode)->dualredsnex->varssize);
539 BMSfreeBlockMemoryArray(blkmem, &(*reoptnode)->dualredsnex->vars, (*reoptnode)->dualredsnex->varssize);
540 BMSfreeBlockMemory(blkmem, &(*reoptnode)->dualredsnex);
541 (*reoptnode)->dualredsnex = NULL;
542 }
543
544 /* free boundtypes */
545 if ((*reoptnode)->varboundtypes != NULL )
546 {
547 assert((*reoptnode)->varssize > 0);
548 BMSfreeBlockMemoryArray(blkmem, &(*reoptnode)->varboundtypes, (*reoptnode)->varssize);
549 (*reoptnode)->varboundtypes = NULL;
550 }
551
552 /* free bounds */
553 if ((*reoptnode)->varbounds != NULL )
554 {
555 assert((*reoptnode)->varssize > 0);
556 BMSfreeBlockMemoryArray(blkmem, &(*reoptnode)->varbounds, (*reoptnode)->varssize);
557 (*reoptnode)->varbounds = NULL;
558 }
559
560 /* free variables */
561 if ((*reoptnode)->vars != NULL )
562 {
563 assert((*reoptnode)->varssize > 0);
564 BMSfreeBlockMemoryArray(blkmem, &(*reoptnode)->vars, (*reoptnode)->varssize);
565 (*reoptnode)->vars = NULL;
566 }
567
568 (*reoptnode)->varssize = 0;
569
570 /* free afterdual-boundtypes */
571 if ((*reoptnode)->afterdualvarboundtypes != NULL )
572 {
573 assert((*reoptnode)->afterdualvarssize > 0);
574 BMSfreeBlockMemoryArray(blkmem, &(*reoptnode)->afterdualvarboundtypes, (*reoptnode)->afterdualvarssize);
575 (*reoptnode)->afterdualvarboundtypes = NULL;
576 }
577
578 /* free afterdual-bounds */
579 if ((*reoptnode)->afterdualvarbounds != NULL )
580 {
581 assert((*reoptnode)->afterdualvarssize > 0);
582 BMSfreeBlockMemoryArray(blkmem, &(*reoptnode)->afterdualvarbounds, (*reoptnode)->afterdualvarssize);
583 (*reoptnode)->afterdualvarbounds = NULL;
584 }
585
586 /* free afterdual-variables */
587 if ((*reoptnode)->afterdualvars != NULL )
588 {
589 assert((*reoptnode)->afterdualvarssize > 0);
590 BMSfreeBlockMemoryArray(blkmem, &(*reoptnode)->afterdualvars, (*reoptnode)->afterdualvarssize);
591 (*reoptnode)->afterdualvars = NULL;
592 }
593
594 (*reoptnode)->afterdualvarssize = 0;
595
596 BMSfreeBlockMemory(blkmem, reoptnode);
597 (*reoptnode) = NULL;
598
599 return SCIP_OKAY;
600}
601
602/** reset the given reoptimization node */
603static
605 SCIP_REOPTNODE* reoptnode, /**< reoptimization node */
606 SCIP_SET* set, /**< global SCIP settings */
607 BMS_BLKMEM* blkmem /**< block memory */
608 )
609{
610 assert(reoptnode != NULL);
611 assert(set != NULL);
612 assert(blkmem != NULL);
613
614 /* remove and delete all constraints */
615 if( reoptnode->nconss > 0 )
616 {
617 assert(reoptnode->conss != NULL);
618 assert(reoptnode->consssize > 0);
619
620 for( int c = 0; c < reoptnode->nconss; ++c )
621 {
622 if( !reoptnode->conss[c]->linear )
623 {
624 assert(reoptnode->conss[c]->boundtypes != NULL);
625 BMSfreeBlockMemoryArray(blkmem, &reoptnode->conss[c]->boundtypes, reoptnode->conss[c]->varssize);
626 }
627 BMSfreeBlockMemoryArray(blkmem, &reoptnode->conss[c]->vals, reoptnode->conss[c]->varssize);
628 BMSfreeBlockMemoryArray(blkmem, &reoptnode->conss[c]->vars, reoptnode->conss[c]->varssize);
629 BMSfreeBlockMemory(blkmem, &reoptnode->conss[c]); /*lint !e866 */
630 }
631 reoptnode->nconss = 0;
632 }
633
634 /* remove all children */
635 if( reoptnode->childids != NULL )
636 reoptnode->nchilds = 0;
637
638 /* delete dual constraint */
639 if( reoptnode->dualredscur != NULL )
640 {
641 assert(reoptnode->dualredscur->varssize > 0);
642 if( !reoptnode->dualredscur->linear )
643 {
644 assert(reoptnode->dualredscur->boundtypes != NULL);
645 BMSfreeBlockMemoryArray(blkmem, &reoptnode->dualredscur->boundtypes, reoptnode->dualredscur->varssize);
646 }
647 BMSfreeBlockMemoryArray(blkmem, &reoptnode->dualredscur->vals, reoptnode->dualredscur->varssize);
648 BMSfreeBlockMemoryArray(blkmem, &reoptnode->dualredscur->vars, reoptnode->dualredscur->varssize);
649 BMSfreeBlockMemory(blkmem, &reoptnode->dualredscur);
650 reoptnode->dualredscur = NULL;
651 }
652
653 /* delete dual constraint */
654 if( reoptnode->dualredsnex != NULL )
655 {
656 assert(reoptnode->dualredsnex->varssize > 0);
657 if( !reoptnode->dualredsnex->linear )
658 {
659 assert(reoptnode->dualredsnex->boundtypes != NULL);
660 BMSfreeBlockMemoryArray(blkmem, &reoptnode->dualredsnex->boundtypes, reoptnode->dualredsnex->varssize);
661 }
662 BMSfreeBlockMemoryArray(blkmem, &reoptnode->dualredsnex->vals, reoptnode->dualredsnex->varssize);
663 BMSfreeBlockMemoryArray(blkmem, &reoptnode->dualredsnex->vars, reoptnode->dualredsnex->varssize);
664 BMSfreeBlockMemory(blkmem, &reoptnode->dualredsnex);
665 reoptnode->dualredsnex = NULL;
666 }
667
668 reoptnode->parentID = 0;
669 reoptnode->nvars = 0;
670 reoptnode->nafterdualvars = 0;
671 reoptnode->dualreds = FALSE;
672 reoptnode->reopttype = (unsigned int)SCIP_REOPTTYPE_NONE;
673 reoptnode->lowerbound = -SCIPsetInfinity(set);
674
675 return SCIP_OKAY;
676}
677
678/** delete the node stored at position @p nodeID of the reoptimization tree */
679static
681 SCIP_REOPTTREE* reopttree, /**< reoptimization tree */
682 SCIP_SET* set, /**< global SCIP settings */
683 BMS_BLKMEM* blkmem, /**< block memory */
684 unsigned int id, /**< id of a node */
685 SCIP_Bool softreset /**< delete at the end of the solving process */
686 )
687{
688 assert(reopttree != NULL );
689 assert(id < reopttree->reoptnodessize);
690 assert(reopttree->reoptnodes[id] != NULL );
691
692 if( softreset )
693 {
694 SCIP_CALL( reoptnodeReset(reopttree->reoptnodes[id], set, blkmem) );
695 }
696 else
697 {
698 SCIP_CALL( reoptnodeDelete(&reopttree->reoptnodes[id], blkmem) );
699 }
700
701 assert(softreset || reopttree->reoptnodes[id] == NULL);
702 assert(reopttree->reoptnodes[id] == NULL || reopttree->reoptnodes[id]->conss == NULL || reopttree->reoptnodes[id]->nconss == 0);
703 assert(reopttree->reoptnodes[id] == NULL || reopttree->reoptnodes[id]->childids == NULL || reopttree->reoptnodes[id]->nchilds == 0);
704
705 --reopttree->nreoptnodes;
706
707 return SCIP_OKAY;
708}
709
710/** constructor of the solution tree */
711static
713 SCIP_SOLTREE* soltree, /**< solution tree */
714 BMS_BLKMEM* blkmem /**< block memory */
715 )
716{
717 assert(soltree != NULL);
718
722
723 for( int s = 0; s < DEFAULT_MEM_RUN; ++s )
724 {
725 soltree->nsols[s] = 0;
726 soltree->solssize[s] = 0;
727 soltree->sols[s] = NULL;
728 }
729
730 /* allocate the root node */
731 SCIP_ALLOC( BMSallocBlockMemory(blkmem, &soltree->root) );
732 soltree->root->sol = NULL;
733 soltree->root->value = SCIP_INVALID;
734 soltree->root->updated = FALSE;
735 soltree->root->father = NULL;
736 soltree->root->child = NULL;
737 soltree->root->sibling = NULL;
738
739 return SCIP_OKAY;
740}
741
742/** free the given solution node */
743static
745 SCIP_REOPT* reopt, /**< reoptimization data */
746 SCIP_SET* set, /**< global SCIP settings */
747 SCIP_PRIMAL* primal, /**< the primal */
748 BMS_BLKMEM* blkmem, /**< block memory */
749 SCIP_SOLNODE** solnode /**< node within the solution tree */
750 )
751{
752 SCIP_SOLNODE* child;
753 SCIP_SOLNODE* sibling;
754
755 assert(reopt != NULL);
756 assert(set != NULL);
757 assert(primal != NULL || set->stage == SCIP_STAGE_INIT);
758 assert(solnode != NULL);
759 assert(blkmem != NULL);
760
761 child = (*solnode)->child;
762
763 /* traverse through the list and free recursive all subtree */
764 while( child != NULL )
765 {
766 SCIP_CALL( soltreefreeNode(reopt, set, primal, blkmem, &child) );
767 assert(child != NULL);
768
769 sibling = child->sibling;
770 BMSfreeBlockMemoryNull(blkmem, &child);
771 child = sibling;
772 }
773
774 if( (*solnode)->sol != NULL )
775 {
776 assert(set->stage == SCIP_STAGE_PROBLEM);
777
778 SCIP_CALL( SCIPsolFree(&(*solnode)->sol, blkmem, primal) );
779 }
780
781 return SCIP_OKAY;
782}
783
784/** free the solution tree */
785static
787 SCIP_REOPT* reopt, /**< reoptimization data */
788 SCIP_SET* set, /**< global SCIP settings */
789 SCIP_PRIMAL* origprimal, /**< the origprimal */
790 BMS_BLKMEM* blkmem /**< block memory */
791 )
792{
793 assert(reopt != NULL);
794 assert(reopt->soltree != NULL);
795 assert(reopt->soltree->root != NULL);
796 assert(set != NULL);
797 assert(blkmem != NULL);
798
799 /* free all nodes recursive */
800 SCIP_CALL( soltreefreeNode(reopt, set, origprimal, blkmem, &reopt->soltree->root) );
801 BMSfreeBlockMemoryNull(blkmem, &reopt->soltree->root);
802
803 BMSfreeBlockMemoryArray(blkmem, &reopt->soltree->sols, reopt->runsize);
804 BMSfreeBlockMemoryArray(blkmem, &reopt->soltree->nsols, reopt->runsize);
805 BMSfreeBlockMemoryArray(blkmem, &reopt->soltree->solssize, reopt->runsize);
806
807 BMSfreeMemory(&reopt->soltree);
808
809 return SCIP_OKAY;
810}
811
812/** creates and adds a solution node to the solution tree */
813static
815 SCIP_SET* set, /**< global SCIP settings */
816 BMS_BLKMEM* blkmem, /**< block memory */
817 SCIP_SOLNODE* curnode, /**< current node in the solution tree */
818 SCIP_SOLNODE** child, /**< pointer to store the node representing the solution value */
819 SCIP_VAR* var, /**< variable represented by this node */
820 SCIP_Real val, /**< value the child shell represent */
821 SCIP_Bool* added /**< TRUE iff we created a new node, i.e, we have not seen this solution so far */
822 )
823{
824 SCIP_SOLNODE* solnode;
825
826 assert(set != NULL);
827 assert(blkmem != NULL);
828 assert(curnode != NULL);
829 assert(child != NULL && *child == NULL);
830 assert(!SCIPsetIsInfinity(set, -val) && !SCIPsetIsInfinity(set, val));
831
832 /* get the first node of the child node list */
833 *child = curnode->child;
834
835 /* this is the first solution in the subtree induced by the current node */
836 if( *child == NULL )
837 {
838 assert(soltreeNInducedSols(curnode) == 0);
839
840 SCIP_ALLOC( BMSallocBlockMemory(blkmem, &solnode) );
841 solnode->sol = NULL;
842 solnode->updated = FALSE;
843 solnode->father = curnode;
844 solnode->child = NULL;
845 solnode->sibling = NULL;
846 solnode->value = val;
847#ifndef NDEBUG
848 assert(var != NULL);
849 solnode->var = var;
850#endif
851
852 *added = TRUE;
853 *child = solnode;
854
855 curnode->child = *child;
856
857#ifdef SCIP_MORE_DEBUG
858 SCIPsetDebugMsg(set, "-> create new node %p: value=%g, sibling=%p\n", (void*) solnode, solnode->value,
859 (void*) solnode->sibling);
860#endif
861 }
862 else
863 {
864 /* we traverse through all children */
865 while( *child != NULL )
866 {
867#ifdef SCIP_MORE_DEBUG
868 SCIPsetDebugMsg(set, "-> check %p: father=%p, value=%g, sibling=%p\n", (void*) *child, (void*) (*child)->father,
869 (*child)->value, (void*) (*child)->sibling);
870#endif
871 /* we found a node repesenting this solution value */
872 if( SCIPsetIsEQ(set, val, (*child)->value) )
873 break;
874
875 /* we are at the end of the list */
876 if( (*child)->sibling == NULL )
877 {
878 /* create a new solnode */
879 SCIP_ALLOC( BMSallocBlockMemory(blkmem, &solnode) );
880 solnode->sol = NULL;
881 solnode->updated = FALSE;
882 solnode->father = curnode;
883 solnode->child = NULL;
884 solnode->value = val;
885#ifndef NDEBUG
886 assert(var != NULL);
887 solnode->var = var;
888#endif
889 *added = TRUE;
890
891 /* we have to append the new node at the end of the list. but we have to check whether the insertion before
892 * the current node would be correct. in that case, we switch the values, the child pointer, and the
893 * solution
894 */
895 solnode->sibling = NULL;
896 (*child)->sibling = solnode;
897
898#ifdef SCIP_MORE_DEBUG
899 SCIPsetDebugMsg(set, "-> create new node %p: value=%g, sibling=%p\n", (void*) solnode, solnode->value,
900 (void*) solnode->sibling);
901#endif
902 /* the given value is lower than the current, insertion before the current node would be correct
903 * in this case we do not have to change the child pointer
904 */
905 if( SCIPsetIsLT(set, val, (*child)->value) )
906 {
907#ifdef SCIP_MORE_DEBUG
908 SCIPsetDebugMsg(set, "-> need to switch:\n");
909 SCIPsetDebugMsg(set, " before switching: node %p witch child=%p, sibling=%p, sol=%p, value=%g\n",
910 (void*) (*child), (void*) (*child)->child, (void*) (*child)->sibling, (void*) (*child)->sol,
911 (*child)->value);
912 SCIPsetDebugMsg(set, " node %p witch child=%p, sibling=%p, sol=%p, value=%g\n",
913 (void*) solnode, (void*) solnode->child, (void*) solnode->sibling, (void*) solnode->sol,
914 solnode->value);
915#endif
916 /* switch child pointer */
917 solnode->child = (*child)->child;
918 (*child)->child = NULL;
919
920 /* switch solution values */
921 solnode->value = (*child)->value;
922 (*child)->value = val;
923 assert(SCIPsetIsLT(set, (*child)->value, solnode->value));
924
925 /* switch solution pointer */
926 solnode->sol = (*child)->sol;
927 (*child)->sol = NULL;
928#ifdef SCIP_MORE_DEBUG
929 SCIPsetDebugMsg(set, " after switching: node %p witch child=%p, sibling=%p, sol=%p, value=%g\n",
930 (void*) (*child), (void*) (*child)->child, (void*) (*child)->sibling, (void*) (*child)->sol,
931 (*child)->value);
932 SCIPsetDebugMsg(set, " node %p witch child=%p, sibling=%p, sol=%p, value=%g\n",
933 (void*) solnode, (void*) solnode->child, (void*) solnode->sibling, (void*) solnode->sol,
934 solnode->value);
935#endif
936 }
937 /* set the child pointer to the new created solnode */
938 else
939 (*child) = solnode;
940
941 break;
942 }
943
944 /* the next sibling represents a solution value of larger size.
945 * we insert a new node between the current child and the next sibling.
946 */
947 if( SCIPsetIsLT(set, val, (*child)->sibling->value) )
948 {
949 /* create a new solnode that points to the sibling of the current child */
950 SCIP_ALLOC( BMSallocBlockMemory(blkmem, &solnode) );
951 solnode->sol = NULL;
952 solnode->updated = FALSE;
953 solnode->father = curnode;
954 solnode->child = NULL;
955 solnode->sibling = (*child)->sibling;
956 solnode->value = val;
957#ifndef NDEBUG
958 assert(var != NULL);
959 solnode->var = var;
960#endif
961 *added = TRUE;
962
963 /* change the poiter of the next sibling to the new node */
964 (*child)->sibling = solnode;
965
966 *child = solnode;
967#ifdef SCIP_MORE_DEBUG
968 SCIPsetDebugMsg(set, "-> create new node %p: value=%g, sibling=%p\n", (void*) solnode, solnode->value,
969 (void*) solnode->sibling);
970#endif
971 break;
972 }
973
974 /* go to the next sibling */
975 *child = (*child)->sibling;
976 }
977
978#ifdef SCIP_DEBUG
979 /* check whether the insert was correct and the list is increasing */
980 solnode = curnode->child;
981 assert(solnode != NULL);
982
983 while( solnode->sibling != NULL )
984 {
985 assert(SCIPsetIsLT(set, solnode->value, solnode->sibling->value));
986 solnode = solnode->sibling;
987 }
988#endif
989 }
990 return SCIP_OKAY;
991}
992
993/** add a solution to the solution tree */
994static
996 SCIP_REOPT* reopt, /**< reoptimization data */
997 SCIP_SET* set, /**< global SCIP settings */
998 SCIP_STAT* stat, /**< dynamic problem statistics */
999 SCIP_PRIMAL* origprimal, /**< orig primal */
1000 BMS_BLKMEM* blkmem, /**< block memory */
1001 SCIP_VAR** vars, /**< array of original variables */
1002 SCIP_SOL* sol, /**< solution to add */
1003 SCIP_SOLNODE** solnode, /**< current solution node */
1004 int nvars, /**< number of variables */
1005 SCIP_Bool bestsol, /**< is the solution an optimal (best found) solution */
1006 SCIP_Bool* added /**< pointer to store the result */
1007 )
1008{
1009 SCIP_SOLNODE* cursolnode;
1010 SCIP_Bool purelp;
1011
1012 assert(reopt != NULL);
1013 assert(set != NULL);
1014 assert(stat != NULL);
1015 assert(origprimal != NULL);
1016 assert(blkmem != NULL);
1017 assert(vars != NULL);
1018 assert(sol != NULL);
1019 assert(solnode != NULL);
1020
1021 cursolnode = reopt->soltree->root;
1022 *added = FALSE;
1023 purelp = TRUE;
1024
1025 if( set->reopt_savesols > 0 )
1026 {
1027#ifdef MORE_DEBUG
1028 SCIPsetDebugMsg(set, "try to add solution found by <%s>\n", (SCIPsolGetHeur(sol) == NULL ?
1029 "relaxation" : SCIPheurGetName(SCIPsolGetHeur(sol))));
1030#endif
1031
1032 for( int varid = 0; varid < nvars; ++varid )
1033 {
1034 if( SCIPvarGetType(vars[varid]) != SCIP_VARTYPE_CONTINUOUS )
1035 {
1036 SCIP_SOLNODE* child;
1037
1038 purelp = FALSE;
1039 child = NULL;
1040 SCIP_CALL( solnodeAddChild(set, blkmem, cursolnode, &child, vars[varid],
1041 SCIPsolGetVal(sol, set, stat, vars[varid]), added) );
1042 assert(child != NULL);
1043 cursolnode = child;
1044 }
1045 }
1046
1047 /* the solution was added or is an optimal solution */
1048 if( (*added || bestsol) && !purelp )
1049 {
1050 SCIP_SOL* copysol;
1051
1052 assert(cursolnode->child == NULL);
1053
1054 if( *added )
1055 {
1056 SCIP_CALL( SCIPsolCopy(&copysol, blkmem, set, stat, origprimal, sol) );
1057 cursolnode->sol = copysol;
1058 }
1059 else
1060 /* this is a pseudo add; we do not want to save this solution more than once, but we will link this solution
1061 * to the solution storage of this round
1062 */
1063 (*added) = TRUE;
1064
1065 if( bestsol )
1066 {
1067 assert(reopt->prevbestsols != NULL);
1068 assert(cursolnode->sol != NULL);
1069
1070 reopt->prevbestsols[reopt->run-1] = cursolnode->sol;
1071 }
1072
1073 (*solnode) = cursolnode;
1074 }
1075 }
1076
1077 return SCIP_OKAY;
1078}
1079
1080/** reset all marks 'updated' to FALSE */
1081static
1083 SCIP_SOLNODE* node /**< node within the solution tree */
1084 )
1085{
1086 assert(node != NULL);
1087
1088 if( node->child != NULL )
1089 {
1090 SCIP_SOLNODE* child;
1091
1092 /* the node is no leaf */
1093 assert(node->sol == NULL);
1094 assert(!node->updated);
1095
1096 child = node->child;
1097
1098 /* traverse through the list of siblings */
1099 while( child != NULL )
1100 {
1101 soltreeResetMarks(child);
1102 child = child->sibling;
1103 }
1104 }
1105 else
1106 {
1107 /* the node is a leaf */
1108 assert(node->father != NULL);
1109 assert(node->sol != NULL);
1110 node->updated = FALSE;
1111 }
1112}
1113
1114/** allocate memory for a node within the reoptimization tree */
1115static
1117 SCIP_REOPTTREE* reopttree, /**< reoptimization tree */
1118 SCIP_SET* set, /**< global SCIP settings */
1119 BMS_BLKMEM* blkmem, /**< block memory */
1120 unsigned int id /**< id of the node to create */
1121 )
1122{
1123 assert(reopttree != NULL );
1124 assert(id < reopttree->reoptnodessize);
1125
1126 SCIPsetDebugMsg(set, "create a reoptnode at ID %u\n", id);
1127
1128 if( reopttree->reoptnodes[id] == NULL )
1129 {
1130 SCIP_ALLOC( BMSallocBlockMemory(blkmem, &reopttree->reoptnodes[id]) ); /*lint !e866*/
1131
1132 reopttree->reoptnodes[id]->conss = NULL;
1133 reopttree->reoptnodes[id]->nconss = 0;
1134 reopttree->reoptnodes[id]->consssize = 0;
1135 reopttree->reoptnodes[id]->childids = NULL;
1136 reopttree->reoptnodes[id]->allocchildmem = 0;
1137 reopttree->reoptnodes[id]->nchilds = 0;
1138 reopttree->reoptnodes[id]->nvars = 0;
1139 reopttree->reoptnodes[id]->nafterdualvars = 0;
1140 reopttree->reoptnodes[id]->parentID = 0;
1141 reopttree->reoptnodes[id]->dualreds = FALSE;
1142 reopttree->reoptnodes[id]->reopttype = (unsigned int)SCIP_REOPTTYPE_NONE;
1143 reopttree->reoptnodes[id]->varssize = 0;
1144 reopttree->reoptnodes[id]->afterdualvarssize = 0;
1145 reopttree->reoptnodes[id]->vars = NULL;
1146 reopttree->reoptnodes[id]->varbounds = NULL;
1147 reopttree->reoptnodes[id]->varboundtypes = NULL;
1148 reopttree->reoptnodes[id]->afterdualvars = NULL;
1149 reopttree->reoptnodes[id]->afterdualvarbounds = NULL;
1150 reopttree->reoptnodes[id]->afterdualvarboundtypes = NULL;
1151 reopttree->reoptnodes[id]->dualredscur = NULL;
1152 reopttree->reoptnodes[id]->dualredsnex = NULL;
1153 reopttree->reoptnodes[id]->lowerbound = -SCIPsetInfinity(set);
1154 }
1155 else
1156 {
1157 assert(reopttree->reoptnodes[id]->nvars == 0);
1158 assert(reopttree->reoptnodes[id]->nafterdualvars == 0);
1159 reopttree->reoptnodes[id]->reopttype = (unsigned int)SCIP_REOPTTYPE_NONE;
1160 reopttree->reoptnodes[id]->lowerbound = -SCIPsetInfinity(set);
1161 }
1162
1163 /* increase the counter */
1164 ++reopttree->nreoptnodes;
1165
1166 assert(reopttree->nreoptnodes + SCIPqueueNElems(reopttree->openids) == (int)reopttree->reoptnodessize);
1167
1168 return SCIP_OKAY;
1169}
1170
1171/** constructor of the reoptimization tree */
1172static
1174 SCIP_REOPTTREE* reopttree, /**< pointer to the reoptimization tree */
1175 SCIP_SET* set, /**< global SCIP settings */
1176 BMS_BLKMEM* blkmem /**< block memory */
1177 )
1178{
1179 assert(reopttree != NULL);
1180 assert(set != NULL);
1181 assert(blkmem != NULL);
1182
1183 /* allocate memory */
1184 reopttree->reoptnodessize = DEFAULT_MEM_NODES;
1185 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &reopttree->reoptnodes, reopttree->reoptnodessize) );
1186
1187 /* initialize the queue of open IDs */
1188 SCIP_CALL( SCIPqueueCreate(&reopttree->openids, (int)reopttree->reoptnodessize, 2.0) );
1189
1190 /* fill the queue, but reserve the 0 for the root */
1191 for( unsigned int id = 1; id < reopttree->reoptnodessize; ++id )
1192 {
1193 reopttree->reoptnodes[id] = NULL;
1194 SCIP_CALL( SCIPqueueInsertUInt(reopttree->openids, id) );
1195 }
1196 assert(SCIPqueueNElems(reopttree->openids) == (int)(reopttree->reoptnodessize)-1);
1197
1198 reopttree->nreoptnodes = 0;
1199 reopttree->ntotalfeasnodes = 0;
1200 reopttree->nfeasnodes = 0;
1201 reopttree->ninfnodes = 0;
1202 reopttree->ntotalinfnodes= 0;
1203 reopttree->nprunednodes = 0;
1204 reopttree->ntotalprunednodes= 0;
1205 reopttree->ncutoffreoptnodes = 0;
1206 reopttree->ntotalcutoffreoptnodes = 0;
1207
1208 /* initialize the root node */
1209 reopttree->reoptnodes[0] = NULL;
1210 SCIP_CALL( createReoptnode(reopttree, set, blkmem, 0) );
1211
1212 return SCIP_OKAY;
1213}
1214
1215/** clears the reopttree, e.g., to restart and solve the next problem from scratch */
1216static
1218 SCIP_REOPTTREE* reopttree, /**< reoptimization tree */
1219 SCIP_SET* set, /**< global SCIP settings */
1220 BMS_BLKMEM* blkmem, /**< block memory */
1221 SCIP_Bool softreset /**< delete nodes before exit the solving process */
1222 )
1223{
1224 assert(reopttree != NULL );
1225
1226 /* clear queue with open IDs */
1227 SCIPqueueClear(reopttree->openids);
1228 assert(SCIPqueueNElems(reopttree->openids) == 0);
1229
1230 /* delete all data about nodes */
1231 for( unsigned int id = 0; id < reopttree->reoptnodessize; ++id )
1232 {
1233 if( reopttree->reoptnodes[id] != NULL )
1234 {
1235 SCIP_CALL( reopttreeDeleteNode(reopttree, set, blkmem, id, softreset) );
1236 assert(reopttree->reoptnodes[id] == NULL || reopttree->reoptnodes[id]->nvars == 0);
1237 }
1238
1239 if( id > 0 )
1240 {
1241 SCIP_CALL( SCIPqueueInsertUInt(reopttree->openids, id) );
1242 }
1243 }
1244 assert(SCIPqueueNElems(reopttree->openids) == (int)(reopttree->reoptnodessize)-1);
1245
1246 reopttree->nreoptnodes = 0;
1247
1248 return SCIP_OKAY;
1249}
1250
1251/** free the reoptimization tree */
1252static
1254 SCIP_REOPTTREE* reopttree, /**< reoptimization tree data */
1255 SCIP_SET* set, /**< global SCIP settings */
1256 BMS_BLKMEM* blkmem /**< block memory */
1257 )
1258{
1259 assert(reopttree != NULL);
1260 assert(blkmem != NULL);
1261
1262 /* free nodes */
1263 SCIP_CALL( clearReoptnodes(reopttree, set, blkmem, FALSE) );
1264
1265 /* free the data */
1266 BMSfreeBlockMemoryArray(blkmem, &reopttree->reoptnodes, reopttree->reoptnodessize);
1267 SCIPqueueFree(&reopttree->openids);
1268
1269 /* free the tree itself */
1270 BMSfreeMemory(&reopttree);
1271
1272 return SCIP_OKAY;
1273}
1274
1275/** check memory for the constraint to handle bound changes based on dual information */
1276static
1278 SCIP_REOPT* reopt, /**< reoptimization data structure */
1279 SCIP_SET* set, /**< global SCIP settings */
1280 BMS_BLKMEM* blkmem, /**< block memory */
1281 int size /**< size which need to be allocated */
1282 )
1283{
1284 assert(reopt != NULL);
1285 assert(blkmem != NULL);
1286 assert(size > 0);
1287
1288 if( reopt->dualreds == NULL )
1289 {
1290 SCIP_ALLOC( BMSallocBlockMemory(blkmem, &reopt->dualreds) );
1291 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &reopt->dualreds->vars, size) );
1292 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &reopt->dualreds->vals, size) );
1293 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &reopt->dualreds->boundtypes, size) );
1294 reopt->dualreds->varssize = size;
1295 reopt->dualreds->nvars = 0;
1296 }
1297 else if( reopt->dualreds->varssize < size )
1298 {
1299 int newsize = SCIPsetCalcMemGrowSize(set, size+1);
1300 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &reopt->dualreds->vars, reopt->dualreds->varssize, newsize) );
1301 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &reopt->dualreds->vals, reopt->dualreds->varssize, newsize) );
1302 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &reopt->dualreds->boundtypes, reopt->dualreds->varssize, newsize) );
1303 reopt->dualreds->varssize = newsize;
1304 }
1305
1306 return SCIP_OKAY;
1307}
1308
1309/** check the memory to store global constraints */
1310static
1312 SCIP_REOPT* reopt, /**< reoptimization data structure */
1313 SCIP_SET* set, /**< global SCIP settings */
1314 BMS_BLKMEM* blkmem, /**< block memory */
1315 int mem /**< memory which has to be allocated */
1316 )
1317{
1318 assert(reopt != NULL);
1319 assert(blkmem != NULL);
1320 assert(mem > 0);
1321
1322 if( mem > 0 ) /*lint !e774*/
1323 {
1324 if( reopt->glbconss == NULL )
1325 {
1326 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &reopt->glbconss, mem) );
1327 reopt->nglbconss = 0;
1328 reopt->allocmemglbconss = mem;
1329
1330 for( int c = 0; c < reopt->allocmemglbconss; ++c )
1331 reopt->glbconss[c] = NULL;
1332 }
1333 else if( reopt->allocmemglbconss < mem )
1334 {
1335 int newsize = SCIPsetCalcMemGrowSize(set, mem+1);
1336
1337 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &reopt->glbconss, reopt->allocmemglbconss, newsize) );
1338
1339 for( int c = reopt->allocmemglbconss; c < newsize; ++c )
1340 reopt->glbconss[c] = NULL;
1341
1342 reopt->allocmemglbconss = newsize;
1343 }
1344 }
1345
1346 return SCIP_OKAY;
1347}
1348
1349/** reactivate globally valid constraints that were deactivated and necessary to ensure correctness */
1350static
1352 SCIP_REOPT* reopt, /**< reoptimization data structure */
1353 SCIP_SET* set, /**< global SCIP settings */
1354 BMS_BLKMEM* blkmem /**< block memory */
1355 )
1356{
1357 assert(reopt != NULL);
1358
1359 /* exit if there are no active constraints */
1360 if( reopt->nactiveconss == 0 )
1361 return SCIP_OKAY;
1362
1363 SCIPsetDebugMsg(set, "Cleaning %d active conss.\n", reopt->nactiveconss);
1364 assert(reopt->activeconss != NULL);
1365 assert(reopt->activeconssset != NULL);
1366 assert(reopt->nactiveconss <= reopt->nmaxactiveconss);
1367
1368 /* loop over all stored constraints and reactivate deactivated constraints */
1369 for( int i = 0; i < reopt->nactiveconss; ++i )
1370 {
1371 assert(reopt->activeconss[i] != NULL);
1372 assert(SCIPhashsetExists(reopt->activeconssset, reopt->activeconss[i]));
1373 SCIP_CALL( SCIPconsRelease(&reopt->activeconss[i], blkmem, set) );
1374 }
1375
1376 /* also clean up hashset */
1378 reopt->nactiveconss = 0;
1379
1380 return SCIP_OKAY;
1381}
1382
1383/** update the bound changes made by propagations during current iteration; stop saving the bound changes if
1384 * we reach a branching decision based on a dual information
1385 */
1386static
1388 SCIP_REOPT* reopt, /**< reoptimization data structure */
1389 SCIP_SET* set, /**< global SCIP settings */
1390 BMS_BLKMEM* blkmem, /**< block memory */
1391 SCIP_NODE* node, /**< node of the search tree */
1392 unsigned int id, /**< id of the node */
1393 SCIP_Bool* transintoorig /**< transform variables into originals */
1394 )
1395{
1396 int nvars;
1397 int nconsprops;
1398 int npropprops;
1399 int naddedbndchgs;
1400
1401 assert(reopt != NULL);
1402 assert(blkmem != NULL);
1403 assert(node != NULL);
1404 assert(0 < id && id < reopt->reopttree->reoptnodessize);
1405 assert(reopt->reopttree->reoptnodes[id] != NULL );
1406
1407 /* get the number of all stored constraint and propagator propagations */
1408 SCIPnodeGetNDomchg(node, NULL, &nconsprops, &npropprops);
1409 nvars = reopt->reopttree->reoptnodes[id]->nvars;
1410
1411 if( nconsprops > 0 || npropprops > 0 )
1412 {
1413 /* check the memory */
1414 SCIP_CALL( reoptnodeCheckMemory(reopt->reopttree->reoptnodes[id], set, blkmem, nvars + nconsprops + npropprops, 0, 0) );
1415
1417 &reopt->reopttree->reoptnodes[id]->vars[nvars],
1418 &reopt->reopttree->reoptnodes[id]->varbounds[nvars],
1419 &reopt->reopttree->reoptnodes[id]->varboundtypes[nvars],
1420 &naddedbndchgs,
1421 reopt->reopttree->reoptnodes[id]->varssize-nvars);
1422
1423 assert(nvars + naddedbndchgs <= reopt->reopttree->reoptnodes[id]->varssize);
1424
1425 reopt->reopttree->reoptnodes[id]->nvars += naddedbndchgs;
1426
1427 *transintoorig = TRUE;
1428 }
1429
1430 return SCIP_OKAY;
1431}
1432
1433/** save bound changes made after the first bound change based on dual information, e.g., mode by strong branching
1434 *
1435 * This method can be used during reoptimization. If we want to reconstruct a node containing dual bound changes we
1436 * have to split the node into the original one and at least one node representing the pruned part. All bound changes,
1437 * i.e., (constraint) propagation, made after the first bound change based on dual information are still valid for
1438 * the original node after changing the objective function. thus, we can store them for the following iterations.
1439 *
1440 * It should be noted, that these bound changes will be found by (constraint) propagation methods anyway after changing
1441 * the objective function. do not saving these information and find them again might be useful for conflict analysis.
1442 */
1443static
1445 SCIP_REOPT* reopt, /**< reoptimization data structure */
1446 SCIP_SET* set, /**< global SCIP settings */
1447 BMS_BLKMEM* blkmem, /**< block memory */
1448 SCIP_NODE* node, /**< node of the search tree */
1449 unsigned int id, /**< id of the node */
1450 SCIP_Bool* transintoorig /**< transform variables into originals */
1451 )
1452{
1453 int nbranchvars;
1454
1455 assert(reopt != NULL);
1456 assert(blkmem != NULL);
1457 assert(node != NULL);
1458 assert(0 < id && id < reopt->reopttree->reoptnodessize);
1459 assert(reopt->reopttree->reoptnodes[id] != NULL );
1460
1461 nbranchvars = 0;
1462
1463 /* allocate memory */
1464 if (reopt->reopttree->reoptnodes[id]->afterdualvarssize == 0)
1465 {
1466 assert(reopt->reopttree->reoptnodes[id]->afterdualvars == NULL );
1467 assert(reopt->reopttree->reoptnodes[id]->afterdualvarbounds == NULL );
1468 assert(reopt->reopttree->reoptnodes[id]->afterdualvarboundtypes == NULL );
1469
1470 /* allocate block memory for node information */
1473 reopt->reopttree->reoptnodes[id]->afterdualvarssize) );
1475 reopt->reopttree->reoptnodes[id]->afterdualvarssize) );
1477 reopt->reopttree->reoptnodes[id]->afterdualvarssize) );
1478 }
1479
1480 assert(reopt->reopttree->reoptnodes[id]->afterdualvarssize > 0);
1481 assert(reopt->reopttree->reoptnodes[id]->nafterdualvars >= 0);
1482
1487 &nbranchvars,
1489
1490 if( nbranchvars > reopt->reopttree->reoptnodes[id]->afterdualvarssize - reopt->reopttree->reoptnodes[id]->nafterdualvars )
1491 {
1492 int newsize = SCIPsetCalcMemGrowSize(set, reopt->reopttree->reoptnodes[id]->nafterdualvars + nbranchvars);
1494 reopt->reopttree->reoptnodes[id]->afterdualvarssize, newsize) );
1496 reopt->reopttree->reoptnodes[id]->afterdualvarssize, newsize) );
1498 reopt->reopttree->reoptnodes[id]->afterdualvarssize, newsize) );
1499 reopt->reopttree->reoptnodes[id]->afterdualvarssize = newsize;
1500
1505 &nbranchvars,
1507 }
1508
1509 /* the stored variables of this node need to be transformed into the original space */
1510 if( nbranchvars > 0 )
1511 *transintoorig = TRUE;
1512
1513 SCIPsetDebugMsg(set, " -> save %d bound changes after dual reductions\n", nbranchvars);
1514
1515 assert(reopt->reopttree->reoptnodes[id]->nafterdualvars + nbranchvars <= reopt->reopttree->reoptnodes[id]->afterdualvarssize); /* this should be the case */
1516
1517 reopt->reopttree->reoptnodes[id]->nafterdualvars += nbranchvars;
1518
1519 return SCIP_OKAY;
1520}
1521
1522/** store cuts that are active in the current LP */
1523static
1525 SCIP_REOPT* reopt, /**< reoptimization data structure */
1526 SCIP_SET* set, /**< global SCIP settings */
1527 BMS_BLKMEM* blkmem, /**< block memory */
1528 SCIP_LP* lp, /**< current LP */
1529 unsigned int id /**< id in the reopttree */
1530 )
1531{
1532 SCIP_ROW** lprows;
1533 int nlprows;
1534
1535 assert(reopt != NULL);
1536 assert(set != NULL);
1537 assert(lp != NULL);
1538 assert(blkmem != NULL);
1539
1540 lprows = SCIPlpGetRows(lp);
1541 nlprows = SCIPlpGetNRows(lp);
1542
1543 for( int r = 0; r < nlprows; ++r )
1544 {
1545 /* we can break if we reach the first row that is not part of the current LP */
1546 if( SCIProwGetLPPos(lprows[r]) == -1 )
1547 break;
1548
1549 /* currently we only want to store cuts generated by a seperator */
1550 if( SCIProwGetOrigintype(lprows[r]) == SCIP_ROWORIGINTYPE_SEPA && SCIProwGetAge(lprows[r]) <= set->reopt_maxcutage )
1551 {
1552 SCIP_VAR** cutvars;
1553 SCIP_COL** cols;
1554 SCIP_Real* cutvals;
1555 SCIP_Real lhs;
1556 SCIP_Real rhs;
1557 int ncutvars;
1558 SCIP_Bool storecut;
1559
1560 ncutvars = SCIProwGetNLPNonz(lprows[r]);
1561 lhs = SCIProwGetLhs(lprows[r]);
1562 rhs = SCIProwGetRhs(lprows[r]);
1563
1564 /* subtract row constant */
1565 if( !SCIPsetIsInfinity(set, -lhs) )
1566 lhs -= SCIProwGetConstant(lprows[r]);
1567 if( !SCIPsetIsInfinity(set, rhs) )
1568 rhs -= SCIProwGetConstant(lprows[r]);
1569
1570 cutvals = SCIProwGetVals(lprows[r]);
1571 cols = SCIProwGetCols(lprows[r]);
1572 storecut = TRUE;
1573
1574 SCIP_CALL( SCIPsetAllocBufferArray(set, &cutvars, ncutvars) );
1575
1576 for( int c = 0; c < ncutvars; ++c )
1577 {
1578 SCIP_Real constant;
1579 SCIP_Real scalar;
1580
1581 cutvars[c] = SCIPcolGetVar(cols[c]);
1582 assert(cutvars[c] != NULL);
1583
1584 constant = 0.0;
1585 scalar = 1.0;
1586
1587 SCIP_CALL( SCIPvarGetOrigvarSum(&cutvars[c], &scalar, &constant) );
1588
1589 /* the cut contains an artificial variable that might not be present after modifying the problem */
1590 if( cutvars[c] != NULL )
1591 {
1592 storecut = FALSE;
1593 break;
1594 }
1595
1596 assert(cutvars[c] != NULL);
1597 assert(!SCIPsetIsZero(set, scalar));
1598
1599 /* subtract constant from sides */
1600 if( !SCIPsetIsZero(set, constant) && !SCIPsetIsInfinity(set, -lhs) )
1601 lhs -= constant;
1602 if( !SCIPsetIsZero(set, constant) && !SCIPsetIsInfinity(set, rhs) )
1603 rhs -= constant;
1604
1605 cutvals[c] = cutvals[c]/scalar;
1606 }
1607
1608 if( storecut )
1609 {
1610 /* add cut as a linear constraint */
1611 SCIP_CALL( SCIPreoptnodeAddCons(reopt->reopttree->reoptnodes[id], set, blkmem, cutvars, cutvals, NULL,
1612 lhs, rhs, ncutvars, REOPT_CONSTYPE_CUT, TRUE) );
1613 }
1614
1615 SCIPsetFreeBufferArray(set, &cutvars);
1616 }
1617 }
1618
1619 return SCIP_OKAY;
1620}
1621
1622/** transform variable and bounds back to the original space */
1623static
1625 SCIP_REOPT* reopt, /**< reoptimization data structure */
1626 unsigned int id /**< id of the node */
1627 )
1628{
1629 assert(reopt != NULL );
1630 assert(0 < id && id < reopt->reopttree->reoptnodessize);
1631 assert(reopt->reopttree->reoptnodes[id] != NULL );
1632
1633 /* transform branching variables and bound changes applied before the first dual reduction */
1634 for( int varnr = 0; varnr < reopt->reopttree->reoptnodes[id]->nvars; ++varnr )
1635 {
1636 SCIP_Real constant = 0.0;
1637 SCIP_Real scalar = 1.0;
1638
1639 if( !SCIPvarIsOriginal(reopt->reopttree->reoptnodes[id]->vars[varnr]) )
1640 {
1641 SCIP_CALL( SCIPvarGetOrigvarSum(&reopt->reopttree->reoptnodes[id]->vars[varnr], &scalar, &constant)) ;
1642 reopt->reopttree->reoptnodes[id]->varbounds[varnr] = (reopt->reopttree->reoptnodes[id]->varbounds[varnr] - constant) / scalar;
1643 }
1644 assert(SCIPvarIsOriginal(reopt->reopttree->reoptnodes[id]->vars[varnr]));
1645 }
1646
1647 /* transform bound changes affected by dual reduction */
1648 for( int varnr = 0; varnr < reopt->reopttree->reoptnodes[id]->nafterdualvars; ++varnr )
1649 {
1650 SCIP_Real constant = 0.0;
1651 SCIP_Real scalar = 1.0;
1652
1653 if( !SCIPvarIsOriginal(reopt->reopttree->reoptnodes[id]->afterdualvars[varnr]) )
1654 {
1655 SCIP_CALL( SCIPvarGetOrigvarSum(&reopt->reopttree->reoptnodes[id]->afterdualvars[varnr], &scalar, &constant)) ;
1656 reopt->reopttree->reoptnodes[id]->afterdualvarbounds[varnr]
1657 = (reopt->reopttree->reoptnodes[id]->afterdualvarbounds[varnr] - constant) / scalar;
1658 }
1659 assert(SCIPvarIsOriginal(reopt->reopttree->reoptnodes[id]->afterdualvars[varnr]));
1660 }
1661
1662 return SCIP_OKAY;
1663}
1664
1665/** search the next node along the root path that was saved by reoptimization */
1666static
1668 SCIP_REOPT* reopt, /**< reoptimization data structure */
1669 SCIP_SET* set, /**< global SCIP settings */
1670 SCIP_NODE* node, /**< node of the search tree */
1671 SCIP_NODE** parent, /**< parent node within the search tree */
1672 unsigned int* parentid, /**< id of the parent node */
1673 int* nbndchgs /**< number of bound changes */
1674 )
1675{
1676 assert(reopt != NULL);
1677 assert(reopt->reopttree != NULL);
1678 assert(reopt->reopttree->reoptnodes != NULL);
1679
1680 (*nbndchgs) = 0;
1681 (*parent) = node;
1682
1683 /* look for a saved parent along the root-path */
1684 while( SCIPnodeGetDepth(*parent) != 0 )
1685 {
1686 int nbranchings = 0;
1687 int nconsprop = 0;
1688 int npropprops = 0;
1689
1690 if( set->reopt_saveprop )
1691 SCIPnodeGetNDomchg((*parent), &nbranchings, &nconsprop, &npropprops);
1692 else
1693 SCIPnodeGetNDomchg((*parent), &nbranchings, NULL, NULL);
1694
1695 (*nbndchgs) = (*nbndchgs) + nbranchings + nconsprop + npropprops;
1696 (*parent) = SCIPnodeGetParent(*parent);
1697 (*parentid) = SCIPnodeGetReoptID(*parent);
1698
1699 if( SCIPnodeGetDepth(*parent) == 0)
1700 {
1701 (*parentid) = 0;
1702 break;
1703 }
1704 else if( SCIPnodeGetReopttype((*parent)) >= SCIP_REOPTTYPE_TRANSIT )
1705 {
1706 /* this is a special case: due to re-propagation the node could be already deleted. We need to reset reoptid
1707 * and reopttype and continue upto we have found the last stored node
1708 */
1709 if( reopt->reopttree->reoptnodes[*parentid] == NULL )
1710 {
1711 SCIPnodeSetReoptID(*parent, 0);
1713 }
1714 else
1715 {
1716 assert(reopt->reopttree->reoptnodes[*parentid] != NULL);
1717 assert(SCIPnodeGetReoptID((*parent)) < reopt->reopttree->reoptnodessize);
1718 assert((*parentid) && (*parentid) < reopt->reopttree->reoptnodessize);
1719 break;
1720 }
1721 }
1722 }
1723
1724 return SCIP_OKAY;
1725}
1726
1727/** adds the id @p childid to the array of child nodes of @p parentid */
1728static
1730 SCIP_REOPTTREE* reopttree, /**< reoptimization tree */
1731 SCIP_SET* set, /**< global SCIP settings */
1732 BMS_BLKMEM* blkmem, /**< block memory */
1733 unsigned int parentid, /**< id of the parent node */
1734 unsigned int childid /**< id of the child node */
1735 )
1736{
1737 int nchilds;
1738
1739 assert(reopttree != NULL);
1740 assert(blkmem != NULL);
1741 assert(parentid < (unsigned int)reopttree->reoptnodessize);
1742 assert(childid < (unsigned int)reopttree->reoptnodessize);
1743 assert(reopttree->reoptnodes[parentid] != NULL);
1744
1745 nchilds = reopttree->reoptnodes[parentid]->nchilds;
1746
1747 /* ensure that the array is large enough */
1748 SCIP_CALL( reoptnodeCheckMemory(reopttree->reoptnodes[parentid], set, blkmem, 0, nchilds+1, 0) );
1749 assert(reopttree->reoptnodes[parentid]->allocchildmem > nchilds);
1750
1751 /* add the child */
1752 reopttree->reoptnodes[parentid]->childids[nchilds] = childid;
1753 ++reopttree->reoptnodes[parentid]->nchilds;
1754
1755 SCIPsetDebugMsg(set, "add ID %u as a child of ID %u.\n", childid, parentid);
1756
1757 return SCIP_OKAY;
1758}
1759
1760/** move all children to the next node (along the root path) stored in the reoptimization tree */
1761static
1763 SCIP_REOPT* reopt, /**< reoptimization data structure */
1764 SCIP_SET* set, /**< global SCIP settings */
1765 BMS_BLKMEM* blkmem, /**< block memory */
1766 unsigned int nodeid, /**< id of the node */
1767 unsigned int parentid /**< id of the parent node */
1768 )
1769{
1770 unsigned int childid;
1771 int nvars;
1772
1773 assert(reopt != NULL);
1774 assert(blkmem != NULL);
1775 assert(0 < nodeid && nodeid < reopt->reopttree->reoptnodessize);
1776 assert(parentid < reopt->reopttree->reoptnodessize);
1777 assert(reopt->reopttree->reoptnodes[nodeid]->childids != NULL);
1778
1779 /* ensure that enough memory at the parentID is available */
1780 SCIP_CALL( reoptnodeCheckMemory(reopt->reopttree->reoptnodes[parentid], set, blkmem, 0,
1781 reopt->reopttree->reoptnodes[parentid]->nchilds + reopt->reopttree->reoptnodes[nodeid]->nchilds, 0) );
1782
1783 while( reopt->reopttree->reoptnodes[nodeid]->nchilds > 0 )
1784 {
1785 int nchilds;
1786
1787 nchilds = reopt->reopttree->reoptnodes[nodeid]->nchilds;
1788 childid = reopt->reopttree->reoptnodes[nodeid]->childids[nchilds-1];
1789 assert(0 < childid && childid < reopt->reopttree->reoptnodessize);
1790
1791 /* check the memory */
1792 SCIP_CALL( reoptnodeCheckMemory(reopt->reopttree->reoptnodes[childid], set, blkmem,
1793 reopt->reopttree->reoptnodes[childid]->nvars + reopt->reopttree->reoptnodes[nodeid]->nvars, 0, 0) );
1794 assert(reopt->reopttree->reoptnodes[childid]->varssize >= reopt->reopttree->reoptnodes[childid]->nvars
1795 + reopt->reopttree->reoptnodes[nodeid]->nvars);
1796
1797 /* save branching information */
1798 for( int varnr = 0; varnr < reopt->reopttree->reoptnodes[nodeid]->nvars; ++varnr )
1799 {
1800 nvars = reopt->reopttree->reoptnodes[childid]->nvars;
1801 reopt->reopttree->reoptnodes[childid]->vars[nvars] = reopt->reopttree->reoptnodes[nodeid]->vars[varnr];
1802 reopt->reopttree->reoptnodes[childid]->varbounds[nvars] = reopt->reopttree->reoptnodes[nodeid]->varbounds[varnr];
1803 reopt->reopttree->reoptnodes[childid]->varboundtypes[nvars] = reopt->reopttree->reoptnodes[nodeid]->varboundtypes[varnr];
1804 ++reopt->reopttree->reoptnodes[childid]->nvars;
1805 }
1806
1807 /* update the ID of the parent node */
1808 reopt->reopttree->reoptnodes[childid]->parentID = parentid;
1809
1810 /* insert the node as a child */
1811 SCIP_CALL( reoptAddChild(reopt->reopttree, set, blkmem, parentid, childid) );
1812
1813 /* reduce the number of child nodes by 1 */
1814 --reopt->reopttree->reoptnodes[nodeid]->nchilds;
1815 }
1816
1817 return SCIP_OKAY;
1818}
1819
1820/** delete all nodes in the subtree induced by nodeID */
1821static
1823 SCIP_REOPTTREE* reopttree, /**< reoptimization tree */
1824 SCIP_SET* set, /**< global SCIP settings */
1825 BMS_BLKMEM* blkmem, /**< block memory */
1826 unsigned int id, /**< id of the node */
1827 SCIP_Bool delnodeitself, /**< should the node be deleted after deleting the induced subtree? */
1828 SCIP_Bool exitsolve /**< will the solving process end after deletion */
1829 )
1830{
1831 assert(reopttree != NULL );
1832 assert(blkmem != NULL);
1833 assert(id < reopttree->reoptnodessize);
1834 assert(reopttree->reoptnodes[id] != NULL);
1835
1836 /* delete all children below */
1837 if( reopttree->reoptnodes[id]->childids != NULL && reopttree->reoptnodes[id]->nchilds > 0 )
1838 {
1839 SCIPsetDebugMsg(set, "-> delete subtree induced by ID %u (hard remove = %u)\n", id, exitsolve);
1840
1841 while( reopttree->reoptnodes[id]->nchilds > 0 )
1842 {
1843 int nchilds;
1844 unsigned int childid;
1845
1846 nchilds = reopttree->reoptnodes[id]->nchilds;
1847 childid = reopttree->reoptnodes[id]->childids[nchilds-1];
1848 assert(0 < childid && childid < reopttree->reoptnodessize);
1849
1850 SCIP_CALL( deleteChildrenBelow(reopttree, set, blkmem, childid, TRUE, exitsolve) );
1851
1852 --reopttree->reoptnodes[id]->nchilds;
1853 }
1854 }
1855
1856 /* delete node data*/
1857 if( delnodeitself )
1858 {
1859 SCIP_CALL( reopttreeDeleteNode(reopttree, set, blkmem, id, exitsolve) );
1860 SCIP_CALL( SCIPqueueInsertUInt(reopttree->openids, id) );
1861 }
1862
1863 return SCIP_OKAY;
1864}
1865
1866/** replaces a reoptimization nodes by its stored child nodes */
1867static
1869 SCIP_REOPT* reopt, /**< reoptimization data structure */
1870 SCIP_SET* set, /**< global SCIP settings */
1871 SCIP_NODE* node, /**< node of the search tree */
1872 unsigned int id, /**< id of the node */
1873 SCIP_Bool* shrank, /**< pointer to store if the node was shrank */
1874 BMS_BLKMEM* blkmem /**< block memory */
1875 )
1876{
1877 SCIP_REOPTNODE** reoptnodes;
1878
1879 assert(reopt != NULL);
1880 assert(node != NULL);
1881 assert(id < reopt->reopttree->reoptnodessize);
1882
1883 reoptnodes = reopt->reopttree->reoptnodes;
1884 assert(reoptnodes != NULL);
1885 assert(reoptnodes[id] != NULL);
1886
1887 if( reoptnodes[id]->childids != NULL && reoptnodes[id]->nchilds > 0 )
1888 {
1889 int ndomchgs = 0;
1890 unsigned int parentid = 0;
1891 SCIP_NODE* parent = NULL;
1892
1893 SCIP_CALL( getLastSavedNode(reopt, set, node, &parent, &parentid, &ndomchgs) );
1894
1895 assert(parentid != id);
1896 assert(reoptnodes[parentid] != NULL );
1897 assert(reoptnodes[parentid]->childids != NULL && reoptnodes[parentid]->nchilds);
1898
1899 /* check if we want move all children to the next saved node above
1900 * we want to shrink the path if either
1901 * - the maximal number of bound changes fix and the number of bound changes is
1902 * less than the given threshold set->reopt_maxdiffofnodes
1903 * or
1904 * - the number is calculated dynamically and the number of bound changes
1905 * is less than log2(SCIPgetNBinVars - (#vars of parent))
1906 * */
1907 if( ndomchgs <= set->reopt_maxdiffofnodes )
1908 {
1909 int c;
1910
1911 SCIPsetDebugMsg(set, " -> shrink node %lld at ID %u, replaced by %d child nodes.\n", SCIPnodeGetNumber(node),
1912 id, reoptnodes[id]->nchilds);
1913
1914 /* copy the references of child nodes to the parent*/
1915 SCIP_CALL( moveChildrenUp(reopt, set, blkmem, id, parentid) );
1916
1917 /* delete the current node */
1918 c = 0;
1919 while( reoptnodes[parentid]->childids[c] != id )
1920 {
1921 ++c;
1922 assert(c < reoptnodes[parentid]->nchilds);
1923 }
1924
1925 assert(reoptnodes[parentid]->childids[c] == id);
1926
1927 /* replace the childid at position c by the last one */
1928 reoptnodes[parentid]->childids[c] = reoptnodes[parentid]->childids[reoptnodes[parentid]->nchilds-1];
1929 --reoptnodes[parentid]->nchilds;
1930
1931 SCIP_CALL( reopttreeDeleteNode(reopt->reopttree, set, blkmem, id, TRUE) );
1933
1934 *shrank = TRUE;
1935
1936 /* set the reopttype to none */
1938 }
1939 }
1940
1941 return SCIP_OKAY;
1942}
1943
1944/** change all reopttypes in the subtree induced by @p nodeID */
1945static
1947 SCIP_REOPTTREE* reopttree, /**< reopttree */
1948 unsigned int id, /**< id of the node */
1949 SCIP_REOPTTYPE reopttype /**< reopttype */
1950 )
1951{
1952 assert(reopttree != NULL);
1953 assert(id < reopttree->reoptnodessize);
1954 assert(reopttree->reoptnodes[id] != NULL);
1955
1956 if( reopttree->reoptnodes[id]->childids != NULL && reopttree->reoptnodes[id]->nchilds > 0 )
1957 {
1958 unsigned int childid;
1959 int nchildids;
1960 int seenids = 0;
1961
1962 nchildids = reopttree->reoptnodes[id]->nchilds;
1963
1964 while( seenids < nchildids )
1965 {
1966 /* get childID */
1967 childid = reopttree->reoptnodes[id]->childids[seenids];
1968 assert(childid < reopttree->reoptnodessize);
1969 assert(reopttree->reoptnodes[childid] != NULL);
1970
1971 /* change the reopttype of the node iff the node is neither infeasible nor induces an
1972 * infeasible subtree and if the node contains no bound changes based on dual decisions
1973 */
1974 if( reopttree->reoptnodes[childid]->reopttype != SCIP_REOPTTYPE_STRBRANCHED
1975 && reopttree->reoptnodes[childid]->reopttype != SCIP_REOPTTYPE_INFSUBTREE ) /*lint !e641*/
1976 reopttree->reoptnodes[childid]->reopttype = reopttype; /*lint !e641*/
1977
1978 /* change reopttype of subtree */
1979 SCIP_CALL( changeReopttypeOfSubtree(reopttree, childid, reopttype) );
1980
1981 ++seenids;
1982 }
1983 }
1984
1985 return SCIP_OKAY;
1986}
1987
1988/** delete the constraint handling dual information for the current iteration and replace it with the dual constraint
1989 * for the next iteration
1990 */
1991static
1993 SCIP_REOPTNODE* reoptnode, /**< reoptimization node */
1994 BMS_BLKMEM* blkmem /**< block memory */
1995 )
1996{
1997 assert(reoptnode != NULL);
1998 assert(blkmem != NULL);
1999
2000 if( reoptnode->dualredscur != NULL )
2001 {
2002 SCIPdebugMessage("reset dual information (current run)\n");
2003
2004 BMSfreeBlockMemoryArray(blkmem, &reoptnode->dualredscur->boundtypes, reoptnode->dualredscur->varssize);
2005 BMSfreeBlockMemoryArray(blkmem, &reoptnode->dualredscur->vals, reoptnode->dualredscur->varssize);
2006 BMSfreeBlockMemoryArray(blkmem, &reoptnode->dualredscur->vars, reoptnode->dualredscur->varssize);
2007 BMSfreeBlockMemory(blkmem, &reoptnode->dualredscur);
2008 reoptnode->dualredscur = NULL;
2009 }
2010
2011 if( reoptnode->dualredsnex != NULL )
2012 {
2013 SCIPdebugMessage("set dual information of next run to current run\n");
2014 reoptnode->dualredscur = reoptnode->dualredsnex;
2015 reoptnode->dualredsnex = NULL;
2016 }
2017
2018 reoptnode->dualreds = (reoptnode->dualredscur != NULL ? TRUE : FALSE);
2019
2020 return SCIP_OKAY;
2021}
2022
2023/** calculates a (local) similarity of a given node and returns if the subproblem should be solved from scratch */
2024static
2026 SCIP_REOPT* reopt, /**< reoptimization data structure */
2027 SCIP_SET* set, /**< global SCIP settings */
2028 BMS_BLKMEM* blkmem, /**< block memory */
2029 SCIP_NODE* node, /**< node of the search tree */
2030 SCIP_VAR** transvars, /**< transformed variables */
2031 int ntransvars, /**< number of transformed variables */
2032 SCIP_Bool* localrestart /**< pointer to store if we want to restart solving the (sub)problem */
2033 )
2034{
2035 unsigned int id;
2036
2037 assert(reopt != NULL);
2038 assert(reopt->reopttree != NULL);
2039 assert(set != NULL);
2040 assert(blkmem != NULL);
2041 assert(node != NULL);
2042 assert(transvars != NULL);
2043
2044 /* node == NULL is equivalent to node == root, this case should be handled by SCIPreoptCheckReopt */
2045 assert(node != NULL);
2046
2047 *localrestart = FALSE;
2048
2049 id = SCIPnodeGetReoptID(node);
2050 assert(id < reopt->reopttree->reoptnodessize);
2051
2052 /* set the id to -1 if the node is not part of the reoptimization tree */
2053 if( SCIPnodeGetDepth(node) > 0 && id == 0 )
2054 return SCIP_OKAY;
2055
2056 if( set->reopt_objsimdelay > -1 )
2057 {
2058 SCIP_Real sim = 0.0;
2059 SCIP_Real lb;
2060 SCIP_Real ub;
2061 SCIP_Real oldcoef;
2062 SCIP_Real newcoef;
2063 int idx;
2064
2065 if( id == 0 )
2066 reopt->nlocrestarts = 0;
2067
2068 /* since the stored objective functions are already normalize the dot-product is equivalent to the similarity */
2069 for( int v = 0; v < ntransvars; ++v )
2070 {
2071 lb = SCIPvarGetLbLocal(transvars[v]);
2072 ub = SCIPvarGetUbLocal(transvars[v]);
2073
2074 /* skip already fixed variables */
2075 if( SCIPsetIsFeasLT(set, lb, ub) )
2076 {
2077 idx = SCIPvarGetProbindex(transvars[v]);
2078 assert(0 <= idx && idx < ntransvars);
2079
2080 oldcoef = SCIPreoptGetOldObjCoef(reopt, reopt->run-1, idx);
2081 newcoef = SCIPreoptGetOldObjCoef(reopt, reopt->run, idx);
2082
2083 sim += (oldcoef * newcoef);
2084 }
2085 }
2086
2087 /* delete the stored subtree and information about bound changes
2088 * based on dual information */
2089 if( SCIPsetIsLT(set, sim, set->reopt_objsimdelay) )
2090 {
2091 /* set the flag */
2092 *localrestart = TRUE;
2093
2094 ++reopt->nlocrestarts;
2095 ++reopt->ntotallocrestarts;
2096
2097 /* delete the stored subtree */
2098 SCIP_CALL( deleteChildrenBelow(reopt->reopttree, set, blkmem, id, FALSE, FALSE) );
2099
2100 /* delete the stored constraints; we do this twice in a row because we want to delete both constraints */
2103 }
2104
2105 SCIPsetDebugMsg(set, " -> local similarity: %.4f%s\n", sim, *localrestart ? " (solve subproblem from scratch)" : "");
2106 }
2107
2108 return SCIP_OKAY;
2109}
2110
2111/** save ancestor branching information up to the next stored node */
2112static
2114 SCIP_REOPTTREE* reopttree, /**< reoptimization tree */
2115 SCIP_SET* set, /**< global SCIP settings */
2116 BMS_BLKMEM* blkmem, /**< block memory */
2117 SCIP_NODE* node, /**< node of the branch and bound tree */
2118 SCIP_NODE* parent, /**< parent node */
2119 unsigned int id, /**< id of the node */
2120 unsigned int parentid /**< id of the parent node */
2121 )
2122{
2123 int nbranchvars;
2124
2125 assert(reopttree != NULL );
2126 assert(node != NULL );
2127 assert(parent != NULL );
2128 assert(1 <= id && id < reopttree->reoptnodessize);
2129 assert(reopttree->reoptnodes[id] != NULL );
2130 assert(parentid < reopttree->reoptnodessize);
2131 assert(parentid == 0 || reopttree->reoptnodes[parentid] != NULL ); /* if the root is the next saved node, the nodedata can be NULL */
2132
2133 SCIPsetDebugMsg(set, " -> save ancestor branchings\n");
2134
2135 /* allocate memory */
2136 if (reopttree->reoptnodes[id]->varssize == 0)
2137 {
2138 assert(reopttree->reoptnodes[id]->vars == NULL );
2139 assert(reopttree->reoptnodes[id]->varbounds == NULL );
2140 assert(reopttree->reoptnodes[id]->varboundtypes == NULL );
2141
2142 /* allocate memory for node information */
2143 SCIP_CALL( reoptnodeCheckMemory(reopttree->reoptnodes[id], set, blkmem, DEFAULT_MEM_VAR, 0, 0) );
2144 }
2145
2146 assert(reopttree->reoptnodes[id]->varssize > 0);
2147 assert(reopttree->reoptnodes[id]->nvars == 0);
2148
2150 reopttree->reoptnodes[id]->vars,
2151 reopttree->reoptnodes[id]->varbounds,
2152 reopttree->reoptnodes[id]->varboundtypes,
2153 &nbranchvars,
2154 reopttree->reoptnodes[id]->varssize);
2155
2156 if( nbranchvars > reopttree->reoptnodes[id]->varssize )
2157 {
2158 /* reallocate memory */
2159 SCIP_CALL( reoptnodeCheckMemory(reopttree->reoptnodes[id], set, blkmem, nbranchvars, 0, 0) );
2160
2162 reopttree->reoptnodes[id]->vars,
2163 reopttree->reoptnodes[id]->varbounds,
2164 reopttree->reoptnodes[id]->varboundtypes,
2165 &nbranchvars,
2166 reopttree->reoptnodes[id]->varssize);
2167 }
2168
2169 assert(nbranchvars <= reopttree->reoptnodes[id]->varssize); /* this should be the case */
2170
2171 reopttree->reoptnodes[id]->nvars = nbranchvars;
2172
2173 assert(nbranchvars <= reopttree->reoptnodes[id]->varssize);
2174 assert(reopttree->reoptnodes[id]->vars != NULL );
2175
2176 return SCIP_OKAY;
2177}
2178
2179
2180/** transform a constraint with linear representation into reoptimization constraint data */
2181static
2183 SCIP_REOPTCONSDATA* reoptconsdata, /**< reoptimization constraint data */
2184 SCIP_SET* set, /**< global SCIP settings */
2185 BMS_BLKMEM* blkmem, /**< block memory */
2186 SCIP_CONS* cons, /**< linear constraint that should be stored */
2187 SCIP_Bool* success /**< pointer to store the success */
2188 )
2189{
2190 SCIP_VAR** vars;
2191 SCIP_Real* vals;
2192 SCIP_CONSHDLR* conshdlr;
2193 SCIP_Bool allocbuffervals;
2194
2195 assert(reoptconsdata != NULL);
2196 assert(cons != NULL);
2197
2198 *success = FALSE;
2199 allocbuffervals = FALSE;
2200 reoptconsdata->linear = TRUE;
2201
2202 vars = NULL;
2203 vals = NULL;
2204 SCIP_CALL( SCIPconsGetNVars(cons, set, &reoptconsdata->nvars, success) );
2205 assert(*success);
2206
2207 /* allocate memory for variables and values; boundtypes are not needed */
2208 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &reoptconsdata->vars, reoptconsdata->nvars) );
2209 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &reoptconsdata->vals, reoptconsdata->nvars) );
2210 reoptconsdata->varssize = reoptconsdata->nvars;
2211
2212 /* only needed for bounddisjuction constraints, thus we set them to NULL to avoid compiler warnings */
2213 reoptconsdata->boundtypes = NULL;
2214
2215 conshdlr = SCIPconsGetHdlr(cons);
2216 assert(conshdlr != NULL);
2217
2218 /* get all variables, values, and sides */
2219 if( strcmp(SCIPconshdlrGetName(conshdlr), "linear") == 0 )
2220 {
2221 vars = SCIPgetVarsLinear(set->scip, cons);
2222 vals = SCIPgetValsLinear(set->scip, cons);
2223 reoptconsdata->lhs = SCIPgetLhsLinear(set->scip, cons);
2224 reoptconsdata->rhs = SCIPgetRhsLinear(set->scip, cons);
2225 }
2226 else if( strcmp(SCIPconshdlrGetName(conshdlr), "logicor") == 0 )
2227 {
2228 vars = SCIPgetVarsLogicor(set->scip, cons);
2229
2230 /* initialize values to 1.0 */
2231 SCIP_CALL( SCIPsetAllocBufferArray(set, &vals, reoptconsdata->nvars) );
2232 allocbuffervals = TRUE;
2233
2234 for( int v = 0; v < reoptconsdata->nvars; ++v )
2235 vals[v] = 1.0;
2236
2237 reoptconsdata->lhs = 1.0;
2238 reoptconsdata->rhs = SCIPsetInfinity(set);
2239 }
2240 else if( strcmp(SCIPconshdlrGetName(conshdlr), "setppc") == 0 )
2241 {
2242 vars = SCIPgetVarsSetppc(set->scip, cons);
2243
2244 /* initialize values to 1.0 */
2245 SCIP_CALL( SCIPsetAllocBufferArray(set, &vals, reoptconsdata->nvars) );
2246 allocbuffervals = TRUE;
2247
2248 for( int v = 0; v < reoptconsdata->nvars; ++v )
2249 vals[v] = 1.0;
2250
2251 switch( SCIPgetTypeSetppc(set->scip, cons) ) {
2253 reoptconsdata->lhs = 1.0;
2254 reoptconsdata->rhs = 1.0;
2255 break;
2257 reoptconsdata->lhs = -SCIPsetInfinity(set);
2258 reoptconsdata->rhs = 1.0;
2259 break;
2261 reoptconsdata->lhs = 1.0;
2262 reoptconsdata->rhs = SCIPsetInfinity(set);
2263 break;
2264 default:
2265 *success = FALSE;
2266 return SCIP_OKAY;
2267 }
2268 }
2269 else
2270 {
2271 assert(strcmp(SCIPconshdlrGetName(conshdlr), "linear") == 0 || strcmp(SCIPconshdlrGetName(conshdlr), "logicor") == 0
2272 || strcmp(SCIPconshdlrGetName(conshdlr), "setppc") == 0);
2273
2274 SCIPerrorMessage("Cannot handle constraints of type <%s> in saveConsLinear.\n", SCIPconshdlrGetName(conshdlr));
2275 return SCIP_INVALIDDATA;
2276 }
2277 assert(vars != NULL);
2278 assert(vals != NULL);
2279
2280 /* transform all variables into the original space */
2281 for( int v = 0; v < reoptconsdata->nvars; ++v )
2282 {
2283 SCIP_Real constant = 0.0;
2284 SCIP_Real scalar = 1.0;
2285
2286 assert(vars[v] != NULL);
2287
2288 reoptconsdata->vars[v] = vars[v];
2289 reoptconsdata->vals[v] = vals[v];
2290
2291 SCIP_CALL( SCIPvarGetOrigvarSum(&reoptconsdata->vars[v], &scalar, &constant) );
2292 assert(!SCIPsetIsZero(set, scalar));
2293
2294 assert(!SCIPsetIsInfinity(set, REALABS(reoptconsdata->vals[v])));
2295 reoptconsdata->vals[v] *= scalar;
2296
2297 if( !SCIPsetIsZero(set, constant) && !SCIPsetIsInfinity(set, -reoptconsdata->lhs) )
2298 reoptconsdata->lhs -= constant;
2299 if( !SCIPsetIsZero(set, constant) && !SCIPsetIsInfinity(set, reoptconsdata->rhs) )
2300 reoptconsdata->rhs -= constant;
2301 }
2302
2303 /* free buffer if needed */
2304 if( allocbuffervals )
2305 {
2307 }
2308
2309 return SCIP_OKAY;
2310}
2311
2312/** transform a bounddisjunction constraint into reoptimization constraint data */
2313static
2315 SCIP_REOPTCONSDATA* reoptconsdata, /**< reoptimization constraint data */
2316 SCIP_SET* set, /**< global SCIP settings */
2317 BMS_BLKMEM* blkmem, /**< block memory */
2318 SCIP_CONS* cons, /**< bounddisjuction constraint that should be stored */
2319 SCIP_Bool* success /**< pointer to store the success */
2320 )
2321{
2322 SCIP_VAR** vars;
2323 SCIP_CONSHDLR* conshdlr;
2324 SCIP_BOUNDTYPE* boundtypes;
2325 SCIP_Real* bounds;
2326
2327 assert(reoptconsdata != NULL);
2328 assert(cons != NULL);
2329
2330 *success = FALSE;
2331 reoptconsdata->linear = FALSE;
2332
2333 conshdlr = SCIPconsGetHdlr(cons);
2334 assert(conshdlr != NULL);
2335 assert(strcmp(SCIPconshdlrGetName(conshdlr), "bounddisjunction") == 0);
2336
2337 if( strcmp(SCIPconshdlrGetName(conshdlr), "bounddisjunction") != 0 )
2338 {
2339 SCIPerrorMessage("Cannot handle constraints of type <%s> in saveConsBounddisjuction.\n",
2340 SCIPconshdlrGetName(conshdlr));
2341 return SCIP_INVALIDDATA;
2342 }
2343
2344 SCIP_CALL( SCIPconsGetNVars(cons, set, &reoptconsdata->nvars, success) );
2345 assert(*success);
2346
2347 /* allocate memory for variables and values; boundtypes are not needed */
2348 vars = SCIPgetVarsBounddisjunction(NULL, cons);
2349 bounds = SCIPgetBoundsBounddisjunction(NULL, cons);
2350 boundtypes = SCIPgetBoundtypesBounddisjunction(NULL, cons);
2351 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &reoptconsdata->vars, vars, reoptconsdata->nvars) );
2352 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &reoptconsdata->vals, bounds, reoptconsdata->nvars) );
2353 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &reoptconsdata->boundtypes, boundtypes, reoptconsdata->nvars) );
2354 reoptconsdata->varssize = reoptconsdata->nvars;
2355 reoptconsdata->lhs = SCIP_UNKNOWN;
2356 reoptconsdata->rhs = SCIP_UNKNOWN;
2357
2358 /* transform all variables into the original space */
2359 for( int v = 0; v < reoptconsdata->nvars; ++v )
2360 {
2361 SCIP_Real constant = 0.0;
2362 SCIP_Real scalar = 1.0;
2363
2364 assert(reoptconsdata->vars[v] != NULL);
2365
2366 SCIP_CALL( SCIPvarGetOrigvarSum(&reoptconsdata->vars[v], &scalar, &constant) );
2367 assert(!SCIPsetIsZero(set, scalar));
2368
2369 assert(!SCIPsetIsInfinity(set, REALABS(reoptconsdata->vals[v])));
2370 reoptconsdata->vals[v] -= constant;
2371 reoptconsdata->vals[v] *= scalar;
2372
2373 /* due to multipling with a negative scalar the relation need to be changed */
2374 if( SCIPsetIsNegative(set, scalar) )
2375 reoptconsdata->boundtypes[v] = (SCIP_BOUNDTYPE)(SCIP_BOUNDTYPE_UPPER - reoptconsdata->boundtypes[v]); /*lint !e656*/
2376 }
2377
2378 return SCIP_OKAY;
2379}
2380
2381/** save additional all constraints that were additionally added to @p node */
2382static
2384 SCIP_REOPTTREE* reopttree, /**< reopttree */
2385 SCIP_SET* set, /**< global SCIP settings */
2386 BMS_BLKMEM* blkmem, /**< block memory */
2387 SCIP_NODE* node, /**< node of the branch and bound tree */
2388 unsigned int id /**< id of the node*/
2389 )
2390{
2391 SCIP_CONS** addedcons;
2392 int naddedconss;
2393 int addedconsssize;
2394 int nconss;
2395
2396 assert(node != NULL );
2397 assert(reopttree != NULL);
2398 assert(id < reopttree->reoptnodessize);
2399
2400 /* save the added pseudo-constraint */
2401 if( SCIPnodeGetNAddedConss(node) > 0 )
2402 {
2403 addedconsssize = SCIPnodeGetNAddedConss(node);
2404
2405 SCIPsetDebugMsg(set, " -> save %d locally added constraints\n", addedconsssize);
2406
2407 /* get memory */
2408 SCIP_CALL( SCIPsetAllocBufferArray(set, &addedcons, addedconsssize) );
2409 SCIPnodeGetAddedConss(node, addedcons, &naddedconss, addedconsssize);
2410
2411 nconss = reopttree->reoptnodes[id]->nconss;
2412
2413 /* check memory for added constraints */
2414 SCIP_CALL( reoptnodeCheckMemory(reopttree->reoptnodes[id], set, blkmem, 0, 0, naddedconss) );
2415
2416 /* since the first nconss are already stored in the data structure, we skip them */
2417 for( int c = nconss; c < naddedconss; ++c )
2418 {
2419 SCIP_CONSHDLR* conshdlr;
2420 SCIP_Bool islinear;
2421 SCIP_Bool success;
2422
2423 conshdlr = SCIPconsGetHdlr(addedcons[c]);
2424
2425 /* check whether the constraint has a linear representation */
2426 islinear = (strcmp(SCIPconshdlrGetName(conshdlr), "linear") == 0
2427 || strcmp(SCIPconshdlrGetName(conshdlr), "logicor") == 0
2428 || strcmp(SCIPconshdlrGetName(conshdlr), "setppc") == 0);
2429
2430 SCIP_ALLOC( BMSallocBlockMemory(blkmem, &reopttree->reoptnodes[id]->conss[c]) ); /*lint !e866*/
2431
2432 success = FALSE;
2433
2434 /* the constraint has a linear representation */
2435 if( islinear )
2436 {
2437 SCIP_CALL( saveConsLinear(reopttree->reoptnodes[id]->conss[c], set, blkmem, addedcons[c], &success) );
2438 assert(success);
2439
2440 /* increase the counter for added constraints */
2441 ++reopttree->reoptnodes[id]->nconss;
2442 }
2443 else
2444 {
2445 assert(strcmp(SCIPconshdlrGetName(conshdlr), "bounddisjunction") == 0);
2446 SCIP_CALL( saveConsBounddisjuction(reopttree->reoptnodes[id]->conss[c], set, blkmem, addedcons[c], &success) );
2447 assert(success);
2448
2449 /* increase the counter for added constraints */
2450 ++reopttree->reoptnodes[id]->nconss;
2451 }
2452 assert(reopttree->reoptnodes[id]->conss[c]->nvars > 0);
2453
2454 if( strcmp("reopt_inf", SCIPconsGetName(addedcons[c])) == 0 )
2455 reopttree->reoptnodes[id]->conss[c]->constype = REOPT_CONSTYPE_INFSUBTREE;
2456 else if( strcmp("reopt_dual", SCIPconsGetName(addedcons[c])) == 0 )
2457 reopttree->reoptnodes[id]->conss[c]->constype = REOPT_CONSTYPE_DUALREDS;
2458 else
2459 reopttree->reoptnodes[id]->conss[c]->constype = REOPT_CONSTYPE_UNKNOWN;
2460 }
2461
2462 assert(reopttree->reoptnodes[id]->nconss == naddedconss);
2463 SCIPsetFreeBufferArray(set, &addedcons);
2464 }
2465
2466 return SCIP_OKAY;
2467}
2468
2469/** collect all bound changes based on dual information
2470 *
2471 * If the bound changes are global, all information are already stored because they were caught by the event handler.
2472 * otherwise, we have to use SCIPnodeGetDualBoundchgs.
2473 *
2474 * Afterwards, we check if the constraint will be added in the next iteration or after splitting the node.
2475 */
2476static
2478 SCIP_REOPT* reopt, /**< reoptimization data structure */
2479 SCIP_SET* set, /**< global SCIP settings */
2480 BMS_BLKMEM* blkmem, /**< block memory */
2481 SCIP_NODE* node, /**< node of the search tree */
2482 unsigned int id, /**< id of the node */
2483 SCIP_REOPTTYPE reopttype /**< reopttype */
2484 )
2485{
2486 SCIP_Bool cons_is_next = TRUE;
2487 int nbndchgs;
2488
2489 assert(reopt != NULL);
2490 assert(reopt->reopttree != NULL);
2491 assert(id < reopt->reopttree->reoptnodessize);
2492 assert(reopt->reopttree->reoptnodes[id]->dualreds);
2493 assert(node != NULL);
2494 assert(blkmem != NULL);
2495
2496 /* first case, all bound changes were global */
2497 if( reopt->currentnode == SCIPnodeGetNumber(node) && reopt->dualreds != NULL && reopt->dualreds->nvars > 0 )
2498 {
2499 nbndchgs = reopt->dualreds->nvars;
2500 }
2501 else
2502 {
2503 assert(reopt->currentnode == SCIPnodeGetNumber(node));
2504
2505 /* get the number of bound changes based on dual information */
2506 nbndchgs = SCIPnodeGetNDualBndchgs(node);
2507
2508 /* ensure that enough memory is allocated */
2509 SCIP_CALL( checkMemDualCons(reopt, set, blkmem, nbndchgs) );
2510
2511 /* collect the bound changes */
2512 SCIPnodeGetDualBoundchgs(node, reopt->dualreds->vars, reopt->dualreds->vals, reopt->dualreds->boundtypes,
2513 &nbndchgs, reopt->dualreds->varssize);
2514 assert(nbndchgs <= reopt->dualreds->varssize);
2515
2516 reopt->dualreds->nvars = nbndchgs;
2517 reopt->dualreds->linear = FALSE;
2518
2519 /* transform the variables into the original space */
2520 for( int v = 0; v < nbndchgs; ++v )
2521 {
2522 SCIP_Real constant = 0.0;
2523 SCIP_Real scalar = 1.0;
2524
2525 SCIP_CALL( SCIPvarGetOrigvarSum(&reopt->dualreds->vars[v], &scalar, &constant) );
2526 reopt->dualreds->vals[v] = (reopt->dualreds->vals[v] - constant) / scalar;
2527
2528 assert(SCIPvarIsOriginal(reopt->dualreds->vars[v]));
2529 }
2530 }
2531
2532 assert(nbndchgs > 0);
2533
2534 /* due to the strong branching initialization it can be possible that two
2535 * constraints handling dual information are stored at the same time.
2536 * During reoptimizing a node we add the constraint stored at dualredscur only,
2537 * i.e, if dualredscur is not NULL, we need to store the constraint for the next
2538 * iteration at dualredsnex because the constraint stored at dualredscur is needed
2539 * to split the constraint in the current iteration.
2540 */
2541 if( reopt->reopttree->reoptnodes[id]->dualredscur != NULL )
2542 {
2543 assert(reopt->reopttree->reoptnodes[id]->dualredsnex == NULL);
2544 cons_is_next = FALSE;
2545 }
2546 assert((cons_is_next && reopt->reopttree->reoptnodes[id]->dualredscur == NULL)
2547 || (!cons_is_next && reopt->reopttree->reoptnodes[id]->dualredsnex == NULL));
2548
2549 /* the constraint will be added next */
2550 if( cons_is_next )
2551 {
2552 assert(reopt->reopttree->reoptnodes[id]->dualredscur == NULL);
2555 reopt->dualreds->vars, nbndchgs) );
2557 reopt->dualreds->vals, nbndchgs) );
2558 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &reopt->reopttree->reoptnodes[id]->dualredscur->boundtypes, \
2559 reopt->dualreds->boundtypes, nbndchgs) );
2560
2561 reopt->reopttree->reoptnodes[id]->dualredscur->nvars = nbndchgs;
2562 reopt->reopttree->reoptnodes[id]->dualredscur->varssize = nbndchgs;
2563 reopt->reopttree->reoptnodes[id]->dualredscur->lhs = 1.0;
2564 reopt->reopttree->reoptnodes[id]->dualredscur->rhs = SCIPsetInfinity(set);
2565 reopt->reopttree->reoptnodes[id]->dualredscur->constype = (reopttype == SCIP_REOPTTYPE_STRBRANCHED ?
2567 reopt->reopttree->reoptnodes[id]->dualredscur->linear = FALSE;
2568
2569 SCIPsetDebugMsg(set, " -> save dual information of type 1: node %lld, nvars %d, constype %d\n",
2570 SCIPnodeGetNumber(node), reopt->reopttree->reoptnodes[id]->dualredscur->nvars,
2571 reopt->reopttree->reoptnodes[id]->dualredscur->constype);
2572 }
2573 /* the constraint will be added after next */
2574 else
2575 {
2576 assert(reopt->reopttree->reoptnodes[id]->dualredsnex == NULL);
2578 reopt->reopttree->reoptnodes[id]->dualredsnex->nvars = -1;
2579
2581 reopt->dualreds->vars, nbndchgs) );
2583 reopt->dualreds->vals, nbndchgs) );
2584 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &reopt->reopttree->reoptnodes[id]->dualredsnex->boundtypes, \
2585 reopt->dualreds->boundtypes, nbndchgs) );
2586 reopt->reopttree->reoptnodes[id]->dualredsnex->nvars = nbndchgs;
2587 reopt->reopttree->reoptnodes[id]->dualredsnex->varssize = nbndchgs;
2588 reopt->reopttree->reoptnodes[id]->dualredsnex->lhs = 1.0;
2589 reopt->reopttree->reoptnodes[id]->dualredsnex->rhs = SCIPsetInfinity(set);
2590 reopt->reopttree->reoptnodes[id]->dualredsnex->constype = (reopttype == SCIP_REOPTTYPE_STRBRANCHED ?
2592
2593 SCIPsetDebugMsg(set, " -> save dual information of type 2: node %lld, nvars %d, constype %d\n",
2594 SCIPnodeGetNumber(node), reopt->reopttree->reoptnodes[id]->dualredsnex->nvars,
2595 reopt->reopttree->reoptnodes[id]->dualredsnex->constype);
2596 }
2597
2598 return SCIP_OKAY;
2599}
2600
2601/** adds a node of the branch and bound tree to the reoptimization tree */
2602static
2604 SCIP_REOPT* reopt, /**< reoptimization data structure */
2605 SCIP_SET* set, /**< global SCIP settings */
2606 SCIP_LP* lp, /**< current LP */
2607 BMS_BLKMEM* blkmem, /**< block memory */
2608 SCIP_NODE* node, /**< current node */
2609 SCIP_REOPTTYPE reopttype, /**< reason for storing the node*/
2610 SCIP_Bool saveafterdual, /**< save branching decisions after the first dual */
2611 SCIP_Bool isrootnode, /**< node is the root node */
2612 SCIP_Real lowerbound /**< lower bound of the node */
2613 )
2614{
2615 SCIP_NODE* parent = NULL;
2616 SCIP_Bool shrank = FALSE;
2617 unsigned int id;
2618 unsigned int parentid = 0;
2619
2620 assert(reopt != NULL);
2621 assert(set != NULL);
2622 assert(blkmem != NULL);
2623 assert(node != NULL);
2624
2625 if( set->reopt_maxsavednodes == 0 )
2626 return SCIP_OKAY;
2627
2628 assert(reopttype == SCIP_REOPTTYPE_TRANSIT
2629 || reopttype == SCIP_REOPTTYPE_INFSUBTREE
2630 || reopttype == SCIP_REOPTTYPE_STRBRANCHED
2631 || reopttype == SCIP_REOPTTYPE_LOGICORNODE
2632 || reopttype == SCIP_REOPTTYPE_LEAF
2633 || reopttype == SCIP_REOPTTYPE_PRUNED
2634 || reopttype == SCIP_REOPTTYPE_FEASIBLE);
2635
2636 /* start clock */
2637 SCIPclockStart(reopt->savingtime, set);
2638
2639 /* the node was created by reoptimization, i.e., we need to update the
2640 * stored data */
2641 if( SCIPnodeGetReoptID(node) >= 1 )
2642 {
2643 SCIP_Bool transintoorig;
2644
2645 assert(reopttype != SCIP_REOPTTYPE_LEAF);
2646 assert(!isrootnode);
2647
2648 id = SCIPnodeGetReoptID(node);
2649 assert(id < reopt->reopttree->reoptnodessize);
2650
2651 /* this is a special case:
2652 * due to re-propagation of the an anchester node it can happen that we try to update a node that was created by
2653 * reoptimization and already removed by deleteChildrenBelow. In this case we do not want to save the current
2654 * node
2655 */
2656 if( reopt->reopttree->reoptnodes[id] == NULL )
2657 {
2658 parent = SCIPnodeGetParent(node);
2659 assert(parent != NULL);
2660
2661 parentid = SCIPnodeGetReoptID(parent);
2662
2663 /* traverse along the branching path until reaching a node that is part of the reoptimization tree or the root node */
2664 while( SCIPnodeGetDepth(parent) > 0 && reopt->reopttree->reoptnodes[parentid] == NULL )
2665 {
2666 /* the parent node is not part of the reoptimization, reset the reoptid and reopttype of the parent node */
2667 SCIPnodeSetReoptID(parent, 0);
2669
2670 parent = SCIPnodeGetParent(parent);
2671 assert(parent != NULL);
2672
2673 parentid = SCIPnodeGetReoptID(parent);
2674 }
2675
2676 /* the anchestor node has to be part of the reoptimization tree. either the parent is the root itself or
2677 * marked to be a leaf, pruned or feasible
2678 */
2679 assert(reopt->reopttree->reoptnodes[parentid] != NULL);
2680 assert(parentid == 0
2681 || reopt->reopttree->reoptnodes[parentid]->reopttype == SCIP_REOPTTYPE_FEASIBLE
2683 || reopt->reopttree->reoptnodes[parentid]->reopttype == SCIP_REOPTTYPE_LEAF
2684 || reopt->reopttree->reoptnodes[parentid]->reopttype == SCIP_REOPTTYPE_PRUNED); /*lint !e641*/
2685
2686 SCIPsetDebugMsg(set, " -> skip saving\n");
2687 SCIPnodeSetReoptID(node, 0);
2689
2690 /* stop clock */
2691 SCIPclockStop(reopt->savingtime, set);
2692
2693 return SCIP_OKAY;
2694 }
2695
2696 SCIPsetDebugMsg(set, "update node %lld at ID %u:\n", SCIPnodeGetNumber(node), id);
2697
2698 transintoorig = FALSE;
2699
2700 /* store separated cuts */
2701 if( set->reopt_usecuts )
2702 {
2703 SCIP_CALL( storeCuts(reopt, set, blkmem, lp, id) );
2704 }
2705
2706 /* save primal bound changes made after the first dual bound change */
2707 if( saveafterdual )
2708 {
2709 assert(reopttype == SCIP_REOPTTYPE_STRBRANCHED);
2710 SCIP_CALL( saveAfterDualBranchings(reopt, set, blkmem, node, id, &transintoorig) );
2711 }
2712
2713 /* update propagations */
2714 if( set->reopt_saveprop )
2715 {
2716 SCIP_CALL( updatePropagation(reopt, set, blkmem, node, id, &transintoorig) );
2717 }
2718
2719 /* ensure that all variables describing the branching path are original */
2720 if( transintoorig )
2721 {
2722 SCIP_CALL( transformIntoOrig(reopt, id) );
2723 }
2724
2725 /* update the lowerbound if the new lower bound is finite */
2726 if( !SCIPsetIsInfinity(set, REALABS(lowerbound)) )
2727 reopt->reopttree->reoptnodes[id]->lowerbound = lowerbound;
2728 SCIPsetDebugMsg(set, " -> reopttype: %d, lowerbound: %g\n", reopttype, reopt->reopttree->reoptnodes[id]->lowerbound);
2729
2730#ifdef SCIP_MORE_DEBUG
2731 {
2732 SCIPsetDebugMsg(set, " -> saved variables:\n");
2733 for( int varnr = 0; varnr < reopt->reopttree->reoptnodes[id]->nvars; ++varnr )
2734 {
2735 SCIPsetDebugMsg(set, " <%s> %s %g\n", SCIPvarGetName(reopt->reopttree->reoptnodes[id]->vars[varnr]),
2737 "=>" : "<=", reopt->reopttree->reoptnodes[id]->varbounds[varnr]);
2738 }
2739 for( int varnr = 0; varnr < reopt->reopttree->reoptnodes[id]->nafterdualvars; ++varnr )
2740 {
2741 SCIPsetDebugMsg(set, " -> saved variables:\n");
2742 for( int varnr = 0; varnr < reopt->reopttree->reoptnodes[id]->nvars; ++varnr )
2743 {
2744 SCIPsetDebugMsg(set, " <%s> %s %g\n", SCIPvarGetName(reopt->reopttree->reoptnodes[id]->vars[varnr]),
2746 "=>" : "<=", reopt->reopttree->reoptnodes[id]->varbounds[varnr]);
2747 }
2748 for( int varnr = 0; varnr < reopt->reopttree->reoptnodes[id]->nafterdualvars; ++varnr )
2749 {
2750 SCIPsetDebugMsg(set, " <%s> %s %g (after dual red.)\n", SCIPvarGetName(reopt->reopttree->reoptnodes[id]->afterdualvars[varnr]),
2752 "=>" : "<=", reopt->reopttree->reoptnodes[id]->afterdualvarbounds[varnr]);
2753 }
2754 }
2755 }
2756#endif
2757
2758 /* update LPI state */
2759 switch( reopttype )
2760 {
2762 if( set->reopt_shrinkinner )
2763 {
2764 SCIP_CALL( shrinkNode(reopt, set, node, id, &shrank, blkmem) );
2765 }
2766 goto TRANSIT;
2767
2770 goto TRANSIT;
2771
2773 /* delete the whole subtree induced be the current node */
2774 SCIP_CALL( deleteChildrenBelow(reopt->reopttree, set, blkmem, id, FALSE, FALSE) );
2775 goto PSEUDO;
2776
2778 goto PSEUDO;
2779
2781 /* delete the subtree */
2782 if( set->reopt_reducetofrontier )
2783 {
2784 SCIP_CALL( deleteChildrenBelow(reopt->reopttree, set, blkmem, id, FALSE, FALSE) );
2785 SCIP_CALL( SCIPreoptResetDualBndchgs(reopt, node, blkmem) );
2786 }
2787 /* dive through all children and change the reopttype to PRUNED */
2788 else
2789 {
2791 }
2792 goto FEASIBLE;
2793
2795 /* delete the subtree */
2796 if( set->reopt_reducetofrontier )
2797 {
2798 SCIP_CALL( deleteChildrenBelow(reopt->reopttree, set, blkmem, id, FALSE, FALSE) );
2799 SCIP_CALL( SCIPreoptResetDualBndchgs(reopt, node, blkmem) );
2800 }
2801 /* dive through all children and change the reopttype to LEAF */
2802 else
2803 {
2805 }
2806
2807 /* increase number of reoptimized nodes that could be pruned */
2808 ++reopt->reopttree->ncutoffreoptnodes;
2810
2811 goto PRUNED;
2812
2813 default:
2814 break;
2815 } /*lint !e788*/
2816
2817 /* stop clock */
2818 SCIPclockStart(reopt->savingtime, set);
2819
2820 return SCIP_OKAY;
2821 }
2822
2823 /* get new IDs */
2824 SCIP_CALL( reopttreeCheckMemory(reopt->reopttree, set, blkmem) );
2825
2826 /* the current node is the root node */
2827 if( isrootnode )
2828 {
2829 id = 0;
2830
2831 /* save local constraints
2832 * note: currently, there will be no constraint to save because all global constraints are added by calling
2833 * SCIPprobAddCons.
2834 */
2835 if (SCIPnodeGetNAddedConss(node) >= 1)
2836 {
2837 assert(reopt->reopttree->reoptnodes[id]->nconss == 0);
2838
2839 SCIP_CALL( saveLocalConssData(reopt->reopttree, set, blkmem, node, id) );
2840 }
2841
2842 /* store separated cuts
2843 * note: we need to call this after saveLocalConssData to be sure that the local conss array is ordered, first all
2844 * local constraints, then cuts
2845 */
2846 if( set->reopt_usecuts )
2847 {
2848 SCIP_CALL( storeCuts(reopt, set, blkmem, lp, id) );
2849 }
2850
2851 switch( reopttype )
2852 {
2854 /* ensure that no dual constraints are stored */
2855 SCIP_CALL( SCIPreoptResetDualBndchgs(reopt, node, blkmem) );
2856
2857 /* update the lowerbound */
2858 if( !SCIPsetIsInfinity(set, REALABS(lowerbound)) )
2859 reopt->reopttree->reoptnodes[id]->lowerbound = lowerbound;
2860
2861 goto TRANSIT;
2862
2865 reopt->reopttree->reoptnodes[0]->reopttype = (unsigned int)reopttype;
2866 reopt->reopttree->reoptnodes[0]->dualreds = TRUE;
2867 reopt->reopttree->reoptnodes[0]->nvars = 0;
2868
2869 if( reopttype == SCIP_REOPTTYPE_INFSUBTREE )
2870 {
2871 /* delete the whole subtree induced be the current node */
2872 SCIP_CALL( deleteChildrenBelow(reopt->reopttree, set, blkmem, 0, FALSE, FALSE) );
2873 }
2874
2875 /* update the lowerbound */
2876 if( !SCIPsetIsInfinity(set, REALABS(lowerbound)) )
2877 reopt->reopttree->reoptnodes[id]->lowerbound = lowerbound;
2878
2879 SCIPsetDebugMsg(set, "update node %d at ID %d:\n", 1, 0);
2880 SCIPsetDebugMsg(set, " -> nvars: 0, ncons: 0, parentID: -, reopttype: %d, lowerbound: %g\n", reopttype,
2881 reopt->reopttree->reoptnodes[id]->lowerbound);
2882
2883 goto PSEUDO;
2884
2886 ++reopt->reopttree->ntotalfeasnodes;
2887 ++reopt->reopttree->nfeasnodes;
2888 reopt->reopttree->reoptnodes[0]->reopttype = (unsigned int)SCIP_REOPTTYPE_FEASIBLE;
2889 reopt->reopttree->reoptnodes[0]->dualreds = FALSE;
2890
2891 if( reopt->reopttree->reoptnodes[0]->childids != NULL && reopt->reopttree->reoptnodes[0]->nchilds > 0 )
2892 {
2893 /* delete the subtree */
2894 if( set->reopt_reducetofrontier )
2895 {
2896 SCIP_CALL( deleteChildrenBelow(reopt->reopttree, set, blkmem, 0, FALSE, FALSE) );
2897 SCIP_CALL( SCIPreoptResetDualBndchgs(reopt, node, blkmem) );
2898 }
2899 /* dive through all children and change the reopttype to LEAF */
2900 else
2901 {
2903 }
2904 }
2905 else
2906 SCIP_CALL( SCIPreoptResetDualBndchgs(reopt, node, blkmem) );
2907
2908 /* update the lowerbound */
2909 if( !SCIPsetIsInfinity(set, REALABS(lowerbound)) )
2910 reopt->reopttree->reoptnodes[id]->lowerbound = lowerbound;
2911
2912 SCIPsetDebugMsg(set, "update node %d at ID %d:\n", 1, 0);
2913 SCIPsetDebugMsg(set, " -> nvars: 0, ncons: 0, parentID: -, reopttype: %d, lowerbound: %g\n", reopttype,
2914 reopt->reopttree->reoptnodes[id]->lowerbound);
2915
2916 break;
2917
2919 ++reopt->reopttree->nprunednodes;
2920 ++reopt->reopttree->ntotalprunednodes;
2921 reopt->reopttree->reoptnodes[0]->reopttype = (unsigned int)SCIP_REOPTTYPE_PRUNED;
2922 reopt->reopttree->reoptnodes[0]->dualreds = FALSE;
2923
2924 if( reopt->reopttree->reoptnodes[0]->childids != NULL && reopt->reopttree->reoptnodes[0]->nchilds > 0 )
2925 {
2926 /* delete the subtree */
2927 if( set->reopt_reducetofrontier )
2928 {
2929 SCIP_CALL( deleteChildrenBelow(reopt->reopttree, set, blkmem, 0, FALSE, FALSE) );
2930 SCIP_CALL( SCIPreoptResetDualBndchgs(reopt, node, blkmem) );
2931 }
2932 /* dive through all children and change the reopttype to LEAF */
2933 else
2934 {
2936 }
2937 }
2938 else
2939 SCIP_CALL( SCIPreoptResetDualBndchgs(reopt, node, blkmem) );
2940
2941 /* update the lowerbound if it was not set */
2942 if( !SCIPsetIsInfinity(set, REALABS(lowerbound)) )
2943 reopt->reopttree->reoptnodes[id]->lowerbound = lowerbound;
2944
2945 SCIPsetDebugMsg(set, "update node %d at ID %d:\n", 1, 0);
2946 SCIPsetDebugMsg(set, " -> nvars: 0, ncons: 0, parentID: -, reopttype: %d, lowerbound:%g \n", reopttype,
2947 reopt->reopttree->reoptnodes[id]->lowerbound);
2948
2949 break;
2950
2951 default:
2952 assert(reopttype == SCIP_REOPTTYPE_TRANSIT
2953 || reopttype == SCIP_REOPTTYPE_INFSUBTREE
2954 || reopttype == SCIP_REOPTTYPE_STRBRANCHED
2955 || reopttype == SCIP_REOPTTYPE_PRUNED
2956 || reopttype == SCIP_REOPTTYPE_FEASIBLE);
2957 break;
2958 }/*lint !e788*/
2959
2960 /* reset the information of dual bound changes */
2961 reopt->currentnode = -1;
2962 if( reopt->dualreds != NULL )
2963 reopt->dualreds->nvars = 0;
2964
2965 /* stop clock */
2966 SCIPclockStop(reopt->savingtime, set);
2967
2968 return SCIP_OKAY;
2969 }
2970 else
2971 {
2972 int nbndchgdiff;
2973 SCIP_Bool transintoorig;
2974
2975 SCIPsetDebugMsg(set, "try to add node #%lld to the reopttree\n", SCIPnodeGetNumber(node));
2976 SCIPsetDebugMsg(set, " -> reopttype = %d\n", reopttype);
2977
2978 /* check if we really want to save this node:
2979 * 1. save the node if reopttype is at least SCIP_REOPTTYPE_INFSUBTREE
2980 * 2. save the node if the number of bound changes of this node
2981 * and the last saved node is at least a given number n
2982 */
2983
2984 /* get the ID of the last saved node or 0 for the root */
2985 SCIP_CALL( getLastSavedNode(reopt, set, node, &parent, &parentid, &nbndchgdiff) );
2986
2987 if( (reopttype < SCIP_REOPTTYPE_INFSUBTREE && nbndchgdiff <= set->reopt_maxdiffofnodes)
2988 || reopt->reopttree->reoptnodes[parentid]->reopttype >= SCIP_REOPTTYPE_LEAF ) /*lint !e641*/
2989 {
2990 SCIPsetDebugMsg(set, " -> skip saving\n");
2991
2992 /* stop clock */
2993 SCIPclockStop(reopt->savingtime, set);
2994
2995 return SCIP_OKAY;
2996 }
2997
2998 /* check if there are free slots to store the node */
2999 SCIP_CALL( reopttreeCheckMemory(reopt->reopttree, set, blkmem) );
3000
3002
3003 SCIPsetDebugMsg(set, " -> save at ID %u\n", id);
3004
3005 assert(reopt->reopttree->reoptnodes[id] == NULL
3006 || (reopt->reopttree->reoptnodes[id]->nvars == 0 && reopt->reopttree->reoptnodes[id]->nconss == 0));
3007 assert(id >= 1 && id < reopt->reopttree->reoptnodessize);
3008 assert(!isrootnode);
3009
3010 /* get memory for nodedata */
3011 assert(reopt->reopttree->reoptnodes[id] == NULL || reopt->reopttree->reoptnodes[id]->nvars == 0);
3012 SCIP_CALL( createReoptnode(reopt->reopttree, set, blkmem, id) );
3013 reopt->reopttree->reoptnodes[id]->parentID = parentid;
3014
3015 assert(parent != NULL );
3016 assert((SCIPnodeGetDepth(parent) == 0 && parentid == 0) || (SCIPnodeGetDepth(parent) >= 1 && parentid > 0));
3017 assert(id >= 1);
3018
3019 /* create the array of "child nodes" if they not exist */
3020 if( reopt->reopttree->reoptnodes[parentid]->childids == NULL
3021 || reopt->reopttree->reoptnodes[parentid]->allocchildmem == 0 )
3022 {
3023 SCIP_CALL( reoptnodeCheckMemory(reopt->reopttree->reoptnodes[parentid], set, blkmem, 0, 2, 0) );
3024 }
3025
3026 /* add the new node as a "child node" of the last saved reoptminization node */
3027 SCIP_CALL( reoptAddChild(reopt->reopttree, set, blkmem, parentid, id) );
3028
3029 /* save branching path */
3030 SCIP_CALL( saveAncestorBranchings(reopt->reopttree, set, blkmem, node, parent, id, parentid) );
3031
3032 /* save bound changes after some dual reduction */
3033 if( saveafterdual )
3034 {
3035 assert(reopttype == SCIP_REOPTTYPE_STRBRANCHED);
3036 SCIP_CALL( saveAfterDualBranchings(reopt, set, blkmem, node, id, &transintoorig) );
3037 }
3038 else
3039 {
3040 SCIPsetDebugMsg(set, " -> skip saving bound changes after dual reductions.\n");
3041 }
3042
3043 /* transform all bounds of branched variables and ensure that they are original. */
3044 SCIP_CALL( transformIntoOrig(reopt, id) );
3045
3046 /* save pseudo-constraints (if one exists) */
3047 if (SCIPnodeGetNAddedConss(node) >= 1)
3048 {
3049 assert(reopt->reopttree->reoptnodes[id]->nconss == 0);
3050
3051 SCIP_CALL( saveLocalConssData(reopt->reopttree, set, blkmem, node, id) );
3052 }
3053
3054 /* store separated cuts
3055 * note: we need to call this after saveLocalConssData to be sure that the local conss array is ordered, first all
3056 * local constraints, then cuts
3057 */
3058 if( set->reopt_usecuts )
3059 {
3060 SCIP_CALL( storeCuts(reopt, set, blkmem, lp, id) );
3061 }
3062
3063 /* update the lowerbound if it was not set */
3064 if( !SCIPsetIsInfinity(set, REALABS(lowerbound)) )
3065 reopt->reopttree->reoptnodes[id]->lowerbound = lowerbound;
3066
3067 /* set ID */
3068 SCIPnodeSetReoptID(node, id);
3069
3070 /* set the REOPTTYPE */
3071 SCIPnodeSetReopttype(node, reopttype);
3072
3073 SCIPsetDebugMsg(set, "save node #%lld successful\n", SCIPnodeGetNumber(node));
3074 SCIPsetDebugMsg(set, " -> nvars: %d, ncons: %d, parentID: %u, reopttype: %d, lowerbound: %g\n",
3075 reopt->reopttree->reoptnodes[id]->nvars + reopt->reopttree->reoptnodes[id]->nafterdualvars,
3076 reopt->reopttree->reoptnodes[id]->nconss, reopt->reopttree->reoptnodes[id]->parentID,
3077 reopttype, reopt->reopttree->reoptnodes[id]->lowerbound);
3078#ifdef SCIP_MORE_DEBUG
3079 {
3080 for( int varnr = 0; varnr < reopt->reopttree->reoptnodes[id]->nvars; ++varnr )
3081 {
3082 for( int varnr = 0; varnr < reopt->reopttree->reoptnodes[id]->nvars; ++varnr )
3083 {
3084 SCIPsetDebugMsg(set, " <%s> %s %g\n", SCIPvarGetName(reopt->reopttree->reoptnodes[id]->vars[varnr]),
3086 "=>" : "<=", reopt->reopttree->reoptnodes[id]->varbounds[varnr]);
3087 }
3088 for( int varnr = 0; varnr < reopt->reopttree->reoptnodes[id]->nafterdualvars; ++varnr )
3089 {
3090 SCIPsetDebugMsg(set, " <%s> %s %g (after dual red.)\n",
3091 SCIPvarGetName(reopt->reopttree->reoptnodes[id]->afterdualvars[varnr]),
3093 "=>" : "<=", reopt->reopttree->reoptnodes[id]->afterdualvarbounds[varnr]);
3094 }
3095 }
3096 }
3097#endif
3098 } /*lint !e438*/
3099
3100 switch( reopttype )
3101 {
3105 TRANSIT:
3106 if( !shrank )
3107 reopt->reopttree->reoptnodes[id]->reopttype = (unsigned int)reopttype;
3108 else
3109 {
3110 SCIPnodeSetReoptID(node, 0);
3112 }
3113 break;
3114
3117 PSEUDO:
3118 assert(reopt->currentnode == SCIPnodeGetNumber(node));
3119
3120 reopt->reopttree->reoptnodes[id]->reopttype = (unsigned int)reopttype;
3121 reopt->reopttree->reoptnodes[id]->dualreds = TRUE;
3122
3123 /* get all the dual information and decide if the constraint need
3124 * to be added next or after next */
3125 SCIP_CALL( collectDualInformation(reopt, set, blkmem, node, id, reopttype) );
3126
3127 break;
3128
3130 FEASIBLE:
3131 reopt->reopttree->reoptnodes[id]->reopttype = (unsigned int)SCIP_REOPTTYPE_FEASIBLE;
3132 reopt->reopttree->reoptnodes[id]->dualreds = FALSE;
3133 ++reopt->reopttree->nfeasnodes;
3134 ++reopt->reopttree->ntotalfeasnodes;
3135
3136 break;
3137
3139 PRUNED:
3140 reopt->reopttree->reoptnodes[id]->reopttype = (unsigned int)SCIP_REOPTTYPE_PRUNED;
3141 reopt->reopttree->reoptnodes[id]->dualreds = FALSE;
3142 ++reopt->reopttree->nprunednodes;
3143 ++reopt->reopttree->ntotalprunednodes;
3144
3145 break;
3146
3147 default:
3148 assert(reopttype == SCIP_REOPTTYPE_TRANSIT
3149 || reopttype == SCIP_REOPTTYPE_LOGICORNODE
3150 || reopttype == SCIP_REOPTTYPE_LEAF
3151 || reopttype == SCIP_REOPTTYPE_INFSUBTREE
3152 || reopttype == SCIP_REOPTTYPE_STRBRANCHED
3153 || reopttype == SCIP_REOPTTYPE_FEASIBLE
3154 || reopttype == SCIP_REOPTTYPE_PRUNED);
3155 break;
3156 } /*lint !e788*/
3157
3158 /* stop clock */
3159 SCIPclockStop(reopt->savingtime, set);
3160
3161 /* reset the information of dual bound changes */
3162 reopt->currentnode = -1;
3163 if( reopt->dualreds != NULL )
3164 reopt->dualreds->nvars = 0;
3165
3166 return SCIP_OKAY;
3167}
3168
3169/** delete the stored information about dual bound changes of the last focused node */
3170static
3172 SCIP_REOPT* reopt /**< reoptimization data structure */
3173 )
3174{
3175 assert(reopt != NULL);
3176
3177 if( reopt->dualreds != NULL && reopt->dualreds->nvars > 0 )
3178 {
3179 SCIPdebugMessage("delete %d dual variable information about node %lld\n", reopt->dualreds->nvars,
3180 reopt->currentnode);
3181 reopt->dualreds->nvars = 0;
3182 reopt->currentnode = -1;
3183 }
3184}
3185
3186/** delete the stored constraints that dual information at the given reoptimization node */
3187static
3189 SCIP_REOPTNODE* reoptnode, /**< reoptimization node */
3190 BMS_BLKMEM* blkmem /**< block memory */
3191 )
3192{
3193 assert(reoptnode != NULL);
3194 assert(blkmem != NULL);
3195
3196 if( reoptnode->dualredscur != NULL )
3197 {
3198 SCIP_REOPTCONSDATA* reoptconsdata;
3199
3200 SCIPdebugMessage("reset dual information (current run)\n");
3201
3202 reoptconsdata = reoptnode->dualredscur;
3203
3204 BMSfreeBlockMemoryArray(blkmem, &reoptconsdata->boundtypes, reoptconsdata->varssize);
3205 BMSfreeBlockMemoryArray(blkmem, &reoptconsdata->vals, reoptconsdata->varssize);
3206 BMSfreeBlockMemoryArray(blkmem, &reoptconsdata->vars, reoptconsdata->varssize);
3207 BMSfreeBlockMemory(blkmem, &reoptnode->dualredscur);
3208 reoptnode->dualredscur = NULL;
3209 }
3210
3211 if( reoptnode->dualredsnex != NULL )
3212 {
3213 SCIP_REOPTCONSDATA* reoptconsdata;
3214
3215 SCIPdebugMessage("reset dual information (next run)\n");
3216
3217 reoptconsdata = reoptnode->dualredsnex;
3218
3219 BMSfreeBlockMemoryArray(blkmem, &reoptconsdata->boundtypes, reoptconsdata->varssize);
3220 BMSfreeBlockMemoryArray(blkmem, &reoptconsdata->vals, reoptconsdata->varssize);
3221 BMSfreeBlockMemoryArray(blkmem, &reoptconsdata->vars, reoptconsdata->varssize);
3222 BMSfreeBlockMemory(blkmem, &reoptnode->dualredsnex);
3223 reoptnode->dualredsnex = NULL;
3224 }
3225
3226 reoptnode->dualreds = FALSE;
3227
3228 return SCIP_OKAY;
3229}
3230
3231
3232/** transform given set of variables, bounds and boundtypes into a global cut.
3233 *
3234 * @note: boundtypes can be NULL if all variables are binary or a MIP solution should be separated.
3235 * @note: continuous variables will be skiped if boundtypes is NULL
3236 */
3237static
3239 SCIP_REOPT* reopt, /**< reoptimization data structure */
3240 BMS_BLKMEM* blkmem, /**< block memory */
3241 SCIP_SET* set, /**< global SCIP settings */
3242 SCIP_VAR** vars, /**< variables of the cut */
3243 SCIP_Real* vals, /**< values of the cut */
3244 SCIP_BOUNDTYPE* boundtypes, /**< bounds of the cut */
3245 int nvars, /**< number of variables in the cut */
3246 int nbinvars, /**< number of binary variables */
3247 int nintvars /**< number of integer variables */
3248 )
3249{
3250 SCIP_REOPTCONSDATA* reoptconsdata;
3251 int nglbconss;
3252 int nvarsadded;
3253
3254 assert(reopt != NULL);
3255 assert(blkmem != NULL);
3256 assert(set != NULL);
3257 assert(vars != NULL);
3258 assert(vals != NULL);
3259 assert(nbinvars + nintvars == nvars);
3260
3261 nvarsadded = 0;
3262
3263 /* check whether we have enough memory allocated */
3264 SCIP_CALL( checkMemGlbCons(reopt, set, blkmem, 10) );
3265 nglbconss = reopt->nglbconss;
3266 reoptconsdata = NULL;
3267
3268 if( reopt->glbconss[nglbconss] == NULL )
3269 {
3270 SCIP_ALLOC( BMSallocBlockMemory(blkmem, &reopt->glbconss[nglbconss]) ); /*lint !e866*/
3271 reoptconsdata = reopt->glbconss[nglbconss];
3272
3273 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &reoptconsdata->vars, (int)(nbinvars+2*nintvars)) );
3274 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &reoptconsdata->vals, (int)(nbinvars+2*nintvars)) );
3275 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &reoptconsdata->boundtypes, (int)(nbinvars+2*nintvars)) );
3276 reoptconsdata->varssize = (int)(nbinvars+2*nintvars);
3277 reoptconsdata->nvars = 0;
3278 }
3279 else
3280 {
3281 assert(reopt->glbconss[nglbconss]->nvars == 0);
3282 assert(reopt->glbconss[nglbconss]->varssize > 0);
3283
3284 reoptconsdata = reopt->glbconss[nglbconss];
3285
3286 if( reoptconsdata->varssize < nbinvars+2*nintvars )
3287 {
3288 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &reoptconsdata->vars, reoptconsdata->varssize, \
3289 (int)(nbinvars+2*nintvars)) );
3290 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &reoptconsdata->vals, reoptconsdata->varssize, \
3291 (int)(nbinvars+2*nintvars)) );
3292 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &reoptconsdata->boundtypes, reoptconsdata->varssize, \
3293 (int)(nbinvars+2*nintvars)) );
3294 reoptconsdata->varssize = (int)(nbinvars+2*nintvars);
3295 }
3296 }
3297 assert(reoptconsdata != NULL);
3298
3299 reoptconsdata->lhs = 1.0;
3300 reoptconsdata->rhs = SCIPsetInfinity(set);
3301 reoptconsdata->linear = FALSE;
3302 reoptconsdata->constype = REOPT_CONSTYPE_CUT;
3303
3304 for( int v = 0; v < nvars; ++v )
3305 {
3306 assert(nvarsadded < reoptconsdata->varssize);
3307 assert(vars[v] != NULL);
3308 assert(SCIPvarIsOriginal(vars[v]));
3309 assert(SCIPvarGetType(vars[v]) == SCIP_VARTYPE_CONTINUOUS || SCIPsetIsIntegral(set, vals[v]));
3310
3311 /* if no boundtypes are given we skip continuous variables, otherwise we would add trivial clauses:
3312 * a) x <= ub
3313 * b) lb <= x
3314 * c) (x <= val) or (x >= val)
3315 */
3316 if( boundtypes == NULL && SCIPvarGetType(vars[v]) == SCIP_VARTYPE_CONTINUOUS )
3317 continue;
3318
3319 if( SCIPvarGetType(vars[v]) == SCIP_VARTYPE_BINARY )
3320 {
3321 reoptconsdata->vars[nvarsadded] = vars[v];
3322
3323 if( SCIPsetIsEQ(set, vals[v], 1.0) )
3324 {
3325 assert(boundtypes == NULL || boundtypes[v] == SCIP_BOUNDTYPE_LOWER);
3326 reoptconsdata->vals[nvarsadded] = 0.0;
3327 reoptconsdata->boundtypes[nvarsadded] = SCIP_BOUNDTYPE_UPPER;
3328 }
3329 else
3330 {
3331 assert(SCIPsetIsEQ(set, vals[v], 0.0));
3332 assert(boundtypes == NULL || boundtypes[v] == SCIP_BOUNDTYPE_UPPER);
3333 reoptconsdata->vals[nvarsadded] = 1.0;
3334 reoptconsdata->boundtypes[nvarsadded] = SCIP_BOUNDTYPE_LOWER;
3335 }
3336 ++nvarsadded;
3337 }
3338 else if( SCIPvarGetType(vars[v]) == SCIP_VARTYPE_CONTINUOUS)
3339 {
3340 assert(boundtypes != NULL);
3341
3342 reoptconsdata->vals[nvarsadded] = vals[v];
3343 reoptconsdata->boundtypes[nvarsadded] = (boundtypes[v] == SCIP_BOUNDTYPE_LOWER ? SCIP_BOUNDTYPE_UPPER : SCIP_BOUNDTYPE_LOWER);
3344 ++nvarsadded;
3345 }
3346 else
3347 {
3348 SCIP_Real roundedval;
3349 SCIP_Real ubglb;
3350 SCIP_Real lbglb;
3351
3353
3354 reoptconsdata->vars[nvarsadded] = vars[v];
3355
3356 ubglb = SCIPvarGetUbGlobal(vars[v]);
3357 lbglb = SCIPvarGetLbGlobal(vars[v]);
3358
3359 /* case 1 : x == val == ub -> x <= ub-1
3360 * case 2 : x == val == lb -> x >= lb+1
3361 * case 3.1: x <= val < ub -> x >= y+1
3362 * case 3.2: x >= val > lb -> x <= y-1
3363 * case 4 : lb < x == val < ub -> (x <= y-1) or (x >= y+1)
3364 */
3365
3366 /* case 1 */
3367 if( SCIPsetIsEQ(set, vals[v], ubglb) )
3368 {
3369 assert(boundtypes == NULL || boundtypes[v] == SCIP_BOUNDTYPE_LOWER);
3370 reoptconsdata->vals[nvarsadded] = ubglb - 1.0;
3371 reoptconsdata->boundtypes[nvarsadded] = SCIP_BOUNDTYPE_UPPER;
3372 ++nvarsadded;
3373 }
3374 /* case 2 */
3375 else if( SCIPsetIsEQ(set, vals[v], lbglb) )
3376 {
3377 assert(boundtypes == NULL || boundtypes[v] == SCIP_BOUNDTYPE_UPPER);
3378 reoptconsdata->vals[nvarsadded] = lbglb + 1.0;
3379 reoptconsdata->boundtypes[nvarsadded] = SCIP_BOUNDTYPE_LOWER;
3380 ++nvarsadded;
3381 }
3382 else if( boundtypes != NULL )
3383 {
3384 /* we round the solution value to get a 'clean' bound */
3385 assert(SCIPsetIsIntegral(set, vals[v]));
3386 roundedval = SCIPsetRound(set, vals[v]);
3387
3388 /* case 3.1 */
3389 if( boundtypes[v] == SCIP_BOUNDTYPE_UPPER )
3390 {
3391 reoptconsdata->vals[nvarsadded] = roundedval + 1.0;
3392 reoptconsdata->boundtypes[nvarsadded] = SCIP_BOUNDTYPE_LOWER;
3393 ++nvarsadded;
3394 }
3395 /* case 3.2 */
3396 else
3397 {
3398 assert(boundtypes[v] == SCIP_BOUNDTYPE_LOWER);
3399 reoptconsdata->vals[nvarsadded] = roundedval - 1.0;
3400 reoptconsdata->boundtypes[nvarsadded] = SCIP_BOUNDTYPE_UPPER;
3401 ++nvarsadded;
3402 }
3403 }
3404 /* case 4: in this case we have to add two clauses: (x <= val-1) and (x >= val+1) */
3405 else
3406 {
3407 /* we round the solution value to get a 'clean' bound */
3408 assert(SCIPsetIsIntegral(set, vals[v]));
3409 roundedval = SCIPsetRound(set, vals[v]);
3410
3411 /* first clause: x <= val-1 */
3412 reoptconsdata->vals[nvarsadded] = roundedval - 1.0;
3413 reoptconsdata->boundtypes[nvarsadded] = SCIP_BOUNDTYPE_UPPER;
3414 ++nvarsadded;
3415
3416 /* second clause: x >= val+1 */
3417 reoptconsdata->vars[nvarsadded] = vars[v];
3418 reoptconsdata->vals[nvarsadded] = roundedval + 1.0;
3419 reoptconsdata->boundtypes[nvarsadded] = SCIP_BOUNDTYPE_LOWER;
3420 ++nvarsadded;
3421 }
3422 }
3423 }
3424 assert(nvars <= nvarsadded);
3425 assert(nvarsadded == nbinvars + 2 * nintvars);
3426
3427 reoptconsdata->nvars = nvarsadded;
3428 ++reopt->nglbconss;
3429
3430 return SCIP_OKAY;
3431}
3432
3433/** generate a global constraint to separate an infeasible subtree */
3434static
3436 SCIP_REOPT* reopt, /**< reoptimization data structure */
3437 SCIP_SET* set, /**< global SCIP settings */
3438 BMS_BLKMEM* blkmem, /**< block memory */
3439 SCIP_NODE* node, /**< node of the search tree */
3440 REOPT_CONSTYPE consttype /**< reopttype of the constraint */
3441 )
3442{
3443 assert(reopt != NULL);
3444 assert(node != NULL);
3445
3446 if( consttype == REOPT_CONSTYPE_INFSUBTREE )
3447 {
3448 SCIP_VAR** vars;
3449 SCIP_Real* vals;
3450 SCIP_BOUNDTYPE* boundtypes;
3451 int allocmem;
3452 int nbranchvars;
3453 int nbinvars;
3454 int nintvars;
3455
3456 /* allocate memory to store the infeasible path */
3457 allocmem = SCIPnodeGetDepth(node);
3458 SCIP_CALL( SCIPsetAllocBufferArray(set, &vars, allocmem) );
3459 SCIP_CALL( SCIPsetAllocBufferArray(set, &vals, allocmem) );
3460 SCIP_CALL( SCIPsetAllocBufferArray(set, &boundtypes, allocmem) );
3461
3462 /* get the branching path */
3463 SCIPnodeGetAncestorBranchings(node, vars, vals, boundtypes, &nbranchvars, allocmem);
3464
3465 if( allocmem < nbranchvars )
3466 {
3467 SCIP_CALL( SCIPsetReallocBufferArray(set, &vars, nbranchvars) );
3468 SCIP_CALL( SCIPsetReallocBufferArray(set, &vals, nbranchvars) );
3469 SCIP_CALL( SCIPsetReallocBufferArray(set, &boundtypes, nbranchvars) );
3470 allocmem = nbranchvars;
3471
3472 SCIPnodeGetAncestorBranchings(node, vars, vals, boundtypes, &nbranchvars, allocmem);
3473 }
3474
3475 /* we count the number of binary and (impl) integer variables */
3476 nbinvars = 0;
3477 nintvars = 0;
3478 for( int v = 0; v < nbranchvars; ++v )
3479 {
3480 if( SCIPvarGetType(vars[v]) == SCIP_VARTYPE_BINARY )
3481 ++nbinvars;
3483 ++nintvars;
3484 }
3485 assert(nbinvars + nintvars == nbranchvars);
3486
3487 SCIP_CALL( addGlobalCut(reopt, blkmem, set, vars, vals, boundtypes, nbranchvars, nbinvars, nintvars) );
3488 assert(!reopt->glbconss[reopt->nglbconss - 1]->linear);
3489
3490 /* free buffer */
3491 SCIPsetFreeBufferArray(set, &boundtypes);
3494 }
3495
3496 return SCIP_OKAY;
3497}
3498
3499
3500/** move all id of child nodes from reoptimization node stored at @p id1 to the node stored at @p id2 */
3501static
3503 SCIP_REOPTTREE* reopttree, /**< reopttree */
3504 SCIP_SET* set, /**< global SCIP settings */
3505 BMS_BLKMEM* blkmem, /**< block memory */
3506 unsigned int id1, /**< source id */
3507 unsigned int id2 /**< target id */
3508 )
3509{
3510 int nchilds_id1;
3511 int nchilds_id2;
3512
3513 assert(reopttree != NULL);
3514 assert(blkmem != NULL);
3515 assert(id1 < reopttree->reoptnodessize);
3516 assert(id2 < reopttree->reoptnodessize);
3517 assert(reopttree->reoptnodes[id1] != NULL);
3518 assert(reopttree->reoptnodes[id2] != NULL);
3519
3520 nchilds_id1 = reopttree->reoptnodes[id1]->nchilds;
3521 nchilds_id2 = reopttree->reoptnodes[id2]->nchilds;
3522
3523 /* ensure that the array storing the child id's is large enough */
3524 SCIP_CALL( reoptnodeCheckMemory(reopttree->reoptnodes[id2], set, blkmem, 0, nchilds_id1+nchilds_id2, 0) );
3525 assert(reopttree->reoptnodes[id2]->allocchildmem >= nchilds_id1+nchilds_id2);
3526
3527 SCIPsetDebugMsg(set, "move %d IDs: %u -> %u\n", nchilds_id1, id1, id2);
3528
3529 /* move the ids */
3530 for( int c = 0; c < nchilds_id1; ++c )
3531 {
3532#ifdef SCIP_DEBUG
3533 {
3534 /* check that no id is added twice */
3535 for( int k = 0; k < nchilds_id2; ++k )
3536 assert(reopttree->reoptnodes[id2]->childids[k] != reopttree->reoptnodes[id1]->childids[c]);
3537 }
3538#endif
3539
3540 reopttree->reoptnodes[id2]->childids[nchilds_id2+c] = reopttree->reoptnodes[id1]->childids[c];
3541 }
3542
3543 /* update the number of childs */
3544 reopttree->reoptnodes[id1]->nchilds = 0;
3545 reopttree->reoptnodes[id2]->nchilds += nchilds_id1;
3546
3547 return SCIP_OKAY;
3548}
3549
3550/** change all bound changes along the root path */
3551static
3553 SCIP_REOPT* reopt, /**< reoptimization data structure */
3554 SCIP_SET* set, /**< global SCIP settings */
3555 SCIP_STAT* stat, /**< dynamic problem statistics */
3556 SCIP_PROB* transprob, /**< transformed problem */
3557 SCIP_PROB* origprob, /**< original problem */
3558 SCIP_TREE* tree, /**< search tree */
3559 SCIP_LP* lp, /**< current LP */
3560 SCIP_BRANCHCAND* branchcand, /**< branching candidates */
3561 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3562 SCIP_CLIQUETABLE* cliquetable, /**< clique table */
3563 BMS_BLKMEM* blkmem, /**< block memory */
3564 SCIP_NODE* node, /**< node of the branch and bound tree */
3565 unsigned int id, /**< id of stored node */
3566 SCIP_Bool afterdualbranching /**< convert all bound changes made directly after the first bound
3567 * changes based on dual information into normal branchings */
3568 )
3569{
3570 SCIP_REOPTTREE* reopttree;
3571 SCIP_REOPTNODE* reoptnode;
3572
3573 assert(reopt != NULL);
3574 assert(set != NULL);
3575 assert(stat != NULL);
3576 assert(transprob != NULL);
3577 assert(tree != NULL);
3578 assert(lp != NULL);
3579 assert(branchcand != NULL);
3580 assert(eventqueue != NULL);
3581 assert(cliquetable != NULL);
3582 assert(node != NULL);
3583 assert(blkmem != NULL);
3584
3585 reopttree = reopt->reopttree;
3586 assert(reopttree != NULL);
3587 assert(id < reopttree->reoptnodessize);
3588
3589 reoptnode = reopttree->reoptnodes[id];
3590 assert(reoptnode != NULL);
3591
3592 /* copy memory to ensure that only original variables are saved */
3593 if( reoptnode->nvars == 0 && reoptnode->nafterdualvars == 0)
3594 return SCIP_OKAY;
3595
3596 /* change the bounds along the branching path */
3597 for( int v = 0; v < reoptnode->nvars; ++v )
3598 {
3599 SCIP_VAR* var;
3600 SCIP_Real val;
3601 SCIP_BOUNDTYPE boundtype;
3602 SCIP_Real oldlb;
3603 SCIP_Real oldub;
3604 SCIP_Real newbound;
3605
3606 var = reoptnode->vars[v];
3607 val = reoptnode->varbounds[v];
3608 boundtype = reoptnode->varboundtypes[v];
3609
3610 assert(SCIPvarIsOriginal(var));
3611 SCIP_CALL( SCIPvarGetProbvarBound(&var, &val, &boundtype) );
3612 assert(SCIPvarIsTransformed(var));
3614
3615 oldlb = SCIPvarGetLbLocal(var);
3616 oldub = SCIPvarGetUbLocal(var);
3617 newbound = val;
3618
3619 assert(boundtype == SCIP_BOUNDTYPE_LOWER || boundtype == SCIP_BOUNDTYPE_UPPER);
3620
3621 if( boundtype == SCIP_BOUNDTYPE_LOWER && SCIPsetIsGT(set, newbound, oldlb) && SCIPsetIsFeasLE(set, newbound, oldub) )
3622 {
3623 SCIPvarAdjustLb(var, set, &newbound);
3624
3625 SCIP_CALL( SCIPnodeAddBoundchg(node, blkmem, set, stat, transprob, origprob,
3626 tree, reopt, lp, branchcand, eventqueue, cliquetable, var, newbound, SCIP_BOUNDTYPE_LOWER, FALSE) );
3627 }
3628 else if( boundtype == SCIP_BOUNDTYPE_UPPER && SCIPsetIsLT(set, newbound, oldub) && SCIPsetIsFeasGE(set, newbound, oldlb) )
3629 {
3630 SCIPvarAdjustUb(var, set, &newbound);
3631
3632 SCIP_CALL( SCIPnodeAddBoundchg(node, blkmem, set, stat, transprob, origprob,
3633 tree, reopt, lp, branchcand, eventqueue, cliquetable, var, newbound, SCIP_BOUNDTYPE_UPPER, FALSE) );
3634 }
3635#ifdef SCIP_MORE_DEBUG
3636 SCIPsetDebugMsg(set, " (path) <%s> %s %g\n", SCIPvarGetName(var), boundtype == SCIP_BOUNDTYPE_LOWER ? "=>" : "<=", newbound);
3637#endif
3638 }
3639
3640 if( afterdualbranching && reoptnode->nafterdualvars > 0 )
3641 {
3642 /* check the memory to convert this bound changes into 'normal' */
3643 SCIP_CALL( reoptnodeCheckMemory(reopttree->reoptnodes[id], set, blkmem,
3644 reoptnode->nvars + reoptnode->nafterdualvars, 0, 0) );
3645
3646 /* change the bounds */
3647 for( int v = 0; v < reoptnode->nafterdualvars; ++v )
3648 {
3649 SCIP_VAR* var;
3650 SCIP_Real val;
3651 SCIP_BOUNDTYPE boundtype;
3652 SCIP_Bool bndchgd;
3653 SCIP_Real oldlb;
3654 SCIP_Real oldub;
3655 SCIP_Real newbound;
3656
3657 var = reoptnode->afterdualvars[v];
3658 val = reoptnode->afterdualvarbounds[v];
3659 boundtype = reoptnode->afterdualvarboundtypes[v];
3660
3661 assert(SCIPvarIsOriginal(var));
3662 SCIP_CALL( SCIPvarGetProbvarBound(&var, &val, &boundtype) );
3663 assert(SCIPvarIsTransformed(var));
3665
3666 bndchgd = FALSE;
3667
3668 oldlb = SCIPvarGetLbLocal(var);
3669 oldub = SCIPvarGetUbLocal(var);
3670 newbound = val;
3671
3672 if( boundtype == SCIP_BOUNDTYPE_LOWER && SCIPsetIsGT(set, newbound, oldlb) && SCIPsetIsFeasLE(set, newbound, oldub) )
3673 {
3674 SCIPvarAdjustLb(var, set, &newbound);
3675 SCIP_CALL( SCIPnodeAddBoundchg(node, blkmem, set, stat, transprob, origprob,
3676 tree, reopt, lp, branchcand, eventqueue, cliquetable, var, newbound, SCIP_BOUNDTYPE_LOWER, FALSE) );
3677
3678 bndchgd = TRUE;
3679 }
3680 else if( boundtype == SCIP_BOUNDTYPE_UPPER && SCIPsetIsLT(set, newbound, oldub) && SCIPsetIsFeasGE(set, newbound, oldlb) )
3681 {
3682 SCIPvarAdjustUb(var, set, &newbound);
3683 SCIP_CALL( SCIPnodeAddBoundchg(node, blkmem, set, stat, transprob, origprob,
3684 tree, reopt, lp, branchcand, eventqueue, cliquetable, var, newbound, SCIP_BOUNDTYPE_UPPER, FALSE) );
3685
3686 bndchgd = TRUE;
3687 }
3688
3689 assert(boundtype == SCIP_BOUNDTYPE_LOWER || boundtype == SCIP_BOUNDTYPE_UPPER);
3690
3691#ifdef SCIP_MORE_DEBUG
3692 SCIPsetDebugMsg(set, " (prop) <%s> %s %g\n", SCIPvarGetName(var), boundtype == SCIP_BOUNDTYPE_LOWER ? "=>" : "<=", newbound);
3693#endif
3694 if( bndchgd )
3695 {
3696 int nvars;
3697
3698 nvars = reoptnode->nvars;
3699 reoptnode->vars[nvars] = reoptnode->afterdualvars[v];
3700 reoptnode->varbounds[nvars] = reoptnode->afterdualvarbounds[v];
3701 reoptnode->varboundtypes[nvars] = reoptnode->afterdualvarboundtypes[v];
3702 ++reoptnode->nvars;
3703 }
3704 }
3705
3706 /* free the afterdualvars, -bounds, and -boundtypes */
3707 BMSfreeBlockMemoryArray(blkmem, &reoptnode->afterdualvarboundtypes, reoptnode->afterdualvarssize);
3708 reoptnode->afterdualvarboundtypes = NULL;
3709
3710 BMSfreeBlockMemoryArray(blkmem, &reoptnode->afterdualvarbounds, reoptnode->afterdualvarssize);
3711 reoptnode->afterdualvarbounds = NULL;
3712
3713 BMSfreeBlockMemoryArray(blkmem, &reoptnode->afterdualvars, reoptnode->afterdualvarssize);
3714 reoptnode->afterdualvars = NULL;
3715
3716 reoptnode->nafterdualvars = 0;
3717 reoptnode->afterdualvarssize = 0;
3718 }
3719
3720 return SCIP_OKAY;
3721}
3722
3723
3724/** add a constraint to ensure that at least one variable bound gets different */
3725static
3727 SCIP_REOPT* reopt, /**< reoptimization data structure */
3728 SCIP* scip, /**< SCIP data structure */
3729 SCIP_SET* set, /**< global SCIP settings */
3730 SCIP_STAT* stat, /**< dynamic problem statistics */
3731 BMS_BLKMEM* blkmem, /**< block memory */
3732 SCIP_PROB* transprob, /**< transformed problem */
3733 SCIP_PROB* origprob, /**< original problem */
3734 SCIP_TREE* tree, /**< search tree */
3735 SCIP_LP* lp, /**< current LP */
3736 SCIP_BRANCHCAND* branchcand, /**< branching candidates */
3737 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3738 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
3739 SCIP_NODE* node, /**< node corresponding to the pruned part */
3740 unsigned int id /**< id of stored node */
3741 )
3742{
3743 SCIP_CONS* cons;
3744 char name[SCIP_MAXSTRLEN];
3745
3746 assert(reopt != NULL);
3747 assert(reopt->reopttree != NULL);
3748 assert(id < reopt->reopttree->reoptnodessize);
3749 assert(reopt->reopttree->reoptnodes[id] != NULL);
3750 assert(reopt->reopttree->reoptnodes[id]->dualreds);
3751 assert(reopt->reopttree->reoptnodes[id]->dualredscur != NULL);
3752 assert(scip != NULL);
3753 assert(set != NULL);
3754 assert(stat != NULL);
3755 assert(blkmem != NULL);
3756 assert(transprob != NULL);
3757 assert(origprob != NULL);
3758 assert(tree != NULL);
3759 assert(lp != NULL);
3760 assert(branchcand != NULL);
3761 assert(eventqueue != NULL);
3762 assert(node != NULL);
3763
3764 assert(reopt->reopttree->reoptnodes[id]->dualredscur->constype == REOPT_CONSTYPE_DUALREDS
3765 || reopt->reopttree->reoptnodes[id]->dualredscur->constype == REOPT_CONSTYPE_INFSUBTREE);
3766
3767#ifndef NDEBUG
3768 if( reopt->reopttree->reoptnodes[id]->dualredscur->constype == REOPT_CONSTYPE_DUALREDS )
3769 SCIPsetDebugMsg(set, " create a split-node #%lld\n", SCIPnodeGetNumber(node));
3770 else
3771 SCIPsetDebugMsg(set, " separate an infeasible subtree\n");
3772#endif
3773
3774 /* if the constraint consists of exactly one variable it can be interpreted
3775 * as a normal branching step, i.e., we can fix the variable to the negated bound */
3776 if( reopt->reopttree->reoptnodes[id]->dualredscur->nvars == 1 )
3777 {
3778 SCIP_REOPTCONSDATA* reoptconsdata;
3779 SCIP_VAR* var;
3780 SCIP_BOUNDTYPE boundtype;
3781 SCIP_Real oldlb;
3782 SCIP_Real oldub;
3783 SCIP_Real newbound;
3784
3785 reoptconsdata = reopt->reopttree->reoptnodes[id]->dualredscur;
3786 assert(!reoptconsdata->linear);
3787 assert(reoptconsdata->vars != NULL);
3788 assert(reoptconsdata->vals != NULL);
3789 assert(reoptconsdata->boundtypes != NULL);
3790
3791 var = reoptconsdata->vars[0];
3792 newbound = reoptconsdata->vals[0];
3793 boundtype = reoptconsdata->boundtypes[0];
3794
3795 assert(SCIPvarIsOriginal(var));
3796 SCIP_CALL( SCIPvarGetProbvarBound(&var, &newbound, &boundtype) );
3797 assert(SCIPvarIsTransformed(var));
3798
3799 oldlb = SCIPvarGetLbLocal(var);
3800 oldub = SCIPvarGetUbLocal(var);
3801
3802 if( boundtype == SCIP_BOUNDTYPE_LOWER )
3803 {
3804 newbound = reoptconsdata->vals[0] - 1.0;
3805 /* if newbound > local upper bound, the variable cannot take the old value and we exit */
3806 if( SCIPisGT(scip, newbound, oldub) )
3807 return SCIP_OKAY;
3808 assert(SCIPisLE(scip, newbound, oldub));
3809 }
3810 else
3811 {
3812 newbound = reoptconsdata->vals[0] + 1.0;
3813 /* if newbound < local lower bound, the variable cannot take the old value and we exit */
3814 if( SCIPisLT(scip, newbound, oldlb) )
3815 return SCIP_OKAY;
3816 assert(SCIPisGE(scip, newbound, oldlb));
3817 }
3818 boundtype = (SCIP_BOUNDTYPE) (1 - (int)boundtype);
3819 assert(boundtype == SCIP_BOUNDTYPE_LOWER || boundtype == SCIP_BOUNDTYPE_UPPER);
3820
3821 if( boundtype == SCIP_BOUNDTYPE_LOWER && SCIPsetIsGT(set, newbound, oldlb) && SCIPsetIsFeasLE(set, newbound, oldub) )
3822 {
3823 SCIPvarAdjustLb(var, set, &newbound);
3824 SCIP_CALL( SCIPnodeAddBoundchg(node, blkmem, set, stat, transprob, origprob,
3825 tree, reopt, lp, branchcand, eventqueue, cliquetable, var, newbound, SCIP_BOUNDTYPE_LOWER, FALSE) );
3826 }
3827 else if( boundtype == SCIP_BOUNDTYPE_UPPER && SCIPsetIsLT(set, newbound, oldub) && SCIPsetIsFeasGE(set, newbound, oldlb) )
3828 {
3829 SCIPvarAdjustUb(var, set, &newbound);
3830 SCIP_CALL( SCIPnodeAddBoundchg(node, blkmem, set, stat, transprob, origprob,
3831 tree, reopt, lp, branchcand, eventqueue, cliquetable, var, newbound, SCIP_BOUNDTYPE_UPPER, FALSE) );
3832 }
3833
3834 SCIPsetDebugMsg(set, " -> constraint consists of only one variable: <%s> %s %g\n", SCIPvarGetName(var),
3835 boundtype == SCIP_BOUNDTYPE_LOWER ? "=>" : "<=", newbound);
3836 }
3837 else
3838 {
3839 SCIP_REOPTCONSDATA* reoptconsdata;
3840 SCIP_VAR** consvars;
3841 SCIP_Real consval;
3842 SCIP_BOUNDTYPE consboundtype;
3843 int nbinvars = 0;
3844#ifndef NDEBUG
3845 int nintvars = 0;
3846 int ncontvars = 0;
3847#endif
3848
3849 reoptconsdata = reopt->reopttree->reoptnodes[id]->dualredscur;
3850 assert(!reoptconsdata->linear);
3851 assert(reoptconsdata->vars != NULL);
3852 assert(reoptconsdata->vals != NULL);
3853 assert(reoptconsdata->boundtypes != NULL);
3854
3855 /* allocate buffer */
3856 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, reoptconsdata->nvars) );
3857
3858 /* count number of binary, integer, and continuous variables */
3859 for( int v = 0; v < reoptconsdata->nvars; ++v )
3860 {
3861 switch ( SCIPvarGetType(reoptconsdata->vars[v]) )
3862 {
3864 ++nbinvars;
3865 break;
3868 if( SCIPisEQ(scip, SCIPvarGetLbLocal(reoptconsdata->vars[v]), 0.0)
3869 && SCIPisEQ(scip, SCIPvarGetUbLocal(reoptconsdata->vars[v]), 1.0) )
3870 ++nbinvars;
3871#ifndef NDEBUG
3872 else
3873 ++nintvars;
3874#endif
3875 break;
3877#ifndef NDEBUG
3878 ++ncontvars;
3879#endif
3880 break;
3881 default:
3882 SCIPerrorMessage("Variable <%s> has to be either binary, (implied) integer, or continuous.\n",
3883 SCIPvarGetName(reoptconsdata->vars[v]));
3884 return SCIP_INVALIDDATA;
3885 }
3886 }
3887
3888 if( reoptconsdata->constype == REOPT_CONSTYPE_INFSUBTREE )
3889 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "reopt_inf");
3890 else
3891 {
3892 assert(reoptconsdata->constype == REOPT_CONSTYPE_DUALREDS);
3893 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "reopt_dual");
3894 }
3895
3896 /* case 1: all variables are binary, we use a logic-or constraint. */
3897 if( reoptconsdata->nvars == nbinvars )
3898 {
3899 for( int v = 0; v < reoptconsdata->nvars; ++v )
3900 {
3901 consvars[v] = reoptconsdata->vars[v];
3902 consval = reoptconsdata->vals[v];
3903 consboundtype = SCIPsetIsFeasEQ(set, consval, 1.0) ? SCIP_BOUNDTYPE_LOWER : SCIP_BOUNDTYPE_UPPER;
3904
3905 assert(SCIPvarIsOriginal(consvars[v]));
3906 SCIP_CALL( SCIPvarGetProbvarBound(&consvars[v], &consval, &consboundtype) );
3907 assert(SCIPvarIsTransformed(consvars[v]));
3908 assert(SCIPvarGetStatus(consvars[v]) != SCIP_VARSTATUS_MULTAGGR);
3909
3910 if ( SCIPsetIsFeasEQ(set, consval, 1.0) )
3911 {
3912 SCIP_CALL( SCIPvarNegate(consvars[v], blkmem, set, stat, &consvars[v]) );
3913 assert(SCIPvarIsNegated(consvars[v]));
3914 }
3915 }
3916
3917 SCIP_CALL( SCIPcreateConsLogicor(scip, &cons, name, reoptconsdata->nvars, consvars,
3919 }
3920 /* case 2: at least one variable is integer or continuous. we use a bounddisjunction constraint. */
3921 else
3922 {
3923 SCIP_Real* consvals;
3924 SCIP_BOUNDTYPE* consboundtypes;
3925
3926 assert(nintvars > 0 || ncontvars > 0);
3927
3928 /* alloc buffer memory */
3929 SCIP_CALL( SCIPallocBufferArray(scip, &consvals, reoptconsdata->nvars) );
3930 SCIP_CALL( SCIPallocBufferArray(scip, &consboundtypes, reoptconsdata->nvars) );
3931
3932 /* iterate over all variables and transform them */
3933 for( int v = 0; v < reoptconsdata->nvars; ++v )
3934 {
3935 consvars[v] = reoptconsdata->vars[v];
3936 consvals[v] = reoptconsdata->vals[v];
3937 consboundtypes[v] = reoptconsdata->boundtypes[v];
3938
3939 /* we have to switch the bounds.
3940 * case 1: integer variable with bound x <= u is transformed to u+1 <= x
3941 * and l <= x is transformed to x <= l-1
3942 * case 2: continuous variable with bound x <= u is transformed to u <= x
3943 * and l <= x is transformed to x <= l
3944 */
3945 if( SCIPvarGetType(consvars[v]) == SCIP_VARTYPE_BINARY
3946 || SCIPvarGetType(consvars[v]) == SCIP_VARTYPE_INTEGER
3947 || SCIPvarGetType(consvars[v]) == SCIP_VARTYPE_IMPLINT )
3948 {
3949 if( consboundtypes[v] == SCIP_BOUNDTYPE_UPPER )
3950 {
3951 consvals[v] += 1.0;
3952 assert(SCIPsetIsLE(set, consvals[v], SCIPvarGetUbGlobal(consvars[v])));
3953 }
3954 else
3955 {
3956 consvals[v] -= 1.0;
3957 assert(SCIPsetIsGE(set, consvals[v], SCIPvarGetLbGlobal(consvars[v])));
3958 }
3959 }
3960
3961 consboundtypes[v] = (SCIP_BOUNDTYPE)(1 - consboundtypes[v]); /*lint !e641*/
3962
3963 assert(SCIPvarIsOriginal(consvars[v]));
3964 SCIP_CALL( SCIPvarGetProbvarBound(&consvars[v], &consvals[v], &consboundtypes[v]) );
3965 assert(SCIPvarIsTransformed(consvars[v]));
3966 assert(SCIPvarGetStatus(consvars[v]) != SCIP_VARSTATUS_MULTAGGR);
3967 }
3968
3969 /* create the constraints and add them to the corresponding nodes */
3970 SCIP_CALL( SCIPcreateConsBounddisjunctionRedundant(scip, &cons, name, reoptconsdata->nvars, consvars, consboundtypes,
3971 consvals, FALSE, FALSE, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE, FALSE, TRUE) );
3972
3973 /* free buffer memory */
3974 SCIPfreeBufferArray(scip, &consboundtypes);
3975 SCIPfreeBufferArray(scip, &consvals);
3976 }
3977
3978 SCIPsetDebugMsg(set, " -> add constraint in node #%lld:\n", SCIPnodeGetNumber(node));
3979#ifdef SCIP_DEBUG_CONSS
3981#endif
3982
3983 SCIP_CALL( SCIPaddConsNode(scip, node, cons, NULL) );
3984 SCIP_CALL( SCIPreleaseCons(scip, &cons) );
3985
3986 /* free buffer */
3987 SCIPfreeBufferArray(scip, &consvars);
3988 }
3989
3990 return SCIP_OKAY;
3991}
3992
3993/** fix all bounds ad stored in dualredscur at the given node @p node_fix */
3994static
3996 SCIP_REOPT* reopt, /**< reoptimization data structure */
3997 SCIP_SET* set, /**< global SCIP settings */
3998 SCIP_STAT* stat, /**< dynamic problem statistics */
3999 SCIP_PROB* transprob, /**< transformed problem */
4000 SCIP_PROB* origprob, /**< original problem */
4001 SCIP_TREE* tree, /**< search tree */
4002 SCIP_LP* lp, /**< current LP */
4003 SCIP_BRANCHCAND* branchcand, /**< branching candidates */
4004 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
4005 SCIP_CLIQUETABLE* cliquetable, /**< clique table */
4006 BMS_BLKMEM* blkmem, /**< block memory */
4007 SCIP_NODE* node, /**< node corresponding to the fixed part */
4008 unsigned int id, /**< id of stored node */
4009 SCIP_Bool updatedualconss /**< update constraint representing dual bound changes */
4010 )
4011{
4012 SCIP_REOPTTREE* reopttree;
4013 SCIP_REOPTNODE* reoptnode;
4014
4015 assert(reopt != NULL);
4016 assert(set != NULL);
4017 assert(stat != NULL);
4018 assert(transprob != NULL);
4019 assert(origprob != NULL);
4020 assert(tree != NULL);
4021 assert(lp != NULL);
4022 assert(branchcand != NULL);
4023 assert(eventqueue != NULL);
4024 assert(cliquetable != NULL);
4025 assert(node != NULL);
4026 assert(blkmem != NULL);
4027
4028 reopttree = reopt->reopttree;
4029 assert(reopttree != NULL);
4030 assert(0 < id && id < reopttree->reoptnodessize);
4031
4032 reoptnode = reopttree->reoptnodes[id];
4033 assert(reoptnode != NULL);
4034 assert(reoptnode->dualreds);
4035 assert(reoptnode->dualredscur != NULL);
4036
4037 /* ensure that the arrays to store the bound changes are large enough */
4038 SCIP_CALL( reoptnodeCheckMemory(reoptnode, set, blkmem, reoptnode->nvars + reoptnode->dualredscur->nvars, 0, 0) );
4039
4040 for( int v = 0; v < reoptnode->dualredscur->nvars; ++v )
4041 {
4042 SCIP_VAR* var;
4043 SCIP_Real val;
4044 SCIP_BOUNDTYPE boundtype;
4045 SCIP_Bool bndchgd;
4046
4047 var = reoptnode->dualredscur->vars[v];
4048 val = reoptnode->dualredscur->vals[v];
4049 boundtype = reoptnode->dualredscur->boundtypes[v];
4050
4051 SCIP_CALL(SCIPvarGetProbvarBound(&var, &val, &boundtype));
4052 assert(SCIPvarIsTransformedOrigvar(var));
4053
4054 bndchgd = FALSE;
4055
4056 if( boundtype == SCIP_BOUNDTYPE_LOWER && SCIPsetIsGT(set, val, SCIPvarGetLbLocal(var))
4057 && SCIPsetIsFeasLE(set, val, SCIPvarGetUbLocal(var)) )
4058 {
4059 SCIPvarAdjustLb(var, set, &val);
4060 SCIP_CALL( SCIPnodeAddBoundchg(node, blkmem, set, stat, transprob, origprob,
4061 tree, reopt, lp, branchcand, eventqueue, cliquetable, var, val, SCIP_BOUNDTYPE_LOWER, FALSE) );
4062
4063 bndchgd = TRUE;
4064 }
4065 else if( boundtype == SCIP_BOUNDTYPE_UPPER && SCIPsetIsLT(set, val, SCIPvarGetUbLocal(var))
4066 && SCIPsetIsFeasGE(set, val, SCIPvarGetLbLocal(var)) )
4067 {
4068 SCIPvarAdjustUb(var, set, &val);
4069 SCIP_CALL( SCIPnodeAddBoundchg(node, blkmem, set, stat, transprob, origprob,
4070 tree, reopt, lp, branchcand, eventqueue, cliquetable, var, val, SCIP_BOUNDTYPE_UPPER, FALSE) );
4071
4072 bndchgd = TRUE;
4073 }
4074 else if( boundtype != SCIP_BOUNDTYPE_LOWER && boundtype != SCIP_BOUNDTYPE_UPPER )
4075 {
4076 SCIPerrorMessage("** Unknown boundtype: %d **\n", boundtype);
4077 return SCIP_INVALIDDATA;
4078 }
4079#ifdef SCIP_MORE_DEBUG
4080 SCIPsetDebugMsg(set, " (dual) <%s> %s %g\n", SCIPvarGetName(var), boundtype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", val);
4081#endif
4082 /* add variable and bound to branching path information, because we don't want to delete this data */
4083 if( bndchgd )
4084 {
4085 int pos;
4086 SCIP_Real constant;
4087 SCIP_Real scalar;
4088
4089 pos = reoptnode->nvars;
4090
4091 reoptnode->vars[pos] = var;
4092 scalar = 1.0;
4093 constant = 0.0;
4094 SCIP_CALL( SCIPvarGetOrigvarSum(&reoptnode->vars[pos], &scalar, &constant) );
4095 assert(SCIPvarIsOriginal(reoptnode->vars[pos]));
4096
4097 reoptnode->varbounds[pos] = reoptnode->dualredscur->vals[v];
4098 reoptnode->varboundtypes[pos] = (SCIPsetIsFeasEQ(set, reoptnode->varbounds[pos], 0.0) ? SCIP_BOUNDTYPE_UPPER : SCIP_BOUNDTYPE_LOWER);
4099 ++reoptnode->nvars;
4100 }
4101 }
4102
4103 if( updatedualconss )
4104 {
4105 /* delete dualredscur and move dualredsnex -> dualredscur */
4106 SCIP_CALL( reoptnodeUpdateDualConss(reoptnode, blkmem) );
4107 }
4108
4109 return SCIP_OKAY;
4110}
4111
4112/** fix all bounds corresponding to dual bound changes in a previous iteration in the fashion of interdiction branching;
4113 * keep the first negbndchg-1 bound changes as stored in dualredscur and negate the negbndchg-th bound.
4114 */
4115static
4117 SCIP_REOPT* reopt, /**< reoptimization data structure */
4118 SCIP_SET* set, /**< global SCIP settings */
4119 SCIP_STAT* stat, /**< dynamic problem statistics */
4120 SCIP_PROB* transprob, /**< transformed problem */
4121 SCIP_PROB* origprob, /**< original problem */
4122 SCIP_TREE* tree, /**< search tree */
4123 SCIP_LP* lp, /**< current LP */
4124 SCIP_BRANCHCAND* branchcand, /**< branching candidates */
4125 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
4126 SCIP_CLIQUETABLE* cliquetable, /**< clique table */
4127 BMS_BLKMEM* blkmem, /**< block memory */
4128 SCIP_NODE* node, /**< child node */
4129 unsigned int id, /**< id of the node */
4130 int* perm, /**< array of permuted indices */
4131 SCIP_VAR** vars, /**< variables */
4132 SCIP_Real* vals, /**< bounds */
4133 SCIP_BOUNDTYPE* boundtypes, /**< boundtypes */
4134 int nvars, /**< number of variables */
4135 int negbndchg /**< index of the variable that should negated */
4136 )
4137{
4138 SCIP_VAR* var;
4139 SCIP_Real val;
4140 SCIP_BOUNDTYPE boundtype;
4141 int nbndchgs;
4142
4143 assert(reopt != NULL);
4144 assert(set != NULL);
4145 assert(stat != NULL);
4146 assert(transprob != NULL);
4147 assert(origprob != NULL);
4148 assert(tree != NULL);
4149 assert(lp != NULL);
4150 assert(branchcand != NULL);
4151 assert(eventqueue != NULL);
4152 assert(cliquetable != NULL);
4153 assert(node != NULL);
4154 assert(perm != NULL);
4155 assert(vars != NULL);
4156 assert(vals != NULL);
4157 assert(boundtypes != NULL);
4158 assert(nvars >= 0);
4159 assert(blkmem != NULL);
4160 assert(0 < id && id < reopt->reopttree->reoptnodessize);
4161
4162#ifndef NDEBUG
4163 {
4164 SCIP_REOPTTREE* reopttree;
4165 SCIP_REOPTNODE* reoptnode;
4166
4167 reopttree = reopt->reopttree;
4168 assert(reopttree != NULL);
4169
4170 reoptnode = reopttree->reoptnodes[id];
4171 assert(reoptnode != NULL);
4172 assert(reoptnode->dualreds);
4173 }
4174#endif
4175
4176 nbndchgs = MIN(negbndchg, nvars);
4177
4178 /* change the first nbndchg-1 bounds as stored in dualredscur and negate the negbndchg-th bound */
4179 for( int v = 0; v < nbndchgs; ++v )
4180 {
4181 var = vars[perm[v]];
4182 val = vals[perm[v]];
4183 boundtype = boundtypes[perm[v]];
4184
4185 SCIP_CALL(SCIPvarGetProbvarBound(&var, &val, &boundtype));
4186 assert(SCIPvarIsTransformedOrigvar(var));
4187
4188 /* negate the last bound change */
4189 if( v == nbndchgs-1 )
4190 {
4191 boundtype = (SCIP_BOUNDTYPE)(SCIP_BOUNDTYPE_UPPER - boundtype); /*lint !e656*/
4192 if( SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS && boundtype == SCIP_BOUNDTYPE_UPPER )
4193 val = val - 1.0;
4194 else if( SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS && boundtype == SCIP_BOUNDTYPE_LOWER )
4195 val = val + 1.0;
4196 }
4197
4198 if( boundtype == SCIP_BOUNDTYPE_LOWER && SCIPsetIsGT(set, val, SCIPvarGetLbLocal(var))
4199 && SCIPsetIsFeasLE(set, val, SCIPvarGetUbLocal(var)) )
4200 {
4201 SCIPvarAdjustLb(var, set, &val);
4202 SCIP_CALL( SCIPnodeAddBoundchg(node, blkmem, set, stat, transprob, origprob,
4203 tree, reopt, lp, branchcand, eventqueue, cliquetable, var, val, SCIP_BOUNDTYPE_LOWER, FALSE) );
4204 }
4205 else if( boundtype == SCIP_BOUNDTYPE_UPPER && SCIPsetIsLT(set, val, SCIPvarGetUbLocal(var))
4206 && SCIPsetIsFeasGE(set, val, SCIPvarGetLbLocal(var)) )
4207 {
4208 SCIPvarAdjustUb(var, set, &val);
4209 SCIP_CALL( SCIPnodeAddBoundchg(node, blkmem, set, stat, transprob, origprob,
4210 tree, reopt, lp, branchcand, eventqueue, cliquetable, var, val, SCIP_BOUNDTYPE_UPPER, FALSE) );
4211 }
4212 else if( boundtype != SCIP_BOUNDTYPE_LOWER && boundtype != SCIP_BOUNDTYPE_UPPER )
4213 {
4214 SCIPerrorMessage("** Unknown boundtype: %d **\n", boundtype);
4215 return SCIP_INVALIDDATA;
4216 }
4217#ifdef SCIP_MORE_DEBUG
4218 SCIPsetDebugMsg(set, " (dual) <%s> %s %g\n", SCIPvarGetName(var), boundtype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", val);
4219#endif
4220 }
4221
4222 return SCIP_OKAY;
4223}
4224
4225/** add all constraints stored at @p id to the given nodes @p node_fix and @p node_cons */
4226static
4228 SCIP* scip, /**< SCIP data structure */
4229 SCIP_REOPT* reopt, /**< reoptimization data structure */
4230 SCIP_SET* set, /**< global SCIP settings */
4231 SCIP_STAT* stat, /**< dynamic problem statistics */
4232 BMS_BLKMEM* blkmem, /**< block memory */
4233 SCIP_NODE* node, /**< node of the branch and bound tree*/
4234 unsigned int id /**< id of stored node */
4235 )
4236{
4237 char name[SCIP_MAXSTRLEN];
4238
4239 assert(scip != NULL);
4240 assert(reopt != NULL);
4241 assert(reopt->reopttree != NULL);
4242 assert(set != NULL);
4243 assert(stat != NULL);
4244 assert(blkmem != NULL);
4245 assert(node != NULL);
4246 assert(0 < id && id < reopt->reopttree->reoptnodessize);
4247
4248 if( reopt->reopttree->reoptnodes[id]->nconss == 0 )
4249 return SCIP_OKAY;
4250
4251 SCIPsetDebugMsg(set, " -> add %d constraint(s) to node #%lld:\n", reopt->reopttree->reoptnodes[id]->nconss,
4252 SCIPnodeGetNumber(node));
4253
4254 for( int c = 0; c < reopt->reopttree->reoptnodes[id]->nconss; ++c )
4255 {
4256 SCIP_CONS* cons;
4257 SCIP_REOPTCONSDATA* reoptconsdata;
4258
4259 reoptconsdata = reopt->reopttree->reoptnodes[id]->conss[c];
4260 assert(reoptconsdata != NULL);
4261 assert(reoptconsdata->nvars > 0);
4262 assert(reoptconsdata->varssize >= reoptconsdata->nvars);
4263
4264 if( reoptconsdata->constype == REOPT_CONSTYPE_CUT )
4265 continue;
4266
4267 if( reoptconsdata->constype == REOPT_CONSTYPE_INFSUBTREE )
4268 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "reopt_inf");
4269 else if( reoptconsdata->constype == REOPT_CONSTYPE_DUALREDS )
4270 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "reopt_dual");
4271 else
4272 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "reopt_unkn");
4273
4274 if( reoptconsdata->linear )
4275 {
4276 SCIP_CALL( SCIPcreateConsLinear(scip, &cons, name, reoptconsdata->nvars, reoptconsdata->vars, reoptconsdata->vals,
4277 reoptconsdata->lhs, reoptconsdata->rhs, FALSE, FALSE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, TRUE) );
4278 }
4279 else
4280 {
4281 assert(reoptconsdata->boundtypes != NULL);
4282 SCIP_CALL( SCIPcreateConsBounddisjunctionRedundant(scip, &cons, name, reoptconsdata->nvars, reoptconsdata->vars, reoptconsdata->boundtypes,
4283 reoptconsdata->vals, FALSE, FALSE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, TRUE) );
4284 }
4285#ifdef SCIP_DEBUG_CONSS
4287#endif
4288 SCIP_CALL( SCIPaddConsNode(scip, node, cons, NULL) );
4289 SCIP_CALL( SCIPreleaseCons(scip, &cons) );
4290 }
4291
4292 return SCIP_OKAY;
4293}
4294
4295/** reset the internal statistics at the beginning of a new iteration */
4296static
4298 SCIP_REOPT* reopt /**< reoptimization data structure */
4299 )
4300{
4301 assert(reopt != NULL);
4302
4303 reopt->lastbranched = -1;
4304 reopt->currentnode = -1;
4305 reopt->lastseennode = -1;
4306 reopt->reopttree->nfeasnodes = 0;
4307 reopt->reopttree->ninfnodes = 0;
4308 reopt->reopttree->nprunednodes = 0;
4309 reopt->reopttree->ncutoffreoptnodes = 0;
4310
4311 if( reopt->dualreds != NULL )
4312 reopt->dualreds->nvars = 0;
4313}
4314
4315/** check the stored bound changes of all child nodes for redundancy and infeasibility
4316 *
4317 * Due to strongbranching initialization at node stored at @p id it can happen, that some bound changes stored in the
4318 * child nodes of the reoptimization node stored at @p id become redundant or make the subproblem infeasible. in this
4319 * method we remove all redundant bound changes and delete infeasible child nodes.
4320 */
4321static
4323 SCIP_REOPT* reopt, /**< reoptimization data structure */
4324 SCIP_SET* set, /**< global SCIP settings */
4325 BMS_BLKMEM* blkmem, /**< block memory */
4326 SCIP_Bool* runagain, /**< pointer to store of this method should run again */
4327 unsigned int id /**< id of stored node */
4328 )
4329{
4330 SCIP_REOPTNODE* reoptnode;
4331 unsigned int* cutoffchilds;
4332 int ncutoffchilds = 0;
4333 unsigned int* redchilds;
4334 int nredchilds = 0;
4335 int c;
4336
4337 assert(reopt != NULL);
4338 assert(reopt->reopttree != NULL);
4339 assert(id < reopt->reopttree->reoptnodessize);
4340 assert(reopt->reopttree->reoptnodes != NULL);
4341 assert(reopt->reopttree->reoptnodes[id] != NULL);
4342
4343 reoptnode = reopt->reopttree->reoptnodes[id];
4344
4345 *runagain = FALSE;
4346
4347 SCIPsetDebugMsg(set, "start dry branching of node at ID %u\n", id);
4348
4349 /* allocate buffer arrays */
4350 SCIP_CALL( SCIPsetAllocBufferArray(set, &cutoffchilds, reoptnode->nchilds) );
4351 SCIP_CALL( SCIPsetAllocBufferArray(set, &redchilds, reoptnode->nchilds) );
4352
4353 /* iterate over all child nodes and check each bound changes
4354 * for redundancy and conflict */
4355 for( c = 0; c < reoptnode->nchilds; ++c )
4356 {
4357 SCIP_REOPTNODE* child;
4358 SCIP_Bool cutoff;
4359 SCIP_Bool redundant;
4360 int* redundantvars;
4361 int nredundantvars;
4362 unsigned int childid;
4363
4364 cutoff = FALSE;
4365 redundant = FALSE;
4366 nredundantvars = 0;
4367
4368 childid = reoptnode->childids[c];
4369 assert(childid < reopt->reopttree->reoptnodessize);
4370 child = reopt->reopttree->reoptnodes[childid];
4371 assert(child != NULL);
4372#ifdef SCIP_MORE_DEBUG
4373 SCIPsetDebugMsg(set, "-> check child at ID %d (%d vars, %d conss):\n", childid, child->nvars, child->nconss);
4374#endif
4375 if( child->nvars > 0 )
4376 {
4377 /* allocate buffer memory to store the redundant variables */
4378 SCIP_CALL( SCIPsetAllocBufferArray(set, &redundantvars, child->nvars) );
4379
4380 for( int v = 0; v < child->nvars && !cutoff; ++v )
4381 {
4382 SCIP_VAR* transvar;
4383 SCIP_Real transval;
4384 SCIP_BOUNDTYPE transbndtype;
4385 SCIP_Real ub;
4386 SCIP_Real lb;
4387
4388 transvar = child->vars[v];
4389 transval = child->varbounds[v];
4390 transbndtype = child->varboundtypes[v];
4391
4392 /* transform into the transformed space */
4393 SCIP_CALL( SCIPvarGetProbvarBound(&transvar, &transval, &transbndtype) );
4394
4395 lb = SCIPvarGetLbLocal(transvar);
4396 ub = SCIPvarGetUbLocal(transvar);
4397
4398 /* check for infeasibility */
4399 if( SCIPsetIsFeasEQ(set, lb, ub) && !SCIPsetIsFeasEQ(set, lb, transval) )
4400 {
4401 SCIPsetDebugMsg(set, " -> <%s> is fixed to %g, can not change bound to %g -> cutoff\n",
4402 SCIPvarGetName(transvar), lb, transval);
4403
4404 cutoff = TRUE;
4405 break;
4406 }
4407
4408 /* check for redundancy */
4409 if( SCIPsetIsFeasEQ(set, lb, ub) && SCIPsetIsFeasEQ(set, lb, transval) )
4410 {
4411 SCIPsetDebugMsg(set, " -> <%s> is already fixed to %g -> redundant bound change\n",
4412 SCIPvarGetName(transvar), lb);
4413
4414 redundantvars[nredundantvars] = v;
4415 ++nredundantvars;
4416 }
4417 }
4418
4419 if( !cutoff && nredundantvars > 0 )
4420 {
4421 for( int v = 0; v < nredundantvars; ++v )
4422 {
4423 /* replace the redundant variable by the last stored variable */
4424 child->vars[redundantvars[v]] = child->vars[child->nvars-1];
4425 child->varbounds[redundantvars[v]] = child->varbounds[child->nvars-1];
4426 child->varboundtypes[redundantvars[v]] = child->varboundtypes[child->nvars-1];
4427 --child->nvars;
4428 }
4429 }
4430
4431 /* free buffer memory */
4432 SCIPsetFreeBufferArray(set, &redundantvars);
4433 }
4434 else if( child->nconss == 0 )
4435 {
4436 redundant = TRUE;
4437 SCIPsetDebugMsg(set, " -> redundant node found.\n");
4438 }
4439
4440 if( cutoff )
4441 {
4442 cutoffchilds[ncutoffchilds] = childid;
4443 ++ncutoffchilds;
4444 }
4445 else if( redundant )
4446 {
4447 redchilds[nredchilds] = childid;
4448 ++nredchilds;
4449 }
4450 }
4451
4452 SCIPsetDebugMsg(set, "-> found %d redundant and %d infeasible nodes\n", nredchilds, ncutoffchilds);
4453
4454 /* delete all nodes that can be cut off */
4455 while( ncutoffchilds > 0 )
4456 {
4457 /* delete the node and the induced subtree */
4458 SCIP_CALL( deleteChildrenBelow(reopt->reopttree, set, blkmem, cutoffchilds[ncutoffchilds-1], TRUE, TRUE) );
4459
4460 /* find the position in the childid array */
4461 c = 0;
4462 while( reoptnode->childids[c] != cutoffchilds[ncutoffchilds-1] && c < reoptnode->nchilds )
4463 ++c;
4464 assert(reoptnode->childids[c] == cutoffchilds[ncutoffchilds-1]);
4465
4466 /* replace the ID at position c by the last ID */
4467 reoptnode->childids[c] = reoptnode->childids[reoptnode->nchilds-1];
4468 --reoptnode->nchilds;
4469
4470 /* decrease the number of nodes to cutoff */
4471 --ncutoffchilds;
4472 }
4473
4474 /* replace all redundant nodes their child nodes or cutoff the node if it is a leaf */
4475 while( nredchilds > 0 )
4476 {
4477 /* find the position in the childid array */
4478 c = 0;
4479 while( reoptnode->childids[c] != redchilds[nredchilds-1] && c < reoptnode->nchilds )
4480 ++c;
4481 assert(reoptnode->childids[c] == redchilds[nredchilds-1]);
4482
4483 /* the node is a leaf and we can cutoff them */
4484 if( reopt->reopttree->reoptnodes[redchilds[nredchilds-1]]->nchilds == 0 )
4485 {
4486 /* delete the node and the induced subtree */
4487 SCIP_CALL( deleteChildrenBelow(reopt->reopttree, set, blkmem, redchilds[nredchilds-1], TRUE, TRUE) );
4488
4489 /* replace the ID at position c by the last ID */
4490 reoptnode->childids[c] = reoptnode->childids[reoptnode->nchilds-1];
4491 --reoptnode->nchilds;
4492
4493 /* decrease the number of redundant nodes */
4494 --nredchilds;
4495 }
4496 else
4497 {
4498 int ncc;
4499
4500 /* replace the ID at position c by the last ID */
4501 reoptnode->childids[c] = reoptnode->childids[reoptnode->nchilds-1];
4502 --reoptnode->nchilds;
4503
4504 ncc = reopt->reopttree->reoptnodes[redchilds[nredchilds-1]]->nchilds;
4505
4506 /* check the memory */
4507 SCIP_CALL( reoptnodeCheckMemory(reopt->reopttree->reoptnodes[id], set, blkmem, 0, reoptnode->nchilds+ncc, 0) );
4508
4509 /* add all IDs of child nodes to the current node */
4510 for( int cc = 0; cc < ncc; ++cc )
4511 {
4512 reoptnode->childids[reoptnode->nchilds] = reopt->reopttree->reoptnodes[redchilds[nredchilds-1]]->childids[cc];
4513 ++reoptnode->nchilds;
4514 }
4515
4516 /* delete the redundant node */
4517 SCIP_CALL( reopttreeDeleteNode(reopt->reopttree, set, blkmem, redchilds[nredchilds-1], TRUE) );
4518 SCIP_CALL( SCIPqueueInsertUInt(reopt->reopttree->openids, redchilds[nredchilds-1]) );
4519
4520 /* decrease the number of redundant nodes */
4521 --nredchilds;
4522
4523 /* update the flag to rerun this method */
4524 *runagain = TRUE;
4525 }
4526 }
4527
4528 /* free buffer arrays */
4529 SCIPsetFreeBufferArray(set, &redchilds);
4530 SCIPsetFreeBufferArray(set, &cutoffchilds);
4531
4532 return SCIP_OKAY;
4533}
4534
4535/** return the number of all nodes in the subtree induced by the reoptimization node stored at @p id */
4536static
4538 SCIP_REOPTTREE* reopttree, /**< reopttree */
4539 unsigned int id /**< id of stored node */
4540 )
4541{
4542 int nnodes = 0;
4543
4544 assert(reopttree != NULL);
4545 assert(id < reopttree->reoptnodessize);
4546
4547 for( int i = 0; i < reopttree->reoptnodes[id]->nchilds; ++i )
4548 nnodes += reopttreeGetNNodes(reopttree, reopttree->reoptnodes[id]->childids[i]);
4549
4550 return nnodes + 1;
4551}
4552
4553/** returns the number of leaf nodes of the induced subtree */
4554static
4556 SCIP_REOPT* reopt, /**< reoptimization data structure */
4557 unsigned int id /**< id of stored node */
4558 )
4559{
4560 int nleaves = 0;
4561
4562 assert(reopt != NULL);
4563 assert(id < reopt->reopttree->reoptnodessize);
4564 assert(reopt->reopttree->reoptnodes[id] != NULL);
4565
4566 /* iterate over all child nods and check whether they are leaves or not */
4567 for( int i = 0; i < reopt->reopttree->reoptnodes[id]->nchilds; ++i )
4568 {
4569 unsigned int childid;
4570
4571 childid = reopt->reopttree->reoptnodes[id]->childids[i];
4572 assert(childid < reopt->reopttree->reoptnodessize);
4573
4574 if( reopt->reopttree->reoptnodes[childid]->nchilds == 0 )
4575 ++nleaves;
4576 else
4577 nleaves += reoptGetNLeaves(reopt, childid);
4578 }
4579
4580 return nleaves;
4581}
4582
4583/** returns all leaves of the subtree induced by the node stored at @p id*/
4584static
4586 SCIP_REOPT* reopt, /**< reoptimization data structure*/
4587 unsigned int id, /**< id of stored node */
4588 unsigned int* leaves, /**< array of leave nodes */
4589 int leavessize, /**< size of leaves array */
4590 int* nleaves /**< pointer to store the number of leave nodes */
4591 )
4592{
4593 assert(reopt != NULL);
4594 assert(leavessize > 0 && leaves != NULL);
4595 assert((*nleaves) >= 0);
4596 assert(id < reopt->reopttree->reoptnodessize);
4597 assert(reopt->reopttree->reoptnodes[id] != NULL);
4598
4599 for( int i = 0, l = 0; i < reopt->reopttree->reoptnodes[id]->nchilds; ++i )
4600 {
4601 unsigned int childid;
4602
4603 assert(*nleaves <= leavessize);
4604
4605 childid = reopt->reopttree->reoptnodes[id]->childids[i];
4606 assert(childid < reopt->reopttree->reoptnodessize);
4607
4608 if( reopt->reopttree->reoptnodes[childid]->nchilds == 0 )
4609 {
4610 leaves[l] = reopt->reopttree->reoptnodes[id]->childids[i];
4611 ++l;
4612 ++(*nleaves);
4613 }
4614 else
4615 {
4616 int nleaves2 = 0;
4617
4618 SCIP_CALL( reoptGetLeaves(reopt, childid, &leaves[l], leavessize - l, &nleaves2) );
4619 l += nleaves2;
4620 (*nleaves) += nleaves2;
4621 }
4622 }
4623
4624 return SCIP_OKAY;
4625}
4626
4627/** after restarting the reoptimization and an after compressing the search tree we have to delete all stored information */
4628static
4630 SCIP_REOPT* reopt, /**< reoptimization data structure */
4631 SCIP_SET* set, /**< global SCIP settings */
4632 BMS_BLKMEM* blkmem, /**< block memory */
4633 SCIP_Bool softreset /**< mark the nodes to overwriteable (TRUE) or delete them completely (FALSE) */
4634 )
4635{
4636 assert(reopt != NULL);
4637 assert(set != NULL);
4638 assert(blkmem != NULL);
4639
4640 /* clear the tree */
4641 SCIP_CALL( clearReoptnodes(reopt->reopttree, set, blkmem, softreset) );
4642 assert(reopt->reopttree->nreoptnodes == 0);
4643
4644 /* reset the dual constraint */
4645 if( reopt->dualreds != NULL )
4646 reopt->dualreds->nvars = 0;
4647
4648 reopt->currentnode = -1;
4649
4650 return SCIP_OKAY;
4651}
4652
4653/** restart the reoptimization by removing all stored information about nodes and increase the number of restarts */
4654static
4656 SCIP_REOPT* reopt, /**< reoptimization data structure */
4657 SCIP_SET* set, /**< global SCIP settings */
4658 BMS_BLKMEM* blkmem /**< block memory */
4659 )
4660{
4661 assert(reopt != NULL);
4662 assert(reopt->reopttree != NULL);
4663 assert(set != NULL);
4664 assert(blkmem != NULL);
4665
4666 /* clear the tree */
4667 SCIP_CALL( reoptResetTree(reopt, set, blkmem, FALSE)