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