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