# 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-2024 Zuse Institute Berlin (ZIB) */
7 /* */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
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
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
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
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
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
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
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  {
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]));
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  {
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]));
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  {
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]));
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  {
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]));
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
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
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  {
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
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 */
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 */
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 */
1698  "presolving/tworowbnd/enablecopy",
1699  "should tworowbnd presolver be copied to sub-SCIPs?",
1700  &presoldata->enablecopy, TRUE, DEFAULT_ENABLECOPY, NULL, NULL) );
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) );
1706  "presolving/tworowbnd/maxretrievefails",
1707  "maximal number of consecutive useless hashtable retrieves",
1708  &presoldata->maxretrievefails, FALSE, DEFAULT_MAXRETRIEVEFAILS, -1, INT_MAX, NULL, NULL) );
1710  "presolving/tworowbnd/maxcombinefails",
1711  "maximal number of consecutive useless row combines",
1712  &presoldata->maxcombinefails, FALSE, DEFAULT_MAXCOMBINEFAILS, -1, INT_MAX, NULL, NULL) );
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) );
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 }
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
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:105
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
struct SCIP_PresolData SCIP_PRESOLDATA
Definition: type_presol.h:51
SCIP_VAR * SCIPmatrixGetVar(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1629
#define NULL
Definition: def.h:267
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5205
int SCIPmatrixGetNRows(SCIP_MATRIX *matrix)
Definition: matrix.c:1701
SCIP_RETCODE SCIPsetPresolFree(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLFREE((*presolfree)))
Definition: scip_presol.c:156
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)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:139
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18135
static SCIP_DECL_PRESOLEXEC(presolExecTworowbnd)
SCIP_RETCODE SCIPincludePresolTworowbnd(SCIP *scip)
void SCIPmatrixFree(SCIP *scip, SCIP_MATRIX **matrix)
Definition: matrix.c:1041
#define FALSE
Definition: def.h:94
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_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
#define TRUE
Definition: def.h:93
SCIP_RETCODE SCIPhashsetCreate(SCIP_HASHSET **hashset, BMS_BLKMEM *blkmem, int size)
Definition: misc.c:3759
#define DEFAULT_MAXRETRIEVEFAILS
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
static void findNextBlock(int *list, int len, int *start, int *end)
SCIP_PRESOLDATA * SCIPpresolGetData(SCIP_PRESOL *presol)
Definition: presol.c:512
SCIP_Bool SCIPhashsetExists(SCIP_HASHSET *hashset, void *element)
Definition: misc.c:3817
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5322
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPdebugMessage
Definition: pub_message.h:96
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIP_LONGINT_MAX
Definition: def.h:159
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
static SCIP_DECL_PRESOLCOPY(presolCopyTworowbnd)
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
#define SCIPdebugMsg
Definition: scip_message.h:78
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:83
int SCIPmatrixGetRowNNonzs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1677
SCIP_Real SCIPmatrixGetRowLhs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1711
static int hashIndexPair(int idx1, int idx2)
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static void * encodeRowPair(ROWPAIR *rowpair)
void SCIPpresolSetData(SCIP_PRESOL *presol, SCIP_PRESOLDATA *presoldata)
Definition: presol.c:522
void SCIPhashsetFree(SCIP_HASHSET **hashset, BMS_BLKMEM *blkmem)
Definition: misc.c:3790
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:57
SCIP_RETCODE SCIPsetPresolInit(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLINIT((*presolinit)))
Definition: scip_presol.c:172
int * SCIPmatrixGetRowIdxPtr(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1665
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17420
static SCIP_RETCODE addEntry(SCIP *scip, int *pos, int *listsize, int **hashlist, int **rowidxlist, int hash, int rowidx)
#define DEFAULT_ENABLECOPY
#define DEFAULT_MAXCOMBINEFAILS
const char * SCIPmatrixGetRowName(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1689
const char * SCIPmatrixGetColName(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1641
#define SCIP_CALL(x)
Definition: def.h:380
#define SCIPhashTwo(a, b)
Definition: pub_misc.h:551
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:454
SCIP_Real * SCIPmatrixGetRowValPtr(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1653
#define PRESOL_MAXROUNDS
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define PRESOL_NAME
#define SCIP_Bool
Definition: def.h:91
#define MIN(x, y)
Definition: def.h:243
static SCIP_DECL_PRESOLFREE(presolFreeTworowbnd)
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
Definition: presol.c:599
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip_var.c:8278
Constraint handler for linear constraints in their most general form, .
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
public methods for matrix
do bound tightening by using two rows
SCIP_VAR ** b
Definition: circlepacking.c:65
#define DEFAULT_MAXHASHFAC
#define DEFAULT_MAXCONSIDEREDNONZEROS
#define MAX(x, y)
Definition: def.h:239
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_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPmatrixGetRowRhs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1723
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_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLCOPY((*presolcopy)))
Definition: scip_presol.c:140
SCIP_VAR * a
Definition: circlepacking.c:66
SCIP_RETCODE SCIPhashsetInsert(SCIP_HASHSET *hashset, BMS_BLKMEM *blkmem, void *element)
Definition: misc.c:3800
#define SCIP_Real
Definition: def.h:173
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:718
#define SCIP_INVALID
Definition: def.h:193
#define SCIP_Longint
Definition: def.h:158
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17585
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18145
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
default SCIP plugins
int SCIPmatrixGetNColumns(SCIP_MATRIX *matrix)
Definition: matrix.c:1573
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
#define PRESOL_PRIORITY
#define PRESOL_DESC
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:57
void SCIPsortIntReal(int *intarray, SCIP_Real *realarray, int len)
void SCIPselectWeightedReal(SCIP_Real *realarray, SCIP_Real *weights, SCIP_Real capacity, int len, int *medianpos)