Scippy

SCIP

Solving Constraint Integer Programs

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