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