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