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-2015 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 implie 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, /**< array of active! variables for which at least one must be fulfilled
956  * in the following bounds and boundtypes
957  */
958  SCIP_Real* bounds, /**< bounds array for which at least one must be fulfilled */
959  SCIP_Bool* boundtypes, /**< boundtypes array (TRUE == SCIP_BOUNDTYPE_UPPER, FALSE ==
960  * SCIP_BOUNDTYPE_LOWER) for which at least one must be fulfilled
961  */
962  SCIP_Bool* redundants, /**< array initialized to all FALSE, which will be filled and then indicates
963  * if a variable in the set is redundant
964  */
965  int nvars, /**< number of variables */
966  int* nredvars, /**< pointer to store how many variables can be removed */
967  int* nglobalred, /**< pointer to store number of global reductions on variable bounds found
968  * through this set of variables
969  */
970  SCIP_Bool* setredundant, /**< pointer to store if we found a global reduction on a variable which
971  * was part of the given set of variables, this makes this disjunction
972  * redundant
973  */
974  SCIP_Bool fullshortening /**< do we want to try the shortening procedure over the whole set (which
975  * might be expensive)
976  */
977  )
978 {
979  SCIP_Real* newbounds; /* array saving all overall implied global bounds, first nprobvars for lower bound, second
980  * nprobvars for upper bound
981  */
982  SCIP_Real* lastbounds;/* temporary array to remember last implied bounds before taken the current variable into
983  * account, first nprobvars for lower bound, second nprobvars for upper bound
984  *
985  * this array is used when a set variable got redundant, because it implies another set
986  * variable, and we need to correct the counts array
987  */
988  int* issetvar; /* array for mapping from a problem variable to the position in the variable set (,pos + 1 in
989  * the variable set, 0 for no set variable, and -1 if this variable was removed from the set),
990  * first nprobvars for lower bound, second nprobvars for upper bound
991  */
992  int* counts; /* array saving number of implication by set variables, first nprobvars for lower bound, second
993  * nprobvars for upper bound
994  */
995  int* implidx; /* temporary array to remember all indices of implied variables by the current set variable
996  * looked at, first nprobvars for lower bound, second nprobvars for upper bound
997  *
998  * this array is used when a set variable got redundant, because it implies another set
999  * variable, and we need to correct the counts array
1000  */
1001  int* countnonzeros;
1002 
1003  SCIP_VAR* var;
1004  SCIP_Bool usebin = TRUE;
1005  SCIP_Bool usenonbin = TRUE;
1006  SCIP_Bool globalred = TRUE;
1007  SCIP_Bool reducedset;
1008  SCIP_Bool value;
1009  SCIP_Bool implbinvarsexist;
1010  int start = INT_MAX;
1011  int nimplidx;
1012  int foundbin;
1013  int foundnonbin;
1014  int varidx;
1015  int nprobvars;
1016  int ncountnonzeros;
1017  int maxcountnonzeros;
1018  int w;
1019  int v;
1020 
1021  if( nvars == 0 )
1022  return SCIP_OKAY;
1023 
1024  assert(scip != NULL);
1025  assert(vars != NULL);
1026  assert(bounds != NULL);
1027  assert(boundtypes != NULL);
1028  assert(redundants != NULL);
1029  assert(nredvars != NULL);
1030  assert(nglobalred != NULL);
1031  assert(setredundant != NULL);
1032  assert(scip->transprob != NULL);
1033  nprobvars = SCIPprobGetNVars(scip->transprob);
1034 
1035  /* allocate temporary memory */
1036  SCIP_CALL( SCIPallocCleanBufferArray(scip, &issetvar, 2*nprobvars) ); /*lint !e647*/
1037  SCIP_CALL( SCIPallocCleanBufferArray(scip, &counts, 2*nprobvars) ); /*lint !e647*/
1038  SCIP_CALL( SCIPallocBufferArray(scip, &newbounds, 2*nprobvars) );
1039  SCIP_CALL( SCIPallocBufferArray(scip, &lastbounds, 2*nprobvars) );
1040  SCIP_CALL( SCIPallocBufferArray(scip, &implidx, 2*nprobvars) );
1041  SCIP_CALL( SCIPallocBufferArray(scip, &countnonzeros, 2*nprobvars) );
1042 
1043  *nredvars = 0;
1044  ncountnonzeros = 0;
1045 
1046  maxcountnonzeros = (int)(2*nprobvars*CLEARRATIO); /*lint !e790*/
1047 
1048  /* initialize variable indices data */
1049  for( v = 0; v < nvars; ++v )
1050  {
1051  varidx = SCIPvarGetProbindex(vars[v]);
1052  assert(varidx >= 0);
1053 
1054  if( boundtypes[v] )
1055  varidx += nprobvars;
1056 
1057  /* initialize issetvar array */
1058  issetvar[varidx] = v+1;
1059  }
1060 
1061  /* check if implied binary variables exist, because for these variables the implications can be stored in the
1062  * variable bounds instead of the 'normal' implications
1063  */
1064  implbinvarsexist = (SCIPprobGetNImplBinVars(scip->transprob) > 0);
1065 
1066 #if 0
1067  /* @todo do the cleanup here rather than before calling SCIPshrinkDisjunctiveVarSet()? */
1068  if( usebin )
1069  {
1070  SCIP_Bool infeasible;
1071 
1072  SCIP_CALL( SCIPcleanupCliques(scip, &infeasible) );
1073  }
1074 #endif
1075 
1076  /* check for same implied binary variables */
1077  for( v = 0; v < nvars; ++v )
1078  {
1079  var = vars[v];
1080 
1081  foundbin = INT_MAX;
1082  foundnonbin = INT_MAX;
1083  reducedset = FALSE;
1084  nimplidx = 0;
1085 
1086  value = (!boundtypes[v]);
1087 
1088  varidx = SCIPvarGetProbindex(var);
1089  assert(varidx >= 0);
1090 
1091  if( !value )
1092  varidx += nprobvars;
1093 
1094  if( usebin )
1095  {
1096  /* collect clique data on binary variables */
1097  if( SCIPvarIsBinary(var) )
1098  {
1099  collectBinaryCliqueData(var, varidx, v, *nredvars, value, bounds, boundtypes, newbounds, counts, countnonzeros,
1100  &ncountnonzeros, issetvar, nprobvars, &foundbin, implidx, &nimplidx);
1101  }
1102  }
1103 
1104  /* only variable which have the vartype SCIP_VARTYPE_BINARY have implications, otherwise the implications are
1105  * saved as variable bounds
1106  *
1107  * we only check binary to non-binary implications if we can detect further implications which either lead to
1108  * global reductions or to redundant set variables
1109  */
1110  if( SCIPvarGetType(var) == SCIP_VARTYPE_BINARY && ((usebin && implbinvarsexist) || usenonbin) )
1111  {
1112  collectNonBinaryImplicationData(scip, var, varidx, v, *nredvars, value, bounds, boundtypes, newbounds, counts,
1113  countnonzeros, &ncountnonzeros, issetvar, nprobvars, &foundbin, &foundnonbin, implidx, &nimplidx, lastbounds);
1114  }
1115  /* only variable which have the vartype != SCIP_VARTYPE_BINARY have variable bounds
1116  *
1117  * we only check the variable bounds if we can detect further implications which either lead to global reductions
1118  * or to redundant set variables
1119  */
1120  else if( SCIPvarGetType(var) != SCIP_VARTYPE_BINARY && ((usebin && implbinvarsexist) || usenonbin) )
1121  {
1122  collectNonBinaryVBoundData(scip, var, varidx, v, *nredvars, bounds, boundtypes, newbounds, counts, countnonzeros,
1123  &ncountnonzeros, issetvar, nprobvars, &foundbin, &foundnonbin, implidx, &nimplidx, lastbounds);
1124  }
1125 
1126  /* reduce implication counters on all variables which are implied by a variable now marked as redundant */
1127  if( issetvar[varidx] < 0 )
1128  {
1129  SCIP_VAR** probvars;
1130 
1131  SCIPdebugMessage("marked variable <%s> as redundant variable in variable set\n", SCIPvarGetName(var));
1132 
1133  probvars = SCIPprobGetVars(scip->transprob);
1134  assert(probvars != NULL);
1135 
1136  /* correct implication counters and bounds, if the redundant variable implies other variables we need to reduce
1137  * the counter and get the last bounds before this implication
1138  */
1139  for( w = nimplidx - 1; w >= 0; --w )
1140  {
1141  assert(implidx[w] < 2 * nprobvars);
1142  assert(counts[implidx[w]] == v - (*nredvars) + 1);
1143 
1144  --counts[implidx[w]];
1145 
1146  if( implidx[w] == countnonzeros[ncountnonzeros-1] && counts[implidx[w]] == 0 )
1147  --ncountnonzeros;
1148 
1149  /* only for non-binary variables we need to correct the bounds */
1150  if( implidx[w] < nprobvars )
1151  {
1152  if( !SCIPvarIsBinary(probvars[implidx[w]]) && lastbounds[w] != SCIP_INVALID )/*lint !e777*/
1153  newbounds[implidx[w]] = lastbounds[w];
1154  }
1155  else
1156  {
1157  if( !SCIPvarIsBinary(probvars[implidx[w] - nprobvars]) && lastbounds[w] != SCIP_INVALID )/*lint !e777*/
1158  newbounds[implidx[w] - nprobvars] = lastbounds[w];
1159  }
1160  }
1161 
1162  reducedset = TRUE;
1163  ++(*nredvars);
1164  }
1165 
1166  /* check if we want to shorten the whole set of variables, or terminate early if we did not find any further
1167  * implication
1168  */
1169  if( !fullshortening )
1170  {
1171  /* check if it makes sense to look for further binary implications */
1172  if( foundbin < INT_MAX && !reducedset )
1173  usebin = FALSE;
1174  /* check if it makes sense to look for further non-binary implications */
1175  if( foundnonbin < INT_MAX && !reducedset )
1176  usenonbin = FALSE;
1177  }
1178 
1179  /* are global reductions still possible */
1180  globalred = globalred && (foundbin < INT_MAX || foundnonbin < INT_MAX);
1181 
1182  /* remember the first possible position for a global bound change */
1183  if( globalred )
1184  {
1185  /* get correct variable index(, we added nprobvars for the upper bound implication) */
1186  if( foundbin < INT_MAX && foundbin >= nprobvars )
1187  foundbin -= nprobvars;
1188 
1189  /* get correct variable index(, we added nprobvars for the upper bound implication) */
1190  if( foundnonbin < INT_MAX && foundnonbin >= nprobvars )
1191  foundnonbin -= nprobvars;
1192 
1193  if( start > foundbin )
1194  start = foundbin;
1195 
1196  if( start > foundnonbin )
1197  start = foundnonbin;
1198  }
1199  else
1200  start = INT_MAX;
1201 
1202  /* check if it can find any global implications anymore */
1203  if( !usebin && !usenonbin )
1204  break;
1205  }
1206 
1207  /* remove redundant set variables */
1208  if( *nredvars > 0 )
1209  {
1210 #ifndef NDEBUG
1211  int nreds = 0;
1212 #endif
1213 
1214  for( v = nvars - 1; v >= 0; --v )
1215  {
1216  var = vars[v];
1217 
1218  varidx = SCIPvarGetProbindex(var);
1219  assert(varidx >= 0);
1220 
1221  if( boundtypes[v] )
1222  varidx += nprobvars;
1223 
1224  /* if set variable was marked to be redundant remove it */
1225  if( issetvar[varidx] < 0 )
1226  {
1227  SCIPdebugMessage("mark redundant variable <%s> to be removed from variable set\n", SCIPvarGetName(var));
1228 
1229  redundants[v] = TRUE;
1230 #ifndef NDEBUG
1231  ++nreds;
1232 #endif
1233  }
1234  }
1235  assert((*nredvars) == nreds);
1236  }
1237 
1238  /* if we found some global boundchanges, we perform then now */
1239  if( globalred )
1240  {
1241  SCIP_VAR** probvars;
1242  SCIP_VAR* probvar;
1243 
1244  SCIPdebugMessage("variable set led to global reductions (in %s)\n", SCIPprobGetName(scip->transprob));
1245 
1246  probvars = SCIPprobGetVars(scip->transprob);
1247  assert(probvars != NULL);
1248 
1249  assert(start < nprobvars);
1250 
1251  /* check for same implied binary variables */
1252  for( v = start; v < nprobvars; ++v )
1253  {
1254  probvar = probvars[v];
1255  assert(probvar != NULL);
1256 
1257  assert(counts[v] <= nvars);
1258  assert(counts[nprobvars + v] <= nvars);
1259 
1260  if( counts[v] + (*nredvars) == nvars )
1261  {
1262  if( SCIPvarIsBinary(probvar) )
1263  {
1264  SCIPdebugMessage("can fix variable %s [%g, %g] to 1.0\n", SCIPvarGetName(probvar),
1265  SCIPvarGetLbGlobal(probvar), SCIPvarGetUbGlobal(probvar));
1266 
1267  if( SCIPvarGetLbGlobal(probvar) < 0.5 )
1268  {
1269  SCIP_CALL( SCIPnodeAddBoundchg(scip->tree->root, scip->mem->probmem, scip->set, scip->stat,
1270  scip->transprob, scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand,
1271  scip->eventqueue, scip->cliquetable, probvar, 1.0, SCIP_BOUNDTYPE_LOWER, FALSE) );
1272 
1273  assert(SCIPvarGetLbGlobal(probvar) > 0.5 || scip->tree->npendingbdchgs > 0);
1274 
1275  ++(*nglobalred);
1276 
1277  if( issetvar[v] > 0 )
1278  *setredundant = TRUE;
1279  }
1280  }
1281  else
1282  {
1283  SCIPdebugMessage("can tighten lower bound variable %s [%g, %g] to %g\n", SCIPvarGetName(probvar),
1284  SCIPvarGetLbGlobal(probvar), SCIPvarGetUbGlobal(probvar), newbounds[v]);
1285 
1286  if( SCIPisLT(scip, SCIPvarGetLbGlobal(probvar), newbounds[v]) )
1287  {
1288  SCIP_CALL( SCIPnodeAddBoundchg(scip->tree->root, scip->mem->probmem, scip->set, scip->stat,
1289  scip->transprob, scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand,
1290  scip->eventqueue, scip->cliquetable, probvar, newbounds[v], SCIP_BOUNDTYPE_LOWER, FALSE) );
1291 
1292  ++(*nglobalred);
1293 
1294  if( issetvar[v] > 0 && newbounds[v] >= bounds[issetvar[v] - 1] )
1295  *setredundant = TRUE;
1296  }
1297  }
1298  }
1299  else if( counts[nprobvars + v] + (*nredvars) == nvars )
1300  {
1301  if( SCIPvarIsBinary(probvar) )
1302  {
1303  SCIPdebugMessage("can fix variable %s [%g, %g] to 0.0\n", SCIPvarGetName(probvar),
1304  SCIPvarGetLbGlobal(probvar), SCIPvarGetUbGlobal(probvar));
1305 
1306  if( SCIPvarGetUbGlobal(probvar) > 0.5 )
1307  {
1308  SCIP_CALL( SCIPnodeAddBoundchg(scip->tree->root, scip->mem->probmem, scip->set, scip->stat,
1309  scip->transprob, scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue,
1310  scip->cliquetable, probvar, 0.0, SCIP_BOUNDTYPE_UPPER, FALSE) );
1311 
1312  assert(SCIPvarGetUbGlobal(probvar) < 0.5 || scip->tree->npendingbdchgs > 0);
1313 
1314  ++(*nglobalred);
1315 
1316  if( issetvar[nprobvars + v] > 0 )
1317  *setredundant = TRUE;
1318  }
1319  }
1320  else
1321  {
1322  int idx = nprobvars + v;
1323 
1324  SCIPdebugMessage("can tighten upper bound variable %s [%g, %g] to %g\n", SCIPvarGetName(probvar),
1325  SCIPvarGetLbGlobal(probvar), SCIPvarGetUbGlobal(probvar), newbounds[idx]);
1326 
1327  if( SCIPisGT(scip, SCIPvarGetUbGlobal(probvar), newbounds[idx]) )
1328  {
1329  SCIP_CALL( SCIPnodeAddBoundchg(scip->tree->root, scip->mem->probmem, scip->set, scip->stat,
1330  scip->transprob, scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue,
1331  scip->cliquetable, probvar, newbounds[idx], SCIP_BOUNDTYPE_UPPER, FALSE) );
1332 
1333  ++(*nglobalred);
1334 
1335  if( issetvar[idx] > 0 && newbounds[idx] <= bounds[issetvar[idx] - 1] )
1336  *setredundant = TRUE;
1337  }
1338  }
1339  }
1340  }
1341  }
1342 
1343  /* reset issetvar array to 0 */
1344  for( v = 0; v < nvars; ++v )
1345  {
1346  varidx = SCIPvarGetProbindex(vars[v]);
1347  assert(varidx >= 0);
1348 
1349  if( boundtypes[v] )
1350  varidx += nprobvars;
1351 
1352  issetvar[varidx] = 0;
1353  }
1354 
1355  if( ncountnonzeros >= maxcountnonzeros )
1356  {
1357  BMSclearMemoryArray(counts, 2*nprobvars);
1358  }
1359  else
1360  {
1361  while( --ncountnonzeros >= 0 )
1362  counts[countnonzeros[ncountnonzeros]] = 0;
1363  }
1364 
1365 
1366  SCIPfreeBufferArray(scip, &countnonzeros);
1367  SCIPfreeBufferArray(scip, &implidx);
1368  SCIPfreeBufferArray(scip, &lastbounds);
1369  SCIPfreeBufferArray(scip, &newbounds);
1370  SCIPfreeCleanBufferArray(scip, &counts);
1371  SCIPfreeCleanBufferArray(scip, &issetvar);
1372 
1373  return SCIP_OKAY;
1374 }
SCIPvarGetImplVars
SCIP_VAR ** SCIPvarGetImplVars(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17250
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:41293
SCIPcliqueGetVars
SCIP_VAR ** SCIPcliqueGetVars(SCIP_CLIQUE *clique)
Definition: implics.c:3105
SCIPvarGetName
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16341
tree.h
internal methods for branch and bound tree
SCIPvarIsBinary
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16521
SCIPisFeasLT
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41528
SCIPvarGetCliques
SCIP_CLIQUE ** SCIPvarGetCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17318
NULL
#define NULL
Definition: lpi_spx.cpp:130
SCIPvarGetVubConstants
SCIP_Real * SCIPvarGetVubConstants(SCIP_VAR *var)
Definition: var.c:17221
SCIPvarGetVlbVars
SCIP_VAR ** SCIPvarGetVlbVars(SCIP_VAR *var)
Definition: var.c:17159
Scip::eventqueue
SCIP_EVENTQUEUE * eventqueue
Definition: struct_scip.h:73
SCIPvarGetUbGlobal
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:16965
SCIP_Var
Definition: struct_var.h:196
SCIPvarGetNVubs
int SCIPvarGetNVubs(SCIP_VAR *var)
Definition: var.c:17189
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 fullshortening)
Definition: presolve.c:953
SCIPprobGetNVars
int SCIPprobGetNVars(SCIP_PROB *prob)
Definition: prob.c:2157
Scip::branchcand
SCIP_BRANCHCAND * branchcand
Definition: struct_scip.h:74
FALSE
#define FALSE
Definition: def.h:53
TRUE
#define TRUE
Definition: def.h:52
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_VARTYPE_BINARY
Definition: type_var.h:53
CLEARRATIO
#define CLEARRATIO
Definition: presolve.c:930
SCIPdebugMessage
#define SCIPdebugMessage
Definition: pub_message.h:77
SCIPallocBufferArray
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:20414
Scip::transprob
SCIP_PROB * transprob
Definition: struct_scip.h:82
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:22052
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:41193
SCIPvarGetVubVars
SCIP_VAR ** SCIPvarGetVubVars(SCIP_VAR *var)
Definition: var.c:17201
prob.h
internal methods for storing and manipulating the main problem
SCIPfreeBufferArray
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:20426
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:41515
Scip::reopt
SCIP_REOPT * reopt
Definition: struct_scip.h:69
SCIPvarGetImplTypes
SCIP_BOUNDTYPE * SCIPvarGetImplTypes(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17265
SCIP_OKAY
Definition: type_retcode.h:33
SCIP_CALL
#define SCIP_CALL(x)
Definition: def.h:263
struct_scip.h
SCIP main data structure.
SCIPisFeasGT
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41554
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:41219
SCIP_Bool
#define SCIP_Bool
Definition: def.h:50
SCIPvarGetNImpls
int SCIPvarGetNImpls(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17233
SCIPvarGetVubCoefs
SCIP_Real * SCIPvarGetVubCoefs(SCIP_VAR *var)
Definition: var.c:17211
SCIPvarGetVlbConstants
SCIP_Real * SCIPvarGetVlbConstants(SCIP_VAR *var)
Definition: var.c:17179
SCIPcliqueGetValues
SCIP_Bool * SCIPcliqueGetValues(SCIP_CLIQUE *clique)
Definition: implics.c:3117
SCIPallocCleanBufferArray
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip.h:20432
SCIPvarGetNVlbs
int SCIPvarGetNVlbs(SCIP_VAR *var)
Definition: var.c:17147
SCIPvarGetType
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16506
SCIPvarGetVlbCoefs
SCIP_Real * SCIPvarGetVlbCoefs(SCIP_VAR *var)
Definition: var.c:17169
SCIPvarGetLbGlobal
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:16955
SCIP_Mem::probmem
BMS_BLKMEM * probmem
Definition: struct_mem.h:39
SCIPfreeCleanBufferArray
#define SCIPfreeCleanBufferArray(scip, ptr)
Definition: scip.h:20436
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:1979
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:41541
SCIPvarGetProbindex
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:16648
SCIP_Real
#define SCIP_Real
Definition: def.h:124
SCIPvarGetNCliques
int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17307
MIN
#define MIN(x, y)
Definition: memory.c:63
SCIP_Clique
Definition: struct_implics.h:64
SCIPisFeasGE
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41567
SCIPprobGetVars
SCIP_VAR ** SCIPprobGetVars(SCIP_PROB *prob)
Definition: prob.c:2202
SCIP_INVALID
#define SCIP_INVALID
Definition: def.h:144
SCIPprobGetNImplBinVars
int SCIPprobGetNImplBinVars(SCIP_PROB *prob)
Definition: prob.c:1890
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
SCIPcliqueGetNVars
int SCIPcliqueGetNVars(SCIP_CLIQUE *clique)
Definition: implics.c:3095
SCIPvarGetImplBounds
SCIP_Real * SCIPvarGetImplBounds(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17279
BMSclearMemoryArray
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:85
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:2148