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-2014 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 information for primal variable fixings:
22  * a) The first method is an enhanced dual fixing technique.
23  * b) The second method does dual bound strengthening on continuous primal
24  * variables and applies complementary slackness (yA-c)_i > 0 => x_i = 0
25  * for fixing primal variables at their lower bound.
26  *
27  */
28 
29 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
30 
31 #include <stdio.h>
32 #include <assert.h>
33 #include <string.h>
34 
35 /* includes necessary for matrix data structure */
36 #include "scip/cons_knapsack.h"
37 #include "scip/cons_linear.h"
38 #include "scip/cons_logicor.h"
39 #include "scip/cons_setppc.h"
40 #include "scip/cons_varbound.h"
41 
42 #include "presol_dualinfer.h"
43 
44 #define PRESOL_NAME "dualinfer"
45 #define PRESOL_DESC "exploit dual informations for variable fixings"
46 #define PRESOL_PRIORITY 20010000 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */
47 #define PRESOL_MAXROUNDS 0 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
48 #define PRESOL_DELAY TRUE /**< should presolver be delayed, if other presolvers found reductions? */
49 
50 #define MAX_LOOPS 7 /**< maximal number of dual bound strengthening loops */
51 
52 
53 /*
54  * Data structures
55  */
56 
57 
58 /** type of fixing direction */
59 enum Fixingdirection
60 {
61  FIXATLB = -1,
62  NOFIX = 0,
63  FIXATUB = 1
64 };
65 typedef enum Fixingdirection FIXINGDIRECTION;
66 
67 /********************************************************************/
68 /************** matrix data structure and functions *****************/
69 
70 /** constraint matrix data structure in column and row major format */
71 struct ConstraintMatrix
72 {
73  SCIP_Real* colmatval; /**< coefficients in column major format */
74  int* colmatind; /**< row indexes in column major format */
75  int* colmatbeg; /**< column storage offset */
76  int* colmatcnt; /**< number of row entries per column */
77  int ncols; /**< complete number of columns */
78  SCIP_Real* lb; /**< lower bound per variable */
79  SCIP_Real* ub; /**< upper bound per variable */
80 
81  SCIP_VAR** vars; /**< variables pointer */
82 
83  SCIP_Real* rowmatval; /**< coefficients in row major format */
84  int* rowmatind; /**< column indexed in row major format */
85  int* rowmatbeg; /**< row storage offset */
86  int* rowmatcnt; /**< number of column entries per row */
87 #ifdef SCIP_DEBUG
88  const char** rowname; /**< name of row */
89 #endif
90  int nrows; /**< complete number of rows */
91  SCIP_Real* lhs; /**< left hand side per row */
92  SCIP_Real* rhs; /**< right hand side per row */
93  SCIP_Bool* isrhsinfinite; /**< is right hand side infinity */
94  int nnonzs; /**< sparsity counter */
95  SCIP_Real* minactivity; /**< min activity per row */
96  SCIP_Real* maxactivity; /**< max activity per row */
97  int* minactivityneginf; /**< min activity negative infinity counter */
98  int* minactivityposinf; /**< min activity positive infinity counter */
99  int* maxactivityneginf; /**< max activity negative infinity counter */
100  int* maxactivityposinf; /**< max activity positive infinity counter */
101 };
102 typedef struct ConstraintMatrix CONSTRAINTMATRIX;
103 
104 /** transforms given variables, scalars, and constant to the corresponding active variables, scalars, and constant */
105 static
106 SCIP_RETCODE getActiveVariables(
107  SCIP* scip, /**< SCIP data structure */
108  SCIP_VAR*** vars, /**< vars array to get active variables for */
109  SCIP_Real** scalars, /**< scalars a_1, ..., a_n in linear sum a_1*x_1 + ... + a_n*x_n + c */
110  int* nvars, /**< pointer to number of variables and values in vars and vals array */
111  SCIP_Real* constant /**< pointer to constant c in linear sum a_1*x_1 + ... + a_n*x_n + c */
112  )
113 {
114  int requiredsize;
115 
116  assert(scip != NULL);
117  assert(vars != NULL);
118  assert(scalars != NULL);
119  assert(*vars != NULL);
120  assert(*scalars != NULL);
121  assert(nvars != NULL);
122  assert(constant != NULL);
123 
124  SCIP_CALL( SCIPgetProbvarLinearSum(scip, *vars, *scalars, nvars, *nvars, constant, &requiredsize, TRUE) );
125 
126  if( requiredsize > *nvars )
127  {
128  SCIP_CALL( SCIPreallocBufferArray(scip, vars, requiredsize) );
129  SCIP_CALL( SCIPreallocBufferArray(scip, scalars, requiredsize) );
130 
131  /* call function a second time with enough memory */
132  SCIP_CALL( SCIPgetProbvarLinearSum(scip, *vars, *scalars, nvars, requiredsize, constant, &requiredsize, TRUE) );
133  assert(requiredsize <= *nvars);
134  }
135 
136  return SCIP_OKAY;
137 }
138 
139 /** add one row to the constraint matrix */
140 static
141 SCIP_RETCODE addRow(
142  SCIP* scip, /**< SCIP data structure */
143  CONSTRAINTMATRIX* matrix, /**< constraint matrix */
144 #ifdef SCIP_DEBUG
145  const char* name, /**< name of constraint corresponding to row */
146 #endif
147  SCIP_VAR** vars, /**< variables of this row */
148  SCIP_Real* vals, /**< coefficients of this row */
149  int nvars, /**< number of variables of this row */
150  SCIP_Real lhs, /**< left hand side */
151  SCIP_Real rhs /**< right hand side */
152  )
153 {
154  int j;
155  int probindex;
156  int rowidx;
157  SCIP_Real factor;
158 
159  assert(vars != NULL);
160  assert(vals != NULL);
161 
162  rowidx = matrix->nrows;
163 
164  if( SCIPisInfinity(scip, -lhs) )
165  {
166  factor = -1.0;
167  matrix->lhs[rowidx] = -rhs;
168  matrix->rhs[rowidx] = SCIPinfinity(scip);
169  matrix->isrhsinfinite[rowidx] = TRUE;
170  }
171  else
172  {
173  factor = 1.0;
174  matrix->lhs[rowidx] = lhs;
175  matrix->rhs[rowidx] = rhs;
176  matrix->isrhsinfinite[rowidx] = SCIPisInfinity(scip, matrix->rhs[rowidx]);
177  }
178  assert(!SCIPisInfinity(scip, -matrix->lhs[rowidx]));
179 
180 
181 #ifdef SCIP_DEBUG
182  matrix->rowname[rowidx] = name;
183 #endif
184 
185  matrix->rowmatbeg[rowidx] = matrix->nnonzs;
186 
187  for( j = 0; j < nvars; j++ )
188  {
189  matrix->rowmatval[matrix->nnonzs] = factor * vals[j];
190  probindex = SCIPvarGetProbindex(vars[j]);
191  assert(matrix->vars[probindex] == vars[j]);
192 
193  assert(0 <= probindex && probindex < matrix->ncols);
194  matrix->rowmatind[matrix->nnonzs] = probindex;
195  (matrix->nnonzs)++;
196  }
197 
198  matrix->rowmatcnt[rowidx] = matrix->nnonzs - matrix->rowmatbeg[rowidx];
199 
200  ++(matrix->nrows);
201 
202  return SCIP_OKAY;
203 }
204 
205 /** add one constraint to matrix */
206 static
207 SCIP_RETCODE addConstraint(
208  SCIP* scip, /**< current scip instance */
209  CONSTRAINTMATRIX* matrix, /**< constraint matrix */
210 #ifdef SCIP_DEBUG
211  const char* name, /**< name of constraint corresponding to row */
212 #endif
213  SCIP_VAR** vars, /**< variables of this constraint */
214  SCIP_Real* vals, /**< variable coefficients of this constraint */
215  int nvars, /**< number of variables */
216  SCIP_Real lhs, /**< left hand side */
217  SCIP_Real rhs /**< right hand side */
218  )
219 {
220  SCIP_VAR** activevars;
221  SCIP_Real* activevals;
222  SCIP_Real activeconstant;
223  int nactivevars;
224  int v;
225 
226  assert(scip != NULL);
227  assert(matrix != NULL);
228  assert(vars != NULL || nvars == 0);
229  assert(SCIPisLE(scip, lhs, rhs));
230 
231  /* constraint is redundant */
232  if( SCIPisInfinity(scip, -lhs) && SCIPisInfinity(scip, rhs) )
233  return SCIP_OKAY;
234 
235  /* we do not add empty constraints to the matrix */
236  if( nvars == 0 )
237  return SCIP_OKAY;
238 
239  activevars = NULL;
240  activevals = NULL;
241  nactivevars = nvars;
242  activeconstant = 0.0;
243 
244  /* duplicate variable and value array */
245  SCIP_CALL( SCIPduplicateBufferArray(scip, &activevars, vars, nactivevars ) );
246  if( vals != NULL )
247  {
248  SCIP_CALL( SCIPduplicateBufferArray(scip, &activevals, vals, nactivevars ) );
249  }
250  else
251  {
252  SCIP_CALL( SCIPallocBufferArray(scip, &activevals, nactivevars) );
253 
254  for( v = 0; v < nactivevars; v++ )
255  activevals[v] = 1.0;
256  }
257 
258  /* retransform given variables to active variables */
259  SCIP_CALL( getActiveVariables(scip, &activevars, &activevals, &nactivevars, &activeconstant) );
260 
261  /* adapt left and right hand side */
262  if( !SCIPisInfinity(scip, -lhs) )
263  lhs -= activeconstant;
264  if( !SCIPisInfinity(scip, rhs) )
265  rhs -= activeconstant;
266 
267  /* add single row to matrix */
268  if( nactivevars > 0 )
269  {
270 #ifdef SCIP_DEBUG
271  SCIP_CALL( addRow(scip, matrix, name, activevars, activevals, nactivevars, lhs, rhs) );
272 #else
273  SCIP_CALL( addRow(scip, matrix, activevars, activevals, nactivevars, lhs, rhs) );
274 #endif
275  }
276 
277  /* free buffer arrays */
278  SCIPfreeBufferArray(scip, &activevals);
279  SCIPfreeBufferArray(scip, &activevars);
280 
281  return SCIP_OKAY;
282 }
283 
284 /** transform row major format into column major format */
285 static
286 SCIP_RETCODE setColumnMajorFormat(
287  SCIP* scip, /**< current scip instance */
288  CONSTRAINTMATRIX* matrix /**< constraint matrix */
289  )
290 {
291  int colidx;
292  int i;
293  int* rowpnt;
294  int* rowend;
295  SCIP_Real* valpnt;
296  int* fillidx;
297 
298  assert(scip != NULL);
299  assert(matrix != NULL);
300  assert(matrix->colmatval != NULL);
301  assert(matrix->colmatind != NULL);
302  assert(matrix->colmatbeg != NULL);
303  assert(matrix->colmatcnt != NULL);
304  assert(matrix->rowmatval != NULL);
305  assert(matrix->rowmatind != NULL);
306  assert(matrix->rowmatbeg != NULL);
307  assert(matrix->rowmatcnt != NULL);
308 
309  SCIP_CALL( SCIPallocBufferArray(scip, &fillidx, matrix->ncols) );
310  BMSclearMemoryArray(fillidx, matrix->ncols);
311  BMSclearMemoryArray(matrix->colmatcnt, matrix->ncols);
312 
313  for( i = 0; i < matrix->nrows; i++ )
314  {
315  rowpnt = matrix->rowmatind + matrix->rowmatbeg[i];
316  rowend = rowpnt + matrix->rowmatcnt[i];
317  for( ; rowpnt < rowend; rowpnt++ )
318  {
319  colidx = *rowpnt;
320  (matrix->colmatcnt[colidx])++;
321  }
322  }
323 
324  matrix->colmatbeg[0] = 0;
325  for( i = 0; i < matrix->ncols-1; i++ )
326  {
327  matrix->colmatbeg[i+1] = matrix->colmatbeg[i] + matrix->colmatcnt[i];
328  }
329 
330  for( i = 0; i < matrix->nrows; i++ )
331  {
332  rowpnt = matrix->rowmatind + matrix->rowmatbeg[i];
333  rowend = rowpnt + matrix->rowmatcnt[i];
334  valpnt = matrix->rowmatval + matrix->rowmatbeg[i];
335 
336  for( ; rowpnt < rowend; rowpnt++, valpnt++ )
337  {
338  assert(*rowpnt < matrix->ncols);
339  colidx = *rowpnt;
340  matrix->colmatval[matrix->colmatbeg[colidx] + fillidx[colidx]] = *valpnt;
341  matrix->colmatind[matrix->colmatbeg[colidx] + fillidx[colidx]] = i;
342  fillidx[colidx]++;
343  }
344  }
345 
346  SCIPfreeBufferArray(scip, &fillidx);
347 
348  return SCIP_OKAY;
349 }
350 
351 /** calculate min/max activity per row */
352 static
353 SCIP_RETCODE calcActivityBounds(
354  SCIP* scip, /**< current scip instance */
355  CONSTRAINTMATRIX* matrix /**< constraint matrix */
356  )
357 {
358  SCIP_Real val;
359  int* rowpnt;
360  int* rowend;
361  SCIP_Real* valpnt;
362  int col;
363  int row;
364 
365  assert(scip != NULL);
366  assert(matrix != NULL);
367 
368  for( row = 0; row < matrix->nrows; row++ )
369  {
370  matrix->minactivity[row] = 0;
371  matrix->maxactivity[row] = 0;
372  matrix->minactivityneginf[row] = 0;
373  matrix->minactivityposinf[row] = 0;
374  matrix->maxactivityneginf[row] = 0;
375  matrix->maxactivityposinf[row] = 0;
376 
377  rowpnt = matrix->rowmatind + matrix->rowmatbeg[row];
378  rowend = rowpnt + matrix->rowmatcnt[row];
379  valpnt = matrix->rowmatval + matrix->rowmatbeg[row];
380 
381  for( ; rowpnt < rowend; rowpnt++, valpnt++ )
382  {
383  /* get column index */
384  col = *rowpnt;
385 
386  /* get variable coefficient */
387  val = *valpnt;
388 
389  assert(matrix->ncols > col);
390 
391  assert(!SCIPisInfinity(scip, matrix->lb[col]));
392  assert(!SCIPisInfinity(scip, -matrix->ub[col]));
393 
394  if( val > 0.0 )
395  {
396  if( SCIPisInfinity(scip, matrix->ub[col]) )
397  matrix->maxactivityposinf[row]++;
398  else
399  matrix->maxactivity[row] += val * matrix->ub[col];
400 
401  if( SCIPisInfinity(scip, -matrix->lb[col]) )
402  matrix->minactivityneginf[row]++;
403  else
404  matrix->minactivity[row] += val * matrix->lb[col];
405  }
406  else if( val < 0.0 )
407  {
408  if( SCIPisInfinity(scip, -matrix->lb[col]) )
409  matrix->maxactivityneginf[row]++;
410  else
411  matrix->maxactivity[row] += val * matrix->lb[col];
412 
413  if( SCIPisInfinity(scip, matrix->ub[col]) )
414  matrix->minactivityposinf[row]++;
415  else
416  matrix->minactivity[row] += val * matrix->ub[col];
417  }
418  }
419 
420  if( (matrix->minactivityneginf[row] + matrix->minactivityposinf[row]) > 0 )
421  matrix->minactivity[row] = -SCIPinfinity(scip);
422  if( (matrix->maxactivityneginf[row] + matrix->maxactivityposinf[row]) > 0 )
423  matrix->maxactivity[row] = SCIPinfinity(scip);
424  }
425 
426  return SCIP_OKAY;
427 }
428 
429 /** initialize matrix */
430 static
431 SCIP_RETCODE initMatrix(
432  SCIP* scip, /**< current scip instance */
433  CONSTRAINTMATRIX** matrixptr, /**< pointer to constraint matrix object to be initialized */
434  SCIP_Bool* initialized /**< was the initialization successful? */
435  )
436 {
437  CONSTRAINTMATRIX* matrix;
438  SCIP_CONSHDLR** conshdlrs;
439  const char* conshdlrname;
440  SCIP_Bool stopped;
441  SCIP_VAR** vars;
442  SCIP_VAR* var;
443  SCIP_CONS* cons;
444  int nconshdlrs;
445  int nconss;
446  int nnonzstmp;
447  int nvars;
448  int c;
449  int i;
450  int v;
451 
452  nnonzstmp = 0;
453 
454  assert(scip != NULL);
455  assert(matrixptr != NULL);
456  assert(initialized != NULL);
457 
458  *initialized = FALSE;
459 
460  /* return if no variables or constraints are present */
461  if( SCIPgetNVars(scip) == 0 || SCIPgetNConss(scip) == 0 )
462  return SCIP_OKAY;
463 
464  /* loop over all constraint handlers and collect the number of checked constraints */
465  nconshdlrs = SCIPgetNConshdlrs(scip);
466  conshdlrs = SCIPgetConshdlrs(scip);
467  nconss = 0;
468 
469  for( i = 0; i < nconshdlrs; ++i )
470  {
471  int nconshdlrconss;
472 
473  nconshdlrconss = SCIPconshdlrGetNCheckConss(conshdlrs[i]);
474 
475  if( nconshdlrconss > 0 )
476  {
477  conshdlrname = SCIPconshdlrGetName(conshdlrs[i]);
478 
479  if( (strcmp(conshdlrname, "linear") != 0) && (strcmp(conshdlrname, "setppc") != 0)
480  && (strcmp(conshdlrname, "logicor") != 0) && (strcmp(conshdlrname, "knapsack") != 0)
481  && (strcmp(conshdlrname, "varbound") != 0) )
482  {
483  SCIPdebugMessage("unsupported constraint type <%s>: aborting domcol presolver\n", conshdlrname);
484  break;
485  }
486  }
487 
488  nconss += nconshdlrconss;
489  }
490 
491  /* do nothing if we have unsupported constraint types or no checked constraints */
492  if( i < nconshdlrs || nconss == 0 )
493  return SCIP_OKAY;
494 
495  stopped = FALSE;
496 
497  vars = SCIPgetVars(scip);
498  nvars = SCIPgetNVars(scip);
499 
500  /* approximate number of nonzeros by taking for each variable the number of up- and downlocks;
501  * this counts nonzeros in equalities twice, but can be at most two times as high as the exact number
502  */
503  for( i = nvars - 1; i >= 0; --i )
504  {
505  nnonzstmp += SCIPvarGetNLocksDown(vars[i]);
506  nnonzstmp += SCIPvarGetNLocksUp(vars[i]);
507  }
508 
509  /* do nothing if we have no entries */
510  if( nnonzstmp == 0 )
511  return SCIP_OKAY;
512 
513  /* build the matrix structure */
514  SCIP_CALL( SCIPallocBuffer(scip, matrixptr) );
515  matrix = *matrixptr;
516 
517  /* copy vars array and set number of variables */
518  SCIP_CALL( SCIPduplicateBufferArray(scip, &matrix->vars, SCIPgetVars(scip), nvars) );
519  matrix->ncols = nvars;
520 
521  matrix->nrows = 0;
522  matrix->nnonzs = 0;
523 
524  /* allocate memory for columns */
525  SCIP_CALL( SCIPallocBufferArray(scip, &matrix->colmatval, nnonzstmp) );
526  SCIP_CALL( SCIPallocBufferArray(scip, &matrix->colmatind, nnonzstmp) );
527  SCIP_CALL( SCIPallocBufferArray(scip, &matrix->colmatbeg, matrix->ncols) );
528  SCIP_CALL( SCIPallocBufferArray(scip, &matrix->colmatcnt, matrix->ncols) );
529  SCIP_CALL( SCIPallocBufferArray(scip, &matrix->lb, matrix->ncols) );
530  SCIP_CALL( SCIPallocBufferArray(scip, &matrix->ub, matrix->ncols) );
531 
532  for( v = 0; v < matrix->ncols; v++ )
533  {
534  var = matrix->vars[v];
535  assert(var != NULL);
536 
537  matrix->lb[v] = SCIPvarGetLbGlobal(var);
538  matrix->ub[v] = SCIPvarGetUbGlobal(var);
539  }
540 
541  /* allocate memory for rows */
542  SCIP_CALL( SCIPallocBufferArray(scip, &matrix->rowmatval, nnonzstmp) );
543  SCIP_CALL( SCIPallocBufferArray(scip, &matrix->rowmatind, nnonzstmp) );
544  SCIP_CALL( SCIPallocBufferArray(scip, &matrix->rowmatbeg, nconss) );
545  SCIP_CALL( SCIPallocBufferArray(scip, &matrix->rowmatcnt, nconss) );
546  SCIP_CALL( SCIPallocBufferArray(scip, &matrix->lhs, nconss) );
547  SCIP_CALL( SCIPallocBufferArray(scip, &matrix->rhs, nconss) );
548 
549  /* allocate memory for status of finiteness of row sides */
550  SCIP_CALL( SCIPallocClearMemoryArray(scip, &matrix->isrhsinfinite, nconss) );
551 
552 #ifdef SCIP_DEBUG
553  SCIP_CALL( SCIPallocBufferArray(scip, &matrix->rowname, nconss) );
554 #endif
555 
556  SCIP_CALL( SCIPallocBufferArray(scip, &matrix->minactivity, nconss) );
557  SCIP_CALL( SCIPallocBufferArray(scip, &matrix->maxactivity, nconss) );
558  SCIP_CALL( SCIPallocBufferArray(scip, &matrix->minactivityneginf, nconss) );
559  SCIP_CALL( SCIPallocBufferArray(scip, &matrix->minactivityposinf, nconss) );
560  SCIP_CALL( SCIPallocBufferArray(scip, &matrix->maxactivityneginf, nconss) );
561  SCIP_CALL( SCIPallocBufferArray(scip, &matrix->maxactivityposinf, nconss) );
562 
563  /* loop a second time over constraints handlers and add constraints to the matrix */
564  for( i = 0; i < nconshdlrs; ++i )
565  {
566  SCIP_CONS** conshdlrconss;
567  int nconshdlrconss;
568 
569  if( SCIPisStopped(scip) )
570  {
571  stopped = TRUE;
572  break;
573  }
574 
575  conshdlrname = SCIPconshdlrGetName(conshdlrs[i]);
576  conshdlrconss = SCIPconshdlrGetCheckConss(conshdlrs[i]);
577  nconshdlrconss = SCIPconshdlrGetNCheckConss(conshdlrs[i]);
578 
579  if( strcmp(conshdlrname, "linear") == 0 )
580  {
581  for( c = 0; c < nconshdlrconss && (c % 1000 != 0 || !SCIPisStopped(scip)); ++c )
582  {
583  cons = conshdlrconss[c];
584  assert(SCIPconsIsTransformed(cons));
585 
586 #ifdef SCIP_DEBUG
587  SCIP_CALL( addConstraint(scip, matrix, SCIPconsGetName(cons), SCIPgetVarsLinear(scip, cons),
588  SCIPgetValsLinear(scip, cons), SCIPgetNVarsLinear(scip, cons),
589  SCIPgetLhsLinear(scip, cons), SCIPgetRhsLinear(scip, cons)) );
590 #else
591  SCIP_CALL( addConstraint(scip, matrix, SCIPgetVarsLinear(scip, cons),
592  SCIPgetValsLinear(scip, cons), SCIPgetNVarsLinear(scip, cons),
593  SCIPgetLhsLinear(scip, cons), SCIPgetRhsLinear(scip, cons)) );
594 #endif
595  }
596  }
597  else if( strcmp(conshdlrname, "setppc") == 0 )
598  {
599  for( c = 0; c < nconshdlrconss && (c % 1000 != 0 || !SCIPisStopped(scip)); ++c )
600  {
601  SCIP_Real lhs;
602  SCIP_Real rhs;
603 
604  cons = conshdlrconss[c];
605  assert(SCIPconsIsTransformed(cons));
606 
607  switch( SCIPgetTypeSetppc(scip, cons) )
608  {
609  case SCIP_SETPPCTYPE_PARTITIONING :
610  lhs = 1.0;
611  rhs = 1.0;
612  break;
613  case SCIP_SETPPCTYPE_PACKING :
614  lhs = -SCIPinfinity(scip);
615  rhs = 1.0;
616  break;
617  case SCIP_SETPPCTYPE_COVERING :
618  lhs = 1.0;
619  rhs = SCIPinfinity(scip);
620  break;
621  default:
622  return SCIP_ERROR;
623  }
624 
625 #ifdef SCIP_DEBUG
626  SCIP_CALL( addConstraint(scip, matrix, SCIPconsGetName(cons), SCIPgetVarsSetppc(scip, cons), NULL,
627  SCIPgetNVarsSetppc(scip, cons), lhs, rhs) );
628 #else
629  SCIP_CALL( addConstraint(scip, matrix, SCIPgetVarsSetppc(scip, cons), NULL,
630  SCIPgetNVarsSetppc(scip, cons), lhs, rhs) );
631 #endif
632  }
633  }
634  else if( strcmp(conshdlrname, "logicor") == 0 )
635  {
636  for( c = 0; c < nconshdlrconss && (c % 1000 != 0 || !SCIPisStopped(scip)); ++c )
637  {
638  cons = conshdlrconss[c];
639  assert(SCIPconsIsTransformed(cons));
640 
641 #ifdef SCIP_DEBUG
642  SCIP_CALL( addConstraint(scip, matrix, SCIPconsGetName(cons), SCIPgetVarsLogicor(scip, cons),
643  NULL, SCIPgetNVarsLogicor(scip, cons), 1.0, SCIPinfinity(scip)) );
644 #else
645  SCIP_CALL( addConstraint(scip, matrix, SCIPgetVarsLogicor(scip, cons),
646  NULL, SCIPgetNVarsLogicor(scip, cons), 1.0, SCIPinfinity(scip)) );
647 #endif
648  }
649  }
650  else if( strcmp(conshdlrname, "knapsack") == 0 )
651  {
652  if( nconshdlrconss > 0 )
653  {
654  SCIP_Real* consvals;
655  int valssize;
656 
657  valssize = 100;
658  SCIP_CALL( SCIPallocBufferArray(scip, &consvals, valssize) );
659 
660  for( c = 0; c < nconshdlrconss && (c % 1000 != 0 || !SCIPisStopped(scip)); ++c )
661  {
662  SCIP_Longint* weights;
663 
664  cons = conshdlrconss[c];
665  assert(SCIPconsIsTransformed(cons));
666 
667  weights = SCIPgetWeightsKnapsack(scip, cons);
668  nvars = SCIPgetNVarsKnapsack(scip, cons);
669 
670  if( nvars > valssize )
671  {
672  valssize = (int) (1.5 * nvars);
673  SCIP_CALL( SCIPreallocBufferArray(scip, &consvals, valssize) );
674  }
675 
676  for( v = 0; v < nvars; v++ )
677  consvals[v] = (SCIP_Real)weights[v];
678 
679 #ifdef SCIP_DEBUG
680  SCIP_CALL( addConstraint(scip, matrix, SCIPconsGetName(cons), SCIPgetVarsKnapsack(scip, cons), consvals,
681  SCIPgetNVarsKnapsack(scip, cons), -SCIPinfinity(scip),
682  (SCIP_Real)SCIPgetCapacityKnapsack(scip, cons)) );
683 #else
684  SCIP_CALL( addConstraint(scip, matrix, SCIPgetVarsKnapsack(scip, cons), consvals,
685  SCIPgetNVarsKnapsack(scip, cons), -SCIPinfinity(scip),
686  (SCIP_Real)SCIPgetCapacityKnapsack(scip, cons)) );
687 #endif
688  }
689 
690  SCIPfreeBufferArray(scip, &consvals);
691  }
692  }
693  else if( strcmp(conshdlrname, "varbound") == 0 )
694  {
695  if( nconshdlrconss > 0 )
696  {
697  SCIP_VAR** consvars;
698  SCIP_Real* consvals;
699 
700  SCIP_CALL( SCIPallocBufferArray(scip, &consvars, 2) );
701  SCIP_CALL( SCIPallocBufferArray(scip, &consvals, 2) );
702  consvals[0] = 1.0;
703 
704  for( c = 0; c < nconshdlrconss && (c % 1000 != 0 || !SCIPisStopped(scip)); ++c )
705  {
706  cons = conshdlrconss[c];
707  assert(SCIPconsIsTransformed(cons));
708 
709  consvars[0] = SCIPgetVarVarbound(scip, cons);
710  consvars[1] = SCIPgetVbdvarVarbound(scip, cons);
711 
712  consvals[1] = SCIPgetVbdcoefVarbound(scip, cons);
713 
714 #ifdef SCIP_DEBUG
715  SCIP_CALL( addConstraint(scip, matrix, SCIPconsGetName(cons), consvars, consvals, 2, SCIPgetLhsVarbound(scip, cons),
716  SCIPgetRhsVarbound(scip, cons)) );
717 #else
718  SCIP_CALL( addConstraint(scip, matrix, consvars, consvals, 2, SCIPgetLhsVarbound(scip, cons),
719  SCIPgetRhsVarbound(scip, cons)) );
720 #endif
721  }
722 
723  SCIPfreeBufferArray(scip, &consvals);
724  SCIPfreeBufferArray(scip, &consvars);
725  }
726  }
727 #ifndef NDEBUG
728  else
729  {
730  assert(nconshdlrconss == 0);
731  }
732 #endif
733  }
734  assert(matrix->nrows <= nconss);
735  assert(matrix->nnonzs <= nnonzstmp);
736 
737  if( !stopped )
738  {
739  /* calculate row activity bounds */
740  SCIP_CALL( calcActivityBounds(scip, matrix) );
741 
742  /* transform row major format into column major format */
743  SCIP_CALL( setColumnMajorFormat(scip, matrix) );
744 
745  *initialized = TRUE;
746  }
747 
748  return SCIP_OKAY;
749 }
750 
751 
752 /** frees the constraint matrix */
753 static
754 void freeMatrix(
755  SCIP* scip, /**< current SCIP instance */
756  CONSTRAINTMATRIX** matrix /**< constraint matrix object */
757  )
758 {
759  assert(scip != NULL);
760  assert(matrix != NULL);
761 
762  if( (*matrix) != NULL )
763  {
764  assert((*matrix)->colmatval != NULL);
765  assert((*matrix)->colmatind != NULL);
766  assert((*matrix)->colmatbeg != NULL);
767  assert((*matrix)->colmatcnt != NULL);
768  assert((*matrix)->lb != NULL);
769  assert((*matrix)->ub != NULL);
770 
771  assert((*matrix)->rowmatval != NULL);
772  assert((*matrix)->rowmatind != NULL);
773  assert((*matrix)->rowmatbeg != NULL);
774  assert((*matrix)->rowmatcnt != NULL);
775  assert((*matrix)->lhs != NULL);
776  assert((*matrix)->rhs != NULL);
777 #ifdef SCIP_DEBUG
778  assert((*matrix)->rowname != NULL);
779 #endif
780 
781  SCIPfreeBufferArray(scip, &((*matrix)->maxactivityposinf));
782  SCIPfreeBufferArray(scip, &((*matrix)->maxactivityneginf));
783  SCIPfreeBufferArray(scip, &((*matrix)->minactivityposinf));
784  SCIPfreeBufferArray(scip, &((*matrix)->minactivityneginf));
785  SCIPfreeBufferArray(scip, &((*matrix)->maxactivity));
786  SCIPfreeBufferArray(scip, &((*matrix)->minactivity));
787 
788 #ifdef SCIP_DEBUG
789  SCIPfreeBufferArray(scip, &((*matrix)->rowname));
790 #endif
791 
792  SCIPfreeMemoryArray(scip, &((*matrix)->isrhsinfinite));
793 
794  SCIPfreeBufferArray(scip, &((*matrix)->rhs));
795  SCIPfreeBufferArray(scip, &((*matrix)->lhs));
796  SCIPfreeBufferArray(scip, &((*matrix)->rowmatcnt));
797  SCIPfreeBufferArray(scip, &((*matrix)->rowmatbeg));
798  SCIPfreeBufferArray(scip, &((*matrix)->rowmatind));
799  SCIPfreeBufferArray(scip, &((*matrix)->rowmatval));
800 
801  SCIPfreeBufferArray(scip, &((*matrix)->ub));
802  SCIPfreeBufferArray(scip, &((*matrix)->lb));
803  SCIPfreeBufferArray(scip, &((*matrix)->colmatcnt));
804  SCIPfreeBufferArray(scip, &((*matrix)->colmatbeg));
805  SCIPfreeBufferArray(scip, &((*matrix)->colmatind));
806  SCIPfreeBufferArray(scip, &((*matrix)->colmatval));
807 
808  (*matrix)->nrows = 0;
809  (*matrix)->ncols = 0;
810  (*matrix)->nnonzs = 0;
811 
812  SCIPfreeBufferArrayNull(scip, &((*matrix)->vars));
813 
814  SCIPfreeBuffer(scip, matrix);
815  }
816 }
817 
818 /************** end matrix data structure and functions *************/
819 /********************************************************************/
820 
821 
822 
823 /*
824  * Local methods
825  */
826 
827 /** return if row is redundant or not */
828 static
829 SCIP_Bool isRowRedundant(
830  SCIP* scip, /**< SCIP main data structure */
831  CONSTRAINTMATRIX* matrix, /**< matrix containing the constraints */
832  int row /**< row to be checked for redundancy */
833  )
834 {
835  assert(scip != NULL);
836  assert(matrix != NULL);
837  assert(0 <= row && row < matrix->nrows);
838 
839  return SCIPisFeasLE(scip, matrix->lhs[row], matrix->minactivity[row])
840  && SCIPisFeasLE(scip, matrix->maxactivity[row], matrix->rhs[row]);
841 }
842 
843 /** initialize shadow prices */
844 static
845 void initShadowPrices(
846  SCIP* scip, /**< SCIP main data structure */
847  CONSTRAINTMATRIX* matrix, /**< matrix containing the constraints */
848  SCIP_Real* lowershadow, /**< lower shadow prices */
849  SCIP_Real* uppershadow /**< upper shadow prices */
850  )
851 {
852  int r;
853 
854  assert(scip != NULL);
855  assert(matrix != NULL);
856  assert(lowershadow != NULL);
857  assert(uppershadow != NULL);
858 
859  for( r = 0; r < matrix->nrows; r++ )
860  {
861  lowershadow[r] = -SCIPinfinity(scip);
862  uppershadow[r] = matrix->isrhsinfinite[r] ? 0 : SCIPinfinity(scip);
863  }
864 }
865 
866 /** search for singleton columns and update shadow prices */
867 static
868 SCIP_RETCODE singletonColumns(
869  SCIP* scip, /**< SCIP main data structure */
870  CONSTRAINTMATRIX* matrix, /**< matrix containing the constraints */
871  SCIP_Real* lowershadow, /**< lower shadows */
872  SCIP_Real* uppershadow, /**< upper shadows */
873  int* nfitsinglecols /**< number of fitting singleton columns */
874  )
875 {
876  int c;
877 
878  assert(scip != NULL);
879  assert(matrix != NULL);
880  assert(lowershadow != NULL);
881  assert(uppershadow != NULL);
882  assert(nfitsinglecols != NULL);
883 
884  for( c = 0; c < matrix->ncols; c++ )
885  {
886  if( matrix->colmatcnt[c] == 1 && SCIPvarGetType(matrix->vars[c]) == SCIP_VARTYPE_CONTINUOUS &&
887  SCIPisInfinity(scip, SCIPvarGetUbGlobal(matrix->vars[c]))
888  /*&& SCIPisEQ(scip, SCIPvarGetLbGlobal(matrix->vars[c]), 0)*/ )
889  {
890  int row;
891 
892  row = *(matrix->colmatind + matrix->colmatbeg[c]);
893 
894  if( matrix->isrhsinfinite[row] )
895  {
896  SCIP_Real val;
897  SCIP_Real tmp;
898 
899  val = *(matrix->colmatval + matrix->colmatbeg[c]);
900  tmp = -SCIPvarGetObj(matrix->vars[c]) / val;
901 
902  (*nfitsinglecols)++;
903 
904  if( val > 0 )
905  {
906  if( tmp > lowershadow[row] )
907  lowershadow[row] = tmp;
908  }
909  else
910  {
911  assert(val < 0);
912 
913  if( tmp < uppershadow[row] )
914  uppershadow[row] = tmp;
915  }
916  }
917  }
918  }
919 
920  return SCIP_OKAY;
921 }
922 
923 /** calculate min/max costs per column */
924 static
925 void costCalculation(
926  SCIP* scip, /**< SCIP main data structure */
927  CONSTRAINTMATRIX* matrix, /**< matrix containing the constraints */
928  SCIP_Real* lowershadow, /**< lower shadows */
929  SCIP_Real* uppershadow, /**< upper shadows */
930  SCIP_Real* lowercosts, /**< lower shadow costs */
931  SCIP_Real* uppercosts /**< upper shadow costs */
932  )
933 {
934  SCIP_Real* valpnt;
935  int* colpnt;
936  int* colend;
937  SCIP_Real val;
938  SCIP_Bool mininfinite;
939  SCIP_Bool maxinfinite;
940  int row;
941  int c;
942 
943  assert(scip != NULL);
944  assert(matrix != NULL);
945  assert(lowershadow != NULL);
946  assert(uppershadow != NULL);
947  assert(lowercosts != NULL);
948  assert(uppercosts != NULL);
949 
950  for( c = 0; c < matrix->ncols; c++)
951  {
952  mininfinite = FALSE;
953  maxinfinite = FALSE;
954  lowercosts[c] = 0;
955  uppercosts[c] = 0;
956 
957  colpnt = matrix->colmatind + matrix->colmatbeg[c];
958  colend = colpnt + matrix->colmatcnt[c];
959  valpnt = matrix->colmatval + matrix->colmatbeg[c];
960 
961  for( ; (colpnt < colend) && (!mininfinite || !maxinfinite); colpnt++, valpnt++ )
962  {
963  row = *colpnt;
964  val = *valpnt;
965 
966  if( !isRowRedundant(scip, matrix, row) )
967  {
968  if( val >= 0.0 )
969  {
970  mininfinite = mininfinite || SCIPisInfinity(scip, -lowershadow[row]);
971  maxinfinite = maxinfinite || SCIPisInfinity(scip, uppershadow[row]);
972 
973  if( !mininfinite )
974  {
975  lowercosts[c] += val * lowershadow[row];
976  }
977  if( !maxinfinite )
978  {
979  uppercosts[c] += val * uppershadow[row];
980  }
981  }
982  else
983  {
984  mininfinite = mininfinite || SCIPisInfinity(scip, uppershadow[row]);
985  maxinfinite = maxinfinite || SCIPisInfinity(scip, -lowershadow[row]);
986 
987  if( !mininfinite )
988  {
989  lowercosts[c] += val * uppershadow[row];
990  }
991  if( !maxinfinite )
992  {
993  uppercosts[c] += val * lowershadow[row];
994  }
995  }
996  }
997  }
998 
999  if( mininfinite )
1000  lowercosts[c] = -SCIPinfinity(scip);
1001  if( maxinfinite )
1002  uppercosts[c] = SCIPinfinity(scip);
1003  }
1004 }
1005 
1006 /** fix variables at their bounds out of the min/max costs */
1007 static
1008 void fixColumns(
1009  SCIP* scip, /**< SCIP main data structure */
1010  CONSTRAINTMATRIX* matrix, /**< matrix containing the constraints */
1011  SCIP_Real* lowercosts, /**< lower shadow costs */
1012  SCIP_Real* uppercosts, /**< upper shadow costs */
1013  int* npossiblefixings, /**< number of possible fixings */
1014  FIXINGDIRECTION* varstofix /**< array holding information for later upper/lower bound fixing */
1015  )
1016 {
1017  int c;
1018 
1019  assert(scip != NULL);
1020  assert(matrix != NULL);
1021  assert(lowercosts != NULL);
1022  assert(uppercosts != NULL);
1023  assert(npossiblefixings != NULL);
1024  assert(varstofix != NULL);
1025 
1026  for( c = 0; c < matrix->ncols; c++ )
1027  {
1028  SCIP_Real objval;
1029 
1030  objval = -SCIPvarGetObj(matrix->vars[c]);
1031 
1032  if( !SCIPisInfinity(scip, lowercosts[c]) && !SCIPisInfinity(scip, -lowercosts[c]) )
1033  {
1034  if( lowercosts[c] > objval )
1035  {
1036  if( !SCIPisInfinity(scip, -SCIPvarGetLbGlobal(matrix->vars[c])) )
1037  {
1038  varstofix[c] = FIXATLB;
1039  (*npossiblefixings)++;
1040  }
1041  }
1042  }
1043  if( !SCIPisInfinity(scip, uppercosts[c]) && !SCIPisInfinity(scip, -uppercosts[c]) )
1044  {
1045  if( uppercosts[c] < objval )
1046  {
1047  if( !SCIPisInfinity(scip, SCIPvarGetUbGlobal(matrix->vars[c])) )
1048  {
1049  varstofix[c] = FIXATUB;
1050  (*npossiblefixings)++;
1051  }
1052  }
1053  }
1054  }
1055 }
1056 
1057 /** dual cost fixing */
1058 static
1059 SCIP_RETCODE costFixing(
1060  SCIP* scip, /**< SCIP main data structure */
1061  CONSTRAINTMATRIX* matrix, /**< matrix containing the constraints */
1062  FIXINGDIRECTION* varstofix, /**< array holding information for later upper/lower bound fixing */
1063  int* nfitsinglecols, /**< number of continuous singleton columns */
1064  int* npossiblefixings /**< number of possible fixings */
1065  )
1066 {
1067  SCIP_Real* lowershadow;
1068  SCIP_Real* uppershadow;
1069  SCIP_Real* lowercosts;
1070  SCIP_Real* uppercosts;
1071 
1072  assert(scip != NULL);
1073  assert(matrix != NULL);
1074  assert(varstofix != NULL);
1075  assert(nfitsinglecols != NULL);
1076  assert(npossiblefixings != NULL);
1077 
1078  SCIP_CALL( SCIPallocBufferArray(scip, &lowershadow, matrix->nrows) );
1079  SCIP_CALL( SCIPallocBufferArray(scip, &uppershadow, matrix->nrows) );
1080  SCIP_CALL( SCIPallocBufferArray(scip, &lowercosts, matrix->ncols) );
1081  SCIP_CALL( SCIPallocBufferArray(scip, &uppercosts, matrix->ncols) );
1082 
1083  initShadowPrices(scip, matrix, lowershadow, uppershadow);
1084 
1085  SCIP_CALL( singletonColumns(scip, matrix, lowershadow, uppershadow, nfitsinglecols) );
1086 
1087  costCalculation(scip, matrix, lowershadow, uppershadow, lowercosts, uppercosts);
1088 
1089  fixColumns(scip, matrix, lowercosts, uppercosts, npossiblefixings, varstofix);
1090 
1091  SCIPfreeBufferArray(scip, &uppercosts);
1092  SCIPfreeBufferArray(scip, &lowercosts);
1093  SCIPfreeBufferArray(scip, &uppershadow);
1094  SCIPfreeBufferArray(scip, &lowershadow);
1095 
1096  return SCIP_OKAY;
1097 }
1098 
1099 /** calculate maximal column activity from one continuous variable without one row */
1100 static
1101 SCIP_Real getMaxColActWithoutRow(
1102  SCIP* scip, /**< SCIP main data structure */
1103  CONSTRAINTMATRIX* matrix, /**< matrix containing the constraints */
1104  int col, /**< column index */
1105  int withoutrow, /**< exclude row index */
1106  SCIP_Real* lbdual, /**< lower bounds of dual variables */
1107  SCIP_Real* ubdual /**< upper bounds of dual variables */
1108  )
1109 {
1110  SCIP_Real* valpnt;
1111  int* colpnt;
1112  int* colend;
1113  SCIP_Real val;
1114  SCIP_Real maxcolactivity;
1115  int row;
1116 
1117  assert(scip != NULL);
1118  assert(matrix != NULL);
1119  assert(0 <= col && col < matrix->ncols);
1120  assert(0 <= withoutrow && withoutrow < matrix->nrows);
1121  assert(lbdual != NULL);
1122  assert(ubdual != NULL);
1123  assert(SCIPvarGetType(matrix->vars[col]) == SCIP_VARTYPE_CONTINUOUS);
1124 
1125  maxcolactivity = 0;
1126 
1127  colpnt = matrix->colmatind + matrix->colmatbeg[col];
1128  colend = colpnt + matrix->colmatcnt[col];
1129  valpnt = matrix->colmatval + matrix->colmatbeg[col];
1130 
1131  for(; (colpnt < colend); colpnt++, valpnt++ )
1132  {
1133  row = *colpnt;
1134  val = *valpnt;
1135 
1136  assert(matrix->isrhsinfinite[row]);
1137 
1138  if( row == withoutrow )
1139  continue;
1140 
1141  if( val > 0 )
1142  {
1143  assert(!SCIPisInfinity(scip, ubdual[row]));
1144  maxcolactivity += val * ubdual[row];
1145  }
1146  else if( val < 0.0 )
1147  {
1148  assert(!SCIPisInfinity(scip, -lbdual[row]));
1149  maxcolactivity += val * lbdual[row];
1150  }
1151  }
1152  return maxcolactivity;
1153 }
1154 
1155 /** calculate minimal column activity from one continuous variable without one row */
1156 static
1157 SCIP_Real getMinColActWithoutRow(
1158  SCIP* scip, /**< SCIP main data structure */
1159  CONSTRAINTMATRIX* matrix, /**< matrix containing the constraints */
1160  int col, /**< column index */
1161  int withoutrow, /**< exclude row index */
1162  SCIP_Real* lbdual, /**< lower bounds of dual variables */
1163  SCIP_Real* ubdual /**< upper bounds of dual variables */
1164  )
1165 {
1166  SCIP_Real* valpnt;
1167  int* colpnt;
1168  int* colend;
1169  SCIP_Real val;
1170  SCIP_Real mincolactivity;
1171  int row;
1172 
1173  assert(scip != NULL);
1174  assert(matrix != NULL);
1175  assert(0 <= col && col < matrix->ncols);
1176  assert(0 <= withoutrow && withoutrow < matrix->nrows);
1177  assert(lbdual != NULL);
1178  assert(ubdual != NULL);
1179  assert(SCIPvarGetType(matrix->vars[col]) == SCIP_VARTYPE_CONTINUOUS);
1180 
1181  mincolactivity = 0;
1182 
1183  colpnt = matrix->colmatind + matrix->colmatbeg[col];
1184  colend = colpnt + matrix->colmatcnt[col];
1185  valpnt = matrix->colmatval + matrix->colmatbeg[col];
1186 
1187  for(; (colpnt < colend); colpnt++, valpnt++ )
1188  {
1189  row = *colpnt;
1190  val = *valpnt;
1191 
1192  assert(matrix->isrhsinfinite[row]);
1193 
1194  if( row == withoutrow )
1195  continue;
1196 
1197  if( val > 0 )
1198  {
1199  assert(!SCIPisInfinity(scip, -lbdual[row]));
1200  mincolactivity += val * lbdual[row];
1201  }
1202  else if( val < 0.0 )
1203  {
1204  assert(!SCIPisInfinity(scip, ubdual[row]));
1205  mincolactivity += val * ubdual[row];
1206  }
1207  }
1208  return mincolactivity;
1209 }
1210 
1211 /** calculate minimal/maximal column residual activities */
1212 static
1213 void calcColActivityResiduals(
1214  SCIP* scip, /**< SCIP main data structure */
1215  CONSTRAINTMATRIX* matrix, /**< matrix containing the constraints */
1216  int col, /**< column index */
1217  int row, /**< row index */
1218  SCIP_Real val, /**< matrix coefficient */
1219  SCIP_Real* lbdual, /**< lower bounds of dual variables */
1220  SCIP_Real* ubdual, /**< upper bounds of dual variables */
1221  SCIP_Real* mincolact, /**< minimal column activities */
1222  SCIP_Real* maxcolact, /**< maximal column activities */
1223  int* maxcolactinf, /**< number of (positive) infinite contributions to maximal column activity */
1224  int* mincolactinf, /**< number of (negative) infinite contributions to minimal column activity */
1225  SCIP_Real* mincolresact, /**< minimal column residual activity */
1226  SCIP_Real* maxcolresact /**< maximal column residual activity */
1227  )
1228 {
1229  assert(scip != NULL);
1230  assert(matrix != NULL);
1231  assert(0 <= col && col < matrix->ncols);
1232  assert(0 <= row && row < matrix->nrows);
1233  assert(lbdual != NULL);
1234  assert(ubdual != NULL);
1235  assert(mincolact != NULL);
1236  assert(maxcolact != NULL);
1237  assert(maxcolactinf != NULL);
1238  assert(mincolactinf != NULL);
1239  assert(mincolresact != NULL);
1240  assert(maxcolresact != NULL);
1241  assert(matrix->isrhsinfinite[row]);
1242  assert(SCIPvarGetType(matrix->vars[col]) == SCIP_VARTYPE_CONTINUOUS);
1243 
1244  if( val > 0.0 )
1245  {
1246  if( SCIPisInfinity(scip, ubdual[row]) )
1247  {
1248  assert(maxcolactinf[col] >= 1);
1249  if( maxcolactinf[col] == 1 )
1250  *maxcolresact = getMaxColActWithoutRow(scip, matrix, col, row, lbdual, ubdual);
1251  else
1252  *maxcolresact = SCIPinfinity(scip);
1253  }
1254  else
1255  {
1256  if( maxcolactinf[col] > 0 )
1257  *maxcolresact = SCIPinfinity(scip);
1258  else
1259  *maxcolresact = maxcolact[col] - val * ubdual[row];
1260  }
1261 
1262  if( SCIPisInfinity(scip, -lbdual[row]) )
1263  {
1264  assert(mincolactinf[col] >= 1);
1265  if( mincolactinf[col] == 1 )
1266  *mincolresact = getMinColActWithoutRow(scip, matrix, col, row, lbdual, ubdual);
1267  else
1268  *mincolresact = -SCIPinfinity(scip);
1269  }
1270  else
1271  {
1272  if( mincolactinf[col] > 0 )
1273  *mincolresact = -SCIPinfinity(scip);
1274  else
1275  *mincolresact = mincolact[col] - val * lbdual[row];
1276  }
1277  }
1278  else if( val < 0.0 )
1279  {
1280  if( SCIPisInfinity(scip, -lbdual[row]) )
1281  {
1282  assert(maxcolactinf[col] >= 1);
1283  if( maxcolactinf[col] == 1 )
1284  *maxcolresact = getMaxColActWithoutRow(scip, matrix, col, row, lbdual, ubdual);
1285  else
1286  *maxcolresact = SCIPinfinity(scip);
1287  }
1288  else
1289  {
1290  if( maxcolactinf[col] > 0 )
1291  *maxcolresact = SCIPinfinity(scip);
1292  else
1293  *maxcolresact = maxcolact[col] - val * lbdual[row];
1294  }
1295 
1296  if( SCIPisInfinity(scip, ubdual[row]) )
1297  {
1298  assert(mincolactinf[col] >= 1);
1299  if( mincolactinf[col] == 1 )
1300  *mincolresact = getMinColActWithoutRow(scip, matrix, col, row, lbdual, ubdual);
1301  else
1302  *mincolresact = -SCIPinfinity(scip);
1303  }
1304  else
1305  {
1306  if( mincolactinf[col] > 0 )
1307  *mincolresact = -SCIPinfinity(scip);
1308  else
1309  *mincolresact = mincolact[col] - val * ubdual[row];
1310  }
1311  }
1312 }
1313 
1314 /** calculate minimal/maximal column activity on continuous variables */
1315 static
1316 void calcColActivity(
1317  SCIP* scip, /**< SCIP main data structure */
1318  CONSTRAINTMATRIX* matrix, /**< matrix containing the constraints */
1319  SCIP_Real* lbdual, /**< lower bounds of dual variables */
1320  SCIP_Real* ubdual, /**< upper bounds of dual variables */
1321  int startcol, /**< start column index */
1322  int stopcol, /**< stop column index */
1323  SCIP_Bool* excludevar, /**< indicating if variable is within an equation or ranged row */
1324  SCIP_Real* mincolact, /**< minimal column activities */
1325  SCIP_Real* maxcolact, /**< maximal column activities */
1326  int* maxcolactinf, /**< number of (positive) inifite contributions to maximal column activity */
1327  int* mincolactinf /**< number of (negative) infinite contributions to minimal column activity */
1328  )
1329 {
1330  SCIP_Real* valpnt;
1331  int* colpnt;
1332  int* colend;
1333  SCIP_Real val;
1334  int row;
1335  int c;
1336 
1337  assert(scip != NULL);
1338  assert(matrix != NULL);
1339  assert(lbdual != NULL);
1340  assert(ubdual != NULL);
1341  assert(0 <= startcol && startcol < matrix->ncols);
1342  assert(0 < stopcol && stopcol <= matrix->ncols);
1343  assert(excludevar != NULL);
1344  assert(mincolact != NULL);
1345  assert(maxcolact != NULL);
1346  assert(maxcolactinf != NULL);
1347  assert(mincolactinf != NULL);
1348 
1349  for( c = startcol; c < stopcol; c++ )
1350  {
1351  excludevar[c] = FALSE;
1352  mincolact[c] = 0;
1353  maxcolact[c] = 0;
1354  maxcolactinf[c] = 0;
1355  mincolactinf[c] = 0;
1356 
1357  /* no activity calculation for non-continuous variables */
1358  if( SCIPvarGetType(matrix->vars[c]) != SCIP_VARTYPE_CONTINUOUS )
1359  continue;
1360 
1361  colpnt = matrix->colmatind + matrix->colmatbeg[c];
1362  colend = colpnt + matrix->colmatcnt[c];
1363  valpnt = matrix->colmatval + matrix->colmatbeg[c];
1364 
1365  /* calculate column activities */
1366  for(; (colpnt < colend); colpnt++, valpnt++ )
1367  {
1368  row = *colpnt;
1369  val = *valpnt;
1370 
1371  if( matrix->isrhsinfinite[row] )
1372  {
1373  if( val > 0 )
1374  {
1375  if(SCIPisInfinity(scip, ubdual[row]))
1376  maxcolactinf[c]++;
1377  else
1378  maxcolact[c] += val * ubdual[row];
1379 
1380  if(SCIPisInfinity(scip, -lbdual[row]))
1381  mincolactinf[c]++;
1382  else
1383  mincolact[c] += val * lbdual[row];
1384  }
1385  else if( val < 0.0 )
1386  {
1387  if(SCIPisInfinity(scip, -lbdual[row]))
1388  maxcolactinf[c]++;
1389  else
1390  maxcolact[c] += val * lbdual[row];
1391 
1392  if(SCIPisInfinity(scip, ubdual[row]))
1393  mincolactinf[c]++;
1394  else
1395  mincolact[c] += val * ubdual[row];
1396  }
1397  }
1398  else if( !matrix->isrhsinfinite[row] )
1399  {
1400  excludevar[c] = TRUE;
1401  break;
1402  }
1403  }
1404 
1405  if( !excludevar[c] )
1406  {
1407  /* consider lower bounds on variables */
1408  if( SCIPisPositive(scip, SCIPvarGetLbGlobal(matrix->vars[c])) )
1409  maxcolactinf[c]++;
1410 
1411  /* consider upper bounds on variables */
1412  if( !SCIPisInfinity(scip, SCIPvarGetUbGlobal(matrix->vars[c])) )
1413  mincolactinf[c]++;
1414 
1415  /* update column activities */
1416  if( mincolactinf[c] > 0 )
1417  mincolact[c] = -SCIPinfinity(scip);
1418  if( maxcolactinf[c] > 0 )
1419  maxcolact[c] = SCIPinfinity(scip);
1420  }
1421  }
1422 }
1423 
1424 
1425 /** update bounds on dual variables */
1426 static
1427 void updateDualBounds(
1428  SCIP* scip, /**< SCIP main data structure */
1429  CONSTRAINTMATRIX* matrix, /**< matrix containing the constraints */
1430  SCIP_Real objval, /**< objective function value */
1431  SCIP_Real val, /**< matrix coefficient */
1432  int row, /**< row index */
1433  SCIP_Real mincolresact, /**< minimal column residual activity */
1434  SCIP_Real* lbdual, /**< dual lower bounds */
1435  SCIP_Real* ubdual, /**< dual upper bounds */
1436  int* boundchanges, /**< number of bound changes */
1437  SCIP_Bool* updateinfcnt /**< flag indicating to update infinity counters */
1438  )
1439 {
1440  SCIP_Real newlbdual;
1441  SCIP_Real newubdual;
1442 
1443  assert(scip != NULL);
1444  assert(matrix != NULL);
1445  assert(lbdual != NULL);
1446  assert(ubdual != NULL);
1447  assert(boundchanges != NULL);
1448  assert(updateinfcnt != NULL);
1449  assert(matrix->isrhsinfinite[row]);
1450 
1451  *updateinfcnt = FALSE;
1452 
1453  if( val > 0 )
1454  {
1455  if( !SCIPisInfinity(scip, mincolresact) &&
1456  !SCIPisInfinity(scip, -mincolresact) )
1457  {
1458  /* upper bound calculation on dual variable */
1459  newubdual = (objval - mincolresact) / val;
1460  if( newubdual < ubdual[row] )
1461  {
1462  if( SCIPisInfinity(scip, ubdual[row]) )
1463  *updateinfcnt = TRUE;
1464 
1465  ubdual[row] = newubdual;
1466  (*boundchanges)++;
1467  }
1468  }
1469  }
1470  else if( val < 0 )
1471  {
1472  if( !SCIPisInfinity(scip, mincolresact) &&
1473  !SCIPisInfinity(scip, -mincolresact) )
1474  {
1475  /* lower bound calculation on dual variable */
1476  newlbdual = (objval - mincolresact) / val;
1477  if( newlbdual > lbdual[row] )
1478  {
1479  if( SCIPisInfinity(scip, -lbdual[row]) )
1480  *updateinfcnt = TRUE;
1481 
1482  lbdual[row] = newlbdual;
1483  (*boundchanges)++;
1484  }
1485  }
1486  }
1487 }
1488 
1489 /** update minimal/maximal column activity infinity counters */
1490 static
1491 void infCounterUpdate(
1492  SCIP* scip, /**< SCIP main data structure */
1493  CONSTRAINTMATRIX* matrix, /**< matrix containing the constraints */
1494  SCIP_Real val, /**< matrix coefficient */
1495  int row, /**< row index */
1496  SCIP_Real* lbdual, /**< lower bounds of dual variables */
1497  SCIP_Real* ubdual, /**< upper bounds of dual variables */
1498  SCIP_Bool* excludevar, /**< indicating if variable is within an equation or ranged row */
1499  SCIP_Real* mincolact, /**< minimal column activities */
1500  SCIP_Real* maxcolact, /**< maximal column activities */
1501  int* maxcolactinf, /**< number of (positive) infinity contributions to maximal column activity */
1502  int* mincolactinf /**< number of (negative) infinity contributions to minimal column activity */
1503  )
1504 {
1505  SCIP_Real* valpnt;
1506  int* rowpnt;
1507  int* rowend;
1508  SCIP_Real aij;
1509  int c;
1510 
1511  assert(scip != NULL);
1512  assert(matrix != NULL);
1513  assert(0 <= row && row < matrix->nrows);
1514  assert(lbdual != NULL);
1515  assert(ubdual != NULL);
1516  assert(excludevar != NULL);
1517  assert(mincolact != NULL);
1518  assert(maxcolact != NULL);
1519  assert(maxcolactinf != NULL);
1520  assert(mincolactinf != NULL);
1521  assert(matrix->isrhsinfinite[row]);
1522 
1523  rowpnt = matrix->rowmatind + matrix->rowmatbeg[row];
1524  rowend = rowpnt + matrix->rowmatcnt[row];
1525  valpnt = matrix->rowmatval + matrix->rowmatbeg[row];
1526 
1527  /* look at all columns entries present within row and update the corresponding infinity counters.
1528  * if one counter gets to zero, then calculate this column activity completely new
1529  */
1530 
1531  if( val > 0 )
1532  {
1533  /* we did an upper dual bound change from +infinity to a value < infinity */
1534  for(; (rowpnt < rowend); rowpnt++, valpnt++ )
1535  {
1536  c = *rowpnt;
1537  aij = *valpnt;
1538 
1539  if( excludevar[c] || SCIPvarGetType(matrix->vars[c]) != SCIP_VARTYPE_CONTINUOUS )
1540  continue;
1541 
1542  if( aij > 0 )
1543  {
1544  assert(maxcolactinf[c] > 0);
1545  maxcolactinf[c]--;
1546 
1547  if( maxcolactinf[c] == 0 )
1548  {
1549  calcColActivity(scip, matrix, lbdual, ubdual, c, c+1, excludevar, mincolact, maxcolact,
1550  maxcolactinf, mincolactinf);
1551  }
1552  }
1553  else if( aij < 0 )
1554  {
1555  assert(mincolactinf[c] > 0);
1556  mincolactinf[c]--;
1557 
1558  if( mincolactinf[c] == 0 )
1559  {
1560  calcColActivity(scip, matrix, lbdual, ubdual, c, c+1, excludevar, mincolact, maxcolact,
1561  maxcolactinf, mincolactinf);
1562  }
1563  }
1564  }
1565  }
1566  else if( val < 0 )
1567  {
1568  /* we did a lower dual bound change from -infinity to a value > -infinity */
1569  for(; (rowpnt < rowend); rowpnt++, valpnt++ )
1570  {
1571  c = *rowpnt;
1572  aij = *valpnt;
1573 
1574  if( excludevar[c] || SCIPvarGetType(matrix->vars[c]) != SCIP_VARTYPE_CONTINUOUS )
1575  continue;
1576 
1577  if( aij > 0 )
1578  {
1579  assert(mincolactinf[c] > 0);
1580  mincolactinf[c]--;
1581 
1582  if( mincolactinf[c] == 0 )
1583  calcColActivity(scip, matrix, lbdual, ubdual, c, c+1, excludevar, mincolact, maxcolact,
1584  maxcolactinf, mincolactinf);
1585  }
1586  else if( aij < 0 )
1587  {
1588  assert(maxcolactinf[c] > 0);
1589  maxcolactinf[c]--;
1590 
1591  if( maxcolactinf[c] == 0 )
1592  calcColActivity(scip, matrix, lbdual, ubdual, c, c+1, excludevar, mincolact, maxcolact,
1593  maxcolactinf, mincolactinf);
1594  }
1595  }
1596  }
1597 }
1598 
1599 /** dual bound strengthening on continuous variables */
1600 static
1601 SCIP_RETCODE dualBoundStrengthening(
1602  SCIP* scip, /**< SCIP main data structure */
1603  CONSTRAINTMATRIX* matrix, /**< matrix containing the constraints */
1604  FIXINGDIRECTION* varstofix, /**< array holding information for later upper/lower bound fixing */
1605  int* nfitsinglecols, /**< number of continuous singleton columns */
1606  int* npossiblefixings /**< found number of possible fixings */
1607  )
1608 {
1609  SCIP_Real* valpnt;
1610  SCIP_Real* lbdual;
1611  SCIP_Real* ubdual;
1612  SCIP_Real* mincolact;
1613  SCIP_Real* maxcolact;
1614  SCIP_Bool* excludevar;
1615  SCIP_Bool* varissingcol;
1616  int* maxcolactinf;
1617  int* mincolactinf;
1618  int* colpnt;
1619  int* colend;
1620  int cnt;
1621  int boundchanges;
1622  int loops;
1623  int c;
1624  int r;
1625 
1626  assert(scip != NULL);
1627  assert(matrix != NULL);
1628  assert(varstofix != NULL);
1629  assert(nfitsinglecols != NULL);
1630  assert(npossiblefixings != NULL);
1631 
1632  /* all variables must have a lower bound >= 0 */
1633  for( c = 0; c < matrix->ncols; c++ )
1634  {
1635  if( SCIPisNegative(scip, SCIPvarGetLbGlobal(matrix->vars[c])) )
1636  return SCIP_OKAY;
1637  }
1638 
1639  SCIP_CALL( SCIPallocBufferArray(scip, &varissingcol, matrix->ncols) );
1640  SCIP_CALL( SCIPallocBufferArray(scip, &excludevar, matrix->ncols) );
1641  SCIP_CALL( SCIPallocBufferArray(scip, &mincolact, matrix->ncols) );
1642  SCIP_CALL( SCIPallocBufferArray(scip, &maxcolact, matrix->ncols) );
1643  SCIP_CALL( SCIPallocBufferArray(scip, &maxcolactinf, matrix->ncols) );
1644  SCIP_CALL( SCIPallocBufferArray(scip, &mincolactinf, matrix->ncols) );
1645  SCIP_CALL( SCIPallocBufferArray(scip, &lbdual, matrix->nrows) );
1646  SCIP_CALL( SCIPallocBufferArray(scip, &ubdual, matrix->nrows) );
1647 
1648  for( r = 0; r < matrix->nrows; r++ )
1649  {
1650  /* initialize dual bounds */
1651  lbdual[r] = 0.0;
1652  ubdual[r] = SCIPinfinity(scip);
1653  }
1654 
1655  /* calculate bounds on dual variables from singleton continuous columns */
1656  cnt = 0;
1657  for( c = 0; c < matrix->ncols; c++ )
1658  {
1659  int row;
1660 
1661  row = *(matrix->colmatind + matrix->colmatbeg[c]);
1662  varissingcol[c] = FALSE;
1663 
1664  if( matrix->colmatcnt[c] == 1 && matrix->isrhsinfinite[row] )
1665  {
1666  varissingcol[c] = TRUE;
1667 
1668  if( SCIPvarGetType(matrix->vars[c]) == SCIP_VARTYPE_CONTINUOUS &&
1669  /*SCIPisZero(scip, SCIPvarGetLbGlobal(matrix->vars[c])) &&*/
1670  SCIPisInfinity(scip, SCIPvarGetUbGlobal(matrix->vars[c])) )
1671  {
1672  SCIP_Real objval;
1673  SCIP_Real val;
1674  SCIP_Real newubdual;
1675  SCIP_Real newlbdual;
1676 
1677  objval = SCIPvarGetObj(matrix->vars[c]);
1678  val = *(matrix->colmatval + matrix->colmatbeg[c]);
1679 
1680  if( val > 0 )
1681  {
1682  newubdual = objval/val;
1683  if( newubdual < ubdual[row] )
1684  {
1685  ubdual[row] = newubdual;
1686  cnt++;
1687  }
1688  }
1689  else if( val < 0 )
1690  {
1691  newlbdual = objval/val;
1692  if( newlbdual > lbdual[row] )
1693  {
1694  lbdual[row] = newlbdual;
1695  cnt++;
1696  }
1697  }
1698  }
1699  }
1700  }
1701  (*nfitsinglecols) = cnt;
1702 
1703  /* do dual bound strengthening only if fitting singleton continuous variables are present */
1704  if( cnt > 0 )
1705  {
1706  loops = 0;
1707  boundchanges = 1;
1708 
1709  /* continue dual bound strengthening only if some bounds were change in the last round and
1710  * a maximal number of processing loops is not exceeded
1711  */
1712  while( boundchanges && loops < MAX_LOOPS )
1713  {
1714  loops++;
1715  boundchanges = 0;
1716 
1717  /* calculate minimal and maximal column activity */
1718  calcColActivity(scip, matrix, lbdual, ubdual, 0, matrix->ncols, excludevar, mincolact, maxcolact,
1719  maxcolactinf, mincolactinf);
1720 
1721  for( c = 0 ; c < matrix->ncols; c++ )
1722  {
1723  SCIP_Real objval;
1724 
1725  /* do no dual bound strengthing for variables which are present within
1726  * equalities or ranged rows, for singleton columns and non-continuous variables
1727  */
1728  if( excludevar[c] || varissingcol[c] || (SCIPvarGetType(matrix->vars[c]) != SCIP_VARTYPE_CONTINUOUS))
1729  continue;
1730 
1731  objval = SCIPvarGetObj(matrix->vars[c]);
1732 
1733  colpnt = matrix->colmatind + matrix->colmatbeg[c];
1734  colend = colpnt + matrix->colmatcnt[c];
1735  valpnt = matrix->colmatval + matrix->colmatbeg[c];
1736 
1737  for(; (colpnt < colend); colpnt++, valpnt++ )
1738  {
1739  int row;
1740  SCIP_Real val;
1741  SCIP_Real mincolresact;
1742  SCIP_Real maxcolresact;
1743  SCIP_Bool updateinfcnt;
1744 
1745  row = *colpnt;
1746  val = *valpnt;
1747  mincolresact = -SCIPinfinity(scip);
1748  maxcolresact = SCIPinfinity(scip);
1749  updateinfcnt = FALSE;
1750 
1751  /* calulate column activity residuals */
1752  calcColActivityResiduals(scip, matrix, c, row, val, lbdual, ubdual, mincolact, maxcolact,
1753  maxcolactinf, mincolactinf, &mincolresact, &maxcolresact);
1754 
1755  /* update dual bounds */
1756  updateDualBounds(scip, matrix, objval, val, row, mincolresact,
1757  lbdual, ubdual, &boundchanges, &updateinfcnt);
1758 
1759  /* update infinity counters if bound changed properly */
1760  if( updateinfcnt )
1761  infCounterUpdate(scip, matrix, val, row, lbdual, ubdual, excludevar, mincolact, maxcolact,
1762  maxcolactinf, mincolactinf);
1763  }
1764  }
1765  }
1766 
1767  if( boundchanges > 0 )
1768  {
1769  /* calculate minimal/maximal column activity the last time */
1770  calcColActivity(scip, matrix, lbdual, ubdual, 0, matrix->ncols, excludevar, mincolact, maxcolact,
1771  maxcolactinf, mincolactinf);
1772  }
1773 
1774  for( c = 0; c < matrix->ncols; c++ )
1775  {
1776  SCIP_Real objval;
1777  objval = SCIPvarGetObj(matrix->vars[c]);
1778 
1779  /* exclude non-continuous variables and variables which are
1780  present within equalities */
1781  if( (SCIPvarGetType(matrix->vars[c]) != SCIP_VARTYPE_CONTINUOUS) || excludevar[c] )
1782  continue;
1783 
1784  /* apply complementary slackness: (yA-c)_i > 0 => x_i = 0 */
1785  if( SCIPisLT(scip, maxcolact[c], objval) && varstofix[c] == NOFIX )
1786  {
1787  varstofix[c] = FIXATLB;
1788  (*npossiblefixings)++;
1789  }
1790  }
1791  }
1792 
1793  SCIPfreeBufferArray(scip, &ubdual);
1794  SCIPfreeBufferArray(scip, &lbdual);
1795  SCIPfreeBufferArray(scip, &mincolactinf);
1796  SCIPfreeBufferArray(scip, &maxcolactinf);
1797  SCIPfreeBufferArray(scip, &maxcolact);
1798  SCIPfreeBufferArray(scip, &mincolact);
1799  SCIPfreeBufferArray(scip, &excludevar);
1800  SCIPfreeBufferArray(scip, &varissingcol);
1801 
1802  return SCIP_OKAY;
1803 }
1804 
1805 /*
1806  * Callback methods of presolver
1807  */
1808 
1809 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
1810 static
1811 SCIP_DECL_PRESOLCOPY(presolCopyDualinfer)
1812 { /*lint --e{715}*/
1813  assert(scip != NULL);
1814  assert(presol != NULL);
1815  assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
1816 
1817  /* call inclusion method of presolver */
1818  SCIP_CALL( SCIPincludePresolDualinfer(scip) );
1819 
1820  return SCIP_OKAY;
1821 }
1822 
1823 /** execution method of presolver */
1824 static
1825 SCIP_DECL_PRESOLEXEC(presolExecDualinfer)
1826 { /*lint --e{715}*/
1827  CONSTRAINTMATRIX* matrix;
1828  SCIP_Bool initialized;
1829 
1830  assert(result != NULL);
1831  *result = SCIP_DIDNOTRUN;
1832 
1833  if( (SCIPgetStage(scip) != SCIP_STAGE_PRESOLVING) || SCIPinProbing(scip) )
1834  return SCIP_OKAY;
1835 
1836  *result = SCIP_DIDNOTFIND;
1837 
1838  /* initialize constraint matrix */
1839  matrix = NULL;
1840  initialized = FALSE;
1841  SCIP_CALL( initMatrix(scip, &matrix, &initialized) );
1842 
1843  if( initialized )
1844  {
1845  FIXINGDIRECTION* varstofix;
1846  int nconvarsfixed;
1847  int nintvarsfixed;
1848  int nbinvarsfixed;
1849  int npossiblefixings;
1850  int nfitsinglecols;
1851  int i;
1852 
1853  nconvarsfixed = 0;
1854  nintvarsfixed = 0;
1855  nbinvarsfixed = 0;
1856  npossiblefixings = 0;
1857  nfitsinglecols = 0;
1858 
1859  SCIP_CALL( SCIPallocBufferArray(scip, &varstofix, matrix->ncols) );
1860 
1861  /* initialize varstofix to 0 (= NOFIX) */
1862  BMSclearMemoryArray(varstofix, matrix->ncols);
1863 
1864  /* dual cost fixing */
1865  SCIP_CALL( costFixing(scip, matrix, varstofix, &nfitsinglecols, &npossiblefixings) );
1866 
1867  if( SCIPgetNContVars(scip) > 1 )
1868  {
1869  /* dual bound strengthening */
1870  SCIP_CALL( dualBoundStrengthening(scip, matrix, varstofix, &nfitsinglecols, &npossiblefixings) );
1871  }
1872 
1873  if( npossiblefixings > 0 )
1874  {
1875  /* look for fixable variables */
1876  for( i = matrix->ncols - 1; i >= 0; --i )
1877  {
1878  SCIP_Bool infeasible;
1879  SCIP_Bool fixed;
1880  SCIP_VAR* var;
1881 
1882  if( varstofix[i] == FIXATLB )
1883  {
1884  SCIP_Real lb;
1885 
1886  var = matrix->vars[i];
1887  lb = SCIPvarGetLbLocal(var);
1888  assert(SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS || SCIPisFeasIntegral(scip, lb));
1889 
1890  /* fix at lower bound */
1891  SCIP_CALL( SCIPfixVar(scip, var, lb, &infeasible, &fixed) );
1892  if( infeasible )
1893  {
1894  SCIPdebugMessage(" -> infeasible fixing\n");
1895  *result = SCIP_CUTOFF;
1896  break;
1897  }
1898  assert(fixed);
1899  (*nfixedvars)++;
1900  *result = SCIP_SUCCESS;
1901 
1902  if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS )
1903  nconvarsfixed++;
1904  else if( SCIPvarGetType(var) == SCIP_VARTYPE_BINARY )
1905  nbinvarsfixed++;
1906  else
1907  nintvarsfixed++;
1908  }
1909  else if( varstofix[i] == FIXATUB )
1910  {
1911  SCIP_Real ub;
1912 
1913  var = matrix->vars[i];
1914  ub = SCIPvarGetUbLocal(var);
1915  assert(SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS || SCIPisFeasIntegral(scip, ub));
1916 
1917  /* fix at upper bound */
1918  SCIP_CALL( SCIPfixVar(scip, var, ub, &infeasible, &fixed) );
1919  if( infeasible )
1920  {
1921  SCIPdebugMessage(" -> infeasible fixing\n");
1922  *result = SCIP_CUTOFF;
1923  break;
1924  }
1925  assert(fixed);
1926  (*nfixedvars)++;
1927  *result = SCIP_SUCCESS;
1928 
1929  if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS )
1930  nconvarsfixed++;
1931  else if( SCIPvarGetType(var) == SCIP_VARTYPE_BINARY )
1932  nbinvarsfixed++;
1933  else
1934  nintvarsfixed++;
1935  }
1936  }
1937  }
1938 
1939  SCIPfreeBufferArray(scip, &varstofix);
1940 
1941  if( (*result) != SCIP_CUTOFF && (nconvarsfixed + nintvarsfixed + nbinvarsfixed) > 0 )
1942  {
1943  SCIPdebugMessage("### %d vars [%d column singletons] ===>>> fixed [cont: %d, int: %d, bin: %d]\n",
1944  matrix->ncols, nfitsinglecols, nconvarsfixed, nintvarsfixed, nbinvarsfixed);
1945  }
1946  }
1947 
1948  freeMatrix(scip, &matrix);
1949 
1950  return SCIP_OKAY;
1951 }
1952 
1953 
1954 /*
1955  * presolver specific interface methods
1956  */
1957 
1958 /** creates the dual inference presolver and includes it in SCIP */
1959 SCIP_RETCODE SCIPincludePresolDualinfer(
1960  SCIP* scip /**< SCIP data structure */
1961  )
1962 {
1963  SCIP_PRESOLDATA* presoldata;
1964  SCIP_PRESOL* presol;
1965 
1966  presoldata = NULL;
1967 
1968  /* include presolver */
1969  SCIP_CALL( SCIPincludePresolBasic(scip, &presol, PRESOL_NAME, PRESOL_DESC, PRESOL_PRIORITY, PRESOL_MAXROUNDS,
1970  PRESOL_DELAY, presolExecDualinfer, presoldata) );
1971  SCIP_CALL( SCIPsetPresolCopy(scip, presol, presolCopyDualinfer) );
1972 
1973  return SCIP_OKAY;
1974 }
1975