1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 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
isVub(SCIP * scip,SCIP_MATRIX * matrix,int row,SCIP_Real * lowthreshold,SCIP_Real * highthreshold,int * conidx,int * binidx)64 SCIP_Bool isVub(
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
isVlb(SCIP * scip,SCIP_MATRIX * matrix,int row,SCIP_Real * lowthreshold,SCIP_Real * highthreshold,int * conidx,int * binidx)145 SCIP_Bool isVlb(
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
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)227 SCIP_RETCODE detectDominatingVubs(
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
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)333 SCIP_RETCODE detectDominatingVlbs(
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
findVarAggrRedVbcons(SCIP * scip,SCIP_MATRIX * matrix,int * nvaragg,SCIP_Bool * isvartoagg,SCIP_VAR ** aggvars,int * ndeletecons,SCIP_Bool * deletecons)440 SCIP_RETCODE findVarAggrRedVbcons(
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
477 if( SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS )
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
SCIP_DECL_PRESOLEXEC(presolExecRedvub)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
564 if( (SCIPgetStage(scip) != SCIP_STAGE_PRESOLVING) || SCIPinProbing(scip) || SCIPisNLPEnabled(scip) )
565 return SCIP_OKAY;
566
567 if( SCIPgetNContVars(scip) == 0 || SCIPisStopped(scip) || SCIPgetNActivePricers(scip) > 0 )
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 */
SCIPincludePresolRedvub(SCIP * scip)684 SCIP_RETCODE SCIPincludePresolRedvub(
685 SCIP* scip /**< SCIP data structure */
686 )
687 {
688 SCIP_PRESOL* presol;
689
690 /* include presolver */
691 SCIP_CALL( SCIPincludePresolBasic(scip, &presol, PRESOL_NAME, PRESOL_DESC, PRESOL_PRIORITY, PRESOL_MAXROUNDS,
692 PRESOL_TIMING, presolExecRedvub, NULL) );
693
694 return SCIP_OKAY;
695 }
696