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_dualagg.c
26   	 * @ingroup DEFPLUGINS_PRESOL
27   	 * @brief  aggregate variables by dual arguments
28   	 * @author Dieter Weninger
29   	 *
30   	 * This presolver looks for variables which could not be handled by
31   	 * duality fixing because of one up-/downlock.
32   	 * If the constraint which delivers the up-/downlock has
33   	 * a specific structure, we can aggregate the corresponding variable.
34   	 *
35   	 * In more detail (for a minimization problem and the case of only one uplock):
36   	 *
37   	 * Given a variable \f$x_i\f$ with \f$c_i \leq 0\f$ and only one up lock (originating from a constraint c),
38   	 * we are looking for a binary variable \f$x_j\f$ such that:
39   	 * 1. if \f$x_j = 0\f$, constraint c can only be fulfilled for \f$x_i = lb_i\f$, and
40   	 * 2. if \f$x_j = 1\f$, constraint c becomes redundant and \f$x_i\f$ can be dual-fixed to its upper bound \f$ub_i\f$
41   	 * (or vice versa). Then we can perform the following aggregation: \f$x_i = lb_i + x_j (ub_i - lb_i)\f$.
42   	 *
43   	 * Similar arguments apply for the case of only one down lock and \f$c_i \geq 0\f$.
44   	 */
45   	
46   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
47   	
48   	#include "blockmemshell/memory.h"
49   	#include "scip/presol_dualagg.h"
50   	#include "scip/pub_matrix.h"
51   	#include "scip/pub_message.h"
52   	#include "scip/pub_var.h"
53   	#include "scip/scip_general.h"
54   	#include "scip/scip_mem.h"
55   	#include "scip/scip_message.h"
56   	#include "scip/scip_nlp.h"
57   	#include "scip/scip_numerics.h"
58   	#include "scip/scip_presol.h"
59   	#include "scip/scip_pricer.h"
60   	#include "scip/scip_prob.h"
61   	#include "scip/scip_probing.h"
62   	#include "scip/scip_var.h"
63   	
64   	#define PRESOL_NAME            "dualagg"
65   	#define PRESOL_DESC            "aggregate variables by dual arguments"
66   	#define PRESOL_PRIORITY           -12000     /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */
67   	#define PRESOL_MAXROUNDS               0     /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
68   	#define PRESOL_TIMING           SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */
69   	
70   	/** type of aggregation */
71   	enum AggrType
72   	{
73   	   BIN0UBOUND = -1,         /**< x_j = u_j + (l_j-u_j)x_i with x_i binary and x_j aggregation variable */
74   	   NOAGG      =  0,         /**< do not aggregate */
75   	   BIN0LBOUND =  1          /**< x_j = l_j + (u_j-l_j)x_i with x_i binary and x_j aggregation variable */
76   	};
77   	typedef enum AggrType AGGRTYPE;
78   	
79   	/*
80   	 * Local methods
81   	 */
82   	
83   	/** find row which leads to the uplock of the given variable */
84   	static
85   	void getUplockRowIdx(
86   	   SCIP_MATRIX*          matrix,             /**< constraint matrix */
87   	   int                   aggvaridx,          /**< index of variable which should be aggregated */
88   	   int*                  rowidx,             /**< pointer to store row index of uplock */
89   	   SCIP_Real*            coef                /**< pointer to store coefficient of variable */
90   	   )
91   	{
92   	   int* colpnt;
93   	   int* colend;
94   	   SCIP_Real* valpnt;
95   	
96   	   assert(rowidx != NULL);
97   	   assert(coef != NULL);
98   	   assert(SCIPmatrixGetColNUplocks(matrix, aggvaridx) == 1);
99   	
100  	   /* get nonzero entries of the variable in the matrix */
101  	   colpnt = SCIPmatrixGetColIdxPtr(matrix, aggvaridx);
102  	   colend = colpnt + SCIPmatrixGetColNNonzs(matrix, aggvaridx);
103  	   valpnt = SCIPmatrixGetColValPtr(matrix, aggvaridx);
104  	
105  	   /* iterate over all non-zero coefficients of the column */
106  	   *rowidx = -1;
107  	   for(; (colpnt < colend); colpnt++, valpnt++)
108  	   {
109  	      /* currently we support only >= relation */
110  	      if( !SCIPmatrixIsRowRhsInfinity(matrix, *colpnt) )
111  	         break;
112  	
113  	      /* coef < 0 for >= relation: this row provides an uplock for the variable */
114  	      if( *valpnt < 0.0 )
115  	      {
116  	         *rowidx = *colpnt;
117  	         *coef = *valpnt;
118  	         break;
119  	      }
120  	   }
121  	#ifndef NDEBUG
122  	   /* in debug mode, we check that the lock number is correct */
123  	   assert(colpnt < colend);
124  	   for(colpnt++, valpnt++; (colpnt < colend); colpnt++, valpnt++)
125  	   {
126  	      assert(*valpnt > 0.0);
127  	   }
128  	#endif
129  	}
130  	
131  	/** find row which leads to the downlock of the given variable */
132  	static
133  	void getDownlockRowIdx(
134  	   SCIP_MATRIX*          matrix,             /**< constraint matrix */
135  	   int                   aggvaridx,          /**< index of variable which should be aggregated */
136  	   int*                  rowidx,             /**< pointer to store row index of downlock */
137  	   SCIP_Real*            coef                /**< pointer to store coefficient of variable */
138  	   )
139  	{
140  	   int* colpnt;
141  	   int* colend;
142  	   SCIP_Real* valpnt;
143  	
144  	   assert(rowidx != NULL);
145  	   assert(coef != NULL);
146  	   assert(SCIPmatrixGetColNDownlocks(matrix, aggvaridx) == 1);
147  	
148  	   /* get nonzero entries of the variable in the matrix */
149  	   colpnt = SCIPmatrixGetColIdxPtr(matrix, aggvaridx);
150  	   colend = colpnt + SCIPmatrixGetColNNonzs(matrix, aggvaridx);
151  	   valpnt = SCIPmatrixGetColValPtr(matrix, aggvaridx);
152  	
153  	   /* iterate over all non-zero coefficients of the column */
154  	   *rowidx = -1;
155  	   for(; (colpnt < colend); colpnt++, valpnt++)
156  	   {
157  	      /* currently we support only >= relation */
158  	      if( !SCIPmatrixIsRowRhsInfinity(matrix, *colpnt) )
159  	         break;
160  	
161  	      /* coef > 0 for >= relation: this row provides a downlock for the variable */
162  	      if( *valpnt > 0.0 )
163  	      {
164  	         *rowidx = *colpnt;
165  	         *coef = *valpnt;
166  	         break;
167  	      }
168  	   }
169  	#ifndef NDEBUG
170  	   /* in debug mode, we check that the lock number is correct */
171  	   assert(colpnt < colend);
172  	   for(colpnt++, valpnt++; (colpnt < colend); colpnt++, valpnt++)
173  	   {
174  	      assert(*valpnt < 0.0);
175  	   }
176  	#endif
177  	}
178  	
179  	/** find fitting binary variable aggregation for uplock case */
180  	static
181  	void getBinVarIdxInUplockRow(
182  	   SCIP*                 scip,               /**< SCIP main data structure */
183  	   SCIP_MATRIX*          matrix,             /**< constraint matrix */
184  	   int                   aggvaridx,          /**< index of variable which should be aggregated */
185  	   int*                  binvaridx,          /**< pointer to store index of binary variable */
186  	   AGGRTYPE*             aggtype             /**< pointer to store type of aggregation */
187  	   )
188  	{
189  	   int rowidx;
190  	   SCIP_Real coef;
191  	   int* rowpnt;
192  	   int* rowend;
193  	   SCIP_Real* valpnt;
194  	   SCIP_Real minact;
195  	   SCIP_Real maxact;
196  	   SCIP_Real lhs;
197  	   SCIP_Real lb;
198  	
199  	   assert(binvaridx != NULL);
200  	   assert(aggtype != NULL);
201  	
202  	   *binvaridx = -1;
203  	   *aggtype = NOAGG;
204  	
205  	   getUplockRowIdx(matrix, aggvaridx, &rowidx, &coef);
206  	
207  	   if( rowidx < 0 )
208  	      return;
209  	
210  	   assert(coef < 0);
211  	   minact = SCIPmatrixGetRowMinActivity(matrix, rowidx);
212  	   maxact = SCIPmatrixGetRowMaxActivity(matrix, rowidx);
213  	
214  	   if( SCIPisInfinity(scip, -minact) || SCIPisInfinity(scip, maxact) )
215  	      return;
216  	
217  	   lhs = SCIPmatrixGetRowLhs(matrix, rowidx);
218  	   lb = SCIPmatrixGetColLb(matrix, aggvaridx);
219  	
220  	   /* search for appropriate binary variables */
221  	   rowpnt = SCIPmatrixGetRowIdxPtr(matrix, rowidx);
222  	   rowend = rowpnt + SCIPmatrixGetRowNNonzs(matrix, rowidx);
223  	   valpnt = SCIPmatrixGetRowValPtr(matrix, rowidx);
224  	   for( ; (rowpnt < rowend); rowpnt++, valpnt++ )
225  	   {
226  	      SCIP_VAR* var;
227  	
228  	      if( *rowpnt == aggvaridx )
229  	         continue;
230  	
231  	      var = SCIPmatrixGetVar(matrix, *rowpnt);
232  	
233  	      /* avoid cases where the binary variable has lb=ub=1 or lb=ub=0 */
234  	      if( SCIPvarGetType(var) == SCIP_VARTYPE_BINARY &&
235  	          SCIPmatrixGetColLb(matrix, *rowpnt) < 0.5 &&
236  	          SCIPmatrixGetColUb(matrix, *rowpnt) > 0.5 )
237  	      {
238  	         SCIP_Real bincoef;
239  	         bincoef = *valpnt;
240  	
241  	         if( bincoef < 0 )
242  	         {
243  	            /* binvar = 0 implies that the constraint is redundant */
244  	            if( SCIPisGE(scip, minact-bincoef, lhs) )
245  	            {
246  	               /* binvar = 1 implies that aggvar = lb */
247  	               SCIP_Real bnd;
248  	               bnd = (lhs - maxact + coef*lb - bincoef) / coef;
249  	               if( SCIPisGE(scip, lb, bnd) )
250  	               {
251  	                  *binvaridx = *rowpnt;
252  	                  *aggtype = BIN0UBOUND;
253  	                  break;
254  	               }
255  	            }
256  	         }
257  	
258  	         if( bincoef > 0 )
259  	         {
260  	            /* binvar = 1 implies that the constraint is redundant */
261  	            if( SCIPisGE(scip, minact+bincoef, lhs) )
262  	            {
263  	               /* binvar = 0 implies that aggvar = lb */
264  	               SCIP_Real bnd;
265  	               bnd = (lhs - maxact + coef*lb + bincoef) / coef;
266  	               if( SCIPisGE(scip, lb, bnd) )
267  	               {
268  	                  *binvaridx = *rowpnt;
269  	                  *aggtype = BIN0LBOUND;
270  	               }
271  	            }
272  	         }
273  	      }
274  	   }
275  	}
276  	
277  	/** find fitting binary variable aggregation for downlock case */
278  	static
279  	void getBinVarIdxInDownlockRow(
280  	   SCIP*                 scip,               /**< SCIP main data structure */
281  	   SCIP_MATRIX*          matrix,             /**< constraint matrix */
282  	   int                   aggvaridx,          /**< index of variable which should be aggregated */
283  	   int*                  binvaridx,          /**< pointer to store index of binary variable */
284  	   AGGRTYPE*             aggtype             /**< pointer to store type of aggregation */
285  	   )
286  	{
287  	   int rowidx;
288  	   SCIP_Real coef;
289  	   int* rowpnt;
290  	   int* rowend;
291  	   SCIP_Real* valpnt;
292  	   SCIP_Real minact;
293  	   SCIP_Real maxact;
294  	   SCIP_Real lhs;
295  	   SCIP_Real ub;
296  	
297  	   assert(binvaridx != NULL);
298  	   assert(aggtype != NULL);
299  	
300  	   *binvaridx = -1;
301  	   *aggtype = NOAGG;
302  	
303  	   getDownlockRowIdx(matrix, aggvaridx, &rowidx, &coef);
304  	
305  	   if( rowidx < 0 )
306  	      return;
307  	
308  	   assert(coef > 0);
309  	   minact = SCIPmatrixGetRowMinActivity(matrix, rowidx);
310  	   maxact = SCIPmatrixGetRowMaxActivity(matrix, rowidx);
311  	
312  	   if( SCIPisInfinity(scip, -minact) || SCIPisInfinity(scip, maxact) )
313  	      return;
314  	
315  	   lhs = SCIPmatrixGetRowLhs(matrix, rowidx);
316  	   ub = SCIPmatrixGetColUb(matrix, aggvaridx);
317  	
318  	   /* search for appropriate binary variables */
319  	   rowpnt = SCIPmatrixGetRowIdxPtr(matrix, rowidx);
320  	   rowend = rowpnt + SCIPmatrixGetRowNNonzs(matrix, rowidx);
321  	   valpnt = SCIPmatrixGetRowValPtr(matrix, rowidx);
322  	   for( ; (rowpnt < rowend); rowpnt++, valpnt++ )
323  	   {
324  	      SCIP_VAR* var;
325  	
326  	      if( *rowpnt == aggvaridx )
327  	         continue;
328  	
329  	      var = SCIPmatrixGetVar(matrix, *rowpnt);
330  	
331  	      /* avoid cases where the binary variable has lb=ub=1 or lb=ub=0 */
332  	      if( SCIPvarGetType(var) == SCIP_VARTYPE_BINARY &&
333  	          SCIPmatrixGetColLb(matrix, *rowpnt) < 0.5 &&
334  	          SCIPmatrixGetColUb(matrix, *rowpnt) > 0.5 )
335  	      {
336  	         SCIP_Real bincoef;
337  	
338  	         bincoef = *valpnt;
339  	
340  	         if( bincoef < 0 )
341  	         {
342  	            /* binvar = 0 implies that the constraint is redundant */
343  	            if( SCIPisGE(scip, minact-bincoef, lhs) )
344  	            {
345  	               /* binvar = 1 implies that aggvar = ub */
346  	               SCIP_Real bnd;
347  	               bnd = (lhs - maxact + coef*ub - bincoef) / coef;
348  	               if( SCIPisGE(scip, bnd, ub) )
349  	               {
350  	                  *binvaridx = *rowpnt;
351  	                  *aggtype = BIN0LBOUND;
352  	                  break;
353  	               }
354  	            }
355  	         }
356  	
357  	         if( bincoef > 0 )
358  	         {
359  	            /* binvar = 1 implies that the constraint is redundant */
360  	            if( SCIPisGE(scip, minact+bincoef, lhs) )
361  	            {
362  	               /* binvar = 0 implies that aggvar = ub */
363  	               SCIP_Real bnd;
364  	               bnd = (lhs - maxact + coef*ub + bincoef) / coef;
365  	               if( SCIPisGE(scip, bnd, ub) )
366  	               {
367  	                  *binvaridx = *rowpnt;
368  	                  *aggtype = BIN0UBOUND;
369  	                  break;
370  	               }
371  	            }
372  	         }
373  	      }
374  	   }
375  	}
376  	
377  	/** find variable aggregations for uplock case */
378  	static
379  	SCIP_RETCODE findUplockAggregations(
380  	   SCIP*                 scip,               /**< SCIP main data structure */
381  	   SCIP_MATRIX*          matrix,             /**< constraint matrix */
382  	   int*                  nvaragg,            /**< number of redundant variables */
383  	   AGGRTYPE*             aggtypes,           /**< type of aggregations (in same order as variables in matrix) */
384  	   SCIP_VAR**            binvars             /**< pointers to the binary variables (in same order as variables in matrix) */
385  	   )
386  	{
387  	   int nvars;
388  	   int i;
389  	
390  	   assert(scip != NULL);
391  	   assert(matrix != NULL);
392  	   assert(nvaragg != NULL);
393  	   assert(aggtypes != NULL);
394  	   assert(binvars != NULL);
395  	
396  	   nvars = SCIPmatrixGetNColumns(matrix);
397  	
398  	   for( i = 0; i < nvars; i++ )
399  	   {
400  	      /* column has only one uplock which keeps it from being fixed by duality fixing */
401  	      if( SCIPmatrixGetColNUplocks(matrix, i) == 1 &&
402  	         SCIPisLE(scip, SCIPvarGetObj(SCIPmatrixGetVar(matrix, i)), 0.0) )
403  	      {
404  	         SCIP_Real lb;
405  	         SCIP_Real ub;
406  	
407  	         lb = SCIPmatrixGetColLb(matrix, i);
408  	         ub = SCIPmatrixGetColUb(matrix, i);
409  	         assert(lb == SCIPvarGetLbGlobal(SCIPmatrixGetVar(matrix, i))); /*lint !e777*/
410  	         assert(ub == SCIPvarGetUbGlobal(SCIPmatrixGetVar(matrix, i))); /*lint !e777*/
411  	
412  	         /* the variable needs to have finite bounds to allow an agregation */
413  	         if( !SCIPisInfinity(scip, -lb) && !SCIPisInfinity(scip, ub) )
414  	         {
415  	            int binvaridx;
416  	            AGGRTYPE aggtype;
417  	
418  	            getBinVarIdxInUplockRow(scip, matrix, i, &binvaridx, &aggtype);
419  	
420  	            if( binvaridx >= 0 )
421  	            {
422  	               aggtypes[i] = aggtype;
423  	               binvars[i] = SCIPmatrixGetVar(matrix, binvaridx);
424  	               (*nvaragg)++;
425  	            }
426  	         }
427  	      }
428  	   }
429  	
430  	   return SCIP_OKAY;
431  	}
432  	
433  	/** find variable aggregations for downlock case */
434  	static
435  	SCIP_RETCODE findDownlockAggregations(
436  	   SCIP*                 scip,               /**< SCIP main data structure */
437  	   SCIP_MATRIX*          matrix,             /**< constraint matrix */
438  	   int*                  nvaragg,            /**< number of redundant variables */
439  	   AGGRTYPE*             aggtypes,           /**< type of aggregations (in same order as variables in matrix) */
440  	   SCIP_VAR**            binvars             /**< pointers to the binary variables (in same order as variables in matrix) */
441  	   )
442  	{
443  	   int nvars;
444  	   int i;
445  	
446  	   assert(scip != NULL);
447  	   assert(matrix != NULL);
448  	   assert(nvaragg != NULL);
449  	   assert(aggtypes != NULL);
450  	   assert(binvars != NULL);
451  	
452  	   nvars = SCIPmatrixGetNColumns(matrix);
453  	
454  	   for( i = 0; i < nvars; i++ )
455  	   {
456  	      /* column has only one downlock which keeps it from being fixed by duality fixing;
457  	       * only handle variable if it was not yet aggregated due to a single uplock
458  	       */
459  	      if( SCIPmatrixGetColNDownlocks(matrix, i) == 1 &&
460  	         SCIPisGE(scip, SCIPvarGetObj(SCIPmatrixGetVar(matrix, i)), 0.0) &&
461  	         aggtypes[i] == NOAGG )
462  	      {
463  	         SCIP_Real lb;
464  	         SCIP_Real ub;
465  	
466  	         lb = SCIPmatrixGetColLb(matrix, i);
467  	         ub = SCIPmatrixGetColUb(matrix, i);
468  	         assert(lb == SCIPvarGetLbGlobal(SCIPmatrixGetVar(matrix, i))); /*lint !e777*/
469  	         assert(ub == SCIPvarGetUbGlobal(SCIPmatrixGetVar(matrix, i))); /*lint !e777*/
470  	
471  	         /* the variable needs to have finite bounds to allow an agregation */
472  	         if( !SCIPisInfinity(scip, -lb) && !SCIPisInfinity(scip, ub) )
473  	         {
474  	            int binvaridx;
475  	            AGGRTYPE aggtype;
476  	            getBinVarIdxInDownlockRow(scip, matrix, i, &binvaridx, &aggtype);
477  	
478  	            if( binvaridx >= 0 )
479  	            {
480  	               aggtypes[i] = aggtype;
481  	               binvars[i] = SCIPmatrixGetVar(matrix, binvaridx);
482  	               (*nvaragg)++;
483  	            }
484  	         }
485  	      }
486  	   }
487  	
488  	   return SCIP_OKAY;
489  	}
490  	
491  	/*
492  	 * Callback methods of presolver
493  	 */
494  	
495  	
496  	/** execution method of presolver */
497  	static
498  	SCIP_DECL_PRESOLEXEC(presolExecDualagg)
499  	{  /*lint --e{715}*/
500  	   SCIP_MATRIX* matrix;
501  	   SCIP_Bool initialized;
502  	   SCIP_Bool complete;
503  	   SCIP_Bool infeasible;
504  	
505  	   assert(result != NULL);
506  	   *result = SCIP_DIDNOTRUN;
507  	
508  	   if( (SCIPgetStage(scip) != SCIP_STAGE_PRESOLVING) || SCIPinProbing(scip) || SCIPisNLPEnabled(scip) )
509  	      return SCIP_OKAY;
510  	
511  	   if( SCIPisStopped(scip) || SCIPgetNActivePricers(scip) > 0 )
512  	      return SCIP_OKAY;
513  	
514  	   if( SCIPgetNBinVars(scip) == 0 )
515  	      return SCIP_OKAY;
516  	
517  	   if( !SCIPallowStrongDualReds(scip) )
518  	      return SCIP_OKAY;
519  	
520  	   *result = SCIP_DIDNOTFIND;
521  	
522  	   matrix = NULL;
523  	
524  	   SCIP_CALL( SCIPmatrixCreate(scip, &matrix, TRUE, &initialized, &complete, &infeasible,
525  	      naddconss, ndelconss, nchgcoefs, nchgbds, nfixedvars) );
526  	
527  	   /* if infeasibility was detected during matrix creation, return here */
528  	   if( infeasible )
529  	   {
530  	      if( initialized )
531  	         SCIPmatrixFree(scip, &matrix);
532  	
533  	      *result = SCIP_CUTOFF;
534  	      return SCIP_OKAY;
535  	   }
536  	
537  	   /* we only work on pure MIPs currently */
538  	   if( initialized && complete )
539  	   {
540  	      AGGRTYPE* aggtypes;
541  	      SCIP_VAR** binvars;
542  	      int nvaragg;
543  	      int ncols;
544  	
545  	      ncols = SCIPmatrixGetNColumns(matrix);
546  	      nvaragg = 0;
547  	
548  	      SCIP_CALL( SCIPallocBufferArray(scip, &aggtypes, ncols) );
549  	      BMSclearMemoryArray(aggtypes, ncols);
550  	
551  	      SCIP_CALL( SCIPallocBufferArray(scip, &binvars, ncols) );
552  	      SCIPdebug( BMSclearMemoryArray(binvars, ncols) );
553  	
554  	      /* search for aggregations */
555  	      SCIP_CALL( findUplockAggregations(scip, matrix, &nvaragg, aggtypes, binvars) );
556  	      SCIP_CALL( findDownlockAggregations(scip, matrix, &nvaragg, aggtypes, binvars) );
557  	
558  	      /* apply aggregations, if we found any */
559  	      if( nvaragg > 0 )
560  	      {
561  	         int v;
562  	
563  	         for( v = 0; v < ncols; v++ )
564  	         {
565  	            if( aggtypes[v] != NOAGG )
566  	            {
567  	               SCIP_Bool redundant;
568  	               SCIP_Bool aggregated;
569  	               SCIP_Real ub;
570  	               SCIP_Real lb;
571  	
572  	               ub = SCIPmatrixGetColUb(matrix, v);
573  	               lb = SCIPmatrixGetColLb(matrix, v);
574  	
575  	               /* aggregate variable */
576  	               assert(binvars[v] != NULL);
577  	               if( aggtypes[v] == BIN0UBOUND )
578  	               {
579  	                  SCIP_CALL( SCIPaggregateVars(scip, SCIPmatrixGetVar(matrix, v), binvars[v], 1.0, ub-lb,
580  	                        ub, &infeasible, &redundant, &aggregated) );
581  	               }
582  	               else
583  	               {
584  	                  assert(aggtypes[v] == BIN0LBOUND);
585  	                  SCIP_CALL( SCIPaggregateVars(scip, SCIPmatrixGetVar(matrix, v), binvars[v], 1.0, lb-ub,
586  	                        lb, &infeasible, &redundant, &aggregated) );
587  	               }
588  	
589  	               /* infeasible aggregation */
590  	               if( infeasible )
591  	               {
592  	                  SCIPdebugMsg(scip, " -> infeasible aggregation\n");
593  	                  *result = SCIP_CUTOFF;
594  	                  return SCIP_OKAY;
595  	               }
596  	
597  	               if( aggregated )
598  	                  (*naggrvars)++;
599  	            }
600  	         }
601  	
602  	         /* set result pointer */
603  	         if( (*naggrvars) > 0 )
604  	            *result = SCIP_SUCCESS;
605  	      }
606  	
607  	      SCIPfreeBufferArray(scip, &binvars);
608  	      SCIPfreeBufferArray(scip, &aggtypes);
609  	   }
610  	
611  	   SCIPmatrixFree(scip, &matrix);
612  	
613  	   return SCIP_OKAY;
614  	}
615  	
616  	/*
617  	 * presolver specific interface methods
618  	 */
619  	
620  	/** creates the dualagg presolver and includes it in SCIP */
621  	SCIP_RETCODE SCIPincludePresolDualagg(
622  	   SCIP*                 scip                /**< SCIP data structure */
623  	   )
624  	{
625  	   SCIP_PRESOL* presol;
626  	
627  	   /* include presolver */
628  	   SCIP_CALL( SCIPincludePresolBasic(scip, &presol, PRESOL_NAME, PRESOL_DESC, PRESOL_PRIORITY, PRESOL_MAXROUNDS,
629  	         PRESOL_TIMING, presolExecDualagg, NULL) );
630  	
631  	   return SCIP_OKAY;
632  	}
633