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