# SCIP

Solving Constraint Integer Programs

presol_redvub.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-2020 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file presol_redvub.c
17  * @ingroup DEFPLUGINS_PRESOL
18  * @brief remove redundant variable upper bound constraints
19  * @author Dieter Weninger
20  *
21  * This presolver looks for dominating variable bound constraints
22  * on the same continuous variable and discards them. For example let x be a
23  * continuous variable and y, y' are binary variables. In addition, let two variable
24  * upper bound constraints ax - by <= e and cx - dy' <= f are given. If
25  * ax - by <= e implies cx - dy' <= f, then we can remove the second constraint
26  * and substitute/aggregate y' := y. The same can be done with variable lower
27  * bound constraints.
28  *
29  */
30
31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32
33 #include "blockmemshell/memory.h"
34 #include "scip/presol_redvub.h"
35 #include "scip/pub_matrix.h"
36 #include "scip/pub_message.h"
37 #include "scip/pub_var.h"
38 #include "scip/scip_cons.h"
39 #include "scip/scip_general.h"
40 #include "scip/scip_mem.h"
41 #include "scip/scip_message.h"
42 #include "scip/scip_nlp.h"
43 #include "scip/scip_numerics.h"
44 #include "scip/scip_presol.h"
45 #include "scip/scip_pricer.h"
46 #include "scip/scip_prob.h"
47 #include "scip/scip_probing.h"
48 #include "scip/scip_var.h"
49
50 #define PRESOL_NAME "redvub"
51 #define PRESOL_DESC "detect redundant variable bound constraints"
52 #define PRESOL_PRIORITY -9000000 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */
53 #define PRESOL_MAXROUNDS 0 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
54 #define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */
55
56 #define MAXPAIRCOMP 1000 /**< maximal number of pairwise comparisons */
57
58 /*
59  * Local methods
60  */
61
62 /** verify if the constraint is a variable upper bound constraint */
63 static
65  SCIP* scip, /**< SCIP main data structure */
66  SCIP_MATRIX* matrix, /**< matrix instance */
67  int row, /**< row index */
68  SCIP_Real* lowthreshold, /**< low switching threshold */
69  SCIP_Real* highthreshold, /**< high switching threshold */
70  int* conidx, /**< variable index of continuous variable */
71  int* binidx /**< variable index of binary variable */
72  )
73 {
74  SCIP_Real* valpnt;
75  int* rowpnt;
76  SCIP_Bool isvub;
77
78  assert(scip != NULL);
79  assert(matrix != NULL);
80  assert(0 <= row && row < SCIPmatrixGetNRows(matrix));
81  assert(lowthreshold != NULL);
82  assert(highthreshold != NULL);
83  assert(conidx != NULL);
84  assert(binidx != NULL);
85
86  isvub = FALSE;
87
88  if( SCIPmatrixGetRowNNonzs(matrix, row) == 2 && SCIPmatrixIsRowRhsInfinity(matrix, row) )
89  {
90  SCIP_VARTYPE type1;
91  SCIP_VARTYPE type2;
92  int idx1;
93  int idx2;
94  SCIP_VAR* var1;
95  SCIP_VAR* var2;
96  SCIP_Real val1;
97  SCIP_Real val2;
98
99  rowpnt = SCIPmatrixGetRowIdxPtr(matrix, row);
100  valpnt = SCIPmatrixGetRowValPtr(matrix, row);
101
102  idx1 = *rowpnt;
103  val1 = *valpnt;
104  var1 = SCIPmatrixGetVar(matrix, idx1);
105  type1 = SCIPvarGetType(var1);
106
107  rowpnt++;
108  valpnt++;
109
110  idx2 = *rowpnt;
111  val2 = *valpnt;
112  var2 = SCIPmatrixGetVar(matrix, idx2);
113  type2 = SCIPvarGetType(var2);
114
115  /* we claim that the vub has the structure ax + cy >= b
116  * with a<0, c>0, x continuous, x>=0, y binary and obj(y)>=0
117  */
118  if( (type1 == SCIP_VARTYPE_CONTINUOUS && type2 == SCIP_VARTYPE_BINARY)
119  && val1 < 0.0 && val2 > 0.0 && SCIPisGE(scip, SCIPvarGetLbGlobal(var1), 0.0)
120  && SCIPisGE(scip, SCIPvarGetObj(var2), 0.0) )
121  {
122  *lowthreshold = SCIPmatrixGetRowLhs(matrix, row) / val1;
123  *highthreshold = (SCIPmatrixGetRowLhs(matrix, row) - val2) / val1;
124  *conidx = idx1;
125  *binidx = idx2;
126  isvub = TRUE;
127  }
128  else if( (type1 == SCIP_VARTYPE_BINARY && type2 == SCIP_VARTYPE_CONTINUOUS)
129  && val1 > 0.0 && val2 < 0.0 && SCIPisGE(scip, SCIPvarGetLbGlobal(var2), 0.0)
130  && SCIPisGE(scip, SCIPvarGetObj(var1), 0.0) )
131  {
132  *lowthreshold = SCIPmatrixGetRowLhs(matrix, row) / val2;
133  *highthreshold = (SCIPmatrixGetRowLhs(matrix, row) - val1) / val2;
134  *conidx = idx2;
135  *binidx = idx1;
136  isvub = TRUE;
137  }
138  }
139
140  return isvub;
141 }
142
143 /** verify if the constraint is a variable lower bound constraint */
144 static
146  SCIP* scip, /**< SCIP main data structure */
147  SCIP_MATRIX* matrix, /**< matrix instance */
148  int row, /**< row index */
149  SCIP_Real* lowthreshold, /**< low switching threshold */
150  SCIP_Real* highthreshold, /**< high switching threshold */
151  int* conidx, /**< variable index of continuous variable */
152  int* binidx /**< variable index of binary variable */
153  )
154 {
155  SCIP_Real* valpnt;
156  int* rowpnt;
157  SCIP_Bool isvlb;
158
159  assert(scip != NULL);
160  assert(matrix != NULL);
161  assert(0 <= row && row < SCIPmatrixGetNRows(matrix));
162  assert(lowthreshold != NULL);
163  assert(highthreshold != NULL);
164  assert(conidx != NULL);
165  assert(binidx != NULL);
166
167  isvlb = FALSE;
168
169  if( SCIPmatrixGetRowNNonzs(matrix, row) == 2 && SCIPmatrixIsRowRhsInfinity(matrix, row) )
170  {
171  SCIP_VARTYPE type1;
172  SCIP_VARTYPE type2;
173  int idx1;
174  int idx2;
175  SCIP_VAR* var1;
176  SCIP_VAR* var2;
177  SCIP_Real val1;
178  SCIP_Real val2;
179
180  rowpnt = SCIPmatrixGetRowIdxPtr(matrix, row);
181  valpnt = SCIPmatrixGetRowValPtr(matrix, row);
182
183  idx1 = *rowpnt;
184  val1 = *valpnt;
185  var1 = SCIPmatrixGetVar(matrix, idx1);
186  type1 = SCIPvarGetType(var1);
187
188  rowpnt++;
189  valpnt++;
190
191  idx2 = *rowpnt;
192  val2 = *valpnt;
193  var2 = SCIPmatrixGetVar(matrix, idx2);
194  type2 = SCIPvarGetType(var2);
195
196  /* we claim that the vlb has the structure ax + cy >= b
197  * with a>0, c<0, x continuous, x>=0, y binary and obj(y)>=0
198  */
199  if( (type1 == SCIP_VARTYPE_CONTINUOUS && type2 == SCIP_VARTYPE_BINARY)
200  && val1 > 0.0 && val2 < 0.0 && SCIPisGE(scip, SCIPvarGetLbGlobal(var1), 0.0)
201  && SCIPisGE(scip, SCIPvarGetObj(var2), 0.0) )
202  {
203  *lowthreshold = SCIPmatrixGetRowLhs(matrix, row) / val1;
204  *highthreshold = (SCIPmatrixGetRowLhs(matrix, row) - val2) / val1;
205  *conidx = idx1;
206  *binidx = idx2;
207  isvlb = TRUE;
208  }
209  else if( (type1 == SCIP_VARTYPE_BINARY && type2 == SCIP_VARTYPE_CONTINUOUS)
210  && val1 < 0.0 && val2 > 0.0 && SCIPisGE(scip, SCIPvarGetLbGlobal(var2), 0.0)
211  && SCIPisGE(scip, SCIPvarGetObj(var1), 0.0) )
212  {
213  *lowthreshold = SCIPmatrixGetRowLhs(matrix, row) / val2;
214  *highthreshold = (SCIPmatrixGetRowLhs(matrix, row) - val1) / val2;
215  *conidx = idx2;
216  *binidx = idx1;
217  isvlb = TRUE;
218  }
219  }
220
221  return isvlb;
222 }
223
224
225 /** searches for variable upper bound constraints on the same continuous variable with a dominance relation */
226 static
228  SCIP* scip, /**< SCIP main data structure */
229  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
230  int nvubs, /**< number of vubs */
231  int* vubs, /**< row indices of the vubs */
232  SCIP_Real* lowthresholds, /**< low switching thresholds */
233  SCIP_Real* highthresholds, /**< high switching thresholds */
234  int* conidxs, /**< variable indexes of continuous variable */
235  int* binidxs, /**< variable indexes of binary variable */
236  int* nvaragg, /**< number of variables for aggregation */
237  SCIP_Bool* isvartoagg, /**< flags indicating if variable could be aggregated */
238  SCIP_VAR** aggvars, /**< pointers to the variables by which the aggregation should be done */
239  int* ndeletecons, /**< number of deleteable constraints */
240  SCIP_Bool* deletecons /**< flags which constraints could be deleted */
241  )
242 {
243  int i;
244  int j;
245  SCIP_Bool uselinearscan;
246
247  assert(scip != NULL);
248  assert(matrix != NULL);
249  assert(vubs != NULL);
250  assert(nvubs >= 2);
251  assert(lowthresholds != NULL);
252  assert(highthresholds != NULL);
253  assert(conidxs != NULL);
254  assert(binidxs != NULL);
255  assert(nvaragg != NULL);
256  assert(isvartoagg != NULL);
257  assert(aggvars != NULL);
258  assert(ndeletecons != NULL);
259  assert(deletecons != NULL);
260
261  /* use pairwise comparison only for a small number of vub constraints */
262  if( nvubs >= MAXPAIRCOMP )
263  uselinearscan = TRUE;
264  else
265  uselinearscan = FALSE;
266
267  for( i = 0; i < nvubs; i++ )
268  {
269  for( j = i+1; j < nvubs; j++ )
270  {
271  SCIP_VAR* var1;
272  SCIP_VAR* var2;
273
274  if( !SCIPisEQ(scip, lowthresholds[i], lowthresholds[j]) )
275  continue;
276
277  var1 = SCIPmatrixGetVar(matrix, binidxs[i]);
278  var2 = SCIPmatrixGetVar(matrix, binidxs[j]);
279
280  /* make sure that the binary variables switch synchronously */
281  if((SCIPmatrixGetColNDownlocks(matrix, binidxs[j]) == 1 &&
282  SCIPmatrixGetColNDownlocks(matrix, binidxs[i]) == 1 &&
283  SCIPmatrixGetColNUplocks(matrix, binidxs[j]) == 0 &&
284  SCIPmatrixGetColNUplocks(matrix, binidxs[i]) == 0) ||
285  (SCIPvarsHaveCommonClique(var1, FALSE, var2, TRUE, TRUE) &&
286  SCIPvarsHaveCommonClique(var1, TRUE, var2, FALSE, TRUE)) )
287  {
288  if( SCIPisLE(scip, highthresholds[i], highthresholds[j]) )
289  {
290 #ifdef SCIP_DEBUG
291  SCIPdebugMsg(scip, "Aggregate variable %s by %s\n", SCIPvarGetName(var2), SCIPvarGetName(var1));
292  SCIPdebugMsg(scip, "Delete variable upper bound constraint:\n");
293  SCIP_CALL( SCIPprintCons(scip, SCIPmatrixGetCons(matrix, vubs[j]), NULL));
294  SCIPinfoMessage(scip, NULL, "\n");
295 #endif
296
297  isvartoagg[binidxs[j]] = TRUE;
298  aggvars[binidxs[j]] = SCIPmatrixGetVar(matrix, binidxs[i]);
299  (*nvaragg)++;
300
301  deletecons[vubs[j]] = TRUE;
302  (*ndeletecons)++;
303  }
304  else
305  {
306  assert(SCIPisGT(scip, highthresholds[i], highthresholds[j]));
307 #ifdef SCIP_DEBUG
308  SCIPdebugMsg(scip, "Aggregate variable %s by %s\n", SCIPvarGetName(var1), SCIPvarGetName(var2));
309  SCIPdebugMsg(scip, "Delete variable upper bound constraint:\n");
310  SCIP_CALL( SCIPprintCons(scip, SCIPmatrixGetCons(matrix, vubs[i]), NULL));
311  SCIPinfoMessage(scip, NULL, "\n");
312 #endif
313
314  isvartoagg[binidxs[i]] = TRUE;
315  aggvars[binidxs[i]] = SCIPmatrixGetVar(matrix, binidxs[j]);
316  (*nvaragg)++;
317
318  deletecons[vubs[i]] = TRUE;
319  (*ndeletecons)++;
320  }
321  }
322
323  if( uselinearscan )
324  break;
325  }
326  }
327
328  return SCIP_OKAY;
329 }
330
331 /** searches for variable lower bound constraints on the same continuous variable with a dominance relation */
332 static
334  SCIP* scip, /**< SCIP main data structure */
335  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
336  int nvlbs, /**< number of vlbs */
337  int* vlbs, /**< row indices of the vlbs */
338  SCIP_Real* lowthresholds, /**< low switching thresholds */
339  SCIP_Real* highthresholds, /**< high switching thresholds */
340  int* conidxs, /**< variable indexes of continuous variable */
341  int* binidxs, /**< variable indexes of binary variable */
342  int* nvaragg, /**< number of variables for aggregation */
343  SCIP_Bool* isvartoagg, /**< flags indicating if variable could be aggregated */
344  SCIP_VAR** aggvars, /**< pointers to the variables by which the aggregation should be done */
345  int* ndeletecons, /**< number of deleteable constraints */
346  SCIP_Bool* deletecons /**< flags which constraints could be deleted */
347
348  )
349 {
350  int i;
351  int j;
352  SCIP_Bool uselinearscan;
353
354  assert(scip != NULL);
355  assert(matrix != NULL);
356  assert(vlbs != NULL);
357  assert(nvlbs >= 2);
358  assert(lowthresholds != NULL);
359  assert(highthresholds != NULL);
360  assert(conidxs != NULL);
361  assert(binidxs != NULL);
362  assert(nvaragg != NULL);
363  assert(isvartoagg != NULL);
364  assert(aggvars != NULL);
365  assert(ndeletecons != NULL);
366  assert(deletecons != NULL);
367
368  /* use pairwise comparison only for a small number of vlb constraints */
369  if( nvlbs >= MAXPAIRCOMP )
370  uselinearscan = TRUE;
371  else
372  uselinearscan = FALSE;
373
374  for( i = 0; i < nvlbs; i++ )
375  {
376  for( j = i+1; j < nvlbs; j++ )
377  {
378  SCIP_VAR* var1;
379  SCIP_VAR* var2;
380
381  if( !SCIPisEQ(scip, lowthresholds[i], lowthresholds[j]) )
382  continue;
383
384  var1 = SCIPmatrixGetVar(matrix, binidxs[i]);
385  var2 = SCIPmatrixGetVar(matrix, binidxs[j]);
386
387  /* make sure that the binary variables switch synchronously */
388  if((SCIPmatrixGetColNUplocks(matrix, binidxs[j]) == 1 &&
389  SCIPmatrixGetColNUplocks(matrix, binidxs[i]) == 1 &&
390  SCIPmatrixGetColNDownlocks(matrix, binidxs[j]) == 0 &&
391  SCIPmatrixGetColNDownlocks(matrix, binidxs[i]) == 0) ||
392  (SCIPvarsHaveCommonClique(var1, FALSE, var2, TRUE, TRUE) &&
393  SCIPvarsHaveCommonClique(var1, TRUE, var2, FALSE, TRUE)) )
394  {
395  if( SCIPisGE(scip, highthresholds[i], highthresholds[j]) )
396  {
397 #ifdef SCIP_DEBUG
398  SCIPdebugMsg(scip, "Aggregate variable %s by %s\n", SCIPvarGetName(var2), SCIPvarGetName(var1));
399  SCIPdebugMsg(scip, "Delete variable lower bound constraint:\n");
400  SCIP_CALL( SCIPprintCons(scip, SCIPmatrixGetCons(matrix, vlbs[j]), NULL));
401  SCIPinfoMessage(scip, NULL, "\n");
402 #endif
403
404  isvartoagg[binidxs[j]] = TRUE;
405  aggvars[binidxs[j]] = SCIPmatrixGetVar(matrix, binidxs[i]);
406  (*nvaragg)++;
407
408  deletecons[vlbs[j]] = TRUE;
409  (*ndeletecons)++;
410  }
411  else
412  {
413  assert(SCIPisLT(scip, highthresholds[i], highthresholds[j]));
414 #ifdef SCIP_DEBUG
415  SCIPdebugMsg(scip, "Aggregate variable %s by %s\n", SCIPvarGetName(var1), SCIPvarGetName(var2));
416  SCIPdebugMsg(scip, "Delete variable lower bound constraint:\n");
417  SCIP_CALL( SCIPprintCons(scip, SCIPmatrixGetCons(matrix, vlbs[i]), NULL));
418  SCIPinfoMessage(scip, NULL, "\n");
419 #endif
420
421  isvartoagg[binidxs[i]] = TRUE;
422  aggvars[binidxs[i]] = SCIPmatrixGetVar(matrix, binidxs[j]);
423  (*nvaragg)++;
424
425  deletecons[vlbs[i]] = TRUE;
426  (*ndeletecons)++;
427  }
428  }
429
430  if( uselinearscan )
431  break;
432  }
433  }
434
435  return SCIP_OKAY;
436 }
437
438 /** find variable aggregations and redundant variable bound constraints */
439 static
441  SCIP* scip, /**< SCIP main data structure */
442  SCIP_MATRIX* matrix, /**< constraint matrix */
443  int* nvaragg, /**< number of redundant variables */
444  SCIP_Bool* isvartoagg, /**< flags indicating which variables could be substituted/aggregated */
445  SCIP_VAR** aggvars, /**< pointers to the variables by which the aggregation should be done */
446  int* ndeletecons, /**< number of redundant constraints */
447  SCIP_Bool* deletecons /**< flags indicating which constraints could be deleted */
448  )
449 {
450  int c;
451  int* colpnt;
452  int* colend;
453  int* vbcons;
454  int nvbcons;
455  int ncols;
456  int nrows;
457  SCIP_Real* lowthresholds;
458  SCIP_Real* highthresholds;
459  int* conidxs;
460  int* binidxs;
461
462  ncols = SCIPmatrixGetNColumns(matrix);
463  nrows = SCIPmatrixGetNRows(matrix);
464
465  SCIP_CALL( SCIPallocBufferArray(scip, &binidxs, nrows) );
466  SCIP_CALL( SCIPallocBufferArray(scip, &conidxs, nrows) );
467  SCIP_CALL( SCIPallocBufferArray(scip, &lowthresholds, nrows) );
468  SCIP_CALL( SCIPallocBufferArray(scip, &highthresholds, nrows) );
469  SCIP_CALL( SCIPallocBufferArray(scip, &vbcons, nrows) );
470
471  for( c = 0; c < ncols; c++ )
472  {
473  SCIP_VAR* var;
474
475  var = SCIPmatrixGetVar(matrix, c);
476
478  continue;
479
480  /* search vubs per variable */
481  nvbcons = 0;
482  colpnt = SCIPmatrixGetColIdxPtr(matrix, c);
483  colend = colpnt + SCIPmatrixGetColNNonzs(matrix, c);
484  for( ; (colpnt < colend); colpnt++ )
485  {
486  SCIP_Real lowthreshold;
487  SCIP_Real highthreshold;
488  int conidx;
489  int binidx;
490
491  if( isVub(scip, matrix, *colpnt, &lowthreshold, &highthreshold, &conidx, &binidx) )
492  {
493  vbcons[nvbcons] = *colpnt;
494  lowthresholds[nvbcons] = lowthreshold;
495  highthresholds[nvbcons] = highthreshold;
496  conidxs[nvbcons] = conidx;
497  binidxs[nvbcons] = binidx;
498  nvbcons++;
499  }
500  }
501  if( nvbcons >= 2 )
502  {
503  SCIP_CALL( detectDominatingVubs(scip, matrix, nvbcons, vbcons,
504  lowthresholds, highthresholds, conidxs, binidxs,
505  nvaragg, isvartoagg, aggvars, ndeletecons, deletecons) );
506  }
507
508  /* search vlbs per variable */
509  nvbcons = 0;
510  colpnt = SCIPmatrixGetColIdxPtr(matrix, c);
511  colend = colpnt + SCIPmatrixGetColNNonzs(matrix, c);
512  for( ; (colpnt < colend); colpnt++ )
513  {
514  SCIP_Real lowthreshold;
515  SCIP_Real highthreshold;
516  int conidx;
517  int binidx;
518
519  if( isVlb(scip, matrix, *colpnt, &lowthreshold, &highthreshold, &conidx, &binidx) )
520  {
521  vbcons[nvbcons] = *colpnt;
522  lowthresholds[nvbcons] = lowthreshold;
523  highthresholds[nvbcons] = highthreshold;
524  conidxs[nvbcons] = conidx;
525  binidxs[nvbcons] = binidx;
526  nvbcons++;
527  }
528  }
529  if( nvbcons >= 2 )
530  {
531  SCIP_CALL( detectDominatingVlbs(scip, matrix, nvbcons, vbcons,
532  lowthresholds, highthresholds, conidxs, binidxs,
533  nvaragg, isvartoagg, aggvars, ndeletecons, deletecons) );
534  }
535  }
536
537  SCIPfreeBufferArray(scip, &vbcons);
538  SCIPfreeBufferArray(scip, &highthresholds);
539  SCIPfreeBufferArray(scip, &lowthresholds);
540  SCIPfreeBufferArray(scip, &conidxs);
541  SCIPfreeBufferArray(scip, &binidxs);
542
543  return SCIP_OKAY;
544 }
545
546
547 /*
548  * Callback methods of presolver
549  */
550
551
552 /** execution method of presolver */
553 static
554 SCIP_DECL_PRESOLEXEC(presolExecRedvub)
555 { /*lint --e{715}*/
556  SCIP_MATRIX* matrix;
557  SCIP_Bool initialized;
558  SCIP_Bool complete;
559  SCIP_Bool infeasible;
560
561  assert(result != NULL);
562  *result = SCIP_DIDNOTRUN;
563
565  return SCIP_OKAY;
566
568  return SCIP_OKAY;
569
570  *result = SCIP_DIDNOTFIND;
571
572  matrix = NULL;
573  SCIP_CALL( SCIPmatrixCreate(scip, &matrix, TRUE, &initialized, &complete, &infeasible,
574  naddconss, ndelconss, nchgcoefs, nchgbds, nfixedvars) );
575
576  /* if infeasibility was detected during matrix creation, return here */
577  if( infeasible )
578  {
579  if( initialized )
580  SCIPmatrixFree(scip, &matrix);
581
582  *result = SCIP_CUTOFF;
583  return SCIP_OKAY;
584  }
585
586  if( initialized && complete )
587  {
588  int nvaragg;
589  SCIP_Bool* isvartoagg;
590  int ndeletecons;
591  SCIP_Bool* deletecons;
592  SCIP_VAR** aggvars;
593  int ncols;
594  int nrows;
595
596  ncols = SCIPmatrixGetNColumns(matrix);
597  nrows = SCIPmatrixGetNRows(matrix);
598
599  nvaragg = 0;
600  ndeletecons = 0;
601
602  SCIP_CALL( SCIPallocBufferArray(scip, &isvartoagg, ncols) );
603  BMSclearMemoryArray(isvartoagg, ncols);
604
605  SCIP_CALL( SCIPallocBufferArray(scip, &deletecons, nrows) );
606  BMSclearMemoryArray(deletecons, nrows);
607
608  SCIP_CALL( SCIPallocBufferArray(scip, &aggvars, ncols) );
609  BMSclearMemoryArray(aggvars, ncols);
610
611  SCIP_CALL( findVarAggrRedVbcons(scip, matrix, &nvaragg, isvartoagg, aggvars, &ndeletecons, deletecons) );
612
613  if( nvaragg > 0 )
614  {
615  int v;
616  for( v = 0; v < ncols; v++ )
617  {
618  if( isvartoagg[v] )
619  {
620  SCIP_Bool redundant;
621  SCIP_Bool aggregated;
622
623  /* substitute/aggregate binary variable */
624  assert(aggvars[v] != NULL);
625  SCIP_CALL( SCIPaggregateVars(scip, SCIPmatrixGetVar(matrix,v), aggvars[v], 1.0, -1.0,
626  0.0, &infeasible, &redundant, &aggregated) );
627
628  if( infeasible )
629  {
630  SCIPdebugMsg(scip, " -> infeasible aggregation\n");
631  *result = SCIP_CUTOFF;
632  return SCIP_OKAY;
633  }
634
635  if( aggregated )
636  {
637  (*naggrvars)++;
638
639  /* set result pointer */
640  if( (*result) == SCIP_DIDNOTFIND )
641  *result = SCIP_SUCCESS;
642  }
643  }
644  }
645  }
646
647  if( ndeletecons > 0 )
648  {
649  int r;
650  for( r = 0; r < nrows; r++ )
651  {
652  if( deletecons[r] )
653  {
654  SCIP_CONS* cons;
655
656  /* remove redundant variable bound constraint */
657  cons = SCIPmatrixGetCons(matrix, r);
658  SCIP_CALL( SCIPdelCons(scip, cons) );
659
660  (*ndelconss)++;
661
662  /* set result pointer */
663  if( (*result) == SCIP_DIDNOTFIND )
664  *result = SCIP_SUCCESS;
665  }
666  }
667  }
668
669  SCIPfreeBufferArray(scip, &aggvars);
670  SCIPfreeBufferArray(scip, &deletecons);
671  SCIPfreeBufferArray(scip, &isvartoagg);
672  }
673
674  SCIPmatrixFree(scip, &matrix);
675
676  return SCIP_OKAY;
677 }
678
679 /*
680  * presolver specific interface methods
681  */
682
683 /** creates the redvub presolver and includes it in SCIP */
685  SCIP* scip /**< SCIP data structure */
686  )
687 {
688  SCIP_PRESOL* presol;
689
690  /* include presolver */
692  PRESOL_TIMING, presolExecRedvub, NULL) );
693
694  return SCIP_OKAY;
695 }
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPgetNContVars(SCIP *scip)
Definition: scip_prob.c:2166
SCIP_VAR * SCIPmatrixGetVar(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1620
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:687
int SCIPmatrixGetNRows(SCIP_MATRIX *matrix)
Definition: matrix.c:1692
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for memory management
SCIP_CONS * SCIPmatrixGetCons(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1820
SCIP_Bool SCIPisNLPEnabled(SCIP *scip)
Definition: scip_nlp.c:172
void SCIPmatrixFree(SCIP *scip, SCIP_MATRIX **matrix)
Definition: matrix.c:1032
#define MAXPAIRCOMP
Definition: presol_redvub.c:56
#define FALSE
Definition: def.h:73
public methods for presolving plugins
SCIP_EXPORT SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17510
SCIP_EXPORT SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17177
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
static SCIP_RETCODE findVarAggrRedVbcons(SCIP *scip, SCIP_MATRIX *matrix, int *nvaragg, SCIP_Bool *isvartoagg, SCIP_VAR **aggvars, int *ndeletecons, SCIP_Bool *deletecons)
static SCIP_Bool isVub(SCIP *scip, SCIP_MATRIX *matrix, int row, SCIP_Real *lowthreshold, SCIP_Real *highthreshold, int *conidx, int *binidx)
Definition: presol_redvub.c:64
public methods for problem variables
static SCIP_Bool isVlb(SCIP *scip, SCIP_MATRIX *matrix, int row, SCIP_Real *lowthreshold, SCIP_Real *highthreshold, int *conidx, int *binidx)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
public methods for SCIP variables
#define SCIPdebugMsg
Definition: scip_message.h:69
public methods for numerical tolerances
int SCIPmatrixGetRowNNonzs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1668
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2837
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPmatrixGetRowLhs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1702
SCIP_EXPORT const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17012
int * SCIPmatrixGetRowIdxPtr(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1656
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:88
#define NULL
Definition: lpi_spx1.cpp:155
#define SCIP_CALL(x)
Definition: def.h:364
SCIP_RETCODE SCIPmatrixCreate(SCIP *scip, SCIP_MATRIX **matrixptr, SCIP_Bool onlyifcomplete, SCIP_Bool *initialized, SCIP_Bool *complete, SCIP_Bool *infeasible, int *naddconss, int *ndelconss, int *nchgcoefs, int *nchgbds, int *nfixedvars)
Definition: matrix.c:445
SCIP_Real * SCIPmatrixGetRowValPtr(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1644
public methods for constraint handler plugins and constraints
#define PRESOL_NAME
Definition: presol_redvub.c:50
static SCIP_RETCODE detectDominatingVubs(SCIP *scip, SCIP_MATRIX *matrix, int nvubs, int *vubs, SCIP_Real *lowthresholds, SCIP_Real *highthresholds, int *conidxs, int *binidxs, int *nvaragg, SCIP_Bool *isvartoagg, SCIP_VAR **aggvars, int *ndeletecons, SCIP_Bool *deletecons)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
#define SCIP_Bool
Definition: def.h:70
static SCIP_DECL_PRESOLEXEC(presolExecRedvub)
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
Definition: scip_cons.c:2473
#define PRESOL_TIMING
Definition: presol_redvub.c:54
int * SCIPmatrixGetColIdxPtr(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1540
#define PRESOL_DESC
Definition: presol_redvub.c:51
int SCIPgetNActivePricers(SCIP *scip)
Definition: scip_pricer.c:339
#define PRESOL_PRIORITY
Definition: presol_redvub.c:52
public methods for matrix
public methods for variable pricer plugins
static SCIP_RETCODE detectDominatingVlbs(SCIP *scip, SCIP_MATRIX *matrix, int nvlbs, int *vlbs, SCIP_Real *lowthresholds, SCIP_Real *highthresholds, int *conidxs, int *binidxs, int *nvaragg, SCIP_Bool *isvartoagg, SCIP_VAR **aggvars, int *ndeletecons, SCIP_Bool *deletecons)
public methods for nonlinear relaxations
SCIP_Real * r
Definition: circlepacking.c:50
remove redundant variable upper bound constraints
general public methods
SCIP_EXPORT SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17662
public methods for the probing mode
SCIP_Bool SCIPmatrixIsRowRhsInfinity(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1726
public methods for message output
#define SCIP_Real
Definition: def.h:163
SCIP_RETCODE SCIPincludePresolBasic(SCIP *scip, SCIP_PRESOL **presolptr, const char *name, const char *desc, int priority, int maxrounds, SCIP_PRESOLTIMING timing, SCIP_DECL_PRESOLEXEC((*presolexec)), SCIP_PRESOLDATA *presoldata)
Definition: scip_presol.c:95
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for message handling
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPmatrixGetColNDownlocks(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1608
SCIP_EXPORT SCIP_Bool SCIPvarsHaveCommonClique(SCIP_VAR *var1, SCIP_Bool value1, SCIP_VAR *var2, SCIP_Bool value2, SCIP_Bool regardimplics)
Definition: var.c:11244
enum SCIP_Vartype SCIP_VARTYPE
Definition: type_var.h:60
int SCIPmatrixGetColNUplocks(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1596
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:122
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:199
SCIP_RETCODE SCIPaggregateVars(SCIP *scip, SCIP_VAR *varx, SCIP_VAR *vary, SCIP_Real scalarx, SCIP_Real scalary, SCIP_Real rhs, SCIP_Bool *infeasible, SCIP_Bool *redundant, SCIP_Bool *aggregated)
Definition: scip_var.c:8380
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:356
public methods for global and local (sub)problems
int SCIPmatrixGetNColumns(SCIP_MATRIX *matrix)
Definition: matrix.c:1564
#define PRESOL_MAXROUNDS
Definition: presol_redvub.c:53
SCIP_RETCODE SCIPincludePresolRedvub(SCIP *scip)
int SCIPmatrixGetColNNonzs(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1552
memory allocation routines