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