Scippy

SCIP

Solving Constraint Integer Programs

presolve.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-2014 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file presolve.c
17  * @brief methods for presolving
18  * @author Michael Winkler
19  */
20 
21 /* all general presolving methods (not working on any specific kind of data(, e.g. consdata) should be implemented here */
22 
23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
24 
25 #include "scip/mem.h"
26 #include "scip/presolve.h"
27 #include "scip/prob.h"
28 #include "scip/tree.h"
29 #include "scip/solve.h"
30 #include "scip/struct_scip.h"
31 
32 /*
33  * Local methods
34  */
35 
36 /** collect variable bound information for a avraibel set reduction and global implication, only variable which have the
37  * vartype != SCIP_VARTYPE_BINARY have variable bounds
38  */
39 static
40 void collectNonBinaryVBoundData(
41  SCIP* scip, /**< SCIP data structure */
42  SCIP_VAR* var, /**< set variable */
43  int varidx, /**< for lower bound set variable index, for upper bound set variable index
44  * + number of variables
45  */
46  int pos, /**< variables's position in bdchinfos */
47  SCIP_Real* bounds, /**< array of bounds where one of them must be fullfilled */
48  SCIP_Bool* boundtypes, /**< array of bound types */
49  SCIP_Real* newbounds, /**< array of implied bounds(, size is two times number of variables, first
50  * half for implied lower bounds, second for implied upper bounds)
51  */
52  int* counts, /**< array of number of implication on a bound (, size is two times number
53  * of variables, first half for implied lower bounds, second for implied
54  * upper bounds)
55  */
56  int* issetvar, /**< array containing for set variables the position in the current set, or
57  * 0 if it is not a set variable or -1, if it is a redundant(i.e. implies
58  * another set variable) set variables(, size is two times number of
59  * variables, first half for implied lower bounds, second for implied
60  * upper bounds) */
61  int nvars, /**< number of problem variables */
62  int* foundbin, /**< pointer to store the lowest index of a binary implication variable
63  * when found
64  */
65  int* foundnonbin, /**< pointer to store the lowest index of a non-binary implication variable
66  * when found
67  */
68  int* implidx, /**< array to store the variable indices (for upper bound 'nvars' is added
69  * to the index) which are implied
70  */
71  int* nimplidx, /**< pointer to store the number of implied variables */
72  SCIP_Real* lastbounds /**< array to remember last implied bounds before taken the current
73  * variable into account, first nvars for lower bound, second nvars for
74  * upper bound
75  *
76  * this array is used when a set variable got redundant, because it
77  * implies another set variable, and we need to correct the counts array
78  */
79  )
80 {
81  SCIP_VAR** implvars;
82  SCIP_Real* implcoefs;
83  SCIP_Real* implconsts;
84  int nimpls;
85  int idx;
86  int w;
87 
88  assert(scip != NULL);
89  assert(var != NULL);
90  assert(SCIPvarGetType(var) != SCIP_VARTYPE_BINARY);
91  assert(varidx >= 0);
92  assert(pos >= 0);
93  assert(bounds != NULL);
94  assert(boundtypes != NULL);
95  assert(newbounds != NULL);
96  assert(counts != NULL);
97  assert(issetvar != NULL);
98  assert(2 * nvars > varidx);
99  assert(foundbin != NULL);
100  assert(foundnonbin != NULL);
101  assert(implidx != NULL);
102  assert(nimplidx != NULL);
103  assert(lastbounds != NULL);
104 
105  /* 1. case: lower bound in set */
106  if( !boundtypes[pos] )
107  {
108  /* update implication counter of set variable */
109  if( counts[varidx] == pos )
110  {
111  ++counts[varidx];
112 
113  if( counts[varidx] == 1 )
114  newbounds[varidx] = bounds[pos];
115  else if( newbounds[varidx] > bounds[pos] )
116  newbounds[varidx] = bounds[pos];
117 
118  *foundnonbin = MIN(*foundnonbin, varidx);
119 
120  implidx[*nimplidx] = varidx;
121  ++(*nimplidx);
122  }
123 
124  nimpls = SCIPvarGetNVubs(var);
125  implvars = SCIPvarGetVubVars(var);
126  implcoefs = SCIPvarGetVubCoefs(var);
127  implconsts = SCIPvarGetVubConstants(var);
128 
129  for( w = nimpls - 1; w >= 0; --w )
130  {
131  assert(!SCIPisZero(scip, implcoefs[w]));
132  idx = SCIPvarGetProbindex(implvars[w]);
133 
134  /* do not use inactive variables */
135  /* @todo if implvars[x] is aggregated, we could transform the variable into the active representation */
136  if( idx < 0 || SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(implvars[w]), SCIPvarGetUbGlobal(implvars[w])) )
137  continue;
138 
139  /* the upper bound of implvars[w] is bounding upper bound of var */
140  if( implcoefs[w] < 0.0 )
141  {
142  /* update the counters and implied bounds */
143  idx += nvars;
144 
145  if( counts[idx] == pos )
146  {
147  if( SCIPvarIsBinary(implvars[w]) )
148  {
149  /* do not look at fixed variables */
150  if( SCIPvarGetLbGlobal(implvars[w]) > 0.5 || SCIPvarGetUbGlobal(implvars[w]) < 0.5 )
151  continue;
152 
153  /* (implvars[w] = 1 ===> var <= implcoefs[w] + implconsts[w] and if implcoefs[w] +
154  * implconsts[w] < bounds[pos]) ===> (because var => bounds[v] ===> implvars[w] = 0)
155  */
156  if( SCIPisFeasLT(scip, implcoefs[w] + implconsts[w], bounds[pos]) )
157  {
158  /* set variable 'var' with bound implies other set variable 'implvars[w]' with corresponding bound
159  * so we can remove the set variable 'var'
160  */
161  if( issetvar[idx] > 0 )
162  {
163  SCIPdebugMessage("set variable <%s> %s %g implies other set variable <%s> %s %g\n", SCIPvarGetName(var), ">=", bounds[pos], SCIPvarGetName(implvars[w]), "<=", 0.0);
164 
165  issetvar[varidx] = -1;
166  break;
167  }
168 
169  ++counts[idx];
170  *foundbin = MIN(*foundbin, idx);
171 
172  implidx[*nimplidx] = idx;
173  ++(*nimplidx);
174  }
175  }
176  /* if (implvars[w] = ub(implvars[w]) ==> var <= implcoefs[w]*SCIPvarGetUbGlobal(implvars[w]) +
177  * implconsts[w]) but (var >= bounds[pos] with bounds[pos] >
178  * implcoefs[w]*SCIPvarGetUbGlobal(implvars[w]) + implconsts[w]) it follows (new_ub(var) <
179  * ub(var))
180  */
181  else if( SCIPisFeasLT(scip, implcoefs[w] * SCIPvarGetUbGlobal(implvars[w]) + implconsts[w], bounds[pos]) )
182  {
183  SCIP_Real newub;
184 
185  newub = (bounds[pos] - implconsts[w]) / implcoefs[w];
186 
187  /* set variable 'var' with bound implies other set variable 'implvars[w]' with corresponding bound so
188  * we can remove the set variable 'var'
189  */
190  if( issetvar[idx] > 0 && newub <= bounds[issetvar[idx] - 1] )
191  {
192  SCIPdebugMessage("set variable <%s> %s %g implies other set variable <%s> %s %g (%g)\n", SCIPvarGetName(var), ">=", bounds[pos], SCIPvarGetName(implvars[w]), "<=", newub, bounds[issetvar[idx] - 1] );
193 
194  issetvar[varidx] = -1;
195  break;
196  }
197 
198  ++counts[idx];
199 
200  if( counts[idx] == 1 )
201  {
202  newbounds[idx] = newub;
203  lastbounds[*nimplidx] = SCIP_INVALID;
204  }
205  else if( newbounds[idx] < newub )
206  {
207  lastbounds[*nimplidx] = newbounds[idx];
208  newbounds[idx] = newub;
209  }
210  else
211  lastbounds[*nimplidx] = SCIP_INVALID;
212 
213  *foundnonbin = MIN(*foundnonbin, idx);
214 
215  implidx[*nimplidx] = idx;
216  ++(*nimplidx);
217  }
218  }
219  }
220  else
221  {
222  /* update the counters and implied bounds */
223  if( counts[idx] == pos )
224  {
225  if( SCIPvarIsBinary(implvars[w]) )
226  {
227  /* do not look at fixed variables */
228  if( SCIPvarGetLbGlobal(implvars[w]) > 0.5 || SCIPvarGetUbGlobal(implvars[w]) < 0.5 )
229  continue;
230 
231  /* (implvars[w] = 0 ===> var <= implconsts[w] and if implconsts[w] < bounds[pos]) ===> (because
232  * var >= bounds[pos] ===> implvars[w] = 1)
233  */
234  if( SCIPisFeasLT(scip, implconsts[w], bounds[pos]) )
235  {
236  /* set variable 'var' with bound implies other set variable 'implvars[w]' with corresponding bound
237  * so we can remove the set variable 'var'
238  */
239  if( issetvar[idx] > 0 )
240  {
241  SCIPdebugMessage("set variable <%s> %s %g implies other set variable <%s> %s %g\n", SCIPvarGetName(var), ">=", bounds[pos], SCIPvarGetName(implvars[w]), ">=", 1.0);
242 
243  issetvar[varidx] = -1;
244  break;
245  }
246 
247  ++counts[idx];
248  *foundbin = MIN(*foundbin, idx);
249 
250  implidx[*nimplidx] = idx;
251  ++(*nimplidx);
252  }
253  }
254  /* if (implvars[w] = lb(implvars[w]) => var <= implcoefs[w]*SCIPvarGetLbGlobal(implvars[w]) +
255  * implconsts[w]) but (var >= bounds[pos] with bounds[pos] >
256  * implcoefs[w]*SCIPvarGetLbGlobal(implvars[w]) + implconsts[w]) it follows (new_lb(var) >
257  * lb(var))
258  */
259  else if( SCIPisFeasLT(scip, implcoefs[w]*SCIPvarGetLbGlobal(implvars[w]) + implconsts[w], bounds[pos]) )
260  {
261  SCIP_Real newlb;
262 
263  newlb = (bounds[pos] - implconsts[w]) / implcoefs[w];
264 
265  /* set variable 'var' with bound implies other set variable 'implvars[w]' with corresponding bound so
266  * we can remove the set variable 'var'
267  */
268  if( issetvar[idx] > 0 && newlb >= bounds[issetvar[idx] - 1] )
269  {
270  SCIPdebugMessage("set variable <%s> %s %g implies other set variable <%s> %s %g (%g)\n", SCIPvarGetName(var), ">=", bounds[pos], SCIPvarGetName(implvars[w]), ">=", newlb, bounds[issetvar[idx] - 1] );
271 
272  issetvar[varidx] = -1;
273  break;
274  }
275 
276  ++counts[idx];
277 
278  if( counts[idx] == 1 )
279  {
280  lastbounds[*nimplidx] = SCIP_INVALID;
281  newbounds[idx] = newlb;
282  }
283  else if( newbounds[idx] > newlb )
284  {
285  lastbounds[*nimplidx] = newbounds[idx];
286  newbounds[idx] = newlb;
287  }
288  else
289  lastbounds[*nimplidx] = SCIP_INVALID;
290 
291 
292  *foundnonbin = MIN(*foundnonbin, idx);
293 
294  implidx[*nimplidx] = idx;
295  ++(*nimplidx);
296  }
297  }
298  }
299  }
300  }
301  /* 2.case: upper bound in set */
302  else
303  {
304  assert(boundtypes[pos]);
305 
306  /* update implication counter of set variable */
307  if( counts[varidx] == pos )
308  {
309  ++counts[varidx];
310 
311  if( counts[varidx] == 1 )
312  newbounds[varidx] = bounds[pos];
313  else if( newbounds[varidx] < bounds[pos] )
314  newbounds[varidx] = bounds[pos];
315 
316  *foundnonbin = MIN(*foundnonbin, varidx);
317 
318  implidx[*nimplidx] = varidx;
319  ++(*nimplidx);
320  }
321 
322  nimpls = SCIPvarGetNVlbs(var);
323  implvars = SCIPvarGetVlbVars(var);
324  implcoefs = SCIPvarGetVlbCoefs(var);
325  implconsts = SCIPvarGetVlbConstants(var);
326 
327  for( w = nimpls - 1; w >= 0; --w )
328  {
329  assert(!SCIPisZero(scip, implcoefs[w]));
330  idx = SCIPvarGetProbindex(implvars[w]);
331 
332  /* do not use inactive variables */
333  /* @todo if implvars[x] is aggregated, we could transform the variable into the active representation */
334  if( idx < 0 || SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(implvars[w]), SCIPvarGetUbGlobal(implvars[w])) )
335  continue;
336 
337  /* the lower bound of implvars[w] is bounding lower bound of var */
338  if( implcoefs[w] < 0.0 )
339  {
340  /* update the counters and implied bounds */
341  if( counts[idx] == pos )
342  {
343  if( SCIPvarIsBinary(implvars[w]) )
344  {
345  /* do not look at fixed variables */
346  if( SCIPvarGetLbGlobal(implvars[w]) > 0.5 || SCIPvarGetUbGlobal(implvars[w]) < 0.5 )
347  continue;
348 
349  /* (implvars[w] = 0 ===> var >= implconsts[w] and if implconsts[w] > bounds[pos]) ===> (because
350  * var <= bounds[pos] ===> implvars[w] = 1)
351  */
352  if( SCIPisFeasGT(scip, implconsts[w], bounds[pos]) )
353  {
354  if( issetvar[idx] > 0 )
355  {
356  SCIPdebugMessage("set variable <%s> %s %g implies other set variable <%s> %s %g\n", SCIPvarGetName(var), "<=", bounds[pos], SCIPvarGetName(implvars[w]), ">=", 1.0);
357 
358  issetvar[varidx] = -1;
359  break;
360  }
361 
362  ++counts[idx];
363  *foundbin = MIN(*foundbin, idx);
364 
365  implidx[*nimplidx] = idx;
366  ++(*nimplidx);
367  }
368  }
369  /* if (implvars[w] = lb(implvars[w]) ==> var <= implcoefs[w]*SCIPvarGetLbGlobal(implvars[w]) +
370  * implconsts[w]) but (var <= bounds[pos] with bounds[pos] <
371  * implcoefs[w]*SCIPvarGetLbGlobal(implvars[w]) + implconsts[w]) it follows (new_lb(var) >
372  * ub(var))
373  */
374  else if( SCIPisFeasGT(scip, implcoefs[w]*SCIPvarGetLbGlobal(implvars[w]) + implconsts[w], bounds[pos]) )
375  {
376  SCIP_Real newlb;
377 
378  newlb = (bounds[pos] - implconsts[w]) / implcoefs[w];
379 
380  if( issetvar[idx] > 0 && newlb >= bounds[issetvar[idx] - 1] )
381  {
382  SCIPdebugMessage("set variable <%s> %s %g implies other set variable <%s> %s %g (%g)\n", SCIPvarGetName(var), "<=", bounds[pos], SCIPvarGetName(implvars[w]), ">=", newlb, bounds[issetvar[idx] - 1]);
383 
384  issetvar[varidx] = -1;
385  break;
386  }
387 
388  ++counts[idx];
389 
390  if( counts[idx] == 1 )
391  {
392  lastbounds[*nimplidx] = SCIP_INVALID;
393  newbounds[idx] = newlb;
394  }
395  else if( newbounds[idx] > newlb )
396  {
397  lastbounds[*nimplidx] = newbounds[idx];
398  newbounds[idx] = newlb;
399  }
400  else
401  lastbounds[*nimplidx] = SCIP_INVALID;
402 
403  *foundnonbin = MIN(*foundnonbin, idx);
404 
405  implidx[*nimplidx] = idx;
406  ++(*nimplidx);
407  }
408  }
409  }
410  else
411  {
412  /* update the counters and implied bounds */
413  idx += nvars;
414 
415  if( counts[idx] == pos )
416  {
417  if( SCIPvarIsBinary(implvars[w]) )
418  {
419  /* do not look at fixed variables */
420  if( SCIPvarGetLbGlobal(implvars[w]) > 0.5 || SCIPvarGetUbGlobal(implvars[w]) < 0.5 )
421  continue;
422 
423  /* (implvars[w] = 1 ===> var >= implcoefs[w] + implconsts[w] and if implcoefs[w] +
424  * implconsts[w] > bounds[pos]) ===> (because var <= bounds[pos] ===> implvars[w] = 0)
425  */
426  if( SCIPisFeasGT(scip, implcoefs[w] + implconsts[w], bounds[pos]) )
427  {
428  if( issetvar[idx] > 0 )
429  {
430  SCIPdebugMessage("set variable <%s> %s %g implies other set variable <%s> %s %g\n", SCIPvarGetName(var), "<=", bounds[pos], SCIPvarGetName(implvars[w]), "<=", 0.0);
431 
432  issetvar[varidx] = -1;
433  break;
434  }
435 
436  ++counts[idx];
437  *foundbin = MIN(*foundbin, idx);
438 
439  implidx[*nimplidx] = idx;
440  ++(*nimplidx);
441  }
442  }
443  /* if (implvars[w] = ub(implvars[w]) => var <= implcoefs[w]*SCIPvarGetUbGlobal(implvars[w]) +
444  * implconsts[w]) but (var <= bounds[pos] with bounds[pos] <
445  * implcoefs[w]*SCIPvarGetUbGlobal(implvars[w]) + implconsts[w]) it follows (new_ub(var) <
446  * ub(var))
447  */
448  else if( SCIPisFeasGT(scip, implcoefs[w]*SCIPvarGetUbGlobal(implvars[w]) + implconsts[w], bounds[pos]) )
449  {
450  SCIP_Real newub;
451 
452  newub = (bounds[pos] - implconsts[w]) / implcoefs[w];
453 
454  if( issetvar[idx] > 0 && newub <= bounds[issetvar[idx] - 1] )
455  {
456  SCIPdebugMessage("set variable <%s> %s %g implies other set variable <%s> %s %g (%g)\n", SCIPvarGetName(var), "<=", bounds[pos], SCIPvarGetName(implvars[w]), "<=", newub, bounds[issetvar[idx] - 1]);
457 
458  issetvar[varidx] = -1;
459  break;
460  }
461 
462  ++counts[idx];
463 
464  if( counts[idx] == 1 )
465  {
466  lastbounds[*nimplidx] = SCIP_INVALID;
467  newbounds[idx] = newub;
468  }
469  else if( newbounds[idx] < newub )
470  {
471  lastbounds[*nimplidx] = newbounds[idx];
472  newbounds[idx] = newub;
473  }
474  else
475  lastbounds[*nimplidx] = SCIP_INVALID;
476 
477  *foundnonbin = MIN(*foundnonbin, idx);
478 
479  implidx[*nimplidx] = idx;
480  ++(*nimplidx);
481  }
482  }
483  }
484  }
485  }
486 }
487 
488 
489 /** collect non-binary implication data for variable set reduction and global bound implications; only variable which
490  * have the vartype SCIP_VARTYPE_BINARY have implications, otherwise the implications are saved as variable bounds
491  */
492 static
493 void collectNonBinaryImplicationData(
494  SCIP* scip, /**< SCIP data structure */
495  SCIP_VAR* var, /**< set variable */
496  int varidx, /**< for lower bound set variable index, for upper bound set
497  * variable index + number of variables
498  */
499  int pos, /**< variables's position in bdchinfos */
500  SCIP_Bool value, /**< value used for clique and implication info */
501  SCIP_Real* bounds, /**< array of bounds where one of them must be fullfilled */
502  SCIP_Bool* boundtypes, /**< array of bound types */
503  SCIP_Real* newbounds, /**< array of implied bounds(, size is two times number of variables, first
504  * half for implied lower bounds, second for implied upper bounds)
505  */
506  int* counts, /**< array of number of implication on a bound (, size is two times number
507  * of variables, first half for implied lower bounds, second for implied
508  * upper bounds)
509  */
510  int* issetvar, /**< array containing for set variables the position in the current set, or
511  * 0 if it is not a set variable or -1, if it is a redundant(i.e. implies
512  * another set variable) set variables(, size is two times number of
513  * variables, first half for implied lower bounds, second for implied
514  * upper bounds) */
515  int nvars, /**< number of problem variables */
516  int* foundbin, /**< pointer to store the lowest index of a binary implication variable
517  * when found
518  */
519  int* foundnonbin, /**< pointer to store the lowest index of a non-binary implication variable
520  * when found
521  */
522  int* implidx, /**< array to store the variable indices (for upper bound 'nvars' is added
523  * to the index) which are implied
524  */
525  int* nimplidx, /**< pointer to store the number of implied variables */
526  SCIP_Real* lastbounds /**< array to remember last implied bounds before taken the current
527  * variable into account, first nvars for lower bound, second nvars for
528  * upper bound
529  *
530  * this array is used when a set variable got redundant, because it
531  * implies another set variable, and we need to correct the counts array
532  */
533  )
534 {
535  assert(scip != NULL);
536  assert(var != NULL);
537  assert(SCIPvarGetType(var) == SCIP_VARTYPE_BINARY);
538  assert(varidx >= 0);
539  assert(pos >= 0);
540  assert(bounds != NULL);
541  assert(boundtypes != NULL);
542  assert(newbounds != NULL);
543  assert(counts != NULL);
544  assert(issetvar != NULL);
545  assert(2 * nvars > varidx);
546  assert(foundbin != NULL);
547  assert(foundnonbin != NULL);
548  assert(implidx != NULL);
549  assert(nimplidx != NULL);
550  assert(lastbounds != NULL);
551 
552  if( issetvar[varidx] > 0 )
553  {
554  SCIP_VAR** implvars;
555  SCIP_Real* implbounds;
556  SCIP_BOUNDTYPE* implboundtypes;
557  int nbinimplsvar;
558  int idx;
559  int w;
560 
561  /* get implication information */
562  implvars = SCIPvarGetImplVars(var, value);
563  implboundtypes = SCIPvarGetImplTypes(var, value);
564  implbounds = SCIPvarGetImplBounds(var, value);
565  nbinimplsvar = SCIPvarGetNBinImpls(var, value);
566 
567 
568  /* update implication counter on all by non-binary implication implied variables */
569  for( w = SCIPvarGetNImpls(var, value) - 1; w >= nbinimplsvar; --w )
570  {
571  assert(implvars != NULL);
572  assert(implboundtypes != NULL);
573 
574  /* no self implication should exist in the implication data structure */
575  assert(implvars[w] != var);
576 
577  idx = SCIPvarGetProbindex(implvars[w]);
578 
579  /* do not use inactive variables */
580  /* @todo if implvars[x] is aggregated, we could transform the variable into the active representation */
581  if( idx < 0 || SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(implvars[w]), SCIPvarGetUbGlobal(implvars[w])) )
582  continue;
583 
584  if( implboundtypes[w] == SCIP_BOUNDTYPE_UPPER )
585  {
586  idx += nvars;
587 
588  assert(counts[idx] <= pos+1);
589 
590  /* set variable 'var' with bound implies other set variable 'implvars[w]' with a non-worse bound than the
591  * bound so we can remove the set variable 'var'
592  */
593  if( issetvar[idx] > 0 && bounds[issetvar[idx] - 1] >= implbounds[w] )
594  {
595  SCIPdebugMessage("set variable <%s> %s %g implies other set variable <%s> %s %g (%g)\n", SCIPvarGetName(var), boundtypes[pos] ? "<=" : ">=", bounds[pos], SCIPvarGetName(implvars[w]), "<=", implbounds[w], bounds[issetvar[idx] - 1]);
596 
597  issetvar[varidx] = -1;
598  break;
599  }
600 
601  /* update implication counter and implied upper bound */
602  if( counts[idx] == pos )
603  {
604  ++counts[idx];
605 
606  if( SCIPvarIsBinary(implvars[w]) )
607  {
608  /* the implied upper bound on a binary variable should not be trivial, otherwise we might globally fix
609  * this variable to a wrong value
610  *
611  * @note is is possible that the implied bound is lower than zero, when the implied variable has
612  * become binary during the search
613  */
614  assert(SCIPisFeasLE(scip, implbounds[w], 0.0));
615  *foundbin = MIN(*foundbin, idx);
616  }
617  else
618  {
619  *foundnonbin = MIN(*foundnonbin, idx);
620 
621  if( counts[idx] == 1 )
622  {
623  newbounds[idx] = implbounds[w];
624  lastbounds[*nimplidx] = SCIP_INVALID;
625  }
626  else if( newbounds[idx] < implbounds[w] )
627  {
628  lastbounds[*nimplidx] = newbounds[idx];
629  newbounds[idx] = implbounds[w];
630  }
631  else
632  lastbounds[*nimplidx] = SCIP_INVALID;
633  }
634 
635  implidx[*nimplidx] = idx;
636  ++(*nimplidx);
637  }
638  }
639  else
640  {
641  assert(counts[idx] <= pos+1);
642 
643  /* set variable 'var' with bound implies other set variable 'implvars[w]' with a non-worse bound than the
644  * bound so we can remove the set variable 'var'
645  */
646  if( issetvar[idx] > 0 && bounds[issetvar[idx] - 1] <= implbounds[w] )
647  {
648  SCIPdebugMessage("set variable <%s> %s %g implies other set variable <%s> %s %g (%g)\n", SCIPvarGetName(var), boundtypes[pos] ? "<=" : ">=", bounds[pos], SCIPvarGetName(implvars[w]), ">=", implbounds[w], bounds[issetvar[idx] - 1]);
649 
650  issetvar[varidx] = -1;
651  break;
652  }
653 
654  /* update implication counter */
655  if( counts[idx] == pos )
656  {
657  ++counts[idx];
658 
659  if( SCIPvarIsBinary(implvars[w]) )
660  {
661  /* the implied lower bound on a binary variable should not be trivial, otherwise we might globally fix
662  * this variable to a wrong value
663  *
664  * @note is is possible that the implied bound is greater than one, when the implied variable has
665  * become binary during the search
666  */
667  assert(SCIPisFeasGE(scip, implbounds[w], 1.0));
668  *foundbin = MIN(*foundbin, idx);
669  }
670  else
671  {
672  *foundnonbin = MIN(*foundnonbin, idx);
673 
674  if( counts[idx] == 1 )
675  {
676  newbounds[idx] = implbounds[w];
677  lastbounds[*nimplidx] = SCIP_INVALID;
678  }
679  else if( newbounds[idx] > implbounds[w] )
680  {
681  lastbounds[*nimplidx] = newbounds[idx];
682  newbounds[idx] = implbounds[w];
683  }
684  else
685  lastbounds[*nimplidx] = SCIP_INVALID;
686  }
687 
688  implidx[*nimplidx] = idx;
689  ++(*nimplidx);
690  }
691  }
692  }
693  }
694 }
695 
696 /** collect binary implication data for variable set reduction and global bound implications; only variable which have
697  * the vartype SCIP_VARTYPE_BINARY have binary implications, otherwise the implications are saved as variable bounds
698  */
699 static
700 void collectBinaryImplicationData(
701  SCIP_VAR* var, /**< set variable */
702  int varidx, /**< for lower bound set variable index, for upper bound set variable index
703  * + number of variables
704  */
705  int pos, /**< variables's position in bdchinfos */
706  SCIP_Bool value, /**< value used for clique and implication info */
707  SCIP_Real* bounds, /**< array of bounds where one of them must be fullfilled */
708  SCIP_Bool* boundtypes, /**< array of bound types */
709  SCIP_Real* newbounds, /**< array of implied bounds(, size is two times number of variables, first
710  * half for implied lower bounds, second for implied upper bounds)
711  */
712  int* counts, /**< array of number of implication on a bound (, size is two times number of
713  * variables, first half for implied lower bounds, second for implied upper
714  * bounds)
715  */
716  int* issetvar, /**< array containing for set variables the position in the current set, or
717  * 0 if it is not a set variable or -1, if it is a redundant(i.e. implies
718  * another set variable) set variables(, size is two times number of
719  * variables, first half for implied lower bounds, second for implied
720  * upper bounds) */
721  int nvars, /**< number of problem variables */
722  int* foundbin, /**< pointer to store the lowest index of a binary implication variable when found */
723  int* implidx, /**< array to store the variable indices (for upper bound 'nvars' is added
724  * to the index) which are implied
725  */
726  int* nimplidx /**< pointer to store the number of implied variables */
727  )
728 {
729  assert(var != NULL);
730  assert(SCIPvarGetType(var) == SCIP_VARTYPE_BINARY);
731  assert(varidx >= 0);
732  assert(pos >= 0);
733  assert(bounds != NULL);
734  assert(boundtypes != NULL);
735  assert(newbounds != NULL);
736  assert(counts != NULL);
737  assert(issetvar != NULL);
738  assert(2 * nvars > varidx);
739  assert(foundbin != NULL);
740  assert(implidx != NULL);
741  assert(nimplidx != NULL);
742 
743  /* if the set variable is not yet redundant check the implication data */
744  if( issetvar[varidx] > 0 )
745  {
746  SCIP_VAR** implvars;
747  SCIP_BOUNDTYPE* implboundtypes;
748  int nbinimplsvar;
749  int idx;
750  int w;
751 
752  implvars = SCIPvarGetImplVars(var, value);
753  implboundtypes = SCIPvarGetImplTypes(var, value);
754  nbinimplsvar = SCIPvarGetNBinImpls(var, value);
755 
756  /* update implication counter on all by binary implication implied variables */
757  for( w = nbinimplsvar - 1; w >= 0; --w )
758  {
759  /* no self implication should exist in the implication data structure */
760  assert(implvars[w] != var);
761 
762  /* do not look at fixed variables */
763  if( SCIPvarGetLbGlobal(implvars[w]) > 0.5 || SCIPvarGetUbGlobal(implvars[w]) < 0.5 )
764  continue;
765 
766  idx = SCIPvarGetProbindex(implvars[w]);
767  assert(idx >= 0);
768 
769  if( implboundtypes[w] == SCIP_BOUNDTYPE_UPPER )
770  idx += nvars;
771 
772  assert(counts[idx] <= pos+1);
773 
774  /* set variable 'var' with bound implies other set variable 'implvars[w]' with corresponding bound so we can
775  * remove the set variable 'var'
776  */
777  if( issetvar[idx] > 0 )
778  {
779  SCIPdebugMessage("set variable <%s> %s %g implies other set variable <%s> %s %g\n", SCIPvarGetName(var), boundtypes[pos] ? "<=" : ">=", bounds[pos], SCIPvarGetName(implvars[w]), implboundtypes[w] ? "<=" : ">=", implboundtypes[w] ? 0.0 : 1.0);
780 
781  issetvar[varidx] = -1;
782  break;
783  }
784 
785  /* update implication counter */
786  if( counts[idx] == pos )
787  {
788  ++counts[idx];
789  *foundbin = MIN(*foundbin, idx);
790 
791  implidx[*nimplidx] = idx;
792  ++(*nimplidx);
793  }
794  }
795  }
796 }
797 
798 /** collect clique data on binary variables for variable set reduction and global bound implications */
799 static
800 void collectBinaryCliqueData(
801  SCIP_VAR* var, /**< set variable */
802  int varidx, /**< for lower bound set variable index, for upper bound set variable index
803  * + number of variables
804  */
805  int pos, /**< variables's position in bdchinfos */
806  SCIP_Bool value, /**< value used for clique and implication info */
807  SCIP_Real* bounds, /**< array of bounds where one of them must be fullfilled */
808  SCIP_Bool* boundtypes, /**< array of bound types */
809  SCIP_Real* newbounds, /**< array of implied bounds(, size is two times number of variables, first
810  * half for implied lower bounds, second for implied upper bounds)
811  */
812  int* counts, /**< array of number of implication on a bound (, size is two times number of
813  * variables, first half for implied lower bounds, second for implied upper
814  * bounds)
815  */
816  int* issetvar, /**< array containing for set variables the position in the current set, or
817  * 0 if it is not a set variable or -1, if it is a redundant(i.e. implies
818  * another set variable) set variables(, size is two times number of
819  * variables, first half for implied lower bounds, second for implied
820  * upper bounds) */
821  int nvars, /**< number of problem variables */
822  int* foundbin, /**< pointer to store the lowest index of a binary implication variable when found */
823  int* implidx, /**< array to store the variable indices (for upper bound 'nvars' is added
824  * to the index) which are implied
825  */
826  int* nimplidx /**< pointer to store the number of implied variables */
827  )
828 {
829  SCIP_CLIQUE** cliques;
830  SCIP_VAR** clqvars;
831  SCIP_Bool* clqvalues;
832  int idx;
833  int c;
834  int w;
835 
836  assert(var != NULL);
837  assert(SCIPvarIsBinary(var));
838  assert(varidx >= 0);
839  assert(pos >= 0);
840  assert(bounds != NULL);
841  assert(boundtypes != NULL);
842  assert(newbounds != NULL);
843  assert(counts != NULL);
844  assert(issetvar != NULL);
845  assert(2 * nvars > varidx);
846  assert(foundbin != NULL);
847  assert(implidx != NULL);
848  assert(nimplidx != NULL);
849 
850  /* implication counter cannot exceed number implication variables */
851  assert(counts[varidx] <= pos);
852 
853  /* if the set variable is not yet redundant we might increase the self implication counter */
854  if( issetvar[varidx] > 0 )
855  {
856  /* update implication counter for set variables */
857  if( counts[varidx] == pos )
858  {
859  ++counts[varidx];
860  *foundbin = MIN(*foundbin, varidx);
861 
862  implidx[*nimplidx] = varidx;
863  ++(*nimplidx);
864  }
865  }
866 
867  cliques = SCIPvarGetCliques(var, value);
868 
869  /* update implication counter on all by cliques implied variables */
870  for( c = SCIPvarGetNCliques(var, value) - 1; c >= 0; --c )
871  {
872  clqvars = SCIPcliqueGetVars(cliques[c]);
873  clqvalues = SCIPcliqueGetValues(cliques[c]);
874 
875  for( w = SCIPcliqueGetNVars(cliques[c]) - 1; w >= 0; --w )
876  {
877  /* already handle self-implication and do not look at fixed variables */
878  if( clqvars[w] == var || SCIPvarGetLbGlobal(clqvars[w]) > 0.5 || SCIPvarGetUbGlobal(clqvars[w]) < 0.5 )
879  continue;
880 
881  idx = SCIPvarGetProbindex(clqvars[w]);
882  assert(idx >= 0);
883 
884  if( clqvalues[w] )
885  idx += nvars;
886 
887  assert(counts[idx] <= pos+1);
888 
889  /* set variable 'var' with bound implies other set variable 'clqvars[w]' with corresponding set bound so we can
890  * remove the set variable 'var'
891  */
892  if( issetvar[idx] > 0 )
893  {
894  SCIPdebugMessage("set variable <%s> %s %g implies other set variable <%s> %s %g\n", SCIPvarGetName(var), boundtypes[pos] ? "<=" : ">=", bounds[pos], SCIPvarGetName(clqvars[w]), clqvalues[w] ? "<=" : ">=", clqvalues[w] ? 0.0 : 1.0);
895 
896  issetvar[varidx] = -1;
897  break;
898  }
899 
900  /* update implication counter */
901  if( counts[idx] == pos )
902  {
903  ++counts[idx];
904  *foundbin = MIN(*foundbin, idx);
905 
906  implidx[*nimplidx] = idx;
907  ++(*nimplidx);
908  }
909  }
910  }
911 }
912 
913 
914 
915 /*
916  * presolving methods
917  */
918 
919 
920 /** try to reduce the necessary variable in a set of variables with corresponding bounds and boundtypes for which one
921  * must be fulfilled
922  *
923  * e.g. a set of logicor or bounddisjunctive constraint variables would be such a set
924  *
925  * consider the following set:
926  *
927  * x1 >= 1, x2 >= 3, x3 >= 1, x4 <= 0
928  *
929  * by (global) implication data (cliques, implications, and variable bounds) we have also the following implications
930  * given:
931  *
932  * x1 >= 1 => x3 >= 1
933  * x2 >= 2 => x3 >= 1
934  * x4 <= 0 => x1 >= 1
935  *
936  * Because of the last implication x4 is redundant, because x1 >= 1 would also be fulfilled in the variable set, so we
937  * can reduce the set by x4.
938  * Also, the both other implications and x3 >= 1 (in the given variable set) all implie exactly x3 >= 1, so we tighten
939  * the global lower bound of x3 to 1 and the set of variables gets redundant.
940  */
941 SCIP_RETCODE SCIPshrinkDisjunctiveVarSet(
942  SCIP* scip, /**< SCIP data structure */
943  SCIP_VAR** vars, /**< array of active! variables for which at least one must be fulfilled
944  * in the following bounds and boundtypes
945  */
946  SCIP_Real* bounds, /**< bounds array for which at least one must be fulfilled */
947  SCIP_Bool* boundtypes, /**< boundtypes array (TRUE == SCIP_BOUNDTYPE_UPPER, FALSE ==
948  * SCIP_BOUNDTYPE_LOWER) for which at least one must be fulfilled
949  */
950  SCIP_Bool* redundants, /**< array which be filled and then indicate if a variable in the set is
951  * redundant
952  */
953  int nvars, /**< number of variables */
954  int* nredvars, /**< pointer to store how many variables can be removed */
955  int* nglobalred, /**< pointer to store number of global reductions on variable bounds found
956  * through this set of variables
957  */
958  SCIP_Bool* setredundant, /**< pointer to store if we found a global reduction on a variable which
959  * was part of the given set of variables, this makes this disjunction
960  * redundant
961  */
962  SCIP_Bool fullshortening /**< do we want to try the shortening procedure over the whole set (which
963  * might be expensive)
964  */
965  )
966 {
967  SCIP_Real* newbounds; /* array saving all overall implied global bounds, first nprobvars for lower bound, second
968  * nprobvars for upper bound
969  */
970  SCIP_Real* lastbounds;/* temporary array to remember last implied bounds before taken the current variable into
971  * account, first nprobvars for lower bound, second nprobvars for upper bound
972  *
973  * this array is used when a set variable got redundant, because it implies another set
974  * variable, and we need to correct the counts array
975  */
976  int* issetvar; /* array for mapping from a problem variable to the position in the variable set (,pos + 1 in
977  * the variable set, 0 for no set variable, and -1 if this variable was removed from the set),
978  * first nprobvars for lower bound, second nprobvars for upper bound
979  */
980  int* counts; /* array saving number of implication by set variables, first nprobvars for lower bound, second
981  * nprobvars for upper bound
982  */
983  int* implidx; /* temporary array to remember all indices of implied variables by the current set variable
984  * looked at, first nprobvars for lower bound, second nprobvars for upper bound
985  *
986  * this array is used when a set variable got redundant, because it implies another set
987  * variable, and we need to correct the counts array
988  */
989 
990  SCIP_VAR* var;
991  SCIP_Bool usebin = TRUE;
992  SCIP_Bool usenonbin = TRUE;
993  SCIP_Bool globalred = TRUE;
994  SCIP_Bool reducedset;
995  SCIP_Bool value;
996  SCIP_Bool implbinvarsexist;
997  int start = INT_MAX;
998  int nimplidx;
999  int foundbin;
1000  int foundnonbin;
1001  int varidx;
1002  int nprobvars;
1003  int w;
1004  int v;
1005 
1006  if( nvars == 0 )
1007  return SCIP_OKAY;
1008 
1009  assert(scip != NULL);
1010  assert(vars != NULL);
1011  assert(bounds != NULL);
1012  assert(boundtypes != NULL);
1013  assert(redundants != NULL);
1014  assert(nredvars != NULL);
1015  assert(nglobalred != NULL);
1016  assert(setredundant != NULL);
1017 
1018  /* clear given redundancy array, indicating whether a variable is redundant */
1019  BMSclearMemoryArray(redundants, nvars);
1020 
1021  assert(scip->transprob != NULL);
1022  nprobvars = SCIPprobGetNVars(scip->transprob);
1023 
1024  /* @todo need global memory because allocating and clearing can be expensive in presolving, i.e. calloc(memset) is
1025  * too expensive, might also consider other data structures like hashmaps for issetvar and counts
1026  */
1027  /* allocate temporary memory */
1028  SCIP_ALLOC( BMSallocClearMemoryArray(&issetvar, 2*nprobvars) );
1029  SCIP_ALLOC( BMSallocClearMemoryArray(&counts, 2*nprobvars) );
1030  SCIP_CALL( SCIPallocBufferArray(scip, &newbounds, 2*nprobvars) );
1031  SCIP_CALL( SCIPallocBufferArray(scip, &lastbounds, 2*nprobvars) );
1032  SCIP_CALL( SCIPallocBufferArray(scip, &implidx, 2*nprobvars) );
1033 
1034  *nredvars = 0;
1035 
1036  /* initialize variable indices data */
1037  for( v = 0; v < nvars; ++v )
1038  {
1039  varidx = SCIPvarGetProbindex(vars[v]);
1040  assert(varidx >= 0);
1041 
1042  if( boundtypes[v] )
1043  varidx += nprobvars;
1044 
1045  /* initialize issetvar array */
1046  issetvar[varidx] = v+1;
1047  }
1048 
1049  /* check if implied binary variables exist, because for these variables the implications can be stored in the
1050  * variable bounds instead of the 'normal' implications
1051  */
1052  implbinvarsexist = (SCIPprobGetNImplBinVars(scip->transprob) > 0);
1053 
1054  /* check for same implied binary variables */
1055  for( v = 0; v < nvars; ++v )
1056  {
1057  var = vars[v];
1058 
1059  foundbin = INT_MAX;
1060  foundnonbin = INT_MAX;
1061  reducedset = FALSE;
1062  nimplidx = 0;
1063 
1064  value = (!boundtypes[v]);
1065 
1066  varidx = SCIPvarGetProbindex(var);
1067  assert(varidx >= 0);
1068 
1069  if( !value )
1070  varidx += nprobvars;
1071 
1072  if( usebin )
1073  {
1074  /* collect clique data on binary variables */
1075  if( SCIPvarIsBinary(var) )
1076  {
1077  collectBinaryCliqueData(var, varidx, v, value, bounds, boundtypes, newbounds, counts, issetvar, nprobvars, &foundbin, implidx, &nimplidx);
1078 
1079  /* only variable which have the vartype SCIP_VARTYPE_BINARY have binary implications, otherwise the
1080  * implications are saved as variable bounds
1081  *
1082  * @note if implications on two binary variables are stored in the clique data, the following if block can be deleted
1083  */
1084  if( SCIPvarGetType(var) == SCIP_VARTYPE_BINARY )
1085  {
1086  collectBinaryImplicationData(var, varidx, v, value, bounds, boundtypes, newbounds, counts, issetvar, nprobvars, &foundbin, implidx, &nimplidx);
1087  }
1088  }
1089  }
1090 
1091  /* only variable which have the vartype SCIP_VARTYPE_BINARY have implications, otherwise the implications are
1092  * saved as variable bounds
1093  *
1094  * we only check binary to non-binary implications if we can detect further implications which either lead to
1095  * global reductions or to redundant set variables
1096  */
1097  if( SCIPvarGetType(var) == SCIP_VARTYPE_BINARY && ((usebin && implbinvarsexist) || usenonbin) )
1098  {
1099  collectNonBinaryImplicationData(scip, var, varidx, v, value, bounds, boundtypes, newbounds, counts, issetvar, nprobvars, &foundbin, &foundnonbin, implidx, &nimplidx, lastbounds);
1100  }
1101  /* only variable which have the vartype != SCIP_VARTYPE_BINARY have variable bounds
1102  *
1103  * we only check the variable bounds if we can detect further implications which either lead to global reductions
1104  * or to redundant set variables
1105  */
1106  else if( SCIPvarGetType(var) != SCIP_VARTYPE_BINARY && ((usebin && implbinvarsexist) || usenonbin) )
1107  {
1108  collectNonBinaryVBoundData(scip, var, varidx, v, bounds, boundtypes, newbounds, counts, issetvar, nprobvars, &foundbin, &foundnonbin, implidx, &nimplidx, lastbounds);
1109  }
1110 
1111  /* reduce implication counters on all variables which are implied by a variable now marked as redundant */
1112  if( issetvar[varidx] < 0 )
1113  {
1114  SCIP_VAR** probvars;
1115 #ifndef NDEBUG
1116  int tmp = v+1;
1117 #endif
1118 
1119  SCIPdebugMessage("marked variable <%s> as redundant variable in variable set\n", SCIPvarGetName(var));
1120 
1121  probvars = SCIPprobGetVars(scip->transprob);
1122  assert(probvars != NULL);
1123 
1124  /* correct implication counters and bounds, if the redundant variable implies other variables we need to reduce
1125  * the the counter and get the last bounds before this implication
1126  */
1127  for( w = nimplidx - 1; w >= 0; --w )
1128  {
1129  assert(counts[implidx[w]] == tmp);
1130  --counts[implidx[w]];
1131 
1132  assert(implidx[w] < 2 * nprobvars);
1133 
1134  /* only for non-binary variables we need to correct the bounds */
1135  if( implidx[w] < nprobvars )
1136  {
1137  if( !SCIPvarIsBinary(probvars[implidx[w]]) && lastbounds[w] != SCIP_INVALID )/*lint !e777*/
1138  newbounds[implidx[w]] = lastbounds[w];
1139  }
1140  else
1141  {
1142  if( !SCIPvarIsBinary(probvars[implidx[w] - nprobvars]) && lastbounds[w] != SCIP_INVALID )/*lint !e777*/
1143  newbounds[implidx[w] - nprobvars] = lastbounds[w];
1144  }
1145  }
1146 
1147  reducedset = TRUE;
1148  ++(*nredvars);
1149  }
1150 
1151  /* check if we want to shorten the whole set of variables, or terminate early if we did not find any further
1152  * implication
1153  */
1154  if( !fullshortening )
1155  {
1156  /* check if it makes sense to look for further binary implications */
1157  if( foundbin < INT_MAX && !reducedset )
1158  usebin = FALSE;
1159  /* check if it makes sense to look for further non-binary implications */
1160  if( foundnonbin < INT_MAX && !reducedset )
1161  usenonbin = FALSE;
1162  }
1163 
1164  /* are global reductions still possible */
1165  globalred = globalred && (foundbin < INT_MAX || foundnonbin < INT_MAX);
1166 
1167  /* remember the first possible position for a global bound change */
1168  if( globalred )
1169  {
1170  /* get correct variable index(, we added nprobvars for the upper bound implication) */
1171  if( foundbin < INT_MAX && foundbin >= nprobvars )
1172  foundbin -= nprobvars;
1173 
1174  /* get correct variable index(, we added nprobvars for the upper bound implication) */
1175  if( foundnonbin < INT_MAX && foundnonbin >= nprobvars )
1176  foundnonbin -= nprobvars;
1177 
1178  if( start > foundbin )
1179  start = foundbin;
1180 
1181  if( start > foundnonbin )
1182  start = foundnonbin;
1183  }
1184  else
1185  start = INT_MAX;
1186 
1187  /* check if it can find any global implications anymore */
1188  if( !usebin && !usenonbin )
1189  break;
1190  }
1191 
1192  /* remove redundant set variables */
1193  if( *nredvars > 0 )
1194  {
1195 #ifndef NDEBUG
1196  int nreds = 0;
1197 #endif
1198 
1199  for( v = nvars - 1; v >= 0; --v )
1200  {
1201  var = vars[v];
1202 
1203  varidx = SCIPvarGetProbindex(var);
1204  assert(varidx >= 0);
1205 
1206  if( boundtypes[v] )
1207  varidx += nprobvars;
1208 
1209  /* if set variable was marked to be redundant remove it */
1210  if( issetvar[varidx] < 0 )
1211  {
1212  SCIPdebugMessage("mark redundant variable <%s> to be removed from variable set\n", SCIPvarGetName(var));
1213 
1214  redundants[v] = TRUE;
1215 #ifndef NDEBUG
1216  ++nreds;
1217 #endif
1218  }
1219  }
1220  assert((*nredvars) == nreds);
1221  }
1222 
1223  /* if we found some global boundchanges, we perform then now */
1224  if( globalred )
1225  {
1226  SCIP_VAR** probvars;
1227  SCIP_VAR* probvar;
1228 
1229  SCIPdebugMessage("variable set led to global reductions (in %s)\n", SCIPprobGetName(scip->transprob));
1230 
1231  probvars = SCIPprobGetVars(scip->transprob);
1232  assert(probvars != NULL);
1233 
1234  assert(start < nprobvars);
1235 
1236  /* check for same implied binary variables */
1237  for( v = start; v < nprobvars; ++v )
1238  {
1239  probvar = probvars[v];
1240  assert(probvar != NULL);
1241 
1242  assert(counts[v] <= nvars);
1243  assert(counts[nprobvars + v] <= nvars);
1244 
1245  if( counts[v] + (*nredvars) == nvars )
1246  {
1247  if( SCIPvarIsBinary(probvar) )
1248  {
1249  SCIPdebugMessage("can fix variable %s [%g, %g] to 1.0\n", SCIPvarGetName(probvar), SCIPvarGetLbGlobal(probvar), SCIPvarGetUbGlobal(probvar));
1250 
1251  if( SCIPvarGetLbGlobal(probvar) < 0.5 )
1252  {
1253  SCIP_CALL( SCIPnodeAddBoundchg(scip->tree->root, scip->mem->probmem, scip->set, scip->stat,
1254  scip->transprob, scip->origprob, scip->tree, scip->lp, scip->branchcand, scip->eventqueue, probvar, 1.0,
1255  SCIP_BOUNDTYPE_LOWER, FALSE) );
1256 
1257  assert(SCIPvarGetLbGlobal(probvar) > 0.5 || scip->tree->npendingbdchgs > 0);
1258 
1259  ++(*nglobalred);
1260 
1261  if( issetvar[v] > 0 )
1262  *setredundant = TRUE;
1263  }
1264  }
1265  else
1266  {
1267  SCIPdebugMessage("can tighten lower bound variable %s [%g, %g] to %g\n", SCIPvarGetName(probvar), SCIPvarGetLbGlobal(probvar), SCIPvarGetUbGlobal(probvar), newbounds[v]);
1268 
1269  if( SCIPisLT(scip, SCIPvarGetLbGlobal(probvar), newbounds[v]) )
1270  {
1271  SCIP_CALL( SCIPnodeAddBoundchg(scip->tree->root, scip->mem->probmem, scip->set, scip->stat,
1272  scip->transprob, scip->origprob, scip->tree, scip->lp, scip->branchcand, scip->eventqueue, probvar,
1273  newbounds[v], SCIP_BOUNDTYPE_LOWER, FALSE) );
1274 
1275  ++(*nglobalred);
1276 
1277  if( issetvar[v] > 0 && newbounds[v] >= bounds[issetvar[v] - 1] )
1278  *setredundant = TRUE;
1279  }
1280  }
1281  }
1282  else if( counts[nprobvars + v] + (*nredvars) == nvars )
1283  {
1284  if( SCIPvarIsBinary(probvar) )
1285  {
1286  SCIPdebugMessage("can fix variable %s [%g, %g] to 0.0\n", SCIPvarGetName(probvar), SCIPvarGetLbGlobal(probvar), SCIPvarGetUbGlobal(probvar));
1287 
1288  if( SCIPvarGetUbGlobal(probvar) > 0.5 )
1289  {
1290  SCIP_CALL( SCIPnodeAddBoundchg(scip->tree->root, scip->mem->probmem, scip->set, scip->stat,
1291  scip->transprob, scip->origprob, scip->tree, scip->lp, scip->branchcand, scip->eventqueue, probvar, 0.0,
1292  SCIP_BOUNDTYPE_UPPER, FALSE) );
1293 
1294  assert(SCIPvarGetUbGlobal(probvar) < 0.5 || scip->tree->npendingbdchgs > 0);
1295 
1296  ++(*nglobalred);
1297 
1298  if( issetvar[nprobvars + v] > 0 )
1299  *setredundant = TRUE;
1300  }
1301  }
1302  else
1303  {
1304  int idx = nprobvars + v;
1305 
1306  SCIPdebugMessage("can tighten upper bound variable %s [%g, %g] to %g\n", SCIPvarGetName(probvar), SCIPvarGetLbGlobal(probvar), SCIPvarGetUbGlobal(probvar), newbounds[idx]);
1307 
1308  if( SCIPisGT(scip, SCIPvarGetUbGlobal(probvar), newbounds[idx]) )
1309  {
1310  SCIP_CALL( SCIPnodeAddBoundchg(scip->tree->root, scip->mem->probmem, scip->set, scip->stat,
1311  scip->transprob, scip->origprob, scip->tree, scip->lp, scip->branchcand, scip->eventqueue, probvar,
1312  newbounds[idx], SCIP_BOUNDTYPE_UPPER, FALSE) );
1313 
1314  ++(*nglobalred);
1315 
1316  if( issetvar[idx] > 0 && newbounds[idx] <= bounds[issetvar[idx] - 1] )
1317  *setredundant = TRUE;
1318  }
1319  }
1320  }
1321  }
1322  }
1323 
1324  SCIPfreeBufferArray(scip, &implidx);
1325  SCIPfreeBufferArray(scip, &lastbounds);
1326  SCIPfreeBufferArray(scip, &newbounds);
1327  BMSfreeMemoryArray(&counts);
1328  BMSfreeMemoryArray(&issetvar);
1329 
1330  return SCIP_OKAY;
1331 }
1332