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