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-2024 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
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
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 */
72static
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 */
153static
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 */
235static
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 */
341static
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 */
448static
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 */
562static
563SCIP_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_Real * r
Definition: circlepacking.c:59
#define NULL
Definition: def.h:267
#define SCIP_Bool
Definition: def.h:91
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:724
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:380
int SCIPgetNContVars(SCIP *scip)
Definition: scip_prob.c:2172
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2843
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_RETCODE SCIPincludePresolRedvub(SCIP *scip)
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
Definition: scip_cons.c:2537
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
SCIP_Bool SCIPisNLPEnabled(SCIP *scip)
Definition: scip_nlp.c:74
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
int SCIPgetNActivePricers(SCIP *scip)
Definition: scip_pricer.c:348
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:97
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
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
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17926
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17584
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18078
SCIP_Bool SCIPvarsHaveCommonClique(SCIP_VAR *var1, SCIP_Bool value1, SCIP_VAR *var2, SCIP_Bool value2, SCIP_Bool regardimplics)
Definition: var.c:11475
int * SCIPmatrixGetColIdxPtr(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1580
int SCIPmatrixGetRowNNonzs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1708
int SCIPmatrixGetColNDownlocks(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1648
int SCIPmatrixGetColNNonzs(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1592
SCIP_Bool SCIPmatrixIsRowRhsInfinity(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1766
int SCIPmatrixGetColNUplocks(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1636
SCIP_Real SCIPmatrixGetRowLhs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1742
SCIP_Real * SCIPmatrixGetRowValPtr(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1684
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
int SCIPmatrixGetNColumns(SCIP_MATRIX *matrix)
Definition: matrix.c:1604
SCIP_CONS * SCIPmatrixGetCons(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1860
void SCIPmatrixFree(SCIP *scip, SCIP_MATRIX **matrix)
Definition: matrix.c:1072
SCIP_VAR * SCIPmatrixGetVar(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1660
int * SCIPmatrixGetRowIdxPtr(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1696
int SCIPmatrixGetNRows(SCIP_MATRIX *matrix)
Definition: matrix.c:1732
memory allocation routines
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:130
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)
static SCIP_Bool isVlb(SCIP *scip, SCIP_MATRIX *matrix, int row, SCIP_Real *lowthreshold, SCIP_Real *highthreshold, int *conidx, int *binidx)
#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 MAXPAIRCOMP
Definition: presol_redvub.c:65
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
#define PRESOL_PRIORITY
Definition: presol_redvub.c:61
static SCIP_RETCODE findVarAggrRedVbcons(SCIP *scip, SCIP_MATRIX *matrix, int *nvaragg, SCIP_Bool *isvartoagg, SCIP_VAR **aggvars, int *ndeletecons, SCIP_Bool *deletecons)
#define PRESOL_MAXROUNDS
Definition: presol_redvub.c:62
#define PRESOL_TIMING
Definition: presol_redvub.c:63
static SCIP_DECL_PRESOLEXEC(presolExecRedvub)
#define PRESOL_DESC
Definition: presol_redvub.c:60
remove redundant variable upper bound constraints
public methods for matrix
public methods for message output
public methods for problem variables
public methods for constraint handler plugins and constraints
general public methods
public methods for memory management
public methods for message handling
public methods for nonlinear relaxation
public methods for numerical tolerances
public methods for presolving plugins
public methods for variable pricer plugins
public methods for global and local (sub)problems
public methods for the probing mode
public methods for SCIP variables
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_CUTOFF
Definition: type_result.h:48
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_SUCCESS
Definition: type_result.h:58
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_STAGE_PRESOLVING
Definition: type_set.h:49
@ SCIP_VARTYPE_CONTINUOUS
Definition: type_var.h:71
@ SCIP_VARTYPE_BINARY
Definition: type_var.h:62
enum SCIP_Vartype SCIP_VARTYPE
Definition: type_var.h:73