1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 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
encodeRowPair(ROWPAIR * rowpair)110 void* encodeRowPair(
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
hashIndexPair(int idx1,int idx2)121 int hashIndexPair(
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
addEntry(SCIP * scip,int * pos,int * listsize,int ** hashlist,int ** rowidxlist,int hash,int rowidx)132 SCIP_RETCODE addEntry(
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
findNextBlock(int * list,int len,int * start,int * end)164 void findNextBlock(
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
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)191 SCIP_RETCODE solveSingleRowLP(
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
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)537 SCIP_RETCODE transformAndSolve(
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 {
851 if( SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_BINARY
852 || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_INTEGER
853 || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_IMPLINT )
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]));
871 if( SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_BINARY
872 || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_INTEGER
873 || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_IMPLINT )
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 {
902 if( SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_BINARY
903 || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_INTEGER
904 || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_IMPLINT )
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]));
922 if( SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_BINARY
923 || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_INTEGER
924 || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_IMPLINT )
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 {
977 if( SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_BINARY
978 || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_INTEGER
979 || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_IMPLINT )
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]));
998 if( SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_BINARY
999 || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_INTEGER
1000 || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_IMPLINT )
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 {
1030 if( SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_BINARY
1031 || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_INTEGER
1032 || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_IMPLINT )
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]));
1050 if( SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_BINARY
1051 || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_INTEGER
1052 || SCIPvarGetType(SCIPmatrixGetVar(matrix, idx1)) == SCIP_VARTYPE_IMPLINT )
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
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)1078 SCIP_RETCODE applyLPboundTightening(
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
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)1150 SCIP_RETCODE processHashlists(
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
SCIP_DECL_PRESOLCOPY(presolCopyTworowbnd)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 {
1293 SCIP_CALL( SCIPincludePresolTworowbnd(scip) );
1294 }
1295
1296 return SCIP_OKAY;
1297 }
1298
1299 /** destructor of presolver to free user data (called when SCIP is exiting) */
1300 static
SCIP_DECL_PRESOLFREE(presolFreeTworowbnd)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
SCIP_DECL_PRESOLINIT(presolInitTworowbnd)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
SCIP_DECL_PRESOLEXEC(presolExecTworowbnd)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
1570 assert(SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS || SCIPvarGetType(var) == SCIP_VARTYPE_IMPLINT
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 */
SCIPincludePresolTworowbnd(SCIP * scip)1664 SCIP_RETCODE SCIPincludePresolTworowbnd(
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 */
1677 SCIP_CALL( SCIPincludePresolBasic(scip, &presol, PRESOL_NAME, PRESOL_DESC, PRESOL_PRIORITY, PRESOL_MAXROUNDS, PRESOL_TIMING,
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 */
1688 SCIP_CALL( SCIPaddBoolParam(scip,
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 }
1715