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