Scippy

SCIP

Solving Constraint Integer Programs

presol_dualinfer.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_dualinfer.c
17  * @ingroup PRESOLVERS
18  * @brief dual inference presolver
19  * @author Dieter Weninger
20  *
21  * This presolver does bound strengthening on continuous variables
22  * for getting better bounds on dual variables y. The bounds on the dual
23  * variables are then used to derive variable fixings or side changes.
24  * We distinguish two cases:
25  * i) positive reduced costs: c_j - sup{A_{.j}^T y} > 0 => x_j = l_j
26  * ii) positive dual lower bound: y_i > 0 => A_{i.}x = b_i
27  */
28 
29 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
30 
31 #include <stdio.h>
32 #include <assert.h>
33 #include <string.h>
34 
35 #include "scip/pub_matrix.h"
36 #include "scip/cons_linear.h"
37 #include "presol_dualinfer.h"
38 
39 #define PRESOL_NAME "dualinfer"
40 #define PRESOL_DESC "exploit dual informations for fixings and side changes"
41 #define PRESOL_PRIORITY -2000 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */
42 #define PRESOL_MAXROUNDS 0 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
43 #define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */
44 #define MAX_LOOPS 3 /**< maximal number of dual bound strengthening loops */
45 
46 
47 /*
48  * Data structures
49  */
50 
51 
52 /** type of fixing direction */
54 {
55  FIXATLB = -1,
56  NOFIX = 0
57 };
59 
60 /** type of side change */
62 {
63  RHSTOLHS = -1,
64  NOCHANGE = 0,
66 };
67 typedef enum SideChange SIDECHANGE;
68 
69 
70 /*
71  * Local methods
72  */
73 
74 /** calculate max activity of one row without one column */
75 static
77  SCIP* scip, /**< SCIP main data structure */
78  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
79  int row, /**< row index */
80  int col /**< column index */
81  )
82 {
83  int c;
84  SCIP_Real val;
85  int* rowpnt;
86  int* rowend;
87  SCIP_Real* valpnt;
88  SCIP_Real maxactivity;
89  SCIP_Real lb;
90  SCIP_Real ub;
91 
92  assert(scip != NULL);
93  assert(matrix != NULL);
94 
95  maxactivity = 0;
96 
97  rowpnt = SCIPmatrixGetRowIdxPtr(matrix, row);
98  rowend = rowpnt + SCIPmatrixGetRowNNonzs(matrix, row);
99  valpnt = SCIPmatrixGetRowValPtr(matrix, row);
100 
101  for(; (rowpnt < rowend); rowpnt++, valpnt++)
102  {
103  c = *rowpnt;
104  val = *valpnt;
105 
106  if( c == col )
107  continue;
108 
109  if( val > 0.0 )
110  {
111  ub = SCIPmatrixGetColUb(matrix, c);
112  assert(!SCIPisInfinity(scip, ub));
113  maxactivity += val * ub;
114  }
115  else if( val < 0.0 )
116  {
117  lb = SCIPmatrixGetColLb(matrix, c);
118  assert(!SCIPisInfinity(scip, -lb));
119  maxactivity += val * lb;
120  }
121  }
122 
123  return maxactivity;
124 }
125 
126 /** calculate min activity of one row without one column */
127 static
129  SCIP* scip, /**< SCIP main data structure */
130  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
131  int row, /**< row index */
132  int col /**< column index */
133  )
134 {
135  int c;
136  SCIP_Real val;
137  int* rowpnt;
138  int* rowend;
139  SCIP_Real* valpnt;
140  SCIP_Real minactivity;
141  SCIP_Real lb;
142  SCIP_Real ub;
143 
144  assert(scip != NULL);
145  assert(matrix != NULL);
146 
147  minactivity = 0;
148 
149  rowpnt = SCIPmatrixGetRowIdxPtr(matrix, row);
150  rowend = rowpnt + SCIPmatrixGetRowNNonzs(matrix, row);
151  valpnt = SCIPmatrixGetRowValPtr(matrix, row);
152 
153  for(; (rowpnt < rowend); rowpnt++, valpnt++)
154  {
155  c = *rowpnt;
156  val = *valpnt;
157 
158  if( c == col )
159  continue;
160 
161  if( val > 0.0 )
162  {
163  lb = SCIPmatrixGetColLb(matrix, c);
164  assert(!SCIPisInfinity(scip, -lb));
165  minactivity += val * lb;
166  }
167  else if( val < 0.0 )
168  {
169  ub = SCIPmatrixGetColUb(matrix, c);
170  assert(!SCIPisInfinity(scip, ub));
171  minactivity += val * ub;
172  }
173  }
174 
175  return minactivity;
176 }
177 
178 /** get min/max residual activity without the specified column */
179 static
181  SCIP* scip, /**< SCIP main data structure */
182  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
183  int col, /**< column index */
184  int row, /**< row index */
185  SCIP_Real val, /**< coefficient of this variable in this row */
186  SCIP_Real* minresactivity, /**< minimum residual activity of this row */
187  SCIP_Real* maxresactivity, /**< maximum residual activity of this row */
188  SCIP_Bool* isminsettoinfinity, /**< flag indicating if minresactiviy is set to infinity */
189  SCIP_Bool* ismaxsettoinfinity /**< flag indicating if maxresactiviy is set to infinity */
190  )
191 {
192  SCIP_Real lb;
193  SCIP_Real ub;
194  int nmaxactneginf;
195  int nmaxactposinf;
196  int nminactneginf;
197  int nminactposinf;
198  SCIP_Real maxactivity;
199  SCIP_Real minactivity;
200 
201  assert(scip != NULL);
202  assert(matrix != NULL);
203  assert(minresactivity != NULL);
204  assert(maxresactivity != NULL);
205  assert(isminsettoinfinity != NULL);
206  assert(ismaxsettoinfinity != NULL);
207 
208  lb = SCIPmatrixGetColLb(matrix, col);
209  ub = SCIPmatrixGetColUb(matrix, col);
210 
211  *isminsettoinfinity = FALSE;
212  *ismaxsettoinfinity = FALSE;
213 
214  nmaxactneginf = SCIPmatrixGetRowNMaxActNegInf(matrix, row);
215  nmaxactposinf = SCIPmatrixGetRowNMaxActPosInf(matrix, row);
216  nminactneginf = SCIPmatrixGetRowNMinActNegInf(matrix, row);
217  nminactposinf = SCIPmatrixGetRowNMinActPosInf(matrix, row);
218 
219  maxactivity = SCIPmatrixGetRowMaxActivity(matrix, row);
220  minactivity = SCIPmatrixGetRowMinActivity(matrix, row);
221 
222  if( val >= 0.0 )
223  {
224  if( SCIPisInfinity(scip, ub) )
225  {
226  assert(nmaxactposinf >= 1);
227  if( nmaxactposinf == 1 && nmaxactneginf == 0 )
228  *maxresactivity = getMaxActivitySingleRowWithoutCol(scip, matrix, row, col);
229  else
230  {
231  *maxresactivity = SCIPinfinity(scip);
232  *ismaxsettoinfinity = TRUE;
233  }
234  }
235  else
236  {
237  if( (nmaxactneginf + nmaxactposinf) > 0 )
238  {
239  *maxresactivity = SCIPinfinity(scip);
240  *ismaxsettoinfinity = TRUE;
241  }
242  else
243  *maxresactivity = maxactivity - val * ub;
244  }
245 
246  if( SCIPisInfinity(scip, -lb) )
247  {
248  assert(nminactneginf >= 1);
249  if( nminactneginf == 1 && nminactposinf == 0 )
250  *minresactivity = getMinActivitySingleRowWithoutCol(scip, matrix, row, col);
251  else
252  {
253  *minresactivity = -SCIPinfinity(scip);
254  *isminsettoinfinity = TRUE;
255  }
256  }
257  else
258  {
259  if( (nminactneginf + nminactposinf) > 0 )
260  {
261  *minresactivity = -SCIPinfinity(scip);
262  *isminsettoinfinity = TRUE;
263  }
264  else
265  *minresactivity = minactivity - val * lb;
266  }
267  }
268  else
269  {
270  if( SCIPisInfinity(scip, -lb) )
271  {
272  assert(nmaxactneginf >= 1);
273  if( nmaxactneginf == 1 && nmaxactposinf == 0 )
274  *maxresactivity = getMaxActivitySingleRowWithoutCol(scip, matrix, row, col);
275  else
276  {
277  *maxresactivity = SCIPinfinity(scip);
278  *ismaxsettoinfinity = TRUE;
279  }
280  }
281  else
282  {
283  if( (nmaxactneginf + nmaxactposinf) > 0 )
284  {
285  *maxresactivity = SCIPinfinity(scip);
286  *ismaxsettoinfinity = TRUE;
287  }
288  else
289  *maxresactivity = maxactivity - val * lb;
290  }
291 
292  if( SCIPisInfinity(scip, ub) )
293  {
294  assert(nminactposinf >= 1);
295  if( nminactposinf == 1 && nminactneginf == 0 )
296  *minresactivity = getMinActivitySingleRowWithoutCol(scip, matrix, row, col);
297  else
298  {
299  *minresactivity = -SCIPinfinity(scip);
300  *isminsettoinfinity = TRUE;
301  }
302  }
303  else
304  {
305  if( (nminactneginf + nminactposinf) > 0 )
306  {
307  *minresactivity = -SCIPinfinity(scip);
308  *isminsettoinfinity = TRUE;
309  }
310  else
311  *minresactivity = minactivity - val * ub;
312  }
313  }
314 }
315 
316 /** calculate the upper bound of one variable from one row */
317 static
319  SCIP* scip, /**< SCIP main data structure */
320  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
321  int col, /**< column index of variable */
322  int row, /**< row index */
323  SCIP_Real val, /**< coefficient of this column in this row */
324  SCIP_Real* rowub, /**< upper bound of row */
325  SCIP_Bool* ubfound /**< flag indicating that an upper bound was calculated */
326  )
327 {
328  SCIP_Bool isminsettoinfinity;
329  SCIP_Bool ismaxsettoinfinity;
330  SCIP_Real minresactivity;
331  SCIP_Real maxresactivity;
332  SCIP_Real lhs;
333  SCIP_Real rhs;
334 
335  assert(rowub != NULL);
336  assert(ubfound != NULL);
337 
338  *rowub = SCIPinfinity(scip);
339  *ubfound = FALSE;
340 
341  getMinMaxActivityResiduals(scip, matrix, col, row, val, &minresactivity, &maxresactivity,
342  &isminsettoinfinity, &ismaxsettoinfinity);
343 
344  lhs = SCIPmatrixGetRowLhs(matrix, row);
345  rhs = SCIPmatrixGetRowRhs(matrix, row);
346 
347  if( val > 0.0 )
348  {
349  if( !isminsettoinfinity && !SCIPisInfinity(scip, rhs) )
350  {
351  *rowub = (rhs - minresactivity)/val;
352  *ubfound = TRUE;
353  }
354  }
355  else
356  {
357  if( !ismaxsettoinfinity && !SCIPisInfinity(scip, -lhs) )
358  {
359  *rowub = (lhs - maxresactivity)/val;
360  *ubfound = TRUE;
361  }
362  }
363 }
364 
365 
366 /** verify which variable upper bounds are implied */
367 static
369  SCIP* scip, /**< SCIP main data structure */
370  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
371  int col /**< column index for implied free test */
372  )
373 {
374  SCIP_Real varub;
375  SCIP_Real impliedub;
376  int* colpnt;
377  int* colend;
378  SCIP_Real* valpnt;
379  SCIP_Bool ubimplied;
380 
381  assert(scip != NULL);
382  assert(matrix != NULL);
383 
384  ubimplied = FALSE;
385  impliedub = SCIPinfinity(scip);
386 
387  colpnt = SCIPmatrixGetColIdxPtr(matrix, col);
388  colend = colpnt + SCIPmatrixGetColNNonzs(matrix, col);
389  valpnt = SCIPmatrixGetColValPtr(matrix, col);
390 
391  for( ; (colpnt < colend); colpnt++, valpnt++ )
392  {
393  SCIP_Real rowub;
394  SCIP_Bool ubfound;
395 
396  getVarUpperBoundOfRow(scip, matrix, col, *colpnt, *valpnt, &rowub, &ubfound);
397 
398  if( ubfound && (rowub < impliedub) )
399  impliedub = rowub;
400  }
401 
402  varub = SCIPmatrixGetColUb(matrix, col);
403 
404  if( !SCIPisInfinity(scip, varub) && SCIPisFeasLE(scip, impliedub, varub) )
405  ubimplied = TRUE;
406 
407  return ubimplied;
408 }
409 
410 
411 /** calculate minimal column activity from one continuous variable without one row */
412 static
414  SCIP* scip, /**< SCIP main data structure */
415  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
416  int col, /**< column index */
417  int withoutrow, /**< exclude row index */
418  SCIP_Real* lbdual[2], /**< lower bounds of dual variables */
419  SCIP_Real* ubdual[2], /**< upper bounds of dual variables */
420  int part /**< which of part of the dual variables is active */
421  )
422 {
423  SCIP_Real* valpnt;
424  int* colpnt;
425  int* colend;
426  SCIP_Real val;
427  SCIP_Real mincolactivity;
428  int row;
429  int p;
430 
431  assert(scip != NULL);
432  assert(matrix != NULL);
433  assert(lbdual[0] != NULL);
434  assert(ubdual[0] != NULL);
435  assert(lbdual[1] != NULL);
436  assert(ubdual[1] != NULL);
437 
438  mincolactivity = 0;
439  colpnt = SCIPmatrixGetColIdxPtr(matrix, col);
440  colend = colpnt + SCIPmatrixGetColNNonzs(matrix, col);
441  valpnt = SCIPmatrixGetColValPtr(matrix, col);
442 
443  for( ; colpnt < colend; colpnt++, valpnt++ )
444  {
445  row = *colpnt;
446  val = *valpnt;
447 
448  if( row == withoutrow )
449  {
450  if( SCIPmatrixIsRowRhsInfinity(matrix, row) )
451  continue;
452 
453  /* treat remaining part of equalities or ranged rows */
454  if( part == 0 )
455  {
456  /* consider second part */
457  val = -val;
458  p = 1;
459  }
460  else
461  {
462  /* consider first part */
463  p = 0;
464  }
465 
466  if( val > 0.0 )
467  {
468  assert(!SCIPisInfinity(scip, -lbdual[p][row]));
469  mincolactivity += val * lbdual[p][row];
470  }
471  else if( val < 0.0 )
472  {
473  assert(!SCIPisInfinity(scip, ubdual[p][row]));
474  mincolactivity += val * ubdual[p][row];
475  }
476  }
477  else
478  {
479  p = 0;
480 
481  do
482  {
483  if( val > 0.0 )
484  {
485  assert(!SCIPisInfinity(scip, -lbdual[p][row]));
486  mincolactivity += val * lbdual[p][row];
487  }
488  else if( val < 0.0 )
489  {
490  assert(!SCIPisInfinity(scip, ubdual[p][row]));
491  mincolactivity += val * ubdual[p][row];
492  }
493 
494  val = -val;
495  p++;
496  }
497  while ( !SCIPmatrixIsRowRhsInfinity(matrix, row) && p < 2 );
498  }
499  }
500 
501  return mincolactivity;
502 }
503 
504 
505 /** calculate minimal/maximal column residual activities */
506 static
508  SCIP* scip, /**< SCIP main data structure */
509  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
510  int col, /**< column index */
511  int row, /**< row index */
512  SCIP_Real val, /**< matrix coefficient */
513  SCIP_Real* lbdual[2], /**< lower bounds of dual variables */
514  SCIP_Real* ubdual[2], /**< upper bounds of dual variables */
515  int part, /**< which of part of the dual variables is active */
516  SCIP_Real* mincolact, /**< minimal column activities */
517  int* mincolactinf, /**< number of (negative) infinite contributions to minimal column activity */
518  SCIP_Real* mincolresact /**< minimal column residual activity */
519  )
520 {
521  assert(scip != NULL);
522  assert(matrix != NULL);
523  assert(lbdual[0] != NULL);
524  assert(ubdual[0] != NULL);
525  assert(lbdual[1] != NULL);
526  assert(ubdual[1] != NULL);
527  assert(mincolact != NULL);
528  assert(mincolactinf != NULL);
529  assert(mincolresact != NULL);
530 
531  if( !SCIPmatrixIsRowRhsInfinity(matrix, row) && part == 1 )
532  val = -val;
533 
534  if( val > 0.0 )
535  {
536  if( SCIPisInfinity(scip, -lbdual[part][row]) )
537  {
538  assert(mincolactinf[col] >= 1);
539  if( mincolactinf[col] == 1 )
540  *mincolresact = getMinColActWithoutRow(scip, matrix, col, row, lbdual, ubdual, part);
541  else
542  *mincolresact = -SCIPinfinity(scip);
543  }
544  else
545  {
546  if( mincolactinf[col] > 0 )
547  *mincolresact = -SCIPinfinity(scip);
548  else
549  *mincolresact = mincolact[col] - val * lbdual[part][row];
550  }
551  }
552  else if( val < 0.0 )
553  {
554  if( SCIPisInfinity(scip, ubdual[part][row]) )
555  {
556  assert(mincolactinf[col] >= 1);
557  if( mincolactinf[col] == 1 )
558  *mincolresact = getMinColActWithoutRow(scip, matrix, col, row, lbdual, ubdual, part);
559  else
560  *mincolresact = -SCIPinfinity(scip);
561  }
562  else
563  {
564  if( mincolactinf[col] > 0 )
565  *mincolresact = -SCIPinfinity(scip);
566  else
567  *mincolresact = mincolact[col] - val * ubdual[part][row];
568  }
569  }
570 }
571 
572 
573 /** calculate minimal/maximal column activities */
574 static
576  SCIP* scip, /**< SCIP main data structure */
577  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
578  SCIP_Bool onlyconvars, /**< consider only continuous variables for activity calculation */
579  int startcol, /**< start column for activity calculations */
580  int stopcol, /**< stop column for activity calculations */
581  SCIP_Real* lbdual[2], /**< lower bounds of dual variables */
582  SCIP_Real* ubdual[2], /**< upper bounds of dual variables */
583  SCIP_Real* mincolact, /**< minimal column activities */
584  SCIP_Real* maxcolact, /**< maximal column activities */
585  int* maxcolactinf, /**< number of (positive) infinite contributions to maximal column activity */
586  int* mincolactinf, /**< number of (negative) infinite contributions to minimal column activity */
587  SCIP_Bool* isimplfree /**< is upper bound of variable implied */
588  )
589 {
590  SCIP_VAR* var;
591  SCIP_Real* valpnt;
592  int* colpnt;
593  int* colend;
594  SCIP_Real val;
595  int row;
596  int c;
597 
598  assert(scip != NULL);
599  assert(matrix != NULL);
600  assert(lbdual[0] != NULL);
601  assert(ubdual[0] != NULL);
602  assert(lbdual[1] != NULL);
603  assert(ubdual[1] != NULL);
604  assert(mincolact != NULL);
605  assert(maxcolact != NULL);
606  assert(maxcolactinf != NULL);
607  assert(mincolactinf != NULL);
608 
609  for( c = startcol; c < stopcol; c++ )
610  {
611  var = SCIPmatrixGetVar(matrix, c);
612 
613  if( onlyconvars )
614  {
615  /* exclude non-continuous variables for bound calculation */
617  {
618  mincolact[c] = -SCIPinfinity(scip);
619  maxcolact[c] = SCIPinfinity(scip);
620  maxcolactinf[c] = 1;
621  mincolactinf[c] = 1;
622  continue;
623  }
624  }
625 
626  /* exclude some bound cases for activity calculation */
627  if( SCIPisInfinity(scip, -SCIPvarGetLbGlobal(var)) ||
628  !(isimplfree[c] || SCIPisInfinity(scip, SCIPvarGetUbGlobal(var))) )
629  {
630  mincolact[c] = -SCIPinfinity(scip);
631  maxcolact[c] = SCIPinfinity(scip);
632  maxcolactinf[c] = 1;
633  mincolactinf[c] = 1;
634  continue;
635  }
636 
637  /* init activities */
638  mincolact[c] = 0;
639  maxcolact[c] = 0;
640  maxcolactinf[c] = 0;
641  mincolactinf[c] = 0;
642 
643  colpnt = SCIPmatrixGetColIdxPtr(matrix, c);
644  colend = colpnt + SCIPmatrixGetColNNonzs(matrix, c);
645  valpnt = SCIPmatrixGetColValPtr(matrix, c);
646 
647  /* calculate column activities */
648  for( ; colpnt < colend; colpnt++, valpnt++ )
649  {
650  row = *colpnt;
651  val = *valpnt;
652 
653  /* consider >= inequalities */
654  if( val > 0 )
655  {
656  if(SCIPisInfinity(scip, ubdual[0][row]))
657  maxcolactinf[c]++;
658  else
659  maxcolact[c] += val * ubdual[0][row];
660 
661  if(SCIPisInfinity(scip, -lbdual[0][row]))
662  mincolactinf[c]++;
663  else
664  mincolact[c] += val * lbdual[0][row];
665  }
666  else if( val < 0.0 )
667  {
668  if(SCIPisInfinity(scip, -lbdual[0][row]))
669  maxcolactinf[c]++;
670  else
671  maxcolact[c] += val * lbdual[0][row];
672 
673  if(SCIPisInfinity(scip, ubdual[0][row]))
674  mincolactinf[c]++;
675  else
676  mincolact[c] += val * ubdual[0][row];
677  }
678 
679  /* consider equations and ranged rows */
680  if( !SCIPmatrixIsRowRhsInfinity(matrix, row) )
681  {
682  val = -val;
683  if( val > 0 )
684  {
685  if(SCIPisInfinity(scip, ubdual[1][row]))
686  maxcolactinf[c]++;
687  else
688  maxcolact[c] += val * ubdual[1][row];
689 
690  if(SCIPisInfinity(scip, -lbdual[1][row]))
691  mincolactinf[c]++;
692  else
693  mincolact[c] += val * lbdual[1][row];
694  }
695  else if( val < 0.0 )
696  {
697  if(SCIPisInfinity(scip, -lbdual[1][row]))
698  maxcolactinf[c]++;
699  else
700  maxcolact[c] += val * lbdual[1][row];
701 
702  if(SCIPisInfinity(scip, ubdual[1][row]))
703  mincolactinf[c]++;
704  else
705  mincolact[c] += val * ubdual[1][row];
706  }
707  }
708  }
709 
710  /* update column activities if infinity counters are greater 0 */
711  if( mincolactinf[c] > 0 )
712  mincolact[c] = -SCIPinfinity(scip);
713  if( maxcolactinf[c] > 0 )
714  maxcolact[c] = SCIPinfinity(scip);
715  }
716 }
717 
718 
719 /** update bounds on dual variables */
720 static
722  SCIP* scip, /**< SCIP main data structure */
723  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
724  SCIP_Real objval, /**< objective function value */
725  SCIP_Real val, /**< matrix coefficient */
726  int row, /**< row index */
727  SCIP_Real mincolresact, /**< minimal column residual activity */
728  SCIP_Real* lbdual[2], /**< dual lower bounds (ranged, equality) */
729  SCIP_Real* ubdual[2], /**< dual upper bounds (ranged, equatity)*/
730  int part, /**< which of part of the dual variables is active */
731  int* boundchanges, /**< number of bound changes */
732  SCIP_Bool* updateinfcnt /**< flag indicating to update infinity counters */
733  )
734 {
735  SCIP_Real newlbdual;
736  SCIP_Real newubdual;
737 
738  assert(scip != NULL);
739  assert(matrix != NULL);
740  assert(lbdual[0] != NULL);
741  assert(ubdual[0] != NULL);
742  assert(lbdual[1] != NULL);
743  assert(ubdual[1] != NULL);
744  assert(boundchanges != NULL);
745  assert(updateinfcnt != NULL);
746 
747  *updateinfcnt = FALSE;
748 
749  /* return if minimal residual activity is infinite */
750  if( SCIPisInfinity(scip, mincolresact) || SCIPisInfinity(scip, -mincolresact) )
751  return;
752 
753  if( !SCIPmatrixIsRowRhsInfinity(matrix, row) && part == 1 )
754  val = -val;
755 
756  if( val > 0 )
757  {
758  newubdual = (objval - mincolresact) / val;
759  assert(SCIPisGE(scip, newubdual, 0.0));
760 
761  if( newubdual < ubdual[part][row] )
762  {
763  if( SCIPisInfinity(scip, ubdual[part][row]) )
764  *updateinfcnt = TRUE;
765 
766  ubdual[part][row] = newubdual;
767  (*boundchanges)++;
768  }
769  }
770  else if( val < 0 )
771  {
772  newlbdual = (objval - mincolresact) / val;
773  assert(SCIPisGE(scip, ubdual[part][row], newlbdual));
774 
775  if( newlbdual > lbdual[part][row] )
776  {
777  if( SCIPisInfinity(scip, -lbdual[part][row]) )
778  *updateinfcnt = TRUE;
779 
780  lbdual[part][row] = newlbdual;
781  (*boundchanges)++;
782  }
783  }
784 }
785 
786 
787 /** update minimal/maximal column activity infinity counters */
788 static
790  SCIP* scip, /**< SCIP main data structure */
791  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
792  SCIP_Real val, /**< matrix coefficient */
793  int row, /**< row index */
794  SCIP_Real* lbdual[2], /**< lower bounds of dual variables */
795  SCIP_Real* ubdual[2], /**< upper bounds of dual variables */
796  int part, /**< which part of the dual variables is active */
797  SCIP_Real* mincolact, /**< minimal column activities */
798  SCIP_Real* maxcolact, /**< maximal column activities */
799  int* maxcolactinf, /**< number of (positive) infinity contributions to maximal column activity */
800  int* mincolactinf, /**< number of (negative) infinity contributions to minimal column activity */
801  SCIP_Bool* isimplfree /**< is upper bound of variable implied */
802  )
803 {
804  SCIP_Real* valpnt;
805  int* rowpnt;
806  int* rowend;
807  SCIP_Real aij;
808  int c;
809  SCIP_VAR* var;
810 
811  assert(scip != NULL);
812  assert(matrix != NULL);
813  assert(lbdual[0] != NULL);
814  assert(ubdual[0] != NULL);
815  assert(lbdual[1] != NULL);
816  assert(ubdual[1] != NULL);
817  assert(mincolact != NULL);
818  assert(maxcolact != NULL);
819  assert(maxcolactinf != NULL);
820  assert(mincolactinf != NULL);
821 
822  rowpnt = SCIPmatrixGetRowIdxPtr(matrix, row);
823  rowend = rowpnt + SCIPmatrixGetRowNNonzs(matrix, row);
824  valpnt = SCIPmatrixGetRowValPtr(matrix, row);
825 
826  if( !SCIPmatrixIsRowRhsInfinity(matrix, row) && part == 1 )
827  val = -val;
828 
829  /* look at all column entries present within row and update the
830  * corresponding infinity counters. if one counter gets to zero,
831  * then calculate this column activity new.
832  */
833  if( val > 0 )
834  {
835  /* finite upper bound change */
836  for(; (rowpnt < rowend); rowpnt++, valpnt++ )
837  {
838  c = *rowpnt;
839  var = SCIPmatrixGetVar(matrix, c);
840 
842  SCIPisInfinity(scip, -SCIPvarGetLbGlobal(var)))
843  continue;
844 
845  aij = *valpnt;
846 
847  if( aij < 0 )
848  {
849  assert(mincolactinf[c] > 0);
850  mincolactinf[c]--;
851 
852  if( mincolactinf[c] == 0 )
853  calcColActivity(scip, matrix, TRUE, c, c+1, lbdual, ubdual,
854  mincolact, maxcolact,
855  maxcolactinf, mincolactinf, isimplfree);
856  }
857  }
858  }
859  else if( val < 0 )
860  {
861  /* finite lower bound change */
862  for(; (rowpnt < rowend); rowpnt++, valpnt++ )
863  {
864  c = *rowpnt;
865  var = SCIPmatrixGetVar(matrix, c);
866 
868  SCIPisInfinity(scip, -SCIPvarGetLbGlobal(var)))
869  continue;
870 
871  aij = *valpnt;
872 
873  if( aij > 0 )
874  {
875  assert(mincolactinf[c] > 0);
876  mincolactinf[c]--;
877 
878  if( mincolactinf[c] == 0 )
879  calcColActivity(scip, matrix, TRUE, c, c+1, lbdual, ubdual,
880  mincolact, maxcolact,
881  maxcolactinf, mincolactinf, isimplfree);
882  }
883  }
884  }
885 }
886 
887 
888 /** dual bound strengthening */
889 static
891  SCIP* scip, /**< SCIP main data structure */
892  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
893  FIXINGDIRECTION* varstofix, /**< array holding information for later upper/lower bound fixing */
894  int* npossiblefixings, /**< number of possible fixings */
895  SIDECHANGE* sidestochange, /**< array holding if this is an implied equality */
896  int* npossiblesidechanges/**< number of possible equality changes */
897  )
898 {
899  SCIP_Real* valpnt;
900  SCIP_Real* lbdual[2];
901  SCIP_Real* ubdual[2];
902  SCIP_Real* mincolact;
903  SCIP_Real* maxcolact;
904  int* maxcolactinf;
905  int* mincolactinf;
906  int* colpnt;
907  int* colend;
908  int boundchanges;
909  int loops;
910  int c;
911  int r;
912  int nrows;
913  int ncols;
914  SCIP_Bool* isubimplied;
915 
916  assert(scip != NULL);
917  assert(matrix != NULL);
918  assert(varstofix != NULL);
919  assert(npossiblefixings != NULL);
920  assert(sidestochange != NULL);
921  assert(npossiblesidechanges != NULL);
922 
923  nrows = SCIPmatrixGetNRows(matrix);
924  ncols = SCIPmatrixGetNColumns(matrix);
925 
926  SCIP_CALL( SCIPallocBufferArray(scip, &mincolact, ncols) );
927  SCIP_CALL( SCIPallocBufferArray(scip, &maxcolact, ncols) );
928  SCIP_CALL( SCIPallocBufferArray(scip, &maxcolactinf, ncols) );
929  SCIP_CALL( SCIPallocBufferArray(scip, &mincolactinf, ncols) );
930  SCIP_CALL( SCIPallocBufferArray(scip, &(lbdual[0]), nrows) );
931  SCIP_CALL( SCIPallocBufferArray(scip, &(ubdual[0]), nrows) );
932  SCIP_CALL( SCIPallocBufferArray(scip, &(lbdual[1]), nrows) );
933  SCIP_CALL( SCIPallocBufferArray(scip, &(ubdual[1]), nrows) );
934  SCIP_CALL( SCIPallocBufferArray(scip, &isubimplied, ncols) );
935 
936  for( c = 0; c < ncols; c++ )
937  {
938  if( isUpperBoundImplied(scip,matrix,c) )
939  isubimplied[c] = TRUE;
940  else
941  isubimplied[c] = FALSE;
942  }
943 
944  /* initialize bounds of dual variables */
945  for( r = 0; r < nrows; r++ )
946  {
947  /* >= inequalities */
948  lbdual[0][r] = 0.0;
949  ubdual[0][r] = SCIPinfinity(scip);
950 
951  /* additional dual variable for equalities and ranged rows */
952  lbdual[1][r] = 0.0;
953  ubdual[1][r] = SCIPinfinity(scip);
954  }
955 
956  loops = 0;
957  boundchanges = 1;
958 
959  while( boundchanges && loops < MAX_LOOPS )
960  {
961  loops++;
962  boundchanges = 0;
963 
964  calcColActivity(scip, matrix, TRUE, 0, ncols, lbdual, ubdual,
965  mincolact, maxcolact, maxcolactinf, mincolactinf, isubimplied);
966 
967  for( c = 0 ; c < ncols; c++ )
968  {
969  SCIP_Real objval;
970  SCIP_Real mincolresact;
971  SCIP_Bool updateinfcnt;
972  SCIP_VAR* var;
973 
974  var = SCIPmatrixGetVar(matrix, c);
975 
976  /* consider only continuous variables and certain bound cases */
978  SCIPisInfinity(scip, -SCIPvarGetLbGlobal(var)) ||
979  !(isubimplied[c] || SCIPisInfinity(scip, SCIPvarGetUbGlobal(var))))
980  continue;
981 
982  objval = SCIPvarGetObj(var);
983  colpnt = SCIPmatrixGetColIdxPtr(matrix, c);
984  colend = colpnt + SCIPmatrixGetColNNonzs(matrix, c);
985  valpnt = SCIPmatrixGetColValPtr(matrix, c);
986  mincolresact = -SCIPinfinity(scip);
987 
988  for( ; colpnt < colend; colpnt++, valpnt++ )
989  {
990  int row;
991  SCIP_Real val;
992  int part;
993 
994  row = *colpnt;
995  val = *valpnt;
996  mincolresact = -SCIPinfinity(scip);
997 
998  part = 0;
999 
1000  do
1001  {
1002  /* calulate column activity residuals */
1003  calcColActResidual(scip, matrix, c, row, val, lbdual, ubdual,
1004  part, mincolact, mincolactinf, &mincolresact);
1005 
1006  /* update dual bounds */
1007  updateDualBounds(scip, matrix, objval, val, row, mincolresact,
1008  lbdual, ubdual, part, &boundchanges, &updateinfcnt);
1009 
1010  /* update infinity counters if bound changed properly */
1011  if( updateinfcnt )
1012  infCntUpdate(scip, matrix, val, row, lbdual, ubdual, part,
1013  mincolact, maxcolact, maxcolactinf, mincolactinf, isubimplied);
1014 
1015  part++;
1016  }
1017  while( !SCIPmatrixIsRowRhsInfinity(matrix, row) && part < 2 );
1018  }
1019  }
1020  }
1021 
1022  /* calculate minimal/maximal column activity over all columns */
1023  calcColActivity(scip, matrix, FALSE, 0, ncols, lbdual, ubdual,
1024  mincolact, maxcolact, maxcolactinf, mincolactinf, isubimplied);
1025 
1026  for( c = 0; c < ncols; c++ )
1027  {
1028  SCIP_Real objval;
1029  SCIP_VAR* var;
1030 
1031  var = SCIPmatrixGetVar(matrix, c);
1032  objval = SCIPvarGetObj(var);
1033 
1034  /* positive reduced costs: c_j - sup{(A_{.j})^T}y > 0 => x_j = 0 */
1035  if( SCIPisLT(scip, maxcolact[c], objval) && varstofix[c] == NOFIX )
1036  {
1037  varstofix[c] = FIXATLB;
1038  (*npossiblefixings)++;
1039  }
1040  }
1041 
1042  for( r = 0; r < nrows; r++ )
1043  {
1044  /* implied equality: y_i > 0 => A_{.i}x - b_i = 0 */
1045  if( SCIPmatrixIsRowRhsInfinity(matrix, r) )
1046  {
1047  if( SCIPisGT(scip, lbdual[0][r], 0.0) )
1048  {
1049  /* change >= inequality to equality */
1050  sidestochange[r] = RHSTOLHS;
1051  (*npossiblesidechanges)++;
1052  }
1053  }
1054  else
1055  {
1056  if( !SCIPmatrixIsRowRhsInfinity(matrix, r) &&
1057  !SCIPisEQ(scip,SCIPmatrixGetRowLhs(matrix, r),SCIPmatrixGetRowRhs(matrix, r)) )
1058  {
1059  /* for ranged rows we have to decide which side determines the equality */
1060  if( SCIPisGT(scip, lbdual[0][r], 0.0) && !SCIPisGT(scip, lbdual[1][r], 0.0) && sidestochange[r]==NOCHANGE )
1061  {
1062  sidestochange[r] = RHSTOLHS;
1063  (*npossiblesidechanges)++;
1064  }
1065 
1066  if( !SCIPisGT(scip, lbdual[0][r], 0.0) && SCIPisGT(scip, lbdual[1][r], 0.0) && sidestochange[r]==NOCHANGE)
1067  {
1068  sidestochange[r] = LHSTORHS;
1069  (*npossiblesidechanges)++;
1070  }
1071  }
1072  }
1073  }
1074 
1075  SCIPfreeBufferArray(scip, &isubimplied);
1076  SCIPfreeBufferArray(scip, &ubdual[1]);
1077  SCIPfreeBufferArray(scip, &lbdual[1]);
1078  SCIPfreeBufferArray(scip, &ubdual[0]);
1079  SCIPfreeBufferArray(scip, &lbdual[0]);
1080  SCIPfreeBufferArray(scip, &mincolactinf);
1081  SCIPfreeBufferArray(scip, &maxcolactinf);
1082  SCIPfreeBufferArray(scip, &maxcolact);
1083  SCIPfreeBufferArray(scip, &mincolact);
1084 
1085  return SCIP_OKAY;
1086 }
1087 
1088 /*
1089  * Callback methods of presolver
1090  */
1091 
1092 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
1093 static
1094 SCIP_DECL_PRESOLCOPY(presolCopyDualinfer)
1095 { /*lint --e{715}*/
1096  assert(scip != NULL);
1097  assert(presol != NULL);
1098  assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
1099 
1100  /* call inclusion method of presolver */
1102 
1103  return SCIP_OKAY;
1104 }
1105 
1106 /** execution method of presolver */
1107 static
1108 SCIP_DECL_PRESOLEXEC(presolExecDualinfer)
1109 { /*lint --e{715}*/
1110  SCIP_MATRIX* matrix;
1111  SCIP_Bool initialized;
1112  SCIP_Bool complete;
1113 
1114  assert(result != NULL);
1115  *result = SCIP_DIDNOTRUN;
1116 
1118  return SCIP_OKAY;
1119 
1120  if( SCIPgetNContVars(scip)==0 )
1121  return SCIP_OKAY;
1122 
1123  if( !SCIPallowDualReds(scip) )
1124  return SCIP_OKAY;
1125 
1126  *result = SCIP_DIDNOTFIND;
1127 
1128  matrix = NULL;
1129  SCIP_CALL( SCIPmatrixCreate(scip, &matrix, &initialized, &complete) );
1130 
1131  if( initialized && complete )
1132  {
1133  FIXINGDIRECTION* varstofix;
1134  int npossiblefixings;
1135  int nconvarsfixed;
1136  int nintvarsfixed;
1137  int nbinvarsfixed;
1138  SIDECHANGE* sidestochange;
1139  int npossiblesidechanges;
1140  int nsideschanged;
1141  int i;
1142  int nrows;
1143  int ncols;
1144  SCIP_Bool locksconsistent;
1145  SCIP_VAR* var;
1146 
1147  npossiblefixings = 0;
1148  nconvarsfixed = 0;
1149  nintvarsfixed = 0;
1150  nbinvarsfixed = 0;
1151  npossiblesidechanges = 0;
1152  nsideschanged = 0;
1153  locksconsistent = TRUE;
1154 
1155  nrows = SCIPmatrixGetNRows(matrix);
1156  ncols = SCIPmatrixGetNColumns(matrix);
1157 
1158  /* the locks of the continuous variable must be consistent */
1159  for(i = 0; i < ncols; i++)
1160  {
1161  var = SCIPmatrixGetVar(matrix, i);
1163  {
1164  if( SCIPvarGetNLocksUp(var) != SCIPmatrixGetColNUplocks(matrix, i) ||
1166  {
1167  locksconsistent = FALSE;
1168  break;
1169  }
1170  }
1171  }
1172 
1173  if( locksconsistent )
1174  {
1175  SCIP_CALL( SCIPallocBufferArray(scip, &varstofix, ncols) );
1176  SCIP_CALL( SCIPallocBufferArray(scip, &sidestochange, nrows) );
1177 
1178  BMSclearMemoryArray(varstofix, ncols);
1179  BMSclearMemoryArray(sidestochange, nrows);
1180 
1181  SCIP_CALL( dualBoundStrengthening(scip, matrix, varstofix, &npossiblefixings, sidestochange, &npossiblesidechanges) );
1182 
1183  if( npossiblefixings > 0 )
1184  {
1185  for( i = ncols - 1; i >= 0; --i )
1186  {
1187  SCIP_Bool infeasible;
1188  SCIP_Bool fixed;
1189 
1190  if( varstofix[i] == FIXATLB )
1191  {
1192  SCIP_Real lb;
1193 
1194  var = SCIPmatrixGetVar(matrix, i);
1195 
1196  if( SCIPvarGetNLocksUp(var) != SCIPmatrixGetColNUplocks(matrix, i) ||
1198  {
1199  /* no fixing, locks for this variable not consistent */
1200  continue;
1201  }
1202 
1203  lb = SCIPvarGetLbLocal(var);
1204 
1205  /* fix at lower bound */
1206  SCIP_CALL( SCIPfixVar(scip, var, lb, &infeasible, &fixed) );
1207  if( infeasible )
1208  {
1209  SCIPdebugMsg(scip, " -> infeasible fixing\n");
1210  *result = SCIP_CUTOFF;
1211  break;
1212  }
1213  assert(fixed);
1214  (*nfixedvars)++;
1215  *result = SCIP_SUCCESS;
1216 
1218  nconvarsfixed++;
1219  else if( SCIPvarGetType(var) == SCIP_VARTYPE_BINARY )
1220  nbinvarsfixed++;
1221  else
1222  nintvarsfixed++;
1223  }
1224  }
1225  }
1226 
1227  if( npossiblesidechanges > 0 )
1228  {
1229  for( i = 0; i < nrows; i++ )
1230  {
1231  SCIP_CONS* cons;
1232  SCIP_CONSHDLR* conshdlr;
1233  const char* conshdlrname;
1234 
1235  if( sidestochange[i] == NOCHANGE )
1236  continue;
1237 
1238  cons = SCIPmatrixGetCons(matrix,i);
1239  conshdlr = SCIPconsGetHdlr(cons);
1240  conshdlrname = SCIPconshdlrGetName(conshdlr);
1241 
1242  /* TODO: implement further constraint types */
1243  if( strcmp(conshdlrname, "linear") == 0 )
1244  {
1245  SCIP_Real lhs;
1246  SCIP_Real rhs;
1247  SCIP_Real matrixlhs;
1248  SCIP_Real matrixrhs;
1249 
1250  lhs = SCIPgetLhsLinear(scip, cons);
1251  rhs = SCIPgetRhsLinear(scip, cons);
1252  matrixlhs = SCIPmatrixGetRowLhs(matrix, i);
1253  matrixrhs = SCIPmatrixGetRowRhs(matrix, i);
1254 
1255  if( sidestochange[i] == RHSTOLHS )
1256  {
1257  assert(!SCIPisEQ(scip, matrixlhs, matrixrhs));
1258 
1259  if( SCIPisEQ(scip, matrixlhs, lhs) )
1260  SCIP_CALL( SCIPchgRhsLinear(scip, cons, matrixlhs) );
1261  else
1262  SCIP_CALL( SCIPchgLhsLinear(scip, cons, -matrixlhs) );
1263 
1264  nsideschanged++;
1265  (*nchgsides)++;
1266  }
1267  else
1268  {
1269  assert(!SCIPisEQ(scip, matrixlhs, matrixrhs));
1270 
1271  if( SCIPisEQ(scip, matrixrhs, rhs) )
1272  SCIP_CALL( SCIPchgLhsLinear(scip, cons, matrixrhs) );
1273  else
1274  SCIP_CALL( SCIPchgRhsLinear(scip, cons, -matrixrhs) );
1275 
1276  nsideschanged++;
1277  (*nchgsides)++;
1278  }
1279  }
1280  }
1281  }
1282 
1283  SCIPfreeBufferArray(scip, &sidestochange);
1284  SCIPfreeBufferArray(scip, &varstofix);
1285 
1286  if( (nconvarsfixed + nintvarsfixed + nbinvarsfixed) > 0 || npossiblesidechanges > 0)
1287  {
1288  SCIPdebugMsg(scip, "### fixed vars [cont: %d, int: %d, bin: %d], changed sides [%d]\n",
1289  nconvarsfixed, nintvarsfixed, nbinvarsfixed, nsideschanged);
1290  }
1291  }
1292  }
1293 
1294  SCIPmatrixFree(scip, &matrix);
1295 
1296  return SCIP_OKAY;
1297 }
1298 
1299 
1300 /*
1301  * presolver specific interface methods
1302  */
1303 
1304 /** creates the dual inference presolver and includes it in SCIP */
1306  SCIP* scip /**< SCIP data structure */
1307  )
1308 {
1309  SCIP_PRESOL* presol;
1310 
1311  /* include presolver */
1313  PRESOL_TIMING, presolExecDualinfer, NULL) );
1314  SCIP_CALL( SCIPsetPresolCopy(scip, presol, presolCopyDualinfer) );
1315 
1316  return SCIP_OKAY;
1317 }
static void calcColActivity(SCIP *scip, SCIP_MATRIX *matrix, SCIP_Bool onlyconvars, int startcol, int stopcol, SCIP_Real *lbdual[2], SCIP_Real *ubdual[2], SCIP_Real *mincolact, SCIP_Real *maxcolact, int *maxcolactinf, int *mincolactinf, SCIP_Bool *isimplfree)
SCIP_RETCODE SCIPincludePresolBasic(SCIP *scip, SCIP_PRESOL **presolptr, const char *name, const char *desc, int priority, int maxrounds, SCIP_PRESOLTIMING timing, SCIP_DECL_PRESOLEXEC((*presolexec)), SCIP_PRESOLDATA *presoldata)
Definition: scip.c:6917
SCIP_VAR * SCIPmatrixGetVar(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1325
int SCIPmatrixGetNRows(SCIP_MATRIX *matrix)
Definition: matrix.c:1397
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip.c:821
static SCIP_Bool isUpperBoundImplied(SCIP *scip, SCIP_MATRIX *matrix, int col)
#define PRESOL_TIMING
static SCIP_RETCODE dualBoundStrengthening(SCIP *scip, SCIP_MATRIX *matrix, FIXINGDIRECTION *varstofix, int *npossiblefixings, SIDECHANGE *sidestochange, int *npossiblesidechanges)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17276
static SCIP_Real getMaxActivitySingleRowWithoutCol(SCIP *scip, SCIP_MATRIX *matrix, int row, int col)
SCIP_CONS * SCIPmatrixGetCons(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1525
SideChange
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17332
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47009
void SCIPmatrixFree(SCIP *scip, SCIP_MATRIX **matrix)
Definition: matrix.c:782
#define FALSE
Definition: def.h:64
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:47022
#define TRUE
Definition: def.h:63
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46957
#define PRESOL_MAXROUNDS
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22632
SCIP_Real SCIPmatrixGetRowMaxActivity(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1465
SCIP_RETCODE SCIPmatrixCreate(SCIP *scip, SCIP_MATRIX **matrixptr, SCIP_Bool *initialized, SCIP_Bool *complete)
Definition: matrix.c:430
#define SCIPdebugMsg
Definition: scip.h:455
SCIP_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
int SCIPgetNContVars(SCIP *scip)
Definition: scip.c:11986
static void infCntUpdate(SCIP *scip, SCIP_MATRIX *matrix, SCIP_Real val, int row, SCIP_Real *lbdual[2], SCIP_Real *ubdual[2], int part, SCIP_Real *mincolact, SCIP_Real *maxcolact, int *maxcolactinf, int *mincolactinf, SCIP_Bool *isimplfree)
enum Fixingdirection FIXINGDIRECTION
int SCIPmatrixGetRowNNonzs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1373
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17286
SCIP_Real SCIPmatrixGetRowLhs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1407
enum Fixingdirection FIXINGDIRECTION
Definition: presol_domcol.c:81
Fixingdirection
Definition: presol_domcol.c:75
SCIP_Real * SCIPmatrixGetColValPtr(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1233
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4113
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46970
int SCIPmatrixGetRowNMaxActPosInf(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1513
int * SCIPmatrixGetRowIdxPtr(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1361
static SCIP_DECL_PRESOLCOPY(presolCopyDualinfer)
int SCIPmatrixGetRowNMaxActNegInf(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1501
#define SCIP_CALL(x)
Definition: def.h:350
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47318
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 SCIPincludePresolDualinfer(SCIP *scip)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:22620
#define SCIP_Bool
Definition: def.h:61
int SCIPvarGetNLocksUp(SCIP_VAR *var)
Definition: var.c:3217
int * SCIPmatrixGetColIdxPtr(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1245
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8006
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
Definition: presol.c:553
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17124
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip.c:25569
#define PRESOL_NAME
Constraint handler for linear constraints in their most general form, .
static void calcColActResidual(SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real val, SCIP_Real *lbdual[2], SCIP_Real *ubdual[2], int part, SCIP_Real *mincolact, int *mincolactinf, SCIP_Real *mincolresact)
int SCIPmatrixGetRowNMinActNegInf(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1477
SCIP_RETCODE SCIPchgRhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real rhs)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:47033
public methods for matrix
#define PRESOL_PRIORITY
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip.c:35830
#define MAX_LOOPS
static SCIP_Real getMinActivitySingleRowWithoutCol(SCIP *scip, SCIP_MATRIX *matrix, int row, int col)
int SCIPvarGetNLocksDown(SCIP_VAR *var)
Definition: var.c:3162
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46996
dual inference presolver
SCIP_Real SCIPmatrixGetRowRhs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1419
enum SideChange SIDECHANGE
SCIP_Bool SCIPmatrixIsRowRhsInfinity(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1431
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLCOPY((*presolcopy)))
Definition: scip.c:6952
SCIP_Bool SCIPallowDualReds(SCIP *scip)
Definition: scip.c:25879
#define SCIP_Real
Definition: def.h:149
SCIP_Real SCIPmatrixGetRowMinActivity(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1453
int SCIPmatrixGetColNDownlocks(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1313
static SCIP_DECL_PRESOLEXEC(presolExecDualinfer)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16827
#define PRESOL_DESC
int SCIPmatrixGetRowNMinActPosInf(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1489
static SCIP_Real getMinColActWithoutRow(SCIP *scip, SCIP_MATRIX *matrix, int col, int withoutrow, SCIP_Real *lbdual[2], SCIP_Real *ubdual[2], int part)
SCIP_RETCODE SCIPchgLhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs)
int SCIPmatrixGetColNUplocks(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1301
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:112
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
int SCIPmatrixGetNColumns(SCIP_MATRIX *matrix)
Definition: matrix.c:1269
static void getVarUpperBoundOfRow(SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real val, SCIP_Real *rowub, SCIP_Bool *ubfound)
static void getMinMaxActivityResiduals(SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real val, SCIP_Real *minresactivity, SCIP_Real *maxresactivity, SCIP_Bool *isminsettoinfinity, SCIP_Bool *ismaxsettoinfinity)
static void updateDualBounds(SCIP *scip, SCIP_MATRIX *matrix, SCIP_Real objval, SCIP_Real val, int row, SCIP_Real mincolresact, SCIP_Real *lbdual[2], SCIP_Real *ubdual[2], int part, int *boundchanges, SCIP_Bool *updateinfcnt)
int SCIPmatrixGetColNNonzs(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1257