Scippy

SCIP

Solving Constraint Integer Programs

var.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 var.c
26 * @ingroup OTHER_CFILES
27 * @brief methods for problem variables
28 * @author Tobias Achterberg
29 * @author Timo Berthold
30 * @author Gerald Gamrath
31 * @author Stefan Heinz
32 * @author Marc Pfetsch
33 * @author Michael Winkler
34 * @author Kati Wolter
35 * @author Stefan Vigerske
36 *
37 * @todo Possibly implement the access of bounds of multi-aggregated variables by accessing the
38 * corresponding linear constraint if it exists. This seems to require some work, since the linear
39 * constraint has to be stored. Moreover, it has even to be created in case the original constraint
40 * was deleted after multi-aggregation, but the bounds of the multi-aggregated variable should be
41 * changed. This has to be done with care in order to not loose the performance gains of
42 * multi-aggregation.
43 */
44
45/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
46
47#include "scip/cons.h"
48#include "scip/event.h"
49#include "scip/history.h"
50#include "scip/implics.h"
51#include "scip/lp.h"
52#include "scip/primal.h"
53#include "scip/prob.h"
54#include "scip/pub_cons.h"
55#include "scip/pub_history.h"
56#include "scip/pub_implics.h"
57#include "scip/pub_lp.h"
58#include "scip/pub_message.h"
59#include "scip/pub_misc.h"
60#include "scip/pub_misc_sort.h"
61#include "scip/pub_prop.h"
62#include "scip/pub_var.h"
63#include "scip/relax.h"
64#include "scip/set.h"
65#include "scip/sol.h"
66#include "scip/stat.h"
67#include "scip/struct_event.h"
68#include "scip/struct_lp.h"
69#include "scip/struct_prob.h"
70#include "scip/struct_set.h"
71#include "scip/struct_stat.h"
72#include "scip/struct_var.h"
73#include "scip/tree.h"
74#include "scip/var.h"
75#include <string.h>
76
77#define MAXIMPLSCLOSURE 100 /**< maximal number of descendants of implied variable for building closure
78 * in implication graph */
79#define MAXABSVBCOEF 1e+5 /**< maximal absolute coefficient in variable bounds added due to implications */
80
81
82/*
83 * Debugging variable release and capture
84 *
85 * Define DEBUGUSES_VARNAME to the name of the variable for which to print
86 * a backtrace when it is captured and released.
87 * Optionally define DEBUGUSES_PROBNAME to the name of a SCIP problem to consider.
88 * Have DEBUGUSES_NOADDR2LINE defined if you do not have addr2line installed on your system.
89 */
90/* #define DEBUGUSES_VARNAME "t_t_b7" */
91/* #define DEBUGUSES_PROBNAME "t_st_e35_rens" */
92/* #define DEBUGUSES_NOADDR2LINE */
93
94#ifdef DEBUGUSES_VARNAME
95#include <execinfo.h>
96#include <stdio.h>
97#include <stdlib.h>
98#include "scip/struct_scip.h"
99
100/** obtains a backtrace and prints it to stdout. */
101static
102void print_backtrace(void)
103{
104 void* array[10];
105 char** strings;
106 int size;
107 int i;
108
109 size = backtrace(array, 10);
110 strings = backtrace_symbols(array, size);
111 if( strings == NULL )
112 return;
113
114 /* skip first entry, which is the print_backtrace function */
115 for( i = 1; i < size; ++i )
116 {
117 /* if string is something like
118 * /path/to/scip/bin/../lib/shared/libscip-7.0.1.3.linux.x86_64.gnu.dbg.so(+0x2675dd3)
119 * (that is, no function name because it is a inlined function), then call
120 * addr2line -e <libname> <addr> to get func and code line
121 * dladdr() may be an alternative
122 */
123 char* openpar;
124 char* closepar = NULL;
125#ifndef DEBUGUSES_NOADDR2LINE
126 openpar = strchr(strings[i], '(');
127 if( openpar != NULL && openpar[1] == '+' )
128 closepar = strchr(openpar+2, ')');
129#endif
130 if( closepar != NULL )
131 {
132 char cmd[SCIP_MAXSTRLEN];
133 (void) SCIPsnprintf(cmd, SCIP_MAXSTRLEN, "addr2line -f -p -e \"%.*s\" %.*s", openpar - strings[i], strings[i], closepar-openpar-1, openpar+1);
134 printf(" ");
135 fflush(stdout);
136 system(cmd);
137 }
138 else
139 printf(" %s\n", strings[i]);
140 }
141
142 free(strings);
143}
144#endif
145
146/*
147 * hole, holelist, and domain methods
148 */
149
150/** creates a new holelist element */
151static
153 SCIP_HOLELIST** holelist, /**< pointer to holelist to create */
154 BMS_BLKMEM* blkmem, /**< block memory for target holelist */
155 SCIP_SET* set, /**< global SCIP settings */
156 SCIP_Real left, /**< left bound of open interval in new hole */
157 SCIP_Real right /**< right bound of open interval in new hole */
158 )
159{
160 assert(holelist != NULL);
161 assert(blkmem != NULL);
162 assert(SCIPsetIsLT(set, left, right));
163
164 SCIPsetDebugMsg(set, "create hole list element (%.15g,%.15g) in blkmem %p\n", left, right, (void*)blkmem);
165
166 SCIP_ALLOC( BMSallocBlockMemory(blkmem, holelist) );
167 (*holelist)->hole.left = left;
168 (*holelist)->hole.right = right;
169 (*holelist)->next = NULL;
170
171 return SCIP_OKAY;
172}
173
174/** frees all elements in the holelist */
175static
177 SCIP_HOLELIST** holelist, /**< pointer to holelist to free */
178 BMS_BLKMEM* blkmem /**< block memory for target holelist */
179 )
180{
181 assert(holelist != NULL);
182 assert(blkmem != NULL);
183
184 while( *holelist != NULL )
185 {
186 SCIP_HOLELIST* next;
187
188 SCIPdebugMessage("free hole list element (%.15g,%.15g) in blkmem %p\n",
189 (*holelist)->hole.left, (*holelist)->hole.right, (void*)blkmem);
190
191 next = (*holelist)->next;
192 BMSfreeBlockMemory(blkmem, holelist);
193 assert(*holelist == NULL);
194
195 *holelist = next;
196 }
197 assert(*holelist == NULL);
198}
199
200/** duplicates a list of holes */
201static
203 SCIP_HOLELIST** target, /**< pointer to target holelist */
204 BMS_BLKMEM* blkmem, /**< block memory for target holelist */
205 SCIP_SET* set, /**< global SCIP settings */
206 SCIP_HOLELIST* source /**< holelist to duplicate */
207 )
208{
209 assert(target != NULL);
210
211 while( source != NULL )
212 {
213 assert(source->next == NULL || SCIPsetIsGE(set, source->next->hole.left, source->hole.right));
214 SCIP_CALL( holelistCreate(target, blkmem, set, source->hole.left, source->hole.right) );
215 source = source->next;
216 target = &(*target)->next;
217 }
218
219 return SCIP_OKAY;
220}
221
222/** adds a hole to the domain */
223static
225 SCIP_DOM* dom, /**< domain to add hole to */
226 BMS_BLKMEM* blkmem, /**< block memory */
227 SCIP_SET* set, /**< global SCIP settings */
228 SCIP_Real left, /**< left bound of open interval in new hole */
229 SCIP_Real right, /**< right bound of open interval in new hole */
230 SCIP_Bool* added /**< pointer to store whether the hole was added (variable didn't had that hole before), or NULL */
231 )
232{
233 SCIP_HOLELIST** insertpos;
234 SCIP_HOLELIST* next;
235
236 assert(dom != NULL);
237 assert(added != NULL);
238
239 /* search for the position of the new hole */
240 insertpos = &dom->holelist;
241 while( *insertpos != NULL && (*insertpos)->hole.left < left )
242 insertpos = &(*insertpos)->next;
243
244 /* check if new hole already exists in the hole list or is a sub hole of an existing one */
245 if( *insertpos != NULL && (*insertpos)->hole.left == left && (*insertpos)->hole.right >= right ) /*lint !e777 */
246 {
247 SCIPsetDebugMsg(set, "new hole (%.15g,%.15g) is redundant through known hole (%.15g,%.15g)\n",
248 left, right, (*insertpos)->hole.left, (*insertpos)->hole.right);
249 *added = FALSE;
250 return SCIP_OKAY;
251 }
252
253 /* add hole */
254 *added = TRUE;
255
256 next = *insertpos;
257 SCIP_CALL( holelistCreate(insertpos, blkmem, set, left, right) );
258 (*insertpos)->next = next;
259
260 return SCIP_OKAY;
261}
262
263/** merges overlapping holes into single holes, computes and moves lower and upper bound, respectively */
264/**@todo the domMerge() method is currently called if a lower or an upper bound locally or globally changed; this could
265 * be more efficient if performed with the knowledge if it was a lower or an upper bound which triggered this
266 * merge */
267static
269 SCIP_DOM* dom, /**< domain to merge */
270 BMS_BLKMEM* blkmem, /**< block memory */
271 SCIP_SET* set, /**< global SCIP settings */
272 SCIP_Real* newlb, /**< pointer to store new lower bound */
273 SCIP_Real* newub /**< pointer to store new upper bound */
274 )
275{
276 SCIP_HOLELIST** holelistptr;
277 SCIP_HOLELIST** lastnextptr;
278 SCIP_Real* lastrightptr;
279
280 assert(dom != NULL);
281 assert(SCIPsetIsLE(set, dom->lb, dom->ub));
282
283#ifndef NDEBUG
284 {
285 /* check if the holelist is sorted w.r.t. to the left interval bounds */
286 SCIP_Real lastleft;
287
288 holelistptr = &dom->holelist;
289
290 lastleft = -SCIPsetInfinity(set);
291
292 while( *holelistptr != NULL )
293 {
294 if( (*holelistptr)->next != NULL )
295 {
296 assert( SCIPsetIsLE(set, lastleft, (*holelistptr)->hole.left) );
297 lastleft = (*holelistptr)->hole.left;
298 }
299
300 holelistptr = &(*holelistptr)->next;
301 }
302 }
303#endif
304
305 SCIPsetDebugMsg(set, "merge hole list\n");
306
307 holelistptr = &dom->holelist;
308 lastrightptr = &dom->lb; /* lower bound is the right bound of the hole (-infinity,lb) */
309 lastnextptr = holelistptr;
310
311 while( *holelistptr != NULL )
312 {
313 SCIPsetDebugMsg(set, "check hole (%.15g,%.15g) last right interval was <%.15g>\n", (*holelistptr)->hole.left, (*holelistptr)->hole.right, *lastrightptr);
314
315 /* check that the hole is not empty */
316 assert(SCIPsetIsLT(set, (*holelistptr)->hole.left, (*holelistptr)->hole.right));
317
318 if( SCIPsetIsGE(set, (*holelistptr)->hole.left, dom->ub) )
319 {
320 /* the remaining holes start behind the upper bound: remove them */
321 SCIPsetDebugMsg(set, "remove remaining hole since upper bound <%.15g> is less then the left hand side of the current hole\n", dom->ub);
322 holelistFree(holelistptr, blkmem);
323 assert(*holelistptr == NULL);
324
325 /* unlink this hole from the previous hole */
326 *lastnextptr = NULL;
327 }
328 else if( SCIPsetIsGT(set, (*holelistptr)->hole.right, dom->ub) )
329 {
330 /* the hole overlaps the upper bound: decrease upper bound, remove this hole and all remaining holes */
331 SCIPsetDebugMsg(set, "upper bound <%.15g> lays in current hole; store new upper bound and remove this and all remaining holes\n", dom->ub);
332
333 assert(SCIPsetIsLT(set, (*holelistptr)->hole.left, dom->ub));
334
335 /* adjust upper bound */
336 dom->ub = (*holelistptr)->hole.left;
337
338 if(newub != NULL )
339 *newub = (*holelistptr)->hole.left;
340
341 /* remove remaining hole list */
342 holelistFree(holelistptr, blkmem);
343 assert(*holelistptr == NULL);
344
345 /* unlink this hole from the previous hole */
346 *lastnextptr = NULL;
347 }
348 else if( SCIPsetIsGT(set, *lastrightptr, (*holelistptr)->hole.left) )
349 {
350 /* the right bound of the last hole is greater than the left bound of this hole: increase the right bound of
351 * the last hole, delete this hole */
352 SCIP_HOLELIST* nextholelist;
353
354 if( SCIPsetIsEQ(set, *lastrightptr, dom->lb ) )
355 {
356 /* the reason for the overlap results from the lower bound hole (-infinity,lb); therefore, we can increase
357 * the lower bound */
358 SCIPsetDebugMsg(set, "lower bound <%.15g> lays in current hole; store new lower bound and remove hole\n", dom->lb);
359 *lastrightptr = MAX(*lastrightptr, (*holelistptr)->hole.right);
360
361 /* adjust lower bound */
362 dom->lb = *lastrightptr;
363
364 if(newlb != NULL )
365 *newlb = *lastrightptr;
366 }
367 else
368 {
369 SCIPsetDebugMsg(set, "current hole overlaps with the previous one (...,%.15g); merge to (...,%.15g)\n",
370 *lastrightptr, MAX(*lastrightptr, (*holelistptr)->hole.right) );
371 *lastrightptr = MAX(*lastrightptr, (*holelistptr)->hole.right);
372 }
373 nextholelist = (*holelistptr)->next;
374 (*holelistptr)->next = NULL;
375 holelistFree(holelistptr, blkmem);
376
377 /* connect the linked list after removing the hole */
378 *lastnextptr = nextholelist;
379
380 /* get next hole */
381 *holelistptr = nextholelist;
382 }
383 else
384 {
385 /* the holes do not overlap: update lastholelist and lastrightptr */
386 lastrightptr = &(*holelistptr)->hole.right;
387 lastnextptr = &(*holelistptr)->next;
388
389 /* get next hole */
390 holelistptr = &(*holelistptr)->next;
391 }
392 }
393
394#ifndef NDEBUG
395 {
396 /* check that holes are merged */
397 SCIP_Real lastright;
398
399 lastright = dom->lb; /* lower bound is the right bound of the hole (-infinity,lb) */
400 holelistptr = &dom->holelist;
401
402 while( *holelistptr != NULL )
403 {
404 /* check the the last right interval is smaller or equal to the current left interval (none overlapping) */
405 assert( SCIPsetIsLE(set, lastright, (*holelistptr)->hole.left) );
406
407 /* check the hole property (check that the hole is not empty) */
408 assert( SCIPsetIsLT(set, (*holelistptr)->hole.left, (*holelistptr)->hole.right) );
409 lastright = (*holelistptr)->hole.right;
410
411 /* get next hole */
412 holelistptr = &(*holelistptr)->next;
413 }
414
415 /* check the the last right interval is smaller or equal to the upper bound (none overlapping) */
416 assert( SCIPsetIsLE(set, lastright, dom->ub) );
417 }
418#endif
419}
420
421/*
422 * domain change methods
423 */
424
425/** ensures, that bound change info array for lower bound changes can store at least num entries */
426static
428 SCIP_VAR* var, /**< problem variable */
429 BMS_BLKMEM* blkmem, /**< block memory */
430 SCIP_SET* set, /**< global SCIP settings */
431 int num /**< minimum number of entries to store */
432 )
433{
434 assert(var != NULL);
435 assert(var->nlbchginfos <= var->lbchginfossize);
436 assert(SCIPvarIsTransformed(var));
437
438 if( num > var->lbchginfossize )
439 {
440 int newsize;
441
442 newsize = SCIPsetCalcMemGrowSize(set, num);
443 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &var->lbchginfos, var->lbchginfossize, newsize) );
444 var->lbchginfossize = newsize;
445 }
446 assert(num <= var->lbchginfossize);
447
448 return SCIP_OKAY;
449}
450
451/** ensures, that bound change info array for upper bound changes can store at least num entries */
452static
454 SCIP_VAR* var, /**< problem variable */
455 BMS_BLKMEM* blkmem, /**< block memory */
456 SCIP_SET* set, /**< global SCIP settings */
457 int num /**< minimum number of entries to store */
458 )
459{
460 assert(var != NULL);
461 assert(var->nubchginfos <= var->ubchginfossize);
462 assert(SCIPvarIsTransformed(var));
463
464 if( num > var->ubchginfossize )
465 {
466 int newsize;
467
468 newsize = SCIPsetCalcMemGrowSize(set, num);
469 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &var->ubchginfos, var->ubchginfossize, newsize) );
470 var->ubchginfossize = newsize;
471 }
472 assert(num <= var->ubchginfossize);
473
474 return SCIP_OKAY;
475}
476
477/** adds domain change info to the variable's lower bound change info array */
478static
480 SCIP_VAR* var, /**< problem variable */
481 BMS_BLKMEM* blkmem, /**< block memory */
482 SCIP_SET* set, /**< global SCIP settings */
483 SCIP_Real oldbound, /**< old value for bound */
484 SCIP_Real newbound, /**< new value for bound */
485 int depth, /**< depth in the tree, where the bound change takes place */
486 int pos, /**< position of the bound change in its bound change array */
487 SCIP_VAR* infervar, /**< variable that was changed (parent of var, or var itself) */
488 SCIP_CONS* infercons, /**< constraint that inferred this bound change, or NULL */
489 SCIP_PROP* inferprop, /**< propagator that deduced the bound change, or NULL */
490 int inferinfo, /**< user information for inference to help resolving the conflict */
491 SCIP_BOUNDTYPE inferboundtype, /**< type of bound for inference var: lower or upper bound */
492 SCIP_BOUNDCHGTYPE boundchgtype /**< bound change type: branching decision or inferred bound change */
493 )
494{
495 assert(var != NULL);
496 assert(SCIPsetIsLT(set, oldbound, newbound));
499 assert(!SCIPvarIsBinary(var) || SCIPsetIsEQ(set, oldbound, 0.0));
500 assert(!SCIPvarIsBinary(var) || SCIPsetIsEQ(set, newbound, 1.0));
501 assert(boundchgtype == SCIP_BOUNDCHGTYPE_BRANCHING || infervar != NULL);
502 assert((boundchgtype == SCIP_BOUNDCHGTYPE_CONSINFER) == (infercons != NULL));
503 assert(boundchgtype == SCIP_BOUNDCHGTYPE_PROPINFER || inferprop == NULL);
504
505 SCIPsetDebugMsg(set, "adding lower bound change info to var <%s>[%g,%g]: depth=%d, pos=%d, infer%s=<%s>, inferinfo=%d, %g -> %g\n",
506 SCIPvarGetName(var), var->locdom.lb, var->locdom.ub, depth, pos, infercons != NULL ? "cons" : "prop",
507 infercons != NULL ? SCIPconsGetName(infercons) : (inferprop != NULL ? SCIPpropGetName(inferprop) : "-"), inferinfo,
508 oldbound, newbound);
509
510 SCIP_CALL( varEnsureLbchginfosSize(var, blkmem, set, var->nlbchginfos+1) );
511 var->lbchginfos[var->nlbchginfos].oldbound = oldbound;
512 var->lbchginfos[var->nlbchginfos].newbound = newbound;
513 var->lbchginfos[var->nlbchginfos].var = var;
514 var->lbchginfos[var->nlbchginfos].bdchgidx.depth = depth;
515 var->lbchginfos[var->nlbchginfos].bdchgidx.pos = pos;
516 var->lbchginfos[var->nlbchginfos].pos = var->nlbchginfos; /*lint !e732*/
517 var->lbchginfos[var->nlbchginfos].boundchgtype = boundchgtype; /*lint !e641*/
518 var->lbchginfos[var->nlbchginfos].boundtype = SCIP_BOUNDTYPE_LOWER; /*lint !e641*/
520 var->lbchginfos[var->nlbchginfos].inferboundtype = inferboundtype; /*lint !e641*/
521 var->lbchginfos[var->nlbchginfos].inferencedata.var = infervar;
522 var->lbchginfos[var->nlbchginfos].inferencedata.info = inferinfo;
523
524 /**@note The "pos" data member of the bound change info has a size of 27 bits */
525 assert(var->nlbchginfos < 1 << 27);
526
527 switch( boundchgtype )
528 {
530 break;
532 assert(infercons != NULL);
533 var->lbchginfos[var->nlbchginfos].inferencedata.reason.cons = infercons;
534 break;
536 var->lbchginfos[var->nlbchginfos].inferencedata.reason.prop = inferprop;
537 break;
538 default:
539 SCIPerrorMessage("invalid bound change type %d\n", boundchgtype);
540 return SCIP_INVALIDDATA;
541 }
542
543 var->nlbchginfos++;
544
545 assert(var->nlbchginfos < 2
547 &var->lbchginfos[var->nlbchginfos-1].bdchgidx));
548
549 return SCIP_OKAY;
550}
551
552/** adds domain change info to the variable's upper bound change info array */
553static
555 SCIP_VAR* var, /**< problem variable */
556 BMS_BLKMEM* blkmem, /**< block memory */
557 SCIP_SET* set, /**< global SCIP settings */
558 SCIP_Real oldbound, /**< old value for bound */
559 SCIP_Real newbound, /**< new value for bound */
560 int depth, /**< depth in the tree, where the bound change takes place */
561 int pos, /**< position of the bound change in its bound change array */
562 SCIP_VAR* infervar, /**< variable that was changed (parent of var, or var itself) */
563 SCIP_CONS* infercons, /**< constraint that inferred this bound change, or NULL */
564 SCIP_PROP* inferprop, /**< propagator that deduced the bound change, or NULL */
565 int inferinfo, /**< user information for inference to help resolving the conflict */
566 SCIP_BOUNDTYPE inferboundtype, /**< type of bound for inference var: lower or upper bound */
567 SCIP_BOUNDCHGTYPE boundchgtype /**< bound change type: branching decision or inferred bound change */
568 )
569{
570 assert(var != NULL);
571 assert(SCIPsetIsGT(set, oldbound, newbound));
574 assert(!SCIPvarIsBinary(var) || SCIPsetIsEQ(set, oldbound, 1.0));
575 assert(!SCIPvarIsBinary(var) || SCIPsetIsEQ(set, newbound, 0.0));
576 assert(boundchgtype == SCIP_BOUNDCHGTYPE_BRANCHING || infervar != NULL);
577 assert((boundchgtype == SCIP_BOUNDCHGTYPE_CONSINFER) == (infercons != NULL));
578 assert(boundchgtype == SCIP_BOUNDCHGTYPE_PROPINFER || inferprop == NULL);
579
580 SCIPsetDebugMsg(set, "adding upper bound change info to var <%s>[%g,%g]: depth=%d, pos=%d, infer%s=<%s>, inferinfo=%d, %g -> %g\n",
581 SCIPvarGetName(var), var->locdom.lb, var->locdom.ub, depth, pos, infercons != NULL ? "cons" : "prop",
582 infercons != NULL ? SCIPconsGetName(infercons) : (inferprop != NULL ? SCIPpropGetName(inferprop) : "-"), inferinfo,
583 oldbound, newbound);
584
585 SCIP_CALL( varEnsureUbchginfosSize(var, blkmem, set, var->nubchginfos+1) );
586 var->ubchginfos[var->nubchginfos].oldbound = oldbound;
587 var->ubchginfos[var->nubchginfos].newbound = newbound;
588 var->ubchginfos[var->nubchginfos].var = var;
589 var->ubchginfos[var->nubchginfos].bdchgidx.depth = depth;
590 var->ubchginfos[var->nubchginfos].bdchgidx.pos = pos;
591 var->ubchginfos[var->nubchginfos].pos = var->nubchginfos; /*lint !e732*/
592 var->ubchginfos[var->nubchginfos].boundchgtype = boundchgtype; /*lint !e641*/
593 var->ubchginfos[var->nubchginfos].boundtype = SCIP_BOUNDTYPE_UPPER; /*lint !e641*/
595 var->ubchginfos[var->nubchginfos].inferboundtype = inferboundtype; /*lint !e641*/
596 var->ubchginfos[var->nubchginfos].inferencedata.var = infervar;
597 var->ubchginfos[var->nubchginfos].inferencedata.info = inferinfo;
598
599 /**@note The "pos" data member of the bound change info has a size of 27 bits */
600 assert(var->nubchginfos < 1 << 27);
601
602 switch( boundchgtype )
603 {
605 break;
607 assert(infercons != NULL);
608 var->ubchginfos[var->nubchginfos].inferencedata.reason.cons = infercons;
609 break;
611 var->ubchginfos[var->nubchginfos].inferencedata.reason.prop = inferprop;
612 break;
613 default:
614 SCIPerrorMessage("invalid bound change type %d\n", boundchgtype);
615 return SCIP_INVALIDDATA;
616 }
617
618 var->nubchginfos++;
619
620 assert(var->nubchginfos < 2
622 &var->ubchginfos[var->nubchginfos-1].bdchgidx));
623
624 return SCIP_OKAY;
625}
626
627/** applies single bound change */
629 SCIP_BOUNDCHG* boundchg, /**< bound change to apply */
630 BMS_BLKMEM* blkmem, /**< block memory */
631 SCIP_SET* set, /**< global SCIP settings */
632 SCIP_STAT* stat, /**< problem statistics */
633 SCIP_LP* lp, /**< current LP data */
634 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
635 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
636 int depth, /**< depth in the tree, where the bound change takes place */
637 int pos, /**< position of the bound change in its bound change array */
638 SCIP_Bool* cutoff /**< pointer to store whether an infeasible bound change was detected */
639 )
640{
641 SCIP_VAR* var;
642
643 assert(boundchg != NULL);
644 assert(stat != NULL);
645 assert(depth > 0);
646 assert(pos >= 0);
647 assert(cutoff != NULL);
648
649 *cutoff = FALSE;
650
651 /* ignore redundant bound changes */
652 if( boundchg->redundant )
653 return SCIP_OKAY;
654
655 var = boundchg->var;
656 assert(var != NULL);
658 assert(!SCIPvarIsIntegral(var) || SCIPsetIsFeasIntegral(set, boundchg->newbound));
659
660 /* apply bound change */
661 switch( boundchg->boundtype )
662 {
664 /* check, if the bound change is still active (could be replaced by inference due to repropagation of higher node) */
665 if( SCIPsetIsGT(set, boundchg->newbound, var->locdom.lb) )
666 {
667 if( SCIPsetIsLE(set, boundchg->newbound, var->locdom.ub) )
668 {
669 /* add the bound change info to the variable's bound change info array */
670 switch( boundchg->boundchgtype )
671 {
673 SCIPsetDebugMsg(set, " -> branching: new lower bound of <%s>[%g,%g]: %g\n",
674 SCIPvarGetName(var), var->locdom.lb, var->locdom.ub, boundchg->newbound);
675 SCIP_CALL( varAddLbchginfo(var, blkmem, set, var->locdom.lb, boundchg->newbound, depth, pos,
677 stat->lastbranchvar = var;
679 stat->lastbranchvalue = boundchg->newbound;
680 break;
681
683 assert(boundchg->data.inferencedata.reason.cons != NULL);
684 SCIPsetDebugMsg(set, " -> constraint <%s> inference: new lower bound of <%s>[%g,%g]: %g\n",
685 SCIPconsGetName(boundchg->data.inferencedata.reason.cons),
686 SCIPvarGetName(var), var->locdom.lb, var->locdom.ub, boundchg->newbound);
687 SCIP_CALL( varAddLbchginfo(var, blkmem, set, var->locdom.lb, boundchg->newbound, depth, pos,
688 boundchg->data.inferencedata.var, boundchg->data.inferencedata.reason.cons, NULL,
689 boundchg->data.inferencedata.info,
691 break;
692
694 SCIPsetDebugMsg(set, " -> propagator <%s> inference: new lower bound of <%s>[%g,%g]: %g\n",
695 boundchg->data.inferencedata.reason.prop != NULL
696 ? SCIPpropGetName(boundchg->data.inferencedata.reason.prop) : "-",
697 SCIPvarGetName(var), var->locdom.lb, var->locdom.ub, boundchg->newbound);
698 SCIP_CALL( varAddLbchginfo(var, blkmem, set, var->locdom.lb, boundchg->newbound, depth, pos,
699 boundchg->data.inferencedata.var, NULL, boundchg->data.inferencedata.reason.prop,
700 boundchg->data.inferencedata.info,
702 break;
703
704 default:
705 SCIPerrorMessage("invalid bound change type %d\n", boundchg->boundchgtype);
706 return SCIP_INVALIDDATA;
707 }
708
709 /* change local bound of variable */
710 SCIP_CALL( SCIPvarChgLbLocal(var, blkmem, set, stat, lp, branchcand, eventqueue, boundchg->newbound) );
711 }
712 else
713 {
714 SCIPsetDebugMsg(set, " -> cutoff: new lower bound of <%s>[%g,%g]: %g\n",
715 SCIPvarGetName(var), var->locdom.lb, var->locdom.ub, boundchg->newbound);
716 *cutoff = TRUE;
717 boundchg->redundant = TRUE; /* bound change has not entered the lbchginfos array of the variable! */
718 }
719 }
720 else
721 {
722 /* mark bound change to be inactive */
723 SCIPsetDebugMsg(set, " -> inactive %s: new lower bound of <%s>[%g,%g]: %g\n",
724 (SCIP_BOUNDCHGTYPE)boundchg->boundchgtype == SCIP_BOUNDCHGTYPE_BRANCHING ? "branching" : "inference",
725 SCIPvarGetName(var), var->locdom.lb, var->locdom.ub, boundchg->newbound);
726 boundchg->redundant = TRUE;
727 }
728 break;
729
731 /* check, if the bound change is still active (could be replaced by inference due to repropagation of higher node) */
732 if( SCIPsetIsLT(set, boundchg->newbound, var->locdom.ub) )
733 {
734 if( SCIPsetIsGE(set, boundchg->newbound, var->locdom.lb) )
735 {
736 /* add the bound change info to the variable's bound change info array */
737 switch( boundchg->boundchgtype )
738 {
740 SCIPsetDebugMsg(set, " -> branching: new upper bound of <%s>[%g,%g]: %g\n",
741 SCIPvarGetName(var), var->locdom.lb, var->locdom.ub, boundchg->newbound);
742 SCIP_CALL( varAddUbchginfo(var, blkmem, set, var->locdom.ub, boundchg->newbound, depth, pos,
744 stat->lastbranchvar = var;
746 stat->lastbranchvalue = boundchg->newbound;
747 break;
748
750 assert(boundchg->data.inferencedata.reason.cons != NULL);
751 SCIPsetDebugMsg(set, " -> constraint <%s> inference: new upper bound of <%s>[%g,%g]: %g\n",
752 SCIPconsGetName(boundchg->data.inferencedata.reason.cons),
753 SCIPvarGetName(var), var->locdom.lb, var->locdom.ub, boundchg->newbound);
754 SCIP_CALL( varAddUbchginfo(var, blkmem, set, var->locdom.ub, boundchg->newbound, depth, pos,
755 boundchg->data.inferencedata.var, boundchg->data.inferencedata.reason.cons, NULL,
756 boundchg->data.inferencedata.info,
758 break;
759
761 SCIPsetDebugMsg(set, " -> propagator <%s> inference: new upper bound of <%s>[%g,%g]: %g\n",
762 boundchg->data.inferencedata.reason.prop != NULL
763 ? SCIPpropGetName(boundchg->data.inferencedata.reason.prop) : "-",
764 SCIPvarGetName(var), var->locdom.lb, var->locdom.ub, boundchg->newbound);
765 SCIP_CALL( varAddUbchginfo(var, blkmem, set, var->locdom.ub, boundchg->newbound, depth, pos,
766 boundchg->data.inferencedata.var, NULL, boundchg->data.inferencedata.reason.prop,
767 boundchg->data.inferencedata.info,
769 break;
770
771 default:
772 SCIPerrorMessage("invalid bound change type %d\n", boundchg->boundchgtype);
773 return SCIP_INVALIDDATA;
774 }
775
776 /* change local bound of variable */
777 SCIP_CALL( SCIPvarChgUbLocal(var, blkmem, set, stat, lp, branchcand, eventqueue, boundchg->newbound) );
778 }
779 else
780 {
781 SCIPsetDebugMsg(set, " -> cutoff: new upper bound of <%s>[%g,%g]: %g\n",
782 SCIPvarGetName(var), var->locdom.lb, var->locdom.ub, boundchg->newbound);
783 *cutoff = TRUE;
784 boundchg->redundant = TRUE; /* bound change has not entered the ubchginfos array of the variable! */
785 }
786 }
787 else
788 {
789 /* mark bound change to be inactive */
790 SCIPsetDebugMsg(set, " -> inactive %s: new upper bound of <%s>[%g,%g]: %g\n",
791 (SCIP_BOUNDCHGTYPE)boundchg->boundchgtype == SCIP_BOUNDCHGTYPE_BRANCHING ? "branching" : "inference",
792 SCIPvarGetName(var), var->locdom.lb, var->locdom.ub, boundchg->newbound);
793 boundchg->redundant = TRUE;
794 }
795 break;
796
797 default:
798 SCIPerrorMessage("unknown bound type\n");
799 return SCIP_INVALIDDATA;
800 }
801
802 /* update the branching and inference history */
803 if( !boundchg->applied && !boundchg->redundant )
804 {
805 assert(var == boundchg->var);
806
808 {
809 SCIP_CALL( SCIPvarIncNBranchings(var, blkmem, set, stat,
812 }
813 else if( stat->lastbranchvar != NULL )
814 {
815 /**@todo if last branching variable is unknown, retrieve it from the nodes' boundchg arrays */
816 SCIP_CALL( SCIPvarIncInferenceSum(stat->lastbranchvar, blkmem, set, stat, stat->lastbranchdir, stat->lastbranchvalue, 1.0) );
817 }
818 boundchg->applied = TRUE;
819 }
820
821 return SCIP_OKAY;
822}
823
824/** undoes single bound change */
826 SCIP_BOUNDCHG* boundchg, /**< bound change to remove */
827 BMS_BLKMEM* blkmem, /**< block memory */
828 SCIP_SET* set, /**< global SCIP settings */
829 SCIP_STAT* stat, /**< problem statistics */
830 SCIP_LP* lp, /**< current LP data */
831 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
832 SCIP_EVENTQUEUE* eventqueue /**< event queue */
833 )
834{
835 SCIP_VAR* var;
836
837 assert(boundchg != NULL);
838 assert(stat != NULL);
839
840 /* ignore redundant bound changes */
841 if( boundchg->redundant )
842 return SCIP_OKAY;
843
844 var = boundchg->var;
845 assert(var != NULL);
847
848 /* undo bound change: apply the previous bound change of variable */
849 switch( boundchg->boundtype )
850 {
852 var->nlbchginfos--;
853 assert(var->nlbchginfos >= 0);
854 assert(var->lbchginfos != NULL);
855 assert( SCIPsetIsFeasEQ(set, var->lbchginfos[var->nlbchginfos].newbound, var->locdom.lb) ); /*lint !e777*/
856 assert( SCIPsetIsFeasLE(set, boundchg->newbound, var->locdom.lb) ); /* current lb might be larger to intermediate global bound change */
857
858 SCIPsetDebugMsg(set, "removed lower bound change info of var <%s>[%g,%g]: depth=%d, pos=%d, %g -> %g\n",
859 SCIPvarGetName(var), var->locdom.lb, var->locdom.ub,
862
863 /* reinstall the previous local bound */
864 SCIP_CALL( SCIPvarChgLbLocal(boundchg->var, blkmem, set, stat, lp, branchcand, eventqueue,
865 var->lbchginfos[var->nlbchginfos].oldbound) );
866
867 /* in case all bound changes are removed the local bound should match the global bound */
868 assert(var->nlbchginfos > 0 || SCIPsetIsFeasEQ(set, var->locdom.lb, var->glbdom.lb));
869
870 break;
871
873 var->nubchginfos--;
874 assert(var->nubchginfos >= 0);
875 assert(var->ubchginfos != NULL);
876 assert( SCIPsetIsFeasEQ(set, var->ubchginfos[var->nubchginfos].newbound, var->locdom.ub) ); /*lint !e777*/
877 assert( SCIPsetIsFeasGE(set, boundchg->newbound, var->locdom.ub) ); /* current ub might be smaller to intermediate global bound change */
878
879 SCIPsetDebugMsg(set, "removed upper bound change info of var <%s>[%g,%g]: depth=%d, pos=%d, %g -> %g\n",
880 SCIPvarGetName(var), var->locdom.lb, var->locdom.ub,
883
884 /* reinstall the previous local bound */
885 SCIP_CALL( SCIPvarChgUbLocal(boundchg->var, blkmem, set, stat, lp, branchcand, eventqueue,
886 var->ubchginfos[var->nubchginfos].oldbound) );
887
888 /* in case all bound changes are removed the local bound should match the global bound */
889 assert(var->nubchginfos > 0 || SCIPsetIsFeasEQ(set, var->locdom.ub, var->glbdom.ub));
890
891 break;
892
893 default:
894 SCIPerrorMessage("unknown bound type\n");
895 return SCIP_INVALIDDATA;
896 }
897
898 /* update last branching variable */
900 {
901 stat->lastbranchvar = NULL;
903 }
904
905 return SCIP_OKAY;
906}
907
908/** applies single bound change to the global problem by changing the global bound of the corresponding variable */
909static
911 SCIP_BOUNDCHG* boundchg, /**< bound change to apply */
912 BMS_BLKMEM* blkmem, /**< block memory */
913 SCIP_SET* set, /**< global SCIP settings */
914 SCIP_STAT* stat, /**< problem statistics */
915 SCIP_LP* lp, /**< current LP data */
916 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
917 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
918 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
919 SCIP_Bool* cutoff /**< pointer to store whether an infeasible bound change was detected */
920 )
921{
922 SCIP_VAR* var;
923 SCIP_Real newbound;
924 SCIP_BOUNDTYPE boundtype;
925
926 assert(boundchg != NULL);
927 assert(cutoff != NULL);
928
929 *cutoff = FALSE;
930
931 /* ignore redundant bound changes */
932 if( boundchg->redundant )
933 return SCIP_OKAY;
934
935 var = SCIPboundchgGetVar(boundchg);
936 newbound = SCIPboundchgGetNewbound(boundchg);
937 boundtype = SCIPboundchgGetBoundtype(boundchg);
938
939 /* check if the bound change is redundant which can happen due to a (better) global bound change which was performed
940 * after that bound change was applied
941 *
942 * @note a global bound change is not captured by the redundant member of the bound change data structure
943 */
944 if( (boundtype == SCIP_BOUNDTYPE_LOWER && SCIPsetIsFeasLE(set, newbound, SCIPvarGetLbGlobal(var)))
945 || (boundtype == SCIP_BOUNDTYPE_UPPER && SCIPsetIsFeasGE(set, newbound, SCIPvarGetUbGlobal(var))) )
946 {
947 return SCIP_OKAY;
948 }
949
950 SCIPsetDebugMsg(set, "applying global bound change: <%s>[%g,%g] %s %g\n",
952 boundtype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", newbound);
953
954 /* check for cutoff */
955 if( (boundtype == SCIP_BOUNDTYPE_LOWER && SCIPsetIsFeasGT(set, newbound, SCIPvarGetUbGlobal(var)))
956 || (boundtype == SCIP_BOUNDTYPE_UPPER && SCIPsetIsFeasLT(set, newbound, SCIPvarGetLbGlobal(var))) )
957 {
958 *cutoff = TRUE;
959 return SCIP_OKAY;
960 }
961
962 /* apply bound change */
963 SCIP_CALL( SCIPvarChgBdGlobal(var, blkmem, set, stat, lp, branchcand, eventqueue, cliquetable, newbound, boundtype) );
964
965 return SCIP_OKAY;
966}
967
968/** captures branching and inference data of bound change */
969static
971 SCIP_BOUNDCHG* boundchg /**< bound change to remove */
972 )
973{
974 assert(boundchg != NULL);
975
976 /* capture variable associated with the bound change */
977 assert(boundchg->var != NULL);
978 SCIPvarCapture(boundchg->var);
979
980 switch( boundchg->boundchgtype )
981 {
984 break;
985
987 assert(boundchg->data.inferencedata.var != NULL);
988 assert(boundchg->data.inferencedata.reason.cons != NULL);
989 SCIPconsCapture(boundchg->data.inferencedata.reason.cons);
990 break;
991
992 default:
993 SCIPerrorMessage("invalid bound change type\n");
994 return SCIP_INVALIDDATA;
995 }
996
997 return SCIP_OKAY;
998}
999
1000/** releases branching and inference data of bound change */
1001static
1003 SCIP_BOUNDCHG* boundchg, /**< bound change to remove */
1004 BMS_BLKMEM* blkmem, /**< block memory */
1005 SCIP_SET* set, /**< global SCIP settings */
1006 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1007 SCIP_LP* lp /**< current LP data */
1008
1009 )
1010{
1011 assert(boundchg != NULL);
1012
1013 switch( boundchg->boundchgtype )
1014 {
1017 break;
1018
1020 assert(boundchg->data.inferencedata.var != NULL);
1021 assert(boundchg->data.inferencedata.reason.cons != NULL);
1022 SCIP_CALL( SCIPconsRelease(&boundchg->data.inferencedata.reason.cons, blkmem, set) );
1023 break;
1024
1025 default:
1026 SCIPerrorMessage("invalid bound change type\n");
1027 return SCIP_INVALIDDATA;
1028 }
1029
1030 /* release variable */
1031 assert(boundchg->var != NULL);
1032 SCIP_CALL( SCIPvarRelease(&boundchg->var, blkmem, set, eventqueue, lp) );
1033
1034 return SCIP_OKAY;
1035}
1036
1037/** creates empty domain change data with dynamic arrays */
1038static
1040 SCIP_DOMCHG** domchg, /**< pointer to domain change data */
1041 BMS_BLKMEM* blkmem /**< block memory */
1042 )
1043{
1044 assert(domchg != NULL);
1045 assert(blkmem != NULL);
1046
1047 SCIP_ALLOC( BMSallocBlockMemorySize(blkmem, domchg, sizeof(SCIP_DOMCHGDYN)) );
1048 (*domchg)->domchgdyn.domchgtype = SCIP_DOMCHGTYPE_DYNAMIC; /*lint !e641*/
1049 (*domchg)->domchgdyn.nboundchgs = 0;
1050 (*domchg)->domchgdyn.boundchgs = NULL;
1051 (*domchg)->domchgdyn.nholechgs = 0;
1052 (*domchg)->domchgdyn.holechgs = NULL;
1053 (*domchg)->domchgdyn.boundchgssize = 0;
1054 (*domchg)->domchgdyn.holechgssize = 0;
1055
1056 return SCIP_OKAY;
1057}
1058
1059/** frees domain change data */
1061 SCIP_DOMCHG** domchg, /**< pointer to domain change */
1062 BMS_BLKMEM* blkmem, /**< block memory */
1063 SCIP_SET* set, /**< global SCIP settings */
1064 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1065 SCIP_LP* lp /**< current LP data */
1066 )
1067{
1068 assert(domchg != NULL);
1069 assert(blkmem != NULL);
1070
1071 if( *domchg != NULL )
1072 {
1073 int i;
1074
1075 /* release variables, branching and inference data associated with the bound changes */
1076 for( i = 0; i < (int)(*domchg)->domchgbound.nboundchgs; ++i )
1077 {
1078 SCIP_CALL( boundchgReleaseData(&(*domchg)->domchgbound.boundchgs[i], blkmem, set, eventqueue, lp) );
1079 }
1080
1081 /* free memory for bound and hole changes */
1082 switch( (*domchg)->domchgdyn.domchgtype )
1083 {
1085 BMSfreeBlockMemoryArrayNull(blkmem, &(*domchg)->domchgbound.boundchgs, (*domchg)->domchgbound.nboundchgs);
1086 BMSfreeBlockMemorySize(blkmem, domchg, sizeof(SCIP_DOMCHGBOUND));
1087 break;
1089 BMSfreeBlockMemoryArrayNull(blkmem, &(*domchg)->domchgboth.boundchgs, (*domchg)->domchgboth.nboundchgs);
1090 BMSfreeBlockMemoryArrayNull(blkmem, &(*domchg)->domchgboth.holechgs, (*domchg)->domchgboth.nholechgs);
1091 BMSfreeBlockMemorySize(blkmem, domchg, sizeof(SCIP_DOMCHGBOTH));
1092 break;
1094 BMSfreeBlockMemoryArrayNull(blkmem, &(*domchg)->domchgdyn.boundchgs, (*domchg)->domchgdyn.boundchgssize);
1095 BMSfreeBlockMemoryArrayNull(blkmem, &(*domchg)->domchgdyn.holechgs, (*domchg)->domchgdyn.holechgssize);
1096 BMSfreeBlockMemorySize(blkmem, domchg, sizeof(SCIP_DOMCHGDYN));
1097 break;
1098 default:
1099 SCIPerrorMessage("invalid domain change type\n");
1100 return SCIP_INVALIDDATA;
1101 }
1102 }
1103
1104 return SCIP_OKAY;
1105}
1106
1107/** converts a static domain change data into a dynamic one */
1108static
1110 SCIP_DOMCHG** domchg, /**< pointer to domain change data */
1111 BMS_BLKMEM* blkmem /**< block memory */
1112 )
1113{
1114 assert(domchg != NULL);
1115 assert(blkmem != NULL);
1116
1117 SCIPdebugMessage("making domain change data %p pointing to %p dynamic\n", (void*)domchg, (void*)*domchg);
1118
1119 if( *domchg == NULL )
1120 {
1121 SCIP_CALL( domchgCreate(domchg, blkmem) );
1122 }
1123 else
1124 {
1125 switch( (*domchg)->domchgdyn.domchgtype )
1126 {
1128 SCIP_ALLOC( BMSreallocBlockMemorySize(blkmem, domchg, sizeof(SCIP_DOMCHGBOUND), sizeof(SCIP_DOMCHGDYN)) );
1129 (*domchg)->domchgdyn.nholechgs = 0;
1130 (*domchg)->domchgdyn.holechgs = NULL;
1131 (*domchg)->domchgdyn.boundchgssize = (int) (*domchg)->domchgdyn.nboundchgs;
1132 (*domchg)->domchgdyn.holechgssize = 0;
1133 (*domchg)->domchgdyn.domchgtype = SCIP_DOMCHGTYPE_DYNAMIC; /*lint !e641*/
1134 break;
1136 SCIP_ALLOC( BMSreallocBlockMemorySize(blkmem, domchg, sizeof(SCIP_DOMCHGBOTH), sizeof(SCIP_DOMCHGDYN)) );
1137 (*domchg)->domchgdyn.boundchgssize = (int) (*domchg)->domchgdyn.nboundchgs;
1138 (*domchg)->domchgdyn.holechgssize = (*domchg)->domchgdyn.nholechgs;
1139 (*domchg)->domchgdyn.domchgtype = SCIP_DOMCHGTYPE_DYNAMIC; /*lint !e641*/
1140 break;
1142 break;
1143 default:
1144 SCIPerrorMessage("invalid domain change type\n");
1145 return SCIP_INVALIDDATA;
1146 }
1147 }
1148#ifndef NDEBUG
1149 {
1150 int i;
1151 for( i = 0; i < (int)(*domchg)->domchgbound.nboundchgs; ++i )
1152 assert(SCIPvarGetType((*domchg)->domchgbound.boundchgs[i].var) == SCIP_VARTYPE_CONTINUOUS
1153 || EPSISINT((*domchg)->domchgbound.boundchgs[i].newbound, 1e-06));
1154 }
1155#endif
1156
1157 return SCIP_OKAY;
1158}
1159
1160/** converts a dynamic domain change data into a static one, using less memory than for a dynamic one */
1162 SCIP_DOMCHG** domchg, /**< pointer to domain change data */
1163 BMS_BLKMEM* blkmem, /**< block memory */
1164 SCIP_SET* set, /**< global SCIP settings */
1165 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1166 SCIP_LP* lp /**< current LP data */
1167 )
1168{
1169 assert(domchg != NULL);
1170 assert(blkmem != NULL);
1171
1172 SCIPsetDebugMsg(set, "making domain change data %p pointing to %p static\n", (void*)domchg, (void*)*domchg);
1173
1174 if( *domchg != NULL )
1175 {
1176 switch( (*domchg)->domchgdyn.domchgtype )
1177 {
1179 if( (*domchg)->domchgbound.nboundchgs == 0 )
1180 {
1181 SCIP_CALL( SCIPdomchgFree(domchg, blkmem, set, eventqueue, lp) );
1182 }
1183 break;
1185 if( (*domchg)->domchgboth.nholechgs == 0 )
1186 {
1187 if( (*domchg)->domchgbound.nboundchgs == 0 )
1188 {
1189 SCIP_CALL( SCIPdomchgFree(domchg, blkmem, set, eventqueue, lp) );
1190 }
1191 else
1192 {
1193 SCIP_ALLOC( BMSreallocBlockMemorySize(blkmem, domchg, sizeof(SCIP_DOMCHGBOTH), sizeof(SCIP_DOMCHGBOUND)) );
1194 (*domchg)->domchgdyn.domchgtype = SCIP_DOMCHGTYPE_BOUND; /*lint !e641*/
1195 }
1196 }
1197 break;
1199 if( (*domchg)->domchgboth.nholechgs == 0 )
1200 {
1201 if( (*domchg)->domchgbound.nboundchgs == 0 )
1202 {
1203 SCIP_CALL( SCIPdomchgFree(domchg, blkmem, set, eventqueue, lp) );
1204 }
1205 else
1206 {
1207 /* shrink dynamic size arrays to their minimal sizes */
1208 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(*domchg)->domchgdyn.boundchgs, \
1209 (*domchg)->domchgdyn.boundchgssize, (*domchg)->domchgdyn.nboundchgs) ); /*lint !e571*/
1210 BMSfreeBlockMemoryArrayNull(blkmem, &(*domchg)->domchgdyn.holechgs, (*domchg)->domchgdyn.holechgssize);
1211
1212 /* convert into static domain change */
1213 SCIP_ALLOC( BMSreallocBlockMemorySize(blkmem, domchg, sizeof(SCIP_DOMCHGDYN), sizeof(SCIP_DOMCHGBOUND)) );
1214 (*domchg)->domchgdyn.domchgtype = SCIP_DOMCHGTYPE_BOUND; /*lint !e641*/
1215 }
1216 }
1217 else
1218 {
1219 /* shrink dynamic size arrays to their minimal sizes */
1220 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(*domchg)->domchgdyn.boundchgs, \
1221 (*domchg)->domchgdyn.boundchgssize, (*domchg)->domchgdyn.nboundchgs) ); /*lint !e571*/
1222 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(*domchg)->domchgdyn.holechgs, \
1223 (*domchg)->domchgdyn.holechgssize, (*domchg)->domchgdyn.nholechgs) );
1224
1225 /* convert into static domain change */
1226 SCIP_ALLOC( BMSreallocBlockMemorySize(blkmem, domchg, sizeof(SCIP_DOMCHGDYN), sizeof(SCIP_DOMCHGBOTH)) );
1227 (*domchg)->domchgdyn.domchgtype = SCIP_DOMCHGTYPE_BOTH; /*lint !e641*/
1228 }
1229 break;
1230 default:
1231 SCIPerrorMessage("invalid domain change type\n");
1232 return SCIP_INVALIDDATA;
1233 }
1234#ifndef NDEBUG
1235 if( *domchg != NULL )
1236 {
1237 int i;
1238 for( i = 0; i < (int)(*domchg)->domchgbound.nboundchgs; ++i )
1239 assert(SCIPvarGetType((*domchg)->domchgbound.boundchgs[i].var) == SCIP_VARTYPE_CONTINUOUS
1240 || SCIPsetIsFeasIntegral(set, (*domchg)->domchgbound.boundchgs[i].newbound));
1241 }
1242#endif
1243 }
1244
1245 return SCIP_OKAY;
1246}
1247
1248/** ensures, that boundchgs array can store at least num entries */
1249static
1251 SCIP_DOMCHG* domchg, /**< domain change data structure */
1252 BMS_BLKMEM* blkmem, /**< block memory */
1253 SCIP_SET* set, /**< global SCIP settings */
1254 int num /**< minimum number of entries to store */
1255 )
1256{
1257 assert(domchg != NULL);
1258 assert(domchg->domchgdyn.domchgtype == SCIP_DOMCHGTYPE_DYNAMIC); /*lint !e641*/
1259
1260 if( num > domchg->domchgdyn.boundchgssize )
1261 {
1262 int newsize;
1263
1264 newsize = SCIPsetCalcMemGrowSize(set, num);
1265 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &domchg->domchgdyn.boundchgs, domchg->domchgdyn.boundchgssize, newsize) );
1266 domchg->domchgdyn.boundchgssize = newsize;
1267 }
1268 assert(num <= domchg->domchgdyn.boundchgssize);
1269
1270 return SCIP_OKAY;
1271}
1272
1273/** ensures, that holechgs array can store at least num additional entries */
1274static
1276 SCIP_DOMCHG* domchg, /**< domain change data structure */
1277 BMS_BLKMEM* blkmem, /**< block memory */
1278 SCIP_SET* set, /**< global SCIP settings */
1279 int num /**< minimum number of additional entries to store */
1280 )
1281{
1282 assert(domchg != NULL);
1283 assert(domchg->domchgdyn.domchgtype == SCIP_DOMCHGTYPE_DYNAMIC); /*lint !e641*/
1284
1285 if( num > domchg->domchgdyn.holechgssize )
1286 {
1287 int newsize;
1288
1289 newsize = SCIPsetCalcMemGrowSize(set, num);
1290 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &domchg->domchgdyn.holechgs, domchg->domchgdyn.holechgssize, newsize) );
1291 domchg->domchgdyn.holechgssize = newsize;
1292 }
1293 assert(num <= domchg->domchgdyn.holechgssize);
1294
1295 return SCIP_OKAY;
1296}
1297
1298/** applies domain change */
1300 SCIP_DOMCHG* domchg, /**< domain change to apply */
1301 BMS_BLKMEM* blkmem, /**< block memory */
1302 SCIP_SET* set, /**< global SCIP settings */
1303 SCIP_STAT* stat, /**< problem statistics */
1304 SCIP_LP* lp, /**< current LP data */
1305 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1306 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1307 int depth, /**< depth in the tree, where the domain change takes place */
1308 SCIP_Bool* cutoff /**< pointer to store whether an infeasible domain change was detected */
1309 )
1310{
1311 int i;
1312
1313 assert(cutoff != NULL);
1314
1315 *cutoff = FALSE;
1316
1317 SCIPsetDebugMsg(set, "applying domain changes at %p in depth %d\n", (void*)domchg, depth);
1318
1319 if( domchg == NULL )
1320 return SCIP_OKAY;
1321
1322 /* apply bound changes */
1323 for( i = 0; i < (int)domchg->domchgbound.nboundchgs; ++i )
1324 {
1325 SCIP_CALL( SCIPboundchgApply(&domchg->domchgbound.boundchgs[i], blkmem, set, stat, lp,
1326 branchcand, eventqueue, depth, i, cutoff) );
1327 if( *cutoff )
1328 break;
1329 }
1330 SCIPsetDebugMsg(set, " -> %u bound changes (cutoff %u)\n", domchg->domchgbound.nboundchgs, *cutoff);
1331
1332 /* mark all bound changes after a cutoff redundant */
1333 for( ; i < (int)domchg->domchgbound.nboundchgs; ++i )
1334 domchg->domchgbound.boundchgs[i].redundant = TRUE;
1335
1336 /* apply holelist changes */
1337 if( domchg->domchgdyn.domchgtype != SCIP_DOMCHGTYPE_BOUND ) /*lint !e641*/
1338 {
1339 for( i = 0; i < domchg->domchgboth.nholechgs; ++i )
1340 *(domchg->domchgboth.holechgs[i].ptr) = domchg->domchgboth.holechgs[i].newlist;
1341 SCIPsetDebugMsg(set, " -> %d hole changes\n", domchg->domchgboth.nholechgs);
1342 }
1343
1344 return SCIP_OKAY;
1345}
1346
1347/** undoes domain change */
1349 SCIP_DOMCHG* domchg, /**< domain change to remove */
1350 BMS_BLKMEM* blkmem, /**< block memory */
1351 SCIP_SET* set, /**< global SCIP settings */
1352 SCIP_STAT* stat, /**< problem statistics */
1353 SCIP_LP* lp, /**< current LP data */
1354 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1355 SCIP_EVENTQUEUE* eventqueue /**< event queue */
1356 )
1357{
1358 int i;
1359
1360 SCIPsetDebugMsg(set, "undoing domain changes at %p\n", (void*)domchg);
1361 if( domchg == NULL )
1362 return SCIP_OKAY;
1363
1364 /* undo holelist changes */
1365 if( domchg->domchgdyn.domchgtype != SCIP_DOMCHGTYPE_BOUND ) /*lint !e641*/
1366 {
1367 for( i = domchg->domchgboth.nholechgs-1; i >= 0; --i )
1368 *(domchg->domchgboth.holechgs[i].ptr) = domchg->domchgboth.holechgs[i].oldlist;
1369 SCIPsetDebugMsg(set, " -> %d hole changes\n", domchg->domchgboth.nholechgs);
1370 }
1371
1372 /* undo bound changes */
1373 for( i = domchg->domchgbound.nboundchgs-1; i >= 0; --i )
1374 {
1375 SCIP_CALL( SCIPboundchgUndo(&domchg->domchgbound.boundchgs[i], blkmem, set, stat, lp, branchcand, eventqueue) );
1376 }
1377 SCIPsetDebugMsg(set, " -> %u bound changes\n", domchg->domchgbound.nboundchgs);
1378
1379 return SCIP_OKAY;
1380}
1381
1382/** applies domain change to the global problem */
1384 SCIP_DOMCHG* domchg, /**< domain change to apply */
1385 BMS_BLKMEM* blkmem, /**< block memory */
1386 SCIP_SET* set, /**< global SCIP settings */
1387 SCIP_STAT* stat, /**< problem statistics */
1388 SCIP_LP* lp, /**< current LP data */
1389 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1390 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1391 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
1392 SCIP_Bool* cutoff /**< pointer to store whether an infeasible domain change was detected */
1393 )
1394{
1395 int i;
1396
1397 assert(cutoff != NULL);
1398
1399 *cutoff = FALSE;
1400
1401 if( domchg == NULL )
1402 return SCIP_OKAY;
1403
1404 SCIPsetDebugMsg(set, "applying domain changes at %p to the global problem\n", (void*)domchg);
1405
1406 /* apply bound changes */
1407 for( i = 0; i < (int)domchg->domchgbound.nboundchgs; ++i )
1408 {
1409 SCIP_CALL( boundchgApplyGlobal(&domchg->domchgbound.boundchgs[i], blkmem, set, stat, lp,
1410 branchcand, eventqueue, cliquetable, cutoff) );
1411 if( *cutoff )
1412 break;
1413 }
1414 SCIPsetDebugMsg(set, " -> %u global bound changes\n", domchg->domchgbound.nboundchgs);
1415
1416 /**@todo globally apply holelist changes - how can this be done without confusing pointer updates? */
1417
1418 return SCIP_OKAY;
1419}
1420
1421/** adds bound change to domain changes */
1423 SCIP_DOMCHG** domchg, /**< pointer to domain change data structure */
1424 BMS_BLKMEM* blkmem, /**< block memory */
1425 SCIP_SET* set, /**< global SCIP settings */
1426 SCIP_VAR* var, /**< variable to change the bounds for */
1427 SCIP_Real newbound, /**< new value for bound */
1428 SCIP_BOUNDTYPE boundtype, /**< type of bound for var: lower or upper bound */
1429 SCIP_BOUNDCHGTYPE boundchgtype, /**< type of bound change: branching decision or inference */
1430 SCIP_Real lpsolval, /**< solval of variable in last LP on path to node, or SCIP_INVALID if unknown */
1431 SCIP_VAR* infervar, /**< variable that was changed (parent of var, or var itself), or NULL */
1432 SCIP_CONS* infercons, /**< constraint that deduced the bound change, or NULL */
1433 SCIP_PROP* inferprop, /**< propagator that deduced the bound change, or NULL */
1434 int inferinfo, /**< user information for inference to help resolving the conflict */
1435 SCIP_BOUNDTYPE inferboundtype /**< type of bound for inference var: lower or upper bound */
1436 )
1437{
1438 SCIP_BOUNDCHG* boundchg;
1439
1440 assert(domchg != NULL);
1441 assert(var != NULL);
1444 assert(!SCIPvarIsBinary(var) || SCIPsetIsEQ(set, newbound, boundtype == SCIP_BOUNDTYPE_LOWER ? 1.0 : 0.0));
1445 assert(boundchgtype == SCIP_BOUNDCHGTYPE_BRANCHING || infervar != NULL);
1446 assert((boundchgtype == SCIP_BOUNDCHGTYPE_CONSINFER) == (infercons != NULL));
1447 assert(boundchgtype == SCIP_BOUNDCHGTYPE_PROPINFER || inferprop == NULL);
1448
1449 SCIPsetDebugMsg(set, "adding %s bound change <%s: %g> of variable <%s> to domain change at %p pointing to %p\n",
1450 boundtype == SCIP_BOUNDTYPE_LOWER ? "lower" : "upper", boundchgtype == SCIP_BOUNDCHGTYPE_BRANCHING ? "branching" : "inference",
1451 newbound, var->name, (void*)domchg, (void*)*domchg);
1452
1453 /* if domain change data doesn't exist, create it;
1454 * if domain change is static, convert it into dynamic change
1455 */
1456 if( *domchg == NULL )
1457 {
1458 SCIP_CALL( domchgCreate(domchg, blkmem) );
1459 }
1460 else if( (*domchg)->domchgdyn.domchgtype != SCIP_DOMCHGTYPE_DYNAMIC ) /*lint !e641*/
1461 {
1462 SCIP_CALL( domchgMakeDynamic(domchg, blkmem) );
1463 }
1464 assert(*domchg != NULL && (*domchg)->domchgdyn.domchgtype == SCIP_DOMCHGTYPE_DYNAMIC); /*lint !e641*/
1465
1466 /* get memory for additional bound change */
1467 SCIP_CALL( domchgEnsureBoundchgsSize(*domchg, blkmem, set, (*domchg)->domchgdyn.nboundchgs+1) );
1468
1469 /* fill in the bound change data */
1470 boundchg = &(*domchg)->domchgdyn.boundchgs[(*domchg)->domchgdyn.nboundchgs];
1471 boundchg->var = var;
1472 switch( boundchgtype )
1473 {
1475 boundchg->data.branchingdata.lpsolval = lpsolval;
1476 break;
1478 assert(infercons != NULL);
1479 boundchg->data.inferencedata.var = infervar;
1480 boundchg->data.inferencedata.reason.cons = infercons;
1481 boundchg->data.inferencedata.info = inferinfo;
1482 break;
1484 boundchg->data.inferencedata.var = infervar;
1485 boundchg->data.inferencedata.reason.prop = inferprop;
1486 boundchg->data.inferencedata.info = inferinfo;
1487 break;
1488 default:
1489 SCIPerrorMessage("invalid bound change type %d\n", boundchgtype);
1490 return SCIP_INVALIDDATA;
1491 }
1492
1493 boundchg->newbound = newbound;
1494 boundchg->boundchgtype = boundchgtype; /*lint !e641*/
1495 boundchg->boundtype = boundtype; /*lint !e641*/
1496 boundchg->inferboundtype = inferboundtype; /*lint !e641*/
1497 boundchg->applied = FALSE;
1498 boundchg->redundant = FALSE;
1499 (*domchg)->domchgdyn.nboundchgs++;
1500
1501 /* capture branching and inference data associated with the bound changes */
1502 SCIP_CALL( boundchgCaptureData(boundchg) );
1503
1504#ifdef SCIP_DISABLED_CODE /* expensive debug check */
1505#ifdef SCIP_MORE_DEBUG
1506 {
1507 int i;
1508 for( i = 0; i < (int)(*domchg)->domchgbound.nboundchgs; ++i )
1509 assert(SCIPvarGetType((*domchg)->domchgbound.boundchgs[i].var) == SCIP_VARTYPE_CONTINUOUS
1510 || SCIPsetIsFeasIntegral(set, (*domchg)->domchgbound.boundchgs[i].newbound));
1511 }
1512#endif
1513#endif
1514
1515 return SCIP_OKAY;
1516}
1517
1518/** adds hole change to domain changes */
1520 SCIP_DOMCHG** domchg, /**< pointer to domain change data structure */
1521 BMS_BLKMEM* blkmem, /**< block memory */
1522 SCIP_SET* set, /**< global SCIP settings */
1523 SCIP_HOLELIST** ptr, /**< changed list pointer */
1524 SCIP_HOLELIST* newlist, /**< new value of list pointer */
1525 SCIP_HOLELIST* oldlist /**< old value of list pointer */
1526 )
1527{
1528 SCIP_HOLECHG* holechg;
1529
1530 assert(domchg != NULL);
1531 assert(ptr != NULL);
1532
1533 /* if domain change data doesn't exist, create it;
1534 * if domain change is static, convert it into dynamic change
1535 */
1536 if( *domchg == NULL )
1537 {
1538 SCIP_CALL( domchgCreate(domchg, blkmem) );
1539 }
1540 else if( (*domchg)->domchgdyn.domchgtype != SCIP_DOMCHGTYPE_DYNAMIC ) /*lint !e641*/
1541 {
1542 SCIP_CALL( domchgMakeDynamic(domchg, blkmem) );
1543 }
1544 assert(*domchg != NULL && (*domchg)->domchgdyn.domchgtype == SCIP_DOMCHGTYPE_DYNAMIC); /*lint !e641*/
1545
1546 /* get memory for additional hole change */
1547 SCIP_CALL( domchgEnsureHolechgsSize(*domchg, blkmem, set, (*domchg)->domchgdyn.nholechgs+1) );
1548
1549 /* fill in the hole change data */
1550 holechg = &(*domchg)->domchgdyn.holechgs[(*domchg)->domchgdyn.nholechgs];
1551 holechg->ptr = ptr;
1552 holechg->newlist = newlist;
1553 holechg->oldlist = oldlist;
1554 (*domchg)->domchgdyn.nholechgs++;
1555
1556 return SCIP_OKAY;
1557}
1558
1559
1560
1561
1562/*
1563 * methods for variables
1564 */
1565
1566/** returns adjusted lower bound value, which is rounded for integral variable types */
1567static
1569 SCIP_SET* set, /**< global SCIP settings */
1570 SCIP_VARTYPE vartype, /**< type of variable */
1571 SCIP_Real lb /**< lower bound to adjust */
1572 )
1573{
1574 if( lb < 0.0 && SCIPsetIsInfinity(set, -lb) )
1575 return -SCIPsetInfinity(set);
1576 else if( lb > 0.0 && SCIPsetIsInfinity(set, lb) )
1577 return SCIPsetInfinity(set);
1578 else if( vartype != SCIP_VARTYPE_CONTINUOUS )
1579 return SCIPsetFeasCeil(set, lb);
1580 else if( lb > 0.0 && lb < SCIPsetEpsilon(set) )
1581 return 0.0;
1582 else
1583 return lb;
1584}
1585
1586/** returns adjusted upper bound value, which is rounded for integral variable types */
1587static
1589 SCIP_SET* set, /**< global SCIP settings */
1590 SCIP_VARTYPE vartype, /**< type of variable */
1591 SCIP_Real ub /**< upper bound to adjust */
1592 )
1593{
1594 if( ub > 0.0 && SCIPsetIsInfinity(set, ub) )
1595 return SCIPsetInfinity(set);
1596 else if( ub < 0.0 && SCIPsetIsInfinity(set, -ub) )
1597 return -SCIPsetInfinity(set);
1598 else if( vartype != SCIP_VARTYPE_CONTINUOUS )
1599 return SCIPsetFeasFloor(set, ub);
1600 else if( ub < 0.0 && ub > -SCIPsetEpsilon(set) )
1601 return 0.0;
1602 else
1603 return ub;
1604}
1605
1606/** removes (redundant) cliques, implications and variable bounds of variable from all other variables' implications and variable
1607 * bounds arrays, and optionally removes them also from the variable itself
1608 */
1610 SCIP_VAR* var, /**< problem variable */
1611 BMS_BLKMEM* blkmem, /**< block memory */
1612 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
1613 SCIP_SET* set, /**< global SCIP settings */
1614 SCIP_Bool irrelevantvar, /**< has the variable become irrelevant? */
1615 SCIP_Bool onlyredundant, /**< should only the redundant implications and variable bounds be removed? */
1616 SCIP_Bool removefromvar /**< should the implications and variable bounds be removed from the var itself? */
1617 )
1618{
1619 SCIP_Real lb;
1620 SCIP_Real ub;
1621
1622 assert(var != NULL);
1624 assert(SCIPvarIsActive(var) || SCIPvarGetType(var) != SCIP_VARTYPE_BINARY);
1625
1626 lb = SCIPvarGetLbGlobal(var);
1627 ub = SCIPvarGetUbGlobal(var);
1628
1629 SCIPsetDebugMsg(set, "removing %s implications and vbounds of %s<%s>[%g,%g]\n",
1630 onlyredundant ? "redundant" : "all", irrelevantvar ? "irrelevant " : "", SCIPvarGetName(var), lb, ub);
1631
1632 /* remove implications of (fixed) binary variable */
1633 if( var->implics != NULL && (!onlyredundant || lb > 0.5 || ub < 0.5) )
1634 {
1635 SCIP_Bool varfixing;
1636
1637 assert(SCIPvarIsBinary(var));
1638
1639 varfixing = FALSE;
1640 do
1641 {
1642 SCIP_VAR** implvars;
1643 SCIP_BOUNDTYPE* impltypes;
1644 int nimpls;
1645 int i;
1646
1647 nimpls = SCIPimplicsGetNImpls(var->implics, varfixing);
1648 implvars = SCIPimplicsGetVars(var->implics, varfixing);
1649 impltypes = SCIPimplicsGetTypes(var->implics, varfixing);
1650
1651 for( i = 0; i < nimpls; i++ )
1652 {
1653 SCIP_VAR* implvar;
1654 SCIP_BOUNDTYPE impltype;
1655
1656 implvar = implvars[i];
1657 impltype = impltypes[i];
1658 assert(implvar != var);
1659
1660 /* remove for all implications z == 0 / 1 ==> x <= p / x >= p (x not binary)
1661 * the following variable bound from x's variable bounds
1662 * x <= b*z+d (z in vubs of x) , for z == 0 / 1 ==> x <= p
1663 * x >= b*z+d (z in vlbs of x) , for z == 0 / 1 ==> x >= p
1664 */
1665 if( impltype == SCIP_BOUNDTYPE_UPPER )
1666 {
1667 if( implvar->vubs != NULL ) /* implvar may have been aggregated in the mean time */
1668 {
1669 SCIPsetDebugMsg(set, "deleting variable bound: <%s> == %u ==> <%s> <= %g\n",
1670 SCIPvarGetName(var), varfixing, SCIPvarGetName(implvar),
1671 SCIPimplicsGetBounds(var->implics, varfixing)[i]);
1672 SCIP_CALL( SCIPvboundsDel(&implvar->vubs, blkmem, var, varfixing) );
1673 implvar->closestvblpcount = -1;
1674 var->closestvblpcount = -1;
1675 }
1676 }
1677 else
1678 {
1679 if( implvar->vlbs != NULL ) /* implvar may have been aggregated in the mean time */
1680 {
1681 SCIPsetDebugMsg(set, "deleting variable bound: <%s> == %u ==> <%s> >= %g\n",
1682 SCIPvarGetName(var), varfixing, SCIPvarGetName(implvar),
1683 SCIPimplicsGetBounds(var->implics, varfixing)[i]);
1684 SCIP_CALL( SCIPvboundsDel(&implvar->vlbs, blkmem, var, !varfixing) );
1685 implvar->closestvblpcount = -1;
1686 var->closestvblpcount = -1;
1687 }
1688 }
1689 }
1690 varfixing = !varfixing;
1691 }
1692 while( varfixing == TRUE );
1693
1694 if( removefromvar )
1695 {
1696 /* free the implications data structures */
1697 SCIPimplicsFree(&var->implics, blkmem);
1698 }
1699 }
1700
1701 /* remove the (redundant) variable lower bounds */
1702 if( var->vlbs != NULL )
1703 {
1704 SCIP_VAR** vars;
1705 SCIP_Real* coefs;
1706 SCIP_Real* constants;
1707 int nvbds;
1708 int newnvbds;
1709 int i;
1710
1711 nvbds = SCIPvboundsGetNVbds(var->vlbs);
1712 vars = SCIPvboundsGetVars(var->vlbs);
1713 coefs = SCIPvboundsGetCoefs(var->vlbs);
1714 constants = SCIPvboundsGetConstants(var->vlbs);
1715
1716 /* remove for all variable bounds x >= b*z+d the following implication from z's implications
1717 * z == ub ==> x >= b*ub + d , if b > 0
1718 * z == lb ==> x >= b*lb + d , if b < 0
1719 */
1720 newnvbds = 0;
1721 for( i = 0; i < nvbds; i++ )
1722 {
1723 SCIP_VAR* implvar;
1724 SCIP_Real coef;
1725
1726 assert(newnvbds <= i);
1727
1728 implvar = vars[i];
1729 assert(implvar != NULL);
1730
1731 coef = coefs[i];
1732 assert(!SCIPsetIsZero(set, coef));
1733
1734 /* check, if we want to remove the variable bound */
1735 if( onlyredundant )
1736 {
1737 SCIP_Real vbound;
1738
1739 vbound = MAX(coef * SCIPvarGetUbGlobal(implvar), coef * SCIPvarGetLbGlobal(implvar)) + constants[i]; /*lint !e666*/
1740 if( SCIPsetIsFeasGT(set, vbound, lb) )
1741 {
1742 /* the variable bound is not redundant: keep it */
1743 if( removefromvar )
1744 {
1745 if( newnvbds < i )
1746 {
1747 vars[newnvbds] = implvar;
1748 coefs[newnvbds] = coef;
1749 constants[newnvbds] = constants[i];
1750 }
1751 newnvbds++;
1752 }
1753 continue;
1754 }
1755 }
1756
1757 /* remove the corresponding implication */
1758 if( implvar->implics != NULL ) /* variable may have been aggregated in the mean time */
1759 {
1760 SCIPsetDebugMsg(set, "deleting implication: <%s> == %d ==> <%s> >= %g\n",
1761 SCIPvarGetName(implvar), (coef > 0.0), SCIPvarGetName(var), MAX(coef, 0.0) + constants[i]);
1762 SCIP_CALL( SCIPimplicsDel(&implvar->implics, blkmem, set, (coef > 0.0), var, SCIP_BOUNDTYPE_LOWER) );
1763 }
1764 if( coef > 0.0 && implvar->vubs != NULL ) /* implvar may have been aggregated in the mean time */
1765 {
1766 SCIPsetDebugMsg(set, "deleting variable upper bound from <%s> involving variable %s\n",
1767 SCIPvarGetName(implvar), SCIPvarGetName(var));
1768 SCIP_CALL( SCIPvboundsDel(&implvar->vubs, blkmem, var, FALSE) );
1769 implvar->closestvblpcount = -1;
1770 var->closestvblpcount = -1;
1771 }
1772 else if( coef < 0.0 && implvar->vlbs != NULL ) /* implvar may have been aggregated in the mean time */
1773 {
1774 SCIPsetDebugMsg(set, "deleting variable lower bound from <%s> involving variable %s\n",
1775 SCIPvarGetName(implvar), SCIPvarGetName(var));
1776 SCIP_CALL( SCIPvboundsDel(&implvar->vlbs, blkmem, var, TRUE) );
1777 implvar->closestvblpcount = -1;
1778 var->closestvblpcount = -1;
1779 }
1780 }
1781
1782 if( removefromvar )
1783 {
1784 /* update the number of variable bounds */
1785 SCIPvboundsShrink(&var->vlbs, blkmem, newnvbds);
1786 var->closestvblpcount = -1;
1787 }
1788 }
1789
1790 /**@todo in general, variable bounds like x >= b*z + d corresponding to an implication like z = ub ==> x >= b*ub + d
1791 * might be missing because we only add variable bounds with reasonably small value of b. thus, we currently
1792 * cannot remove such variables x from z's implications.
1793 */
1794
1795 /* remove the (redundant) variable upper bounds */
1796 if( var->vubs != NULL )
1797 {
1798 SCIP_VAR** vars;
1799 SCIP_Real* coefs;
1800 SCIP_Real* constants;
1801 int nvbds;
1802 int newnvbds;
1803 int i;
1804
1805 nvbds = SCIPvboundsGetNVbds(var->vubs);
1806 vars = SCIPvboundsGetVars(var->vubs);
1807 coefs = SCIPvboundsGetCoefs(var->vubs);
1808 constants = SCIPvboundsGetConstants(var->vubs);
1809
1810 /* remove for all variable bounds x <= b*z+d the following implication from z's implications
1811 * z == lb ==> x <= b*lb + d , if b > 0
1812 * z == ub ==> x <= b*ub + d , if b < 0
1813 */
1814 newnvbds = 0;
1815 for( i = 0; i < nvbds; i++ )
1816 {
1817 SCIP_VAR* implvar;
1818 SCIP_Real coef;
1819
1820 assert(newnvbds <= i);
1821
1822 implvar = vars[i];
1823 assert(implvar != NULL);
1824
1825 coef = coefs[i];
1826 assert(!SCIPsetIsZero(set, coef));
1827
1828 /* check, if we want to remove the variable bound */
1829 if( onlyredundant )
1830 {
1831 SCIP_Real vbound;
1832
1833 vbound = MIN(coef * SCIPvarGetUbGlobal(implvar), coef * SCIPvarGetLbGlobal(implvar)) + constants[i]; /*lint !e666*/
1834 if( SCIPsetIsFeasLT(set, vbound, ub) )
1835 {
1836 /* the variable bound is not redundant: keep it */
1837 if( removefromvar )
1838 {
1839 if( newnvbds < i )
1840 {
1841 vars[newnvbds] = implvar;
1842 coefs[newnvbds] = coefs[i];
1843 constants[newnvbds] = constants[i];
1844 }
1845 newnvbds++;
1846 }
1847 continue;
1848 }
1849 }
1850
1851 /* remove the corresponding implication */
1852 if( implvar->implics != NULL ) /* variable may have been aggregated in the mean time */
1853 {
1854 SCIPsetDebugMsg(set, "deleting implication: <%s> == %d ==> <%s> <= %g\n",
1855 SCIPvarGetName(implvar), (coef < 0.0), SCIPvarGetName(var), MIN(coef, 0.0) + constants[i]);
1856 SCIP_CALL( SCIPimplicsDel(&implvar->implics, blkmem, set, (coef < 0.0), var, SCIP_BOUNDTYPE_UPPER) );
1857 }
1858 if( coef < 0.0 && implvar->vubs != NULL ) /* implvar may have been aggregated in the mean time */
1859 {
1860 SCIPsetDebugMsg(set, "deleting variable upper bound from <%s> involving variable %s\n",
1861 SCIPvarGetName(implvar), SCIPvarGetName(var));
1862 SCIP_CALL( SCIPvboundsDel(&implvar->vubs, blkmem, var, TRUE) );
1863 implvar->closestvblpcount = -1;
1864 var->closestvblpcount = -1;
1865 }
1866 else if( coef > 0.0 && implvar->vlbs != NULL ) /* implvar may have been aggregated in the mean time */
1867 {
1868 SCIPsetDebugMsg(set, "deleting variable lower bound from <%s> involving variable %s\n",
1869 SCIPvarGetName(implvar), SCIPvarGetName(var));
1870 SCIP_CALL( SCIPvboundsDel(&implvar->vlbs, blkmem, var, FALSE) );
1871 implvar->closestvblpcount = -1;
1872 var->closestvblpcount = -1;
1873 }
1874 }
1875
1876 if( removefromvar )
1877 {
1878 /* update the number of variable bounds */
1879 SCIPvboundsShrink(&var->vubs, blkmem, newnvbds);
1880 var->closestvblpcount = -1;
1881 }
1882 }
1883
1884 /* remove the variable from all cliques */
1885 if( SCIPvarIsBinary(var) )
1886 SCIPcliquelistRemoveFromCliques(var->cliquelist, cliquetable, var, irrelevantvar);
1887
1888 /**@todo variable bounds like x <= b*z + d with z general integer are not removed from x's vbd arrays, because
1889 * z has no link (like in the binary case) to x
1890 */
1891
1892 return SCIP_OKAY;
1893}
1894
1895/** sets the variable name */
1896static
1898 SCIP_VAR* var, /**< problem variable */
1899 BMS_BLKMEM* blkmem, /**< block memory */
1900 SCIP_STAT* stat, /**< problem statistics, or NULL */
1901 const char* name /**< name of variable, or NULL for automatic name creation */
1902 )
1903{
1904 assert(blkmem != NULL);
1905 assert(var != NULL);
1906
1907 if( name == NULL )
1908 {
1909 char s[SCIP_MAXSTRLEN];
1910
1911 assert(stat != NULL);
1912
1913 (void) SCIPsnprintf(s, SCIP_MAXSTRLEN, "_var%d_", stat->nvaridx);
1914 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &var->name, s, strlen(s)+1) );
1915 }
1916 else
1917 {
1918 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &var->name, name, strlen(name)+1) );
1919 }
1920
1921 return SCIP_OKAY;
1922}
1923
1924
1925/** creates variable; if variable is of integral type, fractional bounds are automatically rounded; an integer variable
1926 * with bounds zero and one is automatically converted into a binary variable
1927 */
1928static
1930 SCIP_VAR** var, /**< pointer to variable data */
1931 BMS_BLKMEM* blkmem, /**< block memory */
1932 SCIP_SET* set, /**< global SCIP settings */
1933 SCIP_STAT* stat, /**< problem statistics */
1934 const char* name, /**< name of variable, or NULL for automatic name creation */
1935 SCIP_Real lb, /**< lower bound of variable */
1936 SCIP_Real ub, /**< upper bound of variable */
1937 SCIP_Real obj, /**< objective function value */
1938 SCIP_VARTYPE vartype, /**< type of variable */
1939 SCIP_Bool initial, /**< should var's column be present in the initial root LP? */
1940 SCIP_Bool removable, /**< is var's column removable from the LP (due to aging or cleanup)? */
1941 SCIP_DECL_VARCOPY ((*varcopy)), /**< copies variable data if wanted to subscip, or NULL */
1942 SCIP_DECL_VARDELORIG ((*vardelorig)), /**< frees user data of original variable, or NULL */
1943 SCIP_DECL_VARTRANS ((*vartrans)), /**< creates transformed user data by transforming original user data, or NULL */
1944 SCIP_DECL_VARDELTRANS ((*vardeltrans)), /**< frees user data of transformed variable, or NULL */
1945 SCIP_VARDATA* vardata /**< user data for this specific variable */
1946 )
1947{
1948 int i;
1949
1950 assert(var != NULL);
1951 assert(blkmem != NULL);
1952 assert(stat != NULL);
1953
1954 /* adjust bounds of variable */
1955 lb = adjustedLb(set, vartype, lb);
1956 ub = adjustedUb(set, vartype, ub);
1957
1958 /* convert [0,1]-integers into binary variables and check that binary variables have correct bounds */
1959 if( (SCIPsetIsEQ(set, lb, 0.0) || SCIPsetIsEQ(set, lb, 1.0))
1960 && (SCIPsetIsEQ(set, ub, 0.0) || SCIPsetIsEQ(set, ub, 1.0)) )
1961 {
1962 if( vartype == SCIP_VARTYPE_INTEGER )
1963 vartype = SCIP_VARTYPE_BINARY;
1964 }
1965 else
1966 {
1967 if( vartype == SCIP_VARTYPE_BINARY )
1968 {
1969 SCIPerrorMessage("invalid bounds [%.2g,%.2g] for binary variable <%s>\n", lb, ub, name);
1970 return SCIP_INVALIDDATA;
1971 }
1972 }
1973
1974 assert(vartype != SCIP_VARTYPE_BINARY || SCIPsetIsEQ(set, lb, 0.0) || SCIPsetIsEQ(set, lb, 1.0));
1975 assert(vartype != SCIP_VARTYPE_BINARY || SCIPsetIsEQ(set, ub, 0.0) || SCIPsetIsEQ(set, ub, 1.0));
1976
1977 SCIP_ALLOC( BMSallocBlockMemory(blkmem, var) );
1978
1979 /* set variable's name */
1980 SCIP_CALL( varSetName(*var, blkmem, stat, name) );
1981
1982#ifndef NDEBUG
1983 (*var)->scip = set->scip;
1984#endif
1985 (*var)->obj = obj;
1986 (*var)->unchangedobj = obj;
1987 (*var)->branchfactor = 1.0;
1988 (*var)->rootsol = 0.0;
1989 (*var)->bestrootsol = 0.0;
1990 (*var)->bestrootredcost = 0.0;
1991 (*var)->bestrootlpobjval = SCIP_INVALID;
1992 (*var)->relaxsol = 0.0;
1993 (*var)->nlpsol = 0.0;
1994 (*var)->primsolavg = 0.5 * (lb + ub);
1995 (*var)->conflictlb = SCIP_REAL_MIN;
1996 (*var)->conflictub = SCIP_REAL_MAX;
1997 (*var)->conflictrelaxedlb = (*var)->conflictlb;
1998 (*var)->conflictrelaxedub = (*var)->conflictub;
1999 (*var)->lazylb = -SCIPsetInfinity(set);
2000 (*var)->lazyub = SCIPsetInfinity(set);
2001 (*var)->glbdom.holelist = NULL;
2002 (*var)->glbdom.lb = lb;
2003 (*var)->glbdom.ub = ub;
2004 (*var)->locdom.holelist = NULL;
2005 (*var)->locdom.lb = lb;
2006 (*var)->locdom.ub = ub;
2007 (*var)->varcopy = varcopy;
2008 (*var)->vardelorig = vardelorig;
2009 (*var)->vartrans = vartrans;
2010 (*var)->vardeltrans = vardeltrans;
2011 (*var)->vardata = vardata;
2012 (*var)->parentvars = NULL;
2013 (*var)->negatedvar = NULL;
2014 (*var)->vlbs = NULL;
2015 (*var)->vubs = NULL;
2016 (*var)->implics = NULL;
2017 (*var)->cliquelist = NULL;
2018 (*var)->eventfilter = NULL;
2019 (*var)->lbchginfos = NULL;
2020 (*var)->ubchginfos = NULL;
2021 (*var)->index = stat->nvaridx;
2022 (*var)->probindex = -1;
2023 (*var)->pseudocandindex = -1;
2024 (*var)->eventqueueindexobj = -1;
2025 (*var)->eventqueueindexlb = -1;
2026 (*var)->eventqueueindexub = -1;
2027 (*var)->parentvarssize = 0;
2028 (*var)->nparentvars = 0;
2029 (*var)->nuses = 0;
2030 (*var)->branchpriority = 0;
2031 (*var)->branchdirection = SCIP_BRANCHDIR_AUTO; /*lint !e641*/
2032 (*var)->lbchginfossize = 0;
2033 (*var)->nlbchginfos = 0;
2034 (*var)->ubchginfossize = 0;
2035 (*var)->nubchginfos = 0;
2036 (*var)->conflictlbcount = 0;
2037 (*var)->conflictubcount = 0;
2038 (*var)->closestvlbidx = -1;
2039 (*var)->closestvubidx = -1;
2040 (*var)->closestvblpcount = -1;
2041 (*var)->initial = initial;
2042 (*var)->removable = removable;
2043 (*var)->deleted = FALSE;
2044 (*var)->donotaggr = FALSE;
2045 (*var)->donotmultaggr = FALSE;
2046 (*var)->vartype = vartype; /*lint !e641*/
2047 (*var)->pseudocostflag = FALSE;
2048 (*var)->eventqueueimpl = FALSE;
2049 (*var)->deletable = FALSE;
2050 (*var)->delglobalstructs = FALSE;
2051 (*var)->relaxationonly = FALSE;
2052
2053 for( i = 0; i < NLOCKTYPES; i++ )
2054 {
2055 (*var)->nlocksdown[i] = 0;
2056 (*var)->nlocksup[i] = 0;
2057 }
2058
2059 stat->nvaridx++;
2060
2061 /* create branching and inference history entries */
2062 SCIP_CALL( SCIPhistoryCreate(&(*var)->history, blkmem) );
2063 SCIP_CALL( SCIPhistoryCreate(&(*var)->historycrun, blkmem) );
2064
2065 /* the value based history is only created on demand */
2066 (*var)->valuehistory = NULL;
2067
2068 return SCIP_OKAY;
2069}
2070
2071/** creates and captures an original problem variable; an integer variable with bounds
2072 * zero and one is automatically converted into a binary variable
2073 */
2075 SCIP_VAR** var, /**< pointer to variable data */
2076 BMS_BLKMEM* blkmem, /**< block memory */
2077 SCIP_SET* set, /**< global SCIP settings */
2078 SCIP_STAT* stat, /**< problem statistics */
2079 const char* name, /**< name of variable, or NULL for automatic name creation */
2080 SCIP_Real lb, /**< lower bound of variable */
2081 SCIP_Real ub, /**< upper bound of variable */
2082 SCIP_Real obj, /**< objective function value */
2083 SCIP_VARTYPE vartype, /**< type of variable */
2084 SCIP_Bool initial, /**< should var's column be present in the initial root LP? */
2085 SCIP_Bool removable, /**< is var's column removable from the LP (due to aging or cleanup)? */
2086 SCIP_DECL_VARDELORIG ((*vardelorig)), /**< frees user data of original variable, or NULL */
2087 SCIP_DECL_VARTRANS ((*vartrans)), /**< creates transformed user data by transforming original user data, or NULL */
2088 SCIP_DECL_VARDELTRANS ((*vardeltrans)), /**< frees user data of transformed variable, or NULL */
2089 SCIP_DECL_VARCOPY ((*varcopy)), /**< copies variable data if wanted to subscip, or NULL */
2090 SCIP_VARDATA* vardata /**< user data for this specific variable */
2091 )
2092{
2093 assert(var != NULL);
2094 assert(blkmem != NULL);
2095 assert(stat != NULL);
2096
2097 /* create variable */
2098 SCIP_CALL( varCreate(var, blkmem, set, stat, name, lb, ub, obj, vartype, initial, removable,
2099 varcopy, vardelorig, vartrans, vardeltrans, vardata) );
2100
2101 /* set variable status and data */
2102 (*var)->varstatus = SCIP_VARSTATUS_ORIGINAL; /*lint !e641*/
2103 (*var)->data.original.origdom.holelist = NULL;
2104 (*var)->data.original.origdom.lb = lb;
2105 (*var)->data.original.origdom.ub = ub;
2106 (*var)->data.original.transvar = NULL;
2107
2108 /* capture variable */
2109 SCIPvarCapture(*var);
2110
2111 return SCIP_OKAY;
2112}
2113
2114/** creates and captures a loose variable belonging to the transformed problem; an integer variable with bounds
2115 * zero and one is automatically converted into a binary variable
2116 */
2118 SCIP_VAR** var, /**< pointer to variable data */
2119 BMS_BLKMEM* blkmem, /**< block memory */
2120 SCIP_SET* set, /**< global SCIP settings */
2121 SCIP_STAT* stat, /**< problem statistics */
2122 const char* name, /**< name of variable, or NULL for automatic name creation */
2123 SCIP_Real lb, /**< lower bound of variable */
2124 SCIP_Real ub, /**< upper bound of variable */
2125 SCIP_Real obj, /**< objective function value */
2126 SCIP_VARTYPE vartype, /**< type of variable */
2127 SCIP_Bool initial, /**< should var's column be present in the initial root LP? */
2128 SCIP_Bool removable, /**< is var's column removable from the LP (due to aging or cleanup)? */
2129 SCIP_DECL_VARDELORIG ((*vardelorig)), /**< frees user data of original variable, or NULL */
2130 SCIP_DECL_VARTRANS ((*vartrans)), /**< creates transformed user data by transforming original user data, or NULL */
2131 SCIP_DECL_VARDELTRANS ((*vardeltrans)), /**< frees user data of transformed variable, or NULL */
2132 SCIP_DECL_VARCOPY ((*varcopy)), /**< copies variable data if wanted to subscip, or NULL */
2133 SCIP_VARDATA* vardata /**< user data for this specific variable */
2134 )
2135{
2136 assert(var != NULL);
2137 assert(blkmem != NULL);
2138
2139 /* create variable */
2140 SCIP_CALL( varCreate(var, blkmem, set, stat, name, lb, ub, obj, vartype, initial, removable,
2141 varcopy, vardelorig, vartrans, vardeltrans, vardata) );
2142
2143 /* create event filter for transformed variable */
2144 SCIP_CALL( SCIPeventfilterCreate(&(*var)->eventfilter, blkmem) );
2145
2146 /* set variable status and data */
2147 (*var)->varstatus = SCIP_VARSTATUS_LOOSE; /*lint !e641*/
2148
2149 /* capture variable */
2150 SCIPvarCapture(*var);
2151
2152 return SCIP_OKAY;
2153}
2154
2155/** copies and captures a variable from source to target SCIP; an integer variable with bounds zero and one is
2156 * automatically converted into a binary variable; in case the variable data cannot be copied the variable is not
2157 * copied at all
2158 */
2160 SCIP_VAR** var, /**< pointer to store the target variable */
2161 BMS_BLKMEM* blkmem, /**< block memory */
2162 SCIP_SET* set, /**< global SCIP settings */
2163 SCIP_STAT* stat, /**< problem statistics */
2164 SCIP* sourcescip, /**< source SCIP data structure */
2165 SCIP_VAR* sourcevar, /**< source variable */
2166 SCIP_HASHMAP* varmap, /**< a hashmap to store the mapping of source variables corresponding
2167 * target variables */
2168 SCIP_HASHMAP* consmap, /**< a hashmap to store the mapping of source constraints to the corresponding
2169 * target constraints */
2170 SCIP_Bool global /**< should global or local bounds be used? */
2171 )
2172{
2173 SCIP_VARDATA* targetdata;
2174 SCIP_RESULT result;
2175 SCIP_Real lb;
2176 SCIP_Real ub;
2177
2178 assert(set != NULL);
2179 assert(blkmem != NULL);
2180 assert(stat != NULL);
2181 assert(sourcescip != NULL);
2182 assert(sourcevar != NULL);
2183 assert(var != NULL);
2184 assert(set->stage == SCIP_STAGE_PROBLEM);
2185 assert(varmap != NULL);
2186 assert(consmap != NULL);
2187
2188 /** @todo copy hole lists */
2189 assert(global || SCIPvarGetHolelistLocal(sourcevar) == NULL);
2190 assert(!global || SCIPvarGetHolelistGlobal(sourcevar) == NULL);
2191
2192 result = SCIP_DIDNOTRUN;
2193 targetdata = NULL;
2194
2195 if( SCIPvarGetStatus(sourcevar) == SCIP_VARSTATUS_ORIGINAL )
2196 {
2197 lb = SCIPvarGetLbOriginal(sourcevar);
2198 ub = SCIPvarGetUbOriginal(sourcevar);
2199 }
2200 else
2201 {
2202 lb = global ? SCIPvarGetLbGlobal(sourcevar) : SCIPvarGetLbLocal(sourcevar);
2203 ub = global ? SCIPvarGetUbGlobal(sourcevar) : SCIPvarGetUbLocal(sourcevar);
2204 }
2205
2206 /* creates and captures the variable in the target SCIP and initialize callback methods and variable data to NULL */
2207 SCIP_CALL( SCIPvarCreateOriginal(var, blkmem, set, stat, SCIPvarGetName(sourcevar),
2208 lb, ub, SCIPvarGetObj(sourcevar), SCIPvarGetType(sourcevar),
2209 SCIPvarIsInitial(sourcevar), SCIPvarIsRemovable(sourcevar),
2210 NULL, NULL, NULL, NULL, NULL) );
2211 assert(*var != NULL);
2212
2213 /* directly copy donot(mult)aggr flag */
2214 (*var)->donotaggr = sourcevar->donotaggr;
2215 (*var)->donotmultaggr = sourcevar->donotmultaggr;
2216
2217 /* insert variable into mapping between source SCIP and the target SCIP */
2218 assert(!SCIPhashmapExists(varmap, sourcevar));
2219 SCIP_CALL( SCIPhashmapInsert(varmap, sourcevar, *var) );
2220
2221 /* in case there exists variable data and the variable data copy callback, try to copy variable data */
2222 if( sourcevar->vardata != NULL && sourcevar->varcopy != NULL )
2223 {
2224 SCIP_CALL( sourcevar->varcopy(set->scip, sourcescip, sourcevar, sourcevar->vardata,
2225 varmap, consmap, (*var), &targetdata, &result) );
2226
2227 /* evaluate result */
2228 if( result != SCIP_DIDNOTRUN && result != SCIP_SUCCESS )
2229 {
2230 SCIPerrorMessage("variable data copying method returned invalid result <%d>\n", result);
2231 return SCIP_INVALIDRESULT;
2232 }
2233
2234 assert(targetdata == NULL || result == SCIP_SUCCESS);
2235
2236 /* if copying was successful, add the created variable data to the variable as well as all callback methods */
2237 if( result == SCIP_SUCCESS )
2238 {
2239 (*var)->varcopy = sourcevar->varcopy;
2240 (*var)->vardelorig = sourcevar->vardelorig;
2241 (*var)->vartrans = sourcevar->vartrans;
2242 (*var)->vardeltrans = sourcevar->vardeltrans;
2243 (*var)->vardata = targetdata;
2244 }
2245 }
2246
2247 /* we initialize histories of the variables by copying the source variable-information */
2248 if( set->history_allowtransfer )
2249 {
2250 SCIPvarMergeHistories((*var), sourcevar, stat);
2251 }
2252
2253 /* in case the copying was successfully, add the created variable data to the variable as well as all callback
2254 * methods
2255 */
2256 if( result == SCIP_SUCCESS )
2257 {
2258 (*var)->varcopy = sourcevar->varcopy;
2259 (*var)->vardelorig = sourcevar->vardelorig;
2260 (*var)->vartrans = sourcevar->vartrans;
2261 (*var)->vardeltrans = sourcevar->vardeltrans;
2262 (*var)->vardata = targetdata;
2263 }
2264
2265 SCIPsetDebugMsg(set, "created copy <%s> of variable <%s>\n", SCIPvarGetName(*var), SCIPvarGetName(sourcevar));
2266
2267 return SCIP_OKAY;
2268}
2269
2270/** parse given string for a SCIP_Real bound */
2271static
2273 SCIP_SET* set, /**< global SCIP settings */
2274 const char* str, /**< string to parse */
2275 SCIP_Real* value, /**< pointer to store the parsed value */
2276 char** endptr /**< pointer to store the final string position if successfully parsed */
2277 )
2278{
2279 /* first check for infinity value */
2280 if( strncmp(str, "+inf", 4) == 0 )
2281 {
2282 *value = SCIPsetInfinity(set);
2283 (*endptr) = (char*)str + 4;
2284 }
2285 else if( strncmp(str, "-inf", 4) == 0 )
2286 {
2287 *value = -SCIPsetInfinity(set);
2288 (*endptr) = (char*)str + 4;
2289 }
2290 else
2291 {
2292 if( !SCIPstrToRealValue(str, value, endptr) )
2293 {
2294 SCIPerrorMessage("expected value: %s.\n", str);
2295 return SCIP_READERROR;
2296 }
2297 }
2298
2299 return SCIP_OKAY;
2300}
2301
2302/** parse the characters as bounds */
2303static
2305 SCIP_SET* set, /**< global SCIP settings */
2306 const char* str, /**< string to parse */
2307 char* type, /**< bound type (global, local, or lazy) */
2308 SCIP_Real* lb, /**< pointer to store the lower bound */
2309 SCIP_Real* ub, /**< pointer to store the upper bound */
2310 char** endptr /**< pointer to store the final string position if successfully parsed (or NULL if an error occured) */
2311 )
2312{
2313 char token[SCIP_MAXSTRLEN];
2314 char* tmpend;
2315
2316 SCIPsetDebugMsg(set, "parsing bounds: '%s'\n", str);
2317
2318 /* get bound type */
2319 SCIPstrCopySection(str, ' ', ' ', type, SCIP_MAXSTRLEN, endptr);
2320 if ( *endptr == str
2321 || ( strncmp(type, "original", 8) != 0 && strncmp(type, "global", 6) != 0 && strncmp(type, "local", 5) != 0 && strncmp(type, "lazy", 4) != 0 ) )
2322 {
2323 SCIPsetDebugMsg(set, "unkown bound type\n");
2324 *endptr = NULL;
2325 return SCIP_OKAY;
2326 }
2327
2328 SCIPsetDebugMsg(set, "parsed bound type <%s>\n", type);
2329
2330 /* get lower bound */
2331 SCIPstrCopySection(str, '[', ',', token, SCIP_MAXSTRLEN, endptr);
2332 str = *endptr;
2333 SCIP_CALL( parseValue(set, token, lb, &tmpend) );
2334
2335 /* get upper bound */
2336 SCIP_CALL( parseValue(set, str, ub, endptr) );
2337
2338 SCIPsetDebugMsg(set, "parsed bounds: [%g,%g]\n", *lb, *ub);
2339
2340 /* skip end of bounds */
2341 while ( **endptr != '\0' && (**endptr == ']' || **endptr == ',') )
2342 ++(*endptr);
2343
2344 return SCIP_OKAY;
2345}
2346
2347/** parses a given string for a variable informations */
2348static
2350 SCIP_SET* set, /**< global SCIP settings */
2351 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
2352 const char* str, /**< string to parse */
2353 char* name, /**< pointer to store the variable name */
2354 SCIP_Real* lb, /**< pointer to store the lower bound */
2355 SCIP_Real* ub, /**< pointer to store the upper bound */
2356 SCIP_Real* obj, /**< pointer to store the objective coefficient */
2357 SCIP_VARTYPE* vartype, /**< pointer to store the variable type */
2358 SCIP_Real* lazylb, /**< pointer to store if the lower bound is lazy */
2359 SCIP_Real* lazyub, /**< pointer to store if the upper bound is lazy */
2360 SCIP_Bool local, /**< should the local bound be applied */
2361 char** endptr, /**< pointer to store the final string position if successfully */
2362 SCIP_Bool* success /**< pointer store if the paring process was successful */
2363 )
2364{
2365 SCIP_Real parsedlb;
2366 SCIP_Real parsedub;
2367 char token[SCIP_MAXSTRLEN];
2368 char* strptr;
2369 int i;
2370
2371 assert(lb != NULL);
2372 assert(ub != NULL);
2373 assert(obj != NULL);
2374 assert(vartype != NULL);
2375 assert(lazylb != NULL);
2376 assert(lazyub != NULL);
2377 assert(success != NULL);
2378
2379 (*success) = TRUE;
2380
2381 /* copy variable type */
2382 SCIPstrCopySection(str, '[', ']', token, SCIP_MAXSTRLEN, endptr);
2383 assert(*endptr != str);
2384 SCIPsetDebugMsg(set, "parsed variable type <%s>\n", token);
2385
2386 /* get variable type */
2387 if( strncmp(token, "binary", 3) == 0 )
2388 (*vartype) = SCIP_VARTYPE_BINARY;
2389 else if( strncmp(token, "integer", 3) == 0 )
2390 (*vartype) = SCIP_VARTYPE_INTEGER;
2391 else if( strncmp(token, "implicit", 3) == 0 )
2392 (*vartype) = SCIP_VARTYPE_IMPLINT;
2393 else if( strncmp(token, "continuous", 3) == 0 )
2394 (*vartype) = SCIP_VARTYPE_CONTINUOUS;
2395 else
2396 {
2397 SCIPmessagePrintWarning(messagehdlr, "unknown variable type\n");
2398 (*success) = FALSE;
2399 return SCIP_OKAY;
2400 }
2401
2402 /* move string pointer behind variable type */
2403 str = *endptr;
2404
2405 /* get variable name */
2406 SCIPstrCopySection(str, '<', '>', name, SCIP_MAXSTRLEN, endptr);
2407 assert(*endptr != str);
2408 SCIPsetDebugMsg(set, "parsed variable name <%s>\n", name);
2409
2410 /* move string pointer behind variable name */
2411 str = *endptr;
2412
2413 /* cut out objective coefficient */
2414 SCIPstrCopySection(str, '=', ',', token, SCIP_MAXSTRLEN, endptr);
2415
2416 /* move string pointer behind objective coefficient */
2417 str = *endptr;
2418
2419 /* get objective coefficient */
2420 if( !SCIPstrToRealValue(token, obj, endptr) )
2421 {
2422 *endptr = NULL;
2423 return SCIP_READERROR;
2424 }
2425
2426 SCIPsetDebugMsg(set, "parsed objective coefficient <%g>\n", *obj);
2427
2428 /* parse global/original bounds */
2429 SCIP_CALL( parseBounds(set, str, token, lb, ub, endptr) );
2430 if ( *endptr == NULL )
2431 {
2432 SCIPerrorMessage("Expected bound type: %s.\n", token);
2433 return SCIP_READERROR;
2434 }
2435 assert(strncmp(token, "global", 6) == 0 || strncmp(token, "original", 8) == 0);
2436
2437 /* initialize the lazy bound */
2438 *lazylb = -SCIPsetInfinity(set);
2439 *lazyub = SCIPsetInfinity(set);
2440
2441 /* store pointer */
2442 strptr = *endptr;
2443
2444 /* possibly parse optional local and lazy bounds */
2445 for( i = 0; i < 2 && *endptr != NULL && **endptr != '\0'; ++i )
2446 {
2447 /* start after previous bounds */
2448 strptr = *endptr;
2449
2450 /* parse global bounds */
2451 SCIP_CALL( parseBounds(set, strptr, token, &parsedlb, &parsedub, endptr) );
2452
2453 /* stop if parsing of bounds failed */
2454 if( *endptr == NULL )
2455 break;
2456
2457 if( strncmp(token, "local", 5) == 0 && local )
2458 {
2459 *lb = parsedlb;
2460 *ub = parsedub;
2461 }
2462 else if( strncmp(token, "lazy", 4) == 0 )
2463 {
2464 *lazylb = parsedlb;
2465 *lazyub = parsedub;
2466 }
2467 }
2468
2469 /* restore pointer */
2470 if ( *endptr == NULL )
2471 *endptr = strptr;
2472
2473 /* check bounds for binary variables */
2474 if ( (*vartype) == SCIP_VARTYPE_BINARY )
2475 {
2476 if ( SCIPsetIsLT(set, *lb, 0.0) || SCIPsetIsGT(set, *ub, 1.0) )
2477 {
2478 SCIPerrorMessage("Parsed invalid bounds for binary variable <%s>: [%f, %f].\n", name, *lb, *ub);
2479 return SCIP_READERROR;
2480 }
2481 if ( !SCIPsetIsInfinity(set, -(*lazylb)) && !SCIPsetIsInfinity(set, *lazyub) &&
2482 ( SCIPsetIsLT(set, *lazylb, 0.0) || SCIPsetIsGT(set, *lazyub, 1.0) ) )
2483 {
2484 SCIPerrorMessage("Parsed invalid lazy bounds for binary variable <%s>: [%f, %f].\n", name, *lazylb, *lazyub);
2485 return SCIP_READERROR;
2486 }
2487 }
2488
2489 return SCIP_OKAY;
2490}
2491
2492/** parses variable information (in cip format) out of a string; if the parsing process was successful an original
2493 * variable is created and captured; if variable is of integral type, fractional bounds are automatically rounded; an
2494 * integer variable with bounds zero and one is automatically converted into a binary variable
2495 */
2497 SCIP_VAR** var, /**< pointer to variable data */
2498 BMS_BLKMEM* blkmem, /**< block memory */
2499 SCIP_SET* set, /**< global SCIP settings */
2500 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
2501 SCIP_STAT* stat, /**< problem statistics */
2502 const char* str, /**< string to parse */
2503 SCIP_Bool initial, /**< should var's column be present in the initial root LP? */
2504 SCIP_Bool removable, /**< is var's column removable from the LP (due to aging or cleanup)? */
2505 SCIP_DECL_VARCOPY ((*varcopy)), /**< copies variable data if wanted to subscip, or NULL */
2506 SCIP_DECL_VARDELORIG ((*vardelorig)), /**< frees user data of original variable */
2507 SCIP_DECL_VARTRANS ((*vartrans)), /**< creates transformed user data by transforming original user data */
2508 SCIP_DECL_VARDELTRANS ((*vardeltrans)), /**< frees user data of transformed variable */
2509 SCIP_VARDATA* vardata, /**< user data for this specific variable */
2510 char** endptr, /**< pointer to store the final string position if successfully */
2511 SCIP_Bool* success /**< pointer store if the paring process was successful */
2512 )
2513{
2514 char name[SCIP_MAXSTRLEN];
2515 SCIP_Real lb;
2516 SCIP_Real ub;
2517 SCIP_Real obj;
2518 SCIP_VARTYPE vartype;
2519 SCIP_Real lazylb;
2520 SCIP_Real lazyub;
2521
2522 assert(var != NULL);
2523 assert(blkmem != NULL);
2524 assert(stat != NULL);
2525 assert(endptr != NULL);
2526 assert(success != NULL);
2527
2528 /* parse string in cip format for variable information */
2529 SCIP_CALL( varParse(set, messagehdlr, str, name, &lb, &ub, &obj, &vartype, &lazylb, &lazyub, FALSE, endptr, success) );
2530
2531 if( *success ) /*lint !e774*/
2532 {
2533 /* create variable */
2534 SCIP_CALL( varCreate(var, blkmem, set, stat, name, lb, ub, obj, vartype, initial, removable,
2535 varcopy, vardelorig, vartrans, vardeltrans, vardata) );
2536
2537 /* set variable status and data */
2538 (*var)->varstatus = SCIP_VARSTATUS_ORIGINAL; /*lint !e641*/
2539 (*var)->data.original.origdom.holelist = NULL;
2540 (*var)->data.original.origdom.lb = lb;
2541 (*var)->data.original.origdom.ub = ub;
2542 (*var)->data.original.transvar = NULL;
2543
2544 /* set lazy status of variable bounds */
2545 (*var)->lazylb = lazylb;
2546 (*var)->lazyub = lazyub;
2547
2548 /* capture variable */
2549 SCIPvarCapture(*var);
2550 }
2551
2552 return SCIP_OKAY;
2553}
2554
2555/** parses variable information (in cip format) out of a string; if the parsing process was successful a loose variable
2556 * belonging to the transformed problem is created and captured; if variable is of integral type, fractional bounds are
2557 * automatically rounded; an integer variable with bounds zero and one is automatically converted into a binary
2558 * variable
2559 */
2561 SCIP_VAR** var, /**< pointer to variable data */
2562 BMS_BLKMEM* blkmem, /**< block memory */
2563 SCIP_SET* set, /**< global SCIP settings */
2564 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
2565 SCIP_STAT* stat, /**< problem statistics */
2566 const char* str, /**< string to parse */
2567 SCIP_Bool initial, /**< should var's column be present in the initial root LP? */
2568 SCIP_Bool removable, /**< is var's column removable from the LP (due to aging or cleanup)? */
2569 SCIP_DECL_VARCOPY ((*varcopy)), /**< copies variable data if wanted to subscip, or NULL */
2570 SCIP_DECL_VARDELORIG ((*vardelorig)), /**< frees user data of original variable */
2571 SCIP_DECL_VARTRANS ((*vartrans)), /**< creates transformed user data by transforming original user data */
2572 SCIP_DECL_VARDELTRANS ((*vardeltrans)), /**< frees user data of transformed variable */
2573 SCIP_VARDATA* vardata, /**< user data for this specific variable */
2574 char** endptr, /**< pointer to store the final string position if successfully */
2575 SCIP_Bool* success /**< pointer store if the paring process was successful */
2576 )
2577{
2578 char name[SCIP_MAXSTRLEN];
2579 SCIP_Real lb;
2580 SCIP_Real ub;
2581 SCIP_Real obj;
2582 SCIP_VARTYPE vartype;
2583 SCIP_Real lazylb;
2584 SCIP_Real lazyub;
2585
2586 assert(var != NULL);
2587 assert(blkmem != NULL);
2588 assert(endptr != NULL);
2589 assert(success != NULL);
2590
2591 /* parse string in cip format for variable information */
2592 SCIP_CALL( varParse(set, messagehdlr, str, name, &lb, &ub, &obj, &vartype, &lazylb, &lazyub, TRUE, endptr, success) );
2593
2594 if( *success ) /*lint !e774*/
2595 {
2596 /* create variable */
2597 SCIP_CALL( varCreate(var, blkmem, set, stat, name, lb, ub, obj, vartype, initial, removable,
2598 varcopy, vardelorig, vartrans, vardeltrans, vardata) );
2599
2600 /* create event filter for transformed variable */
2601 SCIP_CALL( SCIPeventfilterCreate(&(*var)->eventfilter, blkmem) );
2602
2603 /* set variable status and data */
2604 (*var)->varstatus = SCIP_VARSTATUS_LOOSE; /*lint !e641*/
2605
2606 /* set lazy status of variable bounds */
2607 (*var)->lazylb = lazylb;
2608 (*var)->lazyub = lazyub;
2609
2610 /* capture variable */
2611 SCIPvarCapture(*var);
2612 }
2613
2614 return SCIP_OKAY;
2615}
2616
2617/** ensures, that parentvars array of var can store at least num entries */
2618static
2620 SCIP_VAR* var, /**< problem variable */
2621 BMS_BLKMEM* blkmem, /**< block memory */
2622 SCIP_SET* set, /**< global SCIP settings */
2623 int num /**< minimum number of entries to store */
2624 )
2625{
2626 assert(var->nparentvars <= var->parentvarssize);
2627
2628 if( num > var->parentvarssize )
2629 {
2630 int newsize;
2631
2632 newsize = SCIPsetCalcMemGrowSize(set, num);
2633 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &var->parentvars, var->parentvarssize, newsize) );
2634 var->parentvarssize = newsize;
2635 }
2636 assert(num <= var->parentvarssize);
2637
2638 return SCIP_OKAY;
2639}
2640
2641/** adds variable to parent list of a variable and captures parent variable */
2642static
2644 SCIP_VAR* var, /**< variable to add parent to */
2645 BMS_BLKMEM* blkmem, /**< block memory of transformed problem */
2646 SCIP_SET* set, /**< global SCIP settings */
2647 SCIP_VAR* parentvar /**< parent variable to add */
2648 )
2649{
2650 assert(var != NULL);
2651 assert(parentvar != NULL);
2652
2653 /* the direct original counterpart must be stored as first parent */
2654 assert(var->nparentvars == 0 || SCIPvarGetStatus(parentvar) != SCIP_VARSTATUS_ORIGINAL);
2655
2656 SCIPsetDebugMsg(set, "adding parent <%s>[%p] to variable <%s>[%p] in slot %d\n",
2657 parentvar->name, (void*)parentvar, var->name, (void*)var, var->nparentvars);
2658
2659 SCIP_CALL( varEnsureParentvarsSize(var, blkmem, set, var->nparentvars+1) );
2660
2661 var->parentvars[var->nparentvars] = parentvar;
2662 var->nparentvars++;
2663
2664 SCIPvarCapture(parentvar);
2665
2666 return SCIP_OKAY;
2667}
2668
2669/** deletes and releases all variables from the parent list of a variable, frees the memory of parents array */
2670static
2672 SCIP_VAR** var, /**< pointer to variable */
2673 BMS_BLKMEM* blkmem, /**< block memory */
2674 SCIP_SET* set, /**< global SCIP settings */
2675 SCIP_EVENTQUEUE* eventqueue, /**< event queue (or NULL, if it's an original variable) */
2676 SCIP_LP* lp /**< current LP data (or NULL, if it's an original variable) */
2677 )
2678{
2679 SCIP_VAR* parentvar;
2680 int i;
2681
2682 SCIPsetDebugMsg(set, "free parents of <%s>\n", (*var)->name);
2683
2684 /* release the parent variables and remove the link from the parent variable to the child */
2685 for( i = 0; i < (*var)->nparentvars; ++i )
2686 {
2687 assert((*var)->parentvars != NULL);
2688 parentvar = (*var)->parentvars[i];
2689 assert(parentvar != NULL);
2690
2691 switch( SCIPvarGetStatus(parentvar) )
2692 {
2694 assert(parentvar->data.original.transvar == *var);
2695 assert(&parentvar->data.original.transvar != var);
2696 parentvar->data.original.transvar = NULL;
2697 break;
2698
2700 assert(parentvar->data.aggregate.var == *var);
2701 assert(&parentvar->data.aggregate.var != var);
2702 parentvar->data.aggregate.var = NULL;
2703 break;
2704
2705#ifdef SCIP_DISABLED_CODE
2706 /* The following code is unclear: should the current variable be removed from its parents? */
2708 assert(parentvar->data.multaggr.vars != NULL);
2709 for( v = 0; v < parentvar->data.multaggr.nvars && parentvar->data.multaggr.vars[v] != *var; ++v )
2710 {}
2711 assert(v < parentvar->data.multaggr.nvars && parentvar->data.multaggr.vars[v] == *var);
2712 if( v < parentvar->data.multaggr.nvars-1 )
2713 {
2714 parentvar->data.multaggr.vars[v] = parentvar->data.multaggr.vars[parentvar->data.multaggr.nvars-1];
2715 parentvar->data.multaggr.scalars[v] = parentvar->data.multaggr.scalars[parentvar->data.multaggr.nvars-1];
2716 }
2717 parentvar->data.multaggr.nvars--;
2718 break;
2719#endif
2720
2722 assert(parentvar->negatedvar == *var);
2723 assert((*var)->negatedvar == parentvar);
2724 parentvar->negatedvar = NULL;
2725 (*var)->negatedvar = NULL;
2726 break;
2727
2728 default:
2729 SCIPerrorMessage("parent variable is neither ORIGINAL, AGGREGATED nor NEGATED\n");
2730 return SCIP_INVALIDDATA;
2731 } /*lint !e788*/
2732
2733 SCIP_CALL( SCIPvarRelease(&(*var)->parentvars[i], blkmem, set, eventqueue, lp) );
2734 }
2735
2736 /* free parentvars array */
2737 BMSfreeBlockMemoryArrayNull(blkmem, &(*var)->parentvars, (*var)->parentvarssize);
2738
2739 return SCIP_OKAY;
2740}
2741
2742/** frees a variable */
2743static
2745 SCIP_VAR** var, /**< pointer to variable */
2746 BMS_BLKMEM* blkmem, /**< block memory */
2747 SCIP_SET* set, /**< global SCIP settings */
2748 SCIP_EVENTQUEUE* eventqueue, /**< event queue (may be NULL, if it's not a column variable) */
2749 SCIP_LP* lp /**< current LP data (may be NULL, if it's not a column variable) */
2750 )
2751{
2752 assert(var != NULL);
2753 assert(*var != NULL);
2754 assert(SCIPvarGetStatus(*var) != SCIP_VARSTATUS_COLUMN || &(*var)->data.col->var != var);
2755 assert((*var)->nuses == 0);
2756 assert((*var)->probindex == -1);
2757 assert((*var)->nlocksup[SCIP_LOCKTYPE_MODEL] == 0);
2758 assert((*var)->nlocksdown[SCIP_LOCKTYPE_MODEL] == 0);
2759
2760 SCIPsetDebugMsg(set, "free variable <%s> with status=%d\n", (*var)->name, SCIPvarGetStatus(*var));
2761
2762 switch( SCIPvarGetStatus(*var) )
2763 {
2765 assert((*var)->data.original.transvar == NULL); /* cannot free variable, if transformed variable is still existing */
2766 holelistFree(&(*var)->data.original.origdom.holelist, blkmem);
2767 assert((*var)->data.original.origdom.holelist == NULL);
2768 break;
2770 break;
2772 SCIP_CALL( SCIPcolFree(&(*var)->data.col, blkmem, set, eventqueue, lp) ); /* free corresponding LP column */
2773 break;
2776 break;
2778 BMSfreeBlockMemoryArray(blkmem, &(*var)->data.multaggr.vars, (*var)->data.multaggr.varssize);
2779 BMSfreeBlockMemoryArray(blkmem, &(*var)->data.multaggr.scalars, (*var)->data.multaggr.varssize);
2780 break;
2782 break;
2783 default:
2784 SCIPerrorMessage("unknown variable status\n");
2785 return SCIP_INVALIDDATA;
2786 }
2787
2788 /* release all parent variables and free the parentvars array */
2789 SCIP_CALL( varFreeParents(var, blkmem, set, eventqueue, lp) );
2790
2791 /* free user data */
2793 {
2794 if( (*var)->vardelorig != NULL )
2795 {
2796 SCIP_CALL( (*var)->vardelorig(set->scip, *var, &(*var)->vardata) );
2797 }
2798 }
2799 else
2800 {
2801 if( (*var)->vardeltrans != NULL )
2802 {
2803 SCIP_CALL( (*var)->vardeltrans(set->scip, *var, &(*var)->vardata) );
2804 }
2805 }
2806
2807 /* free event filter */
2808 if( (*var)->eventfilter != NULL )
2809 {
2810 SCIP_CALL( SCIPeventfilterFree(&(*var)->eventfilter, blkmem, set) );
2811 }
2812 assert((*var)->eventfilter == NULL);
2813
2814 /* free hole lists */
2815 holelistFree(&(*var)->glbdom.holelist, blkmem);
2816 holelistFree(&(*var)->locdom.holelist, blkmem);
2817 assert((*var)->glbdom.holelist == NULL);
2818 assert((*var)->locdom.holelist == NULL);
2819
2820 /* free variable bounds data structures */
2821 SCIPvboundsFree(&(*var)->vlbs, blkmem);
2822 SCIPvboundsFree(&(*var)->vubs, blkmem);
2823
2824 /* free implications data structures */
2825 SCIPimplicsFree(&(*var)->implics, blkmem);
2826
2827 /* free clique list data structures */
2828 SCIPcliquelistFree(&(*var)->cliquelist, blkmem);
2829
2830 /* free bound change information arrays */
2831 BMSfreeBlockMemoryArrayNull(blkmem, &(*var)->lbchginfos, (*var)->lbchginfossize);
2832 BMSfreeBlockMemoryArrayNull(blkmem, &(*var)->ubchginfos, (*var)->ubchginfossize);
2833
2834 /* free branching and inference history entries */
2835 SCIPhistoryFree(&(*var)->history, blkmem);
2836 SCIPhistoryFree(&(*var)->historycrun, blkmem);
2837 SCIPvaluehistoryFree(&(*var)->valuehistory, blkmem);
2838
2839 /* free variable data structure */
2840 BMSfreeBlockMemoryArray(blkmem, &(*var)->name, strlen((*var)->name)+1);
2841 BMSfreeBlockMemory(blkmem, var);
2842
2843 return SCIP_OKAY;
2844}
2845
2846/** increases usage counter of variable */
2848 SCIP_VAR* var /**< variable */
2849 )
2850{
2851 assert(var != NULL);
2852 assert(var->nuses >= 0);
2853
2854 SCIPdebugMessage("capture variable <%s> with nuses=%d\n", var->name, var->nuses);
2855 var->nuses++;
2856
2857#ifdef DEBUGUSES_VARNAME
2858 if( strcmp(var->name, DEBUGUSES_VARNAME) == 0
2859#ifdef DEBUGUSES_PROBNAME
2860 && ((var->scip->transprob != NULL && strcmp(SCIPprobGetName(var->scip->transprob), DEBUGUSES_PROBNAME) == 0) ||
2861 strcmp(SCIPprobGetName(var->scip->origprob), DEBUGUSES_PROBNAME) == 0)
2862#endif
2863 )
2864 {
2865 printf("Captured variable " DEBUGUSES_VARNAME " in SCIP %p, now %d uses; captured at\n", (void*)var->scip, var->nuses);
2866 print_backtrace();
2867 }
2868#endif
2869}
2870
2871/** decreases usage counter of variable, and frees memory if necessary */
2873 SCIP_VAR** var, /**< pointer to variable */
2874 BMS_BLKMEM* blkmem, /**< block memory */
2875 SCIP_SET* set, /**< global SCIP settings */
2876 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2877 SCIP_LP* lp /**< current LP data (or NULL, if it's an original variable) */
2878 )
2879{
2880 assert(var != NULL);
2881 assert(*var != NULL);
2882 assert((*var)->nuses >= 1);
2883 assert(blkmem != NULL);
2884 assert((*var)->scip == set->scip);
2885
2886 SCIPsetDebugMsg(set, "release variable <%s> with nuses=%d\n", (*var)->name, (*var)->nuses);
2887 (*var)->nuses--;
2888
2889#ifdef DEBUGUSES_VARNAME
2890 if( strcmp((*var)->name, DEBUGUSES_VARNAME) == 0
2891#ifdef DEBUGUSES_PROBNAME
2892 && (((*var)->scip->transprob != NULL && strcmp(SCIPprobGetName((*var)->scip->transprob), DEBUGUSES_PROBNAME) == 0) ||
2893 strcmp(SCIPprobGetName((*var)->scip->origprob), DEBUGUSES_PROBNAME) == 0)
2894#endif
2895 )
2896 {
2897 printf("Released variable " DEBUGUSES_VARNAME " in SCIP %p, now %d uses; released at\n", (void*)(*var)->scip, (*var)->nuses);
2898 print_backtrace();
2899 }
2900#endif
2901
2902 if( (*var)->nuses == 0 )
2903 {
2904 SCIP_CALL( varFree(var, blkmem, set, eventqueue, lp) );
2905 }
2906
2907 *var = NULL;
2908
2909 return SCIP_OKAY;
2910}
2911
2912/** change variable name */
2914 SCIP_VAR* var, /**< problem variable */
2915 BMS_BLKMEM* blkmem, /**< block memory */
2916 const char* name /**< name of variable */
2917 )
2918{
2919 assert(name != NULL);
2920
2921 /* remove old variable name */
2922 BMSfreeBlockMemoryArray(blkmem, &var->name, strlen(var->name)+1);
2923
2924 /* set new variable name */
2925 SCIP_CALL( varSetName(var, blkmem, NULL, name) );
2926
2927 return SCIP_OKAY;
2928}
2929
2930/** initializes variable data structure for solving */
2932 SCIP_VAR* var /**< problem variable */
2933 )
2934{
2935 assert(var != NULL);
2936
2938 var->conflictlbcount = 0;
2939 var->conflictubcount = 0;
2940}
2941
2942/** outputs the given bounds into the file stream */
2943static
2945 SCIP_SET* set, /**< global SCIP settings */
2946 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
2947 FILE* file, /**< output file (or NULL for standard output) */
2948 SCIP_Real lb, /**< lower bound */
2949 SCIP_Real ub, /**< upper bound */
2950 const char* name /**< bound type name */
2951 )
2952{
2953 assert(set != NULL);
2954
2955 SCIPmessageFPrintInfo(messagehdlr, file, ", %s=", name);
2956 if( SCIPsetIsInfinity(set, lb) )
2957 SCIPmessageFPrintInfo(messagehdlr, file, "[+inf,");
2958 else if( SCIPsetIsInfinity(set, -lb) )
2959 SCIPmessageFPrintInfo(messagehdlr, file, "[-inf,");
2960 else
2961 SCIPmessageFPrintInfo(messagehdlr, file, "[%.15g,", lb);
2962 if( SCIPsetIsInfinity(set, ub) )
2963 SCIPmessageFPrintInfo(messagehdlr, file, "+inf]");
2964 else if( SCIPsetIsInfinity(set, -ub) )
2965 SCIPmessageFPrintInfo(messagehdlr, file, "-inf]");
2966 else
2967 SCIPmessageFPrintInfo(messagehdlr, file, "%.15g]", ub);
2968}
2969
2970/** prints hole list to file stream */
2971static
2973 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
2974 FILE* file, /**< output file (or NULL for standard output) */
2975 SCIP_HOLELIST* holelist, /**< hole list pointer to hole of interest */
2976 const char* name /**< hole type name */
2977 )
2978{ /*lint --e{715}*/
2979 SCIP_Real left;
2980 SCIP_Real right;
2981
2982 if( holelist == NULL )
2983 return;
2984
2985 left = SCIPholelistGetLeft(holelist);
2986 right = SCIPholelistGetRight(holelist);
2987
2988 /* display first hole */
2989 SCIPmessageFPrintInfo(messagehdlr, file, ", %s=(%g,%g)", name, left, right);
2990 holelist = SCIPholelistGetNext(holelist);
2991
2992 while(holelist != NULL )
2993 {
2994 left = SCIPholelistGetLeft(holelist);
2995 right = SCIPholelistGetRight(holelist);
2996
2997 /* display hole */
2998 SCIPmessageFPrintInfo(messagehdlr, file, "(%g,%g)", left, right);
2999
3000 /* get next hole */
3001 holelist = SCIPholelistGetNext(holelist);
3002 }
3003}
3004
3005/** outputs variable information into file stream */
3007 SCIP_VAR* var, /**< problem variable */
3008 SCIP_SET* set, /**< global SCIP settings */
3009 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
3010 FILE* file /**< output file (or NULL for standard output) */
3011 )
3012{
3013 SCIP_HOLELIST* holelist;
3014 SCIP_Real lb;
3015 SCIP_Real ub;
3016 int i;
3017
3018 assert(var != NULL);
3019 assert(var->scip == set->scip);
3020
3021 /* type of variable */
3022 switch( SCIPvarGetType(var) )
3023 {
3025 SCIPmessageFPrintInfo(messagehdlr, file, " [binary]");
3026 break;
3028 SCIPmessageFPrintInfo(messagehdlr, file, " [integer]");
3029 break;
3031 SCIPmessageFPrintInfo(messagehdlr, file, " [implicit]");
3032 break;
3034 SCIPmessageFPrintInfo(messagehdlr, file, " [continuous]");
3035 break;
3036 default:
3037 SCIPerrorMessage("unknown variable type\n");
3038 SCIPABORT();
3039 return SCIP_ERROR; /*lint !e527*/
3040 }
3041
3042 /* name */
3043 SCIPmessageFPrintInfo(messagehdlr, file, " <%s>:", var->name);
3044
3045 /* objective value */
3046 SCIPmessageFPrintInfo(messagehdlr, file, " obj=%.15g", var->obj);
3047
3048 /* bounds (global bounds for transformed variables, original bounds for original variables) */
3049 if( !SCIPvarIsTransformed(var) )
3050 {
3051 /* output original bound */
3052 lb = SCIPvarGetLbOriginal(var);
3053 ub = SCIPvarGetUbOriginal(var);
3054 printBounds(set, messagehdlr, file, lb, ub, "original bounds");
3055
3056 /* output lazy bound */
3057 lb = SCIPvarGetLbLazy(var);
3058 ub = SCIPvarGetUbLazy(var);
3059
3060 /* only display the lazy bounds if they are different from [-infinity,infinity] */
3061 if( !SCIPsetIsInfinity(set, -lb) || !SCIPsetIsInfinity(set, ub) )
3062 printBounds(set, messagehdlr, file, lb, ub, "lazy bounds");
3063
3064 holelist = SCIPvarGetHolelistOriginal(var);
3065 printHolelist(messagehdlr, file, holelist, "original holes");
3066 }
3067 else
3068 {
3069 /* output global bound */
3070 lb = SCIPvarGetLbGlobal(var);
3071 ub = SCIPvarGetUbGlobal(var);
3072 printBounds(set, messagehdlr, file, lb, ub, "global bounds");
3073
3074 /* output local bound */
3075 lb = SCIPvarGetLbLocal(var);
3076 ub = SCIPvarGetUbLocal(var);
3077 printBounds(set, messagehdlr, file, lb, ub, "local bounds");
3078
3079 /* output lazy bound */
3080 lb = SCIPvarGetLbLazy(var);
3081 ub = SCIPvarGetUbLazy(var);
3082
3083 /* only display the lazy bounds if they are different from [-infinity,infinity] */
3084 if( !SCIPsetIsInfinity(set, -lb) || !SCIPsetIsInfinity(set, ub) )
3085 printBounds(set, messagehdlr, file, lb, ub, "lazy bounds");
3086
3087 /* global hole list */
3088 holelist = SCIPvarGetHolelistGlobal(var);
3089 printHolelist(messagehdlr, file, holelist, "global holes");
3090
3091 /* local hole list */
3092 holelist = SCIPvarGetHolelistLocal(var);
3093 printHolelist(messagehdlr, file, holelist, "local holes");
3094 }
3095
3096 /* fixings and aggregations */
3097 switch( SCIPvarGetStatus(var) )
3098 {
3102 break;
3103
3105 SCIPmessageFPrintInfo(messagehdlr, file, ", fixed:");
3106 if( SCIPsetIsInfinity(set, var->glbdom.lb) )
3107 SCIPmessageFPrintInfo(messagehdlr, file, "+inf");
3108 else if( SCIPsetIsInfinity(set, -var->glbdom.lb) )
3109 SCIPmessageFPrintInfo(messagehdlr, file, "-inf");
3110 else
3111 SCIPmessageFPrintInfo(messagehdlr, file, "%.15g", var->glbdom.lb);
3112 break;
3113
3115 SCIPmessageFPrintInfo(messagehdlr, file, ", aggregated:");
3117 SCIPmessageFPrintInfo(messagehdlr, file, " %.15g", var->data.aggregate.constant);
3118 SCIPmessageFPrintInfo(messagehdlr, file, " %+.15g<%s>", var->data.aggregate.scalar, SCIPvarGetName(var->data.aggregate.var));
3119 break;
3120
3122 SCIPmessageFPrintInfo(messagehdlr, file, ", aggregated:");
3123 if( var->data.multaggr.nvars == 0 || !SCIPsetIsZero(set, var->data.multaggr.constant) )
3124 SCIPmessageFPrintInfo(messagehdlr, file, " %.15g", var->data.multaggr.constant);
3125 for( i = 0; i < var->data.multaggr.nvars; ++i )
3126 SCIPmessageFPrintInfo(messagehdlr, file, " %+.15g<%s>", var->data.multaggr.scalars[i], SCIPvarGetName(var->data.multaggr.vars[i]));
3127 break;
3128
3130 SCIPmessageFPrintInfo(messagehdlr, file, ", negated: %.15g - <%s>", var->data.negate.constant, SCIPvarGetName(var->negatedvar));
3131 break;
3132
3133 default:
3134 SCIPerrorMessage("unknown variable status\n");
3135 SCIPABORT();
3136 return SCIP_ERROR; /*lint !e527*/
3137 }
3138
3139 SCIPmessageFPrintInfo(messagehdlr, file, "\n");
3140
3141 return SCIP_OKAY;
3142}
3143
3144/** issues a VARUNLOCKED event on the given variable */
3145static
3147 SCIP_VAR* var, /**< problem variable to change */
3148 BMS_BLKMEM* blkmem, /**< block memory */
3149 SCIP_SET* set, /**< global SCIP settings */
3150 SCIP_EVENTQUEUE* eventqueue /**< event queue */
3151 )
3152{
3153 SCIP_EVENT* event;
3154
3155 assert(var != NULL);
3156 assert(var->nlocksdown[SCIP_LOCKTYPE_MODEL] <= 1 && var->nlocksup[SCIP_LOCKTYPE_MODEL] <= 1);
3157 assert(var->scip == set->scip);
3158
3159 /* issue VARUNLOCKED event on variable */
3160 SCIP_CALL( SCIPeventCreateVarUnlocked(&event, blkmem, var) );
3161 SCIP_CALL( SCIPeventqueueAdd(eventqueue, blkmem, set, NULL, NULL, NULL, NULL, &event) );
3162
3163 return SCIP_OKAY;
3164}
3165
3166/** modifies lock numbers for rounding */
3168 SCIP_VAR* var, /**< problem variable */
3169 BMS_BLKMEM* blkmem, /**< block memory */
3170 SCIP_SET* set, /**< global SCIP settings */
3171 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3172 SCIP_LOCKTYPE locktype, /**< type of the variable locks */
3173 int addnlocksdown, /**< increase in number of rounding down locks */
3174 int addnlocksup /**< increase in number of rounding up locks */
3175 )
3176{
3177 SCIP_VAR* lockvar;
3178
3179 assert(var != NULL);
3180 assert((int)locktype >= 0 && (int)locktype < (int)NLOCKTYPES); /*lint !e685 !e568 !e587 !e650*/
3181 assert(var->nlocksup[locktype] >= 0);
3182 assert(var->nlocksdown[locktype] >= 0);
3183 assert(var->scip == set->scip);
3184
3185 if( addnlocksdown == 0 && addnlocksup == 0 )
3186 return SCIP_OKAY;
3187
3188#ifdef SCIP_DEBUG
3189 SCIPsetDebugMsg(set, "add rounding locks %d/%d to variable <%s> (locks=%d/%d, type=%u)\n",
3190 addnlocksdown, addnlocksup, var->name, var->nlocksdown[locktype], var->nlocksup[locktype], locktype);
3191#endif
3192
3193 lockvar = var;
3194
3195 while( TRUE ) /*lint !e716 */
3196 {
3197 assert(lockvar != NULL);
3198
3199 switch( SCIPvarGetStatus(lockvar) )
3200 {
3202 if( lockvar->data.original.transvar != NULL )
3203 {
3204 lockvar = lockvar->data.original.transvar;
3205 break;
3206 }
3207 else
3208 {
3209 lockvar->nlocksdown[locktype] += addnlocksdown;
3210 lockvar->nlocksup[locktype] += addnlocksup;
3211
3212 assert(lockvar->nlocksdown[locktype] >= 0);
3213 assert(lockvar->nlocksup[locktype] >= 0);
3214
3215 return SCIP_OKAY;
3216 }
3220 lockvar->nlocksdown[locktype] += addnlocksdown;
3221 lockvar->nlocksup[locktype] += addnlocksup;
3222
3223 assert(lockvar->nlocksdown[locktype] >= 0);
3224 assert(lockvar->nlocksup[locktype] >= 0);
3225
3226 if( locktype == SCIP_LOCKTYPE_MODEL && lockvar->nlocksdown[locktype] <= 1
3227 && lockvar->nlocksup[locktype] <= 1 )
3228 {
3229 SCIP_CALL( varEventVarUnlocked(lockvar, blkmem, set, eventqueue) );
3230 }
3231
3232 return SCIP_OKAY;
3234 assert(!lockvar->donotaggr);
3235
3236 if( lockvar->data.aggregate.scalar < 0.0 )
3237 {
3238 int tmp = addnlocksup;
3239
3240 addnlocksup = addnlocksdown;
3241 addnlocksdown = tmp;
3242 }
3243
3244 lockvar = lockvar->data.aggregate.var;
3245 break;
3247 {
3248 int v;
3249
3250 assert(!lockvar->donotmultaggr);
3251
3252 lockvar->nlocksdown[locktype] += addnlocksdown;
3253 lockvar->nlocksup[locktype] += addnlocksup;
3254
3255 assert(lockvar->nlocksdown[locktype] >= 0);
3256 assert(lockvar->nlocksup[locktype] >= 0);
3257
3258 for( v = lockvar->data.multaggr.nvars - 1; v >= 0; --v )
3259 {
3260 if( lockvar->data.multaggr.scalars[v] > 0.0 )
3261 {
3262 SCIP_CALL( SCIPvarAddLocks(lockvar->data.multaggr.vars[v], blkmem, set, eventqueue, locktype, addnlocksdown,
3263 addnlocksup) );
3264 }
3265 else
3266 {
3267 SCIP_CALL( SCIPvarAddLocks(lockvar->data.multaggr.vars[v], blkmem, set, eventqueue, locktype, addnlocksup,
3268 addnlocksdown) );
3269 }
3270 }
3271 return SCIP_OKAY;
3272 }
3274 {
3275 int tmp = addnlocksup;
3276
3277 assert(lockvar->negatedvar != NULL);
3279 assert(lockvar->negatedvar->negatedvar == lockvar);
3280
3281 addnlocksup = addnlocksdown;
3282 addnlocksdown = tmp;
3283
3284 lockvar = lockvar->negatedvar;
3285 break;
3286 }
3287 default:
3288 SCIPerrorMessage("unknown variable status\n");
3289 return SCIP_INVALIDDATA;
3290 }
3291 }
3292}
3293
3294/** gets number of locks for rounding down of a special type */
3296 SCIP_VAR* var, /**< problem variable */
3297 SCIP_LOCKTYPE locktype /**< type of variable locks */
3298 )
3299{
3300 int nlocks;
3301 int i;
3302
3303 assert(var != NULL);
3304 assert((int)locktype >= 0 && (int)locktype < (int)NLOCKTYPES); /*lint !e685 !e568 !e587 !e650*/
3305 assert(var->nlocksdown[locktype] >= 0);
3306
3307 switch( SCIPvarGetStatus(var) )
3308 {
3310 if( var->data.original.transvar != NULL )
3311 return SCIPvarGetNLocksDownType(var->data.original.transvar, locktype);
3312 else
3313 return var->nlocksdown[locktype];
3314
3318 return var->nlocksdown[locktype];
3319
3321 assert(!var->donotaggr);
3322 if( var->data.aggregate.scalar > 0.0 )
3323 return SCIPvarGetNLocksDownType(var->data.aggregate.var, locktype);
3324 else
3325 return SCIPvarGetNLocksUpType(var->data.aggregate.var, locktype);
3326
3328 assert(!var->donotmultaggr);
3329 nlocks = 0;
3330 for( i = 0; i < var->data.multaggr.nvars; ++i )
3331 {
3332 if( var->data.multaggr.scalars[i] > 0.0 )
3333 nlocks += SCIPvarGetNLocksDownType(var->data.multaggr.vars[i], locktype);
3334 else
3335 nlocks += SCIPvarGetNLocksUpType(var->data.multaggr.vars[i], locktype);
3336 }
3337 return nlocks;
3338
3340 assert(var->negatedvar != NULL);
3342 assert(var->negatedvar->negatedvar == var);
3343 return SCIPvarGetNLocksUpType(var->negatedvar, locktype);
3344
3345 default:
3346 SCIPerrorMessage("unknown variable status\n");
3347 SCIPABORT();
3348 return INT_MAX; /*lint !e527*/
3349 }
3350}
3351
3352/** gets number of locks for rounding up of a special type */
3354 SCIP_VAR* var, /**< problem variable */
3355 SCIP_LOCKTYPE locktype /**< type of variable locks */
3356 )
3357{
3358 int nlocks;
3359 int i;
3360
3361 assert(var != NULL);
3362 assert((int)locktype >= 0 && (int)locktype < (int)NLOCKTYPES); /*lint !e685 !e568 !e587 !e650*/
3363 assert(var->nlocksup[locktype] >= 0);
3364
3365 switch( SCIPvarGetStatus(var) )
3366 {
3368 if( var->data.original.transvar != NULL )
3369 return SCIPvarGetNLocksUpType(var->data.original.transvar, locktype);
3370 else
3371 return var->nlocksup[locktype];
3372
3376 return var->nlocksup[locktype];
3377
3379 assert(!var->donotaggr);
3380 if( var->data.aggregate.scalar > 0.0 )
3381 return SCIPvarGetNLocksUpType(var->data.aggregate.var, locktype);
3382 else
3383 return SCIPvarGetNLocksDownType(var->data.aggregate.var, locktype);
3384
3386 assert(!var->donotmultaggr);
3387 nlocks = 0;
3388 for( i = 0; i < var->data.multaggr.nvars; ++i )
3389 {
3390 if( var->data.multaggr.scalars[i] > 0.0 )
3391 nlocks += SCIPvarGetNLocksUpType(var->data.multaggr.vars[i], locktype);
3392 else
3393 nlocks += SCIPvarGetNLocksDownType(var->data.multaggr.vars[i], locktype);
3394 }
3395 return nlocks;
3396
3398 assert(var->negatedvar != NULL);
3400 assert(var->negatedvar->negatedvar == var);
3401 return SCIPvarGetNLocksDownType(var->negatedvar, locktype);
3402
3403 default:
3404 SCIPerrorMessage("unknown variable status\n");
3405 SCIPABORT();
3406 return INT_MAX; /*lint !e527*/
3407 }
3408}
3409
3410/** gets number of locks for rounding down
3411 *
3412 * @note This method will always return variable locks of type model
3413 *
3414 * @note It is recommented to use SCIPvarGetNLocksDownType()
3415 */
3417 SCIP_VAR* var /**< problem variable */
3418 )
3419{
3421}
3422
3423/** gets number of locks for rounding up
3424 *
3425 * @note This method will always return variable locks of type model
3426 *
3427 * @note It is recommented to use SCIPvarGetNLocksUpType()
3428 */
3430 SCIP_VAR* var /**< problem variable */
3431 )
3432{
3434}
3435
3436/** is it possible, to round variable down and stay feasible?
3437 *
3438 * @note This method will always check w.r.t variable locks of type model
3439 */
3441 SCIP_VAR* var /**< problem variable */
3442 )
3443{
3445}
3446
3447/** is it possible, to round variable up and stay feasible?
3448 *
3449 * @note This method will always check w.r.t. variable locks of type model
3450 */
3452 SCIP_VAR* var /**< problem variable */
3453 )
3454{
3455 return (SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) == 0);
3456}
3457
3458/** gets and captures transformed variable of a given variable; if the variable is not yet transformed,
3459 * a new transformed variable for this variable is created
3460 */
3462 SCIP_VAR* origvar, /**< original problem variable */
3463 BMS_BLKMEM* blkmem, /**< block memory of transformed problem */
3464 SCIP_SET* set, /**< global SCIP settings */
3465 SCIP_STAT* stat, /**< problem statistics */
3466 SCIP_OBJSENSE objsense, /**< objective sense of original problem; transformed is always MINIMIZE */
3467 SCIP_VAR** transvar /**< pointer to store the transformed variable */
3468 )
3469{
3470 char name[SCIP_MAXSTRLEN];
3471
3472 assert(origvar != NULL);
3473 assert(origvar->scip == set->scip);
3474 assert(SCIPvarGetStatus(origvar) == SCIP_VARSTATUS_ORIGINAL);
3475 assert(SCIPsetIsEQ(set, origvar->glbdom.lb, origvar->locdom.lb));
3476 assert(SCIPsetIsEQ(set, origvar->glbdom.ub, origvar->locdom.ub));
3477 assert(origvar->vlbs == NULL);
3478 assert(origvar->vubs == NULL);
3479 assert(transvar != NULL);
3480
3481 /* check if variable is already transformed */
3482 if( origvar->data.original.transvar != NULL )
3483 {
3484 *transvar = origvar->data.original.transvar;
3485 SCIPvarCapture(*transvar);
3486 }
3487 else
3488 {
3489 int i;
3490
3491 /* create transformed variable */
3492 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "t_%s", origvar->name);
3493 SCIP_CALL( SCIPvarCreateTransformed(transvar, blkmem, set, stat, name,
3494 origvar->glbdom.lb, origvar->glbdom.ub, (SCIP_Real)objsense * origvar->obj,
3495 SCIPvarGetType(origvar), origvar->initial, origvar->removable,
3496 origvar->vardelorig, origvar->vartrans, origvar->vardeltrans, origvar->varcopy, NULL) );
3497
3498 /* copy the branch factor and priority */
3499 (*transvar)->branchfactor = origvar->branchfactor;
3500 (*transvar)->branchpriority = origvar->branchpriority;
3501 (*transvar)->branchdirection = origvar->branchdirection; /*lint !e732*/
3502
3503 /* duplicate hole lists */
3504 SCIP_CALL( holelistDuplicate(&(*transvar)->glbdom.holelist, blkmem, set, origvar->glbdom.holelist) );
3505 SCIP_CALL( holelistDuplicate(&(*transvar)->locdom.holelist, blkmem, set, origvar->locdom.holelist) );
3506
3507 /* link original and transformed variable */
3508 origvar->data.original.transvar = *transvar;
3509 SCIP_CALL( varAddParent(*transvar, blkmem, set, origvar) );
3510
3511 /* copy rounding locks */
3512 for( i = 0; i < NLOCKTYPES; i++ )
3513 {
3514 (*transvar)->nlocksdown[i] = origvar->nlocksdown[i];
3515 (*transvar)->nlocksup[i] = origvar->nlocksup[i];
3516 assert((*transvar)->nlocksdown[i] >= 0);
3517 assert((*transvar)->nlocksup[i] >= 0);
3518 }
3519
3520 /* copy donot(mult)aggr status */
3521 (*transvar)->donotaggr = origvar->donotaggr;
3522 (*transvar)->donotmultaggr = origvar->donotmultaggr;
3523
3524 /* copy lazy bounds */
3525 (*transvar)->lazylb = origvar->lazylb;
3526 (*transvar)->lazyub = origvar->lazyub;
3527
3528 /* transfer eventual variable statistics; do not update global statistics, because this has been done
3529 * when original variable was created
3530 */
3531 SCIPhistoryUnite((*transvar)->history, origvar->history, FALSE);
3532
3533 /* transform user data */
3534 if( origvar->vartrans != NULL )
3535 {
3536 SCIP_CALL( origvar->vartrans(set->scip, origvar, origvar->vardata, *transvar, &(*transvar)->vardata) );
3537 }
3538 else
3539 (*transvar)->vardata = origvar->vardata;
3540 }
3541
3542 SCIPsetDebugMsg(set, "transformed variable: <%s>[%p] -> <%s>[%p]\n", origvar->name, (void*)origvar, (*transvar)->name, (void*)*transvar);
3543
3544 return SCIP_OKAY;
3545}
3546
3547/** gets corresponding transformed variable of an original or negated original variable */
3549 SCIP_VAR* origvar, /**< original problem variable */
3550 BMS_BLKMEM* blkmem, /**< block memory of transformed problem */
3551 SCIP_SET* set, /**< global SCIP settings */
3552 SCIP_STAT* stat, /**< problem statistics */
3553 SCIP_VAR** transvar /**< pointer to store the transformed variable, or NULL if not existing yet */
3554 )
3555{
3556 assert(origvar != NULL);
3558 assert(origvar->scip == set->scip);
3559
3561 {
3562 assert(origvar->negatedvar != NULL);
3564
3565 if( origvar->negatedvar->data.original.transvar == NULL )
3566 *transvar = NULL;
3567 else
3568 {
3569 SCIP_CALL( SCIPvarNegate(origvar->negatedvar->data.original.transvar, blkmem, set, stat, transvar) );
3570 }
3571 }
3572 else
3573 *transvar = origvar->data.original.transvar;
3574
3575 return SCIP_OKAY;
3576}
3577
3578/** converts loose transformed variable into column variable, creates LP column */
3580 SCIP_VAR* var, /**< problem variable */
3581 BMS_BLKMEM* blkmem, /**< block memory */
3582 SCIP_SET* set, /**< global SCIP settings */
3583 SCIP_STAT* stat, /**< problem statistics */
3584 SCIP_PROB* prob, /**< problem data */
3585 SCIP_LP* lp /**< current LP data */
3586 )
3587{
3588 assert(var != NULL);
3589 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE);
3590 assert(var->scip == set->scip);
3591
3592 SCIPsetDebugMsg(set, "creating column for variable <%s>\n", var->name);
3593
3594 /* switch variable status */
3595 var->varstatus = SCIP_VARSTATUS_COLUMN; /*lint !e641*/
3596
3597 /* create column of variable */
3598 SCIP_CALL( SCIPcolCreate(&var->data.col, blkmem, set, stat, var, 0, NULL, NULL, var->removable) );
3599
3600 if( var->probindex != -1 )
3601 {
3602 /* inform problem about the variable's status change */
3603 SCIP_CALL( SCIPprobVarChangedStatus(prob, blkmem, set, NULL, NULL, var) );
3604
3605 /* inform LP, that problem variable is now a column variable and no longer loose */
3606 SCIP_CALL( SCIPlpUpdateVarColumn(lp, set, var) );
3607 }
3608
3609 return SCIP_OKAY;
3610}
3611
3612/** converts column transformed variable back into loose variable, frees LP column */
3614 SCIP_VAR* var, /**< problem variable */
3615 BMS_BLKMEM* blkmem, /**< block memory */
3616 SCIP_SET* set, /**< global SCIP settings */
3617 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3618 SCIP_PROB* prob, /**< problem data */
3619 SCIP_LP* lp /**< current LP data */
3620 )
3621{
3622 assert(var != NULL);
3624 assert(var->scip == set->scip);
3625 assert(var->data.col != NULL);
3626 assert(var->data.col->lppos == -1);
3627 assert(var->data.col->lpipos == -1);
3628
3629 SCIPsetDebugMsg(set, "deleting column for variable <%s>\n", var->name);
3630
3631 /* free column of variable */
3632 SCIP_CALL( SCIPcolFree(&var->data.col, blkmem, set, eventqueue, lp) );
3633
3634 /* switch variable status */
3635 var->varstatus = SCIP_VARSTATUS_LOOSE; /*lint !e641*/
3636
3637 if( var->probindex != -1 )
3638 {
3639 /* inform problem about the variable's status change */
3640 SCIP_CALL( SCIPprobVarChangedStatus(prob, blkmem, set, NULL, NULL, var) );
3641
3642 /* inform LP, that problem variable is now a loose variable and no longer a column */
3643 SCIP_CALL( SCIPlpUpdateVarLoose(lp, set, var) );
3644 }
3645
3646 return SCIP_OKAY;
3647}
3648
3649/** issues a VARFIXED event on the given variable and all its parents (except ORIGINAL parents);
3650 * the event issuing on the parents is necessary, because unlike with bound changes, the parent variables
3651 * are not informed about a fixing of an active variable they are pointing to
3652 */
3653static
3655 SCIP_VAR* var, /**< problem variable to change */
3656 BMS_BLKMEM* blkmem, /**< block memory */
3657 SCIP_SET* set, /**< global SCIP settings */
3658 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3659 int fixeventtype /**< is this event a fixation(0), an aggregation(1), or a
3660 * multi-aggregation(2)
3661 */
3662 )
3663{
3664 SCIP_EVENT* event;
3665 SCIP_VARSTATUS varstatus;
3666 int i;
3667
3668 assert(var != NULL);
3669 assert(var->scip == set->scip);
3670 assert(0 <= fixeventtype && fixeventtype <= 2);
3671
3672 /* issue VARFIXED event on variable */
3673 SCIP_CALL( SCIPeventCreateVarFixed(&event, blkmem, var) );
3674 SCIP_CALL( SCIPeventqueueAdd(eventqueue, blkmem, set, NULL, NULL, NULL, NULL, &event) );
3675
3676#ifndef NDEBUG
3677 for( i = var->nparentvars -1; i >= 0; --i )
3678 {
3680 }
3681#endif
3682
3683 switch( fixeventtype )
3684 {
3685 case 0:
3686 /* process all parents of a fixed variable */
3687 for( i = var->nparentvars - 1; i >= 0; --i )
3688 {
3689 varstatus = SCIPvarGetStatus(var->parentvars[i]);
3690
3691 assert(varstatus != SCIP_VARSTATUS_FIXED);
3692
3693 /* issue event on all not yet fixed parent variables, (that should already issued this event) except the original
3694 * one
3695 */
3696 if( varstatus != SCIP_VARSTATUS_ORIGINAL )
3697 {
3698 SCIP_CALL( varEventVarFixed(var->parentvars[i], blkmem, set, eventqueue, fixeventtype) );
3699 }
3700 }
3701 break;
3702 case 1:
3703 /* process all parents of a aggregated variable */
3704 for( i = var->nparentvars - 1; i >= 0; --i )
3705 {
3706 varstatus = SCIPvarGetStatus(var->parentvars[i]);
3707
3708 assert(varstatus != SCIP_VARSTATUS_FIXED);
3709
3710 /* issue event for not aggregated parent variable, because for these and its parents the var event was already
3711 * issued(, except the original one)
3712 *
3713 * @note that even before an aggregated parent variable, there might be variables, for which the vent was not
3714 * yet issued
3715 */
3716 if( varstatus == SCIP_VARSTATUS_AGGREGATED )
3717 continue;
3718
3719 if( varstatus != SCIP_VARSTATUS_ORIGINAL )
3720 {
3721 SCIP_CALL( varEventVarFixed(var->parentvars[i], blkmem, set, eventqueue, fixeventtype) );
3722 }
3723 }
3724 break;
3725 case 2:
3726 /* process all parents of a aggregated variable */
3727 for( i = var->nparentvars - 1; i >= 0; --i )
3728 {
3729 varstatus = SCIPvarGetStatus(var->parentvars[i]);
3730
3731 assert(varstatus != SCIP_VARSTATUS_FIXED);
3732
3733 /* issue event on all parent variables except the original one */
3734 if( varstatus != SCIP_VARSTATUS_ORIGINAL )
3735 {
3736 SCIP_CALL( varEventVarFixed(var->parentvars[i], blkmem, set, eventqueue, fixeventtype) );
3737 }
3738 }
3739 break;
3740 default:
3741 SCIPerrorMessage("unknown variable fixation event origin\n");
3742 return SCIP_INVALIDDATA;
3743 }
3744
3745 return SCIP_OKAY;
3746}
3747
3748/** converts variable into fixed variable */
3750 SCIP_VAR* var, /**< problem variable */
3751 BMS_BLKMEM* blkmem, /**< block memory */
3752 SCIP_SET* set, /**< global SCIP settings */
3753 SCIP_STAT* stat, /**< problem statistics */
3754 SCIP_PROB* transprob, /**< tranformed problem data */
3755 SCIP_PROB* origprob, /**< original problem data */
3756 SCIP_PRIMAL* primal, /**< primal data */
3757 SCIP_TREE* tree, /**< branch and bound tree */
3758 SCIP_REOPT* reopt, /**< reoptimization data structure */
3759 SCIP_LP* lp, /**< current LP data */
3760 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
3761 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
3762 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
3763 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
3764 SCIP_Real fixedval, /**< value to fix variable at */
3765 SCIP_Bool* infeasible, /**< pointer to store whether the fixing is infeasible */
3766 SCIP_Bool* fixed /**< pointer to store whether the fixing was performed (variable was unfixed) */
3767 )
3768{
3769 SCIP_Real obj;
3770 SCIP_Real childfixedval;
3771
3772 assert(var != NULL);
3773 assert(var->scip == set->scip);
3774 assert(SCIPsetIsEQ(set, var->glbdom.lb, var->locdom.lb));
3775 assert(SCIPsetIsEQ(set, var->glbdom.ub, var->locdom.ub));
3776 assert(infeasible != NULL);
3777 assert(fixed != NULL);
3778
3779 SCIPsetDebugMsg(set, "fix variable <%s>[%g,%g] to %g\n", var->name, var->glbdom.lb, var->glbdom.ub, fixedval);
3780
3781 *infeasible = FALSE;
3782 *fixed = FALSE;
3783
3785 {
3786 *infeasible = !SCIPsetIsFeasEQ(set, fixedval, var->locdom.lb);
3787 SCIPsetDebugMsg(set, " -> variable already fixed to %g (fixedval=%g): infeasible=%u\n", var->locdom.lb, fixedval, *infeasible);
3788 return SCIP_OKAY;
3789 }
3790 else if( (SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS && !SCIPsetIsFeasIntegral(set, fixedval))
3791 || SCIPsetIsFeasLT(set, fixedval, var->locdom.lb)
3792 || SCIPsetIsFeasGT(set, fixedval, var->locdom.ub) )
3793 {
3794 SCIPsetDebugMsg(set, " -> fixing infeasible: locdom=[%g,%g], fixedval=%g\n", var->locdom.lb, var->locdom.ub, fixedval);
3795 *infeasible = TRUE;
3796 return SCIP_OKAY;
3797 }
3798
3799 switch( SCIPvarGetStatus(var) )
3800 {
3802 if( var->data.original.transvar == NULL )
3803 {
3804 SCIPerrorMessage("cannot fix an untransformed original variable\n");
3805 return SCIP_INVALIDDATA;
3806 }
3807 SCIP_CALL( SCIPvarFix(var->data.original.transvar, blkmem, set, stat, transprob, origprob, primal, tree, reopt,
3808 lp, branchcand, eventfilter, eventqueue, cliquetable, fixedval, infeasible, fixed) );
3809 break;
3810
3812 assert(!SCIPeventqueueIsDelayed(eventqueue)); /* otherwise, the pseudo objective value update gets confused */
3813
3814 /* set the fixed variable's objective value to 0.0 */
3815 obj = var->obj;
3816 SCIP_CALL( SCIPvarChgObj(var, blkmem, set, transprob, primal, lp, eventqueue, 0.0) );
3817
3818 /* since we change the variable type form loose to fixed, we have to adjust the number of loose
3819 * variables in the LP data structure; the loose objective value (looseobjval) in the LP data structure, however,
3820 * gets adjusted automatically, due to the event SCIP_EVENTTYPE_OBJCHANGED which dropped in the moment where the
3821 * objective of this variable is set to zero
3822 */
3824
3825 /* change variable's bounds to fixed value (thereby removing redundant implications and variable bounds) */
3826 holelistFree(&var->glbdom.holelist, blkmem);
3827 holelistFree(&var->locdom.holelist, blkmem);
3828 SCIP_CALL( SCIPvarChgLbGlobal(var, blkmem, set, stat, lp, branchcand, eventqueue, cliquetable, fixedval) );
3829 SCIP_CALL( SCIPvarChgUbGlobal(var, blkmem, set, stat, lp, branchcand, eventqueue, cliquetable, fixedval) );
3830
3831 if( var->glbdom.lb != var->glbdom.ub ) /*lint !e777*/
3832 {
3833 /* explicitly set variable's bounds if the fixed value was in epsilon range of the old bound (so above call didn't set bound) */
3835 {
3836 /* if not continuous variable, then make sure variable is fixed to integer value */
3837 assert(SCIPsetIsIntegral(set, fixedval));
3838 fixedval = SCIPsetRound(set, fixedval);
3839 }
3840 var->glbdom.lb = fixedval;
3841 var->glbdom.ub = fixedval;
3842 }
3843
3844 /* ensure local domain is fixed to same value as global domain */
3845 var->locdom.lb = var->glbdom.lb;
3846 var->locdom.ub = var->glbdom.ub;
3847
3848 /* delete implications and variable bounds information */
3849 SCIP_CALL( SCIPvarRemoveCliquesImplicsVbs(var, blkmem, cliquetable, set, FALSE, FALSE, TRUE) );
3850 assert(var->vlbs == NULL);
3851 assert(var->vubs == NULL);
3852 assert(var->implics == NULL);
3853
3854 /* clear the history of the variable */
3857
3858 /* convert variable into fixed variable */
3859 var->varstatus = SCIP_VARSTATUS_FIXED; /*lint !e641*/
3860
3861 /* inform problem about the variable's status change */
3862 if( var->probindex != -1 )
3863 {
3864 SCIP_CALL( SCIPprobVarChangedStatus(transprob, blkmem, set, branchcand, cliquetable, var) );
3865 }
3866
3867 /* reset the objective value of the fixed variable, thus adjusting the problem's objective offset */
3868 SCIP_CALL( SCIPvarAddObj(var, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, eventfilter, eventqueue, obj) );
3869
3870 /* issue VARFIXED event */
3871 SCIP_CALL( varEventVarFixed(var, blkmem, set, eventqueue, 0) );
3872
3873 *fixed = TRUE;
3874 break;
3875
3877 SCIPerrorMessage("cannot fix a column variable\n");
3878 return SCIP_INVALIDDATA;
3879
3881 SCIPerrorMessage("cannot fix a fixed variable again\n"); /*lint !e527*/
3882 SCIPABORT(); /* case is already handled in earlier if condition */
3883 return SCIP_INVALIDDATA; /*lint !e527*/
3884
3886 /* fix aggregation variable y in x = a*y + c, instead of fixing x directly */
3887 assert(SCIPsetIsZero(set, var->obj));
3888 assert(!SCIPsetIsZero(set, var->data.aggregate.scalar));
3889 if( SCIPsetIsInfinity(set, fixedval) || SCIPsetIsInfinity(set, -fixedval) )
3890 childfixedval = (var->data.aggregate.scalar < 0.0 ? -fixedval : fixedval);
3891 else
3892 childfixedval = (fixedval - var->data.aggregate.constant)/var->data.aggregate.scalar;
3893 SCIP_CALL( SCIPvarFix(var->data.aggregate.var, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp,
3894 branchcand, eventfilter, eventqueue, cliquetable, childfixedval, infeasible, fixed) );
3895 break;
3896
3898 SCIPerrorMessage("cannot fix a multiple aggregated variable\n");
3899 SCIPABORT();
3900 return SCIP_INVALIDDATA; /*lint !e527*/
3901
3903 /* fix negation variable x in x' = offset - x, instead of fixing x' directly */
3904 assert(SCIPsetIsZero(set, var->obj));
3905 assert(var->negatedvar != NULL);
3907 assert(var->negatedvar->negatedvar == var);
3908 SCIP_CALL( SCIPvarFix(var->negatedvar, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp,
3909 branchcand, eventfilter, eventqueue, cliquetable, var->data.negate.constant - fixedval, infeasible, fixed) );
3910 break;
3911
3912 default:
3913 SCIPerrorMessage("unknown variable status\n");
3914 return SCIP_INVALIDDATA;
3915 }
3916
3917 return SCIP_OKAY;
3918}
3919
3920/** transforms given variables, scalars and constant to the corresponding active variables, scalars and constant
3921 *
3922 * If the number of needed active variables is greater than the available slots in the variable array, nothing happens except
3923 * that the required size is stored in the corresponding variable; hence, if afterwards the required size is greater than the
3924 * available slots (varssize), nothing happens; otherwise, the active variable representation is stored in the arrays.
3925 *
3926 * The reason for this approach is that we cannot reallocate memory, since we do not know how the
3927 * memory has been allocated (e.g., by a C++ 'new' or SCIP functions).
3928 */
3930 SCIP_SET* set, /**< global SCIP settings */
3931 SCIP_VAR** vars, /**< variable array to get active variables */
3932 SCIP_Real* scalars, /**< scalars a_1, ..., a_n in linear sum a_1*x_1 + ... + a_n*x_n + c */
3933 int* nvars, /**< pointer to number of variables and values in vars and scalars array */
3934 int varssize, /**< available slots in vars and scalars array */
3935 SCIP_Real* constant, /**< pointer to constant c in linear sum a_1*x_1 + ... + a_n*x_n + c */
3936 int* requiredsize, /**< pointer to store the required array size for the active variables */
3937 SCIP_Bool mergemultiples /**< should multiple occurrences of a var be replaced by a single coeff? */
3938 )
3939{
3940 SCIP_VAR** activevars;
3941 SCIP_Real* activescalars;
3942 int nactivevars;
3943 SCIP_Real activeconstant;
3944 SCIP_Bool activeconstantinf;
3945 int activevarssize;
3946
3947 SCIP_VAR* var;
3948 SCIP_Real scalar;
3949 int v;
3950 int k;
3951
3952 SCIP_VAR** tmpvars;
3953 SCIP_VAR** multvars;
3954 SCIP_Real* tmpscalars;
3955 SCIP_Real* multscalars;
3956 int tmpvarssize;
3957 int ntmpvars;
3958 int nmultvars;
3959
3960 SCIP_VAR* multvar;
3961 SCIP_Real multscalar;
3962 SCIP_Real multconstant;
3963 int pos;
3964
3965 int noldtmpvars;
3966
3967 SCIP_VAR** tmpvars2;
3968 SCIP_Real* tmpscalars2;
3969 int tmpvarssize2;
3970 int ntmpvars2;
3971
3972 SCIP_Bool sortagain = FALSE;
3973
3974 assert(set != NULL);
3975 assert(nvars != NULL);
3976 assert(scalars != NULL || *nvars == 0);
3977 assert(constant != NULL);
3978 assert(requiredsize != NULL);
3979 assert(*nvars <= varssize);
3980
3981 *requiredsize = 0;
3982
3983 if( *nvars == 0 )
3984 return SCIP_OKAY;
3985
3986 assert(vars != NULL);
3987
3988 /* handle the "easy" case of just one variable and avoid memory allocation if the variable is already active */
3989 if( *nvars == 1 && (vars[0]->varstatus == ((int) SCIP_VARSTATUS_COLUMN) || vars[0]->varstatus == ((int) SCIP_VARSTATUS_LOOSE)) )
3990 {
3991 *requiredsize = 1;
3992
3993 return SCIP_OKAY;
3994 }
3995
3996 nactivevars = 0;
3997 activeconstant = 0.0;
3998 activeconstantinf = FALSE;
3999 activevarssize = (*nvars) * 2;
4000 ntmpvars = *nvars;
4001 tmpvarssize = *nvars;
4002
4003 tmpvarssize2 = 1;
4004
4005 /* allocate temporary memory */
4006 SCIP_CALL( SCIPsetAllocBufferArray(set, &tmpvars2, tmpvarssize2) );
4007 SCIP_CALL( SCIPsetAllocBufferArray(set, &tmpscalars2, tmpvarssize2) );
4008 SCIP_CALL( SCIPsetAllocBufferArray(set, &activevars, activevarssize) );
4009 SCIP_CALL( SCIPsetAllocBufferArray(set, &activescalars, activevarssize) );
4010 SCIP_CALL( SCIPsetDuplicateBufferArray(set, &tmpvars, vars, ntmpvars) );
4011 SCIP_CALL( SCIPsetDuplicateBufferArray(set, &tmpscalars, scalars, ntmpvars) );
4012
4013 /* to avoid unnecessary expanding of variable arrays while disaggregating several variables multiple times combine same variables
4014 * first, first get all corresponding variables with status loose, column, multaggr or fixed
4015 */
4016 for( v = ntmpvars - 1; v >= 0; --v )
4017 {
4018 var = tmpvars[v];
4019 scalar = tmpscalars[v];
4020
4021 assert(var != NULL);
4022 /* transforms given variable, scalar and constant to the corresponding active, fixed, or
4023 * multi-aggregated variable, scalar and constant; if the variable resolves to a fixed
4024 * variable, "scalar" will be 0.0 and the value of the sum will be stored in "constant".
4025 */
4026 SCIP_CALL( SCIPvarGetProbvarSum(&var, set, &scalar, &activeconstant) );
4027 assert(var != NULL);
4028
4029 assert(SCIPsetIsInfinity(set, activeconstant) == (activeconstant == SCIPsetInfinity(set))); /*lint !e777*/
4030 assert(SCIPsetIsInfinity(set, -activeconstant) == (activeconstant == -SCIPsetInfinity(set))); /*lint !e777*/
4031
4032 activeconstantinf = SCIPsetIsInfinity(set, activeconstant) || SCIPsetIsInfinity(set, -activeconstant);
4033
4038
4039 tmpvars[v] = var;
4040 tmpscalars[v] = scalar;
4041 }
4042 noldtmpvars = ntmpvars;
4043
4044 /* sort all variables to combine equal variables easily */
4045 SCIPsortPtrReal((void**)tmpvars, tmpscalars, SCIPvarComp, noldtmpvars);
4046 ntmpvars = 0;
4047 for( v = 1; v < noldtmpvars; ++v )
4048 {
4049 /* combine same variables */
4050 if( SCIPvarCompare(tmpvars[v], tmpvars[ntmpvars]) == 0 )
4051 {
4052 tmpscalars[ntmpvars] += tmpscalars[v];
4053 }
4054 else
4055 {
4056 ++ntmpvars;
4057 if( v > ntmpvars )
4058 {
4059 tmpscalars[ntmpvars] = tmpscalars[v];
4060 tmpvars[ntmpvars] = tmpvars[v];
4061 }
4062 }
4063 }
4064 ++ntmpvars;
4065
4066#ifdef SCIP_MORE_DEBUG
4067 for( v = 1; v < ntmpvars; ++v )
4068 assert(SCIPvarCompare(tmpvars[v], tmpvars[v-1]) > 0);
4069#endif
4070
4071 /* collect for each variable the representation in active variables */
4072 while( ntmpvars >= 1 )
4073 {
4074 --ntmpvars;
4075 ntmpvars2 = 0;
4076 var = tmpvars[ntmpvars];
4077 scalar = tmpscalars[ntmpvars];
4078
4079 assert(var != NULL);
4080
4081 /* TODO: maybe we should test here on SCIPsetIsZero() instead of 0.0 */
4082 if( scalar == 0.0 )
4083 continue;
4084
4089
4090 switch( SCIPvarGetStatus(var) )
4091 {
4094 /* x = a*y + c */
4095 if( nactivevars >= activevarssize )
4096 {
4097 activevarssize *= 2;
4098 SCIP_CALL( SCIPsetReallocBufferArray(set, &activevars, activevarssize) );
4099 SCIP_CALL( SCIPsetReallocBufferArray(set, &activescalars, activevarssize) );
4100 assert(nactivevars < activevarssize);
4101 }
4102 activevars[nactivevars] = var;
4103 activescalars[nactivevars] = scalar;
4104 nactivevars++;
4105 break;
4106
4108 /* x = a_1*y_1 + ... + a_n*y_n + c */
4109 nmultvars = var->data.multaggr.nvars;
4110 multvars = var->data.multaggr.vars;
4111 multscalars = var->data.multaggr.scalars;
4112 sortagain = TRUE;
4113
4114 if( nmultvars + ntmpvars > tmpvarssize )
4115 {
4116 while( nmultvars + ntmpvars > tmpvarssize )
4117 tmpvarssize *= 2;
4118 SCIP_CALL( SCIPsetReallocBufferArray(set, &tmpvars, tmpvarssize) );
4119 SCIP_CALL( SCIPsetReallocBufferArray(set, &tmpscalars, tmpvarssize) );
4120 assert(nmultvars + ntmpvars <= tmpvarssize);
4121 }
4122
4123 if( nmultvars > tmpvarssize2 )
4124 {
4125 while( nmultvars > tmpvarssize2 )
4126 tmpvarssize2 *= 2;
4127 SCIP_CALL( SCIPsetReallocBufferArray(set, &tmpvars2, tmpvarssize2) );
4128 SCIP_CALL( SCIPsetReallocBufferArray(set, &tmpscalars2, tmpvarssize2) );
4129 assert(nmultvars <= tmpvarssize2);
4130 }
4131
4132 --nmultvars;
4133
4134 for( ; nmultvars >= 0; --nmultvars )
4135 {
4136 multvar = multvars[nmultvars];
4137 multscalar = multscalars[nmultvars];
4138 multconstant = 0;
4139
4140 assert(multvar != NULL);
4141 SCIP_CALL( SCIPvarGetProbvarSum(&multvar, set, &multscalar, &multconstant) );
4142 assert(multvar != NULL);
4143
4148
4149 if( !activeconstantinf )
4150 {
4151 assert(!SCIPsetIsInfinity(set, scalar) && !SCIPsetIsInfinity(set, -scalar));
4152
4153 if( SCIPsetIsInfinity(set, multconstant) || SCIPsetIsInfinity(set, -multconstant) )
4154 {
4155 assert(scalar != 0.0);
4156 if( scalar * multconstant > 0.0 )
4157 {
4158 activeconstant = SCIPsetInfinity(set);
4159 activeconstantinf = TRUE;
4160 }
4161 else
4162 {
4163 activeconstant = -SCIPsetInfinity(set);
4164 activeconstantinf = TRUE;
4165 }
4166 }
4167 else
4168 activeconstant += scalar * multconstant;
4169 }
4170#ifndef NDEBUG
4171 else
4172 {
4173 assert(!SCIPsetIsInfinity(set, activeconstant) || !(scalar * multconstant < 0.0 &&
4174 (SCIPsetIsInfinity(set, multconstant) || SCIPsetIsInfinity(set, -multconstant))));
4175 assert(!SCIPsetIsInfinity(set, -activeconstant) || !(scalar * multconstant > 0.0 &&
4176 (SCIPsetIsInfinity(set, multconstant) || SCIPsetIsInfinity(set, -multconstant))));
4177 }
4178#endif
4179
4180 if( SCIPsortedvecFindPtr((void**)tmpvars, SCIPvarComp, multvar, ntmpvars, &pos) )
4181 {
4182 assert(SCIPvarCompare(tmpvars[pos], multvar) == 0);
4183 tmpscalars[pos] += scalar * multscalar;
4184 }
4185 else
4186 {
4187 tmpvars2[ntmpvars2] = multvar;
4188 tmpscalars2[ntmpvars2] = scalar * multscalar;
4189 ++(ntmpvars2);
4190 assert(ntmpvars2 <= tmpvarssize2);
4191 }
4192 }
4193
4194 if( ntmpvars2 > 0 )
4195 {
4196 /* sort all variables to combine equal variables easily */
4197 SCIPsortPtrReal((void**)tmpvars2, tmpscalars2, SCIPvarComp, ntmpvars2);
4198 pos = 0;
4199 for( v = 1; v < ntmpvars2; ++v )
4200 {
4201 /* combine same variables */
4202 if( SCIPvarCompare(tmpvars2[v], tmpvars2[pos]) == 0 )
4203 {
4204 tmpscalars2[pos] += tmpscalars2[v];
4205 }
4206 else
4207 {
4208 ++pos;
4209 if( v > pos )
4210 {
4211 tmpscalars2[pos] = tmpscalars2[v];
4212 tmpvars2[pos] = tmpvars2[v];
4213 }
4214 }
4215 }
4216 ntmpvars2 = pos + 1;
4217#ifdef SCIP_MORE_DEBUG
4218 for( v = 1; v < ntmpvars2; ++v )
4219 {
4220 assert(SCIPvarCompare(tmpvars2[v], tmpvars2[v-1]) > 0);
4221 }
4222 for( v = 1; v < ntmpvars; ++v )
4223 {
4224 assert(SCIPvarCompare(tmpvars[v], tmpvars[v-1]) > 0);
4225 }
4226#endif
4227 v = ntmpvars - 1;
4228 k = ntmpvars2 - 1;
4229 pos = ntmpvars + ntmpvars2 - 1;
4230 ntmpvars += ntmpvars2;
4231
4232 while( v >= 0 && k >= 0 )
4233 {
4234 assert(pos >= 0);
4235 assert(SCIPvarCompare(tmpvars[v], tmpvars2[k]) != 0);
4236 if( SCIPvarCompare(tmpvars[v], tmpvars2[k]) >= 0 )
4237 {
4238 tmpvars[pos] = tmpvars[v];
4239 tmpscalars[pos] = tmpscalars[v];
4240 --v;
4241 }
4242 else
4243 {
4244 tmpvars[pos] = tmpvars2[k];
4245 tmpscalars[pos] = tmpscalars2[k];
4246 --k;
4247 }
4248 --pos;
4249 assert(pos >= 0);
4250 }
4251 while( v >= 0 )
4252 {
4253 assert(pos >= 0);
4254 tmpvars[pos] = tmpvars[v];
4255 tmpscalars[pos] = tmpscalars[v];
4256 --v;
4257 --pos;
4258 }
4259 while( k >= 0 )
4260 {
4261 assert(pos >= 0);
4262 tmpvars[pos] = tmpvars2[k];
4263 tmpscalars[pos] = tmpscalars2[k];
4264 --k;
4265 --pos;
4266 }
4267 }
4268#ifdef SCIP_MORE_DEBUG
4269 for( v = 1; v < ntmpvars; ++v )
4270 {
4271 assert(SCIPvarCompare(tmpvars[v], tmpvars[v-1]) > 0);
4272 }
4273#endif
4274
4275 if( !activeconstantinf )
4276 {
4277 assert(!SCIPsetIsInfinity(set, scalar) && !SCIPsetIsInfinity(set, -scalar));
4278
4279 multconstant = SCIPvarGetMultaggrConstant(var);
4280
4281 if( SCIPsetIsInfinity(set, multconstant) || SCIPsetIsInfinity(set, -multconstant) )
4282 {
4283 assert(scalar != 0.0);
4284 if( scalar * multconstant > 0.0 )
4285 {
4286 activeconstant = SCIPsetInfinity(set);
4287 activeconstantinf = TRUE;
4288 }
4289 else
4290 {
4291 activeconstant = -SCIPsetInfinity(set);
4292 activeconstantinf = TRUE;
4293 }
4294 }
4295 else
4296 activeconstant += scalar * multconstant;
4297 }
4298#ifndef NDEBUG
4299 else
4300 {
4301 multconstant = SCIPvarGetMultaggrConstant(var);
4302 assert(!SCIPsetIsInfinity(set, activeconstant) || !(scalar * multconstant < 0.0 &&
4303 (SCIPsetIsInfinity(set, multconstant) || SCIPsetIsInfinity(set, -multconstant))));
4304 assert(!SCIPsetIsInfinity(set, -activeconstant) || !(scalar * multconstant > 0.0 &&
4305 (SCIPsetIsInfinity(set, multconstant) || SCIPsetIsInfinity(set, -multconstant))));
4306 }
4307#endif
4308 break;
4309
4314 default:
4315 /* case x = c, but actually we should not be here, since SCIPvarGetProbvarSum() returns a scalar of 0.0 for
4316 * fixed variables and is handled already
4317 */
4318 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED);
4319 assert(SCIPsetIsZero(set, var->glbdom.lb) && SCIPsetIsEQ(set, var->glbdom.lb, var->glbdom.ub));
4320 }
4321 }
4322
4323 if( mergemultiples )
4324 {
4325 if( sortagain )
4326 {
4327 /* sort variable and scalar array by variable index */
4328 SCIPsortPtrReal((void**)activevars, activescalars, SCIPvarComp, nactivevars);
4329
4330 /* eliminate duplicates and count required size */
4331 v = nactivevars - 1;
4332 while( v > 0 )
4333 {
4334 /* combine both variable since they are the same */
4335 if( SCIPvarCompare(activevars[v - 1], activevars[v]) == 0 )
4336 {
4337 if( activescalars[v - 1] + activescalars[v] != 0.0 )
4338 {
4339 activescalars[v - 1] += activescalars[v];
4340 --nactivevars;
4341 activevars[v] = activevars[nactivevars];
4342 activescalars[v] = activescalars[nactivevars];
4343 }
4344 else
4345 {
4346 --nactivevars;
4347 activevars[v] = activevars[nactivevars];
4348 activescalars[v] = activescalars[nactivevars];
4349 --nactivevars;
4350 --v;
4351 activevars[v] = activevars[nactivevars];
4352 activescalars[v] = activescalars[nactivevars];
4353 }
4354 }
4355 --v;
4356 }
4357 }
4358 /* the variables were added in reverse order, we revert the order now;
4359 * this should not be necessary, but not doing this changes the behavior sometimes
4360 */
4361 else
4362 {
4363 SCIP_VAR* tmpvar;
4364 SCIP_Real tmpscalar;
4365
4366 for( v = 0; v < nactivevars / 2; ++v )
4367 {
4368 tmpvar = activevars[v];
4369 tmpscalar = activescalars[v];
4370 activevars[v] = activevars[nactivevars - 1 - v];
4371 activescalars[v] = activescalars[nactivevars - 1 - v];
4372 activevars[nactivevars - 1 - v] = tmpvar;
4373 activescalars[nactivevars - 1 - v] = tmpscalar;
4374 }
4375 }
4376 }
4377 *requiredsize = nactivevars;
4378
4379 if( varssize >= *requiredsize )
4380 {
4381 assert(vars != NULL);
4382
4383 *nvars = *requiredsize;
4384
4385 if( !SCIPsetIsInfinity(set, *constant) && !SCIPsetIsInfinity(set, -(*constant)) )
4386 {
4387 /* if the activeconstant is infinite, the constant pointer gets the same value, otherwise add the value */
4388 if( activeconstantinf )
4389 (*constant) = activeconstant;
4390 else
4391 (*constant) += activeconstant;
4392 }
4393#ifndef NDEBUG
4394 else
4395 {
4396 assert(!SCIPsetIsInfinity(set, (*constant)) || !SCIPsetIsInfinity(set, -activeconstant));
4397 assert(!SCIPsetIsInfinity(set, -(*constant)) || !SCIPsetIsInfinity(set, activeconstant));
4398 }
4399#endif
4400
4401 /* copy active variable and scalar array to the given arrays */
4402 for( v = 0; v < *nvars; ++v )
4403 {
4404 vars[v] = activevars[v];
4405 scalars[v] = activescalars[v]; /*lint !e613*/
4406 }
4407 }
4408
4409 assert(SCIPsetIsInfinity(set, *constant) == ((*constant) == SCIPsetInfinity(set))); /*lint !e777*/
4410 assert(SCIPsetIsInfinity(set, -(*constant)) == ((*constant) == -SCIPsetInfinity(set))); /*lint !e777*/
4411
4412 SCIPsetFreeBufferArray(set, &tmpscalars);
4413 SCIPsetFreeBufferArray(set, &tmpvars);
4414 SCIPsetFreeBufferArray(set, &activescalars);
4415 SCIPsetFreeBufferArray(set, &activevars);
4416 SCIPsetFreeBufferArray(set, &tmpscalars2);
4417 SCIPsetFreeBufferArray(set, &tmpvars2);
4418
4419 return SCIP_OKAY;
4420}
4421
4422
4423/** flattens aggregation graph of multi-aggregated variable in order to avoid exponential recursion later on */
4425 SCIP_VAR* var, /**< problem variable */
4426 BMS_BLKMEM* blkmem, /**< block memory */
4427 SCIP_SET* set, /**< global SCIP settings */
4428 SCIP_EVENTQUEUE* eventqueue /**< event queue */
4429 )
4430{
4431 int nlocksup[NLOCKTYPES];
4432 int nlocksdown[NLOCKTYPES];
4433 SCIP_Real multconstant;
4434 int multvarssize;
4435 int nmultvars;
4436 int multrequiredsize;
4437 int i;
4438
4439 assert( var != NULL );
4440 assert( SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR );
4441 assert(var->scip == set->scip);
4442
4443 /* in order to update the locks on the active representation of the multi-aggregated variable, we remove all locks
4444 * on the current representation now and re-add the locks once the variable graph has been flattened, which
4445 * may lead to duplicate occurences of the same variable being merged
4446 *
4447 * Here is an example. Assume we have the multi-aggregation z = x + y.
4448 * z occures with positive coefficient in a <= constraint c1, so it has an uplock from there.
4449 * When the multi-aggregation is performed, all locks are added to the active representation,
4450 * so x and y both get an uplock from c1. However, z was not yet replaced by x + y in c1.
4451 * Next, a negation y = 1 - x is identified. Again, locks are moved, so that the uplock of y originating
4452 * from c1 is added to x as a downlock. Thus, x has both an up- and downlock from c1.
4453 * The multi-aggregation changes to z = x + 1 - x, which corresponds to the locks.
4454 * However, before z is replaced by that sum, SCIPvarFlattenAggregationGraph() is called
4455 * which changes z = x + y = x + 1 - x = 1, since it merges multiple occurences of the same variable.
4456 * The up- and downlock of x, however, is not removed when replacing z in c1 by its active representation,
4457 * because it is just 1 now. Therefore, we need to update locks when flattening the aggregation graph.
4458 * For this, the multi-aggregated variable knows its locks in addition to adding them to the active
4459 * representation, which corresponds to the locks from constraints where the variable was not replaced yet.
4460 * By removing the locks here, based on the old representation and adding them again after flattening,
4461 * we ensure that the locks are correct afterwards if coefficients were merged.
4462 */
4463 for( i = 0; i < NLOCKTYPES; ++i )
4464 {
4465 nlocksup[i] = var->nlocksup[i];
4466 nlocksdown[i] = var->nlocksdown[i];
4467
4468 SCIP_CALL( SCIPvarAddLocks(var, blkmem, set, eventqueue, (SCIP_LOCKTYPE) i, -nlocksdown[i], -nlocksup[i]) );
4469 }
4470
4471 multconstant = var->data.multaggr.constant;
4472 nmultvars = var->data.multaggr.nvars;
4473 multvarssize = var->data.multaggr.varssize;
4474
4475 SCIP_CALL( SCIPvarGetActiveRepresentatives(set, var->data.multaggr.vars, var->data.multaggr.scalars, &nmultvars, multvarssize, &multconstant, &multrequiredsize, TRUE) );
4476
4477 if( multrequiredsize > multvarssize )
4478 {
4479 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(var->data.multaggr.vars), multvarssize, multrequiredsize) );
4480 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(var->data.multaggr.scalars), multvarssize, multrequiredsize) );
4481 multvarssize = multrequiredsize;
4482 SCIP_CALL( SCIPvarGetActiveRepresentatives(set, var->data.multaggr.vars, var->data.multaggr.scalars, &nmultvars, multvarssize, &multconstant, &multrequiredsize, TRUE) );
4483 assert( multrequiredsize <= multvarssize );
4484 }
4485 /**@note After the flattening the multi aggregation might resolve to be in fact an aggregation (or even a fixing?).
4486 * This issue is not resolved right now, since var->data.multaggr.nvars < 2 should not cause troubles. However, one
4487 * may loose performance hereby, since aggregated variables are easier to handle.
4488 *
4489 * Note, that there are two cases where SCIPvarFlattenAggregationGraph() is called: The easier one is that it is
4490 * called while installing the multi-aggregation. in principle, the described issue could be handled straightforward
4491 * in this case by aggregating or fixing the variable instead. The more complicated case is the one, when the
4492 * multi-aggregation is used, e.g., in linear presolving (and the variable is already declared to be multi-aggregated).
4493 *
4494 * By now, it is not allowed to fix or aggregate multi-aggregated variables which would be necessary in this case.
4495 *
4496 * The same issue appears in the SCIPvarGetProbvar...() methods.
4497 */
4498
4499 var->data.multaggr.constant = multconstant;
4500 var->data.multaggr.nvars = nmultvars;
4501 var->data.multaggr.varssize = multvarssize;
4502
4503 for( i = 0; i < NLOCKTYPES; ++i )
4504 {
4505 SCIP_CALL( SCIPvarAddLocks(var, blkmem, set, eventqueue, (SCIP_LOCKTYPE) i, nlocksdown[i], nlocksup[i]) );
4506 }
4507
4508 return SCIP_OKAY;
4509}
4510
4511/** merge two variable histories together; a typical use case is that \p othervar is an image of the target variable
4512 * in a SCIP copy. Method should be applied with care, especially because no internal checks are performed whether
4513 * the history merge is reasonable
4514 *
4515 * @note Do not use this method if the two variables originate from two SCIP's with different objective functions, since
4516 * this corrupts the variable pseudo costs
4517 * @note Apply with care; no internal checks are performed if the two variables should be merged
4518 */
4520 SCIP_VAR* targetvar, /**< the variable that should contain both histories afterwards */
4521 SCIP_VAR* othervar, /**< the variable whose history is to be merged with that of the target variable */
4522 SCIP_STAT* stat /**< problem statistics */
4523 )
4524{
4525 /* merge only the history of the current run into the target history */
4526 SCIPhistoryUnite(targetvar->history, othervar->historycrun, FALSE);
4527
4528 /* apply the changes also to the global history */
4529 SCIPhistoryUnite(stat->glbhistory, othervar->historycrun, FALSE);
4530}
4531
4532/** sets the history of a variable; this method is typically used within reoptimization to keep and update the variable
4533 * history over several iterations
4534 */
4536 SCIP_VAR* var, /**< variable */
4537 SCIP_HISTORY* history, /**< the history which is to set */
4538 SCIP_STAT* stat /**< problem statistics */
4539 )
4540{
4541 /* merge only the history of the current run into the target history */
4542 SCIPhistoryUnite(var->history, history, FALSE);
4543
4544 /* apply the changes also to the global history */
4545 SCIPhistoryUnite(stat->glbhistory, history, FALSE);
4546}
4547
4548/** tightens the bounds of both variables in aggregation x = a*y + c */
4549static
4551 SCIP_VAR* var, /**< problem variable */
4552 BMS_BLKMEM* blkmem, /**< block memory */
4553 SCIP_SET* set, /**< global SCIP settings */
4554 SCIP_STAT* stat, /**< problem statistics */
4555 SCIP_PROB* transprob, /**< tranformed problem data */
4556 SCIP_PROB* origprob, /**< original problem data */
4557 SCIP_PRIMAL* primal, /**< primal data */
4558 SCIP_TREE* tree, /**< branch and bound tree */
4559 SCIP_REOPT* reopt, /**< reoptimization data structure */
4560 SCIP_LP* lp, /**< current LP data */
4561 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
4562 SCIP_EVENTFILTER* eventfilter, /**< event filter for global (not variable dependent) events */
4563 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
4564 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
4565 SCIP_VAR* aggvar, /**< variable y in aggregation x = a*y + c */
4566 SCIP_Real scalar, /**< multiplier a in aggregation x = a*y + c */
4567 SCIP_Real constant, /**< constant shift c in aggregation x = a*y + c */
4568 SCIP_Bool* infeasible, /**< pointer to store whether the aggregation is infeasible */
4569 SCIP_Bool* fixed /**< pointer to store whether the variables were fixed */
4570 )
4571{
4572 SCIP_Real varlb;
4573 SCIP_Real varub;
4574 SCIP_Real aggvarlb;
4575 SCIP_Real aggvarub;
4576 SCIP_Bool aggvarbdschanged;
4577
4578 assert(var != NULL);
4579 assert(var->scip == set->scip);
4580 assert(aggvar != NULL);
4581 assert(!SCIPsetIsZero(set, scalar));
4582 assert(infeasible != NULL);
4583 assert(fixed != NULL);
4584
4585 *infeasible = FALSE;
4586 *fixed = FALSE;
4587
4588 SCIPsetDebugMsg(set, "updating bounds of variables in aggregation <%s> == %g*<%s> %+g\n", var->name, scalar, aggvar->name, constant);
4589 SCIPsetDebugMsg(set, " old bounds: <%s> [%g,%g] <%s> [%g,%g]\n",
4590 var->name, var->glbdom.lb, var->glbdom.ub, aggvar->name, aggvar->glbdom.lb, aggvar->glbdom.ub);
4591
4592 /* loop as long additional changes may be found */
4593 do
4594 {
4595 aggvarbdschanged = FALSE;
4596
4597 /* update the bounds of the aggregated variable x in x = a*y + c */
4598 if( scalar > 0.0 )
4599 {
4600 if( SCIPsetIsInfinity(set, -aggvar->glbdom.lb) )
4601 varlb = -SCIPsetInfinity(set);
4602 else
4603 varlb = aggvar->glbdom.lb * scalar + constant;
4604 if( SCIPsetIsInfinity(set, aggvar->glbdom.ub) )
4605 varub = SCIPsetInfinity(set);
4606 else
4607 varub = aggvar->glbdom.ub * scalar + constant;
4608 }
4609 else
4610 {
4611 if( SCIPsetIsInfinity(set, -aggvar->glbdom.lb) )
4612 varub = SCIPsetInfinity(set);
4613 else
4614 varub = aggvar->glbdom.lb * scalar + constant;
4615 if( SCIPsetIsInfinity(set, aggvar->glbdom.ub) )
4616 varlb = -SCIPsetInfinity(set);
4617 else
4618 varlb = aggvar->glbdom.ub * scalar + constant;
4619 }
4620 varlb = MAX(varlb, var->glbdom.lb);
4621 varub = MIN(varub, var->glbdom.ub);
4622 SCIPvarAdjustLb(var, set, &varlb);
4623 SCIPvarAdjustUb(var, set, &varub);
4624
4625 /* check the new bounds */
4626 if( SCIPsetIsGT(set, varlb, varub) )
4627 {
4628 /* the aggregation is infeasible */
4629 *infeasible = TRUE;
4630 return SCIP_OKAY;
4631 }
4632 else if( SCIPsetIsEQ(set, varlb, varub) )
4633 {
4634 /* the aggregated variable is fixed -> fix both variables */
4635 SCIP_CALL( SCIPvarFix(var, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand,
4636 eventfilter, eventqueue, cliquetable, varlb, infeasible, fixed) );
4637 if( !(*infeasible) )
4638 {
4639 SCIP_Bool aggfixed;
4640
4641 SCIP_CALL( SCIPvarFix(aggvar, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand,
4642 eventfilter, eventqueue, cliquetable, (varlb-constant)/scalar, infeasible, &aggfixed) );
4643 assert(*fixed == aggfixed);
4644 }
4645 return SCIP_OKAY;
4646 }
4647 else
4648 {
4649 if( SCIPsetIsGT(set, varlb, var->glbdom.lb) )
4650 {
4651 SCIP_CALL( SCIPvarChgLbGlobal(var, blkmem, set, stat, lp, branchcand, eventqueue, cliquetable, varlb) );
4652 }
4653 if( SCIPsetIsLT(set, varub, var->glbdom.ub) )
4654 {
4655 SCIP_CALL( SCIPvarChgUbGlobal(var, blkmem, set, stat, lp, branchcand, eventqueue, cliquetable, varub) );
4656 }
4657
4658 /* update the hole list of the aggregation variable */
4659 /**@todo update hole list of aggregation variable */
4660 }
4661
4662 /* update the bounds of the aggregation variable y in x = a*y + c -> y = (x-c)/a */
4663 if( scalar > 0.0 )
4664 {
4665 if( SCIPsetIsInfinity(set, -var->glbdom.lb) )
4666 aggvarlb = -SCIPsetInfinity(set);
4667 else
4668 aggvarlb = (var->glbdom.lb - constant) / scalar;
4669 if( SCIPsetIsInfinity(set, var->glbdom.ub) )
4670 aggvarub = SCIPsetInfinity(set);
4671 else
4672 aggvarub = (var->glbdom.ub - constant) / scalar;
4673 }
4674 else
4675 {
4676 if( SCIPsetIsInfinity(set, -var->glbdom.lb) )
4677 aggvarub = SCIPsetInfinity(set);
4678 else
4679 aggvarub = (var->glbdom.lb - constant) / scalar;
4680 if( SCIPsetIsInfinity(set, var->glbdom.ub) )
4681 aggvarlb = -SCIPsetInfinity(set);
4682 else
4683 aggvarlb = (var->glbdom.ub - constant) / scalar;
4684 }
4685 aggvarlb = MAX(aggvarlb, aggvar->glbdom.lb);
4686 aggvarub = MIN(aggvarub, aggvar->glbdom.ub);
4687 SCIPvarAdjustLb(aggvar, set, &aggvarlb);
4688 SCIPvarAdjustUb(aggvar, set, &aggvarub);
4689
4690 /* check the new bounds */
4691 if( SCIPsetIsGT(set, aggvarlb, aggvarub) )
4692 {
4693 /* the aggregation is infeasible */
4694 *infeasible = TRUE;
4695 return SCIP_OKAY;
4696 }
4697 else if( SCIPsetIsEQ(set, aggvarlb, aggvarub) )
4698 {
4699 /* the aggregation variable is fixed -> fix both variables */
4700 SCIP_CALL( SCIPvarFix(aggvar, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand,
4701 eventfilter, eventqueue, cliquetable, aggvarlb, infeasible, fixed) );
4702 if( !(*infeasible) )
4703 {
4704 SCIP_Bool varfixed;
4705
4706 SCIP_CALL( SCIPvarFix(var, blkmem, set, stat, transprob, origprob, primal, tree, reopt, lp, branchcand,
4707 eventfilter, eventqueue, cliquetable, aggvarlb * scalar + constant, infeasible, &varfixed) );
4708 assert(*fixed == varfixed);
4709 }
4710 return SCIP_OKAY;
4711 }
4712 else
4713 {
4714 SCIP_Real oldbd;
4715 if( SCIPsetIsGT(set, aggvarlb, aggvar->glbdom.lb) )
4716 {
4717 oldbd = aggvar->glbdom.lb;
4718 SCIP_CALL( SCIPvarChgLbGlobal(aggvar, blkmem, set, stat, lp, branchcand, eventqueue, cliquetable, aggvarlb) );
4719 aggvarbdschanged = !SCIPsetIsEQ(set, oldbd, aggvar->glbdom.lb);
4720 }
4721 if( SCIPsetIsLT(set, aggvarub, aggvar->glbdom.ub) )
4722 {
4723 oldbd = aggvar->glbdom.ub;
4724 SCIP_CALL( SCIPvarChgUbGlobal(aggvar, blkmem, set, stat, lp, branchcand, eventqueue, cliquetable, aggvarub) );
4725 aggvarbdschanged = aggvarbdschanged || !SCIPsetIsEQ(set, oldbd, aggvar->glbdom.ub);
4726 }
4727
4728 /* update the hole list of the aggregation variable */
4729 /**@todo update hole list of aggregation variable */
4730 }
4731 }
4732 while( aggvarbdschanged );
4733
4734 SCIPsetDebugMsg(set, " new bounds: <%s> [%g,%g] <%s> [%g,%g]\n",
4735 var->name, var->glbdom.lb, var->glbdom.ub, aggvar->name, aggvar->glbdom.lb, aggvar->glbdom.ub);
4736
4737 return SCIP_OKAY;
4738}
4739
4740/** converts loose variable into aggregated variable */
4742 SCIP_VAR* var, /**< loose problem variable */
4743 BMS_BLKMEM* blkmem, /**< block memory */
4744 SCIP_SET* set, /**< global SCIP settings */
4745 SCIP_STAT* stat, /**< problem statistics */
4746 SCIP_PROB* transprob, /**< tranformed problem data */
4747 SCIP_PROB* origprob, /**< original problem data */
4748 SCIP_PRIMAL* primal, /**< primal data */
4749 SCIP_TREE* tree, /**< branch and bound tree */
4750 SCIP_REOPT* reopt, /**< reoptimization data structure */
4751 SCIP_LP* lp, /**< current LP data */