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_tworowbnd.c
26   	 * @ingroup DEFPLUGINS_PRESOL
27   	 * @brief  do bound tightening by using two rows
28   	 * @author Dieter Weninger
29   	 * @author Patrick Gemander
30   	 *
31   	 * Perform bound tightening on two inequalities with some common variables.
32   	 * Two possible methods are being used.
33   	 *
34   	 * 1. LP-bound
35   	 * Let two constraints be given:
36   	 * \f{eqnarray*}{
37   	 *   A_{iR} x_R + A_{iS} x_S              \geq b_i\\
38   	 *   A_{kR} x_R              + A_{kT} x_T \geq b_k
39   	 * \f}
40   	 * with \f$N\f$ the set of variable indexes, \f$R \subseteq N\f$, \f$S \subseteq N\f$, \f$T \subseteq N\f$,
41   	 * \f$R \cap S = \emptyset\f$, \f$R \cap T = \emptyset\f$, \f$S \cap T = \emptyset\f$ and row indices \f$i \not= k\f$.
42   	 *
43   	 * Let \f$\ell\f$ and \f$u\f$ be bound vectors for x and solve the following two LPs
44   	 * \f{eqnarray*}{
45   	 *   L = \min \{ A_{kR} x_R : A_{iR} x_R + A_{iS} x_S \geq b_i, \ell \leq x \leq u \}\\
46   	 *   U = \max \{ A_{kR} x_R : A_{iR} x_R + A_{iS} x_S \geq b_i, \ell \leq x \leq u \}
47   	 * \f}
48   	 * and use \f$L\f$ and \f$U\f$ for getting bounds on \f$x_T\f$.
49   	 *
50   	 * If \f$L + \mbox{infimum}(A_{kT}x_T) \geq b_k\f$, then the second constraint above is redundant.
51   	 *
52   	 * More details can be found in
53   	 * - Chen W. et. al "Two-row and two-column mixed-integer presolve using hashing-based pairing methods"
54   	 */
55   	
56   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
57   	
58   	/*
59   	 * Additional debug defines in this presolver
60   	 * SCIP_DEBUG_HASHING
61   	 * SCIP_DEBUG_BOUNDS
62   	 * SCIP_DEBUG_SINGLEROWLP
63   	 */
64   	
65   	#include <assert.h>
66   	
67   	#include "scip/cons_linear.h"
68   	#include "scip/scipdefplugins.h"
69   	#include "scip/pub_matrix.h"
70   	#include "scip/presol_tworowbnd.h"
71   	#include <string.h>
72   	
73   	#define PRESOL_NAME                    "tworowbnd"
74   	#define PRESOL_DESC                    "do bound tigthening by using two rows"
75   	#define PRESOL_PRIORITY                -2000    /**< priority of the presolver (>= 0: before, < 0: after constraint handlers); combined with propagators */
76   	#define PRESOL_MAXROUNDS               0        /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
77   	#define PRESOL_TIMING                  SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */
78   	
79   	#define DEFAULT_ENABLECOPY             TRUE     /**< should tworowbnd presolver be copied to sub-SCIPs? */
80   	#define DEFAULT_MAXCONSIDEREDNONZEROS  100      /**< maximal number of considered non-zeros within one row (-1: no limit) */
81   	#define DEFAULT_MAXRETRIEVEFAILS       1000     /**< maximal number of consecutive useless hashtable retrieves */
82   	#define DEFAULT_MAXCOMBINEFAILS        1000     /**< maximal number of consecutive useless row combines */
83   	#define DEFAULT_MAXHASHFAC             10       /**< maximal number of hashlist entries as multiple of number of rows in the problem (-1: no limit) */
84   	#define DEFAULT_MAXPAIRFAC             1        /**< maximal number of processed row pairs as multiple of the number of rows in the problem (-1: no limit) */
85   	
86   	/*
87   	 * Data structures
88   	 */
89   	
90   	/** presolver data */
91   	struct SCIP_PresolData
92   	{
93   	   int maxpairfac;            /**< maximal number of processed row pairs as multiple of the number of rows in the problem (-1: no limit) */
94   	   int maxhashfac;            /**< maximal number of hashlist entries as multiple of number of rows in the problem (-1: no limit) */
95   	   int maxretrievefails;      /**< maximal number of consecutive useless hashtable retrieves */
96   	   int maxcombinefails;       /**< maximal number of consecutive useless row combines */
97   	   int maxconsiderednonzeros; /**< maximal number of considered non-zeros within one row (-1: no limit) */
98   	   int nchgbnds;              /**< number of variable bounds changed by this presolver */
99   	   int nuselessruns;          /**< number of runs where this presolver did not apply any changes */
100  	   SCIP_Bool enablecopy;      /**< should tworowbnd presolver be copied to sub-SCIPs? */
101  	};
102  	
103  	/** structure representing a pair of row indices; used for lookup in a hashtable */
104  	struct RowPair
105  	{
106  	   int row1idx;               /**< first row index */
107  	   int row2idx;               /**< second row index */
108  	};
109  	
110  	typedef struct RowPair ROWPAIR;
111  	
112  	
113  	/*
114  	 * Local methods
115  	 */
116  	
117  	/** encode contents of a rowpair as void* pointer */
118  	static
119  	void* encodeRowPair(
120  	   ROWPAIR*              rowpair             /**< pointer to rowpair */
121  	   )
122  	{
123  	  uint64_t a = (uint64_t)(long)rowpair->row1idx;
124  	  uint64_t b = (uint64_t)(long)rowpair->row2idx;
125  	   return (void*)((a << 32) | b);
126  	}
127  	
128  	/** compute single positive int hashvalue for two ints */
129  	static
130  	int hashIndexPair(
131  	   int                   idx1,               /**< first integer index */
132  	   int                   idx2                /**< second integer index */
133  	   )
134  	{
135  	   uint32_t hash = SCIPhashTwo(idx1, idx2);
136  	   return (int)(hash >> 1);
137  	}
138  	
139  	/** add hash/rowidx pair to hashlist/rowidxlist */
140  	static
141  	SCIP_RETCODE addEntry(
142  	   SCIP*                 scip,               /**< SCIP datastructure */
143  	   int*                  pos,                /**< position of last entry added */
144  	   int*                  listsize,           /**< size of hashlist and rowidxlist */
145  	   int**                 hashlist,           /**< block memory array containing hashes */
146  	   int**                 rowidxlist,         /**< block memory array containing row indices */
147  	   int                   hash,               /**< hash to be inserted */
148  	   int                   rowidx              /**< row index to be inserted */
149  	   )
150  	{
151  	   if( (*pos) >= (*listsize) )
152  	   {
153  	      int newsize  = SCIPcalcMemGrowSize(scip, (*pos) + 1);
154  	      SCIP_CALL( SCIPreallocBlockMemoryArray(scip, hashlist, (*listsize), newsize) );
155  	      SCIP_CALL( SCIPreallocBlockMemoryArray(scip, rowidxlist, (*listsize), newsize) );
156  	      (*listsize) = newsize;
157  	   }
158  	
159  	   (*hashlist)[(*pos)] = hash;
160  	   (*rowidxlist)[(*pos)] = rowidx;
161  	   (*pos)++;
162  	
163  	   return SCIP_OKAY;
164  	}
165  	
166  	/*  Within a sorted list, get next block with same value
167  	 *  E.g. for [h1, h1, h1, h2, h2, h2, h2, h3,...] and end = 0
168  	 *  returns start = 0, end = 3
169  	 *  and on a second call with end = 3 on the same list
170  	 *  returns start = 3, end = 7.
171  	 */
172  	static
173  	void findNextBlock(
174  	   int*                  list,               /**< list of integers */
175  	   int                   len,                /**< length of list */
176  	   int*                  start,              /**< variable to contain start index of found block */
177  	   int*                  end                 /**< variable to contain end index of found block */
178  	   )
179  	{
180  	   int i;
181  	   (*start) = (*end);
182  	   i = (*end) + 1;
183  	   while( i < len && list[i] == list[i - 1] )
184  	      i++;
185  	
186  	   (*end) = i;
187  	}
188  	
189  	/*  Solve single-row LP of the form
190  	 *  min c^T x
191  	 *  s.t. a^T x >= b
192  	 *  lbs <= x <= ubs
193  	 *
194  	 *  First, the problem is transformed such that
195  	 *  SCIPselectWeightedReal() can be applied, which
196  	 *  then solves the problem as a continuous knapsack
197  	 *  in linear time.
198  	 */
199  	static
200  	SCIP_RETCODE solveSingleRowLP(
201  	   SCIP*                 scip,               /**< SCIP data structure */
202  	   SCIP_Real*            a,                  /**< constraint coefficients */
203  	   SCIP_Real             b,                  /**< right hand side */
204  	   SCIP_Real*            c,                  /**< objective coefficients */
205  	   SCIP_Real*            lbs,                /**< lower variable bounds */
206  	   SCIP_Real*            ubs,                /**< upper variable bounds */
207  	   int                   len,                /**< length of arrays */
208  	   SCIP_Real*            obj,                /**< objective value of solution */
209  	   SCIP_Bool*            solvable            /**< status whether LP was solvable */
210  	   )
211  	{
212  	   int i;
213  	   int k;
214  	   int nvars;
215  	   SCIP_Real lb;
216  	   SCIP_Real ub;
217  	   SCIP_Real mincost;
218  	   SCIP_Real maxgain;
219  	
220  	#ifdef SCIP_DEBUG_SINGLEROWLP
221  	   SCIPdebugMsg(scip, "solving single row LP with %d variables\n", len);
222  	#endif
223  	
224  	   nvars = 0;
225  	   (*obj) = 0;
226  	   (*solvable) = TRUE;
227  	   mincost = SCIPinfinity(scip);
228  	   maxgain = 0;
229  	   for( i = 0; i < len; i++)
230  	   {
231  	      /* Handle variables with zero weight */
232  	      if( SCIPisZero(scip, a[i]) )
233  	      {
234  	         /* a[i] = 0, c[i] > 0 */
235  	         if( SCIPisPositive(scip, c[i]) )
236  	         {
237  	            if( SCIPisInfinity(scip, -lbs[i]) )
238  	            {
239  	               (*solvable) = FALSE;
240  	               return SCIP_OKAY;
241  	            }
242  	            else
243  	               (*obj) += c[i] * lbs[i];
244  	         }
245  	         /* a[i] = 0, c[i] < 0 */
246  	         else if( SCIPisNegative(scip, c[i]) )
247  	         {
248  	            if( SCIPisInfinity(scip, ubs[i]) )
249  	            {
250  	               (*solvable) = FALSE;
251  	               return SCIP_OKAY;
252  	            }
253  	            else
254  	               (*obj) += c[i] * ubs[i];
255  	         }
256  	         /* Note that variables with a[i] = 0, c[i] = 0 can be ignored */
257  	         continue;
258  	      }
259  	
260  	      /* Handle free variables */
261  	      if( SCIPisInfinity(scip, -lbs[i]) && SCIPisInfinity(scip, ubs[i]) )
262  	      {
263  	         /* The problem is unbounded */
264  	         if( (SCIPisPositive(scip, c[i]) && SCIPisNegative(scip, a[i])) ||
265  	             (SCIPisNegative(scip, c[i]) && SCIPisPositive(scip, a[i])) )
266  	         {
267  	            (*solvable) = FALSE;
268  	            return SCIP_OKAY;
269  	         }
270  	         else
271  	         {
272  	            mincost = MIN(mincost, c[i] / a[i]);
273  	            maxgain = MAX(maxgain, c[i] / a[i]);
274  	         }
275  	         continue;
276  	      }
277  	
278  	      /* Swap variable orientation if lower bound is infinite */
279  	      if( SCIPisInfinity(scip, -lbs[i]) )
280  	      {
281  	         c[i] = -c[i];
282  	         a[i] = -a[i];
283  	         lb = -ubs[i];
284  	         ub = -lbs[i];
285  	      }
286  	      else
287  	      {
288  	         lb = lbs[i];
289  	         ub = ubs[i];
290  	      }
291  	
292  	      /* Handle variables with infinite upper bound */
293  	      if( SCIPisInfinity(scip, ub) )
294  	      {
295  	         if( SCIPisPositive(scip, a[i]) )
296  	         {
297  	            /* a[i] > 0, c[i] >= 0 */
298  	            if( !SCIPisNegative(scip, c[i]) )
299  	            {
300  	               mincost = MIN(mincost, c[i]/a[i]);
301  	            }
302  	            /* a[i] > 0, c[i] < 0 */
303  	            else
304  	            {
305  	               (*solvable) = FALSE;
306  	               return SCIP_OKAY;
307  	            }
308  	         }
309  	         /* a[i] < 0, c[i] < 0 */
310  	         else if( SCIPisNegative(scip, c[i]) )
311  	         {
312  	            maxgain = MAX(maxgain, c[i] / a[i]);
313  	         }
314  	         /* a[i] < 0, c[i] >= 0 results in dual fixing of this variable, which is included in the bound shift below */
315  	
316  	         /* Shift lower bound to zero */
317  	         if( !SCIPisZero(scip, lb) )
318  	         {
319  	            (*obj) += c[i] * lb;
320  	            b -= a[i] * lb;
321  	         }
322  	         continue;
323  	      }
324  	
325  	      /* Handle fixed variables */
326  	      if( SCIPisEQ(scip, lb, ub) )
327  	      {
328  	         (*obj) += c[i] * lb;
329  	         b -= a[i] * lb;
330  	         continue;
331  	      }
332  	
333  	      /* Dual fixing for variables with finite bounds */
334  	      if( !SCIPisNegative(scip, c[i]) && SCIPisNegative(scip, a[i]) )
335  	      {
336  	         (*obj) += c[i] * lb;
337  	         b -= a[i] * lb;
338  	         continue;
339  	      }
340  	      else if( !SCIPisPositive(scip, c[i]) && SCIPisPositive(scip, a[i]) )
341  	      {
342  	         (*obj) += c[i] * ub;
343  	         b -= a[i] * ub;
344  	         continue;
345  	      }
346  	
347  	      assert(!SCIPisInfinity(scip, -lb));
348  	      assert(!SCIPisInfinity(scip, ub));
349  	
350  	      /* At this point the variable has finite bounds and a[i],c[i] are both positive or both negative.
351  	       * Normalize variable such that
352  	       *  1. x_i \in [0,1]
353  	       *  2. a[i] > 0
354  	       *  3. c[i] >= 0
355  	       * and calculate its "unit price" c[i]/a[i].
356  	       */
357  	      if( SCIPisNegative(scip, a[i]) )
358  	      {
359  	         c[i] = -c[i];
360  	         a[i] = -a[i];
361  	         lb = -ubs[i];
362  	         ub = -lbs[i];
363  	      }
364  	
365  	      /* All variables with a <= 0 have been handled and variables with a[i] = 0, c[i] = 0 ignored */
366  	      assert(SCIPisPositive(scip, a[i]) && SCIPisPositive(scip, c[i]));
367  	
368  	      /* Adjust objective offset and b to shift lower bound to zero */
369  	      (*obj) += c[i] * lb;
370  	      b -= a[i] * lb;
371  	
372  	      /* Calculate unit price */
373  	      c[nvars] = c[i] / a[i];
374  	
375  	      /* Normalize bound [0, ub] to [0,1] */
376  	      a[nvars] = (ub - lb) * a[i];
377  	      nvars++;
378  	   }
379  	
380  	#ifdef SCIP_DEBUG_SINGLEROWLP
381  	   SCIPdebugMsg(scip, "After preprocessing: obj = %g, b = %g, nvars = %d, mincost = %g, maxgain = %g\n", (*obj), b, nvars, mincost, maxgain);
382  	#endif
383  	
384  	   /* Actual solving starts here.
385  	    * If maxgain > 0 holds, we have a variable that can relax the constraint to an arbitrary degree while yielding
386  	    * a certain profit per unit. This will be called downslack. If mincost < inf holds, we have a variable that can
387  	    * always satisfy the constraint at a certain unit price. This will be called upslack.
388  	    */
389  	
390  	   /* Problem is unbounded since the downslack variable yields higher gains than the upslack variable costs */
391  	   if( SCIPisLT(scip, mincost, maxgain) )
392  	   {
393  	      (*solvable) = FALSE;
394  	      return SCIP_OKAY;
395  	   }
396  	   /* Solution is trivial as we have slack variables of equal price for both directions */
397  	   else if( SCIPisEQ(scip, mincost, maxgain) )
398  	   {
399  	      /* Use all elements with cost smaller than maxgain */
400  	      for( i = 0; i < nvars; i++ )
401  	      {
402  	         if( SCIPisLT(scip, c[i], maxgain) )
403  	         {
404  	            (*obj) += c[i] * a[i];
405  	            b -= a[i];
406  	         }
407  	      }
408  	      /* Use slack variable to satisfy constraint */
409  	      (*obj) += mincost * b;
410  	      return SCIP_OKAY;
411  	   }
412  	   /* mincost > maxgain
413  	    * In this case we need to solve the problem for the remaining variables with mincost > c[i] > maxgain.
414  	    */
415  	   else
416  	   {
417  	      /* Only keep variables that are cheaper than the upslack variable */
418  	      if( !SCIPisInfinity(scip, mincost) )
419  	      {
420  	         k = 0;
421  	         for( i = 0; i < nvars; i++ )
422  	         {
423  	            if( SCIPisLT(scip, c[i], mincost) )
424  	            {
425  	               c[k] = c[i];
426  	               a[k] = a[i];
427  	               k++;
428  	            }
429  	         }
430  	         nvars = k;
431  	      }
432  	
433  	      /* Exploit all variables that are cheaper than the downslack variable */
434  	      if( !SCIPisZero(scip, maxgain) )
435  	      {
436  	         k = 0;
437  	         for( i = 0; i < nvars; i++ )
438  	         {
439  	            if( SCIPisLE(scip, c[i], maxgain) )
440  	            {
441  	               (*obj) += c[i] * a[i];
442  	               b -= a[i];
443  	            }
444  	            else
445  	            {
446  	               c[k] = c[i];
447  	               a[k] = a[i];
448  	               k++;
449  	            }
450  	         }
451  	         if( !SCIPisPositive(scip, b) )
452  	         {
453  	            (*obj) += maxgain * b;
454  	            return SCIP_OKAY;
455  	         }
456  	         nvars = k;
457  	      }
458  	
459  	#ifdef SCIP_DEBUG_SINGLEROWLP
460  	      SCIPdebugMsg(scip, "After exploiting slacks: obj = %g, nvars = %d\n", (*obj), nvars);
461  	#endif
462  	
463  	      /* If there are no variables left we can trivially put together a solution or determine infeasibility */
464  	      if( nvars == 0 )
465  	      {
466  	         if( !SCIPisInfinity(scip, mincost) )
467  	         {
468  	            (*obj) += mincost * b;
469  	            return SCIP_OKAY;
470  	         }
471  	         else
472  	         {
473  	            (*solvable) = FALSE;
474  	            return SCIP_OKAY;
475  	         }
476  	      }
477  	      /* Solve the remaining part of the problem */
478  	      else
479  	      {
480  	         assert(nvars > 0);
481  	#ifdef SCIP_DEBUG_SINGLEROWLP
482  	         for( i = 0; i < nvars; i++ )
483  	            SCIPdebugMsg(scip, "c[%d] = %g, a[%d] = %g\n", i, c[i], i, a[i]);
484  	#endif
485  	
486  	         SCIPselectWeightedReal(c, a, b, nvars, &k);
487  	
488  	#ifdef SCIP_DEBUG_SINGLEROWLP
489  	         SCIPdebugMsg(scip, "k-mean = %g at index %d\n", c[k], k, b);
490  	         for( i = 0; i < nvars; i++ )
491  	            SCIPdebugMsg(scip, "c[%d] = %g, a[%d] = %g\n", i, c[i], i, a[i]);
492  	#endif
493  	
494  	         /* Finalize objective value of solution. First we use all elements cheaper than the k-median */
495  	         for( i = 0; i < k; i++ )
496  	         {
497  	            (*obj) += c[i] * a[i];
498  	            b -= a[i];
499  	         }
500  	
501  	#ifdef SCIP_DEBUG_SINGLEROWLP
502  	         SCIPdebugMsg(scip, "LP is solved: b = %g\n", b);
503  	#endif
504  	
505  	         /* If the constraint is not yet satisfied, we have to fix that */
506  	         if( SCIPisPositive(scip, b) )
507  	         {
508  	            /* There exists an element to satisfy the constraint */
509  	            if( k < nvars )
510  	            {
511  	               (*obj) += c[k] * b;
512  	               return SCIP_OKAY;
513  	            }
514  	            /* There is an upslack variable to satisfy the constraint */
515  	            else if( !SCIPisInfinity(scip, mincost) )
516  	            {
517  	#ifdef SCIP_DEBUG_SINGLEROWLP
518  	               SCIPdebugMsg(scip, "We use %g units of upslack to satisfy the constraint\n", b);
519  	#endif
520  	               (*obj) += mincost * b;
521  	               return SCIP_OKAY;
522  	            }
523  	            /* We cannot satisfy the constraint so the problem is infeasible */
524  	            else
525  	            {
526  	               (*solvable) = FALSE;
527  	               return SCIP_OKAY;
528  	            }
529  	         }
530  	         /* The constraint is already satisfied, i.e. b <= 0 */
531  	         else
532  	         {
533  	            return SCIP_OKAY;
534  	         }
535  	      }
536  	   }
537  	}
538  	
539  	/** Transform rows into single row LPs, solve them and and tighten bounds
540  	 *
541  	 *  During transformation, create coefficient arrays where variables with a zero coefficient in both rows are ignored
542  	 *  and bring the LP in the form min c^T x, s.t. a^T x >= b, lbs <= x <= ubs.
543  	 *  These LPs are then solved and bounds tightened as described in LP-bound (see above).
544  	 */
545  	static
546  	SCIP_RETCODE transformAndSolve(
547  	   SCIP*                 scip,               /**< SCIP data structure */
548  	   SCIP_MATRIX*          matrix,             /**< constraint matrix object, rows specified by row1idx/row2idx must be sorted */
549  	   int                   row1idx,            /**< index of first row */
550  	   int                   row2idx,            /**< index of second row */
551  	   SCIP_Bool             swaprow1,           /**< should row1 <= rhs be used in addition to lhs <= row1 */
552  	   SCIP_Bool             swaprow2,           /**< should row2 <= rhs be used in addition to lhs <= row2 */
553  	   SCIP_Real*            aoriginal,          /**< buffer array for original constraint coefficients */
554  	   SCIP_Real*            acopy,              /**< buffer array for coefficients adjusted to single-row LP to be solved */
555  	   SCIP_Real*            coriginal,          /**< buffer array for original objective coefficients */
556  	   SCIP_Real*            ccopy,              /**< buffer array for coefficients adjusted to single-row LP to be solved */
557  	   SCIP_Bool*            cangetbnd,          /**< buffer array for flags of which variables a bound can be generated */
558  	   SCIP_Real*            lbs,                /**< buffer array for lower bounds for single-row LP */
559  	   SCIP_Real*            ubs,                /**< buffer array for upper bounds for single-row LP */
560  	   SCIP_Real*            newlbsoriginal,     /**< buffer array for new lower bounds not adjusted to individual single-row LPs */
561  	   SCIP_Real*            newlbscopy,         /**< buffer array for adjusted lower bounds */
562  	   SCIP_Real*            newubsoriginal,     /**< buffer array for new upper bounds not adjusted to individual single-row LPs */
563  	   SCIP_Real*            newubscopy,         /**< buffer array for adjusted upper bounds */
564  	   SCIP_Bool*            success,            /**< return (success || "found better bounds") */
565  	   SCIP_Bool*            infeasible          /**< we return (infeasible || "detected infeasibility") */
566  	   )
567  	{
568  	   int i;
569  	   int j;
570  	   int idx1;
571  	   int idx2;
572  	   int row1len;
573  	   int row2len;
574  	   int* row1idxptr;
575  	   int* row2idxptr;
576  	   SCIP_Real* row1valptr;
577  	   SCIP_Real* row2valptr;
578  	   int nvars;
579  	   SCIP_Real minact;
580  	   SCIP_Real maxact;
581  	   int maxinfs;
582  	   int mininfs;
583  	
584  	   SCIP_Bool minsolvable;
585  	   SCIP_Real minobj = SCIP_INVALID;
586  	   SCIP_Bool maxsolvable;
587  	   SCIP_Real maxobj;
588  	   SCIP_Bool minswapsolvable;
589  	   SCIP_Real minswapobj = 0.0;
590  	   SCIP_Bool maxswapsolvable;
591  	   SCIP_Real maxswapobj;
592  	
593  	   SCIP_Real newbnd;
594  	
595  	   assert(!swaprow1 || (swaprow1 && !SCIPisInfinity(scip, SCIPmatrixGetRowRhs(matrix, row1idx))));
596  	   assert(!swaprow2 || (swaprow2 && !SCIPisInfinity(scip, SCIPmatrixGetRowRhs(matrix, row2idx))));
597  	
598  	   row1len = SCIPmatrixGetRowNNonzs(matrix, row1idx);
599  	   row2len = SCIPmatrixGetRowNNonzs(matrix, row2idx);
600  	   row1idxptr = SCIPmatrixGetRowIdxPtr(matrix, row1idx);
601  	   row2idxptr = SCIPmatrixGetRowIdxPtr(matrix, row2idx);
602  	   row1valptr = SCIPmatrixGetRowValPtr(matrix, row1idx);
603  	   row2valptr = SCIPmatrixGetRowValPtr(matrix, row2idx);
604  	
605  	   /*  Preprocess rows:
606  	    *  1. Calculate minimal and maximal activity of variables not appearing in both rows,
607  	    *     as this represents the right-hand sides of the single-row LPs to be solved.
608  	    *  2. Transform rows into format required by solveSingleRowLP where
609  	    *     first row represents the objective vector c and second row represents the constraint vector a.
610  	    *  3. Determine for which variables new bounds can be calculated.
611  	    */
612  	   i = 0;
613  	   j = 0;
614  	   nvars = 0;
615  	   mininfs = 0;
616  	   maxinfs = 0;
617  	   minact = 0;
618  	   maxact = 0;
619  	   while( i < row1len && j < row2len )
620  	   {
621  	      idx1 = row1idxptr[i];
622  	      idx2 = row2idxptr[j];
623  	
624  	      if( idx1 == idx2 )
625  	      {
626  	         coriginal[nvars] = row1valptr[i];
627  	         aoriginal[nvars] = row2valptr[j];
628  	         newlbsoriginal[nvars] = lbs[idx1];
629  	         newubsoriginal[nvars] = ubs[idx1];
630  	         cangetbnd[idx1] = FALSE;
631  	         nvars++;
632  	#ifdef SCIP_DEBUG_2RB
633  	         SCIPdebugMsg(scip, "%g <= (%s) <= %g  has coefs %g and %g, %d LP vars\n",
634  	                      lbs[idx1], SCIPvarGetName(SCIPmatrixGetVar(matrix, idx1)),
635  	                      ubs[idx1], row1valptr[i], row2valptr[j], nvars);
636  	#endif
637  	         i++;
638  	         j++;
639  	      }
640  	      else if( idx1 < idx2 )
641  	      {
642  	         if( SCIPisPositive(scip, row1valptr[i]) )
643  	         {
644  	            if( SCIPisInfinity(scip, ubs[idx1]) )
645  	               maxinfs++;
646  	            else
647  	               maxact -= row1valptr[i] * ubs[idx1];
648  	
649  	            if( SCIPisInfinity(scip, -lbs[idx1]) )
650  	               mininfs++;
651  	            else
652  	               minact -= row1valptr[i] * lbs[idx1];
653  	         }
654  	         else
655  	         {
656  	            if( SCIPisInfinity(scip, -lbs[idx1]) )
657  	               maxinfs++;
658  	            else
659  	               maxact -= row1valptr[i] * lbs[idx1];
660  	
661  	            if( SCIPisInfinity(scip, ubs[idx1]) )
662  	               mininfs++;
663  	            else
664  	               minact -= row1valptr[i] * ubs[idx1];
665  	
666  	            cangetbnd[idx1] = TRUE;
667  	         }
668  	         if( maxinfs > 1 && mininfs > 1 )
669  	         {
670  	            (*success) = FALSE;
671  	            return SCIP_OKAY;
672  	         }
673  	         i++;
674  	#ifdef SCIP_DEBUG_2RB
675  	         SCIPdebugMsg(scip, "%g <= (%s) <= %g has coefs %g and 0.0, minact = %g, maxact = %g\n",
676  	                      lbs[idx1], SCIPvarGetName(SCIPmatrixGetVar(matrix, idx1)),
677  	                      ubs[idx1], row1valptr[i], minact, maxact);
678  	#endif
679  	      }
680  	      else
681  	      {
682  	         coriginal[nvars] = 0.0;
683  	         aoriginal[nvars] = row2valptr[j];
684  	         newlbsoriginal[nvars] = lbs[idx2];
685  	         newubsoriginal[nvars] = ubs[idx2];
686  	         cangetbnd[idx2] = FALSE;
687  	         nvars++;
688  	#ifdef SCIP_DEBUG_2RB
689  	         SCIPdebugMsg(scip, "%g <= (%s) <= %g has coefs 0.0 and %g, %d LP vars\n",
690  	                      lbs[idx2], SCIPvarGetName(SCIPmatrixGetVar(matrix, idx2)),
691  	                      ubs[idx2], row2valptr[j], nvars);
692  	#endif
693  	         j++;
694  	      }
695  	   }
696  	   while( i < row1len )
697  	   {
698  	      idx1 = row1idxptr[i];
699  	      if( SCIPisPositive(scip, row1valptr[i]) )
700  	      {
701  	         if( SCIPisInfinity(scip, ubs[idx1]) )
702  	            maxinfs++;
703  	         else
704  	            maxact -= row1valptr[i] * ubs[idx1];
705  	
706  	         if( SCIPisInfinity(scip, -lbs[idx1]) )
707  	            mininfs++;
708  	         else
709  	            minact -= row1valptr[i] * lbs[idx1];
710  	      }
711  	      else
712  	      {
713  	         if( SCIPisInfinity(scip, -lbs[idx1]) )
714  	            maxinfs++;
715  	         else
716  	            maxact -= row1valptr[i] * lbs[idx1];
717  	
718  	         if( SCIPisInfinity(scip, ubs[idx1]) )
719  	            mininfs++;
720  	         else
721  	            minact -= row1valptr[i] * ubs[idx1];
722  	      }
723  	      cangetbnd[idx1] = TRUE;
724  	#ifdef SCIP_DEBUG_2RB
725  	      SCIPdebugMsg(scip, "%g <= (%s) <= %g  has coefs %g and 0.0, minact = %g, maxact = %g\n",
726  	                   lbs[idx1], SCIPvarGetName(SCIPmatrixGetVar(matrix, idx1)),
727  	                   ubs[idx1], row1valptr[i], minact, maxact);
728  	#endif
729  	      i++;
730  	   }
731  	   while( j < row2len )
732  	   {
733  	      idx2 = row2idxptr[j];
734  	      coriginal[nvars] = 0.0;
735  	      aoriginal[nvars] = row2valptr[j];
736  	      newlbsoriginal[nvars] = lbs[idx2];
737  	      newubsoriginal[nvars] = ubs[idx2];
738  	      nvars++;
739  	#ifdef SCIP_DEBUG_2RB
740  	      SCIPdebugMsg(scip, "%g <= (%s) <= %g has coefs 0.0 and %g, %d LP vars\n",
741  	                   lbs[idx2], SCIPvarGetName(SCIPmatrixGetVar(matrix, idx2)),
742  	                   ubs[idx2], row2valptr[j], nvars);
743  	#endif
744  	      j++;
745  	   }
746  	
747  	#ifdef SCIP_DEBUG_2RB
748  	   SCIPdebugMsg(scip, "right hand sides: %g and %g\n",
749  	                SCIPmatrixGetRowLhs(matrix, row1idx), SCIPmatrixGetRowLhs(matrix, row2idx));
750  	#endif
751  	
752  	   /* solve single-row LPs */
753  	   maxsolvable = FALSE;
754  	   minsolvable = FALSE;
755  	   maxswapsolvable = FALSE;
756  	   minswapsolvable = FALSE;
757  	   /* maximize overlap in first row with lhs <= row2 as constraint */
758  	   if( maxinfs <= 1 )
759  	   {
760  	      for( i = 0; i < nvars; i++ )
761  	      {
762  	         acopy[i] = aoriginal[i];
763  	         ccopy[i] = -coriginal[i];
764  	         newlbscopy[i] = newlbsoriginal[i];
765  	         newubscopy[i] = newubsoriginal[i];
766  	      }
767  	      SCIP_CALL( solveSingleRowLP(scip, acopy, SCIPmatrixGetRowLhs(matrix, row2idx),
768  	                                  ccopy, newlbscopy, newubscopy, nvars, &maxobj, &maxsolvable) );
769  	#ifdef SCIP_DEBUG_2RB
770  	      SCIPdebugMsg(scip, "max-LP solved: obj = %g\n", maxobj);
771  	#endif
772  	   }
773  	
774  	   /* minimize overlap in first row with lhs <= row2 as constraint */
775  	   if( mininfs == 0 || (mininfs == 1 && swaprow1) )
776  	   {
777  	      /* copy coefficients */
778  	      for( i = 0; i < nvars; i++ )
779  	      {
780  	         acopy[i] = aoriginal[i];
781  	         ccopy[i] = coriginal[i];
782  	         newlbscopy[i] = newlbsoriginal[i];
783  	         newubscopy[i] = newubsoriginal[i];
784  	      }
785  	      SCIP_CALL( solveSingleRowLP(scip, acopy, SCIPmatrixGetRowLhs(matrix, row2idx),
786  	                                  ccopy, newlbscopy, newubscopy, nvars, &minobj, &minsolvable) );
787  	#ifdef SCIP_DEBUG_2RB
788  	      SCIPdebugMsg(scip, "min-LP solved: obj = %g\n", minobj);
789  	#endif
790  	   }
791  	
792  	   if( swaprow2 )
793  	   {
794  	     /* maximize overlap in first row with row2 <= rhs as constraint */
795  	      if( maxinfs <= 1 )
796  	      {
797  	         /* copy coefficients */
798  	         for( i = 0; i < nvars; i++ )
799  	         {
800  	            acopy[i] = -aoriginal[i];
801  	            ccopy[i] = -coriginal[i];
802  	            newlbscopy[i] = newlbsoriginal[i];
803  	            newubscopy[i] = newubsoriginal[i];
804  	         }
805  	         SCIP_CALL( solveSingleRowLP(scip, acopy, -SCIPmatrixGetRowRhs(matrix, row2idx),
806  	                                     ccopy, newlbscopy, newubscopy, nvars, &maxswapobj, &maxswapsolvable) );
807  	#ifdef SCIP_DEBUG_2RB
808  	         SCIPdebugMsg(scip, "maxswap-LP solved: obj = %g\n", maxswapobj);
809  	#endif
810  	      }
811  	
812  	      /* minimize overlap in first row with row2 <= rhs as constraint */
813  	      if( mininfs == 0 || (mininfs == 1 && swaprow1) )
814  	      {
815  	         /* copy coefficients */
816  	         for( i = 0; i < nvars; i++ )
817  	         {
818  	            acopy[i] = -aoriginal[i];
819  	            ccopy[i] = coriginal[i];
820  	            newlbscopy[i] = newlbsoriginal[i];
821  	            newubscopy[i] = newubsoriginal[i];
822  	         }
823  	         SCIP_CALL( solveSingleRowLP(scip, acopy, -SCIPmatrixGetRowRhs(matrix, row2idx),
824  	                                     ccopy, newlbscopy, newubscopy, nvars, &minswapobj, &minswapsolvable) );
825  	#ifdef SCIP_DEBUG_2RB
826  	         SCIPdebugMsg(scip, "minswap-LP solved: obj = %g\n", minswapobj);
827  	#endif
828  	      }
829  	   }
830  	
831  	   /* perform bound tightening, infeasibility checks and redundancy checks */
832  	   if( maxinfs <= 1 && (maxsolvable || maxswapsolvable) )
833  	   {
834  	      SCIP_Real activity;
835  	
836  	      if( maxsolvable && maxswapsolvable )
837  	         activity = MAX(maxobj, maxswapobj) + SCIPmatrixGetRowLhs(matrix, row1idx) + maxact; /*lint !e644*/
838  	      else if( maxsolvable )
839  	         activity = maxobj + SCIPmatrixGetRowLhs(matrix, row1idx) + maxact; /*lint !e644*/
840  	      else
841  	         activity = maxswapobj + SCIPmatrixGetRowLhs(matrix, row1idx) + maxact; /*lint !e644*/
842  	
843  	      /* infeasibility check */
844  	      if( maxinfs == 0 && SCIPisPositive(scip, activity) )
845  	      {
846  	         (*infeasible) = TRUE;
847  	         (*success) = TRUE;
848  	         return SCIP_OKAY;
849  	      }
850  	      /* strengthen bounds of all variables outside overlap */
851  	      else if( maxinfs == 0 )
852  	      {
853  	         for( i = 0; i < row1len; i++ )
854  	         {
855  	            idx1 = row1idxptr[i];
856  	            if( cangetbnd[idx1] )
857  	            {
858  	               if( SCIPisPositive(scip, row1valptr[i]) )
859  	               {
860  	                  if( SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_BINARY
861  	                      || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_INTEGER
862  	                      || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_IMPLINT )
863  	                     newbnd = SCIPceil(scip, (activity + row1valptr[i] * ubs[idx1]) / row1valptr[i]);
864  	                  else
865  	                     newbnd = (activity + row1valptr[i] * ubs[idx1]) / row1valptr[i];
866  	
867  	                  if( SCIPisGT(scip, newbnd, lbs[idx1]) )
868  	                  {
869  	#ifdef SCIP_DEBUG_BOUNDS
870  	                     SCIPdebugMsg(scip, "%g <= %g <= %s <= %g\n",
871  	                                  lbs[idx1], newbnd, SCIPmatrixGetColName(matrix, idx1), ubs[idx1]);
872  	#endif
873  	                     lbs[idx1] = newbnd;
874  	                     (*success) = TRUE;
875  	                  }
876  	               }
877  	               else
878  	               {
879  	                  assert(SCIPisNegative(scip, row1valptr[i]));
880  	                  if( SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_BINARY
881  	                      || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_INTEGER
882  	                      || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_IMPLINT )
883  	                     newbnd = SCIPfloor(scip, (activity + row1valptr[i] * lbs[idx1]) / row1valptr[i]);
884  	                  else
885  	                     newbnd = (activity + row1valptr[i] * lbs[idx1]) / row1valptr[i];
886  	
887  	                  if( SCIPisLT(scip, newbnd, ubs[idx1]) )
888  	                  {
889  	#ifdef SCIP_DEBUG_BOUNDS
890  	                     SCIPdebugMsg(scip, "%g <= %s <= %g <= %g\n",
891  	                                  lbs[idx1], SCIPmatrixGetColName(matrix, idx1), newbnd, ubs[idx1]);
892  	#endif
893  	                     ubs[idx1] = newbnd;
894  	                     (*success) = TRUE;
895  	                  }
896  	               }
897  	            }
898  	         }
899  	      }
900  	      /* strengthen bound of the single variable contributing the infinity */
901  	      else
902  	      {
903  	         assert(maxinfs == 1);
904  	         for( i = 0; i < row1len; i++ )
905  	         {
906  	            idx1 = row1idxptr[i];
907  	            if( cangetbnd[idx1] )
908  	            {
909  	               if( SCIPisPositive(scip, row1valptr[i]) && SCIPisInfinity(scip, ubs[idx1]) )
910  	               {
911  	                  if( SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_BINARY
912  	                      || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_INTEGER
913  	                      || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_IMPLINT )
914  	                     newbnd = SCIPceil(scip, activity / row1valptr[i]);
915  	                  else
916  	                     newbnd = activity / row1valptr[i];
917  	
918  	                  if( SCIPisGT(scip, newbnd, lbs[idx1]) )
919  	                  {
920  	#ifdef SCIP_DEBUG_BOUNDS
921  	                     SCIPdebugMsg(scip, "%g <= %g <= %s <= %g\n",
922  	                                  lbs[idx1], newbnd, SCIPmatrixGetColName(matrix, idx1), ubs[idx1]);
923  	#endif
924  	                     lbs[idx1] = newbnd;
925  	                     (*success) = TRUE;
926  	                  }
927  	               }
928  	               else if( SCIPisInfinity(scip, -lbs[idx1]) )
929  	               {
930  	                  assert(SCIPisNegative(scip, row1valptr[i]));
931  	                  if( SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_BINARY
932  	                      || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_INTEGER
933  	                      || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_IMPLINT )
934  	                     newbnd = SCIPfloor(scip, activity / row1valptr[i]);
935  	                  else
936  	                     newbnd = activity / row1valptr[i];
937  	
938  	                  if( SCIPisLT(scip, newbnd, ubs[idx1]) )
939  	                  {
940  	#ifdef SCIP_DEBUG_BOUNDS
941  	                     SCIPdebugMsg(scip, "%g <= %s <= %g <= %g\n",
942  	                                  lbs[idx1], SCIPmatrixGetColName(matrix, idx1), newbnd, ubs[idx1]);
943  	#endif
944  	                     ubs[idx1] = newbnd;
945  	                     (*success) = TRUE;
946  	                  }
947  	               }
948  	            }
949  	         }
950  	      }
951  	   }
952  	
953  	   /* in this case the objective is swapped. therefore the minimum and the maximum of the support switch roles */
954  	   if( swaprow1 )
955  	   {
956  	      /* perform bound tightening, infeasibility checks and redundancy checks */
957  	      if( mininfs <= 1 && (minsolvable || minswapsolvable) )
958  	      {
959  	         SCIP_Real activity;
960  	
961  	         assert(minobj != SCIP_INVALID); /*lint !e777*/
962  	         if( minsolvable && minswapsolvable )
963  	            activity = MAX(minobj, minswapobj) - SCIPmatrixGetRowRhs(matrix, row1idx) - minact;
964  	         else if( minsolvable )
965  	            activity = minobj - SCIPmatrixGetRowRhs(matrix, row1idx) - minact;
966  	         else
967  	            activity = minswapobj - SCIPmatrixGetRowRhs(matrix, row1idx) - minact;
968  	
969  	         /* infeasibility check */
970  	         if( mininfs == 0 && SCIPisPositive(scip, activity) )
971  	         {
972  	            (*infeasible) = TRUE;
973  	            (*success) = TRUE;
974  	            return SCIP_OKAY;
975  	         }
976  	         /* strengthen bounds of all variables outside overlap */
977  	         else if( mininfs == 0 )
978  	         {
979  	            for( i = 0; i < row1len; i++ )
980  	            {
981  	               idx1 = row1idxptr[i];
982  	               if( cangetbnd[idx1] )
983  	               {
984  	                  if( SCIPisNegative(scip, row1valptr[i]) ) /* since we look at the swapped case, this represents a positive coefficient */
985  	                  {
986  	                     if( SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_BINARY
987  	                         || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_INTEGER
988  	                         || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_IMPLINT )
989  	                        newbnd = SCIPceil(scip, (activity - row1valptr[i] * ubs[idx1]) / (-row1valptr[i]));
990  	                     else
991  	                        newbnd = (activity - row1valptr[i] * ubs[idx1]) / (-row1valptr[i]);
992  	
993  	                     if( SCIPisGT(scip, newbnd, lbs[idx1]) )
994  	                     {
995  	#ifdef SCIP_DEBUG_BOUNDS
996  	                        SCIPdebugMsg(scip, "%g <= %g <= %s <= %g\n",
997  	                                     lbs[idx1], newbnd, SCIPmatrixGetColName(matrix, idx1), ubs[idx1]);
998  	#endif
999  	                        lbs[idx1] = newbnd;
1000 	                        (*success) = TRUE;
1001 	                     }
1002 	                  }
1003 	                  else
1004 	                  {
1005 	                     /* since we look at the swapped case, this represents a negative coefficient */
1006 	                     assert(SCIPisPositive(scip, row1valptr[i]));
1007 	                     if( SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_BINARY
1008 	                         || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_INTEGER
1009 	                         || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_IMPLINT )
1010 	                        newbnd = SCIPfloor(scip, (activity - row1valptr[i] * lbs[idx1]) / (-row1valptr[i]));
1011 	                     else
1012 	                        newbnd = (activity - row1valptr[i] * lbs[idx1]) / (-row1valptr[i]);
1013 	
1014 	                     if( SCIPisLT(scip, newbnd, ubs[idx1]) )
1015 	                     {
1016 	#ifdef SCIP_DEBUG_BOUNDS
1017 	                        SCIPdebugMsg(scip, "%g <= %s <= %g <= %g\n",
1018 	                                     lbs[idx1], SCIPmatrixGetColName(matrix, idx1), newbnd, ubs[idx1]);
1019 	#endif
1020 	                        ubs[idx1] = newbnd;
1021 	                        (*success) = TRUE;
1022 	                     }
1023 	                  }
1024 	               }
1025 	            }
1026 	         }
1027 	         /* strengthen bound of the single variable contributing the infinity */
1028 	         else
1029 	         {
1030 	            assert(mininfs == 1);
1031 	            for( i = 0; i < row1len; i++ )
1032 	            {
1033 	               idx1 = row1idxptr[i];
1034 	               if( cangetbnd[idx1] )
1035 	               {
1036 	                  /* since we look at the swapped case, this represents a positive coefficient */
1037 	                  if( SCIPisNegative(scip, row1valptr[i]) && SCIPisInfinity(scip, ubs[idx1]) )
1038 	                  {
1039 	                     if( SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_BINARY
1040 	                         || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_INTEGER
1041 	                         || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_IMPLINT )
1042 	                        newbnd = SCIPceil(scip, activity / (-row1valptr[i]));
1043 	                     else
1044 	                        newbnd = activity / (-row1valptr[i]);
1045 	
1046 	                     if( SCIPisGT(scip, newbnd, lbs[idx1]) )
1047 	                     {
1048 	#ifdef SCIP_DEBUG_BOUNDS
1049 	                        SCIPdebugMsg(scip, "%g <= %g <= %s <= %g\n", lbs[idx1], newbnd, SCIPmatrixGetColName(matrix, idx1), ubs[idx1]);
1050 	#endif
1051 	                        lbs[idx1] = newbnd;
1052 	                        (*success) = TRUE;
1053 	                     }
1054 	                  }
1055 	                  else if( SCIPisInfinity(scip, -lbs[idx1]) )
1056 	                  {
1057 	                     /* since we look at the swapped case, this represents a negative coefficient */
1058 	                     assert(SCIPisPositive(scip, row1valptr[i]));
1059 	                     if( SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_BINARY
1060 	                         || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_INTEGER
1061 	                         || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_IMPLINT )
1062 	                        newbnd = SCIPfloor(scip, activity / (-row1valptr[i]));
1063 	                     else
1064 	                        newbnd = activity / (-row1valptr[i]);
1065 	
1066 	                     if( SCIPisLT(scip, newbnd, ubs[idx1]) )
1067 	                     {
1068 	#ifdef SCIP_DEBUG_BOUNDS
1069 	                        SCIPdebugMsg(scip, "%g <= %s <= %g <= %g\n",
1070 	                                     lbs[idx1], SCIPmatrixGetColName(matrix, idx1), newbnd, ubs[idx1]);
1071 	#endif
1072 	                        ubs[idx1] = newbnd;
1073 	                        (*success) = TRUE;
1074 	                     }
1075 	                  }
1076 	               }
1077 	            }
1078 	         }
1079 	      }
1080 	   }
1081 	
1082 	   return SCIP_OKAY;
1083 	}
1084 	
1085 	/** create required buffer arrays and apply LP-based bound tightening in both directions */
1086 	static
1087 	SCIP_RETCODE applyLPboundTightening(
1088 	   SCIP*                 scip,               /**< SCIP data structure */
1089 	   SCIP_MATRIX*          matrix,             /**< constraint matrix object */
1090 	   int                   row1,               /**< index of first row */
1091 	   int                   row2,               /**< index of seond row */
1092 	   SCIP_Bool             swaprow1,           /**< should row1 <= rhs be used in addition to lhs <= row1 */
1093 	   SCIP_Bool             swaprow2,           /**< should row2 <= rhs be used in addition to lhs <= row2 */
1094 	   SCIP_Real*            lbs,                /**< lower variable bounds */
1095 	   SCIP_Real*            ubs,                /**< upper variable bounds */
1096 	   SCIP_Bool*            success             /**< return (success || "found better bounds") */
1097 	   )
1098 	{
1099 	   SCIP_Real* aoriginal;
1100 	   SCIP_Real* acopy;
1101 	   SCIP_Real* coriginal;
1102 	   SCIP_Real* ccopy;
1103 	   SCIP_Real* newlbsoriginal;
1104 	   SCIP_Real* newlbscopy;
1105 	   SCIP_Real* newubsoriginal;
1106 	   SCIP_Real* newubscopy;
1107 	   SCIP_Bool* cangetbnd;
1108 	   SCIP_Bool infeasible;
1109 	
1110 	#ifdef SCIP_DEBUG_2RB
1111 	   SCIPdebugMsg(scip, "combining rows %d (%s) and %d (%s)\n",
1112 	                row1, SCIPmatrixGetRowName(matrix, row1), row2, SCIPmatrixGetRowName(matrix, row2));
1113 	#endif
1114 	
1115 	   SCIP_CALL( SCIPallocBufferArray(scip, &aoriginal, SCIPmatrixGetNColumns(matrix)) );
1116 	   SCIP_CALL( SCIPallocBufferArray(scip, &acopy, SCIPmatrixGetNColumns(matrix)) );
1117 	   SCIP_CALL( SCIPallocBufferArray(scip, &coriginal, SCIPmatrixGetNColumns(matrix)) );
1118 	   SCIP_CALL( SCIPallocBufferArray(scip, &ccopy, SCIPmatrixGetNColumns(matrix)) );
1119 	   SCIP_CALL( SCIPallocBufferArray(scip, &newlbsoriginal, SCIPmatrixGetNColumns(matrix)) );
1120 	   SCIP_CALL( SCIPallocBufferArray(scip, &newlbscopy, SCIPmatrixGetNColumns(matrix)) );
1121 	   SCIP_CALL( SCIPallocBufferArray(scip, &newubsoriginal, SCIPmatrixGetNColumns(matrix)) );
1122 	   SCIP_CALL( SCIPallocBufferArray(scip, &newubscopy, SCIPmatrixGetNColumns(matrix)) );
1123 	   SCIP_CALL( SCIPallocBufferArray(scip, &cangetbnd, SCIPmatrixGetNColumns(matrix)) );
1124 	
1125 	   /* Sort matrix rows */
1126 	   SCIPsortIntReal(SCIPmatrixGetRowIdxPtr(matrix, row1), SCIPmatrixGetRowValPtr(matrix, row1),
1127 	                   SCIPmatrixGetRowNNonzs(matrix, row1));
1128 	   SCIPsortIntReal(SCIPmatrixGetRowIdxPtr(matrix, row2), SCIPmatrixGetRowValPtr(matrix, row2),
1129 	                   SCIPmatrixGetRowNNonzs(matrix, row2));
1130 	
1131 	   /* Use row2 to strengthen row1 */
1132 	   infeasible = FALSE;
1133 	   SCIP_CALL( transformAndSolve(scip, matrix, row1, row2, swaprow1, swaprow2, aoriginal, acopy,
1134 	                                coriginal, ccopy, cangetbnd, lbs, ubs, newlbsoriginal, newlbscopy,
1135 	                                newubsoriginal, newubscopy, success, &infeasible) );
1136 	
1137 	   /* Switch roles and use row1 to strengthen row2 */
1138 	   SCIP_CALL( transformAndSolve(scip, matrix, row2, row1, swaprow2, swaprow1, aoriginal, acopy,
1139 	                                coriginal, ccopy, cangetbnd, lbs, ubs, newlbsoriginal, newlbscopy,
1140 	                                newubsoriginal, newubscopy, success, &infeasible) );
1141 	
1142 	   SCIPfreeBufferArray(scip, &cangetbnd);
1143 	   SCIPfreeBufferArray(scip, &newubscopy);
1144 	   SCIPfreeBufferArray(scip, &newubsoriginal);
1145 	   SCIPfreeBufferArray(scip, &newlbscopy);
1146 	   SCIPfreeBufferArray(scip, &newlbsoriginal);
1147 	   SCIPfreeBufferArray(scip, &ccopy);
1148 	   SCIPfreeBufferArray(scip, &coriginal);
1149 	   SCIPfreeBufferArray(scip, &acopy);
1150 	   SCIPfreeBufferArray(scip, &aoriginal);
1151 	
1152 	   return SCIP_OKAY;
1153 	}
1154 	
1155 	/* Find hashes contained in both hashlists, and apply LP-bound
1156 	 * on their corresponding rows. Both hashlists must be sorted.
1157 	 */
1158 	static
1159 	SCIP_RETCODE processHashlists(
1160 	   SCIP*                 scip,               /**< SCIP data structure */
1161 	   SCIP_PRESOLDATA*      presoldata,         /**< presolver data structure */
1162 	   SCIP_MATRIX*          matrix,             /**< constraint matrix object */
1163 	   int*                  hashlist1,          /**< first list of hashes */
1164 	   int*                  hashlist2,          /**< second list of hashes */
1165 	   int                   lenhashlist1,       /**< length of first hashlist */
1166 	   int                   lenhashlist2,       /**< length of second hashlist */
1167 	   int*                  rowidxlist1,        /**< list of row indices corresponding to hashes in hashlist1 */
1168 	   int*                  rowidxlist2,        /**< list of row indices corresponding to hashes in hashlist2 */
1169 	   SCIP_Real*            newlbs,             /**< lower variable bounds, new bounds will be written here */
1170 	   SCIP_Real*            newubs              /**< upper variable bounds, new bound will be written here */
1171 	   )
1172 	{
1173 	   int i;
1174 	   int j;
1175 	   int block1start;
1176 	   int block1end;
1177 	   int block2start;
1178 	   int block2end;
1179 	   SCIP_Longint maxcombines;
1180 	   SCIP_Bool finished;
1181 	   SCIP_Bool success;
1182 	   SCIP_Bool swaprow1;
1183 	   SCIP_Bool swaprow2;
1184 	   int ncombines;
1185 	   int combinefails;
1186 	   int retrievefails;
1187 	   ROWPAIR rowpair;
1188 	   SCIP_HASHSET* pairhashset;
1189 	
1190 	   SCIP_CALL( SCIPhashsetCreate(&pairhashset, SCIPblkmem(scip), 1) );
1191 	
1192 	   finished = FALSE;
1193 	   block1start = 0;
1194 	   block1end = 0;
1195 	   block2start = 0;
1196 	   block2end = 0;
1197 	   maxcombines = presoldata->maxpairfac == -1 ? SCIP_LONGINT_MAX : (((SCIP_Longint)SCIPmatrixGetNRows(matrix)) * presoldata->maxpairfac);
1198 	
1199 	   ncombines = 0;
1200 	   combinefails = 0;
1201 	   retrievefails = 0;
1202 	   findNextBlock(hashlist1, lenhashlist1, &block1start, &block1end);
1203 	   findNextBlock(hashlist2, lenhashlist2, &block2start, &block2end);
1204 	   while( !finished )
1205 	   {
1206 	      if( hashlist1[block1start] == hashlist2[block2start] )
1207 	      {
1208 	         for( i = block1start; i < block1end; i++ )
1209 	         {
1210 	            for( j = block2start; j < block2end; j++ )
1211 	            {
1212 	               if( rowidxlist1[i] != rowidxlist2[j] )
1213 	               {
1214 	                  rowpair.row1idx = MIN(rowidxlist1[i], rowidxlist2[j]);
1215 	                  rowpair.row2idx = MAX(rowidxlist1[i], rowidxlist2[j]);
1216 	                  if( !SCIPhashsetExists(pairhashset, encodeRowPair(&rowpair)) )
1217 	                  {
1218 	                     assert(!SCIPisInfinity(scip, -SCIPmatrixGetRowLhs(matrix, rowpair.row1idx)));
1219 	                     assert(!SCIPisInfinity(scip, -SCIPmatrixGetRowLhs(matrix, rowpair.row2idx)));
1220 	
1221 	                     success = FALSE;
1222 	
1223 	                     /* apply lp-based bound tightening */
1224 	                     swaprow1 = !SCIPisInfinity(scip, SCIPmatrixGetRowRhs(matrix, rowpair.row1idx));
1225 	                     swaprow2 = !SCIPisInfinity(scip, SCIPmatrixGetRowRhs(matrix, rowpair.row2idx));
1226 	
1227 	                     SCIP_CALL( applyLPboundTightening(scip, matrix, rowpair.row1idx, rowpair.row2idx,
1228 	                           swaprow1, swaprow2, newlbs, newubs, &success) );
1229 	
1230 	                     if( success )
1231 	                        combinefails = 0;
1232 	                     else
1233 	                        combinefails++;
1234 	
1235 	                     SCIP_CALL( SCIPhashsetInsert(pairhashset, SCIPblkmem(scip), encodeRowPair(&rowpair)) );
1236 	                     ncombines++;
1237 	
1238 	                     if( ncombines >= maxcombines || combinefails >= presoldata->maxcombinefails )
1239 	                        finished = TRUE;
1240 	
1241 	                     retrievefails = 0;
1242 	                  }
1243 	                  else if( retrievefails < presoldata->maxretrievefails )
1244 	                     retrievefails++;
1245 	                  else
1246 	                     finished = TRUE;
1247 	               }
1248 	               /* check if SCIP ran into a time limit already */
1249 	               if( j % 10 == 0 && SCIPisStopped(scip) )
1250 	                  finished = TRUE;
1251 	               if( finished )
1252 	                  break;
1253 	            }
1254 	            /* check if SCIP ran into a time limit already */
1255 	            if( SCIPisStopped(scip) )
1256 	               finished = TRUE;
1257 	            if( finished )
1258 	               break;
1259 	         }
1260 	
1261 	         if( block1end < lenhashlist1 && block2end < lenhashlist2 )
1262 	         {
1263 	            findNextBlock(hashlist1, lenhashlist1, &block1start, &block1end);
1264 	            findNextBlock(hashlist2, lenhashlist2, &block2start, &block2end);
1265 	         }
1266 	         else
1267 	            finished = TRUE;
1268 	      }
1269 	      else if( hashlist1[block1start] < hashlist2[block2start] && block1end < lenhashlist1 )
1270 	         findNextBlock(hashlist1, lenhashlist1, &block1start, &block1end);
1271 	      else if( hashlist1[block1start] > hashlist2[block2start] && block2end < lenhashlist2 )
1272 	         findNextBlock(hashlist2, lenhashlist2, &block2start, &block2end);
1273 	      else
1274 	         finished = TRUE;
1275 	   }
1276 	
1277 	   SCIPhashsetFree(&pairhashset, SCIPblkmem(scip));
1278 	
1279 	   return SCIP_OKAY;
1280 	}
1281 	
1282 	
1283 	/*
1284 	 * Callback methods of presolver
1285 	 */
1286 	
1287 	/** copy method for constraint handler plugins (called when SCIP copies plugins) */
1288 	static
1289 	SCIP_DECL_PRESOLCOPY(presolCopyTworowbnd)
1290 	{
1291 	   SCIP_PRESOLDATA* presoldata;
1292 	
1293 	   assert(scip != NULL);
1294 	   assert(presol != NULL);
1295 	   assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
1296 	
1297 	   /* call inclusion method of presolver if copying is enabled */
1298 	   presoldata = SCIPpresolGetData(presol);
1299 	   assert(presoldata != NULL);
1300 	   if( presoldata->enablecopy )
1301 	   {
1302 	      SCIP_CALL( SCIPincludePresolTworowbnd(scip) );
1303 	   }
1304 	
1305 	   return SCIP_OKAY;
1306 	}
1307 	
1308 	/** destructor of presolver to free user data (called when SCIP is exiting) */
1309 	static
1310 	SCIP_DECL_PRESOLFREE(presolFreeTworowbnd)
1311 	{  /*lint --e{715}*/
1312 	   SCIP_PRESOLDATA* presoldata;
1313 	
1314 	   /* free presolver data */
1315 	   presoldata = SCIPpresolGetData(presol);
1316 	   assert(presoldata != NULL);
1317 	
1318 	   SCIPfreeBlockMemory(scip, &presoldata);
1319 	   SCIPpresolSetData(presol, NULL);
1320 	
1321 	   return SCIP_OKAY;
1322 	}
1323 	
1324 	/** initialization method of presolver (called after problem was transformed) */
1325 	static
1326 	SCIP_DECL_PRESOLINIT(presolInitTworowbnd)
1327 	{
1328 	   SCIP_PRESOLDATA* presoldata;
1329 	
1330 	   presoldata = SCIPpresolGetData(presol);
1331 	   presoldata->nchgbnds = 0;
1332 	   presoldata->nuselessruns = 0;
1333 	
1334 	   return SCIP_OKAY;
1335 	}
1336 	
1337 	/** execution method of presolver */
1338 	static
1339 	SCIP_DECL_PRESOLEXEC(presolExecTworowbnd)
1340 	{  /*lint --e{715}*/
1341 	   SCIP_MATRIX* matrix;
1342 	   SCIP_Bool initialized;
1343 	   SCIP_Bool complete;
1344 	   SCIP_Bool infeasible;
1345 	   SCIP_PRESOLDATA* presoldata;
1346 	   int oldnchgbds;
1347 	   int oldnfixedvars;
1348 	   int nrows;
1349 	   int ncols;
1350 	   SCIP_Real* oldlbs;
1351 	   SCIP_Real* oldubs;
1352 	   SCIP_Real* newlbs;
1353 	   SCIP_Real* newubs;
1354 	   int* rowidxptr;
1355 	   SCIP_Real* rowvalptr;
1356 	   SCIP_VAR* var;
1357 	
1358 	   SCIP_Longint maxhashes;
1359 	
1360 	   int maxlen;
1361 	   int pospp;
1362 	   int listsizepp;
1363 	   int posmm;
1364 	   int listsizemm;
1365 	   int pospm;
1366 	   int listsizepm;
1367 	   int posmp;
1368 	   int listsizemp;
1369 	
1370 	   int* hashlistpp;
1371 	   int* hashlistmm;
1372 	   int* hashlistpm;
1373 	   int* hashlistmp;
1374 	
1375 	   int* rowidxlistpp;
1376 	   int* rowidxlistmm;
1377 	   int* rowidxlistpm;
1378 	   int* rowidxlistmp;
1379 	
1380 	   SCIP_Bool finiterhs;
1381 	
1382 	   int i;
1383 	   int j;
1384 	   int k;
1385 	
1386 	   assert(result != NULL);
1387 	   *result = SCIP_DIDNOTRUN;
1388 	   infeasible = FALSE;
1389 	
1390 	   if( SCIPisStopped(scip) )
1391 	      return SCIP_OKAY;
1392 	
1393 	   presoldata = SCIPpresolGetData(presol);
1394 	   assert(presoldata != NULL);
1395 	
1396 	   if( presoldata->nuselessruns >= 5 )
1397 	      return SCIP_OKAY;
1398 	
1399 	   *result = SCIP_DIDNOTFIND;
1400 	
1401 	   matrix = NULL;
1402 	   SCIP_CALL( SCIPmatrixCreate(scip, &matrix, TRUE, &initialized, &complete, &infeasible,
1403 	      naddconss, ndelconss, nchgcoefs, nchgbds, nfixedvars) );
1404 	
1405 	   /* if infeasibility was detected during matrix creation, return here */
1406 	   if( infeasible )
1407 	   {
1408 	      if( initialized )
1409 	         SCIPmatrixFree(scip, &matrix);
1410 	
1411 	      *result = SCIP_CUTOFF;
1412 	      return SCIP_OKAY;
1413 	   }
1414 	
1415 	   if( !initialized )
1416 	      return SCIP_OKAY;
1417 	
1418 	   nrows = SCIPmatrixGetNRows(matrix);
1419 	   ncols = SCIPmatrixGetNColumns(matrix);
1420 	
1421 	   if( nrows <= 1 )
1422 	   {
1423 	      SCIPmatrixFree(scip, &matrix);
1424 	      return SCIP_OKAY;
1425 	   }
1426 	
1427 	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &hashlistpp, nrows) );
1428 	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &hashlistmm, nrows) );
1429 	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &hashlistpm, nrows) );
1430 	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &hashlistmp, nrows) );
1431 	
1432 	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &rowidxlistpp, nrows) );
1433 	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &rowidxlistmm, nrows) );
1434 	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &rowidxlistpm, nrows) );
1435 	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &rowidxlistmp, nrows) );
1436 	
1437 	   pospp = 0;
1438 	   posmm = 0;
1439 	   pospm = 0;
1440 	   posmp = 0;
1441 	   listsizepp = nrows;
1442 	   listsizemm = nrows;
1443 	   listsizepm = nrows;
1444 	   listsizemp = nrows;
1445 	   maxhashes = presoldata->maxhashfac == -1 ? SCIP_LONGINT_MAX : (((SCIP_Longint)nrows) * presoldata->maxhashfac);
1446 	
1447 	   /* skim through the problem and create hashlists for combination candidates */
1448 	   for( i = 0; i < nrows; i++)
1449 	   {
1450 	      if( ((SCIP_Longint)pospp) + posmm + pospm + posmp > maxhashes )
1451 	         break;
1452 	
1453 	      rowvalptr = SCIPmatrixGetRowValPtr(matrix, i);
1454 	      rowidxptr = SCIPmatrixGetRowIdxPtr(matrix, i);
1455 	      finiterhs = !SCIPisInfinity(scip, SCIPmatrixGetRowRhs(matrix, i));
1456 	      maxlen = MIN(presoldata->maxconsiderednonzeros, SCIPmatrixGetRowNNonzs(matrix, i)); /*lint !e666*/
1457 	      for( j = 0; j < maxlen; j++)
1458 	      {
1459 	         for( k = j+1; k < maxlen; k++)
1460 	         {
1461 	            if( SCIPisPositive(scip, rowvalptr[j]) )
1462 	            {
1463 	               if(SCIPisPositive(scip, rowvalptr[k]) )
1464 	               {
1465 	                  SCIP_CALL( addEntry(scip, &pospp, &listsizepp, &hashlistpp, &rowidxlistpp,
1466 	                     hashIndexPair(rowidxptr[j],rowidxptr[k]), i) );
1467 	                  if( finiterhs )
1468 	                     SCIP_CALL( addEntry(scip, &posmm, &listsizemm, &hashlistmm, &rowidxlistmm,
1469 	                        hashIndexPair(rowidxptr[j],rowidxptr[k]), i) );
1470 	               }
1471 	               else
1472 	               {
1473 	                  SCIP_CALL( addEntry(scip, &pospm, &listsizepm, &hashlistpm, &rowidxlistpm,
1474 	                     hashIndexPair(rowidxptr[j],rowidxptr[k]), i) );
1475 	                  if( finiterhs )
1476 	                     SCIP_CALL( addEntry(scip, &posmp, &listsizemp, &hashlistmp, &rowidxlistmp,
1477 	                        hashIndexPair(rowidxptr[j],rowidxptr[k]), i) );
1478 	               }
1479 	            }
1480 	            else
1481 	            {
1482 	               if(SCIPisPositive(scip, rowvalptr[k]) )
1483 	               {
1484 	                  SCIP_CALL( addEntry(scip, &posmp, &listsizemp, &hashlistmp, &rowidxlistmp,
1485 	                     hashIndexPair(rowidxptr[j],rowidxptr[k]), i) );
1486 	                  if( finiterhs )
1487 	                     SCIP_CALL( addEntry(scip, &pospm, &listsizepm, &hashlistpm, &rowidxlistpm,
1488 	                        hashIndexPair(rowidxptr[j],rowidxptr[k]), i) );
1489 	               }
1490 	               else
1491 	               {
1492 	                  SCIP_CALL( addEntry(scip, &posmm, &listsizemm, &hashlistmm, &rowidxlistmm,
1493 	                     hashIndexPair(rowidxptr[j],rowidxptr[k]), i) );
1494 	                  if( finiterhs )
1495 	                     SCIP_CALL( addEntry(scip, &pospp, &listsizepp, &hashlistpp, &rowidxlistpp,
1496 	                        hashIndexPair(rowidxptr[j],rowidxptr[k]), i) );
1497 	               }
1498 	            }
1499 	         }
1500 	      }
1501 	   }
1502 	
1503 	#ifdef SCIP_DEBUG_HASHING
1504 	   SCIPdebugMsg(scip, "pp\n");
1505 	   for( i = 0; i < pospp; i++)
1506 	      SCIPdebugMsg(scip, "%d: hash  = %d, rowidx = %d\n", i, hashlistpp[i], rowidxlistpp[i]);
1507 	   SCIPdebugMsg(scip, "mm\n");
1508 	   for( i = 0; i < posmm; i++)
1509 	      SCIPdebugMsg(scip, "%d: hash  = %d, rowidx = %d\n", i, hashlistmm[i], rowidxlistmm[i]);
1510 	   SCIPdebugMsg(scip, "pm\n");
1511 	   for( i = 0; i < pospm; i++)
1512 	      SCIPdebugMsg(scip, "%d: hash  = %d, rowidx = %d\n", i, hashlistpm[i], rowidxlistpm[i]);
1513 	   SCIPdebugMsg(scip, "mp\n");
1514 	   for( i = 0; i < posmp; i++)
1515 	      SCIPdebugMsg(scip, "%d: hash  = %d, rowidx = %d\n", i, hashlistmp[i], rowidxlistmp[i]);
1516 	#endif
1517 	   SCIPdebugMsg(scip, "hashlist sizes: pp %d, mm %d, pm %d, mp %d \n", pospp, posmm, pospm, posmp);
1518 	
1519 	   SCIPsortIntInt(hashlistpp, rowidxlistpp, pospp);
1520 	   SCIPsortIntInt(hashlistmm, rowidxlistmm, posmm);
1521 	   SCIPsortIntInt(hashlistpm, rowidxlistpm, pospm);
1522 	   SCIPsortIntInt(hashlistmp, rowidxlistmp, posmp);
1523 	
1524 	#ifdef SCIP_DEBUG_HASHING
1525 	   SCIPdebugMsg(scip, "sorted pp\n");
1526 	   for( i = 0; i < pospp; i++)
1527 	      SCIPdebugMsg(scip, "%d: hash  = %d, rowidx = %d\n", i, hashlistpp[i], rowidxlistpp[i]);
1528 	   SCIPdebugMsg(scip, "sorted mm\n");
1529 	   for( i = 0; i < posmm; i++)
1530 	      SCIPdebugMsg(scip, "%d: hash  = %d, rowidx = %d\n", i, hashlistmm[i], rowidxlistmm[i]);
1531 	   SCIPdebugMsg(scip, "sorted pm\n");
1532 	   for( i = 0; i < pospm; i++)
1533 	      SCIPdebugMsg(scip, "%d: hash  = %d, rowidx = %d\n", i, hashlistpm[i], rowidxlistpm[i]);
1534 	   SCIPdebugMsg(scip, "sorted mp\n");
1535 	   for( i = 0; i < posmp; i++)
1536 	      SCIPdebugMsg(scip, "%d: hash  = %d, rowidx = %d\n", i, hashlistmp[i], rowidxlistmp[i]);
1537 	#endif
1538 	
1539 	   SCIP_CALL( SCIPallocBufferArray(scip, &oldlbs, ncols) );
1540 	   SCIP_CALL( SCIPallocBufferArray(scip, &oldubs, ncols) );
1541 	   SCIP_CALL( SCIPallocBufferArray(scip, &newlbs, ncols) );
1542 	   SCIP_CALL( SCIPallocBufferArray(scip, &newubs, ncols) );
1543 	
1544 	   for( i = 0; i < SCIPmatrixGetNColumns(matrix); i++ )
1545 	   {
1546 	      var = SCIPmatrixGetVar(matrix, i);
1547 	      oldlbs[i] = SCIPvarGetLbLocal(var);
1548 	      oldubs[i] = SCIPvarGetUbLocal(var);
1549 	      newlbs[i] = oldlbs[i];
1550 	      newubs[i] = oldubs[i];
1551 	   }
1552 	
1553 	   /* Process pp and mm hashlists */
1554 	   if( pospp > 0 && posmm > 0 )
1555 	   {
1556 	     SCIPdebugMsg(scip, "processing pp and mm\n");
1557 	     SCIP_CALL( processHashlists(scip, presoldata, matrix, hashlistpp, hashlistmm, pospp, posmm, rowidxlistpp,
1558 	                                 rowidxlistmm, newlbs, newubs) );
1559 	   }
1560 	
1561 	   /* Process pm and mp hashlists */
1562 	   if( pospm > 0 && posmp > 0 )
1563 	   {
1564 	     SCIPdebugMsg(scip, "processing pm and mp\n");
1565 	     SCIP_CALL( processHashlists(scip, presoldata, matrix, hashlistpm, hashlistmp, pospm, posmp, rowidxlistpm,
1566 	                                 rowidxlistmp, newlbs, newubs) );
1567 	   }
1568 	
1569 	   /* Apply reductions */
1570 	   oldnchgbds = *nchgbds;
1571 	   oldnfixedvars = *nfixedvars;
1572 	   for( i = 0; i < SCIPmatrixGetNColumns(matrix); i++ )
1573 	   {
1574 	      SCIP_Bool bndwastightened;
1575 	      SCIP_Bool fixed;
1576 	
1577 	      var = SCIPmatrixGetVar(matrix, i);
1578 	
1579 	      assert(SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS || SCIPvarGetType(var) == SCIP_VARTYPE_IMPLINT
1580 	         || (SCIPisEQ(scip, newlbs[i], SCIPceil(scip, newlbs[i])) && (SCIPisEQ(scip, newubs[i], SCIPfloor(scip, newubs[i])))));
1581 	
1582 	      if( SCIPisEQ(scip, newlbs[i], newubs[i]) )
1583 	      {
1584 	         SCIP_CALL( SCIPfixVar(scip, var, newlbs[i], &infeasible, &fixed) );
1585 	
1586 	         if( infeasible )
1587 	         {
1588 	            SCIPdebugMessage(" -> infeasible fixing of variable %s\n", SCIPvarGetName(var));
1589 	            break;
1590 	         }
1591 	
1592 	         if( fixed )
1593 	         {
1594 	            SCIPdebugMessage("variable %s fixed to %g\n", SCIPvarGetName(var), newlbs[i]);
1595 	            (*nfixedvars)++;
1596 	         }
1597 	      }
1598 	
1599 	      if( SCIPisLT(scip, oldlbs[i], newlbs[i]) )
1600 	      {
1601 	         SCIP_CALL( SCIPtightenVarLb(scip, var, newlbs[i], FALSE, &infeasible, &bndwastightened) );
1602 	
1603 	         if( infeasible )
1604 	         {
1605 	            SCIPdebugMessage(" -> infeasible lower bound tightening: %s >= %g\n", SCIPvarGetName(var), newlbs[i]);
1606 	            break;
1607 	         }
1608 	
1609 	         if( bndwastightened )
1610 	         {
1611 	            SCIPdebugMessage("lower bound of %s changed from %g to %g\n", SCIPvarGetName(var), oldlbs[i], newlbs[i]);
1612 	            (*nchgbds)++;
1613 	         }
1614 	      }
1615 	
1616 	      if( SCIPisGT(scip, oldubs[i], newubs[i]) )
1617 	      {
1618 	         SCIP_CALL( SCIPtightenVarUb(scip, var, newubs[i], FALSE, &infeasible, &bndwastightened) );
1619 	
1620 	         if( infeasible )
1621 	         {
1622 	            SCIPdebugMessage(" -> infeasible upper bound tightening: %s <= %g\n", SCIPvarGetName(var), newubs[i]);
1623 	            break;
1624 	         }
1625 	
1626 	         if( bndwastightened )
1627 	         {
1628 	            SCIPdebugMessage("upper bound of %s changed from %g to %g\n", SCIPvarGetName(var), oldubs[i], newubs[i]);
1629 	            (*nchgbds)++;
1630 	         }
1631 	      }
1632 	   }
1633 	
1634 	   /* set result */
1635 	   if( *nchgbds > oldnchgbds || *nfixedvars > oldnfixedvars )
1636 	   {
1637 	      *result = SCIP_SUCCESS;
1638 	      presoldata->nuselessruns = 0;
1639 	   }
1640 	   else if( infeasible )
1641 	   {
1642 	      *result = SCIP_CUTOFF;
1643 	   }
1644 	   else
1645 	   {
1646 	      presoldata->nuselessruns++;
1647 	   }
1648 	
1649 	   SCIPfreeBufferArray(scip, &newubs);
1650 	   SCIPfreeBufferArray(scip, &newlbs);
1651 	   SCIPfreeBufferArray(scip, &oldubs);
1652 	   SCIPfreeBufferArray(scip, &oldlbs);
1653 	   SCIPfreeBlockMemoryArray(scip, &rowidxlistmp, listsizemp);
1654 	   SCIPfreeBlockMemoryArray(scip, &rowidxlistpm, listsizepm);
1655 	   SCIPfreeBlockMemoryArray(scip, &rowidxlistmm, listsizemm);
1656 	   SCIPfreeBlockMemoryArray(scip, &rowidxlistpp, listsizepp);
1657 	   SCIPfreeBlockMemoryArray(scip, &hashlistmp, listsizemp);
1658 	   SCIPfreeBlockMemoryArray(scip, &hashlistpm, listsizepm);
1659 	   SCIPfreeBlockMemoryArray(scip, &hashlistmm, listsizemm);
1660 	   SCIPfreeBlockMemoryArray(scip, &hashlistpp, listsizepp);
1661 	
1662 	   SCIPmatrixFree(scip, &matrix);
1663 	
1664 	   return SCIP_OKAY;
1665 	}
1666 	
1667 	
1668 	/*
1669 	 * presolver specific interface methods
1670 	 */
1671 	
1672 	/** creates the tworowbndb presolver and includes it in SCIP */
1673 	SCIP_RETCODE SCIPincludePresolTworowbnd(
1674 	   SCIP*                 scip                /**< SCIP data structure */
1675 	   )
1676 	{
1677 	   SCIP_PRESOLDATA* presoldata;
1678 	   SCIP_PRESOL* presol;
1679 	
1680 	   /* create tworowbnd presolver data */
1681 	   SCIP_CALL( SCIPallocBlockMemory(scip, &presoldata) );
1682 	
1683 	   presol = NULL;
1684 	
1685 	   /* include presolver */
1686 	   SCIP_CALL( SCIPincludePresolBasic(scip, &presol, PRESOL_NAME, PRESOL_DESC, PRESOL_PRIORITY, PRESOL_MAXROUNDS, PRESOL_TIMING,
1687 	         presolExecTworowbnd,
1688 	         presoldata) );
1689 	
1690 	   assert(presol != NULL);
1691 	
1692 	   SCIP_CALL( SCIPsetPresolCopy(scip, presol, presolCopyTworowbnd) );
1693 	   SCIP_CALL( SCIPsetPresolFree(scip, presol, presolFreeTworowbnd) );
1694 	   SCIP_CALL( SCIPsetPresolInit(scip, presol, presolInitTworowbnd) );
1695 	
1696 	   /* add tworowbnd presolver parameters */
1697 	   SCIP_CALL( SCIPaddBoolParam(scip,
1698 	         "presolving/tworowbnd/enablecopy",
1699 	         "should tworowbnd presolver be copied to sub-SCIPs?",
1700 	         &presoldata->enablecopy, TRUE, DEFAULT_ENABLECOPY, NULL, NULL) );
1701 	   SCIP_CALL( SCIPaddIntParam(scip,
1702 	         "presolving/tworowbnd/maxconsiderednonzeros",
1703 	         "maximal number of considered non-zeros within one row (-1: no limit)",
1704 	         &presoldata->maxconsiderednonzeros, FALSE, DEFAULT_MAXCONSIDEREDNONZEROS, -1, INT_MAX, NULL, NULL) );
1705 	   SCIP_CALL( SCIPaddIntParam(scip,
1706 	         "presolving/tworowbnd/maxretrievefails",
1707 	         "maximal number of consecutive useless hashtable retrieves",
1708 	         &presoldata->maxretrievefails, FALSE, DEFAULT_MAXRETRIEVEFAILS, -1, INT_MAX, NULL, NULL) );
1709 	   SCIP_CALL( SCIPaddIntParam(scip,
1710 	         "presolving/tworowbnd/maxcombinefails",
1711 	         "maximal number of consecutive useless row combines",
1712 	         &presoldata->maxcombinefails, FALSE, DEFAULT_MAXCOMBINEFAILS, -1, INT_MAX, NULL, NULL) );
1713 	   SCIP_CALL( SCIPaddIntParam(scip,
1714 	         "presolving/tworowbnd/maxhashfac",
1715 	         "Maximum number of hashlist entries as multiple of number of rows in the problem (-1: no limit)",
1716 	         &presoldata->maxhashfac, FALSE, DEFAULT_MAXHASHFAC, -1, INT_MAX, NULL, NULL) );
1717 	   SCIP_CALL( SCIPaddIntParam(scip,
1718 	         "presolving/tworowbnd/maxpairfac",
1719 	         "Maximum number of processed row pairs as multiple of the number of rows in the problem (-1: no limit)",
1720 	         &presoldata->maxpairfac, FALSE, DEFAULT_MAXPAIRFAC, -1, INT_MAX, NULL, NULL) );
1721 	
1722 	   return SCIP_OKAY;
1723 	}
1724