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