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_domcol.c
26   	 * @ingroup DEFPLUGINS_PRESOL
27   	 * @brief   dominated column presolver
28   	 * @author  Dieter Weninger
29   	 * @author  Gerald Gamrath
30   	 *
31   	 * This presolver looks for dominance relations between variable pairs.
32   	 * From a dominance relation and certain bound/clique-constellations
33   	 * variable fixings mostly at the lower bound of the dominated variable can be derived.
34   	 * Additionally it is possible to improve bounds by predictive bound strengthening.
35   	 *
36   	 * @todo Also run on general CIPs, if the number of locks of the investigated variables comes only from (upgraded)
37   	 * linear constraints.
38   	 *
39   	 * @todo Instead of choosing variables for comparison out of one row, we should try to use 'hashvalues' for columns that
40   	 *       indicate in which constraint type (<=, >=, or ranged row / ==) they are existing. Then sort the variables (and
41   	 *       corresponding data) after the ranged row/equation hashvalue and only try to derive dominance on variables with
42   	 *       the same hashvalue on ranged row/equation and fitting hashvalues for the other constraint types.
43   	 * @todo run on incomplete matrices; in order to do so, check at the time when dominance is detected that the locks are
44   	 *       consistent; probably, it is sufficient to check one lock direction for each of the two variables
45   	 *
46   	 */
47   	
48   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
49   	
50   	#include "blockmemshell/memory.h"
51   	#include "scip/presol_domcol.h"
52   	#include "scip/pub_matrix.h"
53   	#include "scip/pub_message.h"
54   	#include "scip/pub_misc_sort.h"
55   	#include "scip/pub_presol.h"
56   	#include "scip/pub_var.h"
57   	#include "scip/scip_general.h"
58   	#include "scip/scip_mem.h"
59   	#include "scip/scip_message.h"
60   	#include "scip/scip_nlp.h"
61   	#include "scip/scip_numerics.h"
62   	#include "scip/scip_param.h"
63   	#include "scip/scip_presol.h"
64   	#include "scip/scip_pricer.h"
65   	#include "scip/scip_prob.h"
66   	#include "scip/scip_probing.h"
67   	#include "scip/scip_var.h"
68   	#include <string.h>
69   	
70   	#define PRESOL_NAME            "domcol"
71   	#define PRESOL_DESC            "dominated column presolver"
72   	#define PRESOL_PRIORITY            -1000     /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */
73   	#define PRESOL_MAXROUNDS              -1     /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
74   	#define PRESOL_TIMING           SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */
75   	
76   	#define DEFAULT_NUMMINPAIRS         1024     /**< minimal number of pair comparisons */
77   	#define DEFAULT_NUMMAXPAIRS      1048576     /**< maximal number of pair comparisons */
78   	
79   	#define DEFAULT_PREDBNDSTR         FALSE     /**< should predictive bound strengthening be applied? */
80   	#define DEFAULT_CONTINUOUS_RED      TRUE     /**< should reductions for continuous variables be carried out? */
81   	
82   	
83   	
84   	/*
85   	 * Data structures
86   	  */
87   	
88   	/** control parameters */
89   	struct SCIP_PresolData
90   	{
91   	   int                   numminpairs;        /**< minimal number of pair comparisons */
92   	   int                   nummaxpairs;        /**< maximal number of pair comparisons */
93   	   int                   numcurrentpairs;    /**< current number of pair comparisons */
94   	   SCIP_Bool             predbndstr;         /**< flag indicating if predictive bound strengthening should be applied */
95   	   SCIP_Bool             continuousred;      /**< flag indicating if reductions for continuous variables should be performed */
96   	};
97   	
98   	/** type of fixing direction */
99   	enum Fixingdirection
100  	{
101  	   FIXATLB = -1,         /**< fix variable at lower bound */
102  	   NOFIX   =  0,         /**< do not fix variable */
103  	   FIXATUB =  1          /**< fix variable at upper bound */
104  	};
105  	typedef enum Fixingdirection FIXINGDIRECTION;
106  	
107  	
108  	/*
109  	 * Local methods
110  	 */
111  	#ifdef SCIP_DEBUG
112  	/** print a row from the constraint matrix */
113  	static
114  	void printRow(
115  	   SCIP*                 scip,               /**< SCIP main data structure */
116  	   SCIP_MATRIX*          matrix,             /**< matrix containing the constraints */
117  	   int                   row                 /**< row index for printing */
118  	   )
119  	{
120  	   int* rowpnt;
121  	   int* rowend;
122  	   int c;
123  	   SCIP_Real val;
124  	   SCIP_Real* valpnt;
125  	   char relation;
126  	   SCIP_VAR* var;
127  	
128  	   relation='-';
129  	   if( !SCIPmatrixIsRowRhsInfinity(matrix, row) &&
130  	      SCIPisEQ(scip, SCIPmatrixGetRowLhs(matrix, row), SCIPmatrixGetRowRhs(matrix, row)) )
131  	   {
132  	      relation='e';
133  	   }
134  	   else if( !SCIPmatrixIsRowRhsInfinity(matrix, row) &&
135  	      !SCIPisEQ(scip, SCIPmatrixGetRowLhs(matrix, row), SCIPmatrixGetRowRhs(matrix, row)) )
136  	   {
137  	      relation='r';
138  	   }
139  	   else
140  	   {
141  	      relation='g';
142  	   }
143  	
144  	   rowpnt = SCIPmatrixGetRowIdxPtr(matrix, row);
145  	   rowend = rowpnt + SCIPmatrixGetRowNNonzs(matrix, row);
146  	   valpnt = SCIPmatrixGetRowValPtr(matrix, row);
147  	
148  	   SCIPdebugMsgPrint(scip, "\n(L:%g) [%c] %g  <=",
149  	      (SCIPmatrixGetRowNMinActPosInf(matrix, row) + SCIPmatrixGetRowNMinActNegInf(matrix,row) > 0) ?
150  	      -SCIPinfinity(scip) :
151  	      SCIPmatrixGetRowMinActivity(matrix, row), relation, SCIPmatrixGetRowLhs(matrix, row));
152  	   for(; (rowpnt < rowend); rowpnt++, valpnt++)
153  	   {
154  	      c = *rowpnt;
155  	      val = *valpnt;
156  	      var = SCIPmatrixGetVar(matrix, c);
157  	      SCIPdebugMsgPrint(scip, "  %g{%s[idx:%d][bnd:%g,%g]}",
158  	         val, SCIPvarGetName(var), c, SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var));
159  	   }
160  	   SCIPdebugMsgPrint(scip, " <=  %g (U:%g)", (SCIPmatrixGetRowNMaxActPosInf(matrix, row) + SCIPmatrixGetRowNMaxActNegInf(matrix, row) > 0) ?
161  	      SCIPinfinity(scip) :
162  	      SCIPmatrixGetRowRhs(matrix, row), SCIPmatrixGetRowMaxActivity(matrix , row));
163  	}
164  	
165  	/** print all rows from the constraint matrix containing a variable */
166  	static
167  	SCIP_RETCODE printRowsOfCol(
168  	   SCIP*                 scip,               /**< SCIP main data structure */
169  	   SCIP_MATRIX*          matrix,             /**< matrix containing the constraints */
170  	   int                   col                 /**< column index for printing */
171  	   )
172  	{
173  	   int numrows;
174  	   int* rows;
175  	   int i;
176  	   int* colpnt;
177  	   int* colend;
178  	
179  	   numrows = SCIPmatrixGetColNNonzs(matrix, col);
180  	
181  	   SCIP_CALL( SCIPallocBufferArray(scip, &rows, numrows) );
182  	
183  	   colpnt = SCIPmatrixGetColIdxPtr(matrix, col);
184  	   colend = colpnt + SCIPmatrixGetColNNonzs(matrix, col);
185  	   for( i = 0; (colpnt < colend); colpnt++, i++ )
186  	   {
187  	      rows[i] = *colpnt;
188  	   }
189  	
190  	   SCIPdebugMsgPrint(scip, "\n-------");
191  	   SCIPdebugMsgPrint(scip, "\ncol %d number rows: %d",col,numrows);
192  	   for( i = 0; i < numrows; i++ )
193  	   {
194  	      printRow(scip, matrix, rows[i]);
195  	   }
196  	   SCIPdebugMsgPrint(scip, "\n-------");
197  	
198  	   SCIPfreeBufferArray(scip, &rows);
199  	
200  	   return SCIP_OKAY;
201  	}
202  	
203  	/** print information about a dominance relation */
204  	static
205  	SCIP_RETCODE printDomRelInfo(
206  	   SCIP*                 scip,               /**< SCIP main data structure */
207  	   SCIP_MATRIX*          matrix,             /**< matrix containing the constraints */
208  	   SCIP_VAR*             dominatingvar,      /**< dominating variable */
209  	   int                   dominatingidx,      /**< index of dominating variable */
210  	   SCIP_VAR*             dominatedvar,       /**< dominated variable */
211  	   int                   dominatedidx,       /**< index of dominated variable */
212  	   SCIP_Real             dominatingub,       /**< predicted upper bound of dominating variable */
213  	   SCIP_Real             dominatingwclb      /**< worst case lower bound of dominating variable */
214  	   )
215  	{
216  	   char type;
217  	
218  	   assert(SCIPvarGetType(dominatingvar)==SCIPvarGetType(dominatedvar));
219  	
220  	   switch(SCIPvarGetType(dominatingvar))
221  	   {
222  	   case SCIP_VARTYPE_CONTINUOUS:
223  	      type='C';
224  	      break;
225  	   case SCIP_VARTYPE_BINARY:
226  	      type='B';
227  	      break;
228  	   case SCIP_VARTYPE_INTEGER:
229  	   case SCIP_VARTYPE_IMPLINT:
230  	      type='I';
231  	      break;
232  	   default:
233  	      SCIPerrorMessage("unknown variable type\n");
234  	      SCIPABORT();
235  	      return SCIP_INVALIDDATA; /*lint !e527*/
236  	   }
237  	
238  	   SCIPdebugMsgPrint(scip, "\n\n### [%c], obj:%g->%g,\t%s[idx:%d](nrows:%d)->%s[idx:%d](nrows:%d)\twclb=%g, ub'=%g, ub=%g",
239  	      type, SCIPvarGetObj(dominatingvar), SCIPvarGetObj(dominatedvar),
240  	      SCIPvarGetName(dominatingvar), dominatingidx, SCIPmatrixGetColNNonzs(matrix, dominatingidx),
241  	      SCIPvarGetName(dominatedvar), dominatedidx, SCIPmatrixGetColNNonzs(matrix, dominatedidx),
242  	      dominatingwclb, dominatingub, SCIPvarGetUbGlobal(dominatingvar));
243  	
244  	   SCIP_CALL( printRowsOfCol(scip, matrix, dominatingidx) );
245  	
246  	   return SCIP_OKAY;
247  	}
248  	#endif
249  	
250  	
251  	/** get minimum/maximum residual activity for the specified variable and with another variable set to its upper bound */
252  	static
253  	void getActivityResidualsUpperBound(
254  	   SCIP*                 scip,
255  	   SCIP_MATRIX*          matrix,
256  	   int                   row,
257  	   int                   col,
258  	   SCIP_Real             coef,
259  	   int                   upperboundcol,
260  	   SCIP_Real             upperboundcoef,
261  	   SCIP_Real*            minresactivity,
262  	   SCIP_Real*            maxresactivity,
263  	   SCIP_Bool*            success
264  	   )
265  	{
266  	   SCIP_VAR* var;
267  	   SCIP_VAR* upperboundvar;
268  	   SCIP_Real lb;
269  	   SCIP_Real ub;
270  	   SCIP_Real lbupperboundvar;
271  	   SCIP_Real ubupperboundvar;
272  	   SCIP_Real tmpmaxact;
273  	   SCIP_Real tmpminact;
274  	   int maxactinf;
275  	   int minactinf;
276  	
277  	   assert(scip != NULL);
278  	   assert(matrix != NULL);
279  	   assert(row < SCIPmatrixGetNRows(matrix));
280  	   assert(minresactivity != NULL);
281  	   assert(maxresactivity != NULL);
282  	
283  	   var = SCIPmatrixGetVar(matrix, col);
284  	   upperboundvar = SCIPmatrixGetVar(matrix, upperboundcol);
285  	   assert(var != NULL);
286  	   assert(upperboundvar != NULL);
287  	
288  	   lb = SCIPvarGetLbGlobal(var);
289  	   ub = SCIPvarGetUbGlobal(var);
290  	
291  	   maxactinf = SCIPmatrixGetRowNMaxActPosInf(matrix, row) + SCIPmatrixGetRowNMaxActNegInf(matrix, row);
292  	   minactinf = SCIPmatrixGetRowNMinActPosInf(matrix, row) + SCIPmatrixGetRowNMinActNegInf(matrix, row);
293  	
294  	   assert(!SCIPisInfinity(scip, lb));
295  	   assert(!SCIPisInfinity(scip, -ub));
296  	
297  	   lbupperboundvar = SCIPvarGetLbGlobal(upperboundvar);
298  	   ubupperboundvar = SCIPvarGetUbGlobal(upperboundvar);
299  	
300  	   assert(!SCIPisInfinity(scip, lbupperboundvar));
301  	   assert(!SCIPisInfinity(scip, -ubupperboundvar));
302  	
303  	   tmpminact = SCIPmatrixGetRowMinActivity(matrix, row);
304  	   tmpmaxact = SCIPmatrixGetRowMaxActivity(matrix, row);
305  	
306  	   /* first, adjust min and max activity such that upperboundvar is always set to its upper bound */
307  	
308  	   /* abort if the upper bound is infty */
309  	   if( SCIPisInfinity(scip, ubupperboundvar) )
310  	   {
311  	      *success = FALSE;
312  	      return;
313  	   }
314  	   else
315  	   {
316  	      /* coef > 0 --> the lower bound is used for the minactivity --> update the minactivity */
317  	      if( upperboundcoef > 0.0 )
318  	      {
319  	         if( SCIPisInfinity(scip, -lbupperboundvar) )
320  	         {
321  	            assert(minactinf > 0);
322  	            minactinf--;
323  	            tmpminact += (upperboundcoef * ubupperboundvar);
324  	         }
325  	         else
326  	         {
327  	            tmpminact = tmpminact - (upperboundcoef * lbupperboundvar) + (upperboundcoef * ubupperboundvar);
328  	         }
329  	      }
330  	      /* coef < 0 --> the lower bound is used for the maxactivity --> update the maxactivity */
331  	      else
332  	      {
333  	         if( SCIPisInfinity(scip, -lbupperboundvar) )
334  	         {
335  	            assert(maxactinf > 0);
336  	            maxactinf--;
337  	            tmpmaxact += (upperboundcoef * ubupperboundvar);
338  	         }
339  	         else
340  	         {
341  	            tmpmaxact = tmpmaxact - (upperboundcoef * lbupperboundvar) + (upperboundcoef * ubupperboundvar);
342  	         }
343  	      }
344  	   }
345  	
346  	   *success = TRUE;
347  	
348  	   /* the coefficient is positive, so the upper bound contributed to the maxactivity and the lower bound to the minactivity */
349  	   if( coef >= 0.0 )
350  	   {
351  	      if( SCIPisInfinity(scip, ub) )
352  	      {
353  	         assert(maxactinf >= 1);
354  	         if( maxactinf == 1 )
355  	         {
356  	            *maxresactivity = tmpmaxact;
357  	         }
358  	         else
359  	            *maxresactivity = SCIPinfinity(scip);
360  	      }
361  	      else
362  	      {
363  	         if( maxactinf > 0 )
364  	            *maxresactivity = SCIPinfinity(scip);
365  	         else
366  	            *maxresactivity = tmpmaxact - coef * ub;
367  	      }
368  	
369  	      if( SCIPisInfinity(scip, -lb) )
370  	      {
371  	         assert(minactinf >= 1);
372  	         if( minactinf == 1 )
373  	         {
374  	            *minresactivity = tmpminact;
375  	         }
376  	         else
377  	            *minresactivity = -SCIPinfinity(scip);
378  	      }
379  	      else
380  	      {
381  	         if( minactinf > 0 )
382  	            *minresactivity = -SCIPinfinity(scip);
383  	         else
384  	            *minresactivity = tmpminact - coef * lb;
385  	      }
386  	   }
387  	   /* the coefficient is negative, so the lower bound contributed to the maxactivity and the upper bound to the minactivity */
388  	   else
389  	   {
390  	      if( SCIPisInfinity(scip, -lb) )
391  	      {
392  	         assert(maxactinf >= 1);
393  	         if( maxactinf == 1 )
394  	         {
395  	            *maxresactivity = tmpmaxact;
396  	         }
397  	         else
398  	            *maxresactivity = SCIPinfinity(scip);
399  	      }
400  	      else
401  	      {
402  	         if( maxactinf > 0 )
403  	            *maxresactivity = SCIPinfinity(scip);
404  	         else
405  	            *maxresactivity = tmpmaxact - coef * lb;
406  	      }
407  	
408  	      if( SCIPisInfinity(scip, ub) )
409  	      {
410  	         assert(minactinf >= 1);
411  	         if( minactinf == 1 )
412  	         {
413  	            *minresactivity = tmpminact;
414  	         }
415  	         else
416  	            *minresactivity = -SCIPinfinity(scip);
417  	      }
418  	      else
419  	      {
420  	         if( minactinf > 0 )
421  	            *minresactivity = -SCIPinfinity(scip);
422  	         else
423  	            *minresactivity = tmpminact - coef * ub;
424  	      }
425  	   }
426  	}
427  	
428  	/** get minimum/maximum residual activity for the specified variable and with another variable set to its lower bound */
429  	static
430  	void getActivityResidualsLowerBound(
431  	   SCIP*                 scip,               /**< SCIP main data structure */
432  	   SCIP_MATRIX*          matrix,             /**< matrix containing the constraints */
433  	   int                   row,                /**< row index */
434  	   int                   col,                /**< column index */
435  	   SCIP_Real             coef,               /**< coefficient of the column in this row */
436  	   int                   lowerboundcol,      /**< column index of variable to set to its lower bound */
437  	   SCIP_Real             lowerboundcoef,     /**< coefficient in this row of the column to be set to its lower bound */
438  	   SCIP_Real*            minresactivity,     /**< minimum residual activity of this row */
439  	   SCIP_Real*            maxresactivity,     /**< maximum residual activity of this row */
440  	   SCIP_Bool*            success             /**< pointer to store whether the computation was successful */
441  	   )
442  	{
443  	   SCIP_VAR* var;
444  	   SCIP_VAR* lowerboundvar;
445  	   SCIP_Real lb;
446  	   SCIP_Real ub;
447  	   SCIP_Real lblowerboundvar;
448  	   SCIP_Real ublowerboundvar;
449  	   SCIP_Real tmpmaxact;
450  	   SCIP_Real tmpminact;
451  	   int maxactinf;
452  	   int minactinf;
453  	
454  	   assert(scip != NULL);
455  	   assert(matrix != NULL);
456  	   assert(row < SCIPmatrixGetNRows(matrix));
457  	   assert(minresactivity != NULL);
458  	   assert(maxresactivity != NULL);
459  	
460  	   var = SCIPmatrixGetVar(matrix, col);;
461  	   lowerboundvar = SCIPmatrixGetVar(matrix, lowerboundcol);
462  	   assert(var != NULL);
463  	   assert(lowerboundvar != NULL);
464  	
465  	   lb = SCIPvarGetLbGlobal(var);
466  	   ub = SCIPvarGetUbGlobal(var);
467  	
468  	   maxactinf = SCIPmatrixGetRowNMaxActPosInf(matrix, row) + SCIPmatrixGetRowNMaxActNegInf(matrix, row);
469  	   minactinf = SCIPmatrixGetRowNMinActPosInf(matrix, row) + SCIPmatrixGetRowNMinActNegInf(matrix, row);
470  	
471  	   assert(!SCIPisInfinity(scip, lb));
472  	   assert(!SCIPisInfinity(scip, -ub));
473  	
474  	   lblowerboundvar = SCIPvarGetLbGlobal(lowerboundvar);
475  	   ublowerboundvar = SCIPvarGetUbGlobal(lowerboundvar);
476  	
477  	   assert(!SCIPisInfinity(scip, lblowerboundvar));
478  	   assert(!SCIPisInfinity(scip, -ublowerboundvar));
479  	
480  	   tmpminact = SCIPmatrixGetRowMinActivity(matrix, row);
481  	   tmpmaxact = SCIPmatrixGetRowMaxActivity(matrix, row);
482  	
483  	   /* first, adjust min and max activity such that lowerboundvar is always set to its lower bound */
484  	
485  	   /* abort if the lower bound is -infty */
486  	   if( SCIPisInfinity(scip, -lblowerboundvar) )
487  	   {
488  	      *success = FALSE;
489  	      return;
490  	   }
491  	   else
492  	   {
493  	      /* coef > 0 --> the upper bound is used for the maxactivity --> update the maxactivity */
494  	      if( lowerboundcoef > 0.0 )
495  	      {
496  	         if( SCIPisInfinity(scip, ublowerboundvar) )
497  	         {
498  	            assert(maxactinf > 0);
499  	            maxactinf--;
500  	            tmpmaxact += (lowerboundcoef * lblowerboundvar);
501  	         }
502  	         else
503  	         {
504  	            tmpmaxact = tmpmaxact - (lowerboundcoef * ublowerboundvar) + (lowerboundcoef * lblowerboundvar);
505  	         }
506  	      }
507  	      /* coef < 0 --> the upper bound is used for the minactivity --> update the minactivity */
508  	      else
509  	      {
510  	         if( SCIPisInfinity(scip, ublowerboundvar) )
511  	         {
512  	            assert(minactinf > 0);
513  	            minactinf--;
514  	            tmpminact += (lowerboundcoef * lblowerboundvar);
515  	         }
516  	         else
517  	         {
518  	            tmpminact = tmpminact - (lowerboundcoef * ublowerboundvar) + (lowerboundcoef * lblowerboundvar);
519  	         }
520  	      }
521  	   }
522  	
523  	   *success = TRUE;
524  	
525  	   /* the coefficient is positive, so the upper bound contributed to the maxactivity and the lower bound to the minactivity */
526  	   if( coef >= 0.0 )
527  	   {
528  	      if( SCIPisInfinity(scip, ub) )
529  	      {
530  	         assert(maxactinf >= 1);
531  	         if( maxactinf == 1 )
532  	         {
533  	            *maxresactivity = tmpmaxact;
534  	         }
535  	         else
536  	            *maxresactivity = SCIPinfinity(scip);
537  	      }
538  	      else
539  	      {
540  	         if( maxactinf > 0 )
541  	            *maxresactivity = SCIPinfinity(scip);
542  	         else
543  	            *maxresactivity = tmpmaxact - coef * ub;
544  	      }
545  	
546  	      if( SCIPisInfinity(scip, -lb) )
547  	      {
548  	         assert(minactinf >= 1);
549  	         if( minactinf == 1 )
550  	         {
551  	            *minresactivity = tmpminact;
552  	         }
553  	         else
554  	            *minresactivity = -SCIPinfinity(scip);
555  	      }
556  	      else
557  	      {
558  	         if( minactinf > 0 )
559  	            *minresactivity = -SCIPinfinity(scip);
560  	         else
561  	            *minresactivity = tmpminact - coef * lb;
562  	      }
563  	   }
564  	   /* the coefficient is negative, so the lower bound contributed to the maxactivity and the upper bound to the minactivity */
565  	   else
566  	   {
567  	      if( SCIPisInfinity(scip, -lb) )
568  	      {
569  	         assert(maxactinf >= 1);
570  	         if( maxactinf == 1 )
571  	         {
572  	            *maxresactivity = tmpmaxact;
573  	         }
574  	         else
575  	            *maxresactivity = SCIPinfinity(scip);
576  	      }
577  	      else
578  	      {
579  	         if( maxactinf > 0 )
580  	            *maxresactivity = SCIPinfinity(scip);
581  	         else
582  	            *maxresactivity = tmpmaxact - coef * lb;
583  	      }
584  	
585  	      if( SCIPisInfinity(scip, ub) )
586  	      {
587  	         assert(minactinf >= 1);
588  	         if( minactinf == 1 )
589  	         {
590  	            *minresactivity = tmpminact;
591  	         }
592  	         else
593  	            *minresactivity = -SCIPinfinity(scip);
594  	      }
595  	      else
596  	      {
597  	         if( minactinf > 0 )
598  	            *minresactivity = -SCIPinfinity(scip);
599  	         else
600  	            *minresactivity = tmpminact - coef * ub;
601  	      }
602  	   }
603  	}
604  	
605  	/** Calculate bounds of the dominated variable by rowbound analysis.
606  	 *  We use a special kind of predictive rowbound analysis by first setting the dominating variable to its upper bound.
607  	 */
608  	static
609  	SCIP_RETCODE calcVarBoundsDominated(
610  	   SCIP*                 scip,               /**< SCIP main data structure */
611  	   SCIP_MATRIX*          matrix,             /**< matrix containing the constraints */
612  	   int                   row,                /**< current row index */
613  	   int                   coldominating,      /**< column index of dominating variable */
614  	   SCIP_Real             valdominating,      /**< row coefficient of dominating variable */
615  	   int                   coldominated,       /**< column index of dominated variable */
616  	   SCIP_Real             valdominated,       /**< row coefficient of dominated variable */
617  	   SCIP_Bool*            ubcalculated,       /**< was a upper bound calculated? */
618  	   SCIP_Real*            calculatedub,       /**< predicted upper bound */
619  	   SCIP_Bool*            wclbcalculated,     /**< was a lower worst case bound calculated? */
620  	   SCIP_Real*            calculatedwclb,     /**< predicted worst case lower bound */
621  	   SCIP_Bool*            lbcalculated,       /**< was a lower bound calculated? */
622  	   SCIP_Real*            calculatedlb,       /**< predicted lower bound */
623  	   SCIP_Bool*            wcubcalculated,     /**< was a worst case upper bound calculated? */
624  	   SCIP_Real*            calculatedwcub      /**< calculated worst case upper bound */
625  	   )
626  	{
627  	   SCIP_Real minresactivity;
628  	   SCIP_Real maxresactivity;
629  	   SCIP_Real lhs;
630  	   SCIP_Real rhs;
631  	   SCIP_Bool success;
632  	
633  	   assert(scip != NULL);
634  	   assert(matrix != NULL);
635  	   assert(0 <= row && row < SCIPmatrixGetNRows(matrix));
636  	   assert(0 <= coldominating && coldominating < SCIPmatrixGetNColumns(matrix));
637  	   assert(0 <= coldominated && coldominated < SCIPmatrixGetNColumns(matrix));
638  	
639  	   assert(ubcalculated != NULL);
640  	   assert(calculatedub != NULL);
641  	   assert(wclbcalculated != NULL);
642  	   assert(calculatedwclb != NULL);
643  	   assert(lbcalculated != NULL);
644  	   assert(calculatedlb != NULL);
645  	   assert(wcubcalculated != NULL);
646  	   assert(calculatedwcub != NULL);
647  	
648  	   assert(!SCIPisZero(scip, valdominated));
649  	   assert(SCIPmatrixGetVar(matrix, coldominated) != NULL);
650  	
651  	   *ubcalculated = FALSE;
652  	   *wclbcalculated = FALSE;
653  	   *lbcalculated = FALSE;
654  	   *wcubcalculated = FALSE;
655  	
656  	   /* no rowbound analysis for multiaggregated variables, which should not exist, because the matrix only consists of
657  	    * active variables
658  	    */
659  	   assert(SCIPvarGetStatus(SCIPmatrixGetVar(matrix, coldominating)) != SCIP_VARSTATUS_MULTAGGR);
660  	   assert(SCIPvarGetStatus(SCIPmatrixGetVar(matrix, coldominated)) != SCIP_VARSTATUS_MULTAGGR);
661  	
662  	   lhs = SCIPmatrixGetRowLhs(matrix, row);
663  	   rhs = SCIPmatrixGetRowRhs(matrix, row);
664  	   assert(!SCIPisInfinity(scip, lhs));
665  	   assert(!SCIPisInfinity(scip, -rhs));
666  	
667  	   /* get minimum/maximum activity of this row without the dominated variable */
668  	   getActivityResidualsUpperBound(scip, matrix, row, coldominated, valdominated, coldominating, valdominating,
669  	      &minresactivity, &maxresactivity, &success);
670  	
671  	   if( !success )
672  	      return SCIP_OKAY;
673  	
674  	   assert(!SCIPisInfinity(scip, minresactivity));
675  	   assert(!SCIPisInfinity(scip, -maxresactivity));
676  	
677  	   *calculatedub = SCIPinfinity(scip);
678  	   *calculatedwclb = -SCIPinfinity(scip);
679  	   *calculatedlb = -SCIPinfinity(scip);
680  	   *calculatedwcub = SCIPinfinity(scip);
681  	
682  	   /* predictive rowbound analysis */
683  	
684  	   if( valdominated > 0.0 )
685  	   {
686  	      /* lower bound calculation */
687  	      if( !SCIPisInfinity(scip, maxresactivity) )
688  	      {
689  	         *calculatedlb = (lhs - maxresactivity)/valdominated;
690  	         *lbcalculated = TRUE;
691  	      }
692  	
693  	      /* worst case calculation of lower bound */
694  	      if( !SCIPisInfinity(scip, -minresactivity) )
695  	      {
696  	         *calculatedwclb = (lhs - minresactivity)/valdominated;
697  	         *wclbcalculated = TRUE;
698  	      }
699  	      else
700  	      {
701  	         /* worst case lower bound is infinity */
702  	         *calculatedwclb = SCIPinfinity(scip);
703  	         *wclbcalculated = TRUE;
704  	      }
705  	
706  	      /* we can only calculate upper bounds, of the right hand side is finite */
707  	      if( !SCIPmatrixIsRowRhsInfinity(matrix, row) )
708  	      {
709  	         /* upper bound calculation */
710  	         if( !SCIPisInfinity(scip, -minresactivity) )
711  	         {
712  	            *calculatedub = (rhs - minresactivity)/valdominated;
713  	            *ubcalculated = TRUE;
714  	         }
715  	
716  	         /* worst case calculation of upper bound */
717  	         if( !SCIPisInfinity(scip, maxresactivity) )
718  	         {
719  	            *calculatedwcub = (rhs - maxresactivity)/valdominated;
720  	            *wcubcalculated = TRUE;
721  	         }
722  	         else
723  	         {
724  	            /* worst case upper bound is -infinity */
725  	            *calculatedwcub = -SCIPinfinity(scip);
726  	            *wcubcalculated = TRUE;
727  	         }
728  	      }
729  	   }
730  	   else
731  	   {
732  	      /* upper bound calculation */
733  	      if( !SCIPisInfinity(scip, maxresactivity) )
734  	      {
735  	         *calculatedub = (lhs - maxresactivity)/valdominated;
736  	         *ubcalculated = TRUE;
737  	      }
738  	
739  	      /* worst case calculation of upper bound */
740  	      if( !SCIPisInfinity(scip, -minresactivity) )
741  	      {
742  	         *calculatedwcub = (lhs - minresactivity)/valdominated;
743  	         *wcubcalculated = TRUE;
744  	      }
745  	      else
746  	      {
747  	         /* worst case upper bound is -infinity */
748  	         *calculatedwcub = -SCIPinfinity(scip);
749  	         *wcubcalculated = TRUE;
750  	      }
751  	
752  	      /* we can only calculate lower bounds, of the right hand side is finite */
753  	      if( !SCIPmatrixIsRowRhsInfinity(matrix, row) )
754  	      {
755  	         /* lower bound calculation */
756  	         if( !SCIPisInfinity(scip, -minresactivity) )
757  	         {
758  	            *calculatedlb = (rhs - minresactivity)/valdominated;
759  	            *lbcalculated = TRUE;
760  	         }
761  	
762  	         /* worst case calculation of lower bound */
763  	         if( !SCIPisInfinity(scip, maxresactivity) )
764  	         {
765  	            *calculatedwclb = (rhs - maxresactivity)/valdominated;
766  	            *wclbcalculated = TRUE;
767  	         }
768  	         else
769  	         {
770  	            /* worst case lower bound is infinity */
771  	            *calculatedwclb = SCIPinfinity(scip);
772  	            *wclbcalculated = TRUE;
773  	         }
774  	      }
775  	   }
776  	
777  	   return SCIP_OKAY;
778  	}
779  	
780  	/** Calculate bounds of the dominating variable by rowbound analysis.
781  	 *  We use a special kind of predictive rowbound analysis by first setting the dominated variable to its lower bound.
782  	 */
783  	static
784  	SCIP_RETCODE calcVarBoundsDominating(
785  	   SCIP*                 scip,               /**< SCIP main data structure */
786  	   SCIP_MATRIX*          matrix,             /**< matrix containing the constraints */
787  	   int                   row,                /**< current row index */
788  	   int                   coldominating,      /**< column index of dominating variable */
789  	   SCIP_Real             valdominating,      /**< row coefficient of dominating variable */
790  	   int                   coldominated,       /**< column index of dominated variable */
791  	   SCIP_Real             valdominated,       /**< row coefficient of dominated variable */
792  	   SCIP_Bool*            ubcalculated,       /**< was a upper bound calculated? */
793  	   SCIP_Real*            calculatedub,       /**< predicted upper bound */
794  	   SCIP_Bool*            wclbcalculated,     /**< was a lower worst case bound calculated? */
795  	   SCIP_Real*            calculatedwclb,     /**< predicted worst case lower bound */
796  	   SCIP_Bool*            lbcalculated,       /**< was a lower bound calculated? */
797  	   SCIP_Real*            calculatedlb,       /**< predicted lower bound */
798  	   SCIP_Bool*            wcubcalculated,     /**< was a worst case upper bound calculated? */
799  	   SCIP_Real*            calculatedwcub      /**< calculated worst case upper bound */
800  	   )
801  	{
802  	   SCIP_Real minresactivity;
803  	   SCIP_Real maxresactivity;
804  	   SCIP_Real lhs;
805  	   SCIP_Real rhs;
806  	   SCIP_Bool success;
807  	
808  	   assert(scip != NULL);
809  	   assert(matrix != NULL);
810  	   assert(0 <= row && row < SCIPmatrixGetNRows(matrix) );
811  	   assert(0 <= coldominating && coldominating < SCIPmatrixGetNColumns(matrix));
812  	   assert(0 <= coldominated && coldominated < SCIPmatrixGetNColumns(matrix));
813  	
814  	   assert(ubcalculated != NULL);
815  	   assert(calculatedub != NULL);
816  	   assert(wclbcalculated != NULL);
817  	   assert(calculatedwclb != NULL);
818  	   assert(lbcalculated != NULL);
819  	   assert(calculatedlb != NULL);
820  	   assert(wcubcalculated != NULL);
821  	   assert(calculatedwcub != NULL);
822  	
823  	   assert(!SCIPisZero(scip, valdominating));
824  	   assert(SCIPmatrixGetVar(matrix, coldominating) != NULL);
825  	
826  	   *ubcalculated = FALSE;
827  	   *wclbcalculated = FALSE;
828  	   *lbcalculated = FALSE;
829  	   *wcubcalculated = FALSE;
830  	
831  	   /* no rowbound analysis for multiaggregated variables, which should not exist, because the matrix only consists of
832  	    * active variables
833  	    */
834  	   assert(SCIPvarGetStatus(SCIPmatrixGetVar(matrix, coldominating)) != SCIP_VARSTATUS_MULTAGGR);
835  	   assert(SCIPvarGetStatus(SCIPmatrixGetVar(matrix, coldominated)) != SCIP_VARSTATUS_MULTAGGR);
836  	
837  	   lhs = SCIPmatrixGetRowLhs(matrix, row);
838  	   rhs = SCIPmatrixGetRowRhs(matrix, row);
839  	   assert(!SCIPisInfinity(scip, lhs));
840  	   assert(!SCIPisInfinity(scip, -rhs));
841  	
842  	   /* get minimum/maximum activity of this row without the dominating variable */
843  	   getActivityResidualsLowerBound(scip, matrix, row, coldominating, valdominating, coldominated, valdominated,
844  	      &minresactivity, &maxresactivity, &success);
845  	
846  	   if( !success )
847  	      return SCIP_OKAY;
848  	
849  	   assert(!SCIPisInfinity(scip, minresactivity));
850  	   assert(!SCIPisInfinity(scip, -maxresactivity));
851  	
852  	   *calculatedub = SCIPinfinity(scip);
853  	   *calculatedwclb = -SCIPinfinity(scip);
854  	   *calculatedlb = -SCIPinfinity(scip);
855  	   *calculatedwcub = SCIPinfinity(scip);
856  	
857  	   /* predictive rowbound analysis */
858  	
859  	   if( valdominating > 0.0 )
860  	   {
861  	      /* lower bound calculation */
862  	      if( !SCIPisInfinity(scip, maxresactivity) )
863  	      {
864  	         *calculatedlb = (lhs - maxresactivity)/valdominating;
865  	         *lbcalculated = TRUE;
866  	      }
867  	
868  	      /* worst case calculation of lower bound */
869  	      if( !SCIPisInfinity(scip, -minresactivity) )
870  	      {
871  	         *calculatedwclb = (lhs - minresactivity)/valdominating;
872  	         *wclbcalculated = TRUE;
873  	      }
874  	      else
875  	      {
876  	         /* worst case lower bound is infinity */
877  	         *calculatedwclb = SCIPinfinity(scip);
878  	         *wclbcalculated = TRUE;
879  	      }
880  	
881  	      /* we can only calculate upper bounds, of the right hand side is finite */
882  	      if( !SCIPmatrixIsRowRhsInfinity(matrix, row) )
883  	      {
884  	         /* upper bound calculation */
885  	         if( !SCIPisInfinity(scip, -minresactivity) )
886  	         {
887  	            *calculatedub = (rhs - minresactivity)/valdominating;
888  	            *ubcalculated = TRUE;
889  	         }
890  	
891  	         /* worst case calculation of upper bound */
892  	         if( !SCIPisInfinity(scip, maxresactivity) )
893  	         {
894  	            *calculatedwcub = (rhs - maxresactivity)/valdominating;
895  	            *wcubcalculated = TRUE;
896  	         }
897  	         else
898  	         {
899  	            /* worst case upper bound is -infinity */
900  	            *calculatedwcub = -SCIPinfinity(scip);
901  	            *wcubcalculated = TRUE;
902  	         }
903  	      }
904  	   }
905  	   else
906  	   {
907  	      /* upper bound calculation */
908  	      if( !SCIPisInfinity(scip, maxresactivity) )
909  	      {
910  	         *calculatedub = (lhs - maxresactivity)/valdominating;
911  	         *ubcalculated = TRUE;
912  	      }
913  	
914  	      /* worst case calculation of upper bound */
915  	      if( !SCIPisInfinity(scip, -minresactivity) )
916  	      {
917  	         *calculatedwcub = (lhs - minresactivity)/valdominating;
918  	         *wcubcalculated = TRUE;
919  	      }
920  	      else
921  	      {
922  	         /* worst case upper bound is -infinity */
923  	         *calculatedwcub = -SCIPinfinity(scip);
924  	         *wcubcalculated = TRUE;
925  	      }
926  	
927  	      /* we can only calculate lower bounds, of the right hand side is finite */
928  	      if( !SCIPmatrixIsRowRhsInfinity(matrix, row) )
929  	      {
930  	         /* lower bound calculation */
931  	         if( !SCIPisInfinity(scip, -minresactivity) )
932  	         {
933  	            *calculatedlb = (rhs - minresactivity)/valdominating;
934  	            *lbcalculated = TRUE;
935  	         }
936  	
937  	         /* worst case calculation of lower bound */
938  	         if( !SCIPisInfinity(scip, maxresactivity) )
939  	         {
940  	            *calculatedwclb = (rhs - maxresactivity)/valdominating;
941  	            *wclbcalculated = TRUE;
942  	         }
943  	         else
944  	         {
945  	            /* worst case lower bound is infinity */
946  	            *calculatedwclb = SCIPinfinity(scip);
947  	            *wclbcalculated = TRUE;
948  	         }
949  	      }
950  	   }
951  	
952  	   return SCIP_OKAY;
953  	}
954  	
955  	/** try to find new variable bounds and update them when they are better then the old bounds */
956  	static
957  	SCIP_RETCODE updateBounds(
958  	   SCIP*                 scip,               /**< SCIP main data structure */
959  	   SCIP_MATRIX*          matrix,             /**< matrix containing the constraints */
960  	   int                   row,                /**< row index */
961  	   int                   col1,               /**< dominating variable index */
962  	   SCIP_Real             val1,               /**< dominating variable coefficient */
963  	   int                   col2,               /**< dominated variable index */
964  	   SCIP_Real             val2,               /**< dominated variable coefficient */
965  	   SCIP_Bool             predictdominating,  /**< flag indicating if bounds of dominating or dominated variable are predicted */
966  	   SCIP_Real*            upperbound,         /**< predicted upper bound */
967  	   SCIP_Real*            wclowerbound,       /**< predicted worst case lower bound */
968  	   SCIP_Real*            lowerbound,         /**< predicted lower bound */
969  	   SCIP_Real*            wcupperbound        /**< predicted worst case upper bound */
970  	   )
971  	{
972  	   SCIP_Bool ubcalculated;
973  	   SCIP_Bool wclbcalculated;
974  	   SCIP_Bool lbcalculated;
975  	   SCIP_Bool wcubcalculated;
976  	   SCIP_Real newub;
977  	   SCIP_Real newwclb;
978  	   SCIP_Real newlb;
979  	   SCIP_Real newwcub;
980  	
981  	   assert(scip != NULL);
982  	   assert(matrix != NULL);
983  	   assert(upperbound != NULL);
984  	   assert(wclowerbound != NULL);
985  	   assert(lowerbound != NULL);
986  	   assert(wcupperbound != NULL);
987  	
988  	   newub = SCIPinfinity(scip);
989  	   newlb = -SCIPinfinity(scip);
990  	   newwcub = newub;
991  	   newwclb = newlb;
992  	
993  	   if( predictdominating )
994  	   {
995  	      /* do predictive rowbound analysis for the dominating variable */
996  	      SCIP_CALL( calcVarBoundsDominating(scip, matrix, row, col1, val1, col2, val2,
997  	            &ubcalculated, &newub, &wclbcalculated, &newwclb,
998  	            &lbcalculated, &newlb, &wcubcalculated, &newwcub) );
999  	   }
1000 	   else
1001 	   {
1002 	      /* do predictive rowbound analysis for the dominated variable */
1003 	      SCIP_CALL( calcVarBoundsDominated(scip, matrix, row, col1, val1, col2, val2,
1004 	            &ubcalculated, &newub, &wclbcalculated, &newwclb,
1005 	            &lbcalculated, &newlb, &wcubcalculated, &newwcub) );
1006 	   }
1007 	
1008 	   /* update bounds in case if they are better */
1009 	   if( ubcalculated )
1010 	   {
1011 	      if( newub < *upperbound )
1012 	         *upperbound = newub;
1013 	   }
1014 	   if( wclbcalculated )
1015 	   {
1016 	      if( newwclb > *wclowerbound )
1017 	         *wclowerbound = newwclb;
1018 	   }
1019 	   if( lbcalculated )
1020 	   {
1021 	      if( newlb > *lowerbound )
1022 	         *lowerbound = newlb;
1023 	   }
1024 	   if( wcubcalculated )
1025 	   {
1026 	      if( newwcub < *wcupperbound )
1027 	         *wcupperbound = newwcub;
1028 	   }
1029 	
1030 	   return SCIP_OKAY;
1031 	}
1032 	
1033 	/** detect parallel columns by using the algorithm of Bixby and Wagner
1034 	 *  see paper: "A note on Detecting Simple Redundancies in Linear Systems", June 1986
1035 	 */
1036 	static
1037 	SCIP_RETCODE detectParallelCols(
1038 	   SCIP*                 scip,               /**< SCIP main data structure */
1039 	   SCIP_MATRIX*          matrix,             /**< matrix containing the constraints */
1040 	   int*                  pclass,             /**< parallel column classes */
1041 	   SCIP_Bool*            varineq             /**< indicating if variable is within an equation */
1042 	   )
1043 	{
1044 	   SCIP_Real* valpnt;
1045 	   SCIP_Real* values;
1046 	   SCIP_Real* scale;
1047 	   int* classsizes;
1048 	   int* pcset;
1049 	   int* rowpnt;
1050 	   int* rowend;
1051 	   int* colindices;
1052 	   int* pcs;
1053 	   SCIP_Real startval;
1054 	   SCIP_Real aij;
1055 	   int startpc;
1056 	   int startk;
1057 	   int startt;
1058 	   int pcsetfill;
1059 	   int colidx;
1060 	   int k;
1061 	   int t;
1062 	   int m;
1063 	   int i;
1064 	   int r;
1065 	   int newpclass;
1066 	   int pc;
1067 	   int nrows;
1068 	   int ncols;
1069 	
1070 	   assert(scip != NULL);
1071 	   assert(matrix != NULL);
1072 	   assert(pclass != NULL);
1073 	   assert(varineq != NULL);
1074 	
1075 	   nrows = SCIPmatrixGetNRows(matrix);
1076 	   ncols = SCIPmatrixGetNColumns(matrix);
1077 	
1078 	   SCIP_CALL( SCIPallocBufferArray(scip, &classsizes, ncols) );
1079 	   SCIP_CALL( SCIPallocBufferArray(scip, &scale, ncols) );
1080 	   SCIP_CALL( SCIPallocBufferArray(scip, &pcset, ncols) );
1081 	   SCIP_CALL( SCIPallocBufferArray(scip, &values, ncols) );
1082 	   SCIP_CALL( SCIPallocBufferArray(scip, &colindices, ncols) );
1083 	   SCIP_CALL( SCIPallocBufferArray(scip, &pcs, ncols) );
1084 	
1085 	   BMSclearMemoryArray(scale, ncols);
1086 	   BMSclearMemoryArray(pclass, ncols);
1087 	   BMSclearMemoryArray(classsizes, ncols);
1088 	
1089 	   classsizes[0] = ncols;
1090 	   pcsetfill = 0;
1091 	   for( t = 1; t < ncols; ++t )
1092 	      pcset[pcsetfill++] = t;
1093 	
1094 	   /* loop over all rows */
1095 	   for( r = 0; r < nrows; ++r )
1096 	   {
1097 	      /* we consider only non-empty equations or ranged rows */
1098 	      if( !SCIPmatrixIsRowRhsInfinity(matrix, r) && SCIPmatrixGetRowNNonzs(matrix, r) > 0 )
1099 	      {
1100 	         rowpnt = SCIPmatrixGetRowIdxPtr(matrix, r);
1101 	         rowend = rowpnt + SCIPmatrixGetRowNNonzs(matrix, r);
1102 	         valpnt = SCIPmatrixGetRowValPtr(matrix, r);
1103 	
1104 	         i = 0;
1105 	         for( ; (rowpnt < rowend); rowpnt++, valpnt++ )
1106 	         {
1107 	            aij = *valpnt;
1108 	            colidx = *rowpnt;
1109 	
1110 	            /* remember variable was part of an equation or ranged row */
1111 	            varineq[colidx] = TRUE;
1112 	
1113 	            if( scale[colidx] == 0.0 )
1114 	               scale[colidx] = aij;
1115 	            assert(scale[colidx] != 0.0);
1116 	
1117 	            colindices[i] = colidx;
1118 	            values[i] = aij / scale[colidx];
1119 	            pc = pclass[colidx];
1120 	            assert(pc < ncols);
1121 	
1122 	            /* update class sizes and pclass set */
1123 	            assert(classsizes[pc] > 0);
1124 	            classsizes[pc]--;
1125 	            if( classsizes[pc] == 0 )
1126 	            {
1127 	               assert(pcsetfill < ncols);
1128 	               pcset[pcsetfill++] = pc;
1129 	            }
1130 	            pcs[i] = pc;
1131 	
1132 	            i++;
1133 	         }
1134 	
1135 	         assert(i > 0);
1136 	
1137 	         /* sort on the pclass values */
1138 	         if( i > 1 )
1139 	         {
1140 	            SCIPsortIntIntReal(pcs, colindices, values, i);
1141 	         }
1142 	
1143 	         k = 0;
1144 	         while( TRUE ) /*lint !e716*/
1145 	         {
1146 	            assert(k < i);
1147 	            startpc = pcs[k];
1148 	            startk = k;
1149 	
1150 	            /* find pclass-sets */
1151 	            while( k < i && pcs[k] == startpc )
1152 	               k++;
1153 	
1154 	            /* sort on the A values which have equal pclass values */
1155 	            if( k - startk > 1 )
1156 	               SCIPsortRealInt(&(values[startk]), &(colindices[startk]), k - startk);
1157 	
1158 	            t = 0;
1159 	            while( TRUE ) /*lint !e716*/
1160 	            {
1161 	               assert(startk + t < i);
1162 	               startval = values[startk + t];
1163 	               startt = t;
1164 	
1165 	               /* find A-sets */
1166 	               while( t < k - startk && SCIPisEQ(scip, startval, values[startk + t]) )
1167 	                  t++;
1168 	
1169 	               /* get new pclass */
1170 	               newpclass = pcset[0];
1171 	               assert(pcsetfill > 0);
1172 	               pcset[0] = pcset[--pcsetfill];
1173 	
1174 	               /* renumbering */
1175 	               for( m = startk + startt; m < startk + t; m++ )
1176 	               {
1177 	                  assert(m < i);
1178 	                  assert(colindices[m] < ncols);
1179 	                  assert(newpclass < ncols);
1180 	
1181 	                  pclass[colindices[m]] = newpclass;
1182 	                  classsizes[newpclass]++;
1183 	               }
1184 	
1185 	               if( t == k - startk )
1186 	                  break;
1187 	            }
1188 	
1189 	            if( k == SCIPmatrixGetRowNNonzs(matrix, r) )
1190 	               break;
1191 	         }
1192 	      }
1193 	   }
1194 	
1195 	   SCIPfreeBufferArray(scip, &pcs);
1196 	   SCIPfreeBufferArray(scip, &colindices);
1197 	   SCIPfreeBufferArray(scip, &values);
1198 	   SCIPfreeBufferArray(scip, &pcset);
1199 	   SCIPfreeBufferArray(scip, &scale);
1200 	   SCIPfreeBufferArray(scip, &classsizes);
1201 	
1202 	   return SCIP_OKAY;
1203 	}
1204 	
1205 	
1206 	/** try to improve variable bounds by predictive bound strengthening */
1207 	static
1208 	SCIP_RETCODE predBndStr(
1209 	   SCIP*                 scip,               /**< SCIP main data structure */
1210 	   SCIP_VAR*             dominatingvar,      /**< dominating variable */
1211 	   int                   dominatingidx,      /**< column index of the dominating variable */
1212 	   SCIP_Real             dominatingub,       /**< predicted upper bound of the dominating variable */
1213 	   SCIP_Real             dominatinglb,       /**< predicted lower bound of the dominating variable */
1214 	   SCIP_Real             dominatingwcub,     /**< predicted worst case upper bound of the dominating variable */
1215 	   SCIP_VAR*             dominatedvar,       /**< dominated variable */
1216 	   int                   dominatedidx,       /**< column index of the dominated variable */
1217 	   SCIP_Real             dominatedub,        /**< predicted upper bound of the dominated variable */
1218 	   SCIP_Real             dominatedwclb,      /**< predicted worst case lower bound of the dominated variable */
1219 	   SCIP_Real             dominatedlb,        /**< predicted lower bound of the dominated variable */
1220 	   FIXINGDIRECTION*      varstofix,          /**< array holding fixing information */
1221 	   int*                  nchgbds             /**< count number of bound changes */
1222 	   )
1223 	{
1224 	   /* we compare only variables from the same type */
1225 	   if( !(SCIPvarGetType(dominatingvar) == SCIPvarGetType(dominatedvar) ||
1226 	         SCIPvarIsBinary(dominatingvar) == SCIPvarIsBinary(dominatedvar) ||
1227 	         (SCIPvarGetType(dominatingvar) == SCIP_VARTYPE_INTEGER && SCIPvarGetType(dominatedvar) == SCIP_VARTYPE_IMPLINT) ||
1228 	         (SCIPvarGetType(dominatedvar) == SCIP_VARTYPE_INTEGER && SCIPvarGetType(dominatingvar) == SCIP_VARTYPE_IMPLINT)) )
1229 	   {
1230 	      return SCIP_OKAY;
1231 	   }
1232 	
1233 	   if( varstofix[dominatingidx] == NOFIX )
1234 	   {
1235 	      /* assume x dominates y (x->y). we get this bound from a positive coefficient
1236 	       * of the dominating variable. because x->y the dominated variable y has
1237 	       * a positive coefficient too. thus y contributes to the minactivity with its
1238 	       * lower bound. but this case is considered within predictive bound analysis.
1239 	       * thus the dominating upper bound is a common upper bound.
1240 	       */
1241 	      if( !SCIPisInfinity(scip, dominatingub) )
1242 	      {
1243 	         SCIP_Real newub;
1244 	         SCIP_Real oldub;
1245 	         SCIP_Real lb;
1246 	
1247 	         newub = dominatingub;
1248 	         oldub = SCIPvarGetUbGlobal(dominatingvar);
1249 	         lb = SCIPvarGetLbGlobal(dominatingvar);
1250 	
1251 	         /* if( SCIPvarGetType(dominatingvar) != SCIP_VARTYPE_CONTINUOUS )
1252 	            newub = SCIPceil(scip, newub); */
1253 	
1254 	         if( SCIPisLE(scip, lb, newub) && SCIPisLT(scip, newub, oldub) )
1255 	         {
1256 	            SCIPdebugMsg(scip, "[ub]\tupper bound for dominating variable <%s> changed: [%.17f,%.17f] -> [%.17f,%.17f]\n",
1257 	               SCIPvarGetName(dominatingvar), lb, oldub, lb, newub);
1258 	            SCIP_CALL( SCIPchgVarUb(scip, dominatingvar, newub) );
1259 	            (*nchgbds)++;
1260 	         }
1261 	      }
1262 	
1263 	      /* assume x dominates y (x->y). we get this lower bound of the dominating variable
1264 	       * from a negative coefficient within a <= relation. if y has a positive coefficient
1265 	       * we get a common lower bound of x from predictive bound analysis. if y has a
1266 	       * negative coefficient we get an improved lower bound of x because the minactivity
1267 	       * is greater. for discrete variables we have to round down the lower bound.
1268 	       */
1269 	      if( !SCIPisInfinity(scip, -dominatinglb) )
1270 	      {
1271 	         SCIP_Real newlb;
1272 	         SCIP_Real oldlb;
1273 	         SCIP_Real ub;
1274 	
1275 	         newlb = dominatinglb;
1276 	         oldlb = SCIPvarGetLbGlobal(dominatingvar);
1277 	         ub = SCIPvarGetUbGlobal(dominatingvar);
1278 	
1279 	         if( SCIPvarGetType(dominatingvar) != SCIP_VARTYPE_CONTINUOUS )
1280 	            newlb = SCIPfloor(scip, newlb);
1281 	
1282 	         if( SCIPisLT(scip, oldlb, newlb) && SCIPisLE(scip, newlb, ub) )
1283 	         {
1284 	            SCIPdebugMsg(scip, "[lb]\tlower bound of dominating variable <%s> changed: [%.17f,%.17f] -> [%.17f,%.17f]\n",
1285 	               SCIPvarGetName(dominatingvar), oldlb, ub, newlb, ub);
1286 	            SCIP_CALL( SCIPchgVarLb(scip, dominatingvar, newlb) );
1287 	            (*nchgbds)++;
1288 	         }
1289 	      }
1290 	
1291 	      /* assume x dominates y (x->y). we get this bound from a positive coefficient
1292 	       * of x within a <= relation. from x->y it follows, that y has a positive
1293 	       * coefficient in this row too. the worst case upper bound of x is an estimation
1294 	       * of how great x can be in every case. if the objective coefficient of x is
1295 	       * negative we get thus a lower bound of x. for discrete variables we have
1296 	       * to round down the lower bound before.
1297 	       */
1298 	      if( !SCIPisInfinity(scip, dominatingwcub) && SCIPisNegative(scip, SCIPvarGetObj(dominatingvar)))
1299 	      {
1300 	         SCIP_Real newlb;
1301 	         SCIP_Real oldlb;
1302 	         SCIP_Real ub;
1303 	
1304 	         newlb = dominatingwcub;
1305 	         oldlb = SCIPvarGetLbGlobal(dominatingvar);
1306 	         ub = SCIPvarGetUbGlobal(dominatingvar);
1307 	
1308 	         if( SCIPvarGetType(dominatingvar) != SCIP_VARTYPE_CONTINUOUS )
1309 	            newlb = SCIPfloor(scip, newlb);
1310 	
1311 	         if( SCIPisLT(scip, oldlb, newlb) && SCIPisLE(scip, newlb, ub) )
1312 	         {
1313 	            SCIPdebugMsg(scip, "[wcub]\tlower bound of dominating variable <%s> changed: [%.17f,%.17f] -> [%.17f,%.17f]\n",
1314 	               SCIPvarGetName(dominatingvar), oldlb, ub, newlb, ub);
1315 	            SCIP_CALL( SCIPchgVarLb(scip, dominatingvar, newlb) );
1316 	            (*nchgbds)++;
1317 	         }
1318 	      }
1319 	   }
1320 	
1321 	   if( varstofix[dominatedidx] == NOFIX )
1322 	   {
1323 	      /* assume x dominates y (x->y). we get this bound for a positive coefficient of y
1324 	       * within a <= relation. if x has a negative coefficient we get a common upper
1325 	       * bound of y. if x has a positive coefficient we get an improved upper bound
1326 	       * of y because the minactivity is greater.
1327 	       */
1328 	      if( !SCIPisInfinity(scip, dominatedub) )
1329 	      {
1330 	         SCIP_Real newub;
1331 	         SCIP_Real oldub;
1332 	         SCIP_Real lb;
1333 	
1334 	         newub = dominatedub;
1335 	         oldub = SCIPvarGetUbGlobal(dominatedvar);
1336 	         lb = SCIPvarGetLbGlobal(dominatedvar);
1337 	
1338 	         if( SCIPisLE(scip, lb, newub) && SCIPisLT(scip, newub, oldub) )
1339 	         {
1340 	            SCIPdebugMsg(scip, "[ub]\tupper bound of dominated variable <%s> changed: [%.17f,%.17f] -> [%.17f,%.17f]\n",
1341 	               SCIPvarGetName(dominatedvar), lb, oldub, lb, newub);
1342 	            SCIP_CALL( SCIPchgVarUb(scip, dominatedvar, newub) );
1343 	            (*nchgbds)++;
1344 	         }
1345 	      }
1346 	
1347 	      /* assume x dominates y (x->y). we get this bound only from a negative
1348 	       * coefficient of y within a <= relation. because of x->y then x has a negative
1349 	       * coefficient too. the worst case lower bound is an estimation what property
1350 	       * the dominated variable must have if the dominating variable is at its upper bound.
1351 	       * to get an upper bound of the dominated variable we need to consider a positive
1352 	       * objective coefficient. for discrete variables we have to round up the upper bound.
1353 	       */
1354 	      if( !SCIPisInfinity(scip, -dominatedwclb) && SCIPisPositive(scip, SCIPvarGetObj(dominatedvar)) )
1355 	      {
1356 	         SCIP_Real newub;
1357 	         SCIP_Real oldub;
1358 	         SCIP_Real lb;
1359 	
1360 	         newub = dominatedwclb;
1361 	         oldub = SCIPvarGetUbGlobal(dominatedvar);
1362 	         lb = SCIPvarGetLbGlobal(dominatedvar);
1363 	
1364 	         if( SCIPvarGetType(dominatedvar) != SCIP_VARTYPE_CONTINUOUS )
1365 	            newub = SCIPceil(scip, newub);
1366 	
1367 	         if( SCIPisLE(scip, lb, newub) && SCIPisLT(scip, newub, oldub) )
1368 	         {
1369 	            SCIPdebugMsg(scip, "[wclb]\tupper bound of dominated variable <%s> changed: [%.17f,%.17f] -> [%.17f,%.17f]\n",
1370 	               SCIPvarGetName(dominatedvar), lb, oldub, lb, newub);
1371 	            SCIP_CALL( SCIPchgVarUb(scip, dominatedvar, newub) );
1372 	            (*nchgbds)++;
1373 	         }
1374 	      }
1375 	
1376 	      /* assume x dominates y (x->y). we get a lower bound of y from a negative
1377 	       * coefficient within a <= relation. but if x->y then x has a negative
1378 	       * coefficient too and contributes with its upper bound to the minactivity.
1379 	       * thus in all we have a common lower bound calculation and no rounding is necessary.
1380 	       */
1381 	      if( !SCIPisInfinity(scip, -dominatedlb) )
1382 	      {
1383 	         SCIP_Real newlb;
1384 	         SCIP_Real oldlb;
1385 	         SCIP_Real ub;
1386 	
1387 	         newlb = dominatedlb;
1388 	         oldlb = SCIPvarGetLbGlobal(dominatedvar);
1389 	         ub = SCIPvarGetUbGlobal(dominatedvar);
1390 	
1391 	         if( SCIPisLT(scip, oldlb, newlb) && SCIPisLE(scip, newlb, ub) )
1392 	         {
1393 	            SCIPdebugMsg(scip, "[lb]\tlower bound of dominated variable <%s> changed: [%.17f,%.17f] -> [%.17f,%.17f]\n",
1394 	               SCIPvarGetName(dominatedvar), oldlb, ub, newlb, ub);
1395 	            SCIP_CALL( SCIPchgVarLb(scip, dominatedvar, newlb) );
1396 	            (*nchgbds)++;
1397 	         }
1398 	      }
1399 	   }
1400 	
1401 	   return SCIP_OKAY;
1402 	}
1403 	
1404 	/** try to find variable fixings */
1405 	static
1406 	SCIP_RETCODE findFixings(
1407 	   SCIP*                 scip,               /**< SCIP main data structure */
1408 	   SCIP_MATRIX*          matrix,             /**< constraint matrix structure */
1409 	   SCIP_VAR*             dominatingvar,      /**< dominating variable */
1410 	   int                   dominatingidx,      /**< column index of the dominating variable */
1411 	   SCIP_Real             dominatingub,       /**< predicted upper bound of the dominating variable */
1412 	   SCIP_Real             dominatingwclb,     /**< predicted worst case lower bound of the dominating variable */
1413 	   SCIP_Real             dominatinglb,       /**< predicted lower bound of the dominating variable */
1414 	   SCIP_Real             dominatingwcub,     /**< predicted worst case upper bound of the dominating variable */
1415 	   SCIP_VAR*             dominatedvar,       /**< dominated variable */
1416 	   int                   dominatedidx,       /**< column index of the dominated variable */
1417 	   FIXINGDIRECTION*      varstofix,          /**< array holding fixing information */
1418 	   SCIP_Bool             onlybinvars,        /**< flag indicating only binary variables are present */
1419 	   SCIP_Bool             onlyoneone,         /**< when onlybinvars is TRUE, flag indicates if both binary variables are in clique */
1420 	   int*                  nfixings            /**< counter for possible fixings */
1421 	   )
1422 	{
1423 	   /* we compare only variables from the same type */
1424 	   if( !(SCIPvarGetType(dominatingvar) == SCIPvarGetType(dominatedvar) ||
1425 	         SCIPvarIsBinary(dominatingvar) == SCIPvarIsBinary(dominatedvar) ||
1426 	         (SCIPvarGetType(dominatingvar) == SCIP_VARTYPE_INTEGER && SCIPvarGetType(dominatedvar) == SCIP_VARTYPE_IMPLINT) ||
1427 	         (SCIPvarGetType(dominatedvar) == SCIP_VARTYPE_INTEGER && SCIPvarGetType(dominatingvar) == SCIP_VARTYPE_IMPLINT)) )
1428 	   {
1429 	      return SCIP_OKAY;
1430 	   }
1431 	
1432 	   if( varstofix[dominatedidx] == NOFIX && SCIPmatrixGetColNNonzs(matrix, dominatingidx) == 1
1433 	      && SCIPmatrixGetColNNonzs(matrix, dominatedidx) == 1 )
1434 	   {
1435 	      /* We have a x->y dominance relation and only one equality constraint
1436 	       * where the dominating variable x with an infinity upper bound and the
1437 	       * dominated variable y are present. Then the dominated variable y
1438 	       * can be fixed at its lower bound.
1439 	       */
1440 	      int row;
1441 	      row = *(SCIPmatrixGetColIdxPtr(matrix, dominatedidx));
1442 	
1443 	      if( SCIPisEQ(scip, SCIPmatrixGetRowLhs(matrix, row), SCIPmatrixGetRowRhs(matrix, row)) &&
1444 	         SCIPisInfinity(scip, SCIPvarGetUbGlobal(dominatingvar)) )
1445 	      {
1446 	         varstofix[dominatedidx] = FIXATLB;
1447 	         (*nfixings)++;
1448 	
1449 	         return SCIP_OKAY;
1450 	      }
1451 	   }
1452 	
1453 	   if( varstofix[dominatedidx] == NOFIX && !SCIPisNegative(scip, SCIPvarGetObj(dominatedvar)) )
1454 	   {
1455 	      if( !SCIPisInfinity(scip, -dominatingwclb) &&
1456 	         SCIPisLE(scip, dominatingwclb, SCIPvarGetUbGlobal(dominatingvar)) )
1457 	      {
1458 	         /* we have a x->y dominance relation with a positive obj coefficient
1459 	          * of the dominated variable y. we need to secure feasibility
1460 	          * by testing if the predicted lower worst case bound is less equal the
1461 	          * current upper bound. it is possible, that the lower worst case bound
1462 	          * is infinity and the upper bound of the dominating variable x is
1463 	          * infinity too.
1464 	          */
1465 	         varstofix[dominatedidx] = FIXATLB;
1466 	         (*nfixings)++;
1467 	      }
1468 	   }
1469 	
1470 	   if( varstofix[dominatedidx] == NOFIX && !SCIPisInfinity(scip, dominatingub) &&
1471 	      SCIPisLE(scip, dominatingub, SCIPvarGetUbGlobal(dominatingvar)) )
1472 	   {
1473 	      /* we have a x->y dominance relation with an arbitrary obj coefficient
1474 	       * of the dominating variable x. in all cases we have to look
1475 	       * if the predicted upper bound of the dominating variable is great enough.
1476 	       * by testing, that the predicted upper bound is not infinity we avoid problems
1477 	       * with x->y e.g.
1478 	       *    min  -x -y
1479 	       *    s.t. -x -y <= -1
1480 	       *    0<=x<=1, 0<=y<=1
1481 	       * where y is not at their lower bound.
1482 	       */
1483 	      varstofix[dominatedidx] = FIXATLB;
1484 	      (*nfixings)++;
1485 	   }
1486 	
1487 	   if( varstofix[dominatingidx] == NOFIX && !SCIPisPositive(scip, SCIPvarGetObj(dominatingvar)) )
1488 	   {
1489 	      /* we have a x->y dominance relation with a negative obj coefficient
1490 	       * of the dominating variable x. if the worst case upper bound is
1491 	       * greater equal than upper bound, we fix x at the upper bound
1492 	       */
1493 	      if( !SCIPisInfinity(scip, dominatingwcub) &&
1494 	         SCIPisGE(scip, dominatingwcub, SCIPvarGetUbGlobal(dominatingvar)) )
1495 	      {
1496 	         varstofix[dominatingidx] = FIXATUB;
1497 	         (*nfixings)++;
1498 	      }
1499 	   }
1500 	
1501 	   if( varstofix[dominatingidx] == NOFIX && !SCIPisInfinity(scip, -dominatinglb) &&
1502 	      SCIPisGE(scip, dominatinglb, SCIPvarGetUbGlobal(dominatingvar)) )
1503 	   {
1504 	       /* we have a x->y dominance relation with an arbitrary obj coefficient
1505 	        * of the dominating variable x. if the predicted lower bound is greater
1506 	        * equal than upper bound, we fix x at the upper bound.
1507 	        */
1508 	      varstofix[dominatingidx] = FIXATUB;
1509 	      (*nfixings)++;
1510 	   }
1511 	
1512 	   if( onlybinvars )
1513 	   {
1514 	      if( varstofix[dominatedidx] == NOFIX && (onlyoneone || SCIPvarsHaveCommonClique(dominatingvar, TRUE, dominatedvar, TRUE, TRUE)) )
1515 	      {
1516 	         /* We have a (1->1)-clique with dominance relation (x->y) (x dominates y).
1517 	          * From this dominance relation, we know (1->0) is possible and not worse than (0->1)
1518 	          * concerning the objective function. It follows that only (1->0) or (0->0) are possible,
1519 	          * but in both cases y has the value 0 => y=0.
1520 	          */
1521 	         varstofix[dominatedidx] = FIXATLB;
1522 	         (*nfixings)++;
1523 	      }
1524 	
1525 	      if( varstofix[dominatingidx] == NOFIX && SCIPvarsHaveCommonClique(dominatingvar, FALSE, dominatedvar, FALSE, TRUE) )
1526 	      {
1527 	         /* We have a (0->0)-clique with dominance relation x->y (x dominates y).
1528 	          * From this dominance relation, we know (1->0) is possible and not worse than (0->1)
1529 	          * concerning the objective function. It follows that only (1->0) or (1->1) are possible,
1530 	          * but in both cases x has the value 1 => x=1
1531 	          */
1532 	         varstofix[dominatingidx] = FIXATUB;
1533 	         (*nfixings)++;
1534 	      }
1535 	   }
1536 	   else
1537 	      assert(!onlyoneone);
1538 	
1539 	   return SCIP_OKAY;
1540 	}
1541 	
1542 	/** find dominance relation between variable pairs */
1543 	static
1544 	SCIP_RETCODE findDominancePairs(
1545 	   SCIP*                 scip,               /**< SCIP main data structure */
1546 	   SCIP_MATRIX*          matrix,             /**< matrix containing the constraints */
1547 	   SCIP_PRESOLDATA*      presoldata,         /**< presolver data */
1548 	   int*                  searchcols,         /**< indexes of variables for pair comparisons */
1549 	   int                   searchsize,         /**< number of variables for pair comparisons */
1550 	   SCIP_Bool             onlybinvars,        /**< flag indicating searchcols contains only binary variable indexes */
1551 	   FIXINGDIRECTION*      varstofix,          /**< array holding information for later upper/lower bound fixing */
1552 	   int*                  nfixings,           /**< found number of possible fixings */
1553 	   SCIP_Longint*         ndomrelations,      /**< found number of dominance relations */
1554 	   int*                  nchgbds             /**< number of changed bounds */
1555 	   )
1556 	{
1557 	   SCIP_Real* vals1;
1558 	   SCIP_Real* vals2;
1559 	   SCIP_Real tmpupperbounddominatingcol1;
1560 	   SCIP_Real tmpupperbounddominatingcol2;
1561 	   SCIP_Real tmpwclowerbounddominatingcol1;
1562 	   SCIP_Real tmpwclowerbounddominatingcol2;
1563 	   SCIP_Real tmplowerbounddominatingcol1;
1564 	   SCIP_Real tmplowerbounddominatingcol2;
1565 	   SCIP_Real tmpwcupperbounddominatingcol1;
1566 	   SCIP_Real tmpwcupperbounddominatingcol2;
1567 	   int* rows1;
1568 	   int* rows2;
1569 	   int nrows1;
1570 	   int nrows2;
1571 	   SCIP_Real tmpupperbounddominatedcol1;
1572 	   SCIP_Real tmpupperbounddominatedcol2;
1573 	   SCIP_Real tmpwclowerbounddominatedcol1;
1574 	   SCIP_Real tmpwclowerbounddominatedcol2;
1575 	   SCIP_Real tmplowerbounddominatedcol1;
1576 	   SCIP_Real tmplowerbounddominatedcol2;
1577 	   SCIP_Real tmpwcupperbounddominatedcol1;
1578 	   SCIP_Real tmpwcupperbounddominatedcol2;
1579 	   SCIP_Real obj1;
1580 	   SCIP_Bool col1domcol2;
1581 	   SCIP_Bool col2domcol1;
1582 	   SCIP_Bool onlyoneone;
1583 	   int cnt1;
1584 	   int cnt2;
1585 	   int col1;
1586 	   int col2;
1587 	   int r1;
1588 	   int r2;
1589 	   int paircnt;
1590 	   int oldnfixings;
1591 	
1592 	   assert(scip != NULL);
1593 	   assert(matrix != NULL);
1594 	   assert(presoldata != NULL);
1595 	   assert(searchcols != NULL);
1596 	   assert(varstofix != NULL);
1597 	   assert(nfixings != NULL);
1598 	   assert(ndomrelations != NULL);
1599 	   assert(nchgbds != NULL);
1600 	
1601 	   paircnt = 0;
1602 	   oldnfixings = *nfixings;
1603 	
1604 	   /* pair comparisons */
1605 	   for( cnt1 = 0; cnt1 < searchsize; cnt1++ )
1606 	   {
1607 	      SCIP_VAR* varcol1;
1608 	      SCIP_VAR* varcol2;
1609 	
1610 	      /* get index of the first variable */
1611 	      col1 = searchcols[cnt1];
1612 	
1613 	      if( varstofix[col1] == FIXATLB )
1614 	         continue;
1615 	
1616 	      varcol1 = SCIPmatrixGetVar(matrix, col1);
1617 	      obj1 = SCIPvarGetObj(varcol1);
1618 	
1619 	      for( cnt2 = cnt1+1; cnt2 < searchsize; cnt2++ )
1620 	      {
1621 	         /* get index of the second variable */
1622 	         col2 = searchcols[cnt2];
1623 	         varcol2 = SCIPmatrixGetVar(matrix, col2);
1624 	         onlyoneone = FALSE;
1625 	
1626 	         /* we always have minimize as obj sense */
1627 	
1628 	         /* column 1 dominating column 2 */
1629 	         col1domcol2 = (obj1 <= SCIPvarGetObj(varcol2));
1630 	
1631 	         /* column 2 dominating column 1 */
1632 	         col2domcol1 = (SCIPvarGetObj(varcol2) <= obj1);
1633 	
1634 	         /* search only if nothing was found yet */
1635 	         col1domcol2 = col1domcol2 && (varstofix[col2] == NOFIX);
1636 	         col2domcol1 = col2domcol1 && (varstofix[col1] == NOFIX);
1637 	
1638 	         /* we only search for a dominance relation if the lower bounds are not negative */
1639 	         if( !onlybinvars )
1640 	         {
1641 	            if( SCIPisLT(scip, SCIPvarGetLbGlobal(varcol1), 0.0) ||
1642 	               SCIPisLT(scip, SCIPvarGetLbGlobal(varcol2), 0.0) )
1643 	            {
1644 	               col1domcol2 = FALSE;
1645 	               col2domcol1 = FALSE;
1646 	            }
1647 	         }
1648 	
1649 	         /* pair comparison control */
1650 	         if( paircnt == presoldata->numcurrentpairs )
1651 	         {
1652 	            assert(*nfixings >= oldnfixings);
1653 	            if( *nfixings == oldnfixings )
1654 	            {
1655 	               /* not enough fixings found, decrement number of comparisons */
1656 	               presoldata->numcurrentpairs >>= 1; /*lint !e702*/
1657 	               if( presoldata->numcurrentpairs < presoldata->numminpairs )
1658 	                  presoldata->numcurrentpairs = presoldata->numminpairs;
1659 	
1660 	               /* stop searching in this row */
1661 	               return SCIP_OKAY;
1662 	            }
1663 	            oldnfixings = *nfixings;
1664 	            paircnt = 0;
1665 	
1666 	            /* increment number of comparisons */
1667 	            presoldata->numcurrentpairs <<= 1; /*lint !e701*/
1668 	            if( presoldata->numcurrentpairs > presoldata->nummaxpairs )
1669 	               presoldata->numcurrentpairs = presoldata->nummaxpairs;
1670 	         }
1671 	         paircnt++;
1672 	
1673 	         if( !col1domcol2 && !col2domcol1 )
1674 	            continue;
1675 	
1676 	         /* get the data for both columns */
1677 	         vals1 = SCIPmatrixGetColValPtr(matrix, col1);
1678 	         rows1 = SCIPmatrixGetColIdxPtr(matrix, col1);
1679 	         nrows1 = SCIPmatrixGetColNNonzs(matrix, col1);
1680 	         r1 = 0;
1681 	         vals2 = SCIPmatrixGetColValPtr(matrix, col2);
1682 	         rows2 = SCIPmatrixGetColIdxPtr(matrix, col2);
1683 	         nrows2 = SCIPmatrixGetColNNonzs(matrix, col2);
1684 	         r2 = 0;
1685 	
1686 	         /* do we have a obj constant? */
1687 	         if( nrows1 == 0 || nrows2 == 0 )
1688 	            continue;
1689 	
1690 	         /* initialize temporary bounds of dominating variable */
1691 	         tmpupperbounddominatingcol1 = SCIPinfinity(scip);
1692 	         tmpupperbounddominatingcol2 = tmpupperbounddominatingcol1;
1693 	         tmpwclowerbounddominatingcol1 = -SCIPinfinity(scip);
1694 	         tmpwclowerbounddominatingcol2 = tmpwclowerbounddominatingcol1;
1695 	         tmplowerbounddominatingcol1 = -SCIPinfinity(scip);
1696 	         tmplowerbounddominatingcol2 = tmplowerbounddominatingcol1;
1697 	         tmpwcupperbounddominatingcol1 = SCIPinfinity(scip);
1698 	         tmpwcupperbounddominatingcol2 = tmpwcupperbounddominatingcol1;
1699 	
1700 	         /* initialize temporary bounds of dominated variable */
1701 	         tmpupperbounddominatedcol1 = SCIPinfinity(scip);
1702 	         tmpupperbounddominatedcol2 = tmpupperbounddominatedcol1;
1703 	         tmpwclowerbounddominatedcol1 = -SCIPinfinity(scip);
1704 	         tmpwclowerbounddominatedcol2 = tmpwclowerbounddominatedcol1;
1705 	         tmplowerbounddominatedcol1 = -SCIPinfinity(scip);
1706 	         tmplowerbounddominatedcol2 = tmplowerbounddominatedcol1;
1707 	         tmpwcupperbounddominatedcol1 = SCIPinfinity(scip);
1708 	         tmpwcupperbounddominatedcol2 = tmpwcupperbounddominatedcol1;
1709 	
1710 	         /* compare rows of this column pair */
1711 	         while( (col1domcol2 || col2domcol1) && (r1 < nrows1 || r2 < nrows2) )
1712 	         {
1713 	            assert((r1 >= nrows1-1) || (rows1[r1] < rows1[r1+1]));
1714 	            assert((r2 >= nrows2-1) || (rows2[r2] < rows2[r2+1]));
1715 	
1716 	            /* there is a nonredundant row containing column 1 but not column 2 */
1717 	            if( r1 < nrows1 && (r2 == nrows2 || rows1[r1] < rows2[r2]) )
1718 	            {
1719 	               /* dominance depends on the type of relation */
1720 	               if( !SCIPmatrixIsRowRhsInfinity(matrix, rows1[r1]) )
1721 	               {
1722 	                  /* no dominance relation for equations or ranged rows */
1723 	                  col2domcol1 = FALSE;
1724 	                  col1domcol2 = FALSE;
1725 	               }
1726 	               else
1727 	               {
1728 	                  /* >= relation, larger coefficients dominate smaller ones */
1729 	                  if( vals1[r1] > 0.0 )
1730 	                     col2domcol1 = FALSE;
1731 	                  else
1732 	                     col1domcol2 = FALSE;
1733 	               }
1734 	
1735 	               r1++;
1736 	            }
1737 	            /* there is a nonredundant row containing column 2, but not column 1 */
1738 	            else if( r2 < nrows2 && (r1 == nrows1 || rows1[r1] > rows2[r2]) )
1739 	            {
1740 	               /* dominance depends on the type of relation */
1741 	               if( !SCIPmatrixIsRowRhsInfinity(matrix, rows2[r2]) )
1742 	               {
1743 	                  /* no dominance relation for equations or ranged rows */
1744 	                  col2domcol1 = FALSE;
1745 	                  col1domcol2 = FALSE;
1746 	               }
1747 	               else
1748 	               {
1749 	                  /* >= relation, larger coefficients dominate smaller ones */
1750 	                  if( vals2[r2] < 0.0 )
1751 	                     col2domcol1 = FALSE;
1752 	                  else
1753 	                     col1domcol2 = FALSE;
1754 	               }
1755 	
1756 	               r2++;
1757 	            }
1758 	            /* if both columns appear in a common row, compare the coefficients */
1759 	            else
1760 	            {
1761 	               assert(r1 < nrows1 && r2 < nrows2);
1762 	               assert(rows1[r1] == rows2[r2]);
1763 	
1764 	               /* if both columns are binary variables we check if they have a common clique
1765 	                * and do not calculate any bounds
1766 	                */
1767 	               if( onlybinvars && !onlyoneone )
1768 	               {
1769 	                  if( vals1[r1] < 0 && vals2[r2] < 0 )
1770 	                  {
1771 	                     if( (SCIPmatrixGetRowNMaxActPosInf(matrix, rows1[r1]) + SCIPmatrixGetRowNMaxActNegInf(matrix, rows1[r1]) == 0)
1772 	                        && SCIPisFeasLE(scip, SCIPmatrixGetRowMaxActivity(matrix, rows1[r1]) + MAX(vals1[r1], vals2[r2]),
1773 	                           SCIPmatrixGetRowLhs(matrix, rows1[r1])) )
1774 	                     {
1775 	                        onlyoneone = TRUE;
1776 	                     }
1777 	                  }
1778 	
1779 	                  if( !onlyoneone && !SCIPmatrixIsRowRhsInfinity(matrix, rows1[r1]) )
1780 	                  {
1781 	                     if ( vals1[r1] > 0 && vals2[r2] > 0 )
1782 	                     {
1783 	                        if( (SCIPmatrixGetRowNMinActPosInf(matrix, rows1[r1]) + SCIPmatrixGetRowNMinActNegInf(matrix, rows1[r1]) == 0)
1784 	                           && SCIPisFeasGE(scip, SCIPmatrixGetRowMinActivity(matrix, rows1[r1]) + MIN(vals1[r1], vals2[r2]),
1785 	                              SCIPmatrixGetRowRhs(matrix, rows1[r1])) )
1786 	                        {
1787 	                           onlyoneone = TRUE;
1788 	                        }
1789 	                     }
1790 	                  }
1791 	
1792 	                  if( onlyoneone )
1793 	                  {
1794 	                     /* reset bounds */
1795 	                     tmpupperbounddominatingcol1 = SCIPinfinity(scip);
1796 	                     tmpupperbounddominatingcol2 = tmpupperbounddominatingcol1;
1797 	                     tmpwclowerbounddominatingcol1 = -SCIPinfinity(scip);
1798 	                     tmpwclowerbounddominatingcol2 = tmpwclowerbounddominatingcol1;
1799 	                     tmplowerbounddominatingcol1 = -SCIPinfinity(scip);
1800 	                     tmplowerbounddominatingcol2 = tmplowerbounddominatingcol1;
1801 	                     tmpwcupperbounddominatingcol1 = SCIPinfinity(scip);
1802 	                     tmpwcupperbounddominatingcol2 = tmpwcupperbounddominatingcol1;
1803 	
1804 	                     tmpupperbounddominatedcol1 = SCIPinfinity(scip);
1805 	                     tmpupperbounddominatedcol2 = tmpupperbounddominatedcol1;
1806 	                     tmpwclowerbounddominatedcol1 = -SCIPinfinity(scip);
1807 	                     tmpwclowerbounddominatedcol2 = tmpwclowerbounddominatedcol1;
1808 	                     tmplowerbounddominatedcol1 = -SCIPinfinity(scip);
1809 	                     tmplowerbounddominatedcol2 = tmplowerbounddominatedcol1;
1810 	                     tmpwcupperbounddominatedcol1 = SCIPinfinity(scip);
1811 	                     tmpwcupperbounddominatedcol2 = tmpwcupperbounddominatedcol1;
1812 	                  }
1813 	               }
1814 	
1815 	               /* dominance depends on the type of inequality */
1816 	               if( !SCIPmatrixIsRowRhsInfinity(matrix, rows1[r1]) )
1817 	               {
1818 	                  /* no dominance relation if coefficients differ for equations or ranged rows */
1819 	                  if( !SCIPisEQ(scip, vals1[r1], vals2[r2]) )
1820 	                  {
1821 	                     col2domcol1 = FALSE;
1822 	                     col1domcol2 = FALSE;
1823 	                  }
1824 	               }
1825 	               else
1826 	               {
1827 	                  /* >= relation, larger coefficients dominate smaller ones */
1828 	                  if( vals1[r1] > vals2[r2] )
1829 	                     col2domcol1 = FALSE;
1830 	                  else if( vals1[r1] < vals2[r2] )
1831 	                     col1domcol2 = FALSE;
1832 	               }
1833 	
1834 	               /* we do not use bound calulations if two binary variable are in one common clique.
1835 	                * for the other cases we claim the same sign for the coefficients to
1836 	                * achieve monotonically decreasing predictive bound functions.
1837 	                */
1838 	               if( !onlyoneone &&
1839 	                  ((vals1[r1] < 0 && vals2[r2] < 0) || (vals1[r1] > 0 && vals2[r2] > 0)) )
1840 	               {
1841 	                  if( col1domcol2 )
1842 	                  {
1843 	                     /* update bounds of dominating variable for column 1 */
1844 	                     SCIP_CALL( updateBounds(scip, matrix, rows1[r1],
1845 	                           col1, vals1[r1], col2, vals2[r2], TRUE,
1846 	                           &tmpupperbounddominatingcol1, &tmpwclowerbounddominatingcol1,
1847 	                           &tmplowerbounddominatingcol1, &tmpwcupperbounddominatingcol1) );
1848 	
1849 	                     /* update bounds of dominated variable for column 1 */
1850 	                     SCIP_CALL( updateBounds(scip, matrix, rows1[r1],
1851 	                           col1, vals1[r1], col2, vals2[r2], FALSE,
1852 	                           &tmpupperbounddominatedcol1, &tmpwclowerbounddominatedcol1,
1853 	                           &tmplowerbounddominatedcol1, &tmpwcupperbounddominatedcol1) );
1854 	                  }
1855 	
1856 	                  if( col2domcol1 )
1857 	                  {
1858 	                     /* update bounds of dominating variable for column 2 */
1859 	                     SCIP_CALL( updateBounds(scip, matrix, rows2[r2],
1860 	                           col2, vals2[r2], col1, vals1[r1], TRUE,
1861 	                           &tmpupperbounddominatingcol2, &tmpwclowerbounddominatingcol2,
1862 	                           &tmplowerbounddominatingcol2, &tmpwcupperbounddominatingcol2) );
1863 	
1864 	                     /* update bounds of dominated variable for column 2 */
1865 	                     SCIP_CALL( updateBounds(scip, matrix, rows2[r2],
1866 	                           col2, vals2[r2], col1, vals1[r1], FALSE,
1867 	                           &tmpupperbounddominatedcol2, &tmpwclowerbounddominatedcol2,
1868 	                           &tmplowerbounddominatedcol2, &tmpwcupperbounddominatedcol2) );
1869 	                  }
1870 	               }
1871 	
1872 	               r1++;
1873 	               r2++;
1874 	            }
1875 	         }
1876 	
1877 	         /* a column is only dominated, if there are no more rows in which it is contained */
1878 	         col1domcol2 = col1domcol2 && r2 == nrows2;
1879 	         col2domcol1 = col2domcol1 && r1 == nrows1;
1880 	
1881 	         if( !col1domcol2 && !col2domcol1 )
1882 	            continue;
1883 	
1884 	         /* no dominance relation for left equations or ranged rows */
1885 	         while( r1 < nrows1 )
1886 	         {
1887 	            if( !SCIPmatrixIsRowRhsInfinity(matrix, rows1[r1]) )
1888 	            {
1889 	               col2domcol1 = FALSE;
1890 	               col1domcol2 = FALSE;
1891 	               break;
1892 	            }
1893 	            r1++;
1894 	         }
1895 	         if( !col1domcol2 && !col2domcol1 )
1896 	            continue;
1897 	         while( r2 < nrows2 )
1898 	         {
1899 	            if( !SCIPmatrixIsRowRhsInfinity(matrix, rows2[r2]) )
1900 	            {
1901 	               col2domcol1 = FALSE;
1902 	               col1domcol2 = FALSE;
1903 	               break;
1904 	            }
1905 	            r2++;
1906 	         }
1907 	
1908 	         if( col1domcol2 || col2domcol1 )
1909 	            (*ndomrelations)++;
1910 	
1911 	         if( col1domcol2 && col2domcol1 )
1912 	         {
1913 	            /* prefer the variable as dominating variable with the greater upper bound */
1914 	            if( SCIPisGE(scip, SCIPvarGetUbGlobal(varcol1), SCIPvarGetUbGlobal(varcol2)) )
1915 	               col2domcol1 = FALSE;
1916 	            else
1917 	               col1domcol2 = FALSE;
1918 	         }
1919 	
1920 	         /* use dominance relation and clique/bound-information
1921 	          * to find variable fixings. additionally try to strengthen
1922 	          * variable bounds by predictive bound strengthening.
1923 	          */
1924 	         if( col1domcol2 )
1925 	         {
1926 	            SCIP_CALL( findFixings(scip, matrix, varcol1, col1,
1927 	                  tmpupperbounddominatingcol1, tmpwclowerbounddominatingcol1,
1928 	                  tmplowerbounddominatingcol1, tmpwcupperbounddominatingcol1,
1929 	                  varcol2, col2,
1930 	                  varstofix, onlybinvars, onlyoneone, nfixings) );
1931 	
1932 	            if( presoldata->predbndstr )
1933 	            {
1934 	               SCIP_CALL( predBndStr(scip, varcol1, col1,
1935 	                     tmpupperbounddominatingcol1,
1936 	                     tmplowerbounddominatingcol1, tmpwcupperbounddominatingcol1,
1937 	                     varcol2, col2,
1938 	                     tmpupperbounddominatedcol1, tmpwclowerbounddominatedcol1,
1939 	                     tmplowerbounddominatedcol1,
1940 	                     varstofix, nchgbds) );
1941 	            }
1942 	         }
1943 	         else if( col2domcol1 )
1944 	         {
1945 	            SCIP_CALL( findFixings(scip, matrix, varcol2, col2,
1946 	                  tmpupperbounddominatingcol2, tmpwclowerbounddominatingcol2,
1947 	                  tmplowerbounddominatingcol2, tmpwcupperbounddominatingcol2,
1948 	                  varcol1, col1,
1949 	                  varstofix, onlybinvars, onlyoneone, nfixings) );
1950 	
1951 	            if( presoldata->predbndstr )
1952 	            {
1953 	               SCIP_CALL( predBndStr(scip, varcol2, col2,
1954 	                     tmpupperbounddominatingcol2,
1955 	                     tmplowerbounddominatingcol2, tmpwcupperbounddominatingcol2,
1956 	                     varcol1, col1,
1957 	                     tmpupperbounddominatedcol2, tmpwclowerbounddominatedcol2,
1958 	                     tmplowerbounddominatedcol2,
1959 	                     varstofix, nchgbds) );
1960 	            }
1961 	         }
1962 	         if( varstofix[col1] == FIXATLB )
1963 	            break;
1964 	      }
1965 	   }
1966 	
1967 	   return SCIP_OKAY;
1968 	}
1969 	
1970 	
1971 	/*
1972 	 * Callback methods of presolver
1973 	 */
1974 	
1975 	
1976 	/** copy method for constraint handler plugins (called when SCIP copies plugins) */
1977 	static
1978 	SCIP_DECL_PRESOLCOPY(presolCopyDomcol)
1979 	{  /*lint --e{715}*/
1980 	   assert(scip != NULL);
1981 	   assert(presol != NULL);
1982 	   assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
1983 	
1984 	   /* call inclusion method of presolver */
1985 	   SCIP_CALL( SCIPincludePresolDomcol(scip) );
1986 	
1987 	   return SCIP_OKAY;
1988 	}
1989 	
1990 	/** destructor of presolver to free user data (called when SCIP is exiting) */
1991 	static
1992 	SCIP_DECL_PRESOLFREE(presolFreeDomcol)
1993 	{  /*lint --e{715}*/
1994 	   SCIP_PRESOLDATA* presoldata;
1995 	
1996 	   /* free presolver data */
1997 	   presoldata = SCIPpresolGetData(presol);
1998 	   assert(presoldata != NULL);
1999 	
2000 	   SCIPfreeBlockMemory(scip, &presoldata);
2001 	   SCIPpresolSetData(presol, NULL);
2002 	
2003 	   return SCIP_OKAY;
2004 	}
2005 	
2006 	/** execution method of presolver */
2007 	static
2008 	SCIP_DECL_PRESOLEXEC(presolExecDomcol)
2009 	{  /*lint --e{715}*/
2010 	   SCIP_PRESOLDATA* presoldata;
2011 	   SCIP_MATRIX* matrix;
2012 	   SCIP_Bool initialized;
2013 	   SCIP_Bool complete;
2014 	   SCIP_Bool infeasible;
2015 	   int nfixings;
2016 	   SCIP_Longint ndomrelations;
2017 	   int v;
2018 	   int r;
2019 	   FIXINGDIRECTION* varstofix;
2020 	   SCIP_Bool* varsprocessed;
2021 	   int nrows;
2022 	   int ncols;
2023 	   int* rowidxsorted;
2024 	   int* rowsparsity;
2025 	   int varcount;
2026 	   int* consearchcols;
2027 	   int* intsearchcols;
2028 	   int* binsearchcols;
2029 	   int nconfill;
2030 	   int nintfill;
2031 	   int nbinfill;
2032 	#ifdef SCIP_DEBUG
2033 	   int nconvarsfixed = 0;
2034 	   int nintvarsfixed = 0;
2035 	   int nbinvarsfixed = 0;
2036 	#endif
2037 	   int* pclass;
2038 	   int* colidx;
2039 	   int pclassstart;
2040 	   int pc;
2041 	   SCIP_Bool* varineq;
2042 	
2043 	   assert(result != NULL);
2044 	   *result = SCIP_DIDNOTRUN;
2045 	
2046 	   if( !SCIPallowStrongDualReds(scip) || SCIPisStopped(scip) )
2047 	      return SCIP_OKAY;
2048 	
2049 	   presoldata = SCIPpresolGetData(presol);
2050 	   assert(presoldata != NULL);
2051 	
2052 	   /* don't run for pure LPs */
2053 	   if( !presoldata->continuousred && (SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip) == 0) )
2054 	      return SCIP_OKAY;
2055 	
2056 	   *result = SCIP_DIDNOTFIND;
2057 	
2058 	   matrix = NULL;
2059 	   SCIP_CALL( SCIPmatrixCreate(scip, &matrix, TRUE, &initialized, &complete, &infeasible,
2060 	      naddconss, ndelconss, nchgcoefs, nchgbds, nfixedvars) );
2061 	
2062 	   /* if infeasibility was detected during matrix creation, return here */
2063 	   if( infeasible )
2064 	   {
2065 	      if( initialized )
2066 	         SCIPmatrixFree(scip, &matrix);
2067 	
2068 	      *result = SCIP_CUTOFF;
2069 	      return SCIP_OKAY;
2070 	   }
2071 	
2072 	   if( !initialized )
2073 	      return SCIP_OKAY;
2074 	
2075 	   nfixings = 0;
2076 	   ndomrelations = 0;
2077 	   nrows = SCIPmatrixGetNRows(matrix);
2078 	   ncols = SCIPmatrixGetNColumns(matrix);
2079 	   assert(SCIPgetNVars(scip) == ncols);
2080 	
2081 	   SCIP_CALL( SCIPallocBufferArray(scip, &varstofix, ncols) );
2082 	   BMSclearMemoryArray(varstofix, ncols);
2083 	
2084 	   SCIP_CALL( SCIPallocBufferArray(scip, &varsprocessed, ncols) );
2085 	
2086 	   /* do not process columns that do not have all locks represented in the matrix */
2087 	   for( v = 0; v < ncols; ++v )
2088 	      varsprocessed[v] = SCIPmatrixUplockConflict(matrix, v) || SCIPmatrixDownlockConflict(matrix, v);
2089 	
2090 	   SCIP_CALL( SCIPallocBufferArray(scip, &consearchcols, ncols) );
2091 	   SCIP_CALL( SCIPallocBufferArray(scip, &intsearchcols, ncols) );
2092 	   SCIP_CALL( SCIPallocBufferArray(scip, &binsearchcols, ncols) );
2093 	
2094 	   SCIP_CALL( SCIPallocBufferArray(scip, &rowidxsorted, nrows) );
2095 	   SCIP_CALL( SCIPallocBufferArray(scip, &rowsparsity, nrows) );
2096 	   for( r = 0; r < nrows; ++r )
2097 	   {
2098 	      rowidxsorted[r] = r;
2099 	      rowsparsity[r] = SCIPmatrixGetRowNNonzs(matrix, r);
2100 	   }
2101 	
2102 	   SCIP_CALL( SCIPallocBufferArray(scip, &pclass, ncols) );
2103 	   SCIP_CALL( SCIPallocBufferArray(scip, &colidx, ncols) );
2104 	   SCIP_CALL( SCIPallocBufferArray(scip, &varineq, ncols) );
2105 	   for( v = 0; v < ncols; v++ )
2106 	   {
2107 	      colidx[v] = v;
2108 	      varineq[v] = FALSE;
2109 	   }
2110 	
2111 	   /* init pair comparision control */
2112 	   presoldata->numcurrentpairs = presoldata->nummaxpairs;
2113 	
2114 	   varcount = 0;
2115 	
2116 	   /* 1.stage: search dominance relations of parallel columns
2117 	      *          within equalities and ranged rows
2118 	      */
2119 	   if( (presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 )
2120 	   {
2121 	      SCIP_CALL( detectParallelCols(scip, matrix, pclass, varineq) );
2122 	      SCIPsortIntInt(pclass, colidx, ncols);
2123 	
2124 	      pc = 0;
2125 	      while( pc < ncols )
2126 	      {
2127 	         int varidx;
2128 	
2129 	         varidx = 0;
2130 	         nconfill = 0;
2131 	         nintfill = 0;
2132 	         nbinfill = 0;
2133 	
2134 	         pclassstart = pclass[pc];
2135 	         while( pc < ncols && pclassstart == pclass[pc] )
2136 	         {
2137 	            SCIP_VAR* var;
2138 	
2139 	            varidx = colidx[pc];
2140 	            var = SCIPmatrixGetVar(matrix, varidx);
2141 	
2142 	            /* we only regard variables which were not processed yet and
2143 	               * are present within equalities or ranged rows
2144 	               */
2145 	            if( !varsprocessed[varidx] && varineq[varidx] )
2146 	            {
2147 	               /* we search only for dominance relations between the same variable type */
2148 	               if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS )
2149 	               {
2150 	                  consearchcols[nconfill++] = varidx;
2151 	               }
2152 	               else if( SCIPvarIsBinary(var) )
2153 	               {
2154 	                  binsearchcols[nbinfill++] = varidx;
2155 	               }
2156 	               else
2157 	               {
2158 	                  assert(SCIPvarGetType(var) == SCIP_VARTYPE_INTEGER || SCIPvarGetType(var) == SCIP_VARTYPE_IMPLINT);
2159 	                  intsearchcols[nintfill++] = varidx;
2160 	               }
2161 	            }
2162 	            ++pc;
2163 	         }
2164 	
2165 	         /* continuous variables */
2166 	         if( nconfill > 1 && presoldata->continuousred )
2167 	         {
2168 	            SCIP_CALL( findDominancePairs(scip, matrix, presoldata, consearchcols, nconfill, FALSE,
2169 	                  varstofix, &nfixings, &ndomrelations, nchgbds) );
2170 	
2171 	            for( v = 0; v < nconfill; ++v )
2172 	               varsprocessed[consearchcols[v]] = TRUE;
2173 	
2174 	            varcount += nconfill;
2175 	         }
2176 	         else if( nconfill == 1 )
2177 	         {
2178 	            if( varineq[varidx] )
2179 	               varsprocessed[consearchcols[0]] = TRUE;
2180 	         }
2181 	
2182 	         /* integer and impl-integer variables */
2183 	         if( nintfill > 1 )
2184 	         {
2185 	            SCIP_CALL( findDominancePairs(scip, matrix, presoldata, intsearchcols, nintfill, FALSE,
2186 	                  varstofix, &nfixings, &ndomrelations, nchgbds) );
2187 	
2188 	            for( v = 0; v < nintfill; ++v )
2189 	               varsprocessed[intsearchcols[v]] = TRUE;
2190 	
2191 	            varcount += nintfill;
2192 	         }
2193 	         else if( nintfill == 1 )
2194 	         {
2195 	            if( varineq[varidx] )
2196 	               varsprocessed[intsearchcols[0]] = TRUE;
2197 	         }
2198 	
2199 	         /* binary variables */
2200 	         if( nbinfill > 1 )
2201 	         {
2202 	            SCIP_CALL( findDominancePairs(scip, matrix, presoldata, binsearchcols, nbinfill, TRUE,
2203 	                  varstofix, &nfixings, &ndomrelations, nchgbds) );
2204 	
2205 	            for( v = 0; v < nbinfill; ++v )
2206 	               varsprocessed[binsearchcols[v]] = TRUE;
2207 	
2208 	            varcount += nbinfill;
2209 	         }
2210 	         else if( nbinfill == 1 )
2211 	         {
2212 	            if( varineq[varidx] )
2213 	               varsprocessed[binsearchcols[0]] = TRUE;
2214 	         }
2215 	
2216 	         if( varcount >= ncols )
2217 	            break;
2218 	      }
2219 	   }
2220 	
2221 	   /* 2.stage: search dominance relations for the remaining columns
2222 	      *          by increasing row-sparsity
2223 	      */
2224 	   if( (presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 )
2225 	   {
2226 	      SCIPsortIntInt(rowsparsity, rowidxsorted, nrows);
2227 	
2228 	      for( r = 0; r < nrows; ++r )
2229 	      {
2230 	         int rowidx;
2231 	         int* rowpnt;
2232 	         int* rowend;
2233 	
2234 	         /* break if the time limit was reached; since the check is expensive,
2235 	            * we only check all 1000 constraints
2236 	            */
2237 	         if( (r % 1000 == 0) && SCIPisStopped(scip) )
2238 	            break;
2239 	
2240 	         rowidx = rowidxsorted[r];
2241 	         rowpnt = SCIPmatrixGetRowIdxPtr(matrix, rowidx);
2242 	         rowend = rowpnt + SCIPmatrixGetRowNNonzs(matrix, rowidx);
2243 	
2244 	         if( SCIPmatrixGetRowNNonzs(matrix, rowidx) == 1 )
2245 	            continue;
2246 	
2247 	         nconfill = 0;
2248 	         nintfill = 0;
2249 	         nbinfill = 0;
2250 	
2251 	         for( ; rowpnt < rowend; rowpnt++ )
2252 	         {
2253 	            if( !(varsprocessed[*rowpnt]) )
2254 	            {
2255 	               int varidx;
2256 	               SCIP_VAR* var;
2257 	
2258 	               varidx = *rowpnt;
2259 	               var = SCIPmatrixGetVar(matrix, varidx);
2260 	
2261 	               /* we search only for dominance relations between the same variable type */
2262 	               if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS )
2263 	               {
2264 	                  consearchcols[nconfill++] = varidx;
2265 	               }
2266 	               else if( SCIPvarIsBinary(var) )
2267 	               {
2268 	                  binsearchcols[nbinfill++] = varidx;
2269 	               }
2270 	               else
2271 	               {
2272 	                  assert(SCIPvarGetType(var) == SCIP_VARTYPE_INTEGER || SCIPvarGetType(var) == SCIP_VARTYPE_IMPLINT);
2273 	                  intsearchcols[nintfill++] = varidx;
2274 	               }
2275 	            }
2276 	         }
2277 	
2278 	         /* continuous variables */
2279 	         if( nconfill > 1 && presoldata->continuousred )
2280 	         {
2281 	            SCIP_CALL( findDominancePairs(scip, matrix, presoldata, consearchcols, nconfill, FALSE,
2282 	                  varstofix, &nfixings, &ndomrelations, nchgbds) );
2283 	
2284 	            for( v = 0; v < nconfill; ++v )
2285 	               varsprocessed[consearchcols[v]] = TRUE;
2286 	
2287 	            varcount += nconfill;
2288 	         }
2289 	
2290 	         /* integer and impl-integer variables */
2291 	         if( nintfill > 1 )
2292 	         {
2293 	            SCIP_CALL( findDominancePairs(scip, matrix, presoldata, intsearchcols, nintfill, FALSE,
2294 	                  varstofix, &nfixings, &ndomrelations, nchgbds) );
2295 	
2296 	            for( v = 0; v < nintfill; ++v )
2297 	               varsprocessed[intsearchcols[v]] = TRUE;
2298 	
2299 	            varcount += nintfill;
2300 	         }
2301 	
2302 	         /* binary variables */
2303 	         if( nbinfill > 1 )
2304 	         {
2305 	            SCIP_CALL( findDominancePairs(scip, matrix, presoldata, binsearchcols, nbinfill, TRUE,
2306 	                  varstofix, &nfixings, &ndomrelations, nchgbds) );
2307 	
2308 	            for( v = 0; v < nbinfill; ++v )
2309 	               varsprocessed[binsearchcols[v]] = TRUE;
2310 	
2311 	            varcount += nbinfill;
2312 	         }
2313 	
2314 	         if( varcount >= ncols )
2315 	            break;
2316 	      }
2317 	   }
2318 	
2319 	   if( nfixings > 0 )
2320 	   {
2321 	      int oldnfixedvars;
2322 	
2323 	      oldnfixedvars = *nfixedvars;
2324 	
2325 	      for( v = ncols - 1; v >= 0; --v )
2326 	      {
2327 	         SCIP_Bool fixed;
2328 	         SCIP_VAR* var;
2329 	
2330 	         var = SCIPmatrixGetVar(matrix,v);
2331 	
2332 	         /* there should be no fixings for variables with lock conflicts,
2333 	            * since they where marked as processed and therefore should be skipped
2334 	            */
2335 	         assert(varstofix[v] == NOFIX || (!SCIPmatrixUplockConflict(matrix, v) && !SCIPmatrixDownlockConflict(matrix, v)) );
2336 	
2337 	         if( varstofix[v] == FIXATLB )
2338 	         {
2339 	            SCIP_Real lb;
2340 	
2341 	            lb = SCIPvarGetLbGlobal(var);
2342 	            assert(SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS || SCIPisFeasIntegral(scip, lb));
2343 	
2344 	            /* fix at lower bound */
2345 	            SCIP_CALL( SCIPfixVar(scip, var, lb, &infeasible, &fixed) );
2346 	            if( infeasible )
2347 	            {
2348 	               SCIPdebugMsg(scip, " -> infeasible fixing\n");
2349 	               *result = SCIP_CUTOFF;
2350 	
2351 	               break;
2352 	            }
2353 	            assert(fixed);
2354 	            (*nfixedvars)++;
2355 	
2356 	#ifdef SCIP_DEBUG
2357 	            if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS )
2358 	               nconvarsfixed++;
2359 	            else if( SCIPvarIsBinary(var) )
2360 	               nbinvarsfixed++;
2361 	            else
2362 	               nintvarsfixed++;
2363 	#endif
2364 	         }
2365 	         else if( varstofix[v] == FIXATUB )
2366 	         {
2367 	            SCIP_Real ub;
2368 	
2369 	            ub = SCIPvarGetUbGlobal(var);
2370 	            assert(SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS || SCIPisFeasIntegral(scip, ub));
2371 	
2372 	            /* fix at upper bound */
2373 	            SCIP_CALL( SCIPfixVar(scip, var, ub, &infeasible, &fixed) );
2374 	            if( infeasible )
2375 	            {
2376 	               SCIPdebugMsg(scip, " -> infeasible fixing\n");
2377 	               *result = SCIP_CUTOFF;
2378 	
2379 	               break;
2380 	            }
2381 	            assert(fixed);
2382 	            (*nfixedvars)++;
2383 	
2384 	#ifdef SCIP_DEBUG
2385 	            if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS )
2386 	               nconvarsfixed++;
2387 	            else if( SCIPvarIsBinary(var) )
2388 	               nbinvarsfixed++;
2389 	            else
2390 	               nintvarsfixed++;
2391 	#endif
2392 	         }
2393 	      }
2394 	
2395 	      if( *result != SCIP_CUTOFF && *nfixedvars > oldnfixedvars )
2396 	         *result = SCIP_SUCCESS;
2397 	   }
2398 	
2399 	   SCIPfreeBufferArray(scip, &varineq);
2400 	   SCIPfreeBufferArray(scip, &colidx);
2401 	   SCIPfreeBufferArray(scip, &pclass);
2402 	   SCIPfreeBufferArray(scip, &rowsparsity);
2403 	   SCIPfreeBufferArray(scip, &rowidxsorted);
2404 	   SCIPfreeBufferArray(scip, &binsearchcols);
2405 	   SCIPfreeBufferArray(scip, &intsearchcols);
2406 	   SCIPfreeBufferArray(scip, &consearchcols);
2407 	   SCIPfreeBufferArray(scip, &varsprocessed);
2408 	   SCIPfreeBufferArray(scip, &varstofix);
2409 	
2410 	#ifdef SCIP_DEBUG
2411 	   if( (nconvarsfixed + nintvarsfixed + nbinvarsfixed) > 0 )
2412 	   {
2413 	      SCIPdebugMsg(scip, "### %d vars [%" SCIP_LONGINT_FORMAT " dom] => fixed [cont: %d, int: %d, bin: %d], %scutoff detected\n",
2414 	         ncols, ndomrelations, nconvarsfixed, nintvarsfixed, nbinvarsfixed, (*result != SCIP_CUTOFF) ? "no " : "");
2415 	   }
2416 	#endif
2417 	
2418 	   SCIPmatrixFree(scip, &matrix);
2419 	
2420 	   return SCIP_OKAY;
2421 	}
2422 	
2423 	/*
2424 	 * presolver specific interface methods
2425 	 */
2426 	
2427 	/** creates the domcol presolver and includes it in SCIP */
2428 	SCIP_RETCODE SCIPincludePresolDomcol(
2429 	   SCIP*                 scip                /**< SCIP data structure */
2430 	   )
2431 	{
2432 	   SCIP_PRESOLDATA* presoldata;
2433 	   SCIP_PRESOL* presol;
2434 	
2435 	   /* create domcol presolver data */
2436 	   SCIP_CALL( SCIPallocBlockMemory(scip, &presoldata) );
2437 	
2438 	   /* include presolver */
2439 	   SCIP_CALL( SCIPincludePresolBasic(scip, &presol, PRESOL_NAME, PRESOL_DESC, PRESOL_PRIORITY, PRESOL_MAXROUNDS,
2440 	         PRESOL_TIMING, presolExecDomcol, presoldata) );
2441 	   SCIP_CALL( SCIPsetPresolCopy(scip, presol, presolCopyDomcol) );
2442 	   SCIP_CALL( SCIPsetPresolFree(scip, presol, presolFreeDomcol) );
2443 	
2444 	   SCIP_CALL( SCIPaddIntParam(scip,
2445 	         "presolving/domcol/numminpairs",
2446 	         "minimal number of pair comparisons",
2447 	         &presoldata->numminpairs, FALSE, DEFAULT_NUMMINPAIRS, 100, DEFAULT_NUMMAXPAIRS, NULL, NULL) );
2448 	
2449 	   SCIP_CALL( SCIPaddIntParam(scip,
2450 	         "presolving/domcol/nummaxpairs",
2451 	         "maximal number of pair comparisons",
2452 	         &presoldata->nummaxpairs, FALSE, DEFAULT_NUMMAXPAIRS, DEFAULT_NUMMINPAIRS, 1000000000, NULL, NULL) );
2453 	
2454 	   SCIP_CALL( SCIPaddBoolParam(scip,
2455 	         "presolving/domcol/predbndstr",
2456 	         "should predictive bound strengthening be applied?",
2457 	         &presoldata->predbndstr, FALSE, DEFAULT_PREDBNDSTR, NULL, NULL) );
2458 	
2459 	   SCIP_CALL( SCIPaddBoolParam(scip,
2460 	         "presolving/domcol/continuousred",
2461 	         "should reductions for continuous variables be performed?",
2462 	         &presoldata->continuousred, FALSE, DEFAULT_CONTINUOUS_RED, NULL, NULL) );
2463 	
2464 	   return SCIP_OKAY;
2465 	}
2466