Scippy

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