1    	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2    	/*                                                                           */
3    	/*                  This file is part of the program and library             */
4    	/*         SCIP --- Solving Constraint Integer Programs                      */
5    	/*                                                                           */
6    	/*  Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB)                      */
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   presol_redvub.c
26   	 * @ingroup DEFPLUGINS_PRESOL
27   	 * @brief  remove redundant variable upper bound constraints
28   	 * @author Dieter Weninger
29   	 *
30   	 * This presolver looks for dominating variable bound constraints
31   	 * on the same continuous variable and discards them. For example let x be a
32   	 * continuous variable and y, y' are binary variables. In addition, let two variable
33   	 * upper bound constraints ax - by <= e and cx - dy' <= f are given. If
34   	 * ax - by <= e implies cx - dy' <= f, then we can remove the second constraint
35   	 * and substitute/aggregate y' := y. The same can be done with variable lower
36   	 * bound constraints.
37   	 *
38   	 */
39   	
40   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
41   	
42   	#include "blockmemshell/memory.h"
43   	#include "scip/presol_redvub.h"
44   	#include "scip/pub_matrix.h"
45   	#include "scip/pub_message.h"
46   	#include "scip/pub_var.h"
47   	#include "scip/scip_cons.h"
48   	#include "scip/scip_general.h"
49   	#include "scip/scip_mem.h"
50   	#include "scip/scip_message.h"
51   	#include "scip/scip_nlp.h"
52   	#include "scip/scip_numerics.h"
53   	#include "scip/scip_presol.h"
54   	#include "scip/scip_pricer.h"
55   	#include "scip/scip_prob.h"
56   	#include "scip/scip_probing.h"
57   	#include "scip/scip_var.h"
58   	
59   	#define PRESOL_NAME            "redvub"
60   	#define PRESOL_DESC            "detect redundant variable bound constraints"
61   	#define PRESOL_PRIORITY        -9000000     /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */
62   	#define PRESOL_MAXROUNDS               0     /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
63   	#define PRESOL_TIMING           SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */
64   	
65   	#define MAXPAIRCOMP                 1000     /**< maximal number of pairwise comparisons */
66   	
67   	/*
68   	 * Local methods
69   	 */
70   	
71   	/** verify if the constraint is a variable upper bound constraint */
72   	static
73   	SCIP_Bool isVub(
74   	   SCIP*                 scip,               /**< SCIP main data structure */
75   	   SCIP_MATRIX*          matrix,             /**< matrix instance */
76   	   int                   row,                /**< row index */
77   	   SCIP_Real*            lowthreshold,       /**< low switching threshold */
78   	   SCIP_Real*            highthreshold,      /**< high switching threshold */
79   	   int*                  conidx,             /**< variable index of continuous variable */
80   	   int*                  binidx              /**< variable index of binary variable */
81   	   )
82   	{
83   	   SCIP_Real* valpnt;
84   	   int* rowpnt;
85   	   SCIP_Bool isvub;
86   	
87   	   assert(scip != NULL);
88   	   assert(matrix != NULL);
89   	   assert(0 <= row && row < SCIPmatrixGetNRows(matrix));
90   	   assert(lowthreshold != NULL);
91   	   assert(highthreshold != NULL);
92   	   assert(conidx != NULL);
93   	   assert(binidx != NULL);
94   	
95   	   isvub = FALSE;
96   	
97   	   if( SCIPmatrixGetRowNNonzs(matrix, row) == 2 && SCIPmatrixIsRowRhsInfinity(matrix, row) )
98   	   {
99   	      SCIP_VARTYPE type1;
100  	      SCIP_VARTYPE type2;
101  	      int idx1;
102  	      int idx2;
103  	      SCIP_VAR* var1;
104  	      SCIP_VAR* var2;
105  	      SCIP_Real val1;
106  	      SCIP_Real val2;
107  	
108  	      rowpnt = SCIPmatrixGetRowIdxPtr(matrix, row);
109  	      valpnt = SCIPmatrixGetRowValPtr(matrix, row);
110  	
111  	      idx1 = *rowpnt;
112  	      val1 = *valpnt;
113  	      var1 = SCIPmatrixGetVar(matrix, idx1);
114  	      type1 = SCIPvarGetType(var1);
115  	
116  	      rowpnt++;
117  	      valpnt++;
118  	
119  	      idx2 = *rowpnt;
120  	      val2 = *valpnt;
121  	      var2 = SCIPmatrixGetVar(matrix, idx2);
122  	      type2 = SCIPvarGetType(var2);
123  	
124  	      /* we claim that the vub has the structure ax + cy >= b
125  	       * with a<0, c>0, x continuous, x>=0, y binary and obj(y)>=0
126  	       */
127  	      if( (type1 == SCIP_VARTYPE_CONTINUOUS && type2 == SCIP_VARTYPE_BINARY)
128  	         && val1 < 0.0 && val2 > 0.0 && SCIPisGE(scip, SCIPvarGetLbGlobal(var1), 0.0)
129  	         && SCIPisGE(scip, SCIPvarGetObj(var2), 0.0) )
130  	      {
131  	         *lowthreshold = SCIPmatrixGetRowLhs(matrix, row) / val1;
132  	         *highthreshold = (SCIPmatrixGetRowLhs(matrix, row) - val2) / val1;
133  	         *conidx = idx1;
134  	         *binidx = idx2;
135  	         isvub = TRUE;
136  	      }
137  	      else if( (type1 == SCIP_VARTYPE_BINARY && type2 == SCIP_VARTYPE_CONTINUOUS)
138  	         && val1 > 0.0 && val2 < 0.0 && SCIPisGE(scip, SCIPvarGetLbGlobal(var2), 0.0)
139  	         && SCIPisGE(scip, SCIPvarGetObj(var1), 0.0) )
140  	      {
141  	         *lowthreshold = SCIPmatrixGetRowLhs(matrix, row) / val2;
142  	         *highthreshold = (SCIPmatrixGetRowLhs(matrix, row) - val1) / val2;
143  	         *conidx = idx2;
144  	         *binidx = idx1;
145  	         isvub = TRUE;
146  	      }
147  	   }
148  	
149  	   return isvub;
150  	}
151  	
152  	/** verify if the constraint is a variable lower bound constraint */
153  	static
154  	SCIP_Bool isVlb(
155  	   SCIP*                 scip,               /**< SCIP main data structure */
156  	   SCIP_MATRIX*          matrix,             /**< matrix instance */
157  	   int                   row,                /**< row index */
158  	   SCIP_Real*            lowthreshold,       /**< low switching threshold */
159  	   SCIP_Real*            highthreshold,      /**< high switching threshold */
160  	   int*                  conidx,             /**< variable index of continuous variable */
161  	   int*                  binidx              /**< variable index of binary variable */
162  	   )
163  	{
164  	   SCIP_Real* valpnt;
165  	   int* rowpnt;
166  	   SCIP_Bool isvlb;
167  	
168  	   assert(scip != NULL);
169  	   assert(matrix != NULL);
170  	   assert(0 <= row && row < SCIPmatrixGetNRows(matrix));
171  	   assert(lowthreshold != NULL);
172  	   assert(highthreshold != NULL);
173  	   assert(conidx != NULL);
174  	   assert(binidx != NULL);
175  	
176  	   isvlb = FALSE;
177  	
178  	   if( SCIPmatrixGetRowNNonzs(matrix, row) == 2 && SCIPmatrixIsRowRhsInfinity(matrix, row) )
179  	   {
180  	      SCIP_VARTYPE type1;
181  	      SCIP_VARTYPE type2;
182  	      int idx1;
183  	      int idx2;
184  	      SCIP_VAR* var1;
185  	      SCIP_VAR* var2;
186  	      SCIP_Real val1;
187  	      SCIP_Real val2;
188  	
189  	      rowpnt = SCIPmatrixGetRowIdxPtr(matrix, row);
190  	      valpnt = SCIPmatrixGetRowValPtr(matrix, row);
191  	
192  	      idx1 = *rowpnt;
193  	      val1 = *valpnt;
194  	      var1 = SCIPmatrixGetVar(matrix, idx1);
195  	      type1 = SCIPvarGetType(var1);
196  	
197  	      rowpnt++;
198  	      valpnt++;
199  	
200  	      idx2 = *rowpnt;
201  	      val2 = *valpnt;
202  	      var2 = SCIPmatrixGetVar(matrix, idx2);
203  	      type2 = SCIPvarGetType(var2);
204  	
205  	      /* we claim that the vlb has the structure ax + cy >= b
206  	       * with a>0, c<0, x continuous, x>=0, y binary and obj(y)>=0
207  	       */
208  	      if( (type1 == SCIP_VARTYPE_CONTINUOUS && type2 == SCIP_VARTYPE_BINARY)
209  	         && val1 > 0.0 && val2 < 0.0 && SCIPisGE(scip, SCIPvarGetLbGlobal(var1), 0.0)
210  	         && SCIPisGE(scip, SCIPvarGetObj(var2), 0.0) )
211  	      {
212  	         *lowthreshold = SCIPmatrixGetRowLhs(matrix, row) / val1;
213  	         *highthreshold = (SCIPmatrixGetRowLhs(matrix, row) - val2) / val1;
214  	         *conidx = idx1;
215  	         *binidx = idx2;
216  	         isvlb = TRUE;
217  	      }
218  	      else if( (type1 == SCIP_VARTYPE_BINARY && type2 == SCIP_VARTYPE_CONTINUOUS)
219  	         && val1 < 0.0 && val2 > 0.0 && SCIPisGE(scip, SCIPvarGetLbGlobal(var2), 0.0)
220  	         && SCIPisGE(scip, SCIPvarGetObj(var1), 0.0) )
221  	      {
222  	         *lowthreshold = SCIPmatrixGetRowLhs(matrix, row) / val2;
223  	         *highthreshold = (SCIPmatrixGetRowLhs(matrix, row) - val1) / val2;
224  	         *conidx = idx2;
225  	         *binidx = idx1;
226  	         isvlb = TRUE;
227  	      }
228  	   }
229  	
230  	   return isvlb;
231  	}
232  	
233  	
234  	/** searches for variable upper bound constraints on the same continuous variable with a dominance relation */
235  	static
236  	SCIP_RETCODE detectDominatingVubs(
237  	   SCIP*                 scip,               /**< SCIP main data structure */
238  	   SCIP_MATRIX*          matrix,             /**< matrix containing the constraints */
239  	   int                   nvubs,              /**< number of vubs */
240  	   int*                  vubs,               /**< row indices of the vubs */
241  	   SCIP_Real*            lowthresholds,      /**< low switching thresholds */
242  	   SCIP_Real*            highthresholds,     /**< high switching thresholds */
243  	   int*                  conidxs,            /**< variable indexes of continuous variable */
244  	   int*                  binidxs,            /**< variable indexes of binary variable */
245  	   int*                  nvaragg,            /**< number of variables for aggregation */
246  	   SCIP_Bool*            isvartoagg,         /**< flags indicating if variable could be aggregated */
247  	   SCIP_VAR**            aggvars,            /**< pointers to the variables by which the aggregation should be done */
248  	   int*                  ndeletecons,        /**< number of deleteable constraints */
249  	   SCIP_Bool*            deletecons          /**< flags which constraints could be deleted */
250  	   )
251  	{
252  	   int i;
253  	   int j;
254  	   SCIP_Bool uselinearscan;
255  	
256  	   assert(scip != NULL);
257  	   assert(matrix != NULL);
258  	   assert(vubs != NULL);
259  	   assert(nvubs >= 2);
260  	   assert(lowthresholds != NULL);
261  	   assert(highthresholds != NULL);
262  	   assert(conidxs != NULL);
263  	   assert(binidxs != NULL);
264  	   assert(nvaragg != NULL);
265  	   assert(isvartoagg != NULL);
266  	   assert(aggvars != NULL);
267  	   assert(ndeletecons != NULL);
268  	   assert(deletecons != NULL);
269  	
270  	   /* use pairwise comparison only for a small number of vub constraints */
271  	   if( nvubs >= MAXPAIRCOMP )
272  	      uselinearscan = TRUE;
273  	   else
274  	      uselinearscan = FALSE;
275  	
276  	   for( i = 0; i < nvubs; i++ )
277  	   {
278  	      for( j = i+1; j < nvubs; j++ )
279  	      {
280  	         SCIP_VAR* var1;
281  	         SCIP_VAR* var2;
282  	
283  	         if( !SCIPisEQ(scip, lowthresholds[i], lowthresholds[j]) )
284  	            continue;
285  	
286  	         var1 = SCIPmatrixGetVar(matrix, binidxs[i]);
287  	         var2 = SCIPmatrixGetVar(matrix, binidxs[j]);
288  	
289  	         /* make sure that the binary variables switch synchronously */
290  	         if((SCIPmatrixGetColNDownlocks(matrix, binidxs[j]) == 1 &&
291  	               SCIPmatrixGetColNDownlocks(matrix, binidxs[i]) == 1 &&
292  	               SCIPmatrixGetColNUplocks(matrix, binidxs[j]) == 0 &&
293  	               SCIPmatrixGetColNUplocks(matrix, binidxs[i]) == 0) ||
294  	            (SCIPvarsHaveCommonClique(var1, FALSE, var2, TRUE, TRUE) &&
295  	               SCIPvarsHaveCommonClique(var1, TRUE, var2, FALSE, TRUE)) )
296  	         {
297  	            if( SCIPisLE(scip, highthresholds[i], highthresholds[j]) )
298  	            {
299  	#ifdef SCIP_DEBUG
300  	               SCIPdebugMsg(scip, "Aggregate variable %s by %s\n", SCIPvarGetName(var2), SCIPvarGetName(var1));
301  	               SCIPdebugMsg(scip, "Delete variable upper bound constraint:\n");
302  	               SCIP_CALL( SCIPprintCons(scip, SCIPmatrixGetCons(matrix, vubs[j]), NULL));
303  	               SCIPinfoMessage(scip, NULL, "\n");
304  	#endif
305  	
306  	               isvartoagg[binidxs[j]] = TRUE;
307  	               aggvars[binidxs[j]] = SCIPmatrixGetVar(matrix, binidxs[i]);
308  	               (*nvaragg)++;
309  	
310  	               deletecons[vubs[j]] = TRUE;
311  	               (*ndeletecons)++;
312  	            }
313  	            else
314  	            {
315  	               assert(SCIPisGT(scip, highthresholds[i], highthresholds[j]));
316  	#ifdef SCIP_DEBUG
317  	               SCIPdebugMsg(scip, "Aggregate variable %s by %s\n", SCIPvarGetName(var1), SCIPvarGetName(var2));
318  	               SCIPdebugMsg(scip, "Delete variable upper bound constraint:\n");
319  	               SCIP_CALL( SCIPprintCons(scip, SCIPmatrixGetCons(matrix, vubs[i]), NULL));
320  	               SCIPinfoMessage(scip, NULL, "\n");
321  	#endif
322  	
323  	               isvartoagg[binidxs[i]] = TRUE;
324  	               aggvars[binidxs[i]] = SCIPmatrixGetVar(matrix, binidxs[j]);
325  	               (*nvaragg)++;
326  	
327  	               deletecons[vubs[i]] = TRUE;
328  	               (*ndeletecons)++;
329  	            }
330  	         }
331  	
332  	         if( uselinearscan )
333  	            break;
334  	      }
335  	   }
336  	
337  	   return SCIP_OKAY;
338  	}
339  	
340  	/** searches for variable lower bound constraints on the same continuous variable with a dominance relation */
341  	static
342  	SCIP_RETCODE detectDominatingVlbs(
343  	   SCIP*                 scip,               /**< SCIP main data structure */
344  	   SCIP_MATRIX*          matrix,             /**< matrix containing the constraints */
345  	   int                   nvlbs,              /**< number of vlbs */
346  	   int*                  vlbs,               /**< row indices of the vlbs */
347  	   SCIP_Real*            lowthresholds,      /**< low switching thresholds */
348  	   SCIP_Real*            highthresholds,     /**< high switching thresholds */
349  	   int*                  conidxs,            /**< variable indexes of continuous variable */
350  	   int*                  binidxs,            /**< variable indexes of binary variable */
351  	   int*                  nvaragg,            /**< number of variables for aggregation */
352  	   SCIP_Bool*            isvartoagg,         /**< flags indicating if variable could be aggregated */
353  	   SCIP_VAR**            aggvars,            /**< pointers to the variables by which the aggregation should be done */
354  	   int*                  ndeletecons,        /**< number of deleteable constraints */
355  	   SCIP_Bool*            deletecons          /**< flags which constraints could be deleted */
356  	
357  	   )
358  	{
359  	   int i;
360  	   int j;
361  	   SCIP_Bool uselinearscan;
362  	
363  	   assert(scip != NULL);
364  	   assert(matrix != NULL);
365  	   assert(vlbs != NULL);
366  	   assert(nvlbs >= 2);
367  	   assert(lowthresholds != NULL);
368  	   assert(highthresholds != NULL);
369  	   assert(conidxs != NULL);
370  	   assert(binidxs != NULL);
371  	   assert(nvaragg != NULL);
372  	   assert(isvartoagg != NULL);
373  	   assert(aggvars != NULL);
374  	   assert(ndeletecons != NULL);
375  	   assert(deletecons != NULL);
376  	
377  	   /* use pairwise comparison only for a small number of vlb constraints */
378  	   if( nvlbs >= MAXPAIRCOMP )
379  	      uselinearscan = TRUE;
380  	   else
381  	      uselinearscan = FALSE;
382  	
383  	   for( i = 0; i < nvlbs; i++ )
384  	   {
385  	      for( j = i+1; j < nvlbs; j++ )
386  	      {
387  	         SCIP_VAR* var1;
388  	         SCIP_VAR* var2;
389  	
390  	         if( !SCIPisEQ(scip, lowthresholds[i], lowthresholds[j]) )
391  	            continue;
392  	
393  	         var1 = SCIPmatrixGetVar(matrix, binidxs[i]);
394  	         var2 = SCIPmatrixGetVar(matrix, binidxs[j]);
395  	
396  	         /* make sure that the binary variables switch synchronously */
397  	         if((SCIPmatrixGetColNUplocks(matrix, binidxs[j]) == 1 &&
398  	               SCIPmatrixGetColNUplocks(matrix, binidxs[i]) == 1 &&
399  	               SCIPmatrixGetColNDownlocks(matrix, binidxs[j]) == 0 &&
400  	               SCIPmatrixGetColNDownlocks(matrix, binidxs[i]) == 0) ||
401  	            (SCIPvarsHaveCommonClique(var1, FALSE, var2, TRUE, TRUE) &&
402  	               SCIPvarsHaveCommonClique(var1, TRUE, var2, FALSE, TRUE)) )
403  	         {
404  	            if( SCIPisGE(scip, highthresholds[i], highthresholds[j]) )
405  	            {
406  	#ifdef SCIP_DEBUG
407  	               SCIPdebugMsg(scip, "Aggregate variable %s by %s\n", SCIPvarGetName(var2), SCIPvarGetName(var1));
408  	               SCIPdebugMsg(scip, "Delete variable lower bound constraint:\n");
409  	               SCIP_CALL( SCIPprintCons(scip, SCIPmatrixGetCons(matrix, vlbs[j]), NULL));
410  	               SCIPinfoMessage(scip, NULL, "\n");
411  	#endif
412  	
413  	               isvartoagg[binidxs[j]] = TRUE;
414  	               aggvars[binidxs[j]] = SCIPmatrixGetVar(matrix, binidxs[i]);
415  	               (*nvaragg)++;
416  	
417  	               deletecons[vlbs[j]] = TRUE;
418  	               (*ndeletecons)++;
419  	            }
420  	            else
421  	            {
422  	               assert(SCIPisLT(scip, highthresholds[i], highthresholds[j]));
423  	#ifdef SCIP_DEBUG
424  	               SCIPdebugMsg(scip, "Aggregate variable %s by %s\n", SCIPvarGetName(var1), SCIPvarGetName(var2));
425  	               SCIPdebugMsg(scip, "Delete variable lower bound constraint:\n");
426  	               SCIP_CALL( SCIPprintCons(scip, SCIPmatrixGetCons(matrix, vlbs[i]), NULL));
427  	               SCIPinfoMessage(scip, NULL, "\n");
428  	#endif
429  	
430  	               isvartoagg[binidxs[i]] = TRUE;
431  	               aggvars[binidxs[i]] = SCIPmatrixGetVar(matrix, binidxs[j]);
432  	               (*nvaragg)++;
433  	
434  	               deletecons[vlbs[i]] = TRUE;
435  	               (*ndeletecons)++;
436  	            }
437  	         }
438  	
439  	         if( uselinearscan )
440  	            break;
441  	      }
442  	   }
443  	
444  	   return SCIP_OKAY;
445  	}
446  	
447  	/** find variable aggregations and redundant variable bound constraints */
448  	static
449  	SCIP_RETCODE findVarAggrRedVbcons(
450  	   SCIP*                 scip,               /**< SCIP main data structure */
451  	   SCIP_MATRIX*          matrix,             /**< constraint matrix */
452  	   int*                  nvaragg,            /**< number of redundant variables */
453  	   SCIP_Bool*            isvartoagg,         /**< flags indicating which variables could be substituted/aggregated */
454  	   SCIP_VAR**            aggvars,            /**< pointers to the variables by which the aggregation should be done */
455  	   int*                  ndeletecons,        /**< number of redundant constraints */
456  	   SCIP_Bool*            deletecons          /**< flags indicating which constraints could be deleted */
457  	   )
458  	{
459  	   int c;
460  	   int* colpnt;
461  	   int* colend;
462  	   int* vbcons;
463  	   int nvbcons;
464  	   int ncols;
465  	   int nrows;
466  	   SCIP_Real* lowthresholds;
467  	   SCIP_Real* highthresholds;
468  	   int* conidxs;
469  	   int* binidxs;
470  	
471  	   ncols = SCIPmatrixGetNColumns(matrix);
472  	   nrows = SCIPmatrixGetNRows(matrix);
473  	
474  	   SCIP_CALL( SCIPallocBufferArray(scip, &binidxs, nrows) );
475  	   SCIP_CALL( SCIPallocBufferArray(scip, &conidxs, nrows) );
476  	   SCIP_CALL( SCIPallocBufferArray(scip, &lowthresholds, nrows) );
477  	   SCIP_CALL( SCIPallocBufferArray(scip, &highthresholds, nrows) );
478  	   SCIP_CALL( SCIPallocBufferArray(scip, &vbcons, nrows) );
479  	
480  	   for( c = 0; c < ncols; c++ )
481  	   {
482  	      SCIP_VAR* var;
483  	
484  	      var = SCIPmatrixGetVar(matrix, c);
485  	
486  	      if( SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS )
487  	         continue;
488  	
489  	      /* search vubs per variable */
490  	      nvbcons = 0;
491  	      colpnt = SCIPmatrixGetColIdxPtr(matrix, c);
492  	      colend = colpnt + SCIPmatrixGetColNNonzs(matrix, c);
493  	      for( ; (colpnt < colend); colpnt++ )
494  	      {
495  	         SCIP_Real lowthreshold;
496  	         SCIP_Real highthreshold;
497  	         int conidx;
498  	         int binidx;
499  	
500  	         if( isVub(scip, matrix, *colpnt, &lowthreshold, &highthreshold, &conidx, &binidx) )
501  	         {
502  	            vbcons[nvbcons] = *colpnt;
503  	            lowthresholds[nvbcons] = lowthreshold;
504  	            highthresholds[nvbcons] = highthreshold;
505  	            conidxs[nvbcons] = conidx;
506  	            binidxs[nvbcons] = binidx;
507  	            nvbcons++;
508  	         }
509  	      }
510  	      if( nvbcons >= 2 )
511  	      {
512  	         SCIP_CALL( detectDominatingVubs(scip, matrix, nvbcons, vbcons,
513  	               lowthresholds, highthresholds, conidxs, binidxs,
514  	               nvaragg, isvartoagg, aggvars, ndeletecons, deletecons) );
515  	      }
516  	
517  	      /* search vlbs per variable */
518  	      nvbcons = 0;
519  	      colpnt = SCIPmatrixGetColIdxPtr(matrix, c);
520  	      colend = colpnt + SCIPmatrixGetColNNonzs(matrix, c);
521  	      for( ; (colpnt < colend); colpnt++ )
522  	      {
523  	         SCIP_Real lowthreshold;
524  	         SCIP_Real highthreshold;
525  	         int conidx;
526  	         int binidx;
527  	
528  	         if( isVlb(scip, matrix, *colpnt, &lowthreshold, &highthreshold, &conidx, &binidx) )
529  	         {
530  	            vbcons[nvbcons] = *colpnt;
531  	            lowthresholds[nvbcons] = lowthreshold;
532  	            highthresholds[nvbcons] = highthreshold;
533  	            conidxs[nvbcons] = conidx;
534  	            binidxs[nvbcons] = binidx;
535  	            nvbcons++;
536  	         }
537  	      }
538  	      if( nvbcons >= 2 )
539  	      {
540  	         SCIP_CALL( detectDominatingVlbs(scip, matrix, nvbcons, vbcons,
541  	               lowthresholds, highthresholds, conidxs, binidxs,
542  	               nvaragg, isvartoagg, aggvars, ndeletecons, deletecons) );
543  	      }
544  	   }
545  	
546  	   SCIPfreeBufferArray(scip, &vbcons);
547  	   SCIPfreeBufferArray(scip, &highthresholds);
548  	   SCIPfreeBufferArray(scip, &lowthresholds);
549  	   SCIPfreeBufferArray(scip, &conidxs);
550  	   SCIPfreeBufferArray(scip, &binidxs);
551  	
552  	   return SCIP_OKAY;
553  	}
554  	
555  	
556  	/*
557  	 * Callback methods of presolver
558  	 */
559  	
560  	
561  	/** execution method of presolver */
562  	static
563  	SCIP_DECL_PRESOLEXEC(presolExecRedvub)
564  	{  /*lint --e{715}*/
565  	   SCIP_MATRIX* matrix;
566  	   SCIP_Bool initialized;
567  	   SCIP_Bool complete;
568  	   SCIP_Bool infeasible;
569  	
570  	   assert(result != NULL);
571  	   *result = SCIP_DIDNOTRUN;
572  	
573  	   if( (SCIPgetStage(scip) != SCIP_STAGE_PRESOLVING) || SCIPinProbing(scip) || SCIPisNLPEnabled(scip) )
574  	      return SCIP_OKAY;
575  	
576  	   if( SCIPgetNContVars(scip) == 0 || SCIPisStopped(scip) || SCIPgetNActivePricers(scip) > 0 )
577  	      return SCIP_OKAY;
578  	
579  	   *result = SCIP_DIDNOTFIND;
580  	
581  	   matrix = NULL;
582  	   SCIP_CALL( SCIPmatrixCreate(scip, &matrix, TRUE, &initialized, &complete, &infeasible,
583  	      naddconss, ndelconss, nchgcoefs, nchgbds, nfixedvars) );
584  	
585  	   /* if infeasibility was detected during matrix creation, return here */
586  	   if( infeasible )
587  	   {
588  	      if( initialized )
589  	         SCIPmatrixFree(scip, &matrix);
590  	
591  	      *result = SCIP_CUTOFF;
592  	      return SCIP_OKAY;
593  	   }
594  	
595  	   if( initialized && complete )
596  	   {
597  	      int nvaragg;
598  	      SCIP_Bool* isvartoagg;
599  	      int ndeletecons;
600  	      SCIP_Bool* deletecons;
601  	      SCIP_VAR** aggvars;
602  	      int ncols;
603  	      int nrows;
604  	
605  	      ncols = SCIPmatrixGetNColumns(matrix);
606  	      nrows = SCIPmatrixGetNRows(matrix);
607  	
608  	      nvaragg = 0;
609  	      ndeletecons = 0;
610  	
611  	      SCIP_CALL( SCIPallocBufferArray(scip, &isvartoagg, ncols) );
612  	      BMSclearMemoryArray(isvartoagg, ncols);
613  	
614  	      SCIP_CALL( SCIPallocBufferArray(scip, &deletecons, nrows) );
615  	      BMSclearMemoryArray(deletecons, nrows);
616  	
617  	      SCIP_CALL( SCIPallocBufferArray(scip, &aggvars, ncols) );
618  	      BMSclearMemoryArray(aggvars, ncols);
619  	
620  	      SCIP_CALL( findVarAggrRedVbcons(scip, matrix, &nvaragg, isvartoagg, aggvars, &ndeletecons, deletecons) );
621  	
622  	      if( nvaragg > 0 )
623  	      {
624  	         int v;
625  	         for( v = 0; v < ncols; v++ )
626  	         {
627  	            if( isvartoagg[v] )
628  	            {
629  	               SCIP_Bool redundant;
630  	               SCIP_Bool aggregated;
631  	
632  	               /* substitute/aggregate binary variable */
633  	               assert(aggvars[v] != NULL);
634  	               SCIP_CALL( SCIPaggregateVars(scip, SCIPmatrixGetVar(matrix,v), aggvars[v], 1.0, -1.0,
635  	                     0.0, &infeasible, &redundant, &aggregated) );
636  	
637  	               if( infeasible )
638  	               {
639  	                  SCIPdebugMsg(scip, " -> infeasible aggregation\n");
640  	                  *result = SCIP_CUTOFF;
641  	                  return SCIP_OKAY;
642  	               }
643  	
644  	               if( aggregated )
645  	               {
646  	                  (*naggrvars)++;
647  	
648  	                  /* set result pointer */
649  	                  if( (*result) == SCIP_DIDNOTFIND )
650  	                     *result = SCIP_SUCCESS;
651  	               }
652  	            }
653  	         }
654  	      }
655  	
656  	      if( ndeletecons > 0 )
657  	      {
658  	         int r;
659  	         for( r = 0; r < nrows; r++ )
660  	         {
661  	            if( deletecons[r] )
662  	            {
663  	               SCIP_CONS* cons;
664  	
665  	               /* remove redundant variable bound constraint */
666  	               cons = SCIPmatrixGetCons(matrix, r);
667  	               SCIP_CALL( SCIPdelCons(scip, cons) );
668  	
669  	               (*ndelconss)++;
670  	
671  	               /* set result pointer */
672  	               if( (*result) == SCIP_DIDNOTFIND )
673  	                  *result = SCIP_SUCCESS;
674  	            }
675  	         }
676  	      }
677  	
678  	      SCIPfreeBufferArray(scip, &aggvars);
679  	      SCIPfreeBufferArray(scip, &deletecons);
680  	      SCIPfreeBufferArray(scip, &isvartoagg);
681  	   }
682  	
683  	   SCIPmatrixFree(scip, &matrix);
684  	
685  	   return SCIP_OKAY;
686  	}
687  	
688  	/*
689  	 * presolver specific interface methods
690  	 */
691  	
692  	/** creates the redvub presolver and includes it in SCIP */
693  	SCIP_RETCODE SCIPincludePresolRedvub(
694  	   SCIP*                 scip                /**< SCIP data structure */
695  	   )
696  	{
697  	   SCIP_PRESOL* presol;
698  	
699  	   /* include presolver */
700  	   SCIP_CALL( SCIPincludePresolBasic(scip, &presol, PRESOL_NAME, PRESOL_DESC, PRESOL_PRIORITY, PRESOL_MAXROUNDS,
701  	         PRESOL_TIMING, presolExecRedvub, NULL) );
702  	
703  	   return SCIP_OKAY;
704  	}
705