Scippy

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