Scippy

SCIP

Solving Constraint Integer Programs

presol_implfree.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2017 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file presol_implfree.c
17  * @brief perform multi-aggregation on implied free variables
18  * @author Dieter Weninger
19  *
20  * This presolver tries to find implied free variables within equalities
21  * which are convenient for multi-aggregation.
22  *
23  */
24 
25 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
26 
27 #include <stdio.h>
28 #include <assert.h>
29 #include <string.h>
30 
31 
32 #include "scip/pub_matrix.h"
33 #include "presol_implfree.h"
34 
35 #define PRESOL_NAME "implfree"
36 #define PRESOL_DESC "exploit implied free variables for multi-aggregation"
37 #define PRESOL_PRIORITY -1000 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */
38 #define PRESOL_MAXROUNDS 0 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
39 #define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */
40 
41 #define MAXABSRATIO ((SCIP_Real)1000.0) /**< max abs coefficients ratio */
42 #define SIDECHANGERATIO ((SCIP_Real)10.0) /**< max side change ratio */
43 
44 
45 /*
46  * Local methods
47  */
48 
49 /** calculate max activity of one row without one column */
50 static
52  SCIP* scip, /**< SCIP main data structure */
53  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
54  int row, /**< row index */
55  int col /**< column index */
56  )
57 {
58  int c;
59  SCIP_Real val;
60  int* rowpnt;
61  int* rowend;
62  SCIP_Real* valpnt;
63  SCIP_Real maxactivity;
64  SCIP_Real lb;
65  SCIP_Real ub;
66 
67  assert(scip != NULL);
68  assert(matrix != NULL);
69 
70  maxactivity = 0;
71 
72  rowpnt = SCIPmatrixGetRowIdxPtr(matrix, row);
73  rowend = rowpnt + SCIPmatrixGetRowNNonzs(matrix, row);
74  valpnt = SCIPmatrixGetRowValPtr(matrix, row);
75 
76  for(; (rowpnt < rowend); rowpnt++, valpnt++)
77  {
78  c = *rowpnt;
79  val = *valpnt;
80 
81  if( c == col )
82  continue;
83 
84  if( val > 0.0 )
85  {
86  ub = SCIPmatrixGetColUb(matrix, c);
87  assert(!SCIPisInfinity(scip, ub));
88  maxactivity += val * ub;
89  }
90  else if( val < 0.0 )
91  {
92  lb = SCIPmatrixGetColLb(matrix, c);
93  assert(!SCIPisInfinity(scip, -lb));
94  maxactivity += val * lb;
95  }
96  }
97 
98  return maxactivity;
99 }
100 
101 /** calculate min activity of one row without one column */
102 static
104  SCIP* scip, /**< SCIP main data structure */
105  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
106  int row, /**< row index */
107  int col /**< column index */
108  )
109 {
110  int c;
111  SCIP_Real val;
112  int* rowpnt;
113  int* rowend;
114  SCIP_Real* valpnt;
115  SCIP_Real minactivity;
116  SCIP_Real lb;
117  SCIP_Real ub;
118 
119  assert(scip != NULL);
120  assert(matrix != NULL);
121 
122  minactivity = 0;
123 
124  rowpnt = SCIPmatrixGetRowIdxPtr(matrix, row);
125  rowend = rowpnt + SCIPmatrixGetRowNNonzs(matrix, row);
126  valpnt = SCIPmatrixGetRowValPtr(matrix, row);
127 
128  for(; (rowpnt < rowend); rowpnt++, valpnt++)
129  {
130  c = *rowpnt;
131  val = *valpnt;
132 
133  if( c == col )
134  continue;
135 
136  if( val > 0.0 )
137  {
138  lb = SCIPmatrixGetColLb(matrix, c);
139  assert(!SCIPisInfinity(scip, -lb));
140  minactivity += val * lb;
141  }
142  else if( val < 0.0 )
143  {
144  ub = SCIPmatrixGetColUb(matrix, c);
145  assert(!SCIPisInfinity(scip, ub));
146  minactivity += val * ub;
147  }
148  }
149 
150  return minactivity;
151 }
152 
153 /** get min/max residual activity without the specified column */
154 static
156  SCIP* scip, /**< SCIP main data structure */
157  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
158  int col, /**< column index */
159  int row, /**< row index */
160  SCIP_Real val, /**< coefficient of this variable in this row */
161  SCIP_Real* minresactivity, /**< minimum residual activity of this row */
162  SCIP_Real* maxresactivity, /**< maximum residual activity of this row */
163  SCIP_Bool* isminsettoinfinity, /**< flag indicating if minresactiviy is set to infinity */
164  SCIP_Bool* ismaxsettoinfinity /**< flag indicating if maxresactiviy is set to infinity */
165  )
166 {
167  SCIP_Real lb;
168  SCIP_Real ub;
169  int nmaxactneginf;
170  int nmaxactposinf;
171  int nminactneginf;
172  int nminactposinf;
173  SCIP_Real maxactivity;
174  SCIP_Real minactivity;
175 
176  assert(scip != NULL);
177  assert(matrix != NULL);
178  assert(minresactivity != NULL);
179  assert(maxresactivity != NULL);
180  assert(isminsettoinfinity != NULL);
181  assert(ismaxsettoinfinity != NULL);
182 
183  lb = SCIPmatrixGetColLb(matrix, col);
184  ub = SCIPmatrixGetColUb(matrix, col);
185 
186  assert(!SCIPisInfinity(scip, lb));
187  assert(!SCIPisInfinity(scip, -ub));
188 
189  *isminsettoinfinity = FALSE;
190  *ismaxsettoinfinity = FALSE;
191 
192  nmaxactneginf = SCIPmatrixGetRowNMaxActNegInf(matrix, row);
193  nmaxactposinf = SCIPmatrixGetRowNMaxActPosInf(matrix, row);
194  nminactneginf = SCIPmatrixGetRowNMinActNegInf(matrix, row);
195  nminactposinf = SCIPmatrixGetRowNMinActPosInf(matrix, row);
196 
197  maxactivity = SCIPmatrixGetRowMaxActivity(matrix, row);
198  minactivity = SCIPmatrixGetRowMinActivity(matrix, row);
199 
200  if( val >= 0.0 )
201  {
202  if( SCIPisInfinity(scip, ub) )
203  {
204  assert(nmaxactposinf >= 1);
205  if( nmaxactposinf == 1 && nmaxactneginf == 0 )
206  *maxresactivity = getMaxActSingleRowWithoutCol(scip, matrix, row, col);
207  else
208  {
209  *maxresactivity = SCIPinfinity(scip);
210  *ismaxsettoinfinity = TRUE;
211  }
212  }
213  else
214  {
215  if( (nmaxactneginf + nmaxactposinf) > 0 )
216  {
217  *maxresactivity = SCIPinfinity(scip);
218  *ismaxsettoinfinity = TRUE;
219  }
220  else
221  *maxresactivity = maxactivity - val * ub;
222  }
223 
224  if( SCIPisInfinity(scip, -lb) )
225  {
226  assert(nminactneginf >= 1);
227  if( nminactneginf == 1 && nminactposinf == 0 )
228  *minresactivity = getMinActSingleRowWithoutCol(scip, matrix, row, col);
229  else
230  {
231  *minresactivity = -SCIPinfinity(scip);
232  *isminsettoinfinity = TRUE;
233  }
234  }
235  else
236  {
237  if( (nminactneginf + nminactposinf) > 0 )
238  {
239  *minresactivity = -SCIPinfinity(scip);
240  *isminsettoinfinity = TRUE;
241  }
242  else
243  *minresactivity = minactivity - val * lb;
244  }
245  }
246  else
247  {
248  if( SCIPisInfinity(scip, -lb) )
249  {
250  assert(nmaxactneginf >= 1);
251  if( nmaxactneginf == 1 && nmaxactposinf == 0 )
252  *maxresactivity = getMaxActSingleRowWithoutCol(scip, matrix, row, col);
253  else
254  {
255  *maxresactivity = SCIPinfinity(scip);
256  *ismaxsettoinfinity = TRUE;
257  }
258  }
259  else
260  {
261  if( (nmaxactneginf + nmaxactposinf) > 0 )
262  {
263  *maxresactivity = SCIPinfinity(scip);
264  *ismaxsettoinfinity = TRUE;
265  }
266  else
267  *maxresactivity = maxactivity - val * lb;
268  }
269 
270  if( SCIPisInfinity(scip, ub) )
271  {
272  assert(nminactposinf >= 1);
273  if( nminactposinf == 1 && nminactneginf == 0 )
274  *minresactivity = getMinActSingleRowWithoutCol(scip, matrix, row, col);
275  else
276  {
277  *minresactivity = -SCIPinfinity(scip);
278  *isminsettoinfinity = TRUE;
279  }
280  }
281  else
282  {
283  if( (nminactneginf + nminactposinf) > 0 )
284  {
285  *minresactivity = -SCIPinfinity(scip);
286  *isminsettoinfinity = TRUE;
287  }
288  else
289  *minresactivity = minactivity - val * ub;
290  }
291  }
292 }
293 
294 /** calculate the bounds of one variable from one row */
295 static
297  SCIP* scip, /**< SCIP main data structure */
298  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
299  int col, /**< column index of variable */
300  int row, /**< row index */
301  SCIP_Real val, /**< coefficient of this column in this row */
302  SCIP_Real* rowlb, /**< lower bound of row */
303  SCIP_Bool* lbfound, /**< flag indicating that a lower bound was calculated */
304  SCIP_Real* rowub, /**< upper bound of row */
305  SCIP_Bool* ubfound /**< flag indicating that an upper bound was calculated */
306  )
307 {
308  SCIP_Bool isminsettoinfinity;
309  SCIP_Bool ismaxsettoinfinity;
310  SCIP_Real minresactivity;
311  SCIP_Real maxresactivity;
312  SCIP_Real lhs;
313  SCIP_Real rhs;
314 
315  assert(rowlb != NULL);
316  assert(lbfound != NULL);
317  assert(rowub != NULL);
318  assert(ubfound != NULL);
319 
320  *rowlb = -SCIPinfinity(scip);
321  *rowub = SCIPinfinity(scip);
322  *lbfound = FALSE;
323  *ubfound = FALSE;
324 
325  getActivityResiduals(scip, matrix, col, row, val, &minresactivity, &maxresactivity,
326  &isminsettoinfinity, &ismaxsettoinfinity);
327 
328  lhs = SCIPmatrixGetRowLhs(matrix, row);
329  rhs = SCIPmatrixGetRowRhs(matrix, row);
330 
331  if( val > 0.0 )
332  {
333  if( !isminsettoinfinity && !SCIPisInfinity(scip, rhs) )
334  {
335  *rowub = (rhs - minresactivity)/val;
336  *ubfound = TRUE;
337  }
338 
339  if( !ismaxsettoinfinity && !SCIPisInfinity(scip, -lhs) )
340  {
341  *rowlb = (lhs - maxresactivity)/val;
342  *lbfound = TRUE;
343  }
344  }
345  else
346  {
347  if( !isminsettoinfinity && !SCIPisInfinity(scip, rhs) )
348  {
349  *rowlb = (rhs - minresactivity)/val;
350  *lbfound = TRUE;
351  }
352 
353  if( !ismaxsettoinfinity && !SCIPisInfinity(scip, -lhs) )
354  {
355  *rowub = (lhs - maxresactivity)/val;
356  *ubfound = TRUE;
357  }
358  }
359 }
360 
361 /** verify if the variable is implied free */
362 static
364  SCIP* scip, /**< SCIP main data structure */
365  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
366  int col, /**< column index for implied free test */
367  int row, /**< constraint planned for multi-aggregation */
368  SCIP_Bool* lockedcons, /**< constraint not suitable for bound implication */
369  int* impllbrowidx, /**< row which implies the lower bound */
370  int* implubrowidx /**< row which implied the upper bound */
371  )
372 {
373  SCIP_Real varub;
374  SCIP_Real varlb;
375  SCIP_Real impliedub;
376  SCIP_Real impliedlb;
377  int* colpnt;
378  int* colend;
379  SCIP_Real* valpnt;
380  SCIP_Bool impliedfree;
381 
382  assert(scip != NULL);
383  assert(matrix != NULL);
384  assert(lockedcons != NULL);
385  assert(impllbrowidx != NULL);
386  assert(implubrowidx != NULL);
387 
388  impliedfree = FALSE;
389 
390  varub = SCIPmatrixGetColUb(matrix, col);
391  varlb = SCIPmatrixGetColLb(matrix, col);
392 
393  impliedub = SCIPinfinity(scip);
394  impliedlb = -SCIPinfinity(scip);
395 
396  *impllbrowidx = -1;
397  *implubrowidx = -1;
398 
399  colpnt = SCIPmatrixGetColIdxPtr(matrix, col);
400  colend = colpnt + SCIPmatrixGetColNNonzs(matrix, col);
401  valpnt = SCIPmatrixGetColValPtr(matrix, col);
402 
403  for( ; (colpnt < colend); colpnt++, valpnt++ )
404  {
405  SCIP_Real rowlb;
406  SCIP_Real rowub;
407  SCIP_Bool lbfound;
408  SCIP_Bool ubfound;
409 
410  if( lockedcons[*colpnt] )
411  {
412  impliedfree = FALSE;
413  break;
414  }
415 
416  if(*colpnt == row)
417  continue;
418 
419  getVarBoundsOfRow(scip, matrix, col, *colpnt, *valpnt,
420  &rowlb, &lbfound, &rowub, &ubfound);
421 
422  if( lbfound && rowlb > impliedlb )
423  {
424  impliedlb = rowlb;
425  *impllbrowidx = *colpnt;
426  }
427 
428  if( ubfound && rowub < impliedub )
429  {
430  impliedub = rowub;
431  *implubrowidx = *colpnt;
432  }
433  }
434 
435  if( !SCIPisInfinity(scip, -varlb) && !SCIPisInfinity(scip, varub) &&
436  SCIPisFeasLE(scip, impliedub, varub) && SCIPisFeasLE(scip, varlb, impliedlb) )
437  {
438  impliedfree = TRUE;
439  }
440 
441  return impliedfree;
442 }
443 
444 /** calculate the amount of fill-in getting from multi-aggregation */
445 static
447  SCIP_MATRIX* matrix, /**< constraint matrix object */
448  int col, /**< column index */
449  int row /**< row index */
450  )
451 {
452  SCIP_Real fillin;
453  int rowcnt;
454  int colcnt;
455  int nonzerosnew;
456  int nonzerosold;
457 
458  assert(matrix != NULL);
459 
460  rowcnt = SCIPmatrixGetRowNNonzs(matrix, row);
461  colcnt = SCIPmatrixGetColNNonzs(matrix, col);
462  assert(rowcnt > 0 && colcnt > 0);
463 
464  nonzerosold = rowcnt + colcnt - 1;
465  nonzerosnew = (colcnt - 1) * (rowcnt - 1);
466 
467  fillin = (SCIP_Real)nonzerosnew / (SCIP_Real)nonzerosold;
468 
469  return fillin;
470 }
471 
472 /** verify if the multi-aggregation is numerical stable concerning the side change */
473 static
475  SCIP* scip, /**< current scip instance */
476  SCIP_Real oldside, /**< old rhs or lhs of constraint */
477  SCIP_Real aggrconst, /**< multiaggrconstant */
478  SCIP_Real val /**< coefficient of multiaggvariable not within the aggregated constraint */
479  )
480 {
481  SCIP_Real enumerator;
482  SCIP_Real denominator;
483 
484  enumerator = REALABS( -(val * aggrconst) - oldside );
485  denominator = MAX(1.0,REALABS(oldside)); /*lint !e666*/
486 
487  return enumerator/denominator <= SIDECHANGERATIO;
488 }
489 
490 /** calculate the huge contribution counters */
491 static
493  SCIP* scip, /**< current scip instance */
494  SCIP_MATRIX* matrix, /**< constraint matrix */
495  int* maxactposhuge, /**< max activity positive contribution counter */
496  int* maxactneghuge, /**< max activity negative contribution counter */
497  int* minactposhuge, /**< min activity positive contribution counter */
498  int* minactneghuge /**< min activity negative contribution counter */
499  )
500 {
501  SCIP_Real val;
502  int* rowpnt;
503  int* rowend;
504  SCIP_Real* valpnt;
505  int col;
506  int row;
507  SCIP_Real lb;
508  SCIP_Real ub;
509  int nrows;
510 
511  assert(scip != NULL);
512  assert(matrix != NULL);
513 
514  nrows = SCIPmatrixGetNRows(matrix);
515 
516  for( row = 0; row < nrows; row++ )
517  {
518  maxactposhuge[row] = 0;
519  maxactneghuge[row] = 0;
520  minactposhuge[row] = 0;
521  minactneghuge[row] = 0;
522 
523  rowpnt = SCIPmatrixGetRowIdxPtr(matrix, row);
524  rowend = rowpnt + SCIPmatrixGetRowNNonzs(matrix, row);
525  valpnt = SCIPmatrixGetRowValPtr(matrix, row);
526 
527  for( ; rowpnt < rowend; rowpnt++, valpnt++ )
528  {
529  col = *rowpnt;
530  val = *valpnt;
531 
532  lb = SCIPmatrixGetColLb(matrix, col);
533  ub = SCIPmatrixGetColUb(matrix, col);
534 
535  if( val > 0.0 )
536  {
537  if( !SCIPisInfinity(scip, ub) )
538  {
539  if( SCIPisHugeValue(scip, val * ub) )
540  maxactposhuge[row]++;
541  else if( SCIPisHugeValue(scip, -val * ub) )
542  maxactneghuge[row]++;
543  }
544 
545  if( !SCIPisInfinity(scip, -lb) )
546  {
547  if( SCIPisHugeValue(scip, val * lb) )
548  minactposhuge[row]++;
549  else if( SCIPisHugeValue(scip, -val * lb) )
550  minactneghuge[row]++;
551  }
552  }
553  else
554  {
555  if( !SCIPisInfinity(scip, -lb) )
556  {
557  if( SCIPisHugeValue(scip, val * lb) )
558  maxactposhuge[row]++;
559  else if( SCIPisHugeValue(scip, -val * lb) )
560  maxactneghuge[row]++;
561  }
562 
563  if( !SCIPisInfinity(scip, ub) )
564  {
565  if( SCIPisHugeValue(scip, val * ub) )
566  minactposhuge[row]++;
567  else if( SCIPisHugeValue(scip, -val * ub) )
568  minactneghuge[row]++;
569  }
570  }
571  }
572  }
573 }
574 
575 /** verify if activities could be inexact */
576 static
578  SCIP* scip, /**< SCIP data structure */
579  SCIP_MATRIX* matrix, /**< constraint matrix object */
580  int row, /**< row index */
581  int col, /**< column index */
582  SCIP_Real val, /**< coefficient value of variable in linear constraint */
583  int* maxactposhuge, /**< max activity positive contribution counter */
584  int* maxactneghuge, /**< max activity negative contribution counter */
585  int* minactposhuge, /**< min activity positive contribution counter */
586  int* minactneghuge, /**< min activity negative contribution counter */
587  SCIP_Bool* minisrelax, /**< flag indicating min activity could be inexact */
588  SCIP_Bool* maxisrelax /**< flag indicating max activity could be inexact */
589  )
590 {
591  int numinf;
592  int numhuge;
593  SCIP_Real lb;
594  SCIP_Real ub;
595  int nmaxactposinf;
596  int nmaxactneginf;
597  int nminactposinf;
598  int nminactneginf;
599 
600  *minisrelax = FALSE;
601  *maxisrelax = FALSE;
602 
603  nmaxactposinf = SCIPmatrixGetRowNMaxActPosInf(matrix, row);
604  nmaxactneginf = SCIPmatrixGetRowNMaxActNegInf(matrix, row);
605  nminactposinf = SCIPmatrixGetRowNMinActPosInf(matrix, row);
606  nminactneginf = SCIPmatrixGetRowNMinActNegInf(matrix, row);
607 
608  assert(nmaxactposinf >= 0);
609  assert(nmaxactneginf >= 0);
610  assert(nminactposinf >= 0);
611  assert(nminactneginf >= 0);
612  assert(maxactposhuge[row] >= 0);
613  assert(maxactneghuge[row] >= 0);
614  assert(minactposhuge[row] >= 0);
615  assert(minactneghuge[row] >= 0);
616 
617  numinf = nmaxactposinf + nmaxactneginf + nminactposinf + nminactneginf;
618  numhuge = maxactposhuge[row] + maxactneghuge[row] + minactposhuge[row] + minactneghuge[row];
619 
620  lb = SCIPmatrixGetColLb(matrix, col);
621  ub = SCIPmatrixGetColUb(matrix, col);
622 
623  if( val > 0 )
624  {
625  if( SCIPisInfinity(scip, ub) )
626  {
627  assert(nmaxactposinf >= 1);
628  if( numinf + numhuge - 1 >= 1 )
629  *maxisrelax = TRUE;
630  }
631  else if( SCIPisHugeValue(scip, ub * val) )
632  {
633  assert(maxactposhuge[row] >= 1);
634  if( numinf + numhuge - 1 >= 1 )
635  *maxisrelax = TRUE;
636  }
637  else if(SCIPisHugeValue(scip, ub * -val) )
638  {
639  assert(maxactneghuge[row] >= 1);
640  if( numinf + numhuge - 1 >= 1 )
641  *maxisrelax = TRUE;
642  }
643  else
644  {
645  if( numinf + numhuge >= 1 )
646  *maxisrelax = TRUE;
647  }
648 
649  if( SCIPisInfinity(scip, -lb) )
650  {
651  assert(nminactneginf >= 1);
652  if( numinf + numhuge - 1 >= 1 )
653  *minisrelax = TRUE;
654  }
655  else if( SCIPisHugeValue(scip, lb * val) )
656  {
657  assert(minactposhuge[row] >= 1);
658  if( numinf + numhuge - 1 >= 1 )
659  *minisrelax = TRUE;
660  }
661  else if(SCIPisHugeValue(scip, lb * -val) )
662  {
663  assert(minactneghuge[row] >= 1);
664  if( numinf + numhuge - 1 >= 1 )
665  *minisrelax = TRUE;
666  }
667  else
668  {
669  if( numinf + numhuge >= 1 )
670  *minisrelax = TRUE;
671  }
672  }
673  else
674  {
675  if( SCIPisInfinity(scip, -lb) )
676  {
677  assert(nmaxactneginf >= 1);
678  if( numinf + numhuge - 1 >= 1 )
679  *maxisrelax = TRUE;
680  }
681  else if( SCIPisHugeValue(scip, lb * val) )
682  {
683  assert(maxactposhuge[row] >= 1);
684  if( numinf + numhuge - 1 >= 1 )
685  *maxisrelax = TRUE;
686  }
687  else if(SCIPisHugeValue(scip, lb * -val) )
688  {
689  assert(maxactneghuge[row] >= 1);
690  if( numinf + numhuge - 1 >= 1 )
691  *maxisrelax = TRUE;
692  }
693  else
694  {
695  if( numinf + numhuge >= 1 )
696  *maxisrelax = TRUE;
697  }
698 
699  if( SCIPisInfinity(scip, ub) )
700  {
701  assert(nminactposinf >= 1);
702  if( numinf + numhuge - 1 >= 1 )
703  *minisrelax = TRUE;
704  }
705  else if( SCIPisHugeValue(scip, ub * val) )
706  {
707  assert(minactposhuge[row] >= 1);
708  if( numinf + numhuge - 1 >= 1 )
709  *minisrelax = TRUE;
710  }
711  else if(SCIPisHugeValue(scip, ub * -val) )
712  {
713  assert(minactneghuge[row] >= 1);
714  if( numinf + numhuge - 1 >= 1 )
715  *minisrelax = TRUE;
716  }
717  else
718  {
719  if( numinf + numhuge >= 1 )
720  *minisrelax = TRUE;
721  }
722  }
723 }
724 
725 
726 /** verify if the multi-aggregation is numerical stable */
727 static
729  SCIP* scip, /**< SCIP data structure */
730  SCIP_MATRIX* matrix, /**< constraint matrix object */
731  int col, /**< column index */
732  int row, /**< row index */
733  SCIP_Real aggrconst, /**< aggregation constant */
734  int* maxactposhuge, /**< max activity positive contribution counter */
735  int* maxactneghuge, /**< max activity negative contribution counter */
736  int* minactposhuge, /**< min activity positive contribution counter */
737  int* minactneghuge /**< min activity negative contribution counter */
738  )
739 {
740  int* rowpnt;
741  int* rowend;
742  int* colpnt;
743  int* colend;
744  SCIP_Real* valpnt;
745  SCIP_Bool numericalstable;
746  SCIP_Bool minisrelax;
747  SCIP_Bool maxisrelax;
748  SCIP_Real lhs;
749  SCIP_Real rhs;
750  SCIP_Real minabsval;
751  SCIP_Real maxabsval;
752 
753  numericalstable = TRUE;
754 
755  minabsval = SCIPinfinity(scip);
756  maxabsval = -1.0;
757 
758  rowpnt = SCIPmatrixGetRowIdxPtr(matrix, row);
759  rowend = rowpnt + SCIPmatrixGetRowNNonzs(matrix, row);
760  valpnt = SCIPmatrixGetRowValPtr(matrix, row);
761 
762  for( ; rowpnt < rowend; rowpnt++, valpnt++ )
763  {
764  SCIP_Real absval;
765 
766  absval = REALABS(*valpnt);
767  if( absval < minabsval )
768  minabsval = absval;
769  if( absval > maxabsval )
770  maxabsval = absval;
771  }
772 
773  /* 1. criterion:
774  * do not allow multi-aggregation if the abs coefficients differ too much
775  */
776  if( maxabsval / minabsval > MAXABSRATIO )
777  {
778  numericalstable = FALSE;
779  return numericalstable;
780  }
781 
782  colpnt = SCIPmatrixGetColIdxPtr(matrix, col);
783  colend = colpnt + SCIPmatrixGetColNNonzs(matrix, col);
784  valpnt = SCIPmatrixGetColValPtr(matrix, col);
785 
786  for( ; colpnt < colend; colpnt++, valpnt++ )
787  {
788  int r;
789  SCIP_Real val;
790 
791  r = *colpnt;
792  val = *valpnt;
793 
794  /* 2. criterion:
795  * do not allow huge contributions to the activities
796  */
797  getActivityRelax(scip, matrix, r, col, val,
798  maxactposhuge, maxactneghuge, minactposhuge, minactneghuge,
799  &minisrelax, &maxisrelax);
800 
801  if( minisrelax || maxisrelax )
802  {
803  numericalstable = FALSE;
804  break;
805  }
806 
807  if( r == row )
808  continue;
809 
810  /* 3. criterion:
811  * do not allow multi-aggregation if great sides changes appear
812  */
813  lhs = SCIPmatrixGetRowLhs(matrix, r);
814  if( !SCIPisInfinity(scip, -lhs) )
815  {
816  if( !sideChangeNumericalStable(scip, lhs, aggrconst, val) )
817  {
818  numericalstable = FALSE;
819  break;
820  }
821  }
822  rhs = SCIPmatrixGetRowRhs(matrix, r);
823  if( !SCIPisInfinity(scip, rhs) )
824  {
825  if( !sideChangeNumericalStable(scip, rhs, aggrconst, val) )
826  {
827  numericalstable = FALSE;
828  break;
829  }
830  }
831  }
832 
833  return numericalstable;
834 }
835 
836 /** calculate sides after aggregation */
837 static
839  SCIP* scip, /**< SCIP data structure */
840  SCIP_MATRIX* matrix, /**< constraint matrix object */
841  int col, /**< column index */
842  int row, /**< row index */
843  SCIP_Real coef, /**< coefficient of aggregated variable */
844  SCIP_Real* newlhs, /**< new calculated left hand side */
845  SCIP_Real* newrhs /**< new calculated right hand side */
846  )
847 {
848  SCIP_Real lb;
849  SCIP_Real ub;
850  SCIP_Real lhs;
851  SCIP_Real rhs;
852 
853  assert(scip != NULL);
854  assert(matrix != NULL);
855  assert(newlhs != NULL);
856  assert(newrhs != NULL);
857 
858  lhs = SCIPmatrixGetRowLhs(matrix, row);
859  rhs = SCIPmatrixGetRowRhs(matrix, row);
860 
861  lb = SCIPmatrixGetColLb(matrix, col);
862  ub = SCIPmatrixGetColUb(matrix, col);
863 
864  if( coef > 0.0 )
865  {
866  if( SCIPisInfinity(scip, -lb) )
867  *newrhs = SCIPinfinity(scip);
868  else
869  *newrhs = rhs - coef * lb;
870 
871  if( SCIPisInfinity(scip, ub) )
872  *newlhs = -SCIPinfinity(scip);
873  else
874  *newlhs = lhs - coef * ub;
875  }
876  else
877  {
878  if( SCIPisInfinity(scip, -lb) )
879  *newlhs = -SCIPinfinity(scip);
880  else
881  *newlhs = rhs - coef * lb;
882 
883  if( SCIPisInfinity(scip, ub) )
884  *newrhs = SCIPinfinity(scip);
885  else
886  *newrhs = lhs - coef * ub;
887  }
888 
889  assert(SCIPisLE(scip, *newlhs, *newrhs));
890 }
891 
892 /** verify if the constraint becomes redundant after aggregation */
893 static
895  SCIP* scip, /**< SCIP data structure */
896  SCIP_MATRIX* matrix, /**< constraint matrix object */
897  int col, /**< column index */
898  int row, /**< row index */
899  SCIP_Real coef /**< coefficient of aggregated variable */
900  )
901 {
902  SCIP_Real newlhs;
903  SCIP_Real newrhs;
904  SCIP_Bool consredundant;
905  SCIP_Real minresactivity;
906  SCIP_Real maxresactivity;
907  SCIP_Bool isminsettoinfinity;
908  SCIP_Bool ismaxsettoinfinity;
909 
910  consredundant = FALSE;
911 
912  calcNewSidesAfterAggregation(scip, matrix, col, row, coef, &newlhs, &newrhs);
913  getActivityResiduals(scip, matrix, col, row, coef, &minresactivity, &maxresactivity, &isminsettoinfinity, &ismaxsettoinfinity);
914 
915  if( !isminsettoinfinity && !ismaxsettoinfinity )
916  consredundant = (SCIPisFeasLE(scip, newlhs, minresactivity) && SCIPisFeasLE(scip, maxresactivity, newrhs));
917 
918  return consredundant;
919 }
920 
921 /** identify candidates for multi-aggregation */
922 static
924  SCIP* scip, /**< SCIP data structure */
925  SCIP_MATRIX* matrix, /**< constraint matrix object */
926  SCIP_Bool* multiaggvars, /**< array indicating multi-aggregatable variables */
927  int* nummultiaggvars, /**< number of multi-aggregatable variables */
928  int* multiaggequalities, /**< array holding aggregation equality row indices */
929  SCIP_Bool* consredundant, /**< array indicating which constraint became redundant */
930  SCIP_Bool* lockedcons, /**< constraints which could not be used for bound implication */
931  SCIP_Bool* skipvars, /**< array holding which variables should be investigated */
932  int* maxactposhuge, /**< max activity positive contribution counter */
933  int* maxactneghuge, /**< max activity negative contribution counter */
934  int* minactposhuge, /**< min activity positive contribution counter */
935  int* minactneghuge /**< min activity negative contribution counter */
936  )
937 {
938  int r;
939  SCIP_Real bestfillin;
940  int bestvaridx;
941  SCIP_Bool bestconsredundant;
942  int tmpimpllbrowidx;
943  int tmpimplubrowidx;
944  int bestimpllbrowidx;
945  int bestimplubrowidx;
946  int nrows;
947 
948  assert(scip != NULL);
949  assert(matrix != NULL);
950  assert(multiaggvars != NULL);
951  assert(nummultiaggvars != NULL);
952  assert(multiaggequalities != NULL);
953  assert(consredundant != NULL);
954  assert(lockedcons != NULL);
955  assert(skipvars != NULL);
956 
957  nrows = SCIPmatrixGetNRows(matrix);
958 
959  for( r = 0; r < nrows; r++ )
960  {
961  /* consider only equalities with min three variables */
962  if( SCIPmatrixGetRowNNonzs(matrix, r) > 2 &&
963  SCIPisEQ(scip, SCIPmatrixGetRowLhs(matrix, r), SCIPmatrixGetRowRhs(matrix, r)) )
964  {
965  int* rowpnt;
966  int* rowend;
967  SCIP_Real* valpnt;
968 
969  rowpnt = SCIPmatrixGetRowIdxPtr(matrix, r);
970  rowend = rowpnt + SCIPmatrixGetRowNNonzs(matrix, r);
971  valpnt = SCIPmatrixGetRowValPtr(matrix, r);
972 
973  bestfillin = 1.0;
974  bestvaridx = -1;
975  bestimpllbrowidx = -1; /* only for lint */
976  bestimplubrowidx = -1; /* only for lint */
977  bestconsredundant = FALSE;
978 
979  for( ; rowpnt < rowend; rowpnt++, valpnt++ )
980  {
981  SCIP_VAR* var;
982  SCIP_Real aggrconst;
983  SCIP_Real fillin;
984 
985  var = SCIPmatrixGetVar(matrix, *rowpnt);
986 
988  continue;
989 
990  /* search for a continuous variable for aggregation which is implied free,
991  produces less fill-in and leads to numerical stability */
992  if( !skipvars[*rowpnt] && isVarImpliedFree(scip, matrix, *rowpnt, r, lockedcons, &tmpimpllbrowidx, &tmpimplubrowidx) )
993  {
994  assert(tmpimpllbrowidx >= 0 && tmpimplubrowidx >= 0);
995  aggrconst = SCIPmatrixGetRowRhs(matrix, r) / (*valpnt);
996 
997  if( numericalStable(scip, matrix, *rowpnt, r, aggrconst,
998  maxactposhuge, maxactneghuge, minactposhuge, minactneghuge) )
999  {
1000  fillin = getFillIn(matrix, *rowpnt, r);
1001  if( isConsRedundant(scip, matrix, *rowpnt, r, *valpnt) )
1002  {
1003  if( (fillin < bestfillin) || (!bestconsredundant && fillin <= 1.0) )
1004  {
1005  bestfillin = fillin;
1006  bestvaridx = *rowpnt;
1007  bestimpllbrowidx = tmpimpllbrowidx;
1008  bestimplubrowidx = tmpimplubrowidx;
1009  bestconsredundant = TRUE;
1010  }
1011  }
1012  else
1013  {
1014  /* prefer redundant constraints */
1015  if( bestconsredundant )
1016  continue;
1017 
1018  if( fillin < bestfillin )
1019  {
1020  bestfillin = fillin;
1021  bestvaridx = *rowpnt;
1022  bestimpllbrowidx = tmpimpllbrowidx;
1023  bestimplubrowidx = tmpimplubrowidx;
1024  }
1025  }
1026  }
1027  }
1028  else
1029  {
1030  skipvars[*rowpnt] = TRUE;
1031  }
1032  }
1033 
1034  if( bestvaridx > -1 && multiaggvars[bestvaridx] != TRUE )
1035  {
1036  assert(bestvaridx < SCIPmatrixGetNColumns(matrix));
1037  multiaggvars[bestvaridx] = TRUE;
1038  multiaggequalities[bestvaridx] = r;
1039  lockedcons[bestimpllbrowidx] = TRUE;
1040  lockedcons[bestimplubrowidx] = TRUE;
1041  (*nummultiaggvars)++;
1042 
1043  if( bestconsredundant )
1044  {
1045  consredundant[r] = TRUE;
1046  lockedcons[r] = TRUE;
1047  }
1048  }
1049  }
1050  }
1051 }
1052 
1053 /*
1054  * Callback methods of presolver
1055  */
1056 
1057 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
1058 static
1059 SCIP_DECL_PRESOLCOPY(presolCopyImplfree)
1060 { /*lint --e{715}*/
1061  assert(scip != NULL);
1062  assert(presol != NULL);
1063  assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
1064 
1065  /* call inclusion method of presolver */
1067 
1068  return SCIP_OKAY;
1069 }
1070 
1071 
1072 /** execution method of presolver */
1073 static
1074 SCIP_DECL_PRESOLEXEC(presolExecImplfree)
1075 { /*lint --e{715}*/
1076  SCIP_MATRIX* matrix;
1077  SCIP_Bool initialized;
1078  SCIP_Bool complete;
1079 
1080  assert(result != NULL);
1081  *result = SCIP_DIDNOTRUN;
1082 
1084  return SCIP_OKAY;
1085 
1087  return SCIP_OKAY;
1088 
1089  if( SCIPgetNContVars(scip) == 0 )
1090  return SCIP_OKAY;
1091 
1092  *result = SCIP_DIDNOTFIND;
1093 
1094  matrix = NULL;
1095  SCIP_CALL( SCIPmatrixCreate(scip, &matrix, &initialized, &complete) );
1096 
1097  if( initialized && complete )
1098  {
1099  SCIP_Bool* isvartomultiagg;
1100  int* multiaggequalities;
1101  int nummultiaggvars;
1102  SCIP_Bool* consredundant;
1103  SCIP_Bool* lockedcons;
1104  SCIP_Bool* skipvars;
1105  int nrows;
1106  int ncols;
1107  int* maxactposhuge;
1108  int* maxactneghuge;
1109  int* minactposhuge;
1110  int* minactneghuge;
1111 
1112  nrows = SCIPmatrixGetNRows(matrix);
1113  ncols = SCIPmatrixGetNColumns(matrix);
1114  assert(SCIPgetNVars(scip) == ncols);
1115 
1116  SCIP_CALL( SCIPallocBufferArray(scip, &isvartomultiagg, ncols) );
1117  BMSclearMemoryArray(isvartomultiagg, ncols);
1118 
1119  SCIP_CALL( SCIPallocBufferArray(scip, &multiaggequalities, ncols) );
1120  BMSclearMemoryArray(multiaggequalities, ncols);
1121 
1122  SCIP_CALL( SCIPallocBufferArray(scip, &consredundant, nrows) );
1123  BMSclearMemoryArray(consredundant, nrows);
1124 
1125  SCIP_CALL( SCIPallocBufferArray(scip, &lockedcons, nrows) );
1126  BMSclearMemoryArray(lockedcons, nrows);
1127 
1128  SCIP_CALL( SCIPallocBufferArray(scip, &skipvars, ncols) );
1129  BMSclearMemoryArray(skipvars, ncols);
1130 
1131  SCIP_CALL( SCIPallocBufferArray(scip, &maxactposhuge, nrows) );
1132  SCIP_CALL( SCIPallocBufferArray(scip, &maxactneghuge, nrows) );
1133  SCIP_CALL( SCIPallocBufferArray(scip, &minactposhuge, nrows) );
1134  SCIP_CALL( SCIPallocBufferArray(scip, &minactneghuge, nrows) );
1135 
1136  getNumHugeActivities(scip, matrix, maxactposhuge, maxactneghuge, minactposhuge, minactneghuge);
1137 
1138  nummultiaggvars = 0;
1139  getMultiaggVars(scip, matrix, isvartomultiagg,&nummultiaggvars, multiaggequalities,
1140  consredundant, lockedcons, skipvars, maxactposhuge, maxactneghuge, minactposhuge, minactneghuge);
1141 
1142  if( nummultiaggvars > 0 )
1143  {
1144  int v;
1145  for( v = 0; v < ncols; v++ )
1146  {
1147  if( isvartomultiagg[v] )
1148  {
1149  SCIP_VAR* multiaggvar;
1150  SCIP_VAR** vars;
1151  SCIP_Real* scalars;
1152  SCIP_Real multiaggcoef;
1153  SCIP_Real aggrconst;
1154  SCIP_Bool infeasible;
1155  SCIP_Bool aggregated;
1156  SCIP_CONS* multiaggcons;
1157  int row;
1158  int cnt;
1159  int* rowpnt;
1160  int* rowend;
1161  SCIP_Real* valpnt;
1162  int nvars;
1163  SCIP_Real rhs;
1164 
1165  multiaggvar = SCIPmatrixGetVar(matrix, v);
1166  assert(SCIPvarGetType(multiaggvar) == SCIP_VARTYPE_CONTINUOUS);
1167 
1168  row = multiaggequalities[v];
1169  assert(row < nrows);
1170 
1171  multiaggcons = SCIPmatrixGetCons(matrix, row);
1172  rhs = SCIPmatrixGetRowRhs(matrix, row);
1173 
1174  /* get the number of variables without the multi-agg variable itself */
1175  nvars = SCIPmatrixGetRowNNonzs(matrix, row) - 1;
1176 
1177  SCIP_CALL( SCIPallocBufferArray(scip, &scalars, nvars) );
1178  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
1179 
1180  /* get multi-agg variable coefficient and vars */
1181  rowpnt = SCIPmatrixGetRowIdxPtr(matrix, row);
1182  rowend = rowpnt + SCIPmatrixGetRowNNonzs(matrix, row);
1183  valpnt = SCIPmatrixGetRowValPtr(matrix, row);
1184  cnt = 0;
1185  multiaggcoef = 0.0;
1186  for( ; rowpnt < rowend; rowpnt++, valpnt++ )
1187  {
1188  if( *rowpnt == v )
1189  {
1190  multiaggcoef = *valpnt;
1191  continue;
1192  }
1193 
1194  vars[cnt++] = SCIPmatrixGetVar(matrix, *rowpnt);
1195  }
1196 
1197  /* avoid division by zero */
1198  if( SCIPisEQ(scip, multiaggcoef, 0.0) )
1199  continue;
1200 
1201  assert(SCIPisInfinity(scip, -SCIPmatrixGetRowLhs(matrix, row)) ||
1202  SCIPisInfinity(scip, rhs) ||
1203  SCIPisEQ(scip, SCIPmatrixGetRowLhs(matrix, row), rhs));
1204 
1205  /* we have to distinguished two cases */
1206  if( !SCIPisInfinity(scip, rhs) )
1207  aggrconst = rhs / multiaggcoef;
1208  else
1209  aggrconst = SCIPmatrixGetRowLhs(matrix, row) / multiaggcoef;
1210 
1211  /* calculate scalars */
1212  rowpnt = SCIPmatrixGetRowIdxPtr(matrix, row);
1213  rowend = rowpnt + SCIPmatrixGetRowNNonzs(matrix, row);
1214  valpnt = SCIPmatrixGetRowValPtr(matrix, row);
1215  cnt = 0;
1216  SCIPdebugMsg(scip, "constraint <%s>: multi-aggregate <%s> ==", SCIPconsGetName(multiaggcons), SCIPvarGetName(multiaggvar));
1217  for( ; rowpnt < rowend; rowpnt++, valpnt++ )
1218  {
1219  if( *rowpnt == v )
1220  continue;
1221 
1222  scalars[cnt] = -(*valpnt) / multiaggcoef; /*lint !e414*/
1223  SCIPdebugMsgPrint(scip, " %+.15g<%s>", scalars[cnt], SCIPvarGetName(SCIPmatrixGetVar(matrix, *rowpnt)));
1224 
1225  cnt++;
1226  }
1227 
1228  SCIPdebugMsgPrint(scip, " %+.15g, bounds of <%s>: [%.15g,%.15g]\n",
1229  aggrconst, SCIPvarGetName(multiaggvar), SCIPvarGetLbGlobal(multiaggvar), SCIPvarGetUbGlobal(multiaggvar));
1230 
1231  /* perform multi-aggregation */
1232  SCIP_CALL( SCIPmultiaggregateVar(scip, multiaggvar, nvars, vars, scalars, aggrconst, &infeasible, &aggregated) );
1233  assert(aggregated);
1234 
1235  SCIPfreeBufferArray(scip, &vars);
1236  SCIPfreeBufferArray(scip, &scalars);
1237 
1238  /* check for infeasible aggregation */
1239  if( infeasible )
1240  {
1241  SCIPdebugMsg(scip, "constraint <%s>: infeasible multi-aggregation\n", SCIPconsGetName(multiaggcons));
1242  return SCIP_OKAY;
1243  }
1244 
1245  (*naggrvars)++;
1246 
1247  /* remove constraint if it is redundant */
1248  if( consredundant[row] )
1249  {
1250  SCIP_CALL( SCIPdelCons(scip, multiaggcons) );
1251  (*ndelconss)++;
1252  }
1253  }
1254  }
1255  }
1256 
1257  SCIPfreeBufferArray(scip, &minactneghuge);
1258  SCIPfreeBufferArray(scip, &minactposhuge);
1259  SCIPfreeBufferArray(scip, &maxactneghuge);
1260  SCIPfreeBufferArray(scip, &maxactposhuge);
1261  SCIPfreeBufferArray(scip, &skipvars);
1262  SCIPfreeBufferArray(scip, &lockedcons);
1263  SCIPfreeBufferArray(scip, &consredundant);
1264  SCIPfreeBufferArray(scip, &multiaggequalities);
1265  SCIPfreeBufferArray(scip, &isvartomultiagg);
1266  }
1267 
1268  SCIPmatrixFree(scip, &matrix);
1269 
1270  return SCIP_OKAY;
1271 }
1272 
1273 /*
1274  * presolver specific interface methods
1275  */
1276 
1277 /** creates the implied free presolver and includes it in SCIP */
1279  SCIP* scip /**< SCIP data structure */
1280  )
1281 {
1282  SCIP_PRESOL* presol;
1283 
1284  /* include presolver */
1286  PRESOL_TIMING, presolExecImplfree, NULL) );
1287  SCIP_CALL( SCIPsetPresolCopy(scip, presol, presolCopyImplfree) );
1288 
1289  return SCIP_OKAY;
1290 }
SCIP_RETCODE SCIPincludePresolBasic(SCIP *scip, SCIP_PRESOL **presolptr, const char *name, const char *desc, int priority, int maxrounds, SCIP_PRESOLTIMING timing, SCIP_DECL_PRESOLEXEC((*presolexec)), SCIP_PRESOLDATA *presoldata)
Definition: scip.c:6854
static SCIP_DECL_PRESOLEXEC(presolExecImplfree)
static void getNumHugeActivities(SCIP *scip, SCIP_MATRIX *matrix, int *maxactposhuge, int *maxactneghuge, int *minactposhuge, int *minactneghuge)
SCIP_VAR * SCIPmatrixGetVar(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1325
int SCIPmatrixGetNRows(SCIP_MATRIX *matrix)
Definition: matrix.c:1397
static void getActivityResiduals(SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real val, SCIP_Real *minresactivity, SCIP_Real *maxresactivity, SCIP_Bool *isminsettoinfinity, SCIP_Bool *ismaxsettoinfinity)
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip.c:814
static SCIP_Real sideChangeNumericalStable(SCIP *scip, SCIP_Real oldside, SCIP_Real aggrconst, SCIP_Real val)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17166
#define SIDECHANGERATIO
SCIP_CONS * SCIPmatrixGetCons(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1525
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:12481
#define PRESOL_TIMING
static SCIP_Bool isConsRedundant(SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real coef)
void SCIPmatrixFree(SCIP *scip, SCIP_MATRIX **matrix)
Definition: matrix.c:782
#define FALSE
Definition: def.h:64
int SCIPgetNActivePricers(SCIP *scip)
Definition: scip.c:5655
static void calcNewSidesAfterAggregation(SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real coef, SCIP_Real *newlhs, SCIP_Real *newrhs)
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:45816
#define TRUE
Definition: def.h:63
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
static void getMultiaggVars(SCIP *scip, SCIP_MATRIX *matrix, SCIP_Bool *multiaggvars, int *nummultiaggvars, int *multiaggequalities, SCIP_Bool *consredundant, SCIP_Bool *lockedcons, SCIP_Bool *skipvars, int *maxactposhuge, int *maxactneghuge, int *minactposhuge, int *minactneghuge)
static SCIP_DECL_PRESOLCOPY(presolCopyImplfree)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45751
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:21937
SCIP_Real SCIPmatrixGetRowMaxActivity(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1465
#define SCIPdebugMsgPrint
Definition: scip.h:452
SCIP_RETCODE SCIPmatrixCreate(SCIP *scip, SCIP_MATRIX **matrixptr, SCIP_Bool *initialized, SCIP_Bool *complete)
Definition: matrix.c:430
#define SCIPdebugMsg
Definition: scip.h:451
#define PRESOL_PRIORITY
int SCIPgetNContVars(SCIP *scip)
Definition: scip.c:11811
int SCIPmatrixGetRowNNonzs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1373
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17176
SCIP_Real SCIPmatrixGetRowLhs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1407
SCIP_RETCODE SCIPmultiaggregateVar(SCIP *scip, SCIP_VAR *var, int naggvars, SCIP_VAR **aggvars, SCIP_Real *scalars, SCIP_Real constant, SCIP_Bool *infeasible, SCIP_Bool *aggregated)
Definition: scip.c:25384
SCIP_Real * SCIPmatrixGetColValPtr(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1233
int SCIPmatrixGetRowNMaxActPosInf(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1513
#define PRESOL_DESC
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:7881
int * SCIPmatrixGetRowIdxPtr(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1361
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16552
static SCIP_Real getMaxActSingleRowWithoutCol(SCIP *scip, SCIP_MATRIX *matrix, int row, int col)
SCIP_Bool SCIPisNLPEnabled(SCIP *scip)
Definition: scip.c:30797
exploit implied free variables for multi-aggregation
#define NULL
Definition: lpi_spx1.cpp:137
#define REALABS(x)
Definition: def.h:159
int SCIPmatrixGetRowNMaxActNegInf(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1501
#define PRESOL_NAME
#define SCIP_CALL(x)
Definition: def.h:306
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46112
SCIP_Real SCIPmatrixGetColLb(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1290
SCIP_Real * SCIPmatrixGetRowValPtr(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1349
SCIP_Real SCIPmatrixGetColUb(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1279
SCIP_RETCODE SCIPincludePresolImplfree(SCIP *scip)
SCIP_Bool SCIPisHugeValue(SCIP *scip, SCIP_Real val)
Definition: scip.c:45839
static SCIP_Bool isVarImpliedFree(SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Bool *lockedcons, int *impllbrowidx, int *implubrowidx)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:21925
static SCIP_Bool numericalStable(SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real aggrconst, int *maxactposhuge, int *maxactneghuge, int *minactposhuge, int *minactneghuge)
#define SCIP_Bool
Definition: def.h:61
#define MAX(x, y)
Definition: tclique_def.h:75
int * SCIPmatrixGetColIdxPtr(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1245
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
Definition: presol.c:553
static void getActivityRelax(SCIP *scip, SCIP_MATRIX *matrix, int row, int col, SCIP_Real val, int *maxactposhuge, int *maxactneghuge, int *minactposhuge, int *minactneghuge, SCIP_Bool *minisrelax, SCIP_Bool *maxisrelax)
int SCIPmatrixGetRowNMinActNegInf(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1477
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:45827
public methods for matrix
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip.c:35033
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11631
#define MAXABSRATIO
static const SCIP_Real scalars[]
Definition: lp.c:5563
SCIP_Real SCIPmatrixGetRowRhs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1419
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLCOPY((*presolcopy)))
Definition: scip.c:6889
static SCIP_Real getFillIn(SCIP_MATRIX *matrix, int col, int row)
#define SCIP_Real
Definition: def.h:135
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1138
#define PRESOL_MAXROUNDS
SCIP_Real SCIPmatrixGetRowMinActivity(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1453
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16717
int SCIPmatrixGetRowNMinActPosInf(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1489
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45777
static SCIP_Real getMinActSingleRowWithoutCol(SCIP *scip, SCIP_MATRIX *matrix, int row, int col)
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:85
int SCIPmatrixGetNColumns(SCIP_MATRIX *matrix)
Definition: matrix.c:1269
static void getVarBoundsOfRow(SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real val, SCIP_Real *rowlb, SCIP_Bool *lbfound, SCIP_Real *rowub, SCIP_Bool *ubfound)
int SCIPmatrixGetColNNonzs(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1257