# SCIP

Solving Constraint Integer Programs

presol_dualinfer.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 /* */
7 /* fuer Informationstechnik Berlin */
8 /* */
10 /* */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 /**@file presol_dualinfer.c
16  * @ingroup DEFPLUGINS_PRESOL
17  * @brief dual inference presolver
18  * @author Dieter Weninger
19  * @author Patrick Gemander
20  *
21  * This presolver does bound strengthening on continuous variables (columns) for getting bounds on dual variables y.
22  * The bounds of the dual variables are then used to fix primal variables or change the side of constraints.
23  * For ranged rows one needs to decide which side (rhs or lhs) determines the equality.
24  *
25  * We distinguish two cases concerning complementary slackness:
26  * i) reduced cost fixing: c_j - sup_y(y^T A_{.j}) > 0 => x_j = l_j
27  * c_j - inf_y(y^T A_{.j}) < 0 => x_j = u_j
28  * ii) positive dual lower bound: y_i > 0 => A_{i.}x = b_i
29  *
30  * Further information on this presolving approach are given in
31  * Achterberg et al. "Presolve reductions in mixed integer programming"
32  * and for a two-column extension in
33  * Chen et al. "Two-row and two-column mixed-integer presolve using hasing-based pairing methods".
34  */
35
36 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
37
38 #include <stdio.h>
39 #include <assert.h>
40 #include <string.h>
41
42 #include "scip/scipdefplugins.h"
43 #include "scip/pub_matrix.h"
44 #include "blockmemshell/memory.h"
45 #include "scip/cons_linear.h"
46 #include "scip/presol_dualinfer.h"
47 #include "scip/pub_cons.h"
48 #include "scip/pub_matrix.h"
49 #include "scip/pub_message.h"
50 #include "scip/pub_presol.h"
51 #include "scip/pub_var.h"
52 #include "scip/scip_general.h"
53 #include "scip/scip_mem.h"
54 #include "scip/scip_message.h"
55 #include "scip/scip_numerics.h"
56 #include "scip/scip_presol.h"
57 #include "scip/scip_prob.h"
58 #include "scip/scip_probing.h"
59 #include "scip/scip_var.h"
60
61 #define PRESOL_NAME "dualinfer"
62 #define PRESOL_DESC "exploit dual information for fixings and side changes"
63 #define PRESOL_PRIORITY -3000 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */
64 #define PRESOL_MAXROUNDS 0 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
65 #define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */
66
67 #define DEFAULT_TWOCOLUMN_COMBINE TRUE /**< should two column convex combination be used per default */
68 #define DEFAULT_MAXLOOPS_DUALBNDSTR 12 /**< default maximal number of loops for dual bound strengthening */
69 #define DEFAULT_MAXCONSIDEREDNONZEROS 100 /**< default maximal number of considered non-zeros within one row */
70 #define DEFAULT_MAXRETRIEVEFAILS 1000 /**< default maximal number of consecutive useless hashtable retrieves */
71 #define DEFAULT_MAXCOMBINEFAILS 1000 /**< default maximal number of consecutive useless row combines */
72 #define DEFAULT_MAXHASHFAC 10 /**< default maximal number of hashlist entries as multiple of number of rows in the problem */
73 #define DEFAULT_MAXPAIRFAC 1 /**< default maximal number of processed row pairs as multiple of the number of rows in the problem */
74 #define DEFAULT_MAXROWSUPPORT 3 /**< default maximal number of non-zeros in one row for turning an inequality into an equality */
75
76
77 /*
78  * Data structures
79  */
80
81 /** control parameters */
82 struct SCIP_PresolData
83 {
84  SCIP_Bool usetwocolcombine; /**< use convex combination of two columns */
85  int maxdualbndloops; /**< default number of dual bound strengthening loops */
86  int maxpairfac; /**< maximal number of processed row pairs as multiple of the number of rows in the problem (-1: no limit) */
87  int maxhashfac; /**< maximal number of hashlist entries as multiple of number of rows in the problem (-1: no limit) */
88  int maxretrievefails; /**< maximal number of consecutive useless hashtable retrieves */
89  int maxcombinefails; /**< maximal number of consecutive useless row combines */
90  int maxconsiderednonzeros; /**< maximal number of considered non-zeros within one row (-1: no limit) */
91  int maxrowsupport; /**< maximal number of non-zeros in one row for turning an inequality into an equality */
92 };
93
94 /** type of variable fixing direction */
96 {
97  FIXATLB = -1, /** fix variable at its lower bound */
98  NOFIX = 0, /** no fixing */
99  FIXATUB = 1 /** fix variable at its upper bound */
100 };
102
103 /** type of constraint side change */
105 {
106  RHSTOLHS = -1, /** set rhs to value of lhs */
107  NOCHANGE = 0, /** no side change */
108  LHSTORHS = 1 /** set lhs to value of rhs */
109 };
110 typedef enum SideChange SIDECHANGE;
111
112 /** Signum for convex-combined variable coefficients \f$(\lambda * A_{ri} + (1 - \lambda) * A_{si})\f$
113  * UP - Coefficient changes from negative to positive for increasing lambda
114  * DN - Coefficient changes from positive to negative for increasing lambda
115  * POS - Coefficient is positive for all lambda in (0,1)
116  * NEG - Coefficient is negative for all lambda in (0,1)
117  */
118 enum signum {UP, DN, POS, NEG};
119
120 /** structure representing a pair of column indices; used for lookup in a hashtable */
121 struct ColPair
122 {
123  int col1idx; /**< first row index */
124  int col2idx; /**< second row index */
125 };
126 typedef struct ColPair COLPAIR;
127
128 /*
129  * Local methods
130  */
131
132 /** encode contents of a colpair as void* pointer */
133 static
134 void*
136  COLPAIR* colpair /**< pointer to colpair */
137  )
138 {
139  uint64_t a;
140  uint64_t b;
141
142  assert(colpair->col1idx >= 0);
143  assert(colpair->col2idx >= 0);
144
145  a = (uint64_t)(long)colpair->col1idx;
146  b = (uint64_t)(long)colpair->col2idx;
147  return (void*)((a << 32) | b);
148 }
149
150 /** compute single positive int hashvalue for two ints */
151 static
152 int
154  int idx1, /**< first integer index */
155  int idx2 /**< second integer index */
156  )
157 {
158  uint32_t hash = SCIPhashTwo(idx1, idx2);
159  return (int)(hash>>1);
160 }
161
162 /** add hash/rowidx pair to hashlist/rowidxlist **/
163 static
165  SCIP* scip, /**< SCIP datastructure */
166  int* pos, /**< position of last entry added */
167  int* listsize, /**< size of hashlist and rowidxlist */
168  int** hashlist, /**< block memory array containing hashes */
169  int** colidxlist, /**< block memory array containing column indices */
170  int hash, /**< hash to be inserted */
171  int colidx /**< column index to be inserted */
172  )
173 {
174  if( (*pos) >= (*listsize) )
175  {
176  int newsize = SCIPcalcMemGrowSize(scip, (*pos) + 1);
177  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, hashlist, (*listsize), newsize) );
178  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, colidxlist, (*listsize), newsize) );
179  (*listsize) = newsize;
180  }
181
182  (*hashlist)[(*pos)] = hash;
183  (*colidxlist)[(*pos)] = colidx;
184  (*pos)++;
185
186  return SCIP_OKAY;
187 }
188
189 /** Within a sorted list, get next block with same value
190  * E.g. for [h1, h1, h1, h2, h2, h2, h2, h3,...] and end = 0
191  * returns start = 0, end = 3
192  * and on a second call with end = 3 on the same list
193  * returns start = 3, end = 7.
194  */
195 static
197  int* list, /**< list of integers */
198  int len, /**< length of list */
199  int* start, /**< variable to contain start index of found block */
200  int* end /**< variable to contain end index of found block */
201  )
202 {
203  int i;
204  (*start) = (*end);
205  i = (*end) + 1;
206  while( i < len && list[i] == list[i - 1] )
207  i++;
208
209  (*end) = i;
210 }
211
212 /**
213  * The algorithm described in Belotti P. "Bound reduction using pairs of linear inequalities"
214  * tries to derive upper and lower bounds for all variables via convex combinations of linear inequalities
215  * We apply Belotti's algorithm to pairs of columns of continuous variables.
216  */
217 static
219  SCIP* scip, /**< SCIP datastructure */
220  int* row1idxptr, /**< indices specifying bound positions in lbs and ubs for first row */
221  int* row2idxptr, /**< indices specifying bound positions in lbs und ubs for second row */
222  SCIP_Real* row1valptr, /**< first row coefficients */
223  SCIP_Real* row2valptr, /**< second row coefficients */
224  SCIP_Real b1, /**< rhs of first row */
225  SCIP_Real b2, /**< rhs of second row*/
226  int row1len, /**< length of first row (e.g. row1idxptr and row1valptr)*/
227  int row2len, /**< length of second row (e.g. row2idxptr and row2valptr)*/
228  int ncols, /**< length of bound arrays lbs and ubs */
229  SCIP_Bool swaprow1, /**< should the sense of the first row be swapped to <= ? */
230  SCIP_Bool swaprow2, /**< should the sense of the second row be swapped to <= ? */
231  SCIP_Real* lbs, /**< lower bound array */
232  SCIP_Real* ubs, /**< upper bound array */
233  SCIP_Bool* success /**< we return (success || found better bounds") */
234  )
235 {
236  int i;
237  int j;
238  int nvars;
239  int* varinds;
240  int nbreakpoints;
241  SCIP_Real* breakpoints;
242  int idx;
243  int idx1;
244  int idx2;
245  SCIP_Real* row1coefs;
246  SCIP_Real* row2coefs;
247  enum signum* signs;
248  int ninfs;
249  int l1infs;
250  SCIP_Real l1;
251  SCIP_Real l2;
252  SCIP_Real* newlbs;
253  SCIP_Real* newubs;
254  SCIP_Real coef;
255  int sign;
256  int shift;
257
258  SCIP_CALL( SCIPallocBufferArray(scip, &row1coefs, ncols) );
259  SCIP_CALL( SCIPallocBufferArray(scip, &row2coefs, ncols) );
260
261  SCIPsortIntReal(row1idxptr, row1valptr, row1len);
262  SCIPsortIntReal(row2idxptr, row2valptr, row2len);
263
264  /* swap rows if necessary */
265  if( swaprow1 )
266  {
267  for( i = 0; i < row1len; i++ )
268  row1coefs[row1idxptr[i]] = -row1valptr[i];
269  b1 = -b1;
270  }
271  else
272  {
273  for( i = 0; i < row1len; i++ )
274  row1coefs[row1idxptr[i]] = row1valptr[i];
275  }
276
277  if( swaprow2 )
278  {
279  for( i = 0; i < row2len; i++ )
280  row2coefs[row2idxptr[i]] = -row2valptr[i];
281  b2 = -b2;
282  }
283  else
284  {
285  for( i = 0; i < row2len; i++ )
286  row2coefs[row2idxptr[i]] = row2valptr[i];
287  }
288
289  SCIP_CALL( SCIPallocBufferArray(scip, &varinds, ncols) );
290  SCIP_CALL( SCIPallocBufferArray(scip, &signs, ncols) );
291  SCIP_CALL( SCIPallocBufferArray(scip, &breakpoints, ncols) );
292
293  /* calculate cancellation breakpoints and sign behaviour */
294  i = 0;
295  j = 0;
296  nvars = 0;
297  nbreakpoints = 0;
298  while( i < row1len && j < row2len )
299  {
300  assert(i + 1 == row1len || row1idxptr[i] < row1idxptr[i + 1]);
301  assert(j + 1 == row2len || row2idxptr[j] < row2idxptr[j + 1]);
302
303  idx1 = row1idxptr[i];
304  idx2 = row2idxptr[j];
305
306  /* We use 2.0 as default value for "no cancellation". For cancellations, this will be replaced by values in (0,1).
307  * A value larger than 1.0 is used because we sort the array and want to put non-cancellations to the end. */
308  breakpoints[nvars] = 2.0;
309
310  if( idx1 == idx2 )
311  {
312  if( (SCIPisNegative(scip, row1coefs[idx1]) && SCIPisPositive(scip, row2coefs[idx2])) ||
313  (SCIPisPositive(scip, row1coefs[idx1]) && SCIPisNegative(scip, row2coefs[idx2])) )
314  {
315  if( SCIPisNegative(scip, row2coefs[idx2]) )
316  signs[idx1] = UP;
317  else
318  signs[idx1] = DN;
319
320  breakpoints[nvars] = row2coefs[idx2] / (row2coefs[idx2] - row1coefs[idx1]);
321  nbreakpoints++;
322  }
323  else if( SCIPisPositive(scip, row1coefs[idx1]) )
324  signs[idx1] = POS;
325  else
326  signs[idx1] = NEG;
327
328  varinds[nvars] = idx1;
329  i++;
330  j++;
331  }
332  else if( idx1 < idx2 )
333  {
334  if( SCIPisPositive(scip, row1coefs[idx1]) )
335  signs[idx1] = POS;
336  else
337  signs[idx1] = NEG;
338
339  /* We will access this entry later on, so we explicitly write a zero here */
340  row2coefs[idx1] = 0.0;
341
342  varinds[nvars] = idx1;
343  i++;
344  }
345  else
346  {
347  assert(idx1 > idx2);
348  if( SCIPisPositive(scip, row2coefs[idx2]) )
349  signs[idx2] = POS;
350  else
351  signs[idx2] = NEG;
352
353  /* We will access this entry later on, so we explicitly write a zero here */
354  row1coefs[idx2] = 0.0;
355
356  varinds[nvars] = idx2;
357  j++;
358  }
359  nvars++;
360  }
361
362  while( i < row1len )
363  {
364  idx1 = row1idxptr[i];
365
366  if( SCIPisPositive(scip, row1coefs[idx1]) )
367  signs[idx1] = POS;
368  else
369  signs[idx1] = NEG;
370
371  /* We will access this entry later on, so we explicitly write a zero here */
372  row2coefs[idx1] = 0.0;
373
374  varinds[nvars] = idx1;
375  breakpoints[nvars] = 2.0;
376  nvars++;
377  i++;
378  }
379
380  while( j < row2len )
381  {
382  idx2 = row2idxptr[j];
383
384  if( SCIPisPositive(scip, row2coefs[idx2]) )
385  signs[idx2] = POS;
386  else
387  signs[idx2] = NEG;
388
389  /* We will access this entry later on, so we explicitly write a zero here */
390  row1coefs[idx2] = 0.0;
391
392  varinds[nvars] = idx2;
393  breakpoints[nvars] = 2.0;
394  nvars++;
395  j++;
396  }
397
398  SCIPsortRealInt(breakpoints, varinds, nvars);
399
400  /* The obvious preconditions for bound tightenings are met, so we try to calculate new bounds. */
401  if( nbreakpoints >= 1 )
402  {
403  SCIP_CALL( SCIPallocBufferArray(scip, &newlbs, nvars) );
404  SCIP_CALL( SCIPallocBufferArray(scip, &newubs, nvars) );
405
406  for( i = 0; i < nvars; i++)
407  {
408  idx = varinds[i];
409  newlbs[i] = lbs[idx];
410  newubs[i] = ubs[idx];
411  }
412
413  /* calculate activity contributions of each row */
414  l1 = b1;
415  l2 = b2;
416  l1infs = 0;
417  ninfs = 0;
418  for( i = 0; i < nvars; i++ )
419  {
420  idx = varinds[i];
421  if( !SCIPisZero(scip, row2coefs[idx]) )
422  {
423  if( SCIPisNegative(scip, row2coefs[idx]) )
424  {
425  if( !SCIPisInfinity(scip, -lbs[idx]) )
426  {
427  l1 -= row1coefs[idx] * lbs[idx];
428  l2 -= row2coefs[idx] * lbs[idx];
429  }
430  else
431  ninfs++;
432  }
433  else
434  {
435  /* coefficient of second row is positive */
436  if( !SCIPisInfinity(scip, ubs[idx]) )
437  {
438  l1 -= row1coefs[idx] * ubs[idx];
439  l2 -= row2coefs[idx] * ubs[idx];
440  }
441  else
442  ninfs++;
443  }
444  }
445  else
446  {
447  /* since row2coefs[idx] is zero, we have to choose the bound using row1coefs[idx] */
448  assert(!SCIPisZero(scip, row1coefs[idx]) && SCIPisZero(scip, row2coefs[idx]));
449  if( SCIPisNegative(scip, row1coefs[idx]) )
450  {
451  if( !SCIPisInfinity(scip, -lbs[idx]) )
452  l1 -= row1coefs[idx] * lbs[idx];
453  else
454  l1infs++;
455  }
456  else
457  {
458  /* coefficient of first row is positive */
459  if( !SCIPisInfinity(scip, ubs[idx]) )
460  l1 -= row1coefs[idx] * ubs[idx];
461  else
462  l1infs++;
463  }
464  }
465  }
466
467  /* Calculate bounds for lambda = 0 */
468 #ifdef SCIP_MORE_DEBUG
469  SCIPdebugMsg(scip, "lambda = 0, l1 = %g, l2 = %g, ninfs = %d\n", i, breakpoints[i], l1, l2, ninfs);
470 #endif
471
472  if( ninfs <= 1 )
473  {
474 #ifdef SCIP_MORE_DEBUG
475  SCIP_Real oldlb;
476  SCIP_Real oldub;
477 #endif
478  for( i = 0; i < nvars; i++ )
479  {
480 #ifdef SCIP_MORE_DEBUG
481  oldlb = newlbs[i];
482  oldub = newubs[i];
483 #endif
484  idx = varinds[i];
485  if( SCIPisPositive(scip, row2coefs[idx]) )
486  {
487  if( ninfs == 0 )
488  newlbs[i] = MAX(newlbs[i], (l2 + row2coefs[idx] * ubs[idx]) / row2coefs[idx]);
489  else if( SCIPisInfinity(scip, ubs[idx]) )
490  newlbs[i] = MAX(newlbs[i], l2 / row2coefs[idx]);
491  }
492  else if ( SCIPisNegative(scip, row2coefs[idx]) )
493  {
494  if( ninfs == 0 )
495  newubs[i] = MIN(newubs[i], (l2 + row2coefs[idx] * lbs[idx]) / row2coefs[idx]);
496  else if( SCIPisInfinity(scip, -lbs[idx]) )
497  newubs[i] = MIN(newubs[i], l2 / row2coefs[idx]);
498  }
499 #ifdef SCIP_MORE_DEBUG
500  if( !SCIPisEQ(scip, oldlb, newlbs[i]) || !SCIPisEQ(scip, oldub, newubs[i]) )
501  SCIPdebugMsg(scip, "%g <= %g <= var_%d <= %g <= %g\n", oldlb, newlbs[i], i, newubs[i], oldub);
502 #endif
503  }
504  }
505
506  ninfs += l1infs;
507
508  i = 0;
509  while( i < nbreakpoints )
510  {
511  int nnewinfs;
512  SCIP_Real l1update;
513  SCIP_Real l2update;
514  SCIP_Bool updated;
515
516  /* determine number of infinities and compute update for l1 and l2 */
517  shift = 0;
518  nnewinfs = 0;
519  l1update = 0.0;
520  l2update = 0.0;
521  updated = FALSE;
522  j = i;
523  while( !updated )
524  {
525  idx = varinds[j];
526  assert(signs[idx] == UP || signs[idx] == DN);
527  if( signs[idx] == UP )
528  sign = 1;
529  else
530  sign = -1;
531
532  if( !SCIPisInfinity(scip, -lbs[idx]) )
533  {
534  l1update += sign * row1coefs[idx] * lbs[idx];
535  l2update += sign * row2coefs[idx] * lbs[idx];
536  }
537  else
538  {
539  if( signs[idx] == UP )
540  ninfs--;
541  else
542  nnewinfs++;
543  }
544
545  if( !SCIPisInfinity(scip, ubs[idx]) )
546  {
547  l1update -= sign * row1coefs[idx] * ubs[idx];
548  l2update -= sign * row2coefs[idx] * ubs[idx];
549  }
550  else
551  {
552  if( signs[idx] == UP )
553  nnewinfs++;
554  else
555  ninfs--;
556  }
557
558  if( signs[idx] == UP )
559  signs[idx] = POS;
560  else
561  signs[idx] = NEG;
562
563  if( j + 1 >= nbreakpoints || !SCIPisEQ(scip, breakpoints[j], breakpoints[j + 1]) )
564  updated = TRUE;
565
566  shift++;
567  j++;
568  }
569
570 #ifdef SCIP_MORE_DEBUG
571  SCIPdebugMsg(scip, "lambda_%d = %g, l1 = %g, l2 = %g, ninfs = %d\n", i, breakpoints[i], l1, l2, ninfs);
572 #endif
573
574  assert(ninfs >= 0);
575
576  /* if more than one infinity destroys our bounds we cannot tighten anything */
577  if( ninfs <= 1 )
578  {
579  /* check for bounds to be tightened */
580  for( j = 0; j < nvars; j++ )
581  {
582 #ifdef SCIP_MORE_DEBUG
583  SCIP_Real oldlb;
584  SCIP_Real oldub;
585 #endif
586
587  /* catch the special case where the entire remaining constraint is cancelled */
588  if( j >= nvars )
589  break;
590
591 #ifdef SCIP_MORE_DEBUG
592  oldlb = newlbs[j];
593  oldub = newubs[j];
594 #endif
595
596  idx = varinds[j];
597  coef = breakpoints[i] * row1coefs[idx] + (1 - breakpoints[i]) * row2coefs[idx];
598  assert(!SCIPisEQ(scip, breakpoints[i], 2.0));
599
600  /* skip if the coefficient is too close to zero as it becomes numerically unstable */
601  if( SCIPisZero(scip, coef) )
602  continue;
603
604  if( signs[idx] == POS || signs[idx] == DN )
605  {
606  if( ninfs == 0 )
607  newlbs[j] = MAX(newlbs[j], (breakpoints[i] * l1 + (1 - breakpoints[i]) * l2 + coef * ubs[idx]) / coef);
608  else if( SCIPisInfinity(scip, ubs[idx]) )
609  newlbs[j] = MAX(newlbs[j], (breakpoints[i] * l1 + (1 - breakpoints[i]) * l2) / coef);
610  }
611  else if ( signs[idx] == NEG || signs[idx] == UP )
612  {
613  if( ninfs == 0 )
614  newubs[j] = MIN(newubs[j], (breakpoints[i] * l1 + (1 - breakpoints[i]) * l2 + coef * lbs[idx]) / coef);
615  else if( SCIPisInfinity(scip, -lbs[idx]) )
616  newubs[j] = MIN(newubs[j], (breakpoints[i] * l1 + (1 - breakpoints[i]) * l2) / coef);
617  }
618 #ifdef SCIP_MORE_DEBUG
619  if( !SCIPisEQ(scip, oldlb, newlbs[j]) || !SCIPisEQ(scip, oldub, newubs[j]) )
620  SCIPdebugMsg(scip, "%g <= %g <= var_%d <= %g <= %g\n", oldlb, newlbs[j], j, newubs[j], oldub);
621 #endif
622  }
623  }
624
625  i += shift;
626  ninfs += nnewinfs;
627  l1 += l1update;
628  l2 += l2update;
629  }
630
631  /* check infinities in first row */
632  ninfs = 0;
633  for( i = 0; i < nvars; i++ )
634  {
635  idx = varinds[i];
636  if( (SCIPisPositive(scip, row1coefs[idx]) && SCIPisInfinity(scip, ubs[idx]))
637  || (SCIPisNegative(scip, row1coefs[idx]) && SCIPisInfinity(scip, -lbs[idx])) )
638  ninfs++;
639  }
640
641  /* calculate bounds for lambda = 1 */
642 #ifdef SCIP_MORE_DEBUG
643  SCIPdebugMsg(scip, "lambda = 1, l1 = %g, l2 = %g, ninfs = %d\n", i, breakpoints[i], l1, l2, ninfs);
644 #endif
645  if( ninfs <= 1 )
646  {
647 #ifdef SCIP_MORE_DEBUG
648  SCIP_Real oldlb;
649  SCIP_Real oldub;
650 #endif
651  for( i = 0; i < nvars; i++ )
652  {
653 #ifdef SCIP_MORE_DEBUG
654  oldlb = newlbs[i];
655  oldub = newubs[i];
656 #endif
657  idx = varinds[i];
658  if( SCIPisPositive(scip, row1coefs[idx]) )
659  {
660  if( ninfs == 0 )
661  newlbs[i] = MAX(newlbs[i], (l1 + row1coefs[idx] * ubs[idx]) / row1coefs[idx]);
662  else if( SCIPisInfinity(scip, ubs[idx]) )
663  newlbs[i] = MAX(newlbs[i], l1 / row1coefs[idx]);
664  }
665  else if ( SCIPisNegative(scip, row1coefs[idx]) )
666  {
667  if( ninfs == 0 )
668  newubs[i] = MIN(newubs[i], (l1 + row1coefs[idx] * lbs[idx]) / row1coefs[idx]);
669  else if( SCIPisInfinity(scip, -lbs[idx]) )
670  newubs[i] = MIN(newubs[i], l1 / row1coefs[idx]);
671  }
672 #ifdef SCIP_MORE_DEBUG
673  if( !SCIPisEQ(scip, oldlb, newlbs[i]) || !SCIPisEQ(scip, oldub, newubs[i]) )
674  SCIPdebugMsg(scip, "%g <= %g <= var_%i <= %g <= %g\n", oldlb, newlbs[i], i, newubs[i], oldub);
675 #endif
676  }
677  }
678
679  /* update bound arrays and determine success */
680  for( i = 0; i < nvars; i++ )
681  {
682  idx = varinds[i];
683
684  assert(SCIPisLE(scip, lbs[idx], newlbs[i]));
685  assert(SCIPisGE(scip, ubs[idx], newubs[i]));
686
687  if( SCIPisGT(scip, newlbs[i], lbs[idx]) || SCIPisLT(scip, newubs[i], ubs[idx]) )
688  {
689  (*success) = TRUE;
690
691  lbs[idx] = newlbs[i];
692  ubs[idx] = newubs[i];
693  }
694  }
695  SCIPfreeBufferArray(scip, &newubs);
696  SCIPfreeBufferArray(scip, &newlbs);
697  }
698
699  SCIPfreeBufferArray(scip, &breakpoints);
700  SCIPfreeBufferArray(scip, &signs);
701  SCIPfreeBufferArray(scip, &varinds);
702  SCIPfreeBufferArray(scip, &row2coefs);
703  SCIPfreeBufferArray(scip, &row1coefs);
704
705  return SCIP_OKAY;
706 }
707
708 /** get minimal and maximal residual activities without one specific column */
709 static
711  SCIP* scip, /**< SCIP main data structure */
712  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
713  int col, /**< column index */
714  int row, /**< row index */
715  SCIP_Real* lbs, /**< lower bounds */
716  SCIP_Real* ubs, /**< upper bounds */
717  SCIP_Real* minresactivity, /**< minimum residual activity of this row */
718  SCIP_Real* maxresactivity, /**< maximum residual activity of this row */
719  SCIP_Bool* isminsettoinfinity, /**< flag indicating if minresactiviy is set to infinity */
720  SCIP_Bool* ismaxsettoinfinity /**< flag indicating if maxresactiviy is set to infinity */
721  )
722 {
723  SCIP_Real coef;
724  int* rowpnt;
725  int* rowend;
726  SCIP_Real* valpnt;
727  int nmaxactneginf;
728  int nmaxactposinf;
729  int nminactneginf;
730  int nminactposinf;
731  SCIP_Real maxresact;
732  SCIP_Real minresact;
733
734  assert(scip != NULL);
735  assert(matrix != NULL);
736  assert(minresactivity != NULL);
737  assert(maxresactivity != NULL);
738  assert(isminsettoinfinity != NULL);
739  assert(ismaxsettoinfinity != NULL);
740
741  *isminsettoinfinity = FALSE;
742  *ismaxsettoinfinity = FALSE;
743
744  nmaxactneginf = 0;
745  nmaxactposinf = 0;
746  nminactneginf = 0;
747  nminactposinf = 0;
748  maxresact = 0;
749  minresact = 0;
750
751  rowpnt = SCIPmatrixGetRowIdxPtr(matrix, row);
752  rowend = rowpnt + SCIPmatrixGetRowNNonzs(matrix, row);
753  valpnt = SCIPmatrixGetRowValPtr(matrix, row);
754
755  for( ; rowpnt < rowend; rowpnt++, valpnt++ )
756  {
757  if(*rowpnt == col)
758  continue;
759
760  coef = *valpnt;
761
762  /* positive coefficient */
763  if( coef > 0.0 )
764  {
765  if( SCIPisInfinity(scip, ubs[col]) )
766  nmaxactposinf++;
767  else
768  maxresact += coef * ubs[col];
769
770  if( SCIPisInfinity(scip, -lbs[col]) )
771  nminactneginf++;
772  else
773  minresact += coef * lbs[col];
774  }
775  else /* negative coefficient */
776  {
777  if( SCIPisInfinity(scip, -lbs[col]) )
778  nmaxactneginf++;
779  else
780  maxresact += coef * lbs[col];
781
782  if( SCIPisInfinity(scip, ubs[col]) )
783  nminactposinf++;
784  else
785  minresact += coef * ubs[col];
786  }
787  }
788
789  if( (nmaxactneginf + nmaxactposinf) > 0 )
790  *ismaxsettoinfinity = TRUE;
791  else
792  *maxresactivity = maxresact;
793
794  if( (nminactneginf + nminactposinf) > 0 )
795  *isminsettoinfinity = TRUE;
796  else
797  *minresactivity = minresact;
798 }
799
800 /** calculate the upper and lower bound of one variable from one row */
801 static
803  SCIP* scip, /**< SCIP main data structure */
804  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
805  int col, /**< column index of variable */
806  int row, /**< row index */
807  SCIP_Real val, /**< coefficient of this column in this row */
808  SCIP_Real* lbs, /**< lower bounds */
809  SCIP_Real* ubs, /**< upper bounds */
810  SCIP_Real* rowub, /**< upper bound of row */
811  SCIP_Bool* ubfound, /**< flag indicating that an upper bound was calculated */
812  SCIP_Real* rowlb, /**< lower bound of row */
813  SCIP_Bool* lbfound /**< flag indicating that a lower bound was caluclated */
814  )
815 {
816  SCIP_Bool isminsettoinfinity;
817  SCIP_Bool ismaxsettoinfinity;
818  SCIP_Real minresactivity;
819  SCIP_Real maxresactivity;
820  SCIP_Real lhs;
821  SCIP_Real rhs;
822
823  assert(rowub != NULL);
824  assert(ubfound != NULL);
825  assert(rowlb != NULL);
826  assert(lbfound != NULL);
827
828  *rowub = SCIPinfinity(scip);
829  *ubfound = FALSE;
830  *rowlb = -SCIPinfinity(scip);
831  *lbfound = FALSE;
832
833  getMinMaxActivityResiduals(scip, matrix, col, row, lbs, ubs,
834  &minresactivity, &maxresactivity,
835  &isminsettoinfinity, &ismaxsettoinfinity);
836
837  lhs = SCIPmatrixGetRowLhs(matrix, row);
838  rhs = SCIPmatrixGetRowRhs(matrix, row);
839
840  if( val > 0.0 )
841  {
842  if( !isminsettoinfinity && !SCIPisInfinity(scip, rhs) )
843  {
844  *rowub = (rhs - minresactivity) / val; // maybe one wants some kind of numerical guard of check that values is not too small for all these
845  *ubfound = TRUE;
846  }
847
848  if( !ismaxsettoinfinity && !SCIPisInfinity(scip, -lhs) )
849  {
850  *rowlb = (lhs - maxresactivity) / val;
851  *lbfound = TRUE;
852  }
853  }
854  else
855  {
856  if( !ismaxsettoinfinity && !SCIPisInfinity(scip, -lhs) )
857  {
858  *rowub = (lhs - maxresactivity) / val;
859  *ubfound = TRUE;
860  }
861
862  if( !isminsettoinfinity && !SCIPisInfinity(scip, rhs) )
863  {
864  *rowlb = (rhs - minresactivity) / val;
865  *lbfound = TRUE;
866  }
867  }
868 }
869
870
871 /** detect implied variable bounds */
872 static
874  SCIP* scip, /**< SCIP main data structure */
875  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
876  int col, /**< column index for implied free test */
877  SCIP_Real* lbs, /**< lower bounds */
878  SCIP_Real* ubs, /**< upper bounds */
879  SCIP_Bool* ubimplied, /**< flag indicating an implied upper bound */
880  SCIP_Bool* lbimplied /**< flag indicating an implied lower bound */
881  )
882 {
883  SCIP_Real impliedub;
884  SCIP_Real impliedlb;
885  int* colpnt;
886  int* colend;
887  SCIP_Real* valpnt;
888
889  assert(scip != NULL);
890  assert(matrix != NULL);
891  assert(lbs != NULL);
892  assert(ubs != NULL);
893  assert(ubimplied != NULL);
894  assert(lbimplied != NULL);
895
896  *ubimplied = FALSE;
897  impliedub = SCIPinfinity(scip);
898
899  *lbimplied = FALSE;
900  impliedlb = -SCIPinfinity(scip);
901
902  colpnt = SCIPmatrixGetColIdxPtr(matrix, col);
903  colend = colpnt + SCIPmatrixGetColNNonzs(matrix, col);
904  valpnt = SCIPmatrixGetColValPtr(matrix, col);
905  for( ; (colpnt < colend); colpnt++, valpnt++ )
906  {
907  SCIP_Real rowub;
908  SCIP_Bool ubfound;
909  SCIP_Real rowlb;
910  SCIP_Bool lbfound;
911
912  getVarBoundsOfRow(scip, matrix, col, *colpnt, *valpnt, lbs, ubs,
913  &rowub, &ubfound, &rowlb, &lbfound);
914
915  if( ubfound && (rowub < impliedub) )
916  impliedub = rowub;
917
918  if( lbfound && (rowlb > impliedlb) )
919  impliedlb = rowlb;
920  }
921
922  /* we consider +/-inf bounds as implied bounds */
923  if( SCIPisInfinity(scip, ubs[col]) ||
924  (!SCIPisInfinity(scip, ubs[col]) && SCIPisLE(scip, impliedub, ubs[col])) )
925  *ubimplied = TRUE;
926
927  if( SCIPisInfinity(scip, -lbs[col]) ||
928  (!SCIPisInfinity(scip, -lbs[col]) && SCIPisGE(scip, impliedlb, lbs[col])) )
929  *lbimplied = TRUE;
930 }
931
932
933 /** calculate minimal column activity from one variable without one row */
934 static
936  SCIP* scip, /**< SCIP main data structure */
937  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
938  int col, /**< column index */
939  int withoutrow, /**< exclude this row index */
940  SCIP_Real* lbdual, /**< lower bounds of dual variables */
941  SCIP_Real* ubdual /**< upper bounds of dual variables */
942  )
943 {
944  SCIP_Real* valpnt;
945  int* colpnt;
946  int* colend;
947  SCIP_Real val;
948  SCIP_Real mincolactivity;
949  int row;
950
951  assert(scip != NULL);
952  assert(matrix != NULL);
953  assert(lbdual != NULL);
954  assert(ubdual != NULL);
955
956  mincolactivity = 0;
957
958  colpnt = SCIPmatrixGetColIdxPtr(matrix, col);
959  colend = colpnt + SCIPmatrixGetColNNonzs(matrix, col);
960  valpnt = SCIPmatrixGetColValPtr(matrix, col);
961
962  for( ; colpnt < colend; colpnt++, valpnt++ )
963  {
964  row = *colpnt;
965  val = *valpnt;
966
967  if( row == withoutrow )
968  continue;
969
970  if( val > 0.0 )
971  {
972  assert(!SCIPisInfinity(scip, -lbdual[row]));
973  mincolactivity += val * lbdual[row];
974  }
975  else if( val < 0.0 )
976  {
977  assert(!SCIPisInfinity(scip, ubdual[row]));
978  mincolactivity += val * ubdual[row];
979  }
980  }
981
982  return mincolactivity;
983 }
984
985
986 /** In the primal the residual activity of a constraint w.r.t. a variable is the activity of the constraint without the variable.
987  * This function does the same but in the dual.
988  * It computes the residual activity of column 'col' w.r.t. variable 'row'
989  */
990 static
992  SCIP* scip, /**< SCIP main data structure */
993  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
994  int col, /**< column index */
995  int row, /**< row index */
996  SCIP_Real val, /**< matrix coefficient */
997  SCIP_Real* lbdual, /**< lower bounds of the dual variables */
998  SCIP_Real* ubdual, /**< upper bounds of the dual variables */
999  SCIP_Real* mincolact, /**< minimal column activities */
1000  int* mincolactinf, /**< number of infinite contributions to minimal column activity */
1001  SCIP_Real* mincolresact /**< minimal residual column activity */
1002  )
1003 {
1004  assert(scip != NULL);
1005  assert(matrix != NULL);
1006  assert(lbdual != NULL);
1007  assert(ubdual != NULL);
1008  assert(mincolact != NULL);
1009  assert(mincolactinf != NULL);
1010  assert(mincolresact != NULL);
1011
1012  *mincolresact = -SCIPinfinity(scip);
1013
1014  if( val > 0.0 )
1015  {
1016  if( SCIPisInfinity(scip, -lbdual[row]) )
1017  {
1018  assert(mincolactinf[col] >= 1);
1019  if( mincolactinf[col] == 1 )
1020  *mincolresact = getMinColActWithoutRow(scip, matrix, col, row, lbdual, ubdual);
1021  else
1022  *mincolresact = -SCIPinfinity(scip);
1023  }
1024  else
1025  {
1026  if( mincolactinf[col] > 0 )
1027  *mincolresact = -SCIPinfinity(scip);
1028  else
1029  *mincolresact = mincolact[col] - val * lbdual[row];
1030  }
1031  }
1032  else if( val < 0.0 )
1033  {
1034  if( SCIPisInfinity(scip, ubdual[row]) )
1035  {
1036  assert(mincolactinf[col] >= 1);
1037  if( mincolactinf[col] == 1 )
1038  *mincolresact = getMinColActWithoutRow(scip, matrix, col, row, lbdual, ubdual);
1039  else
1040  *mincolresact = -SCIPinfinity(scip);
1041  }
1042  else
1043  {
1044  if( mincolactinf[col] > 0 )
1045  *mincolresact = -SCIPinfinity(scip);
1046  else
1047  *mincolresact = mincolact[col] - val * ubdual[row];
1048  }
1049  }
1050 }
1051
1052 /** calculate minimal column activity of one column */
1053 static
1055  SCIP* scip, /**< SCIP main data structure */
1056  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
1057  int col, /**< column for activity calculations */
1058  SCIP_Real* lbdual, /**< lower bounds of dual variables */
1059  SCIP_Real* ubdual, /**< upper bounds of dual variables */
1060  SCIP_Real* mincolact, /**< minimal column activities */
1061  int* mincolactinf /**< number of -inf contributions to minimal column activity */
1062  )
1063 {
1064  SCIP_Real* valpnt;
1065  int* colpnt;
1066  int* colend;
1067  SCIP_Real val;
1068  int row;
1069
1070  assert(scip != NULL);
1071  assert(matrix != NULL);
1072  assert(lbdual != NULL);
1073  assert(ubdual != NULL);
1074  assert(mincolact != NULL);
1075  assert(mincolactinf != NULL);
1076
1077  /* init activities */
1078  mincolact[col] = 0.0;
1079  mincolactinf[col] = 0;
1080
1081  colpnt = SCIPmatrixGetColIdxPtr(matrix, col);
1082  colend = colpnt + SCIPmatrixGetColNNonzs(matrix, col);
1083  valpnt = SCIPmatrixGetColValPtr(matrix, col);
1084
1085  /* calculate column activities */
1086  for( ; colpnt < colend; colpnt++, valpnt++ )
1087  {
1088  row = *colpnt;
1089  val = *valpnt;
1090
1091  if( val > 0.0 )
1092  {
1093  if(SCIPisInfinity(scip, -lbdual[row]))
1094  mincolactinf[col]++;
1095  else
1096  mincolact[col] += val * lbdual[row];
1097  }
1098  else if( val < 0.0 )
1099  {
1100  if(SCIPisInfinity(scip, ubdual[row]))
1101  mincolactinf[col]++;
1102  else
1103  mincolact[col] += val * ubdual[row];
1104  }
1105  }
1106
1107  /* update column activities if infinity counters are greater 0 */
1108  if( mincolactinf[col] > 0 )
1109  mincolact[col] = -SCIPinfinity(scip);
1110 }
1111
1112 /** calculate maximal column activity of one column */
1113 static
1115  SCIP* scip, /**< SCIP main data structure */
1116  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
1117  int col, /**< column for activity calculations */
1118  SCIP_Real* lbdual, /**< lower bounds of dual variables */
1119  SCIP_Real* ubdual, /**< upper bounds of dual variables */
1120  SCIP_Real* maxcolact, /**< minimal column activities */
1121  int* maxcolactinf /**< number of -inf contributions to minimal column activity */
1122  )
1123 {
1124  SCIP_Real* valpnt;
1125  int* colpnt;
1126  int* colend;
1127  SCIP_Real val;
1128  int row;
1129
1130  assert(scip != NULL);
1131  assert(matrix != NULL);
1132  assert(lbdual != NULL);
1133  assert(ubdual != NULL);
1134  assert(maxcolact != NULL);
1135  assert(maxcolactinf != NULL);
1136
1137  /* init activities */
1138  maxcolact[col] = 0.0;
1139  maxcolactinf[col] = 0;
1140
1141  colpnt = SCIPmatrixGetColIdxPtr(matrix, col);
1142  colend = colpnt + SCIPmatrixGetColNNonzs(matrix, col);
1143  valpnt = SCIPmatrixGetColValPtr(matrix, col);
1144
1145  /* calculate column activities */
1146  for( ; colpnt < colend; colpnt++, valpnt++ )
1147  {
1148  row = *colpnt;
1149  val = *valpnt;
1150
1151  if( val > 0.0 )
1152  {
1153  if(SCIPisInfinity(scip, ubdual[row]))
1154  maxcolactinf[col]++;
1155  else
1156  maxcolact[col] += val * ubdual[row];
1157  }
1158  else if( val < 0.0 )
1159  {
1160  if(SCIPisInfinity(scip, -lbdual[row]))
1161  maxcolactinf[col]++;
1162  else
1163  maxcolact[col] += val * lbdual[row];
1164  }
1165  }
1166
1167  /* update column activities if infinity counters are greater 0 */
1168  if( maxcolactinf[col] > 0 )
1169  maxcolact[col] = SCIPinfinity(scip);
1170 }
1171
1172
1173 /** update minimal/maximal column activity infinity counters */
1174 static
1176  SCIP* scip, /**< SCIP main data structure */
1177  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
1178  int row, /**< row index */
1179  SCIP_Real* lbdual, /**< lower bounds of dual variables */
1180  SCIP_Real* ubdual, /**< upper bounds of dual variables */
1181  SCIP_Bool* isubimplied, /**< flags indicating of the upper bound is implied */
1182  SCIP_Real* mincolact, /**< minimal column activities */
1183  int* mincolactinf, /**< number of infinity contributions to minimal column activity */
1184  SCIP_Bool ubinfchange, /**< flag indicating if the upper bound has changed from infinity to a finite value */
1185  SCIP_Bool lbinfchange /**< flag indicating if the lower bound has changed from -infinity to a finite value */
1186  )
1187 {
1188  SCIP_Real* valpnt;
1189  int* rowpnt;
1190  int* rowend;
1191  SCIP_Real val;
1192  int col;
1193
1194  rowpnt = SCIPmatrixGetRowIdxPtr(matrix, row);
1195  rowend = rowpnt + SCIPmatrixGetRowNNonzs(matrix, row);
1196  valpnt = SCIPmatrixGetRowValPtr(matrix, row);
1197
1198  /* look at all column entries present within row and update the
1199  * corresponding infinity counters. if one counter gets to zero,
1200  * then calculate this column activity new.
1201  */
1202
1203  for(; (rowpnt < rowend); rowpnt++, valpnt++ )
1204  {
1205  col = *rowpnt;
1206  val = *valpnt;
1207
1208  if( isubimplied[col] )
1209  {
1210  if( val < 0 )
1211  {
1212  if( ubinfchange )
1213  {
1214  assert(mincolactinf[col] > 0);
1215  mincolactinf[col]--;
1216  }
1217  }
1218  else if( val > 0 )
1219  {
1220  if( lbinfchange )
1221  {
1222  assert(mincolactinf[col] > 0);
1223  mincolactinf[col]--;
1224  }
1225  }
1226
1227  if( mincolactinf[col] == 0 )
1228  calcMinColActivity(scip, matrix, col, lbdual, ubdual, mincolact, mincolactinf);
1229  }
1230  }
1231 }
1232
1233 #ifdef SCIP_DEBUG
1234 /** use LP calculations for determining the best dual variable bounds from a specific row index */
1235 static
1237  SCIP* scip, /**< SCIP main data structure */
1238  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
1239  int row, /**< row index for dual bound calculations */
1240  SCIP_Bool solveLP, /**< flag indicating to solve subscip LP */
1241  SCIP_Real* lowerbnddual, /**< lower bound of dual variable */
1242  SCIP_Real* upperbnddual /**< upper bound of dual variable */
1243  )
1244 {
1245  int i;
1246  int nrows;
1247  int ncols;
1248  int numberconvars;
1249  SCIP_VAR* var;
1250  SCIP_VAR** variables;
1251  SCIP_VAR** tmpvars;
1252  SCIP_Real* tmpcoef;
1253  SCIP_CONS** constraints;
1254  int numDualVars;
1255  SCIP* subscip;
1256  SCIP_RETCODE retcode;
1257  char name[SCIP_MAXSTRLEN+3];
1258  int fillcnt;
1259  int* colpnt;
1260  int* colend;
1261  SCIP_Real* valpnt;
1262  int* colmap;
1263
1264  *lowerbnddual = -SCIPinfinity(scip);
1265  *upperbnddual = SCIPinfinity(scip);
1266
1267  nrows = SCIPmatrixGetNRows(matrix);
1268  assert(0 <= row && row < nrows);
1269  ncols = SCIPmatrixGetNColumns(matrix);
1270
1271  SCIP_CALL( SCIPcreate(&subscip) );
1272  SCIP_CALL( SCIPcreateProbBasic(subscip, "subscip") );
1274
1275  /* avoid recursive calls */
1276  SCIP_CALL( SCIPsetIntParam(subscip, "presolving/dualinfer/maxrounds", 0) );
1277  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
1278  SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", TRUE) );
1279
1280  SCIP_CALL( SCIPallocBufferArray(scip, &colmap, ncols) );
1281  numberconvars = 0;
1282  for(i = 0; i < ncols; i++)
1283  {
1284  var = SCIPmatrixGetVar(matrix, i);
1286  {
1287  colmap[i] = numberconvars; /* start numbering with 0 */
1288  numberconvars++;
1289  }
1290  else
1291  colmap[i] = -1;
1292  }
1293  numDualVars = nrows + 2 * numberconvars;
1294
1295  /* create dual variables */
1296  SCIP_CALL( SCIPallocBufferArray(scip, &variables, numDualVars) );
1297  for( i = 0; i < nrows; i++ )
1298  {
1299  variables[i] = NULL;
1300  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "y%d", i);
1301  if( !SCIPmatrixIsRowRhsInfinity(matrix, i ) )
1302  {
1303  /* dual variable for equation or ranged row */
1304  SCIP_CALL( SCIPcreateVarBasic(subscip, &variables[i], name,
1305  -SCIPinfinity(scip), SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
1306  }
1307  else
1308  {
1309  /* dual variable for >= inequality */
1310  SCIP_CALL( SCIPcreateVarBasic(subscip, &variables[i], name,
1311  0.0, SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
1312  }
1314  assert( variables[i] != NULL );
1315  }
1316
1317  /* in addition, we introduce dual variables for the bounds,
1318  because we treat each continuous variable as a free variable */
1319  fillcnt = nrows;
1320  for( i = 0; i < numberconvars; i++ )
1321  {
1322  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "ylb%d", fillcnt);
1323  SCIP_CALL( SCIPcreateVarBasic(subscip, &variables[fillcnt], name,
1324  0.0, SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
1326  assert( variables[fillcnt] != NULL );
1327  fillcnt++;
1328
1329  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "yub%d", fillcnt);
1330  SCIP_CALL( SCIPcreateVarBasic(subscip, &variables[fillcnt], name,
1331  0.0, SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
1333  assert( variables[fillcnt] != NULL );
1334  fillcnt++;
1335  }
1336  assert(numDualVars == fillcnt);
1337
1338  SCIP_CALL( SCIPallocBufferArray(scip, &tmpvars, numDualVars) );
1339  SCIP_CALL( SCIPallocBufferArray(scip, &tmpcoef, numDualVars) );
1340
1341  SCIP_CALL( SCIPallocBufferArray(scip, &constraints, numberconvars) );
1342  for( i = 0; i <numberconvars; i++)
1343  constraints[i] = NULL;
1344
1345  for(i = 0; i < ncols; i++)
1346  {
1347  var = SCIPmatrixGetVar(matrix, i);
1349  {
1350  SCIP_Real objval = SCIPvarGetObj(var);
1351  int cidx = colmap[i];
1352  assert(0 <= cidx && cidx < numberconvars);
1353
1354  colpnt = SCIPmatrixGetColIdxPtr(matrix, i);
1355  colend = colpnt + SCIPmatrixGetColNNonzs(matrix, i);
1356  valpnt = SCIPmatrixGetColValPtr(matrix, i);
1357  fillcnt = 0;
1358  for( ; colpnt < colend; colpnt++, valpnt++ )
1359  {
1360  assert(0 <= *colpnt && *colpnt < nrows);
1361  assert(variables[*colpnt] != NULL);
1362  tmpvars[fillcnt] = variables[*colpnt];
1363  tmpcoef[fillcnt] = *valpnt;
1364  fillcnt++;
1365  }
1366
1367  /* consider dual variable for a lower bound */
1368  if(SCIPisGT(scip, SCIPvarGetLbGlobal(var), -SCIPinfinity(scip)))
1369  {
1370  assert(variables[nrows + 2 * cidx] != NULL);
1371  tmpvars[fillcnt] = variables[nrows + 2 * cidx];
1372  tmpcoef[fillcnt] = 1.0;
1373  fillcnt++;
1374  }
1375
1376  /* consider dual variable for an upper bound */
1377  if(SCIPisLT(scip, SCIPvarGetUbGlobal(var), SCIPinfinity(scip)))
1378  {
1379  assert(variables[nrows + 2 * cidx + 1] != NULL);
1380  tmpvars[fillcnt] = variables[nrows + 2 * cidx + 1];
1381  tmpcoef[fillcnt] = -1.0;
1382  fillcnt++;
1383  }
1384
1385  /* because we treat the continuous columns as free variable,
1386  we need here an equality */
1387  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "c%d", cidx);
1388  SCIP_CALL( SCIPcreateConsBasicLinear(subscip, &constraints[cidx], name,
1389  fillcnt, tmpvars, tmpcoef, objval, objval) );
1391  }
1392  }
1393
1394  /* determine lower dual bound via a minimization problem */
1396  SCIP_CALL( SCIPchgVarObj(subscip, variables[row], 1.0) );
1397  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "dbg_min_%s.lp", SCIPvarGetName(variables[row]));
1398  SCIP_CALL( SCIPwriteOrigProblem(subscip, name, "lp", FALSE) );
1399  if( solveLP )
1400  {
1401  retcode = SCIPsolve(subscip);
1402  if( retcode != SCIP_OKAY )
1403  SCIPwarningMessage(scip, "Error subscip: <%d>\n", retcode);
1404  else
1405  {
1406  if( SCIPgetStatus(subscip) == SCIP_STATUS_OPTIMAL )
1407  {
1408  SCIP_SOL* sol;
1409  SCIP_Bool feasible;
1410  sol = SCIPgetBestSol(subscip);
1411  SCIP_CALL( SCIPcheckSolOrig(subscip, sol, &feasible, TRUE, TRUE) );
1412
1413  if(feasible)
1414  *lowerbnddual = SCIPgetSolOrigObj(subscip, sol);
1415  }
1416  }
1417  SCIP_CALL( SCIPfreeTransform(subscip) );
1418  }
1419
1420  /* determine upper dual bound via a maximization problem */
1422  SCIP_CALL( SCIPchgVarObj(subscip, variables[row], 1.0) );
1423  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "dbg_max_%s.lp", SCIPvarGetName(variables[row]));
1424  SCIP_CALL( SCIPwriteOrigProblem(subscip, name, "lp", FALSE) );
1425  if( solveLP )
1426  {
1427  retcode = SCIPsolve(subscip);
1428  if( retcode != SCIP_OKAY )
1429  SCIPwarningMessage(scip, "Error subscip: <%d>\n", retcode);
1430  else
1431  {
1432  if( SCIPgetStatus(subscip) == SCIP_STATUS_OPTIMAL )
1433  {
1434  SCIP_SOL* sol;
1435  SCIP_Bool feasible;
1436  sol = SCIPgetBestSol(subscip);
1437  SCIP_CALL( SCIPcheckSolOrig(subscip, sol, &feasible, TRUE, TRUE) );
1438
1439  if(feasible)
1440  *upperbnddual = SCIPgetSolOrigObj(subscip, sol);
1441  }
1442  }
1443  SCIP_CALL( SCIPfreeTransform(subscip) );
1444  }
1445
1446  /* release variables and constraints */
1447  for( i = 0; i < numDualVars; i++ )
1448  {
1449  if(variables[i] != NULL)
1450  SCIP_CALL( SCIPreleaseVar(subscip, &variables[i]) );
1451  }
1452  for( i = 0; i < numberconvars; i++ )
1453  {
1454  if(constraints[i] != NULL)
1455  SCIP_CALL( SCIPreleaseCons(subscip, &constraints[i]) );
1456  }
1457
1458  SCIPfreeBufferArray(scip, &constraints);
1459  SCIPfreeBufferArray(scip, &tmpcoef);
1460  SCIPfreeBufferArray(scip, &tmpvars);
1461  SCIPfreeBufferArray(scip, &variables);
1462  SCIP_CALL( SCIPfree(&subscip) );
1463  SCIPfreeBufferArray(scip, &colmap);
1464
1465  return SCIP_OKAY;
1466 }
1467 #endif
1468
1469 /** update bounds of the dual variables */
1470 static
1472  SCIP* scip, /**< SCIP main data structure */
1473  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
1474  SCIP_Real objval, /**< objective function value */
1475  SCIP_Real val, /**< matrix coefficient */
1476  int row, /**< row index */
1477  SCIP_Real mincolresact, /**< minimal column residual activity */
1478  SCIP_Real* lbdual, /**< dual lower bounds */
1479  SCIP_Real* ubdual, /**< dual upper bounds */
1480  int* boundchanges, /**< counter for the number of bound changes */
1481  SCIP_Bool* ubinfchange, /**< flag indicating an upper bound change from infinite to finite */
1482  SCIP_Bool* lbinfchange /**< flag indicating a lower bound change from infinite to finite */
1483  )
1484 {
1485  SCIP_Real newlbdual;
1486  SCIP_Real newubdual;
1487
1488  assert(scip != NULL);
1489  assert(matrix != NULL);
1490  assert(lbdual != NULL);
1491  assert(ubdual != NULL);
1492  assert(boundchanges != NULL);
1493  assert(ubinfchange != NULL);
1494  assert(lbinfchange != NULL);
1495
1496  *ubinfchange = FALSE;
1497  *lbinfchange = FALSE;
1498
1499  if( !SCIPisInfinity(scip, -mincolresact) )
1500  {
1501  if( val > 0 )
1502  {
1503  newubdual = (objval - mincolresact) / val;
1504
1505  if( newubdual < ubdual[row] )
1506  {
1507  /* accept the new upper bound only if the numerics are reliable */
1508  if( SCIPisLE(scip,lbdual[row],newubdual) )
1509  {
1510  if( SCIPisInfinity(scip, ubdual[row]) )
1511  *ubinfchange = TRUE;
1512
1513  ubdual[row] = newubdual;
1514  (*boundchanges)++;
1515  }
1516  }
1517  }
1518  else if( val < 0 )
1519  {
1520  newlbdual = (objval - mincolresact) / val;
1521
1522  if( newlbdual > lbdual[row] )
1523  {
1524  /* accept the new lower bound only if the numerics are reliable */
1525  if( SCIPisLE(scip,newlbdual,ubdual[row]) )
1526  {
1527  if( SCIPisInfinity(scip, -lbdual[row]) )
1528  *lbinfchange = TRUE;
1529
1530  lbdual[row] = newlbdual;
1531  (*boundchanges)++;
1532  }
1533  }
1534  }
1535  }
1536 }
1537
1538 /** dual bound strengthening */
1539 static
1541  SCIP* scip, /**< SCIP main data structure */
1542  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
1543  SCIP_PRESOLDATA* presoldata, /**< presolver data structure */
1544  FIXINGDIRECTION* varstofix, /**< array holding information for later upper/lower bound fixing */
1545  int* npossiblefixings, /**< number of possible fixings */
1546  SIDECHANGE* sidestochange, /**< array holding if this is an implied equality */
1547  int* npossiblesidechanges/**< number of possible equality changes */
1548  )
1549 {
1550  SCIP_Real* lbdual;
1551  SCIP_Real* ubdual;
1552  SCIP_Real* mincolact;
1553  int* mincolactinf;
1554  SCIP_Real* maxcolact;
1555  int* maxcolactinf;
1556  int* colpnt;
1557  int* colend;
1558  SCIP_Real* valpnt;
1559  int boundchanges;
1560  int loops;
1561  int i;
1562  int j;
1563  int k;
1564  int nrows;
1565  int ncols;
1566  SCIP_Bool* isubimplied;
1567  SCIP_Bool* islbimplied;
1568  SCIP_Real* tmplbs;
1569  SCIP_Real* tmpubs;
1570  SCIP_VAR* var;
1571  int* implubvars;
1572  int nimplubvars;
1573
1574  SCIP_Longint maxhashes;
1575  int maxlen;
1576  int pospp;
1577  int listsizepp;
1578  int posmm;
1579  int listsizemm;
1580  int pospm;
1581  int listsizepm;
1582  int posmp;
1583  int listsizemp;
1584
1585  int* hashlistpp;
1586  int* hashlistmm;
1587  int* hashlistpm;
1588  int* hashlistmp;
1589
1590  int* colidxlistpp;
1591  int* colidxlistmm;
1592  int* colidxlistpm;
1593  int* colidxlistmp;
1594
1595  int block1start;
1596  int block1end;
1597  int block2start;
1598  int block2end;
1599
1600  SCIP_HASHSET* pairhashset;
1601  SCIP_Real* colvalptr;
1602  int* colidxptr;
1603
1604  assert(scip != NULL);
1605  assert(matrix != NULL);
1606  assert(varstofix != NULL);
1607  assert(npossiblefixings != NULL);
1608  assert(sidestochange != NULL);
1609  assert(npossiblesidechanges != NULL);
1610
1611  nrows = SCIPmatrixGetNRows(matrix);
1612  ncols = SCIPmatrixGetNColumns(matrix);
1613
1614  SCIP_CALL( SCIPallocBufferArray(scip, &tmplbs, ncols) );
1615  SCIP_CALL( SCIPallocBufferArray(scip, &tmpubs, ncols) );
1616  for( i = 0; i < ncols; i++ )
1617  {
1618  var = SCIPmatrixGetVar(matrix, i);
1619  tmplbs[i] = SCIPvarGetLbLocal(var);
1620  tmpubs[i] = SCIPvarGetUbLocal(var);
1621  }
1622
1623  /* verify which bounds of continuous variables are implied */
1624  SCIP_CALL( SCIPallocBufferArray(scip, &isubimplied, ncols) );
1625  SCIP_CALL( SCIPallocBufferArray(scip, &islbimplied, ncols) );
1626  SCIP_CALL( SCIPallocBufferArray(scip, &implubvars, ncols) );
1627  nimplubvars = 0;
1628  for( i = 0; i < ncols; i++ )
1629  {
1630  var = SCIPmatrixGetVar(matrix, i);
1631
1632  if( SCIPmatrixUplockConflict(matrix, i) || SCIPmatrixDownlockConflict(matrix, i) ||
1634  {
1635  /* we don't care about integral variables or variables that have conflicting locks */
1636  isubimplied[i] = FALSE;
1637  islbimplied[i] = FALSE;
1638  }
1639  else
1640  {
1641  getImpliedBounds(scip, matrix, i, tmplbs, tmpubs, &(isubimplied[i]), &(islbimplied[i]));
1642
1643  /* if a continuous variable has a not implied upper bound we can
1644  * not use this variable (column) for propagating dual bounds.
1645  * not implied lowers bound can usually be treated.
1646  */
1647
1648  /* collect continuous variables with implied upper bound */
1649  if( isubimplied[i] )
1650  {
1651  implubvars[nimplubvars] = i;
1652  nimplubvars++;
1653  }
1654
1655  /* reset implied bounds for further detections of other implied bounds */
1656  if( isubimplied[i] )
1657  tmpubs[i] = SCIPinfinity(scip);
1658
1659  if( islbimplied[i] )
1660  tmplbs[i] = -SCIPinfinity(scip);
1661  }
1662  }
1663
1664  /* initialize bounds of the dual variables */
1665  SCIP_CALL( SCIPallocBufferArray(scip, &lbdual, nrows) );
1666  SCIP_CALL( SCIPallocBufferArray(scip, &ubdual, nrows) );
1667  for( i = 0; i < nrows; i++ )
1668  {
1669  if( !SCIPmatrixIsRowRhsInfinity(matrix, i) )
1670  {
1671  /* dual free variable for equation or ranged row */
1672  lbdual[i] = -SCIPinfinity(scip);
1673  ubdual[i] = SCIPinfinity(scip);
1674  }
1675  else
1676  {
1677  /* dual variable for >= inequality */
1678  lbdual[i] = 0.0;
1679  ubdual[i] = SCIPinfinity(scip);
1680  }
1681  }
1682
1683  /* run convex combination on pairs of continuous variables (columns) using Belotti's algorithm */
1684  if( nimplubvars >= 2 && presoldata->usetwocolcombine )
1685  {
1686  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &hashlistpp, ncols) );
1687  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &hashlistmm, ncols) );
1688  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &hashlistpm, ncols) );
1689  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &hashlistmp, ncols) );
1690
1691  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &colidxlistpp, ncols) );
1692  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &colidxlistmm, ncols) );
1693  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &colidxlistpm, ncols) );
1694  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &colidxlistmp, ncols) );
1695
1696  pospp = 0;
1697  posmm = 0;
1698  pospm = 0;
1699  posmp = 0;
1700  listsizepp = ncols;
1701  listsizemm = ncols;
1702  listsizepm = ncols;
1703  listsizemp = ncols;
1704  maxhashes = presoldata->maxhashfac == -1 ? SCIP_LONGINT_MAX : (((SCIP_Longint)ncols) * presoldata->maxhashfac);
1705
1706  for( i = 0; i < nimplubvars; i++)
1707  {
1708  if( ((SCIP_Longint)pospp) + posmm + pospm + posmp > maxhashes )
1709  break;
1710
1711  colvalptr = SCIPmatrixGetColValPtr(matrix, implubvars[i]);
1712  colidxptr = SCIPmatrixGetColIdxPtr(matrix, implubvars[i]);
1713  maxlen = MIN(presoldata->maxconsiderednonzeros, SCIPmatrixGetColNNonzs(matrix, implubvars[i])); /*lint !e666*/
1714  for( j = 0; j < maxlen; j++)
1715  {
1716  for( k = j + 1; k < maxlen; k++)
1717  {
1718  if( SCIPisPositive(scip, colvalptr[j]) )
1719  {
1720  if(SCIPisPositive(scip, colvalptr[k]) )
1721  {
1722  SCIP_CALL( addEntry(scip, &pospp, &listsizepp, &hashlistpp, &colidxlistpp,
1723  hashIndexPair(colidxptr[j], colidxptr[k]), implubvars[i]) );
1724  }
1725  else
1726  {
1727  SCIP_CALL( addEntry(scip, &pospm, &listsizepm, &hashlistpm, &colidxlistpm,
1728  hashIndexPair(colidxptr[j], colidxptr[k]), implubvars[i]) );
1729  }
1730  }
1731  else
1732  {
1733  if(SCIPisPositive(scip, colvalptr[k]) )
1734  {
1735  SCIP_CALL( addEntry(scip, &posmp, &listsizemp, &hashlistmp, &colidxlistmp,
1736  hashIndexPair(colidxptr[j], colidxptr[k]), implubvars[i]) );
1737  }
1738  else
1739  {
1740  SCIP_CALL( addEntry(scip, &posmm, &listsizemm, &hashlistmm, &colidxlistmm,
1741  hashIndexPair(colidxptr[j], colidxptr[k]), implubvars[i]) );
1742  }
1743  }
1744  }
1745  }
1746  }
1747 #ifdef SCIP_MORE_DEBUG
1748  SCIPdebugMsg(scip, "hashlist sizes: pp %d, mm %d, pm %d, mp %d \n", pospp, posmm, pospm, posmp);
1749 #endif
1750  SCIPsortIntInt(hashlistpp, colidxlistpp, pospp);
1751  SCIPsortIntInt(hashlistmm, colidxlistmm, posmm);
1752  SCIPsortIntInt(hashlistpm, colidxlistpm, pospm);
1753  SCIPsortIntInt(hashlistmp, colidxlistmp, posmp);
1754
1755  SCIP_CALL( SCIPhashsetCreate(&pairhashset, SCIPblkmem(scip), 1) );
1756
1757  /* Process pp and mm lists */
1758  if( pospp > 0 && posmm > 0 )
1759  {
1760  SCIP_Longint ncombines;
1761  SCIP_Longint maxcombines;
1762  SCIP_Bool finished;
1763  SCIP_Bool success;
1764  int combinefails;
1765  int retrievefails;
1766  COLPAIR colpair;
1767
1768  finished = FALSE;
1769  block1start = 0;
1770  block1end = 0;
1771  block2start = 0;
1772  block2end = 0;
1773
1774  maxcombines = presoldata->maxpairfac == -1 ? SCIP_LONGINT_MAX : (((SCIP_Longint)ncols) * presoldata->maxpairfac);
1775
1776  ncombines = 0;
1777  combinefails = 0;
1778  retrievefails = 0;
1779  findNextBlock(hashlistpp, pospp, &block1start, &block1end);
1780  findNextBlock(hashlistmm, posmm, &block2start, &block2end);
1781 #ifdef SCIP_MORE_DEBUG
1782  SCIPdebugMsg(scip, "processing pp and mm\n");
1783 #endif
1784
1785  // same as in the rworowbnd presolver - both while loops to basically the same with one using pp and mm and the other pm and mp
1786  // I would write an additional function and remove the code duplication
1787  while( !finished )
1788  {
1789  if( hashlistpp[block1start] == hashlistmm[block2start] )
1790  {
1791  for( i = block1start; i < block1end; i++ )
1792  {
1793  for( j = block2start; j < block2end; j++ )
1794  {
1795  if( colidxlistpp[i] != colidxlistmm[j] )
1796  {
1797  colpair.col1idx = MIN(colidxlistpp[i], colidxlistmm[j]);
1798  colpair.col2idx = MAX(colidxlistpp[i], colidxlistmm[j]);
1799
1800  if( !SCIPhashsetExists(pairhashset, encodeColPair(&colpair)) )
1801  {
1802  int* colpnt1 = SCIPmatrixGetColIdxPtr(matrix, colpair.col1idx);
1803  SCIP_Real* valpnt1 = SCIPmatrixGetColValPtr(matrix, colpair.col1idx);
1804  int* colpnt2 = SCIPmatrixGetColIdxPtr(matrix, colpair.col2idx);
1805  SCIP_Real* valpnt2 = SCIPmatrixGetColValPtr(matrix, colpair.col2idx);
1806  SCIP_Real obj1 = SCIPvarGetObj(SCIPmatrixGetVar(matrix, colpair.col1idx));
1807  SCIP_Real obj2 = SCIPvarGetObj(SCIPmatrixGetVar(matrix, colpair.col2idx));
1808  int collen1 = SCIPmatrixGetColNNonzs(matrix, colpair.col1idx);
1809  int collen2 = SCIPmatrixGetColNNonzs(matrix, colpair.col2idx);
1810
1811  success = FALSE;
1812
1813  SCIP_CALL( combineCols(scip, colpnt1, colpnt2, valpnt1, valpnt2, obj1, obj2, collen1,
1814  collen2, nrows, TRUE, TRUE, lbdual, ubdual, &success) );
1815
1816  if( success )
1817  combinefails = 0;
1818  else
1819  combinefails++;
1820
1821  SCIP_CALL( SCIPhashsetInsert(pairhashset, SCIPblkmem(scip), encodeColPair(&colpair)) );
1822  ncombines++;
1823  if( ncombines >= maxcombines || combinefails >= presoldata->maxcombinefails )
1824  finished = TRUE;
1825 #ifdef SCIP_MORE_DEBUG
1826  SCIPdebugMsg(scip, "pm/mp: %d retrievefails before reset, %d combines\n", retrievefails, ncombines);
1827 #endif
1828  retrievefails = 0;
1829  }
1830  else if( retrievefails < presoldata->maxretrievefails )
1831  retrievefails++;
1832  else
1833  finished = TRUE;
1834  }
1835  if( finished )
1836  break;
1837  }
1838  if( finished )
1839  break;
1840  }
1841
1842  if( block1end < pospp && block2end < posmm )
1843  {
1844  findNextBlock(hashlistpp, pospp, &block1start, &block1end);
1845  findNextBlock(hashlistmm, posmm, &block2start, &block2end);
1846  }
1847  else
1848  finished = TRUE;
1849  }
1850  else if( hashlistpp[block1start] < hashlistmm[block2start] && block1end < pospp )
1851  findNextBlock(hashlistpp, pospp, &block1start, &block1end);
1852  else if( hashlistpp[block1start] > hashlistmm[block2start] && block2end < posmm )
1853  findNextBlock(hashlistmm, posmm, &block2start, &block2end);
1854  else
1855  finished = TRUE;
1856  }
1857  }
1858
1859  /* Process pm and mp lists */
1860  if( pospm > 0 && posmp > 0 )
1861  {
1862  SCIP_Longint maxcombines;
1863  SCIP_Longint ncombines;
1864  SCIP_Bool finished;
1865  SCIP_Bool success;
1866  int combinefails;
1867  int retrievefails;
1868  COLPAIR colpair;
1869
1870  finished = FALSE;
1871  block1start = 0;
1872  block1end = 0;
1873  block2start = 0;
1874  block2end = 0;
1875
1876  maxcombines = presoldata->maxpairfac == -1 ? SCIP_LONGINT_MAX : (((SCIP_Longint)ncols) * presoldata->maxpairfac);
1877
1878  ncombines = 0;
1879  combinefails = 0;
1880  retrievefails = 0;
1881  findNextBlock(hashlistpm, pospm, &block1start, &block1end);
1882  findNextBlock(hashlistmp, posmp, &block2start, &block2end);
1883 #ifdef SCIP_MORE_DEBUG
1884  SCIPdebugMsg(scip, "processing pm and mp\n");
1885 #endif
1886
1887  while( !finished )
1888  {
1889  if( hashlistpm[block1start] == hashlistmp[block2start] )
1890  {
1891  for( i = block1start; i < block1end; i++ )
1892  {
1893  for( j = block2start; j < block2end; j++ )
1894  {
1895  if( colidxlistpm[i] != colidxlistmp[j] )
1896  {
1897  colpair.col1idx = MIN(colidxlistpm[i], colidxlistmp[j]);
1898  colpair.col2idx = MAX(colidxlistpm[i], colidxlistmp[j]);
1899
1900  if( !SCIPhashsetExists(pairhashset, encodeColPair(&colpair)) )
1901  {
1902  int* colpnt1 = SCIPmatrixGetColIdxPtr(matrix, colpair.col1idx);
1903  SCIP_Real* valpnt1 = SCIPmatrixGetColValPtr(matrix, colpair.col1idx);
1904  int* colpnt2 = SCIPmatrixGetColIdxPtr(matrix, colpair.col2idx);
1905  SCIP_Real* valpnt2 = SCIPmatrixGetColValPtr(matrix, colpair.col2idx);
1906  SCIP_Real obj1 = SCIPvarGetObj(SCIPmatrixGetVar(matrix, colpair.col1idx));
1907  SCIP_Real obj2 = SCIPvarGetObj(SCIPmatrixGetVar(matrix, colpair.col2idx));
1908  int collen1 = SCIPmatrixGetColNNonzs(matrix, colpair.col1idx);
1909  int collen2 = SCIPmatrixGetColNNonzs(matrix, colpair.col2idx);
1910
1911  success = FALSE;
1912
1913  SCIP_CALL( combineCols(scip, colpnt1, colpnt2, valpnt1, valpnt2, obj1, obj2, collen1,
1914  collen2, nrows, TRUE, TRUE, lbdual, ubdual, &success) );
1915
1916  if( success )
1917  combinefails = 0;
1918  else
1919  combinefails++;
1920
1921  SCIP_CALL( SCIPhashsetInsert(pairhashset, SCIPblkmem(scip), encodeColPair(&colpair)) );
1922  ncombines++;
1923  if( ncombines >= maxcombines || combinefails >= presoldata->maxcombinefails )
1924  finished = TRUE;
1925
1926  retrievefails = 0;
1927  }
1928  else if( retrievefails < presoldata->maxretrievefails )
1929  retrievefails++;
1930  else
1931  finished = TRUE;
1932  }
1933  if( finished )
1934  break;
1935  }
1936  if( finished )
1937  break;
1938  }
1939
1940  if( block1end < pospm && block2end < posmp )
1941  {
1942  findNextBlock(hashlistpm, pospm, &block1start, &block1end);
1943  findNextBlock(hashlistmp, posmp, &block2start, &block2end);
1944  }
1945  else
1946  finished = TRUE;
1947  }
1948  else if( hashlistpm[block1start] < hashlistmp[block2start] && block1end < pospm )
1949  findNextBlock(hashlistpm, pospm, &block1start, &block1end);
1950  else if( hashlistpm[block1start] > hashlistmp[block2start] && block2end < posmp )
1951  findNextBlock(hashlistmp, posmp, &block2start, &block2end);
1952  else
1953  finished = TRUE;
1954  }
1955  }
1956
1957  SCIPhashsetFree(&pairhashset, SCIPblkmem(scip));
1958  SCIPfreeBlockMemoryArray(scip, &colidxlistmp, listsizemp);
1959  SCIPfreeBlockMemoryArray(scip, &colidxlistpm, listsizepm);
1960  SCIPfreeBlockMemoryArray(scip, &colidxlistmm, listsizemm);
1961  SCIPfreeBlockMemoryArray(scip, &colidxlistpp, listsizepp);
1962  SCIPfreeBlockMemoryArray(scip, &hashlistmp, listsizemp);
1963  SCIPfreeBlockMemoryArray(scip, &hashlistpm, listsizepm);
1964  SCIPfreeBlockMemoryArray(scip, &hashlistmm, listsizemm);
1965  SCIPfreeBlockMemoryArray(scip, &hashlistpp, listsizepp);
1966
1967 #ifdef SCIP_MORE_DEBUG
1968  SCIPdebugMsg(scip, "CombCols:\n");
1969  for( i = 0; i < nrows; i++ )
1970  {
1971  assert(SCIPisLE(scip,lbdual[i],ubdual[i]));
1972  SCIPdebugMsg(scip, "y%d=[%g,%g]\n",i,lbdual[i],ubdual[i]);
1973  }
1974  SCIPdebugMsg(scip,"\n");
1975 #endif
1976  }
1977
1978  SCIP_CALL( SCIPallocBufferArray(scip, &mincolact, ncols) );
1979  SCIP_CALL( SCIPallocBufferArray(scip, &mincolactinf, ncols) );
1980
1981  /* apply dual bound strengthening */
1982  loops = 0;
1983  boundchanges = 1;
1984  while( 0 < boundchanges && loops < presoldata->maxdualbndloops )
1985  {
1986  loops++;
1987  boundchanges = 0;
1988
1989  for( i = 0; i < nimplubvars; i++ )
1990  {
1991  assert(SCIPvarGetType(SCIPmatrixGetVar(matrix, implubvars[i])) == SCIP_VARTYPE_CONTINUOUS ||
1992  SCIPvarGetType(SCIPmatrixGetVar(matrix, implubvars[i])) == SCIP_VARTYPE_IMPLINT);
1993  calcMinColActivity(scip, matrix, implubvars[i], lbdual, ubdual, mincolact, mincolactinf);
1994  }
1995
1996  for( i = 0; i < nimplubvars; i++ )
1997  {
1998  SCIP_Real objval;
1999  SCIP_Bool ubinfchange;
2000  SCIP_Bool lbinfchange;
2001  int col;
2002
2003  col = implubvars[i];
2004  var = SCIPmatrixGetVar(matrix, col);
2005
2006  objval = SCIPvarGetObj(var);
2007  colpnt = SCIPmatrixGetColIdxPtr(matrix, col);
2008  colend = colpnt + SCIPmatrixGetColNNonzs(matrix, col);
2009  valpnt = SCIPmatrixGetColValPtr(matrix, col);
2010
2011  for( ; colpnt < colend; colpnt++, valpnt++ )
2012  {
2013  int row;
2014  SCIP_Real val;
2015  SCIP_Real mincolresact;
2016
2017  row = *colpnt;
2018  val = *valpnt;
2019
2020  calcMinColActResidual(scip, matrix, col, row, val, lbdual, ubdual,
2021  mincolact, mincolactinf, &mincolresact);
2022
2023  updateDualBounds(scip, matrix, objval, val, row, mincolresact,
2024  lbdual, ubdual, &boundchanges, &ubinfchange, &lbinfchange);
2025
2026  if( ubinfchange || lbinfchange )
2027  infinityCountUpdate(scip, matrix, row, lbdual, ubdual, isubimplied,
2028  mincolact, mincolactinf, ubinfchange, lbinfchange);
2029  }
2030  }
2031  }
2032
2033 #ifdef SCIP_MORE_DEBUG
2034  SCIPdebugMsg(scip, "BndStr:\n");
2035  for( i = 0; i < nrows; i++ )
2036  {
2037  assert(SCIPisLE(scip,lbdual[i],ubdual[i]));
2038  SCIPdebugMsg(scip, "y%d=[%g,%g]\n",i,lbdual[i],ubdual[i]);
2039  }
2040  SCIPdebugMsg(scip,"\n");
2041 #endif
2042
2043  SCIP_CALL( SCIPallocBufferArray(scip, &maxcolact, ncols) );
2044  SCIP_CALL( SCIPallocBufferArray(scip, &maxcolactinf, ncols) );
2045
2046  /* calculate final minimal and maximal column activities */
2047  for( i = 0; i < ncols; i++ )
2048  {
2049  calcMinColActivity(scip, matrix, i, lbdual, ubdual, mincolact, mincolactinf);
2050  calcMaxColActivity(scip, matrix, i, lbdual, ubdual, maxcolact, maxcolactinf);
2051  }
2052
2053  for( i = 0; i < ncols; i++ )
2054  {
2055  SCIP_Real objval;
2056
2057  var = SCIPmatrixGetVar(matrix, i);
2058
2059  /* do not fix variables if the locks do not match */
2060  if( SCIPmatrixUplockConflict(matrix, i) || SCIPmatrixDownlockConflict(matrix, i) )
2061  continue;
2062
2063  objval = SCIPvarGetObj(var);
2064
2065  /* c_j - sup(y^T A_{.j}) > 0 => fix x_j to its lower bound */
2066  if( SCIPisGT(scip, objval, maxcolact[i]) && varstofix[i] == NOFIX )
2067  {
2068  if( SCIPisGT(scip, SCIPvarGetLbGlobal(var), -SCIPinfinity(scip)) )
2069  {
2070  varstofix[i] = FIXATLB;
2071  (*npossiblefixings)++;
2072  }
2073  }
2074
2075  /* c_j - inf(y^T A_{.j}) < 0 => fix x_j to its upper bound */
2076  if( SCIPisLT(scip, objval, mincolact[i]) && varstofix[i] == NOFIX )
2077  {
2078  if( SCIPisLT(scip, SCIPvarGetUbGlobal(var), SCIPinfinity(scip)) )
2079  {
2080  varstofix[i] = FIXATUB;
2081  (*npossiblefixings)++;
2082  }
2083  }
2084  }
2085
2086  for( i = 0; i < nrows; i++ )
2087  {
2088  /* implied equality: y_i > 0 => A_{i.}x - b_i = 0 */
2089  if( SCIPmatrixIsRowRhsInfinity(matrix, i) )
2090  {
2091  if( SCIPisGT(scip, lbdual[i], 0.0) && (sidestochange[i] == NOCHANGE) )
2092  {
2093  /* change >= inequality to equality */
2094  sidestochange[i] = RHSTOLHS;
2095  (*npossiblesidechanges)++;
2096  }
2097  }
2098  else
2099  {
2100  if( !SCIPmatrixIsRowRhsInfinity(matrix, i) &&
2101  !SCIPisEQ(scip,SCIPmatrixGetRowLhs(matrix, i),SCIPmatrixGetRowRhs(matrix, i)) )
2102  {
2103  /* for ranged rows we have to decide which side (lhs or rhs) determines the equality */
2104  if( SCIPisGT(scip, lbdual[i], 0.0) && sidestochange[i]==NOCHANGE )
2105  {
2106  sidestochange[i] = RHSTOLHS;
2107  (*npossiblesidechanges)++;
2108  }
2109
2110  if( SCIPisLT(scip, ubdual[i], 0.0) && sidestochange[i]==NOCHANGE)
2111  {
2112  sidestochange[i] = LHSTORHS;
2113  (*npossiblesidechanges)++;
2114  }
2115  }
2116  }
2117  }
2118
2119  SCIPfreeBufferArray(scip, &maxcolactinf);
2120  SCIPfreeBufferArray(scip, &maxcolact);
2121  SCIPfreeBufferArray(scip, &mincolactinf);
2122  SCIPfreeBufferArray(scip, &mincolact);
2123
2124  SCIPfreeBufferArray(scip, &ubdual);
2125  SCIPfreeBufferArray(scip, &lbdual);
2126  SCIPfreeBufferArray(scip, &implubvars);
2127  SCIPfreeBufferArray(scip, &islbimplied);
2128  SCIPfreeBufferArray(scip, &isubimplied);
2129  SCIPfreeBufferArray(scip, &tmpubs);
2130  SCIPfreeBufferArray(scip, &tmplbs);
2131
2132  return SCIP_OKAY;
2133 }
2134
2135 /*
2136  * Callback methods of presolver
2137  */
2138
2139 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
2140 static
2141 SCIP_DECL_PRESOLCOPY(presolCopyDualinfer)
2142 { /*lint --e{715}*/
2143  assert(scip != NULL);
2144  assert(presol != NULL);
2145  assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
2146
2147  /* call inclusion method of presolver */
2149
2150  return SCIP_OKAY;
2151 }
2152
2153 /** destructor of presolver to free user data (called when SCIP is exiting) */
2154 static
2155 SCIP_DECL_PRESOLFREE(presolFreeDualinfer)
2156 { /*lint --e{715}*/
2157  SCIP_PRESOLDATA* presoldata;
2158
2159  /* free presolver data */
2160  presoldata = SCIPpresolGetData(presol);
2161  assert(presoldata != NULL);
2162
2163  SCIPfreeBlockMemory(scip, &presoldata);
2164  SCIPpresolSetData(presol, NULL);
2165
2166  return SCIP_OKAY;
2167 }
2168
2169 /** execution method of presolver */
2170 static
2171 SCIP_DECL_PRESOLEXEC(presolExecDualinfer)
2172 { /*lint --e{715}*/
2173  SCIP_MATRIX* matrix;
2174  SCIP_Bool initialized;
2175  SCIP_Bool complete;
2176  SCIP_Bool infeasible;
2177  SCIP_PRESOLDATA* presoldata;
2178  FIXINGDIRECTION* varstofix;
2179  int npossiblefixings;
2180  int nconvarsfixed;
2181  int nintvarsfixed;
2182  int nbinvarsfixed;
2183  SIDECHANGE* sidestochange;
2184  int npossiblesidechanges;
2185  int nsideschanged;
2186  int i;
2187  int nrows;
2188  int ncols;
2189  SCIP_VAR* var;
2190
2191  assert(result != NULL);
2192  *result = SCIP_DIDNOTRUN;
2193
2194  if( SCIPgetNContVars(scip) + SCIPgetNImplVars(scip) == 0 )
2195  return SCIP_OKAY;
2196
2197  /* the reductions made in this presolver apply to all optimal solutions because of complementary slackness */
2198  if( !SCIPallowWeakDualReds(scip) )
2199  return SCIP_OKAY;
2200
2201  *result = SCIP_DIDNOTFIND;
2202
2203  presoldata = SCIPpresolGetData(presol);
2204  assert(presoldata != NULL);
2205
2206  matrix = NULL;
2207  SCIP_CALL( SCIPmatrixCreate(scip, &matrix, TRUE, &initialized, &complete, &infeasible,
2208  naddconss, ndelconss, nchgcoefs, nchgbds, nfixedvars) );
2209
2210  /* if infeasibility was detected during matrix creation, return here */
2211  if( infeasible )
2212  {
2213  if( initialized )
2214  SCIPmatrixFree(scip, &matrix);
2215
2216  *result = SCIP_CUTOFF;
2217  return SCIP_OKAY;
2218  }
2219
2220  if( !initialized )
2221  return SCIP_OKAY;
2222
2223  npossiblefixings = 0;
2224  nconvarsfixed = 0;
2225  nintvarsfixed = 0;
2226  nbinvarsfixed = 0;
2227  npossiblesidechanges = 0;
2228  nsideschanged = 0;
2229
2230  nrows = SCIPmatrixGetNRows(matrix);
2231  ncols = SCIPmatrixGetNColumns(matrix);
2232
2233  SCIP_CALL( SCIPallocBufferArray(scip, &varstofix, ncols) );
2234  SCIP_CALL( SCIPallocBufferArray(scip, &sidestochange, nrows) );
2235
2236  BMSclearMemoryArray(varstofix, ncols);
2237  BMSclearMemoryArray(sidestochange, nrows);
2238
2239  SCIP_CALL( dualBoundStrengthening(scip, matrix, presoldata,
2240  varstofix, &npossiblefixings, sidestochange, &npossiblesidechanges) );
2241
2242  if( npossiblefixings > 0 )
2243  {
2244  for( i = ncols - 1; i >= 0; --i )
2245  {
2246  SCIP_Bool fixed;
2247
2248  var = SCIPmatrixGetVar(matrix, i);
2249
2250  /* there should be no fixings for variables with inconsistent locks */
2251  assert(varstofix[i] == NOFIX || (!SCIPmatrixUplockConflict(matrix, i) && !SCIPmatrixDownlockConflict(matrix, i)));
2252
2253  fixed = FALSE;
2254
2255  if( varstofix[i] == FIXATLB )
2256  {
2257  SCIP_Real lb;
2258  lb = SCIPvarGetLbLocal(var);
2259
2260  /* fix at lower bound */
2261  SCIP_CALL( SCIPfixVar(scip, var, lb, &infeasible, &fixed) );
2262  if( infeasible )
2263  {
2264  SCIPdebugMsg(scip, " -> infeasible fixing\n");
2265  *result = SCIP_CUTOFF;
2266  break;
2267  }
2268  assert(fixed);
2269  (*nfixedvars)++;
2270  *result = SCIP_SUCCESS;
2271  }
2272  else if( varstofix[i] == FIXATUB )
2273  {
2274  SCIP_Real ub;
2275  ub = SCIPvarGetUbLocal(var);
2276
2277  /* fix at upper bound */
2278  SCIP_CALL( SCIPfixVar(scip, var, ub, &infeasible, &fixed) );
2279  if( infeasible )
2280  {
2281  SCIPdebugMsg(scip, " -> infeasible fixing\n");
2282  *result = SCIP_CUTOFF;
2283  break;
2284  }
2285  assert(fixed);
2286  (*nfixedvars)++;
2287  *result = SCIP_SUCCESS;
2288  }
2289
2290  /* keep a small statistic which types of variables are fixed */
2291  if( fixed )
2292  {
2294  nconvarsfixed++;
2295  else if( SCIPvarGetType(var) == SCIP_VARTYPE_BINARY )
2296  nbinvarsfixed++;
2297  else
2298  nintvarsfixed++;
2299  }
2300  }
2301  }
2302
2303  if( npossiblesidechanges > 0 )
2304  {
2305  for( i = 0; i < nrows; i++ )
2306  {
2307  SCIP_CONS* cons;
2308  SCIP_CONSHDLR* conshdlr;
2309  const char* conshdlrname;
2310
2311  if( sidestochange[i] == NOCHANGE )
2312  continue;
2313
2314  if( presoldata->maxrowsupport < SCIPmatrixGetRowNNonzs(matrix, i) )
2315  continue;
2316
2317  cons = SCIPmatrixGetCons(matrix,i);
2318  conshdlr = SCIPconsGetHdlr(cons);
2319  conshdlrname = SCIPconshdlrGetName(conshdlr);
2320
2321  if( strcmp(conshdlrname, "linear") == 0 )
2322  {
2323  SCIP_Real lhs;
2324  SCIP_Real rhs;
2325  SCIP_Real matrixlhs;
2326  SCIP_Real matrixrhs;
2327
2328  lhs = SCIPgetLhsLinear(scip, cons);
2329  rhs = SCIPgetRhsLinear(scip, cons);
2330  matrixlhs = SCIPmatrixGetRowLhs(matrix, i);
2331  matrixrhs = SCIPmatrixGetRowRhs(matrix, i);
2332
2333  assert(!SCIPisEQ(scip, matrixlhs, matrixrhs));
2334
2335  /* when creating the matrix, contraints are multiplied if necessary by (-1)
2336  * to ensure that the following representation is obtained:
2337  * infty >= a x >= b
2338  * or
2339  * c >= ax >= b (ranged rows)
2340  */
2341
2342  /* for ranged constraints we have to distinguish between both sides */
2343  if( sidestochange[i] == RHSTOLHS )
2344  {
2345  if( SCIPisEQ(scip, matrixlhs, lhs) )
2346  {
2347  /* change rhs to lhs */
2348  SCIP_CALL( SCIPchgRhsLinear(scip, cons, matrixlhs) );
2349  }
2350  else
2351  {
2352  /* consider multiplication by (-1) in the matrix */
2353  SCIP_CALL( SCIPchgLhsLinear(scip, cons, -matrixlhs) );
2354  }
2355
2356  nsideschanged++;
2357  (*nchgsides)++;
2358  }
2359  else if( sidestochange[i] == LHSTORHS )
2360  {
2361  if( SCIPisEQ(scip, matrixrhs, rhs) )
2362  {
2363  /* change lhs to rhs */
2364  SCIP_CALL( SCIPchgLhsLinear(scip, cons, matrixrhs) );
2365  }
2366  else
2367  {
2368  /* consider multiplication by (-1) in the matrix */
2369  SCIP_CALL( SCIPchgRhsLinear(scip, cons, -matrixrhs) );
2370  }
2371
2372  nsideschanged++;
2373  (*nchgsides)++;
2374  }
2375  }
2376  }
2377  }
2378
2379  SCIPfreeBufferArray(scip, &sidestochange);
2380  SCIPfreeBufferArray(scip, &varstofix);
2381
2382  if( (nconvarsfixed + nintvarsfixed + nbinvarsfixed) > 0 || npossiblesidechanges > 0 )
2383  {
2384  SCIPdebugMsg(scip, "### fixed vars [cont: %d, int: %d, bin: %d], changed sides [%d]\n",
2385  nconvarsfixed, nintvarsfixed, nbinvarsfixed, nsideschanged);
2386  }
2387
2388  SCIPmatrixFree(scip, &matrix);
2389
2390  return SCIP_OKAY;
2391 }
2392
2393
2394 /*
2395  * presolver specific interface methods
2396  */
2397
2398 /** creates the dual inference presolver and includes it in SCIP */
2400  SCIP* scip /**< SCIP data structure */
2401  )
2402 {
2403  SCIP_PRESOL* presol;
2404  SCIP_PRESOLDATA* presoldata;
2405
2406  /* create presolver data */
2407  SCIP_CALL( SCIPallocBlockMemory(scip, &presoldata) );
2408
2409  /* include presolver */
2411  PRESOL_TIMING, presolExecDualinfer, presoldata) );
2412  SCIP_CALL( SCIPsetPresolCopy(scip, presol, presolCopyDualinfer) );
2413  SCIP_CALL( SCIPsetPresolFree(scip, presol, presolFreeDualinfer) );
2414
2416  "presolving/dualinfer/twocolcombine",
2417  "use convex combination of columns for determining dual bounds",
2418  &presoldata->usetwocolcombine, FALSE, DEFAULT_TWOCOLUMN_COMBINE, NULL, NULL) );
2419
2421  "presolving/dualinfer/maxdualbndloops",
2422  "maximal number of dual bound strengthening loops",
2423  &presoldata->maxdualbndloops, FALSE, DEFAULT_MAXLOOPS_DUALBNDSTR, -1, INT_MAX, NULL, NULL) );
2424
2426  "presolving/dualinfer/maxconsiderednonzeros",
2427  "maximal number of considered non-zeros within one column (-1: no limit)",
2428  &presoldata->maxconsiderednonzeros, TRUE, DEFAULT_MAXCONSIDEREDNONZEROS, -1, INT_MAX, NULL, NULL) );
2429
2431  "presolving/dualinfer/maxretrievefails",
2432  "maximal number of consecutive useless hashtable retrieves",
2433  &presoldata->maxretrievefails, TRUE, DEFAULT_MAXRETRIEVEFAILS, -1, INT_MAX, NULL, NULL) );
2434
2436  "presolving/dualinfer/maxcombinefails",
2437  "maximal number of consecutive useless column combines",
2438  &presoldata->maxcombinefails, TRUE, DEFAULT_MAXCOMBINEFAILS, -1, INT_MAX, NULL, NULL) );
2439
2441  "presolving/dualinfer/maxhashfac",
2442  "Maximum number of hashlist entries as multiple of number of columns in the problem (-1: no limit)",
2443  &presoldata->maxhashfac, TRUE, DEFAULT_MAXHASHFAC, -1, INT_MAX, NULL, NULL) );
2444
2446  "presolving/dualinfer/maxpairfac",
2447  "Maximum number of processed column pairs as multiple of the number of columns in the problem (-1: no limit)",
2448  &presoldata->maxpairfac, TRUE, DEFAULT_MAXPAIRFAC, -1, INT_MAX, NULL, NULL) );
2449
2451  "presolving/dualinfer/maxrowsupport",
2452  "Maximum number of row's non-zeros for changing inequality to equality",
2453  &presoldata->maxrowsupport, FALSE, DEFAULT_MAXROWSUPPORT, 2, INT_MAX, NULL, NULL) );
2454
2455  return SCIP_OKAY;
2456 }
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:101
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:96
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:90
struct SCIP_PresolData SCIP_PRESOLDATA
Definition: type_presol.h:42
static SCIP_RETCODE addEntry(SCIP *scip, int *pos, int *listsize, int **hashlist, int **colidxlist, int hash, int colidx)
SCIP_VAR * SCIPmatrixGetVar(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1620
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:84
int SCIPmatrixGetNRows(SCIP_MATRIX *matrix)
Definition: matrix.c:1692
SCIP_RETCODE SCIPsetPresolFree(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLFREE((*presolfree)))
Definition: scip_presol.c:147
SCIP_RETCODE SCIPcreateConsBasicLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs)
#define DEFAULT_MAXROWSUPPORT
public methods for memory management
#define DEFAULT_TWOCOLUMN_COMBINE
#define PRESOL_TIMING
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17910
#define SCIP_MAXSTRLEN
Definition: def.h:293
SCIP_CONS * SCIPmatrixGetCons(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1820
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:130
SideChange
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17966
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static void calcMinColActResidual(SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real val, SCIP_Real *lbdual, SCIP_Real *ubdual, SCIP_Real *mincolact, int *mincolactinf, SCIP_Real *mincolresact)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1245
void SCIPmatrixFree(SCIP *scip, SCIP_MATRIX **matrix)
Definition: matrix.c:1032
#define FALSE
Definition: def.h:87
public methods for presolving plugins
static void updateDualBounds(SCIP *scip, SCIP_MATRIX *matrix, SCIP_Real objval, SCIP_Real val, int row, SCIP_Real mincolresact, SCIP_Real *lbdual, SCIP_Real *ubdual, int *boundchanges, SCIP_Bool *ubinfchange, SCIP_Bool *lbinfchange)
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10755
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
#define TRUE
Definition: def.h:86
SCIP_RETCODE SCIPhashsetCreate(SCIP_HASHSET **hashset, BMS_BLKMEM *blkmem, int size)
Definition: misc.c:3699
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_RETCODE SCIPwriteOrigProblem(SCIP *scip, const char *filename, const char *extension, SCIP_Bool genericnames)
Definition: scip_prob.c:600
SCIP_PRESOLDATA * SCIPpresolGetData(SCIP_PRESOL *presol)
Definition: presol.c:503
SCIP_Bool SCIPhashsetExists(SCIP_HASHSET *hashset, void *element)
Definition: misc.c:3757
SCIP_RETCODE SCIPcreateVarBasic(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype)
Definition: scip_var.c:185
static void findNextBlock(int *list, int len, int *start, int *end)
static int hashIndexPair(int idx1, int idx2)
public methods for problem variables
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:99
static void infinityCountUpdate(SCIP *scip, SCIP_MATRIX *matrix, int row, SCIP_Real *lbdual, SCIP_Real *ubdual, SCIP_Bool *isubimplied, SCIP_Real *mincolact, int *mincolactinf, SCIP_Bool ubinfchange, SCIP_Bool lbinfchange)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIP_LONGINT_MAX
Definition: def.h:163
#define PRESOL_MAXROUNDS
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:283
public methods for SCIP variables
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:111
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:74
SCIP_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
int SCIPgetNContVars(SCIP *scip)
Definition: scip_prob.c:2171
SCIP_RETCODE SCIPcreateProbBasic(SCIP *scip, const char *name)
Definition: scip_prob.c:171
public methods for numerical tolerances
enum Fixingdirection FIXINGDIRECTION
int SCIPmatrixGetRowNNonzs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1668
static void * encodeColPair(COLPAIR *colpair)
static SCIP_RETCODE combineCols(SCIP *scip, int *row1idxptr, int *row2idxptr, SCIP_Real *row1valptr, SCIP_Real *row2valptr, SCIP_Real b1, SCIP_Real b2, int row1len, int row2len, int ncols, SCIP_Bool swaprow1, SCIP_Bool swaprow2, SCIP_Real *lbs, SCIP_Real *ubs, SCIP_Bool *success)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17920
SCIP_Real SCIPmatrixGetRowLhs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1702
public methods for managing constraints
static void getVarBoundsOfRow(SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real val, SCIP_Real *lbs, SCIP_Real *ubs, SCIP_Real *rowub, SCIP_Bool *ubfound, SCIP_Real *rowlb, SCIP_Bool *lbfound)
SCIP_RETCODE SCIPsetObjsense(SCIP *scip, SCIP_OBJSENSE objsense)
Definition: scip_prob.c:1241
enum Fixingdirection FIXINGDIRECTION
Definition: presol_domcol.c:96
Fixingdirection
Definition: presol_domcol.c:90
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2613
SCIP_Real * SCIPmatrixGetColValPtr(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1528
static SCIP_Real getMinColActWithoutRow(SCIP *scip, SCIP_MATRIX *matrix, int col, int withoutrow, SCIP_Real *lbdual, SCIP_Real *ubdual)
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4175
Definition: scip_prob.c:2769
static SCIP_RETCODE dualBoundStrengthening(SCIP *scip, SCIP_MATRIX *matrix, SCIP_PRESOLDATA *presoldata, FIXINGDIRECTION *varstofix, int *npossiblefixings, SIDECHANGE *sidestochange, int *npossiblesidechanges)
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_RETCODE solveLP(SCIP *scip, SCIP_DIVESET *diveset, SCIP_Longint maxnlpiterations, SCIP_DIVECONTEXT divecontext, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: heuristics.c:37
void SCIPpresolSetData(SCIP_PRESOL *presol, SCIP_PRESOLDATA *presoldata)
Definition: presol.c:513
void SCIPhashsetFree(SCIP_HASHSET **hashset, BMS_BLKMEM *blkmem)
Definition: misc.c:3730
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:420
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip_general.c:474
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:48
SCIP_RETCODE SCIPcheckSolOrig(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *feasible, SCIP_Bool printreason, SCIP_Bool completely)
Definition: scip_sol.c:3497
int * SCIPmatrixGetRowIdxPtr(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1656
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17251
#define NULL
Definition: lpi_spx1.cpp:155
static SCIP_DECL_PRESOLCOPY(presolCopyDualinfer)
#define SCIP_CALL(x)
Definition: def.h:384
#define SCIPhashTwo(a, b)
Definition: pub_misc.h:510
SCIP_RETCODE SCIPmatrixCreate(SCIP *scip, SCIP_MATRIX **matrixptr, SCIP_Bool onlyifcomplete, SCIP_Bool *initialized, SCIP_Bool *complete, SCIP_Bool *infeasible, int *naddconss, int *ndelconss, int *nchgcoefs, int *nchgbds, int *nfixedvars)
Definition: matrix.c:445
SCIP_Real * SCIPmatrixGetRowValPtr(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1644
SCIP_Bool SCIPmatrixDownlockConflict(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1844
SCIP_RETCODE SCIPincludePresolDualinfer(SCIP *scip)
#define DEFAULT_MAXHASHFAC
SCIP_RETCODE SCIPchgVarObj(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition: scip_var.c:4510
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
SCIP_RETCODE SCIPfreeTransform(SCIP *scip)
Definition: scip_solve.c:3432
static SCIP_DECL_PRESOLFREE(presolFreeDualinfer)
#define SCIP_Bool
Definition: def.h:84
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
int SCIPgetNImplVars(SCIP *scip)
Definition: scip_prob.c:2126
#define DEFAULT_MAXRETRIEVEFAILS
#define MAX(x, y)
Definition: tclique_def.h:83
int * SCIPmatrixGetColIdxPtr(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1540
#define DEFAULT_MAXLOOPS_DUALBNDSTR
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8105
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:478
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
Definition: presol.c:590
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17758
SCIP_Bool SCIPallowWeakDualReds(SCIP *scip)
Definition: scip_var.c:8653
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip_var.c:8273
#define PRESOL_NAME
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1435
static void calcMaxColActivity(SCIP *scip, SCIP_MATRIX *matrix, int col, SCIP_Real *lbdual, SCIP_Real *ubdual, SCIP_Real *maxcolact, int *maxcolactinf)
Constraint handler for linear constraints in their most general form, .
SCIP_RETCODE SCIPchgRhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real rhs)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
public methods for matrix
static void getMinMaxActivityResiduals(SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real *lbs, SCIP_Real *ubs, SCIP_Real *minresactivity, SCIP_Real *maxresactivity, SCIP_Bool *isminsettoinfinity, SCIP_Bool *ismaxsettoinfinity)
#define PRESOL_PRIORITY
#define DEFAULT_MAXCONSIDEREDNONZEROS
SCIP_VAR ** b
Definition: circlepacking.c:56
static void calcMinColActivity(SCIP *scip, SCIP_MATRIX *matrix, int col, SCIP_Real *lbdual, SCIP_Real *ubdual, SCIP_Real *mincolact, int *mincolactinf)
public methods for presolvers
general public methods
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2304
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_RETCODE determineBestBounds(SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, SCIP_Real boundswitch, int usevbds, SCIP_Bool allowlocal, SCIP_Bool fixintegralrhs, SCIP_Bool ignoresol, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, SCIP_Real *bestlb, SCIP_Real *bestub, int *bestlbtype, int *bestubtype, SCIP_BOUNDTYPE *selectedbound, SCIP_Bool *freevariable)
Definition: cuts.c:2637
dual inference presolver
Definition: scip_prob.c:1667
SCIP_Real SCIPmatrixGetRowRhs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1714
enum SideChange SIDECHANGE
public methods for the probing mode
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
SCIP_Bool SCIPmatrixIsRowRhsInfinity(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1726
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLCOPY((*presolcopy)))
Definition: scip_presol.c:131
public methods for message output
SCIP_VAR * a
Definition: circlepacking.c:57
SCIP_RETCODE SCIPhashsetInsert(SCIP_HASHSET *hashset, BMS_BLKMEM *blkmem, void *element)
Definition: misc.c:3740
#define SCIP_Real
Definition: def.h:177
public methods for message handling
SCIP_Bool SCIPmatrixUplockConflict(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1832
#define SCIP_Longint
Definition: def.h:162
static SCIP_DECL_PRESOLEXEC(presolExecDualinfer)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17416
#define PRESOL_DESC
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPchgLhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs)
static void getImpliedBounds(SCIP *scip, SCIP_MATRIX *matrix, int col, SCIP_Real *lbs, SCIP_Real *ubs, SCIP_Bool *ubimplied, SCIP_Bool *lbimplied)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17976
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:123
SCIPallocBlockMemory(scip, subsol))
#define DEFAULT_MAXPAIRFAC
public methods for global and local (sub)problems
default SCIP plugins
#define DEFAULT_MAXCOMBINEFAILS
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
int SCIPmatrixGetNColumns(SCIP_MATRIX *matrix)
Definition: matrix.c:1564
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:48
void SCIPsortIntReal(int *intarray, SCIP_Real *realarray, int len)
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:315
int SCIPmatrixGetColNNonzs(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1552
memory allocation routines