Scippy

SCIP

Solving Constraint Integer Programs

presol_domcol.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2017 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file presol_domcol.c
17  * @ingroup PRESOLVERS
18  * @brief dominated column presolver
19  * @author Dieter Weninger
20  * @author Gerald Gamrath
21  *
22  * This presolver looks for dominance relations between variable pairs.
23  * From a dominance relation and certain bound/clique-constellations
24  * variable fixings mostly at the lower bound of the dominated variable can be derived.
25  * Additionally it is possible to improve bounds by predictive bound strengthening.
26  *
27  * @todo Also run on general CIPs, if the number of locks of the investigated variables comes only from (upgraded)
28  * linear constraints.
29  *
30  * @todo Instead of choosing variables for comparison out of one row, we should try to use 'hashvalues' for columns that
31  * indicate in which constraint type (<=, >=, or ranged row / ==) they are existing. Then sort the variables (and
32  * corresponding data) after the ranged row/equation hashvalue and only try to derive dominance on variables with
33  * the same hashvalue on ranged row/equation and fitting hashvalues for the other constraint types.
34  *
35  */
36 
37 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
38 
39 #include <stdio.h>
40 #include <assert.h>
41 #include <string.h>
42 
43 #include "scip/pub_matrix.h"
44 #include "presol_domcol.h"
45 
46 #define PRESOL_NAME "domcol"
47 #define PRESOL_DESC "dominated column presolver"
48 #define PRESOL_PRIORITY -1000 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */
49 #define PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
50 #define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */
51 
52 #define DEFAULT_NUMMINPAIRS 1024 /**< minimal number of pair comparisons */
53 #define DEFAULT_NUMMAXPAIRS 1048576 /**< maximal number of pair comparisons */
54 
55 #define DEFAULT_PREDBNDSTR FALSE /**< should predictive bound strengthening be applied? */
56 #define DEFAULT_CONTINUOUS_RED TRUE /**< should reductions for continuous variables be carried out? */
57 
58 
59 
60 /*
61  * Data structures
62  */
63 
64 /** control parameters */
65 struct SCIP_PresolData
66 {
67  int numminpairs; /**< minimal number of pair comparisons */
68  int nummaxpairs; /**< maximal number of pair comparisons */
69  int numcurrentpairs; /**< current number of pair comparisons */
70  SCIP_Bool predbndstr; /**< flag indicating if predictive bound strengthening should be applied */
71  SCIP_Bool continuousred; /**< flag indicating if reductions for continuous variables should be performed */
72 };
73 
74 /** type of fixing direction */
75 enum Fixingdirection
76 {
77  FIXATLB = -1, /**< fix variable at lower bound */
78  NOFIX = 0, /**< do not fix variable */
79  FIXATUB = 1 /**< fix variable at upper bound */
80 };
81 typedef enum Fixingdirection FIXINGDIRECTION;
82 
83 
84 /*
85  * Local methods
86  */
87 #ifdef SCIP_DEBUG
88 /** print a row from the constraint matrix */
89 static
90 void printRow(
91  SCIP* scip, /**< SCIP main data structure */
92  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
93  int row /**< row index for printing */
94  )
95 {
96  int* rowpnt;
97  int* rowend;
98  int c;
99  SCIP_Real val;
100  SCIP_Real* valpnt;
101  char relation;
102  SCIP_VAR* var;
103 
104  relation='-';
105  if( !SCIPmatrixIsRowRhsInfinity(matrix, row) &&
106  SCIPisEQ(scip, SCIPmatrixGetRowLhs(matrix, row), SCIPmatrixGetRowRhs(matrix, row)) )
107  {
108  relation='e';
109  }
110  else if( !SCIPmatrixIsRowRhsInfinity(matrix, row) &&
111  !SCIPisEQ(scip, SCIPmatrixGetRowLhs(matrix, row), SCIPmatrixGetRowRhs(matrix, row)) )
112  {
113  relation='r';
114  }
115  else
116  {
117  relation='g';
118  }
119 
120  rowpnt = SCIPmatrixGetRowIdxPtr(matrix, row);
121  rowend = rowpnt + SCIPmatrixGetRowNNonzs(matrix, row);
122  valpnt = SCIPmatrixGetRowValPtr(matrix, row);
123 
124  SCIPdebugMsgPrint(scip, "\n(L:%g) [%c] %g <=",
125  (SCIPmatrixGetRowNMinActPosInf(matrix, row) + SCIPmatrixGetRowNMinActNegInf(matrix,row) > 0) ?
126  -SCIPinfinity(scip) :
127  SCIPmatrixGetRowMinActivity(matrix, row), relation, SCIPmatrixGetRowLhs(matrix, row));
128  for(; (rowpnt < rowend); rowpnt++, valpnt++)
129  {
130  c = *rowpnt;
131  val = *valpnt;
132  var = SCIPmatrixGetVar(matrix, c);
133  SCIPdebugMsgPrint(scip, " %g{%s[idx:%d][bnd:%g,%g]}",
134  val, SCIPvarGetName(var), c, SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var));
135  }
136  SCIPdebugMsgPrint(scip, " <= %g (U:%g)", (SCIPmatrixGetRowNMaxActPosInf(matrix, row) + SCIPmatrixGetRowNMaxActNegInf(matrix, row) > 0) ?
137  SCIPinfinity(scip) :
138  SCIPmatrixGetRowRhs(matrix, row), SCIPmatrixGetRowMaxActivity(matrix , row));
139 }
140 
141 /** print all rows from the constraint matrix containing a variable */
142 static
143 SCIP_RETCODE printRowsOfCol(
144  SCIP* scip, /**< SCIP main data structure */
145  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
146  int col /**< column index for printing */
147  )
148 {
149  int numrows;
150  int* rows;
151  int i;
152  int* colpnt;
153  int* colend;
154 
155  numrows = SCIPmatrixGetColNNonzs(matrix, col);
156 
157  SCIP_CALL( SCIPallocBufferArray(scip, &rows, numrows) );
158 
159  colpnt = SCIPmatrixGetColIdxPtr(matrix, col);
160  colend = colpnt + SCIPmatrixGetColNNonzs(matrix, col);
161  for( i = 0; (colpnt < colend); colpnt++, i++ )
162  {
163  rows[i] = *colpnt;
164  }
165 
166  SCIPdebugMsgPrint(scip, "\n-------");
167  SCIPdebugMsgPrint(scip, "\ncol %d number rows: %d",col,numrows);
168  for( i = 0; i < numrows; i++ )
169  {
170  printRow(scip, matrix, rows[i]);
171  }
172  SCIPdebugMsgPrint(scip, "\n-------");
173 
174  SCIPfreeBufferArray(scip, &rows);
175 
176  return SCIP_OKAY;
177 }
178 
179 /** print information about a dominance relation */
180 static
181 SCIP_RETCODE printDomRelInfo(
182  SCIP* scip, /**< SCIP main data structure */
183  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
184  SCIP_VAR* dominatingvar, /**< dominating variable */
185  int dominatingidx, /**< index of dominating variable */
186  SCIP_VAR* dominatedvar, /**< dominated variable */
187  int dominatedidx, /**< index of dominated variable */
188  SCIP_Real dominatingub, /**< predicted upper bound of dominating variable */
189  SCIP_Real dominatingwclb /**< worst case lower bound of dominating variable */
190  )
191 {
192  char type;
193 
194  assert(SCIPvarGetType(dominatingvar)==SCIPvarGetType(dominatedvar));
195 
196  switch(SCIPvarGetType(dominatingvar))
197  {
198  case SCIP_VARTYPE_CONTINUOUS:
199  type='C';
200  break;
201  case SCIP_VARTYPE_BINARY:
202  type='B';
203  break;
204  case SCIP_VARTYPE_INTEGER:
205  case SCIP_VARTYPE_IMPLINT:
206  type='I';
207  break;
208  default:
209  SCIPerrorMessage("unknown variable type\n");
210  SCIPABORT();
211  return SCIP_INVALIDDATA; /*lint !e527*/
212  }
213 
214  SCIPdebugMsgPrint(scip, "\n\n### [%c], obj:%g->%g,\t%s[idx:%d](nrows:%d)->%s[idx:%d](nrows:%d)\twclb=%g, ub'=%g, ub=%g",
215  type, SCIPvarGetObj(dominatingvar), SCIPvarGetObj(dominatedvar),
216  SCIPvarGetName(dominatingvar), dominatingidx, SCIPmatrixGetColNNonzs(matrix, dominatingidx),
217  SCIPvarGetName(dominatedvar), dominatedidx, SCIPmatrixGetColNNonzs(matrix, dominatedidx),
218  dominatingwclb, dominatingub, SCIPvarGetUbGlobal(dominatingvar));
219 
220  SCIP_CALL( printRowsOfCol(scip, matrix, dominatingidx) );
221 
222  return SCIP_OKAY;
223 }
224 #endif
225 
226 
227 /** get minimum/maximum residual activity for the specified variable and with another variable set to its upper bound */
228 static
229 void getActivityResidualsUpperBound(
230  SCIP* scip,
231  SCIP_MATRIX* matrix,
232  int row,
233  int col,
234  SCIP_Real coef,
235  int upperboundcol,
236  SCIP_Real upperboundcoef,
237  SCIP_Real* minresactivity,
238  SCIP_Real* maxresactivity,
239  SCIP_Bool* success
240  )
241 {
242  SCIP_VAR* var;
243  SCIP_VAR* upperboundvar;
244  SCIP_Real lb;
245  SCIP_Real ub;
246  SCIP_Real lbupperboundvar;
247  SCIP_Real ubupperboundvar;
248  SCIP_Real tmpmaxact;
249  SCIP_Real tmpminact;
250  int maxactinf;
251  int minactinf;
252 
253  assert(scip != NULL);
254  assert(matrix != NULL);
255  assert(row < SCIPmatrixGetNRows(matrix));
256  assert(minresactivity != NULL);
257  assert(maxresactivity != NULL);
258 
259  var = SCIPmatrixGetVar(matrix, col);
260  upperboundvar = SCIPmatrixGetVar(matrix, upperboundcol);
261  assert(var != NULL);
262  assert(upperboundvar != NULL);
263 
264  lb = SCIPvarGetLbGlobal(var);
265  ub = SCIPvarGetUbGlobal(var);
266 
267  maxactinf = SCIPmatrixGetRowNMaxActPosInf(matrix, row) + SCIPmatrixGetRowNMaxActNegInf(matrix, row);
268  minactinf = SCIPmatrixGetRowNMinActPosInf(matrix, row) + SCIPmatrixGetRowNMinActNegInf(matrix, row);
269 
270  assert(!SCIPisInfinity(scip, lb));
271  assert(!SCIPisInfinity(scip, -ub));
272 
273  lbupperboundvar = SCIPvarGetLbGlobal(upperboundvar);
274  ubupperboundvar = SCIPvarGetUbGlobal(upperboundvar);
275 
276  assert(!SCIPisInfinity(scip, lbupperboundvar));
277  assert(!SCIPisInfinity(scip, -ubupperboundvar));
278 
279  tmpminact = SCIPmatrixGetRowMinActivity(matrix, row);
280  tmpmaxact = SCIPmatrixGetRowMaxActivity(matrix, row);
281 
282  /* first, adjust min and max activity such that upperboundvar is always set to its upper bound */
283 
284  /* abort if the upper bound is infty */
285  if( SCIPisInfinity(scip, ubupperboundvar) )
286  {
287  *success = FALSE;
288  return;
289  }
290  else
291  {
292  /* coef > 0 --> the lower bound is used for the minactivity --> update the minactivity */
293  if( upperboundcoef > 0.0 )
294  {
295  if( SCIPisInfinity(scip, -lbupperboundvar) )
296  {
297  assert(minactinf > 0);
298  minactinf--;
299  tmpminact += (upperboundcoef * ubupperboundvar);
300  }
301  else
302  {
303  tmpminact = tmpminact - (upperboundcoef * lbupperboundvar) + (upperboundcoef * ubupperboundvar);
304  }
305  }
306  /* coef < 0 --> the lower bound is used for the maxactivity --> update the maxactivity */
307  else
308  {
309  if( SCIPisInfinity(scip, -lbupperboundvar) )
310  {
311  assert(maxactinf > 0);
312  maxactinf--;
313  tmpmaxact += (upperboundcoef * ubupperboundvar);
314  }
315  else
316  {
317  tmpmaxact = tmpmaxact - (upperboundcoef * lbupperboundvar) + (upperboundcoef * ubupperboundvar);
318  }
319  }
320  }
321 
322  *success = TRUE;
323 
324  /* the coefficient is positive, so the upper bound contributed to the maxactivity and the lower bound to the minactivity */
325  if( coef >= 0.0 )
326  {
327  if( SCIPisInfinity(scip, ub) )
328  {
329  assert(maxactinf >= 1);
330  if( maxactinf == 1 )
331  {
332  *maxresactivity = tmpmaxact;
333  }
334  else
335  *maxresactivity = SCIPinfinity(scip);
336  }
337  else
338  {
339  if( maxactinf > 0 )
340  *maxresactivity = SCIPinfinity(scip);
341  else
342  *maxresactivity = tmpmaxact - coef * ub;
343  }
344 
345  if( SCIPisInfinity(scip, -lb) )
346  {
347  assert(minactinf >= 1);
348  if( minactinf == 1 )
349  {
350  *minresactivity = tmpminact;
351  }
352  else
353  *minresactivity = -SCIPinfinity(scip);
354  }
355  else
356  {
357  if( minactinf > 0 )
358  *minresactivity = -SCIPinfinity(scip);
359  else
360  *minresactivity = tmpminact - coef * lb;
361  }
362  }
363  /* the coefficient is negative, so the lower bound contributed to the maxactivity and the upper bound to the minactivity */
364  else
365  {
366  if( SCIPisInfinity(scip, -lb) )
367  {
368  assert(maxactinf >= 1);
369  if( maxactinf == 1 )
370  {
371  *maxresactivity = tmpmaxact;
372  }
373  else
374  *maxresactivity = SCIPinfinity(scip);
375  }
376  else
377  {
378  if( maxactinf > 0 )
379  *maxresactivity = SCIPinfinity(scip);
380  else
381  *maxresactivity = tmpmaxact - coef * lb;
382  }
383 
384  if( SCIPisInfinity(scip, ub) )
385  {
386  assert(minactinf >= 1);
387  if( minactinf == 1 )
388  {
389  *minresactivity = tmpminact;
390  }
391  else
392  *minresactivity = -SCIPinfinity(scip);
393  }
394  else
395  {
396  if( minactinf > 0 )
397  *minresactivity = -SCIPinfinity(scip);
398  else
399  *minresactivity = tmpminact - coef * ub;
400  }
401  }
402 }
403 
404 /** get minimum/maximum residual activity for the specified variable and with another variable set to its lower bound */
405 static
406 void getActivityResidualsLowerBound(
407  SCIP* scip, /**< SCIP main data structure */
408  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
409  int row, /**< row index */
410  int col, /**< column index */
411  SCIP_Real coef, /**< coefficient of the column in this row */
412  int lowerboundcol, /**< column index of variable to set to its lower bound */
413  SCIP_Real lowerboundcoef, /**< coefficient in this row of the column to be set to its lower bound */
414  SCIP_Real* minresactivity, /**< minimum residual activity of this row */
415  SCIP_Real* maxresactivity, /**< maximum residual activity of this row */
416  SCIP_Bool* success /**< pointer to store whether the computation was successful */
417  )
418 {
419  SCIP_VAR* var;
420  SCIP_VAR* lowerboundvar;
421  SCIP_Real lb;
422  SCIP_Real ub;
423  SCIP_Real lblowerboundvar;
424  SCIP_Real ublowerboundvar;
425  SCIP_Real tmpmaxact;
426  SCIP_Real tmpminact;
427  int maxactinf;
428  int minactinf;
429 
430  assert(scip != NULL);
431  assert(matrix != NULL);
432  assert(row < SCIPmatrixGetNRows(matrix));
433  assert(minresactivity != NULL);
434  assert(maxresactivity != NULL);
435 
436  var = SCIPmatrixGetVar(matrix, col);;
437  lowerboundvar = SCIPmatrixGetVar(matrix, lowerboundcol);
438  assert(var != NULL);
439  assert(lowerboundvar != NULL);
440 
441  lb = SCIPvarGetLbGlobal(var);
442  ub = SCIPvarGetUbGlobal(var);
443 
444  maxactinf = SCIPmatrixGetRowNMaxActPosInf(matrix, row) + SCIPmatrixGetRowNMaxActNegInf(matrix, row);
445  minactinf = SCIPmatrixGetRowNMinActPosInf(matrix, row) + SCIPmatrixGetRowNMinActNegInf(matrix, row);
446 
447  assert(!SCIPisInfinity(scip, lb));
448  assert(!SCIPisInfinity(scip, -ub));
449 
450  lblowerboundvar = SCIPvarGetLbGlobal(lowerboundvar);
451  ublowerboundvar = SCIPvarGetUbGlobal(lowerboundvar);
452 
453  assert(!SCIPisInfinity(scip, lblowerboundvar));
454  assert(!SCIPisInfinity(scip, -ublowerboundvar));
455 
456  tmpminact = SCIPmatrixGetRowMinActivity(matrix, row);
457  tmpmaxact = SCIPmatrixGetRowMaxActivity(matrix, row);
458 
459  /* first, adjust min and max activity such that lowerboundvar is always set to its lower bound */
460 
461  /* abort if the lower bound is -infty */
462  if( SCIPisInfinity(scip, -lblowerboundvar) )
463  {
464  *success = FALSE;
465  return;
466  }
467  else
468  {
469  /* coef > 0 --> the upper bound is used for the maxactivity --> update the maxactivity */
470  if( lowerboundcoef > 0.0 )
471  {
472  if( SCIPisInfinity(scip, ublowerboundvar) )
473  {
474  assert(maxactinf > 0);
475  maxactinf--;
476  tmpmaxact += (lowerboundcoef * lblowerboundvar);
477  }
478  else
479  {
480  tmpmaxact = tmpmaxact - (lowerboundcoef * ublowerboundvar) + (lowerboundcoef * lblowerboundvar);
481  }
482  }
483  /* coef < 0 --> the upper bound is used for the minactivity --> update the minactivity */
484  else
485  {
486  if( SCIPisInfinity(scip, ublowerboundvar) )
487  {
488  assert(minactinf > 0);
489  minactinf--;
490  tmpminact += (lowerboundcoef * lblowerboundvar);
491  }
492  else
493  {
494  tmpminact = tmpminact - (lowerboundcoef * ublowerboundvar) + (lowerboundcoef * lblowerboundvar);
495  }
496  }
497  }
498 
499  *success = TRUE;
500 
501  /* the coefficient is positive, so the upper bound contributed to the maxactivity and the lower bound to the minactivity */
502  if( coef >= 0.0 )
503  {
504  if( SCIPisInfinity(scip, ub) )
505  {
506  assert(maxactinf >= 1);
507  if( maxactinf == 1 )
508  {
509  *maxresactivity = tmpmaxact;
510  }
511  else
512  *maxresactivity = SCIPinfinity(scip);
513  }
514  else
515  {
516  if( maxactinf > 0 )
517  *maxresactivity = SCIPinfinity(scip);
518  else
519  *maxresactivity = tmpmaxact - coef * ub;
520  }
521 
522  if( SCIPisInfinity(scip, -lb) )
523  {
524  assert(minactinf >= 1);
525  if( minactinf == 1 )
526  {
527  *minresactivity = tmpminact;
528  }
529  else
530  *minresactivity = -SCIPinfinity(scip);
531  }
532  else
533  {
534  if( minactinf > 0 )
535  *minresactivity = -SCIPinfinity(scip);
536  else
537  *minresactivity = tmpminact - coef * lb;
538  }
539  }
540  /* the coefficient is negative, so the lower bound contributed to the maxactivity and the upper bound to the minactivity */
541  else
542  {
543  if( SCIPisInfinity(scip, -lb) )
544  {
545  assert(maxactinf >= 1);
546  if( maxactinf == 1 )
547  {
548  *maxresactivity = tmpmaxact;
549  }
550  else
551  *maxresactivity = SCIPinfinity(scip);
552  }
553  else
554  {
555  if( maxactinf > 0 )
556  *maxresactivity = SCIPinfinity(scip);
557  else
558  *maxresactivity = tmpmaxact - coef * lb;
559  }
560 
561  if( SCIPisInfinity(scip, ub) )
562  {
563  assert(minactinf >= 1);
564  if( minactinf == 1 )
565  {
566  *minresactivity = tmpminact;
567  }
568  else
569  *minresactivity = -SCIPinfinity(scip);
570  }
571  else
572  {
573  if( minactinf > 0 )
574  *minresactivity = -SCIPinfinity(scip);
575  else
576  *minresactivity = tmpminact - coef * ub;
577  }
578  }
579 }
580 
581 /** Calculate bounds of the dominated variable by rowbound analysis.
582  * We use a special kind of predictive rowbound analysis by first setting the dominating variable to its upper bound.
583  */
584 static
585 SCIP_RETCODE calcVarBoundsDominated(
586  SCIP* scip, /**< SCIP main data structure */
587  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
588  int row, /**< current row index */
589  int coldominating, /**< column index of dominating variable */
590  SCIP_Real valdominating, /**< row coefficient of dominating variable */
591  int coldominated, /**< column index of dominated variable */
592  SCIP_Real valdominated, /**< row coefficient of dominated variable */
593  SCIP_Bool* ubcalculated, /**< was a upper bound calculated? */
594  SCIP_Real* calculatedub, /**< predicted upper bound */
595  SCIP_Bool* wclbcalculated, /**< was a lower worst case bound calculated? */
596  SCIP_Real* calculatedwclb, /**< predicted worst case lower bound */
597  SCIP_Bool* lbcalculated, /**< was a lower bound calculated? */
598  SCIP_Real* calculatedlb, /**< predicted lower bound */
599  SCIP_Bool* wcubcalculated, /**< was a worst case upper bound calculated? */
600  SCIP_Real* calculatedwcub /**< calculated worst case upper bound */
601  )
602 {
603  SCIP_Real minresactivity;
604  SCIP_Real maxresactivity;
605  SCIP_Real lhs;
606  SCIP_Real rhs;
607  SCIP_Bool success;
608 
609  assert(scip != NULL);
610  assert(matrix != NULL);
611  assert(0 <= row && row < SCIPmatrixGetNRows(matrix));
612  assert(0 <= coldominating && coldominating < SCIPmatrixGetNColumns(matrix));
613  assert(0 <= coldominated && coldominated < SCIPmatrixGetNColumns(matrix));
614 
615  assert(ubcalculated != NULL);
616  assert(calculatedub != NULL);
617  assert(wclbcalculated != NULL);
618  assert(calculatedwclb != NULL);
619  assert(lbcalculated != NULL);
620  assert(calculatedlb != NULL);
621  assert(wcubcalculated != NULL);
622  assert(calculatedwcub != NULL);
623 
624  assert(!SCIPisZero(scip, valdominated));
625  assert(SCIPmatrixGetVar(matrix, coldominated) != NULL);
626 
627  *ubcalculated = FALSE;
628  *wclbcalculated = FALSE;
629  *lbcalculated = FALSE;
630  *wcubcalculated = FALSE;
631 
632  /* no rowbound analysis for multiaggregated variables, which should not exist, because the matrix only consists of
633  * active variables
634  */
635  assert(SCIPvarGetStatus(SCIPmatrixGetVar(matrix, coldominating)) != SCIP_VARSTATUS_MULTAGGR);
636  assert(SCIPvarGetStatus(SCIPmatrixGetVar(matrix, coldominated)) != SCIP_VARSTATUS_MULTAGGR);
637 
638  lhs = SCIPmatrixGetRowLhs(matrix, row);
639  rhs = SCIPmatrixGetRowRhs(matrix, row);
640  assert(!SCIPisInfinity(scip, lhs));
641  assert(!SCIPisInfinity(scip, -rhs));
642 
643  /* get minimum/maximum activity of this row without the dominated variable */
644  getActivityResidualsUpperBound(scip, matrix, row, coldominated, valdominated, coldominating, valdominating,
645  &minresactivity, &maxresactivity, &success);
646 
647  if( !success )
648  return SCIP_OKAY;
649 
650  assert(!SCIPisInfinity(scip, minresactivity));
651  assert(!SCIPisInfinity(scip, -maxresactivity));
652 
653  *calculatedub = SCIPinfinity(scip);
654  *calculatedwclb = -SCIPinfinity(scip);
655  *calculatedlb = -SCIPinfinity(scip);
656  *calculatedwcub = SCIPinfinity(scip);
657 
658  /* predictive rowbound analysis */
659 
660  if( valdominated > 0.0 )
661  {
662  /* lower bound calculation */
663  if( !SCIPisInfinity(scip, maxresactivity) )
664  {
665  *calculatedlb = (lhs - maxresactivity)/valdominated;
666  *lbcalculated = TRUE;
667  }
668 
669  /* worst case calculation of lower bound */
670  if( !SCIPisInfinity(scip, -minresactivity) )
671  {
672  *calculatedwclb = (lhs - minresactivity)/valdominated;
673  *wclbcalculated = TRUE;
674  }
675  else
676  {
677  /* worst case lower bound is infinity */
678  *calculatedwclb = SCIPinfinity(scip);
679  *wclbcalculated = TRUE;
680  }
681 
682  /* we can only calculate upper bounds, of the right hand side is finite */
683  if( !SCIPmatrixIsRowRhsInfinity(matrix, row) )
684  {
685  /* upper bound calculation */
686  if( !SCIPisInfinity(scip, -minresactivity) )
687  {
688  *calculatedub = (rhs - minresactivity)/valdominated;
689  *ubcalculated = TRUE;
690  }
691 
692  /* worst case calculation of upper bound */
693  if( !SCIPisInfinity(scip, maxresactivity) )
694  {
695  *calculatedwcub = (rhs - maxresactivity)/valdominated;
696  *wcubcalculated = TRUE;
697  }
698  else
699  {
700  /* worst case upper bound is -infinity */
701  *calculatedwcub = -SCIPinfinity(scip);
702  *wcubcalculated = TRUE;
703  }
704  }
705  }
706  else
707  {
708  /* upper bound calculation */
709  if( !SCIPisInfinity(scip, maxresactivity) )
710  {
711  *calculatedub = (lhs - maxresactivity)/valdominated;
712  *ubcalculated = TRUE;
713  }
714 
715  /* worst case calculation of upper bound */
716  if( !SCIPisInfinity(scip, -minresactivity) )
717  {
718  *calculatedwcub = (lhs - minresactivity)/valdominated;
719  *wcubcalculated = TRUE;
720  }
721  else
722  {
723  /* worst case upper bound is -infinity */
724  *calculatedwcub = -SCIPinfinity(scip);
725  *wcubcalculated = TRUE;
726  }
727 
728  /* we can only calculate lower bounds, of the right hand side is finite */
729  if( !SCIPmatrixIsRowRhsInfinity(matrix, row) )
730  {
731  /* lower bound calculation */
732  if( !SCIPisInfinity(scip, -minresactivity) )
733  {
734  *calculatedlb = (rhs - minresactivity)/valdominated;
735  *lbcalculated = TRUE;
736  }
737 
738  /* worst case calculation of lower bound */
739  if( !SCIPisInfinity(scip, maxresactivity) )
740  {
741  *calculatedwclb = (rhs - maxresactivity)/valdominated;
742  *wclbcalculated = TRUE;
743  }
744  else
745  {
746  /* worst case lower bound is infinity */
747  *calculatedwclb = SCIPinfinity(scip);
748  *wclbcalculated = TRUE;
749  }
750  }
751  }
752 
753  return SCIP_OKAY;
754 }
755 
756 /** Calculate bounds of the dominating variable by rowbound analysis.
757  * We use a special kind of predictive rowbound analysis by first setting the dominated variable to its lower bound.
758  */
759 static
760 SCIP_RETCODE calcVarBoundsDominating(
761  SCIP* scip, /**< SCIP main data structure */
762  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
763  int row, /**< current row index */
764  int coldominating, /**< column index of dominating variable */
765  SCIP_Real valdominating, /**< row coefficient of dominating variable */
766  int coldominated, /**< column index of dominated variable */
767  SCIP_Real valdominated, /**< row coefficient of dominated variable */
768  SCIP_Bool* ubcalculated, /**< was a upper bound calculated? */
769  SCIP_Real* calculatedub, /**< predicted upper bound */
770  SCIP_Bool* wclbcalculated, /**< was a lower worst case bound calculated? */
771  SCIP_Real* calculatedwclb, /**< predicted worst case lower bound */
772  SCIP_Bool* lbcalculated, /**< was a lower bound calculated? */
773  SCIP_Real* calculatedlb, /**< predicted lower bound */
774  SCIP_Bool* wcubcalculated, /**< was a worst case upper bound calculated? */
775  SCIP_Real* calculatedwcub /**< calculated worst case upper bound */
776  )
777 {
778  SCIP_Real minresactivity;
779  SCIP_Real maxresactivity;
780  SCIP_Real lhs;
781  SCIP_Real rhs;
782  SCIP_Bool success;
783 
784  assert(scip != NULL);
785  assert(matrix != NULL);
786  assert(0 <= row && row < SCIPmatrixGetNRows(matrix) );
787  assert(0 <= coldominating && coldominating < SCIPmatrixGetNColumns(matrix));
788  assert(0 <= coldominated && coldominated < SCIPmatrixGetNColumns(matrix));
789 
790  assert(ubcalculated != NULL);
791  assert(calculatedub != NULL);
792  assert(wclbcalculated != NULL);
793  assert(calculatedwclb != NULL);
794  assert(lbcalculated != NULL);
795  assert(calculatedlb != NULL);
796  assert(wcubcalculated != NULL);
797  assert(calculatedwcub != NULL);
798 
799  assert(!SCIPisZero(scip, valdominating));
800  assert(SCIPmatrixGetVar(matrix, coldominating) != NULL);
801 
802  *ubcalculated = FALSE;
803  *wclbcalculated = FALSE;
804  *lbcalculated = FALSE;
805  *wcubcalculated = FALSE;
806 
807  /* no rowbound analysis for multiaggregated variables, which should not exist, because the matrix only consists of
808  * active variables
809  */
810  assert(SCIPvarGetStatus(SCIPmatrixGetVar(matrix, coldominating)) != SCIP_VARSTATUS_MULTAGGR);
811  assert(SCIPvarGetStatus(SCIPmatrixGetVar(matrix, coldominated)) != SCIP_VARSTATUS_MULTAGGR);
812 
813  lhs = SCIPmatrixGetRowLhs(matrix, row);
814  rhs = SCIPmatrixGetRowRhs(matrix, row);
815  assert(!SCIPisInfinity(scip, lhs));
816  assert(!SCIPisInfinity(scip, -rhs));
817 
818  /* get minimum/maximum activity of this row without the dominating variable */
819  getActivityResidualsLowerBound(scip, matrix, row, coldominating, valdominating, coldominated, valdominated,
820  &minresactivity, &maxresactivity, &success);
821 
822  if( !success )
823  return SCIP_OKAY;
824 
825  assert(!SCIPisInfinity(scip, minresactivity));
826  assert(!SCIPisInfinity(scip, -maxresactivity));
827 
828  *calculatedub = SCIPinfinity(scip);
829  *calculatedwclb = -SCIPinfinity(scip);
830  *calculatedlb = -SCIPinfinity(scip);
831  *calculatedwcub = SCIPinfinity(scip);
832 
833  /* predictive rowbound analysis */
834 
835  if( valdominating > 0.0 )
836  {
837  /* lower bound calculation */
838  if( !SCIPisInfinity(scip, maxresactivity) )
839  {
840  *calculatedlb = (lhs - maxresactivity)/valdominating;
841  *lbcalculated = TRUE;
842  }
843 
844  /* worst case calculation of lower bound */
845  if( !SCIPisInfinity(scip, -minresactivity) )
846  {
847  *calculatedwclb = (lhs - minresactivity)/valdominating;
848  *wclbcalculated = TRUE;
849  }
850  else
851  {
852  /* worst case lower bound is infinity */
853  *calculatedwclb = SCIPinfinity(scip);
854  *wclbcalculated = TRUE;
855  }
856 
857  /* we can only calculate upper bounds, of the right hand side is finite */
858  if( !SCIPmatrixIsRowRhsInfinity(matrix, row) )
859  {
860  /* upper bound calculation */
861  if( !SCIPisInfinity(scip, -minresactivity) )
862  {
863  *calculatedub = (rhs - minresactivity)/valdominating;
864  *ubcalculated = TRUE;
865  }
866 
867  /* worst case calculation of upper bound */
868  if( !SCIPisInfinity(scip, maxresactivity) )
869  {
870  *calculatedwcub = (rhs - maxresactivity)/valdominating;
871  *wcubcalculated = TRUE;
872  }
873  else
874  {
875  /* worst case upper bound is -infinity */
876  *calculatedwcub = -SCIPinfinity(scip);
877  *wcubcalculated = TRUE;
878  }
879  }
880  }
881  else
882  {
883  /* upper bound calculation */
884  if( !SCIPisInfinity(scip, maxresactivity) )
885  {
886  *calculatedub = (lhs - maxresactivity)/valdominating;
887  *ubcalculated = TRUE;
888  }
889 
890  /* worst case calculation of upper bound */
891  if( !SCIPisInfinity(scip, -minresactivity) )
892  {
893  *calculatedwcub = (lhs - minresactivity)/valdominating;
894  *wcubcalculated = TRUE;
895  }
896  else
897  {
898  /* worst case upper bound is -infinity */
899  *calculatedwcub = -SCIPinfinity(scip);
900  *wcubcalculated = TRUE;
901  }
902 
903  /* we can only calculate lower bounds, of the right hand side is finite */
904  if( !SCIPmatrixIsRowRhsInfinity(matrix, row) )
905  {
906  /* lower bound calculation */
907  if( !SCIPisInfinity(scip, -minresactivity) )
908  {
909  *calculatedlb = (rhs - minresactivity)/valdominating;
910  *lbcalculated = TRUE;
911  }
912 
913  /* worst case calculation of lower bound */
914  if( !SCIPisInfinity(scip, maxresactivity) )
915  {
916  *calculatedwclb = (rhs - maxresactivity)/valdominating;
917  *wclbcalculated = TRUE;
918  }
919  else
920  {
921  /* worst case lower bound is infinity */
922  *calculatedwclb = SCIPinfinity(scip);
923  *wclbcalculated = TRUE;
924  }
925  }
926  }
927 
928  return SCIP_OKAY;
929 }
930 
931 /** try to find new variable bounds and update them when they are better then the old bounds */
932 static
933 SCIP_RETCODE updateBounds(
934  SCIP* scip, /**< SCIP main data structure */
935  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
936  int row, /**< row index */
937  int col1, /**< dominating variable index */
938  SCIP_Real val1, /**< dominating variable coefficient */
939  int col2, /**< dominated variable index */
940  SCIP_Real val2, /**< dominated variable coefficient */
941  SCIP_Bool predictdominating, /**< flag indicating if bounds of dominating or dominated variable are predicted */
942  SCIP_Real* upperbound, /**< predicted upper bound */
943  SCIP_Real* wclowerbound, /**< predicted worst case lower bound */
944  SCIP_Real* lowerbound, /**< predicted lower bound */
945  SCIP_Real* wcupperbound /**< predicted worst case upper bound */
946  )
947 {
948  SCIP_Bool ubcalculated;
949  SCIP_Bool wclbcalculated;
950  SCIP_Bool lbcalculated;
951  SCIP_Bool wcubcalculated;
952  SCIP_Real newub;
953  SCIP_Real newwclb;
954  SCIP_Real newlb;
955  SCIP_Real newwcub;
956 
957  assert(scip != NULL);
958  assert(matrix != NULL);
959  assert(upperbound != NULL);
960  assert(wclowerbound != NULL);
961  assert(lowerbound != NULL);
962  assert(wcupperbound != NULL);
963 
964  newub = SCIPinfinity(scip);
965  newlb = -SCIPinfinity(scip);
966  newwcub = newub;
967  newwclb = newlb;
968 
969  if( predictdominating )
970  {
971  /* do predictive rowbound analysis for the dominating variable */
972  SCIP_CALL( calcVarBoundsDominating(scip, matrix, row, col1, val1, col2, val2,
973  &ubcalculated, &newub, &wclbcalculated, &newwclb,
974  &lbcalculated, &newlb, &wcubcalculated, &newwcub) );
975  }
976  else
977  {
978  /* do predictive rowbound analysis for the dominated variable */
979  SCIP_CALL( calcVarBoundsDominated(scip, matrix, row, col1, val1, col2, val2,
980  &ubcalculated, &newub, &wclbcalculated, &newwclb,
981  &lbcalculated, &newlb, &wcubcalculated, &newwcub) );
982  }
983 
984  /* update bounds in case if they are better */
985  if( ubcalculated )
986  {
987  if( newub < *upperbound )
988  *upperbound = newub;
989  }
990  if( wclbcalculated )
991  {
992  if( newwclb > *wclowerbound )
993  *wclowerbound = newwclb;
994  }
995  if( lbcalculated )
996  {
997  if( newlb > *lowerbound )
998  *lowerbound = newlb;
999  }
1000  if( wcubcalculated )
1001  {
1002  if( newwcub < *wcupperbound )
1003  *wcupperbound = newwcub;
1004  }
1005 
1006  return SCIP_OKAY;
1007 }
1008 
1009 /** detect parallel columns by using the algorithm of Bixby and Wagner
1010  * see paper: "A note on Detecting Simple Redundancies in Linear Systems", June 1986
1011  */
1012 static
1013 SCIP_RETCODE detectParallelCols(
1014  SCIP* scip, /**< SCIP main data structure */
1015  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
1016  int* pclass, /**< parallel column classes */
1017  SCIP_Bool* varineq /**< indicating if variable is within an equation */
1018  )
1019 {
1020  SCIP_Real* valpnt;
1021  SCIP_Real* values;
1022  SCIP_Real* scale;
1023  int* classsizes;
1024  int* pcset;
1025  int* rowpnt;
1026  int* rowend;
1027  int* colindices;
1028  int* pcs;
1029  SCIP_Real startval;
1030  SCIP_Real aij;
1031  int startpc;
1032  int startk;
1033  int startt;
1034  int pcsetfill;
1035  int colidx;
1036  int k;
1037  int t;
1038  int m;
1039  int i;
1040  int r;
1041  int newpclass;
1042  int pc;
1043  int nrows;
1044  int ncols;
1045 
1046  assert(scip != NULL);
1047  assert(matrix != NULL);
1048  assert(pclass != NULL);
1049  assert(varineq != NULL);
1050 
1051  nrows = SCIPmatrixGetNRows(matrix);
1052  ncols = SCIPmatrixGetNColumns(matrix);
1053 
1054  SCIP_CALL( SCIPallocBufferArray(scip, &classsizes, ncols) );
1055  SCIP_CALL( SCIPallocBufferArray(scip, &scale, ncols) );
1056  SCIP_CALL( SCIPallocBufferArray(scip, &pcset, ncols) );
1057  SCIP_CALL( SCIPallocBufferArray(scip, &values, ncols) );
1058  SCIP_CALL( SCIPallocBufferArray(scip, &colindices, ncols) );
1059  SCIP_CALL( SCIPallocBufferArray(scip, &pcs, ncols) );
1060 
1061  BMSclearMemoryArray(scale, ncols);
1062  BMSclearMemoryArray(pclass, ncols);
1063  BMSclearMemoryArray(classsizes, ncols);
1064 
1065  classsizes[0] = ncols;
1066  pcsetfill = 0;
1067  for( t = 1; t < ncols; ++t )
1068  pcset[pcsetfill++] = t;
1069 
1070  /* loop over all rows */
1071  for( r = 0; r < nrows; ++r )
1072  {
1073  /* we consider only equations or ranged rows */
1074  if( !SCIPmatrixIsRowRhsInfinity(matrix, r) )
1075  {
1076  rowpnt = SCIPmatrixGetRowIdxPtr(matrix, r);
1077  rowend = rowpnt + SCIPmatrixGetRowNNonzs(matrix, r);
1078  valpnt = SCIPmatrixGetRowValPtr(matrix, r);
1079 
1080  i = 0;
1081  for( ; (rowpnt < rowend); rowpnt++, valpnt++ )
1082  {
1083  aij = *valpnt;
1084  colidx = *rowpnt;
1085 
1086  /* remember variable was part of an equation or ranged row */
1087  varineq[colidx] = TRUE;
1088 
1089  if( scale[colidx] == 0.0 )
1090  scale[colidx] = aij;
1091  assert(scale[colidx] != 0.0);
1092 
1093  colindices[i] = colidx;
1094  values[i] = aij / scale[colidx];
1095  pc = pclass[colidx];
1096  assert(pc < ncols);
1097 
1098  /* update class sizes and pclass set */
1099  assert(classsizes[pc] > 0);
1100  classsizes[pc]--;
1101  if( classsizes[pc] == 0 )
1102  {
1103  assert(pcsetfill < ncols);
1104  pcset[pcsetfill++] = pc;
1105  }
1106  pcs[i] = pc;
1107 
1108  i++;
1109  }
1110 
1111  /* sort on the pclass values */
1112  if( i > 1 )
1113  {
1114  SCIPsortIntIntReal(pcs, colindices, values, i);
1115  }
1116 
1117  k = 0;
1118  while( TRUE ) /*lint !e716*/
1119  {
1120  assert(k < i);
1121  startpc = pcs[k];
1122  startk = k;
1123 
1124  /* find pclass-sets */
1125  while( k < i && pcs[k] == startpc )
1126  k++;
1127 
1128  /* sort on the A values which have equal pclass values */
1129  if( k - startk > 1 )
1130  SCIPsortRealInt(&(values[startk]), &(colindices[startk]), k - startk);
1131 
1132  t = 0;
1133  while( TRUE ) /*lint !e716*/
1134  {
1135  assert(startk + t < i);
1136  startval = values[startk + t];
1137  startt = t;
1138 
1139  /* find A-sets */
1140  while( t < k - startk && SCIPisEQ(scip, startval, values[startk + t]) )
1141  t++;
1142 
1143  /* get new pclass */
1144  newpclass = pcset[0];
1145  assert(pcsetfill > 0);
1146  pcset[0] = pcset[--pcsetfill];
1147 
1148  /* renumbering */
1149  for( m = startk + startt; m < startk + t; m++ )
1150  {
1151  assert(m < i);
1152  assert(colindices[m] < ncols);
1153  assert(newpclass < ncols);
1154 
1155  pclass[colindices[m]] = newpclass;
1156  classsizes[newpclass]++;
1157  }
1158 
1159  if( t == k - startk )
1160  break;
1161  }
1162 
1163  if( k == SCIPmatrixGetRowNNonzs(matrix, r) )
1164  break;
1165  }
1166  }
1167  }
1168 
1169  SCIPfreeBufferArray(scip, &pcs);
1170  SCIPfreeBufferArray(scip, &colindices);
1171  SCIPfreeBufferArray(scip, &values);
1172  SCIPfreeBufferArray(scip, &pcset);
1173  SCIPfreeBufferArray(scip, &scale);
1174  SCIPfreeBufferArray(scip, &classsizes);
1175 
1176  return SCIP_OKAY;
1177 }
1178 
1179 
1180 /** try to improve variable bounds by predictive bound strengthening */
1181 static
1182 SCIP_RETCODE predBndStr(
1183  SCIP* scip, /**< SCIP main data structure */
1184  SCIP_VAR* dominatingvar, /**< dominating variable */
1185  int dominatingidx, /**< column index of the dominating variable */
1186  SCIP_Real dominatingub, /**< predicted upper bound of the dominating variable */
1187  SCIP_Real dominatinglb, /**< predicted lower bound of the dominating variable */
1188  SCIP_Real dominatingwcub, /**< predicted worst case upper bound of the dominating variable */
1189  SCIP_VAR* dominatedvar, /**< dominated variable */
1190  int dominatedidx, /**< column index of the dominated variable */
1191  SCIP_Real dominatedub, /**< predicted upper bound of the dominated variable */
1192  SCIP_Real dominatedwclb, /**< predicted worst case lower bound of the dominated variable */
1193  SCIP_Real dominatedlb, /**< predicted lower bound of the dominated variable */
1194  FIXINGDIRECTION* varstofix, /**< array holding fixing information */
1195  int* nchgbds /**< count number of bound changes */
1196  )
1197 {
1198  /* we compare only variables from the same type */
1199  if( !(SCIPvarGetType(dominatingvar) == SCIPvarGetType(dominatedvar) ||
1200  SCIPvarIsBinary(dominatingvar) == SCIPvarIsBinary(dominatedvar) ||
1201  (SCIPvarGetType(dominatingvar) == SCIP_VARTYPE_INTEGER && SCIPvarGetType(dominatedvar) == SCIP_VARTYPE_IMPLINT) ||
1202  (SCIPvarGetType(dominatedvar) == SCIP_VARTYPE_INTEGER && SCIPvarGetType(dominatingvar) == SCIP_VARTYPE_IMPLINT)) )
1203  {
1204  return SCIP_OKAY;
1205  }
1206 
1207  if( varstofix[dominatingidx] == NOFIX )
1208  {
1209  /* assume x dominates y (x->y). we get this bound from a positive coefficient
1210  * of the dominating variable. because x->y the dominated variable y has
1211  * a positive coefficient too. thus y contributes to the minactivity with its
1212  * lower bound. but this case is considered within predictive bound analysis.
1213  * thus the dominating upper bound is a common upper bound.
1214  */
1215  if( !SCIPisInfinity(scip, dominatingub) )
1216  {
1217  SCIP_Real newub;
1218  SCIP_Real oldub;
1219  SCIP_Real lb;
1220 
1221  newub = dominatingub;
1222  oldub = SCIPvarGetUbGlobal(dominatingvar);
1223  lb = SCIPvarGetLbGlobal(dominatingvar);
1224 
1225  /* if( SCIPvarGetType(dominatingvar) != SCIP_VARTYPE_CONTINUOUS )
1226  newub = SCIPceil(scip, newub); */
1227 
1228  if( SCIPisLE(scip, lb, newub) && SCIPisLT(scip, newub, oldub) )
1229  {
1230  SCIPdebugMsg(scip, "[ub]\tupper bound for dominating variable <%s> changed: [%.17f,%.17f] -> [%.17f,%.17f]\n",
1231  SCIPvarGetName(dominatingvar), lb, oldub, lb, newub);
1232  SCIP_CALL( SCIPchgVarUb(scip, dominatingvar, newub) );
1233  (*nchgbds)++;
1234  }
1235  }
1236 
1237  /* assume x dominates y (x->y). we get this lower bound of the dominating variable
1238  * from a negative coefficient within a <= relation. if y has a positive coefficient
1239  * we get a common lower bound of x from predictive bound analysis. if y has a
1240  * negative coefficient we get an improved lower bound of x because the minactivity
1241  * is greater. for discrete variables we have to round down the lower bound.
1242  */
1243  if( !SCIPisInfinity(scip, -dominatinglb) )
1244  {
1245  SCIP_Real newlb;
1246  SCIP_Real oldlb;
1247  SCIP_Real ub;
1248 
1249  newlb = dominatinglb;
1250  oldlb = SCIPvarGetLbGlobal(dominatingvar);
1251  ub = SCIPvarGetUbGlobal(dominatingvar);
1252 
1253  if( SCIPvarGetType(dominatingvar) != SCIP_VARTYPE_CONTINUOUS )
1254  newlb = SCIPfloor(scip, newlb);
1255 
1256  if( SCIPisLT(scip, oldlb, newlb) && SCIPisLE(scip, newlb, ub) )
1257  {
1258  SCIPdebugMsg(scip, "[lb]\tlower bound of dominating variable <%s> changed: [%.17f,%.17f] -> [%.17f,%.17f]\n",
1259  SCIPvarGetName(dominatingvar), oldlb, ub, newlb, ub);
1260  SCIP_CALL( SCIPchgVarLb(scip, dominatingvar, newlb) );
1261  (*nchgbds)++;
1262  }
1263  }
1264 
1265  /* assume x dominates y (x->y). we get this bound from a positive coefficient
1266  * of x within a <= relation. from x->y it follows, that y has a positive
1267  * coefficient in this row too. the worst case upper bound of x is an estimation
1268  * of how great x can be in every case. if the objective coefficient of x is
1269  * negative we get thus a lower bound of x. for discrete variables we have
1270  * to round down the lower bound before.
1271  */
1272  if( !SCIPisInfinity(scip, dominatingwcub) && SCIPisNegative(scip, SCIPvarGetObj(dominatingvar)))
1273  {
1274  SCIP_Real newlb;
1275  SCIP_Real oldlb;
1276  SCIP_Real ub;
1277 
1278  newlb = dominatingwcub;
1279  oldlb = SCIPvarGetLbGlobal(dominatingvar);
1280  ub = SCIPvarGetUbGlobal(dominatingvar);
1281 
1282  if( SCIPvarGetType(dominatingvar) != SCIP_VARTYPE_CONTINUOUS )
1283  newlb = SCIPfloor(scip, newlb);
1284 
1285  if( SCIPisLT(scip, oldlb, newlb) && SCIPisLE(scip, newlb, ub) )
1286  {
1287  SCIPdebugMsg(scip, "[wcub]\tlower bound of dominating variable <%s> changed: [%.17f,%.17f] -> [%.17f,%.17f]\n",
1288  SCIPvarGetName(dominatingvar), oldlb, ub, newlb, ub);
1289  SCIP_CALL( SCIPchgVarLb(scip, dominatingvar, newlb) );
1290  (*nchgbds)++;
1291  }
1292  }
1293  }
1294 
1295  if( varstofix[dominatedidx] == NOFIX )
1296  {
1297  /* assume x dominates y (x->y). we get this bound for a positive coefficient of y
1298  * within a <= relation. if x has a negative coefficient we get a common upper
1299  * bound of y. if x has a positive coefficient we get an improved upper bound
1300  * of y because the minactivity is greater.
1301  */
1302  if( !SCIPisInfinity(scip, dominatedub) )
1303  {
1304  SCIP_Real newub;
1305  SCIP_Real oldub;
1306  SCIP_Real lb;
1307 
1308  newub = dominatedub;
1309  oldub = SCIPvarGetUbGlobal(dominatedvar);
1310  lb = SCIPvarGetLbGlobal(dominatedvar);
1311 
1312  if( SCIPisLE(scip, lb, newub) && SCIPisLT(scip, newub, oldub) )
1313  {
1314  SCIPdebugMsg(scip, "[ub]\tupper bound of dominated variable <%s> changed: [%.17f,%.17f] -> [%.17f,%.17f]\n",
1315  SCIPvarGetName(dominatedvar), lb, oldub, lb, newub);
1316  SCIP_CALL( SCIPchgVarUb(scip, dominatedvar, newub) );
1317  (*nchgbds)++;
1318  }
1319  }
1320 
1321  /* assume x dominates y (x->y). we get this bound only from a negative
1322  * coefficient of y within a <= relation. because of x->y then x has a negative
1323  * coefficient too. the worst case lower bound is an estimation what property
1324  * the dominated variable must have if the dominating variable is at its upper bound.
1325  * to get an upper bound of the dominated variable we need to consider a positive
1326  * objective coefficient. for discrete variables we have to round up the upper bound.
1327  */
1328  if( !SCIPisInfinity(scip, -dominatedwclb) && SCIPisPositive(scip, SCIPvarGetObj(dominatedvar)) )
1329  {
1330  SCIP_Real newub;
1331  SCIP_Real oldub;
1332  SCIP_Real lb;
1333 
1334  newub = dominatedwclb;
1335  oldub = SCIPvarGetUbGlobal(dominatedvar);
1336  lb = SCIPvarGetLbGlobal(dominatedvar);
1337 
1338  if( SCIPvarGetType(dominatedvar) != SCIP_VARTYPE_CONTINUOUS )
1339  newub = SCIPceil(scip, newub);
1340 
1341  if( SCIPisLE(scip, lb, newub) && SCIPisLT(scip, newub, oldub) )
1342  {
1343  SCIPdebugMsg(scip, "[wclb]\tupper bound of dominated variable <%s> changed: [%.17f,%.17f] -> [%.17f,%.17f]\n",
1344  SCIPvarGetName(dominatedvar), lb, oldub, lb, newub);
1345  SCIP_CALL( SCIPchgVarUb(scip, dominatedvar, newub) );
1346  (*nchgbds)++;
1347  }
1348  }
1349 
1350  /* assume x dominates y (x->y). we get a lower bound of y from a negative
1351  * coefficient within a <= relation. but if x->y then x has a negative
1352  * coefficient too and contributes with its upper bound to the minactivity.
1353  * thus in all we have a common lower bound calculation and no rounding is necessary.
1354  */
1355  if( !SCIPisInfinity(scip, -dominatedlb) )
1356  {
1357  SCIP_Real newlb;
1358  SCIP_Real oldlb;
1359  SCIP_Real ub;
1360 
1361  newlb = dominatedlb;
1362  oldlb = SCIPvarGetLbGlobal(dominatedvar);
1363  ub = SCIPvarGetUbGlobal(dominatedvar);
1364 
1365  if( SCIPisLT(scip, oldlb, newlb) && SCIPisLE(scip, newlb, ub) )
1366  {
1367  SCIPdebugMsg(scip, "[lb]\tlower bound of dominated variable <%s> changed: [%.17f,%.17f] -> [%.17f,%.17f]\n",
1368  SCIPvarGetName(dominatedvar), oldlb, ub, newlb, ub);
1369  SCIP_CALL( SCIPchgVarLb(scip, dominatedvar, newlb) );
1370  (*nchgbds)++;
1371  }
1372  }
1373  }
1374 
1375  return SCIP_OKAY;
1376 }
1377 
1378 /** try to find variable fixings */
1379 static
1380 SCIP_RETCODE findFixings(
1381  SCIP* scip, /**< SCIP main data structure */
1382  SCIP_MATRIX* matrix, /**< constraint matrix structure */
1383  SCIP_VAR* dominatingvar, /**< dominating variable */
1384  int dominatingidx, /**< column index of the dominating variable */
1385  SCIP_Real dominatingub, /**< predicted upper bound of the dominating variable */
1386  SCIP_Real dominatingwclb, /**< predicted worst case lower bound of the dominating variable */
1387  SCIP_Real dominatinglb, /**< predicted lower bound of the dominating variable */
1388  SCIP_Real dominatingwcub, /**< predicted worst case upper bound of the dominating variable */
1389  SCIP_VAR* dominatedvar, /**< dominated variable */
1390  int dominatedidx, /**< column index of the dominated variable */
1391  FIXINGDIRECTION* varstofix, /**< array holding fixing information */
1392  SCIP_Bool onlybinvars, /**< flag indicating only binary variables are present */
1393  SCIP_Bool onlyoneone, /**< when onlybinvars is TRUE, flag indicates if both binary variables are in clique */
1394  int* nfixings /**< counter for possible fixings */
1395  )
1396 {
1397  /* we compare only variables from the same type */
1398  if( !(SCIPvarGetType(dominatingvar) == SCIPvarGetType(dominatedvar) ||
1399  SCIPvarIsBinary(dominatingvar) == SCIPvarIsBinary(dominatedvar) ||
1400  (SCIPvarGetType(dominatingvar) == SCIP_VARTYPE_INTEGER && SCIPvarGetType(dominatedvar) == SCIP_VARTYPE_IMPLINT) ||
1401  (SCIPvarGetType(dominatedvar) == SCIP_VARTYPE_INTEGER && SCIPvarGetType(dominatingvar) == SCIP_VARTYPE_IMPLINT)) )
1402  {
1403  return SCIP_OKAY;
1404  }
1405 
1406  if( varstofix[dominatedidx] == NOFIX && SCIPmatrixGetColNNonzs(matrix, dominatingidx) == 1
1407  && SCIPmatrixGetColNNonzs(matrix, dominatedidx) == 1 )
1408  {
1409  /* We have a x->y dominance relation and only one equality constraint
1410  * where the dominating variable x with an infinity upper bound and the
1411  * dominated variable y are present. Then the dominated variable y
1412  * can be fixed at its lower bound.
1413  */
1414  int row;
1415  row = *(SCIPmatrixGetColIdxPtr(matrix, dominatedidx));
1416 
1417  if( SCIPisEQ(scip, SCIPmatrixGetRowLhs(matrix, row), SCIPmatrixGetRowRhs(matrix, row)) &&
1418  SCIPisInfinity(scip, SCIPvarGetUbGlobal(dominatingvar)) )
1419  {
1420  varstofix[dominatedidx] = FIXATLB;
1421  (*nfixings)++;
1422 
1423  return SCIP_OKAY;
1424  }
1425  }
1426 
1427  if( varstofix[dominatedidx] == NOFIX && !SCIPisNegative(scip, SCIPvarGetObj(dominatedvar)) )
1428  {
1429  if( !SCIPisInfinity(scip, -dominatingwclb) &&
1430  SCIPisLE(scip, dominatingwclb, SCIPvarGetUbGlobal(dominatingvar)) )
1431  {
1432  /* we have a x->y dominance relation with a positive obj coefficient
1433  * of the dominated variable y. we need to secure feasibility
1434  * by testing if the predicted lower worst case bound is less equal the
1435  * current upper bound. it is possible, that the lower worst case bound
1436  * is infinity and the upper bound of the dominating variable x is
1437  * infinity too.
1438  */
1439  varstofix[dominatedidx] = FIXATLB;
1440  (*nfixings)++;
1441  }
1442  }
1443 
1444  if( varstofix[dominatedidx] == NOFIX && !SCIPisInfinity(scip, dominatingub) &&
1445  SCIPisLE(scip, dominatingub, SCIPvarGetUbGlobal(dominatingvar)) )
1446  {
1447  /* we have a x->y dominance relation with an arbitrary obj coefficient
1448  * of the dominating variable x. in all cases we have to look
1449  * if the predicted upper bound of the dominating variable is great enough.
1450  * by testing, that the predicted upper bound is not infinity we avoid problems
1451  * with x->y e.g.
1452  * min -x -y
1453  * s.t. -x -y <= -1
1454  * 0<=x<=1, 0<=y<=1
1455  * where y is not at their lower bound.
1456  */
1457  varstofix[dominatedidx] = FIXATLB;
1458  (*nfixings)++;
1459  }
1460 
1461  if( varstofix[dominatingidx] == NOFIX && !SCIPisPositive(scip, SCIPvarGetObj(dominatingvar)) )
1462  {
1463  /* we have a x->y dominance relation with a negative obj coefficient
1464  * of the dominating variable x. if the worst case upper bound is
1465  * greater equal than upper bound, we fix x at the upper bound
1466  */
1467  if( !SCIPisInfinity(scip, dominatingwcub) &&
1468  SCIPisGE(scip, dominatingwcub, SCIPvarGetUbGlobal(dominatingvar)) )
1469  {
1470  varstofix[dominatingidx] = FIXATUB;
1471  (*nfixings)++;
1472  }
1473  }
1474 
1475  if( varstofix[dominatingidx] == NOFIX && !SCIPisInfinity(scip, -dominatinglb) &&
1476  SCIPisGE(scip, dominatinglb, SCIPvarGetUbGlobal(dominatingvar)) )
1477  {
1478  /* we have a x->y dominance relation with an arbitrary obj coefficient
1479  * of the dominating variable x. if the predicted lower bound is greater
1480  * equal than upper bound, we fix x at the upper bound.
1481  */
1482  varstofix[dominatingidx] = FIXATUB;
1483  (*nfixings)++;
1484  }
1485 
1486  if( onlybinvars )
1487  {
1488  if( varstofix[dominatedidx] == NOFIX && (onlyoneone || SCIPvarsHaveCommonClique(dominatingvar, TRUE, dominatedvar, TRUE, TRUE)) )
1489  {
1490  /* We have a (1->1)-clique with dominance relation (x->y) (x dominates y).
1491  * From this dominance relation, we know (1->0) is possible and not worse than (0->1)
1492  * concerning the objective function. It follows that only (1->0) or (0->0) are possible,
1493  * but in both cases y has the value 0 => y=0.
1494  */
1495  varstofix[dominatedidx] = FIXATLB;
1496  (*nfixings)++;
1497  }
1498 
1499  if( varstofix[dominatingidx] == NOFIX && SCIPvarsHaveCommonClique(dominatingvar, FALSE, dominatedvar, FALSE, TRUE) )
1500  {
1501  /* We have a (0->0)-clique with dominance relation x->y (x dominates y).
1502  * From this dominance relation, we know (1->0) is possible and not worse than (0->1)
1503  * concerning the objective function. It follows that only (1->0) or (1->1) are possible,
1504  * but in both cases x has the value 1 => x=1
1505  */
1506  varstofix[dominatingidx] = FIXATUB;
1507  (*nfixings)++;
1508  }
1509  }
1510  else
1511  assert(!onlyoneone);
1512 
1513  return SCIP_OKAY;
1514 }
1515 
1516 /** find dominance relation between variable pairs */
1517 static
1518 SCIP_RETCODE findDominancePairs(
1519  SCIP* scip, /**< SCIP main data structure */
1520  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
1521  SCIP_PRESOLDATA* presoldata, /**< presolver data */
1522  int* searchcols, /**< indexes of variables for pair comparisons */
1523  int searchsize, /**< number of variables for pair comparisons */
1524  SCIP_Bool onlybinvars, /**< flag indicating searchcols contains only binary variable indexes */
1525  FIXINGDIRECTION* varstofix, /**< array holding information for later upper/lower bound fixing */
1526  int* nfixings, /**< found number of possible fixings */
1527  SCIP_Longint* ndomrelations, /**< found number of dominance relations */
1528  int* nchgbds /**< number of changed bounds */
1529  )
1530 {
1531  SCIP_Real* vals1;
1532  SCIP_Real* vals2;
1533  SCIP_Real tmpupperbounddominatingcol1;
1534  SCIP_Real tmpupperbounddominatingcol2;
1535  SCIP_Real tmpwclowerbounddominatingcol1;
1536  SCIP_Real tmpwclowerbounddominatingcol2;
1537  SCIP_Real tmplowerbounddominatingcol1;
1538  SCIP_Real tmplowerbounddominatingcol2;
1539  SCIP_Real tmpwcupperbounddominatingcol1;
1540  SCIP_Real tmpwcupperbounddominatingcol2;
1541  int* rows1;
1542  int* rows2;
1543  int nrows1;
1544  int nrows2;
1545  SCIP_Real tmpupperbounddominatedcol1;
1546  SCIP_Real tmpupperbounddominatedcol2;
1547  SCIP_Real tmpwclowerbounddominatedcol1;
1548  SCIP_Real tmpwclowerbounddominatedcol2;
1549  SCIP_Real tmplowerbounddominatedcol1;
1550  SCIP_Real tmplowerbounddominatedcol2;
1551  SCIP_Real tmpwcupperbounddominatedcol1;
1552  SCIP_Real tmpwcupperbounddominatedcol2;
1553  SCIP_Real obj1;
1554  SCIP_Bool col1domcol2;
1555  SCIP_Bool col2domcol1;
1556  SCIP_Bool onlyoneone;
1557  int cnt1;
1558  int cnt2;
1559  int col1;
1560  int col2;
1561  int r1;
1562  int r2;
1563  int paircnt;
1564  int oldnfixings;
1565 
1566  assert(scip != NULL);
1567  assert(matrix != NULL);
1568  assert(presoldata != NULL);
1569  assert(searchcols != NULL);
1570  assert(varstofix != NULL);
1571  assert(nfixings != NULL);
1572  assert(ndomrelations != NULL);
1573  assert(nchgbds != NULL);
1574 
1575  paircnt = 0;
1576  oldnfixings = *nfixings;
1577 
1578  /* pair comparisons */
1579  for( cnt1 = 0; cnt1 < searchsize; cnt1++ )
1580  {
1581  SCIP_VAR* varcol1;
1582  SCIP_VAR* varcol2;
1583 
1584  /* get index of the first variable */
1585  col1 = searchcols[cnt1];
1586 
1587  if( varstofix[col1] == FIXATLB )
1588  continue;
1589 
1590  varcol1 = SCIPmatrixGetVar(matrix, col1);
1591  obj1 = SCIPvarGetObj(varcol1);
1592 
1593  for( cnt2 = cnt1+1; cnt2 < searchsize; cnt2++ )
1594  {
1595  /* get index of the second variable */
1596  col2 = searchcols[cnt2];
1597  varcol2 = SCIPmatrixGetVar(matrix, col2);
1598  onlyoneone = FALSE;
1599 
1600  /* we always have minimize as obj sense */
1601 
1602  /* column 1 dominating column 2 */
1603  col1domcol2 = (obj1 <= SCIPvarGetObj(varcol2));
1604 
1605  /* column 2 dominating column 1 */
1606  col2domcol1 = (SCIPvarGetObj(varcol2) <= obj1);
1607 
1608  /* search only if nothing was found yet */
1609  col1domcol2 = col1domcol2 && (varstofix[col2] == NOFIX);
1610  col2domcol1 = col2domcol1 && (varstofix[col1] == NOFIX);
1611 
1612  /* we only search for a dominance relation if the lower bounds are not negative */
1613  if( !onlybinvars )
1614  {
1615  if( SCIPisLT(scip, SCIPvarGetLbGlobal(varcol1), 0.0) ||
1616  SCIPisLT(scip, SCIPvarGetLbGlobal(varcol2), 0.0) )
1617  {
1618  col1domcol2 = FALSE;
1619  col2domcol1 = FALSE;
1620  }
1621  }
1622 
1623  /* pair comparison control */
1624  if( paircnt == presoldata->numcurrentpairs )
1625  {
1626  assert(*nfixings >= oldnfixings);
1627  if( *nfixings == oldnfixings )
1628  {
1629  /* not enough fixings found, decrement number of comparisons */
1630  presoldata->numcurrentpairs >>= 1; /*lint !e702*/
1631  if( presoldata->numcurrentpairs < presoldata->numminpairs )
1632  presoldata->numcurrentpairs = presoldata->numminpairs;
1633 
1634  /* stop searching in this row */
1635  return SCIP_OKAY;
1636  }
1637  oldnfixings = *nfixings;
1638  paircnt = 0;
1639 
1640  /* increment number of comparisons */
1641  presoldata->numcurrentpairs <<= 1; /*lint !e701*/
1642  if( presoldata->numcurrentpairs > presoldata->nummaxpairs )
1643  presoldata->numcurrentpairs = presoldata->nummaxpairs;
1644  }
1645  paircnt++;
1646 
1647  if( !col1domcol2 && !col2domcol1 )
1648  continue;
1649 
1650  /* get the data for both columns */
1651  vals1 = SCIPmatrixGetColValPtr(matrix, col1);
1652  rows1 = SCIPmatrixGetColIdxPtr(matrix, col1);
1653  nrows1 = SCIPmatrixGetColNNonzs(matrix, col1);
1654  r1 = 0;
1655  vals2 = SCIPmatrixGetColValPtr(matrix, col2);
1656  rows2 = SCIPmatrixGetColIdxPtr(matrix, col2);
1657  nrows2 = SCIPmatrixGetColNNonzs(matrix, col2);
1658  r2 = 0;
1659 
1660  /* do we have a obj constant? */
1661  if( nrows1 == 0 || nrows2 == 0 )
1662  continue;
1663 
1664  /* initialize temporary bounds of dominating variable */
1665  tmpupperbounddominatingcol1 = SCIPinfinity(scip);
1666  tmpupperbounddominatingcol2 = tmpupperbounddominatingcol1;
1667  tmpwclowerbounddominatingcol1 = -SCIPinfinity(scip);
1668  tmpwclowerbounddominatingcol2 = tmpwclowerbounddominatingcol1;
1669  tmplowerbounddominatingcol1 = -SCIPinfinity(scip);
1670  tmplowerbounddominatingcol2 = tmplowerbounddominatingcol1;
1671  tmpwcupperbounddominatingcol1 = SCIPinfinity(scip);
1672  tmpwcupperbounddominatingcol2 = tmpwcupperbounddominatingcol1;
1673 
1674  /* initialize temporary bounds of dominated variable */
1675  tmpupperbounddominatedcol1 = SCIPinfinity(scip);
1676  tmpupperbounddominatedcol2 = tmpupperbounddominatedcol1;
1677  tmpwclowerbounddominatedcol1 = -SCIPinfinity(scip);
1678  tmpwclowerbounddominatedcol2 = tmpwclowerbounddominatedcol1;
1679  tmplowerbounddominatedcol1 = -SCIPinfinity(scip);
1680  tmplowerbounddominatedcol2 = tmplowerbounddominatedcol1;
1681  tmpwcupperbounddominatedcol1 = SCIPinfinity(scip);
1682  tmpwcupperbounddominatedcol2 = tmpwcupperbounddominatedcol1;
1683 
1684  /* compare rows of this column pair */
1685  while( (col1domcol2 || col2domcol1) && (r1 < nrows1 || r2 < nrows2) )
1686  {
1687  assert((r1 >= nrows1-1) || (rows1[r1] < rows1[r1+1]));
1688  assert((r2 >= nrows2-1) || (rows2[r2] < rows2[r2+1]));
1689 
1690  /* there is a nonredundant row containing column 1 but not column 2 */
1691  if( r1 < nrows1 && (r2 == nrows2 || rows1[r1] < rows2[r2]) )
1692  {
1693  /* dominance depends on the type of relation */
1694  if( !SCIPmatrixIsRowRhsInfinity(matrix, rows1[r1]) )
1695  {
1696  /* no dominance relation for equations or ranged rows */
1697  col2domcol1 = FALSE;
1698  col1domcol2 = FALSE;
1699  }
1700  else
1701  {
1702  /* >= relation, larger coefficients dominate smaller ones */
1703  if( vals1[r1] > 0.0 )
1704  col2domcol1 = FALSE;
1705  else
1706  col1domcol2 = FALSE;
1707  }
1708 
1709  r1++;
1710  }
1711  /* there is a nonredundant row containing column 2, but not column 1 */
1712  else if( r2 < nrows2 && (r1 == nrows1 || rows1[r1] > rows2[r2]) )
1713  {
1714  /* dominance depends on the type of relation */
1715  if( !SCIPmatrixIsRowRhsInfinity(matrix, rows2[r2]) )
1716  {
1717  /* no dominance relation for equations or ranged rows */
1718  col2domcol1 = FALSE;
1719  col1domcol2 = FALSE;
1720  }
1721  else
1722  {
1723  /* >= relation, larger coefficients dominate smaller ones */
1724  if( vals2[r2] < 0.0 )
1725  col2domcol1 = FALSE;
1726  else
1727  col1domcol2 = FALSE;
1728  }
1729 
1730  r2++;
1731  }
1732  /* if both columns appear in a common row, compare the coefficients */
1733  else
1734  {
1735  assert(r1 < nrows1 && r2 < nrows2);
1736  assert(rows1[r1] == rows2[r2]);
1737 
1738  /* if both columns are binary variables we check if they have a common clique
1739  * and do not calculate any bounds
1740  */
1741  if( onlybinvars && !onlyoneone )
1742  {
1743  if( vals1[r1] < 0 && vals2[r2] < 0 )
1744  {
1745  if( (SCIPmatrixGetRowNMaxActPosInf(matrix, rows1[r1]) + SCIPmatrixGetRowNMaxActNegInf(matrix, rows1[r1]) == 0)
1746  && SCIPisFeasLE(scip, SCIPmatrixGetRowMaxActivity(matrix, rows1[r1]) + MAX(vals1[r1], vals2[r2]),
1747  SCIPmatrixGetRowLhs(matrix, rows1[r1])) )
1748  {
1749  onlyoneone = TRUE;
1750  }
1751  }
1752 
1753  if( !onlyoneone && !SCIPmatrixIsRowRhsInfinity(matrix, rows1[r1]) )
1754  {
1755  if ( vals1[r1] > 0 && vals2[r2] > 0 )
1756  {
1757  if( (SCIPmatrixGetRowNMinActPosInf(matrix, rows1[r1]) + SCIPmatrixGetRowNMinActNegInf(matrix, rows1[r1]) == 0)
1758  && SCIPisFeasGE(scip, SCIPmatrixGetRowMinActivity(matrix, rows1[r1]) + MIN(vals1[r1], vals2[r2]),
1759  SCIPmatrixGetRowRhs(matrix, rows1[r1])) )
1760  {
1761  onlyoneone = TRUE;
1762  }
1763  }
1764  }
1765 
1766  if( onlyoneone )
1767  {
1768  /* reset bounds */
1769  tmpupperbounddominatingcol1 = SCIPinfinity(scip);
1770  tmpupperbounddominatingcol2 = tmpupperbounddominatingcol1;
1771  tmpwclowerbounddominatingcol1 = -SCIPinfinity(scip);
1772  tmpwclowerbounddominatingcol2 = tmpwclowerbounddominatingcol1;
1773  tmplowerbounddominatingcol1 = -SCIPinfinity(scip);
1774  tmplowerbounddominatingcol2 = tmplowerbounddominatingcol1;
1775  tmpwcupperbounddominatingcol1 = SCIPinfinity(scip);
1776  tmpwcupperbounddominatingcol2 = tmpwcupperbounddominatingcol1;
1777 
1778  tmpupperbounddominatedcol1 = SCIPinfinity(scip);
1779  tmpupperbounddominatedcol2 = tmpupperbounddominatedcol1;
1780  tmpwclowerbounddominatedcol1 = -SCIPinfinity(scip);
1781  tmpwclowerbounddominatedcol2 = tmpwclowerbounddominatedcol1;
1782  tmplowerbounddominatedcol1 = -SCIPinfinity(scip);
1783  tmplowerbounddominatedcol2 = tmplowerbounddominatedcol1;
1784  tmpwcupperbounddominatedcol1 = SCIPinfinity(scip);
1785  tmpwcupperbounddominatedcol2 = tmpwcupperbounddominatedcol1;
1786  }
1787  }
1788 
1789  /* dominance depends on the type of inequality */
1790  if( !SCIPmatrixIsRowRhsInfinity(matrix, rows1[r1]) )
1791  {
1792  /* no dominance relation if coefficients differ for equations or ranged rows */
1793  if( !SCIPisEQ(scip, vals1[r1], vals2[r2]) )
1794  {
1795  col2domcol1 = FALSE;
1796  col1domcol2 = FALSE;
1797  }
1798  }
1799  else
1800  {
1801  /* >= relation, larger coefficients dominate smaller ones */
1802  if( vals1[r1] > vals2[r2] )
1803  col2domcol1 = FALSE;
1804  else if( vals1[r1] < vals2[r2] )
1805  col1domcol2 = FALSE;
1806  }
1807 
1808  /* we do not use bound calulations if two binary variable are in one common clique.
1809  * for the other cases we claim the same sign for the coefficients to
1810  * achieve monotonically decreasing predictive bound functions.
1811  */
1812  if( !onlyoneone &&
1813  ((vals1[r1] < 0 && vals2[r2] < 0) || (vals1[r1] > 0 && vals2[r2] > 0)) )
1814  {
1815  if( col1domcol2 )
1816  {
1817  /* update bounds of dominating variable for column 1 */
1818  SCIP_CALL( updateBounds(scip, matrix, rows1[r1],
1819  col1, vals1[r1], col2, vals2[r2], TRUE,
1820  &tmpupperbounddominatingcol1, &tmpwclowerbounddominatingcol1,
1821  &tmplowerbounddominatingcol1, &tmpwcupperbounddominatingcol1) );
1822 
1823  /* update bounds of dominated variable for column 1 */
1824  SCIP_CALL( updateBounds(scip, matrix, rows1[r1],
1825  col1, vals1[r1], col2, vals2[r2], FALSE,
1826  &tmpupperbounddominatedcol1, &tmpwclowerbounddominatedcol1,
1827  &tmplowerbounddominatedcol1, &tmpwcupperbounddominatedcol1) );
1828  }
1829 
1830  if( col2domcol1 )
1831  {
1832  /* update bounds of dominating variable for column 2 */
1833  SCIP_CALL( updateBounds(scip, matrix, rows2[r2],
1834  col2, vals2[r2], col1, vals1[r1], TRUE,
1835  &tmpupperbounddominatingcol2, &tmpwclowerbounddominatingcol2,
1836  &tmplowerbounddominatingcol2, &tmpwcupperbounddominatingcol2) );
1837 
1838  /* update bounds of dominated variable for column 2 */
1839  SCIP_CALL( updateBounds(scip, matrix, rows2[r2],
1840  col2, vals2[r2], col1, vals1[r1], FALSE,
1841  &tmpupperbounddominatedcol2, &tmpwclowerbounddominatedcol2,
1842  &tmplowerbounddominatedcol2, &tmpwcupperbounddominatedcol2) );
1843  }
1844  }
1845 
1846  r1++;
1847  r2++;
1848  }
1849  }
1850 
1851  /* a column is only dominated, if there are no more rows in which it is contained */
1852  col1domcol2 = col1domcol2 && r2 == nrows2;
1853  col2domcol1 = col2domcol1 && r1 == nrows1;
1854 
1855  if( !col1domcol2 && !col2domcol1 )
1856  continue;
1857 
1858  /* no dominance relation for left equations or ranged rows */
1859  while( r1 < nrows1 )
1860  {
1861  if( !SCIPmatrixIsRowRhsInfinity(matrix, rows1[r1]) )
1862  {
1863  col2domcol1 = FALSE;
1864  col1domcol2 = FALSE;
1865  break;
1866  }
1867  r1++;
1868  }
1869  if( !col1domcol2 && !col2domcol1 )
1870  continue;
1871  while( r2 < nrows2 )
1872  {
1873  if( !SCIPmatrixIsRowRhsInfinity(matrix, rows2[r2]) )
1874  {
1875  col2domcol1 = FALSE;
1876  col1domcol2 = FALSE;
1877  break;
1878  }
1879  r2++;
1880  }
1881 
1882  if( col1domcol2 || col2domcol1 )
1883  (*ndomrelations)++;
1884 
1885  if( col1domcol2 && col2domcol1 )
1886  {
1887  /* prefer the variable as dominating variable with the greater upper bound */
1888  if( SCIPisGE(scip, SCIPvarGetUbGlobal(varcol1), SCIPvarGetUbGlobal(varcol2)) )
1889  col2domcol1 = FALSE;
1890  else
1891  col1domcol2 = FALSE;
1892  }
1893 
1894  /* use dominance relation and clique/bound-information
1895  * to find variable fixings. additionally try to strengthen
1896  * variable bounds by predictive bound strengthening.
1897  */
1898  if( col1domcol2 )
1899  {
1900  SCIP_CALL( findFixings(scip, matrix, varcol1, col1,
1901  tmpupperbounddominatingcol1, tmpwclowerbounddominatingcol1,
1902  tmplowerbounddominatingcol1, tmpwcupperbounddominatingcol1,
1903  varcol2, col2,
1904  varstofix, onlybinvars, onlyoneone, nfixings) );
1905 
1906  if( presoldata->predbndstr )
1907  {
1908  SCIP_CALL( predBndStr(scip, varcol1, col1,
1909  tmpupperbounddominatingcol1,
1910  tmplowerbounddominatingcol1, tmpwcupperbounddominatingcol1,
1911  varcol2, col2,
1912  tmpupperbounddominatedcol1, tmpwclowerbounddominatedcol1,
1913  tmplowerbounddominatedcol1,
1914  varstofix, nchgbds) );
1915  }
1916  }
1917  else if( col2domcol1 )
1918  {
1919  SCIP_CALL( findFixings(scip, matrix, varcol2, col2,
1920  tmpupperbounddominatingcol2, tmpwclowerbounddominatingcol2,
1921  tmplowerbounddominatingcol2, tmpwcupperbounddominatingcol2,
1922  varcol1, col1,
1923  varstofix, onlybinvars, onlyoneone, nfixings) );
1924 
1925  if( presoldata->predbndstr )
1926  {
1927  SCIP_CALL( predBndStr(scip, varcol2, col2,
1928  tmpupperbounddominatingcol2,
1929  tmplowerbounddominatingcol2, tmpwcupperbounddominatingcol2,
1930  varcol1, col1,
1931  tmpupperbounddominatedcol2, tmpwclowerbounddominatedcol2,
1932  tmplowerbounddominatedcol2,
1933  varstofix, nchgbds) );
1934  }
1935  }
1936  if( varstofix[col1] == FIXATLB )
1937  break;
1938  }
1939  }
1940 
1941  return SCIP_OKAY;
1942 }
1943 
1944 
1945 /*
1946  * Callback methods of presolver
1947  */
1948 
1949 
1950 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
1951 static
1952 SCIP_DECL_PRESOLCOPY(presolCopyDomcol)
1953 { /*lint --e{715}*/
1954  assert(scip != NULL);
1955  assert(presol != NULL);
1956  assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
1957 
1958  /* call inclusion method of presolver */
1959  SCIP_CALL( SCIPincludePresolDomcol(scip) );
1960 
1961  return SCIP_OKAY;
1962 }
1963 
1964 /** destructor of presolver to free user data (called when SCIP is exiting) */
1965 static
1966 SCIP_DECL_PRESOLFREE(presolFreeDomcol)
1967 { /*lint --e{715}*/
1968  SCIP_PRESOLDATA* presoldata;
1969 
1970  /* free presolver data */
1971  presoldata = SCIPpresolGetData(presol);
1972  assert(presoldata != NULL);
1973 
1974  SCIPfreeBlockMemory(scip, &presoldata);
1975  SCIPpresolSetData(presol, NULL);
1976 
1977  return SCIP_OKAY;
1978 }
1979 
1980 /** execution method of presolver */
1981 static
1982 SCIP_DECL_PRESOLEXEC(presolExecDomcol)
1983 { /*lint --e{715}*/
1984  SCIP_PRESOLDATA* presoldata;
1985  SCIP_MATRIX* matrix;
1986  SCIP_Bool initialized;
1987  SCIP_Bool complete;
1988 
1989  assert(result != NULL);
1990  *result = SCIP_DIDNOTRUN;
1991 
1992  if( (SCIPgetStage(scip) != SCIP_STAGE_PRESOLVING) || SCIPinProbing(scip) || SCIPisNLPEnabled(scip) )
1993  return SCIP_OKAY;
1994 
1995  if( SCIPisStopped(scip) || SCIPgetNActivePricers(scip) > 0 )
1996  return SCIP_OKAY;
1997 
1998  if( !SCIPallowDualReds(scip) )
1999  return SCIP_OKAY;
2000 
2001  presoldata = SCIPpresolGetData(presol);
2002  assert(presoldata != NULL);
2003 
2004  /* don't run for pure LPs */
2005  if( !presoldata->continuousred && (SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip) == 0) )
2006  return SCIP_OKAY;
2007 
2008  *result = SCIP_DIDNOTFIND;
2009 
2010  matrix = NULL;
2011  SCIP_CALL( SCIPmatrixCreate(scip, &matrix, &initialized, &complete) );
2012 
2013  if( initialized && complete )
2014  {
2015  int nfixings;
2016  SCIP_Longint ndomrelations;
2017  int v;
2018  int r;
2019  FIXINGDIRECTION* varstofix;
2020  SCIP_Bool* varsprocessed;
2021  int nrows;
2022  int ncols;
2023  int* rowidxsorted;
2024  int* rowsparsity;
2025  int varcount;
2026  int* consearchcols;
2027  int* intsearchcols;
2028  int* binsearchcols;
2029  int nconfill;
2030  int nintfill;
2031  int nbinfill;
2032 #ifdef SCIP_DEBUG
2033  int nconvarsfixed = 0;
2034  int nintvarsfixed = 0;
2035  int nbinvarsfixed = 0;
2036 #endif
2037  int* pclass;
2038  int* colidx;
2039  int pclassstart;
2040  int pc;
2041  SCIP_Bool* varineq;
2042 
2043  nfixings = 0;
2044  ndomrelations = 0;
2045  nrows = SCIPmatrixGetNRows(matrix);
2046  ncols = SCIPmatrixGetNColumns(matrix);
2047  assert(SCIPgetNVars(scip) == ncols);
2048 
2049  SCIP_CALL( SCIPallocBufferArray(scip, &varstofix, ncols) );
2050  BMSclearMemoryArray(varstofix, ncols);
2051 
2052  SCIP_CALL( SCIPallocBufferArray(scip, &varsprocessed, ncols) );
2053  BMSclearMemoryArray(varsprocessed, ncols);
2054 
2055  SCIP_CALL( SCIPallocBufferArray(scip, &consearchcols, ncols) );
2056  SCIP_CALL( SCIPallocBufferArray(scip, &intsearchcols, ncols) );
2057  SCIP_CALL( SCIPallocBufferArray(scip, &binsearchcols, ncols) );
2058 
2059  SCIP_CALL( SCIPallocBufferArray(scip, &rowidxsorted, nrows) );
2060  SCIP_CALL( SCIPallocBufferArray(scip, &rowsparsity, nrows) );
2061  for( r = 0; r < nrows; ++r )
2062  {
2063  rowidxsorted[r] = r;
2064  rowsparsity[r] = SCIPmatrixGetRowNNonzs(matrix, r);
2065  }
2066 
2067  SCIP_CALL( SCIPallocBufferArray(scip, &pclass, ncols) );
2068  SCIP_CALL( SCIPallocBufferArray(scip, &colidx, ncols) );
2069  SCIP_CALL( SCIPallocBufferArray(scip, &varineq, ncols) );
2070  for( v = 0; v < ncols; v++ )
2071  {
2072  colidx[v] = v;
2073  varineq[v] = FALSE;
2074  }
2075 
2076  /* init pair comparision control */
2077  presoldata->numcurrentpairs = presoldata->nummaxpairs;
2078 
2079  varcount = 0;
2080 
2081  /* 1.stage: search dominance relations of parallel columns
2082  * within equalities and ranged rows
2083  */
2084  if( (presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 )
2085  {
2086  SCIP_CALL( detectParallelCols(scip, matrix, pclass, varineq) );
2087  SCIPsortIntInt(pclass, colidx, ncols);
2088 
2089  pc = 0;
2090  while( pc < ncols )
2091  {
2092  int varidx;
2093 
2094  varidx = 0;
2095  nconfill = 0;
2096  nintfill = 0;
2097  nbinfill = 0;
2098 
2099  pclassstart = pclass[pc];
2100  while( pc < ncols && pclassstart == pclass[pc] )
2101  {
2102  SCIP_VAR* var;
2103 
2104  varidx = colidx[pc];
2105  var = SCIPmatrixGetVar(matrix, varidx);
2106 
2107  /* we only regard variables which were not processed yet and
2108  * are present within equalities or ranged rows
2109  */
2110  if( !varsprocessed[varidx] && varineq[varidx] )
2111  {
2112  /* we search only for dominance relations between the same variable type */
2113  if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS )
2114  {
2115  consearchcols[nconfill++] = varidx;
2116  }
2117  else if( SCIPvarIsBinary(var) )
2118  {
2119  binsearchcols[nbinfill++] = varidx;
2120  }
2121  else
2122  {
2123  assert(SCIPvarGetType(var) == SCIP_VARTYPE_INTEGER || SCIPvarGetType(var) == SCIP_VARTYPE_IMPLINT);
2124  intsearchcols[nintfill++] = varidx;
2125  }
2126  }
2127  ++pc;
2128  }
2129 
2130  /* continuous variables */
2131  if( nconfill > 1 && presoldata->continuousred )
2132  {
2133  SCIP_CALL( findDominancePairs(scip, matrix, presoldata, consearchcols, nconfill, FALSE,
2134  varstofix, &nfixings, &ndomrelations, nchgbds) );
2135 
2136  for( v = 0; v < nconfill; ++v )
2137  varsprocessed[consearchcols[v]] = TRUE;
2138 
2139  varcount += nconfill;
2140  }
2141  else if( nconfill == 1 )
2142  {
2143  if( varineq[varidx] )
2144  varsprocessed[consearchcols[0]] = TRUE;
2145  }
2146 
2147  /* integer and impl-integer variables */
2148  if( nintfill > 1 )
2149  {
2150  SCIP_CALL( findDominancePairs(scip, matrix, presoldata, intsearchcols, nintfill, FALSE,
2151  varstofix, &nfixings, &ndomrelations, nchgbds) );
2152 
2153  for( v = 0; v < nintfill; ++v )
2154  varsprocessed[intsearchcols[v]] = TRUE;
2155 
2156  varcount += nintfill;
2157  }
2158  else if( nintfill == 1 )
2159  {
2160  if( varineq[varidx] )
2161  varsprocessed[intsearchcols[0]] = TRUE;
2162  }
2163 
2164  /* binary variables */
2165  if( nbinfill > 1 )
2166  {
2167  SCIP_CALL( findDominancePairs(scip, matrix, presoldata, binsearchcols, nbinfill, TRUE,
2168  varstofix, &nfixings, &ndomrelations, nchgbds) );
2169 
2170  for( v = 0; v < nbinfill; ++v )
2171  varsprocessed[binsearchcols[v]] = TRUE;
2172 
2173  varcount += nbinfill;
2174  }
2175  else if( nbinfill == 1 )
2176  {
2177  if( varineq[varidx] )
2178  varsprocessed[binsearchcols[0]] = TRUE;
2179  }
2180 
2181  if( varcount >= ncols )
2182  break;
2183  }
2184  }
2185 
2186  /* 2.stage: search dominance relations for the remaining columns
2187  * by increasing row-sparsity
2188  */
2189  if( (presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 )
2190  {
2191  SCIPsortIntInt(rowsparsity, rowidxsorted, nrows);
2192 
2193  for( r = 0; r < nrows; ++r )
2194  {
2195  int rowidx;
2196  int* rowpnt;
2197  int* rowend;
2198 
2199  /* break if the time limit was reached; since the check is expensive,
2200  * we only check all 1000 constraints
2201  */
2202  if( (r % 1000 == 0) && SCIPisStopped(scip) )
2203  break;
2204 
2205  rowidx = rowidxsorted[r];
2206  rowpnt = SCIPmatrixGetRowIdxPtr(matrix, rowidx);
2207  rowend = rowpnt + SCIPmatrixGetRowNNonzs(matrix, rowidx);
2208 
2209  if( SCIPmatrixGetRowNNonzs(matrix, rowidx) == 1 )
2210  continue;
2211 
2212  nconfill = 0;
2213  nintfill = 0;
2214  nbinfill = 0;
2215 
2216  for( ; rowpnt < rowend; rowpnt++ )
2217  {
2218  if( !(varsprocessed[*rowpnt]) )
2219  {
2220  int varidx;
2221  SCIP_VAR* var;
2222 
2223  varidx = *rowpnt;
2224  var = SCIPmatrixGetVar(matrix, varidx);
2225 
2226  /* we search only for dominance relations between the same variable type */
2227  if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS )
2228  {
2229  consearchcols[nconfill++] = varidx;
2230  }
2231  else if( SCIPvarIsBinary(var) )
2232  {
2233  binsearchcols[nbinfill++] = varidx;
2234  }
2235  else
2236  {
2237  assert(SCIPvarGetType(var) == SCIP_VARTYPE_INTEGER || SCIPvarGetType(var) == SCIP_VARTYPE_IMPLINT);
2238  intsearchcols[nintfill++] = varidx;
2239  }
2240  }
2241  }
2242 
2243  /* continuous variables */
2244  if( nconfill > 1 && presoldata->continuousred )
2245  {
2246  SCIP_CALL( findDominancePairs(scip, matrix, presoldata, consearchcols, nconfill, FALSE,
2247  varstofix, &nfixings, &ndomrelations, nchgbds) );
2248 
2249  for( v = 0; v < nconfill; ++v )
2250  varsprocessed[consearchcols[v]] = TRUE;
2251 
2252  varcount += nconfill;
2253  }
2254 
2255  /* integer and impl-integer variables */
2256  if( nintfill > 1 )
2257  {
2258  SCIP_CALL( findDominancePairs(scip, matrix, presoldata, intsearchcols, nintfill, FALSE,
2259  varstofix, &nfixings, &ndomrelations, nchgbds) );
2260 
2261  for( v = 0; v < nintfill; ++v )
2262  varsprocessed[intsearchcols[v]] = TRUE;
2263 
2264  varcount += nintfill;
2265  }
2266 
2267  /* binary variables */
2268  if( nbinfill > 1 )
2269  {
2270  SCIP_CALL( findDominancePairs(scip, matrix, presoldata, binsearchcols, nbinfill, TRUE,
2271  varstofix, &nfixings, &ndomrelations, nchgbds) );
2272 
2273  for( v = 0; v < nbinfill; ++v )
2274  varsprocessed[binsearchcols[v]] = TRUE;
2275 
2276  varcount += nbinfill;
2277  }
2278 
2279  if( varcount >= ncols )
2280  break;
2281  }
2282  }
2283 
2284  if( nfixings > 0 )
2285  {
2286  int oldnfixedvars;
2287 
2288  oldnfixedvars = *nfixedvars;
2289 
2290  for( v = ncols - 1; v >= 0; --v )
2291  {
2292  SCIP_Bool infeasible;
2293  SCIP_Bool fixed;
2294  SCIP_VAR* var;
2295 
2296  var = SCIPmatrixGetVar(matrix,v);
2297 
2298  if( SCIPvarGetNLocksUp(var) != SCIPmatrixGetColNUplocks(matrix, v) ||
2299  SCIPvarGetNLocksDown(var) != SCIPmatrixGetColNDownlocks(matrix, v) )
2300  {
2301  /* no fixing, locks not consistent */
2302  continue;
2303  }
2304 
2305  if( varstofix[v] == FIXATLB )
2306  {
2307  SCIP_Real lb;
2308 
2309  lb = SCIPvarGetLbGlobal(var);
2310  assert(SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS || SCIPisFeasIntegral(scip, lb));
2311 
2312  /* fix at lower bound */
2313  SCIP_CALL( SCIPfixVar(scip, var, lb, &infeasible, &fixed) );
2314  if( infeasible )
2315  {
2316  SCIPdebugMsg(scip, " -> infeasible fixing\n");
2317  *result = SCIP_CUTOFF;
2318 
2319  break;
2320  }
2321  assert(fixed);
2322  (*nfixedvars)++;
2323 
2324 #ifdef SCIP_DEBUG
2325  if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS )
2326  nconvarsfixed++;
2327  else if( SCIPvarIsBinary(var) )
2328  nbinvarsfixed++;
2329  else
2330  nintvarsfixed++;
2331 #endif
2332  }
2333  else if( varstofix[v] == FIXATUB )
2334  {
2335  SCIP_Real ub;
2336 
2337  ub = SCIPvarGetUbGlobal(var);
2338  assert(SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS || SCIPisFeasIntegral(scip, ub));
2339 
2340  /* fix at upper bound */
2341  SCIP_CALL( SCIPfixVar(scip, var, ub, &infeasible, &fixed) );
2342  if( infeasible )
2343  {
2344  SCIPdebugMsg(scip, " -> infeasible fixing\n");
2345  *result = SCIP_CUTOFF;
2346 
2347  break;
2348  }
2349  assert(fixed);
2350  (*nfixedvars)++;
2351 
2352 #ifdef SCIP_DEBUG
2353  if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS )
2354  nconvarsfixed++;
2355  else if( SCIPvarIsBinary(var) )
2356  nbinvarsfixed++;
2357  else
2358  nintvarsfixed++;
2359 #endif
2360  }
2361  }
2362 
2363  if( *result != SCIP_CUTOFF && *nfixedvars > oldnfixedvars )
2364  *result = SCIP_SUCCESS;
2365  }
2366 
2367  SCIPfreeBufferArray(scip, &varineq);
2368  SCIPfreeBufferArray(scip, &colidx);
2369  SCIPfreeBufferArray(scip, &pclass);
2370  SCIPfreeBufferArray(scip, &rowsparsity);
2371  SCIPfreeBufferArray(scip, &rowidxsorted);
2372  SCIPfreeBufferArray(scip, &binsearchcols);
2373  SCIPfreeBufferArray(scip, &intsearchcols);
2374  SCIPfreeBufferArray(scip, &consearchcols);
2375  SCIPfreeBufferArray(scip, &varsprocessed);
2376  SCIPfreeBufferArray(scip, &varstofix);
2377 
2378 #ifdef SCIP_DEBUG
2379  if( (nconvarsfixed + nintvarsfixed + nbinvarsfixed) > 0 )
2380  {
2381  SCIPdebugMsg(scip, "### %d vars [%" SCIP_LONGINT_FORMAT " dom] => fixed [cont: %d, int: %d, bin: %d], %scutoff detected\n",
2382  ncols, ndomrelations, nconvarsfixed, nintvarsfixed, nbinvarsfixed, (*result != SCIP_CUTOFF) ? "no " : "");
2383  }
2384 #endif
2385  }
2386 
2387  SCIPmatrixFree(scip, &matrix);
2388 
2389  return SCIP_OKAY;
2390 }
2391 
2392 /*
2393  * presolver specific interface methods
2394  */
2395 
2396 /** creates the domcol presolver and includes it in SCIP */
2397 SCIP_RETCODE SCIPincludePresolDomcol(
2398  SCIP* scip /**< SCIP data structure */
2399  )
2400 {
2401  SCIP_PRESOLDATA* presoldata;
2402  SCIP_PRESOL* presol;
2403 
2404  /* create domcol presolver data */
2405  SCIP_CALL( SCIPallocBlockMemory(scip, &presoldata) );
2406 
2407  /* include presolver */
2408  SCIP_CALL( SCIPincludePresolBasic(scip, &presol, PRESOL_NAME, PRESOL_DESC, PRESOL_PRIORITY, PRESOL_MAXROUNDS,
2409  PRESOL_TIMING, presolExecDomcol, presoldata) );
2410  SCIP_CALL( SCIPsetPresolCopy(scip, presol, presolCopyDomcol) );
2411  SCIP_CALL( SCIPsetPresolFree(scip, presol, presolFreeDomcol) );
2412 
2413  SCIP_CALL( SCIPaddIntParam(scip,
2414  "presolving/domcol/numminpairs",
2415  "minimal number of pair comparisons",
2416  &presoldata->numminpairs, FALSE, DEFAULT_NUMMINPAIRS, 100, DEFAULT_NUMMAXPAIRS, NULL, NULL) );
2417 
2418  SCIP_CALL( SCIPaddIntParam(scip,
2419  "presolving/domcol/nummaxpairs",
2420  "maximal number of pair comparisons",
2421  &presoldata->nummaxpairs, FALSE, DEFAULT_NUMMAXPAIRS, DEFAULT_NUMMINPAIRS, 1000000000, NULL, NULL) );
2422 
2423  SCIP_CALL( SCIPaddBoolParam(scip,
2424  "presolving/domcol/predbndstr",
2425  "should predictive bound strengthening be applied?",
2426  &presoldata->predbndstr, FALSE, DEFAULT_PREDBNDSTR, NULL, NULL) );
2427 
2428  SCIP_CALL( SCIPaddBoolParam(scip,
2429  "presolving/domcol/continuousred",
2430  "should reductions for continuous variables be performed?",
2431  &presoldata->continuousred, FALSE, DEFAULT_CONTINUOUS_RED, NULL, NULL) );
2432 
2433  return SCIP_OKAY;
2434 }
SCIPsortRealInt
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
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.c:6854
SCIPgetNIntVars
int SCIPgetNIntVars(SCIP *scip)
Definition: scip.c:11721
SCIP_Presol
Definition: struct_presol.h:37
PRESOL_PRIORITY
#define PRESOL_PRIORITY
Definition: presol_domcol.c:48
SCIP_DIDNOTRUN
Definition: type_result.h:33
SCIP_PRESOLDATA
struct SCIP_PresolData SCIP_PRESOLDATA
Definition: type_presol.h:37
SCIPmatrixGetVar
SCIP_VAR * SCIPmatrixGetVar(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1325
SCIPvarsHaveCommonClique
SCIP_Bool SCIPvarsHaveCommonClique(SCIP_VAR *var1, SCIP_Bool value1, SCIP_VAR *var2, SCIP_Bool value2, SCIP_Bool regardimplics)
Definition: var.c:10785
SCIPmatrixGetNRows
int SCIPmatrixGetNRows(SCIP_MATRIX *matrix)
Definition: matrix.c:1397
SCIPsetPresolFree
SCIP_RETCODE SCIPsetPresolFree(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLFREE((*presolfree)))
Definition: scip.c:6905
SCIPgetStage
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip.c:814
calcVarBoundsDominating
static SCIP_RETCODE calcVarBoundsDominating(SCIP *scip, SCIP_MATRIX *matrix, int row, int coldominating, SCIP_Real valdominating, int coldominated, SCIP_Real valdominated, SCIP_Bool *ubcalculated, SCIP_Real *calculatedub, SCIP_Bool *wclbcalculated, SCIP_Real *calculatedwclb, SCIP_Bool *lbcalculated, SCIP_Real *calculatedlb, SCIP_Bool *wcubcalculated, SCIP_Real *calculatedwcub)
Definition: presol_domcol.c:760
DEFAULT_PREDBNDSTR
#define DEFAULT_PREDBNDSTR
Definition: presol_domcol.c:55
SCIPvarGetLbGlobal
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17166
NOFIX
Definition: presol_domcol.c:78
FIXATLB
Definition: presol_domcol.c:77
SCIP_SUCCESS
Definition: type_result.h:49
SCIPisPositive
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
Definition: scip.c:45876
SCIPisGE
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45803
SCIP_Var
Definition: struct_var.h:197
SCIPvarIsBinary
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16732
updateBounds
static SCIP_RETCODE updateBounds(SCIP *scip, SCIP_MATRIX *matrix, int row, int col1, SCIP_Real val1, int col2, SCIP_Real val2, SCIP_Bool predictdominating, SCIP_Real *upperbound, SCIP_Real *wclowerbound, SCIP_Real *lowerbound, SCIP_Real *wcupperbound)
Definition: presol_domcol.c:933
SCIPmatrixFree
void SCIPmatrixFree(SCIP *scip, SCIP_MATRIX **matrix)
Definition: matrix.c:782
SCIPisFeasGE
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46138
presol_domcol.h
dominated column presolver
FALSE
#define FALSE
Definition: def.h:64
SCIPgetNActivePricers
int SCIPgetNActivePricers(SCIP *scip)
Definition: scip.c:5655
SCIPinfinity
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:45816
SCIPisNegative
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
Definition: scip.c:45888
TRUE
#define TRUE
Definition: def.h:63
PRESOL_NAME
#define PRESOL_NAME
Definition: presol_domcol.c:46
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_VARTYPE_BINARY
Definition: type_var.h:53
SCIP_PRESOLTIMING_EXHAUSTIVE
#define SCIP_PRESOLTIMING_EXHAUSTIVE
Definition: type_timing.h:45
PRESOL_DESC
#define PRESOL_DESC
Definition: presol_domcol.c:47
SCIPpresolGetData
SCIP_PRESOLDATA * SCIPpresolGetData(SCIP_PRESOL *presol)
Definition: presol.c:466
SCIPincludePresolDomcol
SCIP_RETCODE SCIPincludePresolDomcol(SCIP *scip)
Definition: presol_domcol.c:2397
SCIPfreeBlockMemory
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:21907
SCIPsortIntIntReal
void SCIPsortIntIntReal(int *intarray1, int *intarray2, SCIP_Real *realarray, int len)
findFixings
static SCIP_RETCODE findFixings(SCIP *scip, SCIP_MATRIX *matrix, SCIP_VAR *dominatingvar, int dominatingidx, SCIP_Real dominatingub, SCIP_Real dominatingwclb, SCIP_Real dominatinglb, SCIP_Real dominatingwcub, SCIP_VAR *dominatedvar, int dominatedidx, FIXINGDIRECTION *varstofix, SCIP_Bool onlybinvars, SCIP_Bool onlyoneone, int *nfixings)
Definition: presol_domcol.c:1380
PRESOL_TIMING
#define PRESOL_TIMING
Definition: presol_domcol.c:50
SCIPchgVarLb
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:21611
SCIPisEQ
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45751
SCIPfreeBufferArray
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:21937
SCIPmatrixGetRowMaxActivity
SCIP_Real SCIPmatrixGetRowMaxActivity(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1465
DEFAULT_NUMMINPAIRS
#define DEFAULT_NUMMINPAIRS
Definition: presol_domcol.c:52
SCIPallocBlockMemory
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:21890
SCIPdebugMsgPrint
#define SCIPdebugMsgPrint
Definition: scip.h:452
SCIPmatrixCreate
SCIP_RETCODE SCIPmatrixCreate(SCIP *scip, SCIP_MATRIX **matrixptr, SCIP_Bool *initialized, SCIP_Bool *complete)
Definition: matrix.c:430
SCIPdebugMsg
#define SCIPdebugMsg
Definition: scip.h:451
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.c:4202
SCIPmatrixGetRowNNonzs
int SCIPmatrixGetRowNNonzs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1373
SCIPvarGetUbGlobal
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17176
SCIPmatrixGetRowLhs
SCIP_Real SCIPmatrixGetRowLhs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1407
FIXINGDIRECTION
enum Fixingdirection FIXINGDIRECTION
Definition: presol_domcol.c:81
Fixingdirection
Fixingdirection
Definition: presol_domcol.c:75
SCIPmatrixGetColValPtr
SCIP_Real * SCIPmatrixGetColValPtr(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1233
getActivityResidualsLowerBound
static void getActivityResidualsLowerBound(SCIP *scip, SCIP_MATRIX *matrix, int row, int col, SCIP_Real coef, int lowerboundcol, SCIP_Real lowerboundcoef, SCIP_Real *minresactivity, SCIP_Real *maxresactivity, SCIP_Bool *success)
Definition: presol_domcol.c:406
SCIP_DIDNOTFIND
Definition: type_result.h:35
SCIPerrorMessage
#define SCIPerrorMessage
Definition: pub_message.h:45
SCIPsortIntInt
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
SCIPisLT
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45764
SCIPpresolSetData
void SCIPpresolSetData(SCIP_PRESOL *presol, SCIP_PRESOLDATA *presoldata)
Definition: presol.c:476
SCIPmatrixGetRowNMaxActPosInf
int SCIPmatrixGetRowNMaxActPosInf(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1513
SCIPchgVarUb
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:21701
SCIPmatrixGetRowIdxPtr
int * SCIPmatrixGetRowIdxPtr(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1361
SCIPvarGetName
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16552
SCIPisNLPEnabled
SCIP_Bool SCIPisNLPEnabled(SCIP *scip)
Definition: scip.c:30797
NULL
#define NULL
Definition: lpi_spx1.cpp:137
SCIPmatrixGetRowNMaxActNegInf
int SCIPmatrixGetRowNMaxActNegInf(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1501
SCIP_OKAY
Definition: type_retcode.h:33
SCIP_CALL
#define SCIP_CALL(x)
Definition: def.h:306
SCIPisFeasLE
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46112
SCIPmatrixGetRowValPtr
SCIP_Real * SCIPmatrixGetRowValPtr(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1349
predBndStr
static SCIP_RETCODE predBndStr(SCIP *scip, SCIP_VAR *dominatingvar, int dominatingidx, SCIP_Real dominatingub, SCIP_Real dominatinglb, SCIP_Real dominatingwcub, SCIP_VAR *dominatedvar, int dominatedidx, SCIP_Real dominatedub, SCIP_Real dominatedwclb, SCIP_Real dominatedlb, FIXINGDIRECTION *varstofix, int *nchgbds)
Definition: presol_domcol.c:1182
findDominancePairs
static SCIP_RETCODE findDominancePairs(SCIP *scip, SCIP_MATRIX *matrix, SCIP_PRESOLDATA *presoldata, int *searchcols, int searchsize, SCIP_Bool onlybinvars, FIXINGDIRECTION *varstofix, int *nfixings, SCIP_Longint *ndomrelations, int *nchgbds)
Definition: presol_domcol.c:1518
SCIPallocBufferArray
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:21925
SCIP_Bool
#define SCIP_Bool
Definition: def.h:61
SCIP_VARTYPE_IMPLINT
Definition: type_var.h:55
SCIP_DECL_PRESOLFREE
static SCIP_DECL_PRESOLFREE(presolFreeDomcol)
Definition: presol_domcol.c:1966
SCIP_VARTYPE_INTEGER
Definition: type_var.h:54
SCIPvarGetNLocksUp
int SCIPvarGetNLocksUp(SCIP_VAR *var)
Definition: var.c:3217
MAX
#define MAX(x, y)
Definition: tclique_def.h:75
SCIPmatrixGetColIdxPtr
int * SCIPmatrixGetColIdxPtr(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1245
SCIP_STAGE_PRESOLVING
Definition: type_set.h:40
SCIPpresolGetName
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
Definition: presol.c:553
SCIPvarGetObj
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17014
SCIP_VARSTATUS_MULTAGGR
Definition: type_var.h:45
SCIP_Matrix
Definition: struct_matrix.h:38
SCIPfixVar
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip.c:25141
calcVarBoundsDominated
static SCIP_RETCODE calcVarBoundsDominated(SCIP *scip, SCIP_MATRIX *matrix, int row, int coldominating, SCIP_Real valdominating, int coldominated, SCIP_Real valdominated, SCIP_Bool *ubcalculated, SCIP_Real *calculatedub, SCIP_Bool *wclbcalculated, SCIP_Real *calculatedwclb, SCIP_Bool *lbcalculated, SCIP_Real *calculatedlb, SCIP_Bool *wcubcalculated, SCIP_Real *calculatedwcub)
Definition: presol_domcol.c:585
SCIPmatrixGetRowNMinActNegInf
int SCIPmatrixGetRowNMinActNegInf(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1477
SCIPisInfinity
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:45827
SCIP_DECL_PRESOLEXEC
static SCIP_DECL_PRESOLEXEC(presolExecDomcol)
Definition: presol_domcol.c:1982
pub_matrix.h
public methods for matrix
SCIPgetNBinVars
int SCIPgetNBinVars(SCIP *scip)
Definition: scip.c:11676
SCIPinProbing
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip.c:35033
SCIPgetNVars
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11631
getActivityResidualsUpperBound
static void getActivityResidualsUpperBound(SCIP *scip, SCIP_MATRIX *matrix, int row, int col, SCIP_Real coef, int upperboundcol, SCIP_Real upperboundcoef, SCIP_Real *minresactivity, SCIP_Real *maxresactivity, SCIP_Bool *success)
Definition: presol_domcol.c:229
SCIPvarGetNLocksDown
int SCIPvarGetNLocksDown(SCIP_VAR *var)
Definition: var.c:3162
SCIPmatrixGetRowRhs
SCIP_Real SCIPmatrixGetRowRhs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1419
SCIPmatrixIsRowRhsInfinity
SCIP_Bool SCIPmatrixIsRowRhsInfinity(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1431
SCIPsetPresolCopy
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLCOPY((*presolcopy)))
Definition: scip.c:6889
SCIPallowDualReds
SCIP_Bool SCIPallowDualReds(SCIP *scip)
Definition: scip.c:25447
SCIPvarGetStatus
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:16671
DEFAULT_NUMMAXPAIRS
#define DEFAULT_NUMMAXPAIRS
Definition: presol_domcol.c:53
SCIP_Real
#define SCIP_Real
Definition: def.h:135
SCIPisStopped
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1138
detectParallelCols
static SCIP_RETCODE detectParallelCols(SCIP *scip, SCIP_MATRIX *matrix, int *pclass, SCIP_Bool *varineq)
Definition: presol_domcol.c:1013
MIN
#define MIN(x, y)
Definition: memory.c:75
SCIPmatrixGetRowMinActivity
SCIP_Real SCIPmatrixGetRowMinActivity(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1453
SCIPmatrixGetColNDownlocks
int SCIPmatrixGetColNDownlocks(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1313
SCIP_Longint
#define SCIP_Longint
Definition: def.h:120
SCIPvarGetType
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16717
SCIPisZero
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:45864
SCIPmatrixGetRowNMinActPosInf
int SCIPmatrixGetRowNMinActPosInf(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1489
SCIPisLE
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45777
SCIPisFeasIntegral
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:46187
SCIPmatrixGetColNUplocks
int SCIPmatrixGetColNUplocks(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1301
BMSclearMemoryArray
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:85
FIXATUB
Definition: presol_domcol.c:79
SCIP_INVALIDDATA
Definition: type_retcode.h:43
SCIPceil
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
Definition: scip.c:45949
SCIPABORT
#define SCIPABORT()
Definition: def.h:278
PRESOL_MAXROUNDS
#define PRESOL_MAXROUNDS
Definition: presol_domcol.c:49
SCIP_DECL_PRESOLCOPY
static SCIP_DECL_PRESOLCOPY(presolCopyDomcol)
Definition: presol_domcol.c:1952
printRow
static SCIP_RETCODE printRow(SCIP *scip, FZNOUTPUT *fznoutput, const char *type, SCIP_VAR **vars, SCIP_Real *vals, int nvars, SCIP_Real rhs, SCIP_Bool hasfloats)
Definition: reader_fzn.c:3989
SCIPmatrixGetNColumns
int SCIPmatrixGetNColumns(SCIP_MATRIX *matrix)
Definition: matrix.c:1269
DEFAULT_CONTINUOUS_RED
#define DEFAULT_CONTINUOUS_RED
Definition: presol_domcol.c:56
SCIPfloor
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
Definition: scip.c:45937
SCIP_CUTOFF
Definition: type_result.h:39
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.c:4176
SCIPmatrixGetColNNonzs
int SCIPmatrixGetColNNonzs(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1257
SCIP_VARTYPE_CONTINUOUS
Definition: type_var.h:58