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