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