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-2018 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 non-empty equations or ranged rows */
1074  if( !SCIPmatrixIsRowRhsInfinity(matrix, r) && SCIPmatrixGetRowNNonzs(matrix, r) > 0 )
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  assert(i > 0);
1112 
1113  /* sort on the pclass values */
1114  if( i > 1 )
1115  {
1116  SCIPsortIntIntReal(pcs, colindices, values, i);
1117  }
1118 
1119  k = 0;
1120  while( TRUE ) /*lint !e716*/
1121  {
1122  assert(k < i);
1123  startpc = pcs[k];
1124  startk = k;
1125 
1126  /* find pclass-sets */
1127  while( k < i && pcs[k] == startpc )
1128  k++;
1129 
1130  /* sort on the A values which have equal pclass values */
1131  if( k - startk > 1 )
1132  SCIPsortRealInt(&(values[startk]), &(colindices[startk]), k - startk);
1133 
1134  t = 0;
1135  while( TRUE ) /*lint !e716*/
1136  {
1137  assert(startk + t < i);
1138  startval = values[startk + t];
1139  startt = t;
1140 
1141  /* find A-sets */
1142  while( t < k - startk && SCIPisEQ(scip, startval, values[startk + t]) )
1143  t++;
1144 
1145  /* get new pclass */
1146  newpclass = pcset[0];
1147  assert(pcsetfill > 0);
1148  pcset[0] = pcset[--pcsetfill];
1149 
1150  /* renumbering */
1151  for( m = startk + startt; m < startk + t; m++ )
1152  {
1153  assert(m < i);
1154  assert(colindices[m] < ncols);
1155  assert(newpclass < ncols);
1156 
1157  pclass[colindices[m]] = newpclass;
1158  classsizes[newpclass]++;
1159  }
1160 
1161  if( t == k - startk )
1162  break;
1163  }
1164 
1165  if( k == SCIPmatrixGetRowNNonzs(matrix, r) )
1166  break;
1167  }
1168  }
1169  }
1170 
1171  SCIPfreeBufferArray(scip, &pcs);
1172  SCIPfreeBufferArray(scip, &colindices);
1173  SCIPfreeBufferArray(scip, &values);
1174  SCIPfreeBufferArray(scip, &pcset);
1175  SCIPfreeBufferArray(scip, &scale);
1176  SCIPfreeBufferArray(scip, &classsizes);
1177 
1178  return SCIP_OKAY;
1179 }
1180 
1181 
1182 /** try to improve variable bounds by predictive bound strengthening */
1183 static
1184 SCIP_RETCODE predBndStr(
1185  SCIP* scip, /**< SCIP main data structure */
1186  SCIP_VAR* dominatingvar, /**< dominating variable */
1187  int dominatingidx, /**< column index of the dominating variable */
1188  SCIP_Real dominatingub, /**< predicted upper bound of the dominating variable */
1189  SCIP_Real dominatinglb, /**< predicted lower bound of the dominating variable */
1190  SCIP_Real dominatingwcub, /**< predicted worst case upper bound of the dominating variable */
1191  SCIP_VAR* dominatedvar, /**< dominated variable */
1192  int dominatedidx, /**< column index of the dominated variable */
1193  SCIP_Real dominatedub, /**< predicted upper bound of the dominated variable */
1194  SCIP_Real dominatedwclb, /**< predicted worst case lower bound of the dominated variable */
1195  SCIP_Real dominatedlb, /**< predicted lower bound of the dominated variable */
1196  FIXINGDIRECTION* varstofix, /**< array holding fixing information */
1197  int* nchgbds /**< count number of bound changes */
1198  )
1199 {
1200  /* we compare only variables from the same type */
1201  if( !(SCIPvarGetType(dominatingvar) == SCIPvarGetType(dominatedvar) ||
1202  SCIPvarIsBinary(dominatingvar) == SCIPvarIsBinary(dominatedvar) ||
1203  (SCIPvarGetType(dominatingvar) == SCIP_VARTYPE_INTEGER && SCIPvarGetType(dominatedvar) == SCIP_VARTYPE_IMPLINT) ||
1204  (SCIPvarGetType(dominatedvar) == SCIP_VARTYPE_INTEGER && SCIPvarGetType(dominatingvar) == SCIP_VARTYPE_IMPLINT)) )
1205  {
1206  return SCIP_OKAY;
1207  }
1208 
1209  if( varstofix[dominatingidx] == NOFIX )
1210  {
1211  /* assume x dominates y (x->y). we get this bound from a positive coefficient
1212  * of the dominating variable. because x->y the dominated variable y has
1213  * a positive coefficient too. thus y contributes to the minactivity with its
1214  * lower bound. but this case is considered within predictive bound analysis.
1215  * thus the dominating upper bound is a common upper bound.
1216  */
1217  if( !SCIPisInfinity(scip, dominatingub) )
1218  {
1219  SCIP_Real newub;
1220  SCIP_Real oldub;
1221  SCIP_Real lb;
1222 
1223  newub = dominatingub;
1224  oldub = SCIPvarGetUbGlobal(dominatingvar);
1225  lb = SCIPvarGetLbGlobal(dominatingvar);
1226 
1227  /* if( SCIPvarGetType(dominatingvar) != SCIP_VARTYPE_CONTINUOUS )
1228  newub = SCIPceil(scip, newub); */
1229 
1230  if( SCIPisLE(scip, lb, newub) && SCIPisLT(scip, newub, oldub) )
1231  {
1232  SCIPdebugMsg(scip, "[ub]\tupper bound for dominating variable <%s> changed: [%.17f,%.17f] -> [%.17f,%.17f]\n",
1233  SCIPvarGetName(dominatingvar), lb, oldub, lb, newub);
1234  SCIP_CALL( SCIPchgVarUb(scip, dominatingvar, newub) );
1235  (*nchgbds)++;
1236  }
1237  }
1238 
1239  /* assume x dominates y (x->y). we get this lower bound of the dominating variable
1240  * from a negative coefficient within a <= relation. if y has a positive coefficient
1241  * we get a common lower bound of x from predictive bound analysis. if y has a
1242  * negative coefficient we get an improved lower bound of x because the minactivity
1243  * is greater. for discrete variables we have to round down the lower bound.
1244  */
1245  if( !SCIPisInfinity(scip, -dominatinglb) )
1246  {
1247  SCIP_Real newlb;
1248  SCIP_Real oldlb;
1249  SCIP_Real ub;
1250 
1251  newlb = dominatinglb;
1252  oldlb = SCIPvarGetLbGlobal(dominatingvar);
1253  ub = SCIPvarGetUbGlobal(dominatingvar);
1254 
1255  if( SCIPvarGetType(dominatingvar) != SCIP_VARTYPE_CONTINUOUS )
1256  newlb = SCIPfloor(scip, newlb);
1257 
1258  if( SCIPisLT(scip, oldlb, newlb) && SCIPisLE(scip, newlb, ub) )
1259  {
1260  SCIPdebugMsg(scip, "[lb]\tlower bound of dominating variable <%s> changed: [%.17f,%.17f] -> [%.17f,%.17f]\n",
1261  SCIPvarGetName(dominatingvar), oldlb, ub, newlb, ub);
1262  SCIP_CALL( SCIPchgVarLb(scip, dominatingvar, newlb) );
1263  (*nchgbds)++;
1264  }
1265  }
1266 
1267  /* assume x dominates y (x->y). we get this bound from a positive coefficient
1268  * of x within a <= relation. from x->y it follows, that y has a positive
1269  * coefficient in this row too. the worst case upper bound of x is an estimation
1270  * of how great x can be in every case. if the objective coefficient of x is
1271  * negative we get thus a lower bound of x. for discrete variables we have
1272  * to round down the lower bound before.
1273  */
1274  if( !SCIPisInfinity(scip, dominatingwcub) && SCIPisNegative(scip, SCIPvarGetObj(dominatingvar)))
1275  {
1276  SCIP_Real newlb;
1277  SCIP_Real oldlb;
1278  SCIP_Real ub;
1279 
1280  newlb = dominatingwcub;
1281  oldlb = SCIPvarGetLbGlobal(dominatingvar);
1282  ub = SCIPvarGetUbGlobal(dominatingvar);
1283 
1284  if( SCIPvarGetType(dominatingvar) != SCIP_VARTYPE_CONTINUOUS )
1285  newlb = SCIPfloor(scip, newlb);
1286 
1287  if( SCIPisLT(scip, oldlb, newlb) && SCIPisLE(scip, newlb, ub) )
1288  {
1289  SCIPdebugMsg(scip, "[wcub]\tlower bound of dominating variable <%s> changed: [%.17f,%.17f] -> [%.17f,%.17f]\n",
1290  SCIPvarGetName(dominatingvar), oldlb, ub, newlb, ub);
1291  SCIP_CALL( SCIPchgVarLb(scip, dominatingvar, newlb) );
1292  (*nchgbds)++;
1293  }
1294  }
1295  }
1296 
1297  if( varstofix[dominatedidx] == NOFIX )
1298  {
1299  /* assume x dominates y (x->y). we get this bound for a positive coefficient of y
1300  * within a <= relation. if x has a negative coefficient we get a common upper
1301  * bound of y. if x has a positive coefficient we get an improved upper bound
1302  * of y because the minactivity is greater.
1303  */
1304  if( !SCIPisInfinity(scip, dominatedub) )
1305  {
1306  SCIP_Real newub;
1307  SCIP_Real oldub;
1308  SCIP_Real lb;
1309 
1310  newub = dominatedub;
1311  oldub = SCIPvarGetUbGlobal(dominatedvar);
1312  lb = SCIPvarGetLbGlobal(dominatedvar);
1313 
1314  if( SCIPisLE(scip, lb, newub) && SCIPisLT(scip, newub, oldub) )
1315  {
1316  SCIPdebugMsg(scip, "[ub]\tupper bound of dominated variable <%s> changed: [%.17f,%.17f] -> [%.17f,%.17f]\n",
1317  SCIPvarGetName(dominatedvar), lb, oldub, lb, newub);
1318  SCIP_CALL( SCIPchgVarUb(scip, dominatedvar, newub) );
1319  (*nchgbds)++;
1320  }
1321  }
1322 
1323  /* assume x dominates y (x->y). we get this bound only from a negative
1324  * coefficient of y within a <= relation. because of x->y then x has a negative
1325  * coefficient too. the worst case lower bound is an estimation what property
1326  * the dominated variable must have if the dominating variable is at its upper bound.
1327  * to get an upper bound of the dominated variable we need to consider a positive
1328  * objective coefficient. for discrete variables we have to round up the upper bound.
1329  */
1330  if( !SCIPisInfinity(scip, -dominatedwclb) && SCIPisPositive(scip, SCIPvarGetObj(dominatedvar)) )
1331  {
1332  SCIP_Real newub;
1333  SCIP_Real oldub;
1334  SCIP_Real lb;
1335 
1336  newub = dominatedwclb;
1337  oldub = SCIPvarGetUbGlobal(dominatedvar);
1338  lb = SCIPvarGetLbGlobal(dominatedvar);
1339 
1340  if( SCIPvarGetType(dominatedvar) != SCIP_VARTYPE_CONTINUOUS )
1341  newub = SCIPceil(scip, newub);
1342 
1343  if( SCIPisLE(scip, lb, newub) && SCIPisLT(scip, newub, oldub) )
1344  {
1345  SCIPdebugMsg(scip, "[wclb]\tupper bound of dominated variable <%s> changed: [%.17f,%.17f] -> [%.17f,%.17f]\n",
1346  SCIPvarGetName(dominatedvar), lb, oldub, lb, newub);
1347  SCIP_CALL( SCIPchgVarUb(scip, dominatedvar, newub) );
1348  (*nchgbds)++;
1349  }
1350  }
1351 
1352  /* assume x dominates y (x->y). we get a lower bound of y from a negative
1353  * coefficient within a <= relation. but if x->y then x has a negative
1354  * coefficient too and contributes with its upper bound to the minactivity.
1355  * thus in all we have a common lower bound calculation and no rounding is necessary.
1356  */
1357  if( !SCIPisInfinity(scip, -dominatedlb) )
1358  {
1359  SCIP_Real newlb;
1360  SCIP_Real oldlb;
1361  SCIP_Real ub;
1362 
1363  newlb = dominatedlb;
1364  oldlb = SCIPvarGetLbGlobal(dominatedvar);
1365  ub = SCIPvarGetUbGlobal(dominatedvar);
1366 
1367  if( SCIPisLT(scip, oldlb, newlb) && SCIPisLE(scip, newlb, ub) )
1368  {
1369  SCIPdebugMsg(scip, "[lb]\tlower bound of dominated variable <%s> changed: [%.17f,%.17f] -> [%.17f,%.17f]\n",
1370  SCIPvarGetName(dominatedvar), oldlb, ub, newlb, ub);
1371  SCIP_CALL( SCIPchgVarLb(scip, dominatedvar, newlb) );
1372  (*nchgbds)++;
1373  }
1374  }
1375  }
1376 
1377  return SCIP_OKAY;
1378 }
1379 
1380 /** try to find variable fixings */
1381 static
1382 SCIP_RETCODE findFixings(
1383  SCIP* scip, /**< SCIP main data structure */
1384  SCIP_MATRIX* matrix, /**< constraint matrix structure */
1385  SCIP_VAR* dominatingvar, /**< dominating variable */
1386  int dominatingidx, /**< column index of the dominating variable */
1387  SCIP_Real dominatingub, /**< predicted upper bound of the dominating variable */
1388  SCIP_Real dominatingwclb, /**< predicted worst case lower bound of the dominating variable */
1389  SCIP_Real dominatinglb, /**< predicted lower bound of the dominating variable */
1390  SCIP_Real dominatingwcub, /**< predicted worst case upper bound of the dominating variable */
1391  SCIP_VAR* dominatedvar, /**< dominated variable */
1392  int dominatedidx, /**< column index of the dominated variable */
1393  FIXINGDIRECTION* varstofix, /**< array holding fixing information */
1394  SCIP_Bool onlybinvars, /**< flag indicating only binary variables are present */
1395  SCIP_Bool onlyoneone, /**< when onlybinvars is TRUE, flag indicates if both binary variables are in clique */
1396  int* nfixings /**< counter for possible fixings */
1397  )
1398 {
1399  /* we compare only variables from the same type */
1400  if( !(SCIPvarGetType(dominatingvar) == SCIPvarGetType(dominatedvar) ||
1401  SCIPvarIsBinary(dominatingvar) == SCIPvarIsBinary(dominatedvar) ||
1402  (SCIPvarGetType(dominatingvar) == SCIP_VARTYPE_INTEGER && SCIPvarGetType(dominatedvar) == SCIP_VARTYPE_IMPLINT) ||
1403  (SCIPvarGetType(dominatedvar) == SCIP_VARTYPE_INTEGER && SCIPvarGetType(dominatingvar) == SCIP_VARTYPE_IMPLINT)) )
1404  {
1405  return SCIP_OKAY;
1406  }
1407 
1408  if( varstofix[dominatedidx] == NOFIX && SCIPmatrixGetColNNonzs(matrix, dominatingidx) == 1
1409  && SCIPmatrixGetColNNonzs(matrix, dominatedidx) == 1 )
1410  {
1411  /* We have a x->y dominance relation and only one equality constraint
1412  * where the dominating variable x with an infinity upper bound and the
1413  * dominated variable y are present. Then the dominated variable y
1414  * can be fixed at its lower bound.
1415  */
1416  int row;
1417  row = *(SCIPmatrixGetColIdxPtr(matrix, dominatedidx));
1418 
1419  if( SCIPisEQ(scip, SCIPmatrixGetRowLhs(matrix, row), SCIPmatrixGetRowRhs(matrix, row)) &&
1420  SCIPisInfinity(scip, SCIPvarGetUbGlobal(dominatingvar)) )
1421  {
1422  varstofix[dominatedidx] = FIXATLB;
1423  (*nfixings)++;
1424 
1425  return SCIP_OKAY;
1426  }
1427  }
1428 
1429  if( varstofix[dominatedidx] == NOFIX && !SCIPisNegative(scip, SCIPvarGetObj(dominatedvar)) )
1430  {
1431  if( !SCIPisInfinity(scip, -dominatingwclb) &&
1432  SCIPisLE(scip, dominatingwclb, SCIPvarGetUbGlobal(dominatingvar)) )
1433  {
1434  /* we have a x->y dominance relation with a positive obj coefficient
1435  * of the dominated variable y. we need to secure feasibility
1436  * by testing if the predicted lower worst case bound is less equal the
1437  * current upper bound. it is possible, that the lower worst case bound
1438  * is infinity and the upper bound of the dominating variable x is
1439  * infinity too.
1440  */
1441  varstofix[dominatedidx] = FIXATLB;
1442  (*nfixings)++;
1443  }
1444  }
1445 
1446  if( varstofix[dominatedidx] == NOFIX && !SCIPisInfinity(scip, dominatingub) &&
1447  SCIPisLE(scip, dominatingub, SCIPvarGetUbGlobal(dominatingvar)) )
1448  {
1449  /* we have a x->y dominance relation with an arbitrary obj coefficient
1450  * of the dominating variable x. in all cases we have to look
1451  * if the predicted upper bound of the dominating variable is great enough.
1452  * by testing, that the predicted upper bound is not infinity we avoid problems
1453  * with x->y e.g.
1454  * min -x -y
1455  * s.t. -x -y <= -1
1456  * 0<=x<=1, 0<=y<=1
1457  * where y is not at their lower bound.
1458  */
1459  varstofix[dominatedidx] = FIXATLB;
1460  (*nfixings)++;
1461  }
1462 
1463  if( varstofix[dominatingidx] == NOFIX && !SCIPisPositive(scip, SCIPvarGetObj(dominatingvar)) )
1464  {
1465  /* we have a x->y dominance relation with a negative obj coefficient
1466  * of the dominating variable x. if the worst case upper bound is
1467  * greater equal than upper bound, we fix x at the upper bound
1468  */
1469  if( !SCIPisInfinity(scip, dominatingwcub) &&
1470  SCIPisGE(scip, dominatingwcub, SCIPvarGetUbGlobal(dominatingvar)) )
1471  {
1472  varstofix[dominatingidx] = FIXATUB;
1473  (*nfixings)++;
1474  }
1475  }
1476 
1477  if( varstofix[dominatingidx] == NOFIX && !SCIPisInfinity(scip, -dominatinglb) &&
1478  SCIPisGE(scip, dominatinglb, SCIPvarGetUbGlobal(dominatingvar)) )
1479  {
1480  /* we have a x->y dominance relation with an arbitrary obj coefficient
1481  * of the dominating variable x. if the predicted lower bound is greater
1482  * equal than upper bound, we fix x at the upper bound.
1483  */
1484  varstofix[dominatingidx] = FIXATUB;
1485  (*nfixings)++;
1486  }
1487 
1488  if( onlybinvars )
1489  {
1490  if( varstofix[dominatedidx] == NOFIX && (onlyoneone || SCIPvarsHaveCommonClique(dominatingvar, TRUE, dominatedvar, TRUE, TRUE)) )
1491  {
1492  /* We have a (1->1)-clique with dominance relation (x->y) (x dominates y).
1493  * From this dominance relation, we know (1->0) is possible and not worse than (0->1)
1494  * concerning the objective function. It follows that only (1->0) or (0->0) are possible,
1495  * but in both cases y has the value 0 => y=0.
1496  */
1497  varstofix[dominatedidx] = FIXATLB;
1498  (*nfixings)++;
1499  }
1500 
1501  if( varstofix[dominatingidx] == NOFIX && SCIPvarsHaveCommonClique(dominatingvar, FALSE, dominatedvar, FALSE, TRUE) )
1502  {
1503  /* We have a (0->0)-clique with dominance relation x->y (x dominates y).
1504  * From this dominance relation, we know (1->0) is possible and not worse than (0->1)
1505  * concerning the objective function. It follows that only (1->0) or (1->1) are possible,
1506  * but in both cases x has the value 1 => x=1
1507  */
1508  varstofix[dominatingidx] = FIXATUB;
1509  (*nfixings)++;
1510  }
1511  }
1512  else
1513  assert(!onlyoneone);
1514 
1515  return SCIP_OKAY;
1516 }
1517 
1518 /** find dominance relation between variable pairs */
1519 static
1520 SCIP_RETCODE findDominancePairs(
1521  SCIP* scip, /**< SCIP main data structure */
1522  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
1523  SCIP_PRESOLDATA* presoldata, /**< presolver data */
1524  int* searchcols, /**< indexes of variables for pair comparisons */
1525  int searchsize, /**< number of variables for pair comparisons */
1526  SCIP_Bool onlybinvars, /**< flag indicating searchcols contains only binary variable indexes */
1527  FIXINGDIRECTION* varstofix, /**< array holding information for later upper/lower bound fixing */
1528  int* nfixings, /**< found number of possible fixings */
1529  SCIP_Longint* ndomrelations, /**< found number of dominance relations */
1530  int* nchgbds /**< number of changed bounds */
1531  )
1532 {
1533  SCIP_Real* vals1;
1534  SCIP_Real* vals2;
1535  SCIP_Real tmpupperbounddominatingcol1;
1536  SCIP_Real tmpupperbounddominatingcol2;
1537  SCIP_Real tmpwclowerbounddominatingcol1;
1538  SCIP_Real tmpwclowerbounddominatingcol2;
1539  SCIP_Real tmplowerbounddominatingcol1;
1540  SCIP_Real tmplowerbounddominatingcol2;
1541  SCIP_Real tmpwcupperbounddominatingcol1;
1542  SCIP_Real tmpwcupperbounddominatingcol2;
1543  int* rows1;
1544  int* rows2;
1545  int nrows1;
1546  int nrows2;
1547  SCIP_Real tmpupperbounddominatedcol1;
1548  SCIP_Real tmpupperbounddominatedcol2;
1549  SCIP_Real tmpwclowerbounddominatedcol1;
1550  SCIP_Real tmpwclowerbounddominatedcol2;
1551  SCIP_Real tmplowerbounddominatedcol1;
1552  SCIP_Real tmplowerbounddominatedcol2;
1553  SCIP_Real tmpwcupperbounddominatedcol1;
1554  SCIP_Real tmpwcupperbounddominatedcol2;
1555  SCIP_Real obj1;
1556  SCIP_Bool col1domcol2;
1557  SCIP_Bool col2domcol1;
1558  SCIP_Bool onlyoneone;
1559  int cnt1;
1560  int cnt2;
1561  int col1;
1562  int col2;
1563  int r1;
1564  int r2;
1565  int paircnt;
1566  int oldnfixings;
1567 
1568  assert(scip != NULL);
1569  assert(matrix != NULL);
1570  assert(presoldata != NULL);
1571  assert(searchcols != NULL);
1572  assert(varstofix != NULL);
1573  assert(nfixings != NULL);
1574  assert(ndomrelations != NULL);
1575  assert(nchgbds != NULL);
1576 
1577  paircnt = 0;
1578  oldnfixings = *nfixings;
1579 
1580  /* pair comparisons */
1581  for( cnt1 = 0; cnt1 < searchsize; cnt1++ )
1582  {
1583  SCIP_VAR* varcol1;
1584  SCIP_VAR* varcol2;
1585 
1586  /* get index of the first variable */
1587  col1 = searchcols[cnt1];
1588 
1589  if( varstofix[col1] == FIXATLB )
1590  continue;
1591 
1592  varcol1 = SCIPmatrixGetVar(matrix, col1);
1593  obj1 = SCIPvarGetObj(varcol1);
1594 
1595  for( cnt2 = cnt1+1; cnt2 < searchsize; cnt2++ )
1596  {
1597  /* get index of the second variable */
1598  col2 = searchcols[cnt2];
1599  varcol2 = SCIPmatrixGetVar(matrix, col2);
1600  onlyoneone = FALSE;
1601 
1602  /* we always have minimize as obj sense */
1603 
1604  /* column 1 dominating column 2 */
1605  col1domcol2 = (obj1 <= SCIPvarGetObj(varcol2));
1606 
1607  /* column 2 dominating column 1 */
1608  col2domcol1 = (SCIPvarGetObj(varcol2) <= obj1);
1609 
1610  /* search only if nothing was found yet */
1611  col1domcol2 = col1domcol2 && (varstofix[col2] == NOFIX);
1612  col2domcol1 = col2domcol1 && (varstofix[col1] == NOFIX);
1613 
1614  /* we only search for a dominance relation if the lower bounds are not negative */
1615  if( !onlybinvars )
1616  {
1617  if( SCIPisLT(scip, SCIPvarGetLbGlobal(varcol1), 0.0) ||
1618  SCIPisLT(scip, SCIPvarGetLbGlobal(varcol2), 0.0) )
1619  {
1620  col1domcol2 = FALSE;
1621  col2domcol1 = FALSE;
1622  }
1623  }
1624 
1625  /* pair comparison control */
1626  if( paircnt == presoldata->numcurrentpairs )
1627  {
1628  assert(*nfixings >= oldnfixings);
1629  if( *nfixings == oldnfixings )
1630  {
1631  /* not enough fixings found, decrement number of comparisons */
1632  presoldata->numcurrentpairs >>= 1; /*lint !e702*/
1633  if( presoldata->numcurrentpairs < presoldata->numminpairs )
1634  presoldata->numcurrentpairs = presoldata->numminpairs;
1635 
1636  /* stop searching in this row */
1637  return SCIP_OKAY;
1638  }
1639  oldnfixings = *nfixings;
1640  paircnt = 0;
1641 
1642  /* increment number of comparisons */
1643  presoldata->numcurrentpairs <<= 1; /*lint !e701*/
1644  if( presoldata->numcurrentpairs > presoldata->nummaxpairs )
1645  presoldata->numcurrentpairs = presoldata->nummaxpairs;
1646  }
1647  paircnt++;
1648 
1649  if( !col1domcol2 && !col2domcol1 )
1650  continue;
1651 
1652  /* get the data for both columns */
1653  vals1 = SCIPmatrixGetColValPtr(matrix, col1);
1654  rows1 = SCIPmatrixGetColIdxPtr(matrix, col1);
1655  nrows1 = SCIPmatrixGetColNNonzs(matrix, col1);
1656  r1 = 0;
1657  vals2 = SCIPmatrixGetColValPtr(matrix, col2);
1658  rows2 = SCIPmatrixGetColIdxPtr(matrix, col2);
1659  nrows2 = SCIPmatrixGetColNNonzs(matrix, col2);
1660  r2 = 0;
1661 
1662  /* do we have a obj constant? */
1663  if( nrows1 == 0 || nrows2 == 0 )
1664  continue;
1665 
1666  /* initialize temporary bounds of dominating variable */
1667  tmpupperbounddominatingcol1 = SCIPinfinity(scip);
1668  tmpupperbounddominatingcol2 = tmpupperbounddominatingcol1;
1669  tmpwclowerbounddominatingcol1 = -SCIPinfinity(scip);
1670  tmpwclowerbounddominatingcol2 = tmpwclowerbounddominatingcol1;
1671  tmplowerbounddominatingcol1 = -SCIPinfinity(scip);
1672  tmplowerbounddominatingcol2 = tmplowerbounddominatingcol1;
1673  tmpwcupperbounddominatingcol1 = SCIPinfinity(scip);
1674  tmpwcupperbounddominatingcol2 = tmpwcupperbounddominatingcol1;
1675 
1676  /* initialize temporary bounds of dominated variable */
1677  tmpupperbounddominatedcol1 = SCIPinfinity(scip);
1678  tmpupperbounddominatedcol2 = tmpupperbounddominatedcol1;
1679  tmpwclowerbounddominatedcol1 = -SCIPinfinity(scip);
1680  tmpwclowerbounddominatedcol2 = tmpwclowerbounddominatedcol1;
1681  tmplowerbounddominatedcol1 = -SCIPinfinity(scip);
1682  tmplowerbounddominatedcol2 = tmplowerbounddominatedcol1;
1683  tmpwcupperbounddominatedcol1 = SCIPinfinity(scip);
1684  tmpwcupperbounddominatedcol2 = tmpwcupperbounddominatedcol1;
1685 
1686  /* compare rows of this column pair */
1687  while( (col1domcol2 || col2domcol1) && (r1 < nrows1 || r2 < nrows2) )
1688  {
1689  assert((r1 >= nrows1-1) || (rows1[r1] < rows1[r1+1]));
1690  assert((r2 >= nrows2-1) || (rows2[r2] < rows2[r2+1]));
1691 
1692  /* there is a nonredundant row containing column 1 but not column 2 */
1693  if( r1 < nrows1 && (r2 == nrows2 || rows1[r1] < rows2[r2]) )
1694  {
1695  /* dominance depends on the type of relation */
1696  if( !SCIPmatrixIsRowRhsInfinity(matrix, rows1[r1]) )
1697  {
1698  /* no dominance relation for equations or ranged rows */
1699  col2domcol1 = FALSE;
1700  col1domcol2 = FALSE;
1701  }
1702  else
1703  {
1704  /* >= relation, larger coefficients dominate smaller ones */
1705  if( vals1[r1] > 0.0 )
1706  col2domcol1 = FALSE;
1707  else
1708  col1domcol2 = FALSE;
1709  }
1710 
1711  r1++;
1712  }
1713  /* there is a nonredundant row containing column 2, but not column 1 */
1714  else if( r2 < nrows2 && (r1 == nrows1 || rows1[r1] > rows2[r2]) )
1715  {
1716  /* dominance depends on the type of relation */
1717  if( !SCIPmatrixIsRowRhsInfinity(matrix, rows2[r2]) )
1718  {
1719  /* no dominance relation for equations or ranged rows */
1720  col2domcol1 = FALSE;
1721  col1domcol2 = FALSE;
1722  }
1723  else
1724  {
1725  /* >= relation, larger coefficients dominate smaller ones */
1726  if( vals2[r2] < 0.0 )
1727  col2domcol1 = FALSE;
1728  else
1729  col1domcol2 = FALSE;
1730  }
1731 
1732  r2++;
1733  }
1734  /* if both columns appear in a common row, compare the coefficients */
1735  else
1736  {
1737  assert(r1 < nrows1 && r2 < nrows2);
1738  assert(rows1[r1] == rows2[r2]);
1739 
1740  /* if both columns are binary variables we check if they have a common clique
1741  * and do not calculate any bounds
1742  */
1743  if( onlybinvars && !onlyoneone )
1744  {
1745  if( vals1[r1] < 0 && vals2[r2] < 0 )
1746  {
1747  if( (SCIPmatrixGetRowNMaxActPosInf(matrix, rows1[r1]) + SCIPmatrixGetRowNMaxActNegInf(matrix, rows1[r1]) == 0)
1748  && SCIPisFeasLE(scip, SCIPmatrixGetRowMaxActivity(matrix, rows1[r1]) + MAX(vals1[r1], vals2[r2]),
1749  SCIPmatrixGetRowLhs(matrix, rows1[r1])) )
1750  {
1751  onlyoneone = TRUE;
1752  }
1753  }
1754 
1755  if( !onlyoneone && !SCIPmatrixIsRowRhsInfinity(matrix, rows1[r1]) )
1756  {
1757  if ( vals1[r1] > 0 && vals2[r2] > 0 )
1758  {
1759  if( (SCIPmatrixGetRowNMinActPosInf(matrix, rows1[r1]) + SCIPmatrixGetRowNMinActNegInf(matrix, rows1[r1]) == 0)
1760  && SCIPisFeasGE(scip, SCIPmatrixGetRowMinActivity(matrix, rows1[r1]) + MIN(vals1[r1], vals2[r2]),
1761  SCIPmatrixGetRowRhs(matrix, rows1[r1])) )
1762  {
1763  onlyoneone = TRUE;
1764  }
1765  }
1766  }
1767 
1768  if( onlyoneone )
1769  {
1770  /* reset bounds */
1771  tmpupperbounddominatingcol1 = SCIPinfinity(scip);
1772  tmpupperbounddominatingcol2 = tmpupperbounddominatingcol1;
1773  tmpwclowerbounddominatingcol1 = -SCIPinfinity(scip);
1774  tmpwclowerbounddominatingcol2 = tmpwclowerbounddominatingcol1;
1775  tmplowerbounddominatingcol1 = -SCIPinfinity(scip);
1776  tmplowerbounddominatingcol2 = tmplowerbounddominatingcol1;
1777  tmpwcupperbounddominatingcol1 = SCIPinfinity(scip);
1778  tmpwcupperbounddominatingcol2 = tmpwcupperbounddominatingcol1;
1779 
1780  tmpupperbounddominatedcol1 = SCIPinfinity(scip);
1781  tmpupperbounddominatedcol2 = tmpupperbounddominatedcol1;
1782  tmpwclowerbounddominatedcol1 = -SCIPinfinity(scip);
1783  tmpwclowerbounddominatedcol2 = tmpwclowerbounddominatedcol1;
1784  tmplowerbounddominatedcol1 = -SCIPinfinity(scip);
1785  tmplowerbounddominatedcol2 = tmplowerbounddominatedcol1;
1786  tmpwcupperbounddominatedcol1 = SCIPinfinity(scip);
1787  tmpwcupperbounddominatedcol2 = tmpwcupperbounddominatedcol1;
1788  }
1789  }
1790 
1791  /* dominance depends on the type of inequality */
1792  if( !SCIPmatrixIsRowRhsInfinity(matrix, rows1[r1]) )
1793  {
1794  /* no dominance relation if coefficients differ for equations or ranged rows */
1795  if( !SCIPisEQ(scip, vals1[r1], vals2[r2]) )
1796  {
1797  col2domcol1 = FALSE;
1798  col1domcol2 = FALSE;
1799  }
1800  }
1801  else
1802  {
1803  /* >= relation, larger coefficients dominate smaller ones */
1804  if( vals1[r1] > vals2[r2] )
1805  col2domcol1 = FALSE;
1806  else if( vals1[r1] < vals2[r2] )
1807  col1domcol2 = FALSE;
1808  }
1809 
1810  /* we do not use bound calulations if two binary variable are in one common clique.
1811  * for the other cases we claim the same sign for the coefficients to
1812  * achieve monotonically decreasing predictive bound functions.
1813  */
1814  if( !onlyoneone &&
1815  ((vals1[r1] < 0 && vals2[r2] < 0) || (vals1[r1] > 0 && vals2[r2] > 0)) )
1816  {
1817  if( col1domcol2 )
1818  {
1819  /* update bounds of dominating variable for column 1 */
1820  SCIP_CALL( updateBounds(scip, matrix, rows1[r1],
1821  col1, vals1[r1], col2, vals2[r2], TRUE,
1822  &tmpupperbounddominatingcol1, &tmpwclowerbounddominatingcol1,
1823  &tmplowerbounddominatingcol1, &tmpwcupperbounddominatingcol1) );
1824 
1825  /* update bounds of dominated variable for column 1 */
1826  SCIP_CALL( updateBounds(scip, matrix, rows1[r1],
1827  col1, vals1[r1], col2, vals2[r2], FALSE,
1828  &tmpupperbounddominatedcol1, &tmpwclowerbounddominatedcol1,
1829  &tmplowerbounddominatedcol1, &tmpwcupperbounddominatedcol1) );
1830  }
1831 
1832  if( col2domcol1 )
1833  {
1834  /* update bounds of dominating variable for column 2 */
1835  SCIP_CALL( updateBounds(scip, matrix, rows2[r2],
1836  col2, vals2[r2], col1, vals1[r1], TRUE,
1837  &tmpupperbounddominatingcol2, &tmpwclowerbounddominatingcol2,
1838  &tmplowerbounddominatingcol2, &tmpwcupperbounddominatingcol2) );
1839 
1840  /* update bounds of dominated variable for column 2 */
1841  SCIP_CALL( updateBounds(scip, matrix, rows2[r2],
1842  col2, vals2[r2], col1, vals1[r1], FALSE,
1843  &tmpupperbounddominatedcol2, &tmpwclowerbounddominatedcol2,
1844  &tmplowerbounddominatedcol2, &tmpwcupperbounddominatedcol2) );
1845  }
1846  }
1847 
1848  r1++;
1849  r2++;
1850  }
1851  }
1852 
1853  /* a column is only dominated, if there are no more rows in which it is contained */
1854  col1domcol2 = col1domcol2 && r2 == nrows2;
1855  col2domcol1 = col2domcol1 && r1 == nrows1;
1856 
1857  if( !col1domcol2 && !col2domcol1 )
1858  continue;
1859 
1860  /* no dominance relation for left equations or ranged rows */
1861  while( r1 < nrows1 )
1862  {
1863  if( !SCIPmatrixIsRowRhsInfinity(matrix, rows1[r1]) )
1864  {
1865  col2domcol1 = FALSE;
1866  col1domcol2 = FALSE;
1867  break;
1868  }
1869  r1++;
1870  }
1871  if( !col1domcol2 && !col2domcol1 )
1872  continue;
1873  while( r2 < nrows2 )
1874  {
1875  if( !SCIPmatrixIsRowRhsInfinity(matrix, rows2[r2]) )
1876  {
1877  col2domcol1 = FALSE;
1878  col1domcol2 = FALSE;
1879  break;
1880  }
1881  r2++;
1882  }
1883 
1884  if( col1domcol2 || col2domcol1 )
1885  (*ndomrelations)++;
1886 
1887  if( col1domcol2 && col2domcol1 )
1888  {
1889  /* prefer the variable as dominating variable with the greater upper bound */
1890  if( SCIPisGE(scip, SCIPvarGetUbGlobal(varcol1), SCIPvarGetUbGlobal(varcol2)) )
1891  col2domcol1 = FALSE;
1892  else
1893  col1domcol2 = FALSE;
1894  }
1895 
1896  /* use dominance relation and clique/bound-information
1897  * to find variable fixings. additionally try to strengthen
1898  * variable bounds by predictive bound strengthening.
1899  */
1900  if( col1domcol2 )
1901  {
1902  SCIP_CALL( findFixings(scip, matrix, varcol1, col1,
1903  tmpupperbounddominatingcol1, tmpwclowerbounddominatingcol1,
1904  tmplowerbounddominatingcol1, tmpwcupperbounddominatingcol1,
1905  varcol2, col2,
1906  varstofix, onlybinvars, onlyoneone, nfixings) );
1907 
1908  if( presoldata->predbndstr )
1909  {
1910  SCIP_CALL( predBndStr(scip, varcol1, col1,
1911  tmpupperbounddominatingcol1,
1912  tmplowerbounddominatingcol1, tmpwcupperbounddominatingcol1,
1913  varcol2, col2,
1914  tmpupperbounddominatedcol1, tmpwclowerbounddominatedcol1,
1915  tmplowerbounddominatedcol1,
1916  varstofix, nchgbds) );
1917  }
1918  }
1919  else if( col2domcol1 )
1920  {
1921  SCIP_CALL( findFixings(scip, matrix, varcol2, col2,
1922  tmpupperbounddominatingcol2, tmpwclowerbounddominatingcol2,
1923  tmplowerbounddominatingcol2, tmpwcupperbounddominatingcol2,
1924  varcol1, col1,
1925  varstofix, onlybinvars, onlyoneone, nfixings) );
1926 
1927  if( presoldata->predbndstr )
1928  {
1929  SCIP_CALL( predBndStr(scip, varcol2, col2,
1930  tmpupperbounddominatingcol2,
1931  tmplowerbounddominatingcol2, tmpwcupperbounddominatingcol2,
1932  varcol1, col1,
1933  tmpupperbounddominatedcol2, tmpwclowerbounddominatedcol2,
1934  tmplowerbounddominatedcol2,
1935  varstofix, nchgbds) );
1936  }
1937  }
1938  if( varstofix[col1] == FIXATLB )
1939  break;
1940  }
1941  }
1942 
1943  return SCIP_OKAY;
1944 }
1945 
1946 
1947 /*
1948  * Callback methods of presolver
1949  */
1950 
1951 
1952 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
1953 static
1954 SCIP_DECL_PRESOLCOPY(presolCopyDomcol)
1955 { /*lint --e{715}*/
1956  assert(scip != NULL);
1957  assert(presol != NULL);
1958  assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
1959 
1960  /* call inclusion method of presolver */
1961  SCIP_CALL( SCIPincludePresolDomcol(scip) );
1962 
1963  return SCIP_OKAY;
1964 }
1965 
1966 /** destructor of presolver to free user data (called when SCIP is exiting) */
1967 static
1968 SCIP_DECL_PRESOLFREE(presolFreeDomcol)
1969 { /*lint --e{715}*/
1970  SCIP_PRESOLDATA* presoldata;
1971 
1972  /* free presolver data */
1973  presoldata = SCIPpresolGetData(presol);
1974  assert(presoldata != NULL);
1975 
1976  SCIPfreeBlockMemory(scip, &presoldata);
1977  SCIPpresolSetData(presol, NULL);
1978 
1979  return SCIP_OKAY;
1980 }
1981 
1982 /** execution method of presolver */
1983 static
1984 SCIP_DECL_PRESOLEXEC(presolExecDomcol)
1985 { /*lint --e{715}*/
1986  SCIP_PRESOLDATA* presoldata;
1987  SCIP_MATRIX* matrix;
1988  SCIP_Bool initialized;
1989  SCIP_Bool complete;
1990 
1991  assert(result != NULL);
1992  *result = SCIP_DIDNOTRUN;
1993 
1994  if( (SCIPgetStage(scip) != SCIP_STAGE_PRESOLVING) || SCIPinProbing(scip) || SCIPisNLPEnabled(scip) )
1995  return SCIP_OKAY;
1996 
1997  if( SCIPisStopped(scip) || SCIPgetNActivePricers(scip) > 0 )
1998  return SCIP_OKAY;
1999 
2000  if( !SCIPallowDualReds(scip) )
2001  return SCIP_OKAY;
2002 
2003  presoldata = SCIPpresolGetData(presol);
2004  assert(presoldata != NULL);
2005 
2006  /* don't run for pure LPs */
2007  if( !presoldata->continuousred && (SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip) == 0) )
2008  return SCIP_OKAY;
2009 
2010  *result = SCIP_DIDNOTFIND;
2011 
2012  matrix = NULL;
2013  SCIP_CALL( SCIPmatrixCreate(scip, &matrix, &initialized, &complete) );
2014 
2015  if( initialized && complete )
2016  {
2017  int nfixings;
2018  SCIP_Longint ndomrelations;
2019  int v;
2020  int r;
2021  FIXINGDIRECTION* varstofix;
2022  SCIP_Bool* varsprocessed;
2023  int nrows;
2024  int ncols;
2025  int* rowidxsorted;
2026  int* rowsparsity;
2027  int varcount;
2028  int* consearchcols;
2029  int* intsearchcols;
2030  int* binsearchcols;
2031  int nconfill;
2032  int nintfill;
2033  int nbinfill;
2034 #ifdef SCIP_DEBUG
2035  int nconvarsfixed = 0;
2036  int nintvarsfixed = 0;
2037  int nbinvarsfixed = 0;
2038 #endif
2039  int* pclass;
2040  int* colidx;
2041  int pclassstart;
2042  int pc;
2043  SCIP_Bool* varineq;
2044 
2045  nfixings = 0;
2046  ndomrelations = 0;
2047  nrows = SCIPmatrixGetNRows(matrix);
2048  ncols = SCIPmatrixGetNColumns(matrix);
2049  assert(SCIPgetNVars(scip) == ncols);
2050 
2051  SCIP_CALL( SCIPallocBufferArray(scip, &varstofix, ncols) );
2052  BMSclearMemoryArray(varstofix, ncols);
2053 
2054  SCIP_CALL( SCIPallocBufferArray(scip, &varsprocessed, ncols) );
2055  BMSclearMemoryArray(varsprocessed, ncols);
2056 
2057  SCIP_CALL( SCIPallocBufferArray(scip, &consearchcols, ncols) );
2058  SCIP_CALL( SCIPallocBufferArray(scip, &intsearchcols, ncols) );
2059  SCIP_CALL( SCIPallocBufferArray(scip, &binsearchcols, ncols) );
2060 
2061  SCIP_CALL( SCIPallocBufferArray(scip, &rowidxsorted, nrows) );
2062  SCIP_CALL( SCIPallocBufferArray(scip, &rowsparsity, nrows) );
2063  for( r = 0; r < nrows; ++r )
2064  {
2065  rowidxsorted[r] = r;
2066  rowsparsity[r] = SCIPmatrixGetRowNNonzs(matrix, r);
2067  }
2068 
2069  SCIP_CALL( SCIPallocBufferArray(scip, &pclass, ncols) );
2070  SCIP_CALL( SCIPallocBufferArray(scip, &colidx, ncols) );
2071  SCIP_CALL( SCIPallocBufferArray(scip, &varineq, ncols) );
2072  for( v = 0; v < ncols; v++ )
2073  {
2074  colidx[v] = v;
2075  varineq[v] = FALSE;
2076  }
2077 
2078  /* init pair comparision control */
2079  presoldata->numcurrentpairs = presoldata->nummaxpairs;
2080 
2081  varcount = 0;
2082 
2083  /* 1.stage: search dominance relations of parallel columns
2084  * within equalities and ranged rows
2085  */
2086  if( (presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 )
2087  {
2088  SCIP_CALL( detectParallelCols(scip, matrix, pclass, varineq) );
2089  SCIPsortIntInt(pclass, colidx, ncols);
2090 
2091  pc = 0;
2092  while( pc < ncols )
2093  {
2094  int varidx;
2095 
2096  varidx = 0;
2097  nconfill = 0;
2098  nintfill = 0;
2099  nbinfill = 0;
2100 
2101  pclassstart = pclass[pc];
2102  while( pc < ncols && pclassstart == pclass[pc] )
2103  {
2104  SCIP_VAR* var;
2105 
2106  varidx = colidx[pc];
2107  var = SCIPmatrixGetVar(matrix, varidx);
2108 
2109  /* we only regard variables which were not processed yet and
2110  * are present within equalities or ranged rows
2111  */
2112  if( !varsprocessed[varidx] && varineq[varidx] )
2113  {
2114  /* we search only for dominance relations between the same variable type */
2115  if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS )
2116  {
2117  consearchcols[nconfill++] = varidx;
2118  }
2119  else if( SCIPvarIsBinary(var) )
2120  {
2121  binsearchcols[nbinfill++] = varidx;
2122  }
2123  else
2124  {
2125  assert(SCIPvarGetType(var) == SCIP_VARTYPE_INTEGER || SCIPvarGetType(var) == SCIP_VARTYPE_IMPLINT);
2126  intsearchcols[nintfill++] = varidx;
2127  }
2128  }
2129  ++pc;
2130  }
2131 
2132  /* continuous variables */
2133  if( nconfill > 1 && presoldata->continuousred )
2134  {
2135  SCIP_CALL( findDominancePairs(scip, matrix, presoldata, consearchcols, nconfill, FALSE,
2136  varstofix, &nfixings, &ndomrelations, nchgbds) );
2137 
2138  for( v = 0; v < nconfill; ++v )
2139  varsprocessed[consearchcols[v]] = TRUE;
2140 
2141  varcount += nconfill;
2142  }
2143  else if( nconfill == 1 )
2144  {
2145  if( varineq[varidx] )
2146  varsprocessed[consearchcols[0]] = TRUE;
2147  }
2148 
2149  /* integer and impl-integer variables */
2150  if( nintfill > 1 )
2151  {
2152  SCIP_CALL( findDominancePairs(scip, matrix, presoldata, intsearchcols, nintfill, FALSE,
2153  varstofix, &nfixings, &ndomrelations, nchgbds) );
2154 
2155  for( v = 0; v < nintfill; ++v )
2156  varsprocessed[intsearchcols[v]] = TRUE;
2157 
2158  varcount += nintfill;
2159  }
2160  else if( nintfill == 1 )
2161  {
2162  if( varineq[varidx] )
2163  varsprocessed[intsearchcols[0]] = TRUE;
2164  }
2165 
2166  /* binary variables */
2167  if( nbinfill > 1 )
2168  {
2169  SCIP_CALL( findDominancePairs(scip, matrix, presoldata, binsearchcols, nbinfill, TRUE,
2170  varstofix, &nfixings, &ndomrelations, nchgbds) );
2171 
2172  for( v = 0; v < nbinfill; ++v )
2173  varsprocessed[binsearchcols[v]] = TRUE;
2174 
2175  varcount += nbinfill;
2176  }
2177  else if( nbinfill == 1 )
2178  {
2179  if( varineq[varidx] )
2180  varsprocessed[binsearchcols[0]] = TRUE;
2181  }
2182 
2183  if( varcount >= ncols )
2184  break;
2185  }
2186  }
2187 
2188  /* 2.stage: search dominance relations for the remaining columns
2189  * by increasing row-sparsity
2190  */
2191  if( (presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 )
2192  {
2193  SCIPsortIntInt(rowsparsity, rowidxsorted, nrows);
2194 
2195  for( r = 0; r < nrows; ++r )
2196  {
2197  int rowidx;
2198  int* rowpnt;
2199  int* rowend;
2200 
2201  /* break if the time limit was reached; since the check is expensive,
2202  * we only check all 1000 constraints
2203  */
2204  if( (r % 1000 == 0) && SCIPisStopped(scip) )
2205  break;
2206 
2207  rowidx = rowidxsorted[r];
2208  rowpnt = SCIPmatrixGetRowIdxPtr(matrix, rowidx);
2209  rowend = rowpnt + SCIPmatrixGetRowNNonzs(matrix, rowidx);
2210 
2211  if( SCIPmatrixGetRowNNonzs(matrix, rowidx) == 1 )
2212  continue;
2213 
2214  nconfill = 0;
2215  nintfill = 0;
2216  nbinfill = 0;
2217 
2218  for( ; rowpnt < rowend; rowpnt++ )
2219  {
2220  if( !(varsprocessed[*rowpnt]) )
2221  {
2222  int varidx;
2223  SCIP_VAR* var;
2224 
2225  varidx = *rowpnt;
2226  var = SCIPmatrixGetVar(matrix, varidx);
2227 
2228  /* we search only for dominance relations between the same variable type */
2229  if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS )
2230  {
2231  consearchcols[nconfill++] = varidx;
2232  }
2233  else if( SCIPvarIsBinary(var) )
2234  {
2235  binsearchcols[nbinfill++] = varidx;
2236  }
2237  else
2238  {
2239  assert(SCIPvarGetType(var) == SCIP_VARTYPE_INTEGER || SCIPvarGetType(var) == SCIP_VARTYPE_IMPLINT);
2240  intsearchcols[nintfill++] = varidx;
2241  }
2242  }
2243  }
2244 
2245  /* continuous variables */
2246  if( nconfill > 1 && presoldata->continuousred )
2247  {
2248  SCIP_CALL( findDominancePairs(scip, matrix, presoldata, consearchcols, nconfill, FALSE,
2249  varstofix, &nfixings, &ndomrelations, nchgbds) );
2250 
2251  for( v = 0; v < nconfill; ++v )
2252  varsprocessed[consearchcols[v]] = TRUE;
2253 
2254  varcount += nconfill;
2255  }
2256 
2257  /* integer and impl-integer variables */
2258  if( nintfill > 1 )
2259  {
2260  SCIP_CALL( findDominancePairs(scip, matrix, presoldata, intsearchcols, nintfill, FALSE,
2261  varstofix, &nfixings, &ndomrelations, nchgbds) );
2262 
2263  for( v = 0; v < nintfill; ++v )
2264  varsprocessed[intsearchcols[v]] = TRUE;
2265 
2266  varcount += nintfill;
2267  }
2268 
2269  /* binary variables */
2270  if( nbinfill > 1 )
2271  {
2272  SCIP_CALL( findDominancePairs(scip, matrix, presoldata, binsearchcols, nbinfill, TRUE,
2273  varstofix, &nfixings, &ndomrelations, nchgbds) );
2274 
2275  for( v = 0; v < nbinfill; ++v )
2276  varsprocessed[binsearchcols[v]] = TRUE;
2277 
2278  varcount += nbinfill;
2279  }
2280 
2281  if( varcount >= ncols )
2282  break;
2283  }
2284  }
2285 
2286  if( nfixings > 0 )
2287  {
2288  int oldnfixedvars;
2289 
2290  oldnfixedvars = *nfixedvars;
2291 
2292  for( v = ncols - 1; v >= 0; --v )
2293  {
2294  SCIP_Bool infeasible;
2295  SCIP_Bool fixed;
2296  SCIP_VAR* var;
2297 
2298  var = SCIPmatrixGetVar(matrix,v);
2299 
2300  if( SCIPvarGetNLocksUp(var) != SCIPmatrixGetColNUplocks(matrix, v) ||
2301  SCIPvarGetNLocksDown(var) != SCIPmatrixGetColNDownlocks(matrix, v) )
2302  {
2303  /* no fixing, locks not consistent */
2304  continue;
2305  }
2306 
2307  if( varstofix[v] == FIXATLB )
2308  {
2309  SCIP_Real lb;
2310 
2311  lb = SCIPvarGetLbGlobal(var);
2312  assert(SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS || SCIPisFeasIntegral(scip, lb));
2313 
2314  /* fix at lower bound */
2315  SCIP_CALL( SCIPfixVar(scip, var, lb, &infeasible, &fixed) );
2316  if( infeasible )
2317  {
2318  SCIPdebugMsg(scip, " -> infeasible fixing\n");
2319  *result = SCIP_CUTOFF;
2320 
2321  break;
2322  }
2323  assert(fixed);
2324  (*nfixedvars)++;
2325 
2326 #ifdef SCIP_DEBUG
2327  if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS )
2328  nconvarsfixed++;
2329  else if( SCIPvarIsBinary(var) )
2330  nbinvarsfixed++;
2331  else
2332  nintvarsfixed++;
2333 #endif
2334  }
2335  else if( varstofix[v] == FIXATUB )
2336  {
2337  SCIP_Real ub;
2338 
2339  ub = SCIPvarGetUbGlobal(var);
2340  assert(SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS || SCIPisFeasIntegral(scip, ub));
2341 
2342  /* fix at upper bound */
2343  SCIP_CALL( SCIPfixVar(scip, var, ub, &infeasible, &fixed) );
2344  if( infeasible )
2345  {
2346  SCIPdebugMsg(scip, " -> infeasible fixing\n");
2347  *result = SCIP_CUTOFF;
2348 
2349  break;
2350  }
2351  assert(fixed);
2352  (*nfixedvars)++;
2353 
2354 #ifdef SCIP_DEBUG
2355  if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS )
2356  nconvarsfixed++;
2357  else if( SCIPvarIsBinary(var) )
2358  nbinvarsfixed++;
2359  else
2360  nintvarsfixed++;
2361 #endif
2362  }
2363  }
2364 
2365  if( *result != SCIP_CUTOFF && *nfixedvars > oldnfixedvars )
2366  *result = SCIP_SUCCESS;
2367  }
2368 
2369  SCIPfreeBufferArray(scip, &varineq);
2370  SCIPfreeBufferArray(scip, &colidx);
2371  SCIPfreeBufferArray(scip, &pclass);
2372  SCIPfreeBufferArray(scip, &rowsparsity);
2373  SCIPfreeBufferArray(scip, &rowidxsorted);
2374  SCIPfreeBufferArray(scip, &binsearchcols);
2375  SCIPfreeBufferArray(scip, &intsearchcols);
2376  SCIPfreeBufferArray(scip, &consearchcols);
2377  SCIPfreeBufferArray(scip, &varsprocessed);
2378  SCIPfreeBufferArray(scip, &varstofix);
2379 
2380 #ifdef SCIP_DEBUG
2381  if( (nconvarsfixed + nintvarsfixed + nbinvarsfixed) > 0 )
2382  {
2383  SCIPdebugMsg(scip, "### %d vars [%" SCIP_LONGINT_FORMAT " dom] => fixed [cont: %d, int: %d, bin: %d], %scutoff detected\n",
2384  ncols, ndomrelations, nconvarsfixed, nintvarsfixed, nbinvarsfixed, (*result != SCIP_CUTOFF) ? "no " : "");
2385  }
2386 #endif
2387  }
2388 
2389  SCIPmatrixFree(scip, &matrix);
2390 
2391  return SCIP_OKAY;
2392 }
2393 
2394 /*
2395  * presolver specific interface methods
2396  */
2397 
2398 /** creates the domcol presolver and includes it in SCIP */
2399 SCIP_RETCODE SCIPincludePresolDomcol(
2400  SCIP* scip /**< SCIP data structure */
2401  )
2402 {
2403  SCIP_PRESOLDATA* presoldata;
2404  SCIP_PRESOL* presol;
2405 
2406  /* create domcol presolver data */
2407  SCIP_CALL( SCIPallocBlockMemory(scip, &presoldata) );
2408 
2409  /* include presolver */
2410  SCIP_CALL( SCIPincludePresolBasic(scip, &presol, PRESOL_NAME, PRESOL_DESC, PRESOL_PRIORITY, PRESOL_MAXROUNDS,
2411  PRESOL_TIMING, presolExecDomcol, presoldata) );
2412  SCIP_CALL( SCIPsetPresolCopy(scip, presol, presolCopyDomcol) );
2413  SCIP_CALL( SCIPsetPresolFree(scip, presol, presolFreeDomcol) );
2414 
2415  SCIP_CALL( SCIPaddIntParam(scip,
2416  "presolving/domcol/numminpairs",
2417  "minimal number of pair comparisons",
2418  &presoldata->numminpairs, FALSE, DEFAULT_NUMMINPAIRS, 100, DEFAULT_NUMMAXPAIRS, NULL, NULL) );
2419 
2420  SCIP_CALL( SCIPaddIntParam(scip,
2421  "presolving/domcol/nummaxpairs",
2422  "maximal number of pair comparisons",
2423  &presoldata->nummaxpairs, FALSE, DEFAULT_NUMMAXPAIRS, DEFAULT_NUMMINPAIRS, 1000000000, NULL, NULL) );
2424 
2425  SCIP_CALL( SCIPaddBoolParam(scip,
2426  "presolving/domcol/predbndstr",
2427  "should predictive bound strengthening be applied?",
2428  &presoldata->predbndstr, FALSE, DEFAULT_PREDBNDSTR, NULL, NULL) );
2429 
2430  SCIP_CALL( SCIPaddBoolParam(scip,
2431  "presolving/domcol/continuousred",
2432  "should reductions for continuous variables be performed?",
2433  &presoldata->continuousred, FALSE, DEFAULT_CONTINUOUS_RED, NULL, NULL) );
2434 
2435  return SCIP_OKAY;
2436 }
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:6917
SCIPgetNIntVars
int SCIPgetNIntVars(SCIP *scip)
Definition: scip.c:11902
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:10889
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:6968
SCIPgetStage
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip.c:821
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:17276
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:47088
SCIPisGE
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47015
SCIP_Var
Definition: struct_var.h:198
SCIPvarIsBinary
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16842
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:47350
presol_domcol.h
dominated column presolver
FALSE
#define FALSE
Definition: def.h:64
SCIPgetNActivePricers
int SCIPgetNActivePricers(SCIP *scip)
Definition: scip.c:5718
SCIPinfinity
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:47028
SCIPisNegative
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
Definition: scip.c:47100
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:2399
SCIPfreeBlockMemory
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:22602
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:1382
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:22016
SCIPisEQ
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46963
SCIPfreeBufferArray
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22632
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:22585
SCIPdebugMsgPrint
#define SCIPdebugMsgPrint
Definition: scip.h:456
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:455
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:4265
SCIPmatrixGetRowNNonzs
int SCIPmatrixGetRowNNonzs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1373
SCIPvarGetUbGlobal
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17286
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:46976
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:22106
SCIPmatrixGetRowIdxPtr
int * SCIPmatrixGetRowIdxPtr(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1361
SCIPvarGetName
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16662
SCIPisNLPEnabled
SCIP_Bool SCIPisNLPEnabled(SCIP *scip)
Definition: scip.c:31195
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:350
SCIPisFeasLE
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47324
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:1184
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:1520
SCIPallocBufferArray
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:22620
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:1968
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:17124
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:25575
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:47039
SCIP_DECL_PRESOLEXEC
static SCIP_DECL_PRESOLEXEC(presolExecDomcol)
Definition: presol_domcol.c:1984
pub_matrix.h
public methods for matrix
SCIPgetNBinVars
int SCIPgetNBinVars(SCIP *scip)
Definition: scip.c:11857
SCIPinProbing
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip.c:35836
SCIPgetNVars
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11812
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:6952
SCIPallowDualReds
SCIP_Bool SCIPallowDualReds(SCIP *scip)
Definition: scip.c:25885
SCIPvarGetStatus
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:16781
DEFAULT_NUMMAXPAIRS
#define DEFAULT_NUMMAXPAIRS
Definition: presol_domcol.c:53
SCIP_Real
#define SCIP_Real
Definition: def.h:149
SCIPisStopped
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1145
detectParallelCols
static SCIP_RETCODE detectParallelCols(SCIP *scip, SCIP_MATRIX *matrix, int *pclass, SCIP_Bool *varineq)
Definition: presol_domcol.c:1013
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:134
SCIPvarGetType
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16827
SCIPisZero
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:47076
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:46989
SCIPisFeasIntegral
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:47399
SCIPmatrixGetColNUplocks
int SCIPmatrixGetColNUplocks(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1301
BMSclearMemoryArray
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:112
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:47161
SCIPABORT
#define SCIPABORT()
Definition: def.h:322
PRESOL_MAXROUNDS
#define PRESOL_MAXROUNDS
Definition: presol_domcol.c:49
SCIP_DECL_PRESOLCOPY
static SCIP_DECL_PRESOLCOPY(presolCopyDomcol)
Definition: presol_domcol.c:1954
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:47149
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:4239
SCIPmatrixGetColNNonzs
int SCIPmatrixGetColNNonzs(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1257
SCIP_VARTYPE_CONTINUOUS
Definition: type_var.h:58