Scippy

SCIP

Solving Constraint Integer Programs

presolve.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 presolve.c
26 * @ingroup OTHER_CFILES
27 * @brief methods for presolving
28 * @author Michael Winkler
29 */
30
31/* all general presolving methods (not working on any specific kind of data(, e.g. consdata) should be implemented here */
32
33/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
34
35#include "blockmemshell/memory.h"
36#include "scip/presolve.h"
37#include "scip/prob.h"
38#include "scip/pub_implics.h"
39#include "scip/pub_message.h"
40#include "scip/pub_var.h"
41#include "scip/scip_mem.h"
42#include "scip/scip_message.h"
43#include "scip/scip_numerics.h"
44#include "scip/scip_tree.h"
45#include "scip/struct_mem.h"
46#include "scip/struct_scip.h"
47#include "scip/tree.h"
48
49/*
50 * Local methods
51 */
52
53/** collect variable bound information for a variable set reduction and global implication; only variable which have the
54 * vartype != SCIP_VARTYPE_BINARY have variable bounds
55 */
56static
57void collectNonBinaryVBoundData(
58 SCIP* scip, /**< SCIP data structure */
59 SCIP_VAR* var, /**< set variable */
60 int varidx, /**< for lower bound set variable index, for upper bound set variable index
61 * + number of variables
62 */
63 int pos, /**< variables's position in bdchinfos */
64 int nredvars, /**< number of reduced variables so far */
65 SCIP_Real* bounds, /**< array of bounds where one of them must be fullfilled */
66 SCIP_Bool* boundtypes, /**< array of bound types */
67 SCIP_Real* newbounds, /**< array of implied bounds(, size is two times number of variables, first
68 * half for implied lower bounds, second for implied upper bounds)
69 */
70 int* counts, /**< array of number of implication on a bound (, size is two times number
71 * of variables, first half for implied lower bounds, second for implied
72 * upper bounds)
73 */
74 int* countnonzeros, /**< array to store the indices of non-zero entries in the counts array */
75 int* ncountnonzeros, /**< pointer to store the number of non-zero entries in the counts array */
76 int* issetvar, /**< array containing for set variables the position in the current set, or
77 * 0 if it is not a set variable or -1, if it is a redundant(i.e. implies
78 * another set variable) set variables(, size is two times number of
79 * variables, first half for implied lower bounds, second for implied
80 * upper bounds) */
81 int nvars, /**< number of problem variables */
82 int* foundbin, /**< pointer to store the lowest index of a binary implication variable
83 * when found
84 */
85 int* foundnonbin, /**< pointer to store the lowest index of a non-binary implication variable
86 * when found
87 */
88 int* implidx, /**< array to store the variable indices (for upper bound 'nvars' is added
89 * to the index) which are implied
90 */
91 int* nimplidx, /**< pointer to store the number of implied variables */
92 SCIP_Real* lastbounds /**< array to remember last implied bounds before taken the current
93 * variable into account, first nvars for lower bound, second nvars for
94 * upper bound
95 *
96 * this array is used when a set variable got redundant, because it
97 * implies another set variable, and we need to correct the counts array
98 */
99 )
100{
101 SCIP_VAR** implvars;
102 SCIP_Real* implcoefs;
103 SCIP_Real* implconsts;
104 int nimpls;
105 int idx;
106 int w;
107
108 assert(scip != NULL);
109 assert(var != NULL);
110 assert(SCIPvarGetType(var) != SCIP_VARTYPE_BINARY);
111 assert(varidx >= 0);
112 assert(pos >= 0);
113 assert(bounds != NULL);
114 assert(boundtypes != NULL);
115 assert(newbounds != NULL);
116 assert(counts != NULL);
117 assert(issetvar != NULL);
118 assert(2 * nvars > varidx);
119 assert(foundbin != NULL);
120 assert(foundnonbin != NULL);
121 assert(implidx != NULL);
122 assert(nimplidx != NULL);
123 assert(lastbounds != NULL);
124
125 /* 1. case: lower bound in set */
126 if( !boundtypes[pos] )
127 {
128 assert(counts[varidx] <= pos - nredvars + 1);
129
130 /* update implication counter of set variable */
131 if( counts[varidx] == pos - nredvars )
132 {
133 ++counts[varidx];
134
135 if( counts[varidx] == 1 )
136 {
137 assert(*ncountnonzeros < 2*nvars);
138 countnonzeros[*ncountnonzeros] = varidx;
139 ++(*ncountnonzeros);
140 newbounds[varidx] = bounds[pos];
141 lastbounds[*nimplidx] = SCIP_INVALID;
142 }
143 else if( newbounds[varidx] > bounds[pos] )
144 {
145 lastbounds[*nimplidx] = newbounds[varidx];
146 newbounds[varidx] = bounds[pos];
147 }
148 else
149 {
150 lastbounds[*nimplidx] = SCIP_INVALID;
151 }
152
153 *foundnonbin = MIN(*foundnonbin, varidx);
154
155 implidx[*nimplidx] = varidx;
156 ++(*nimplidx);
157 }
158
159 nimpls = SCIPvarGetNVubs(var);
160 implvars = SCIPvarGetVubVars(var);
161 implcoefs = SCIPvarGetVubCoefs(var);
162 implconsts = SCIPvarGetVubConstants(var);
163
164 for( w = nimpls - 1; w >= 0; --w )
165 {
166 assert(!SCIPisZero(scip, implcoefs[w]));
167 idx = SCIPvarGetProbindex(implvars[w]);
168
169 /* do not use inactive variables */
170 /* @todo if implvars[x] is aggregated, we could transform the variable into the active representation */
171 if( idx < 0 || SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(implvars[w]), SCIPvarGetUbGlobal(implvars[w])) )
172 continue;
173
174 /* the upper bound of implvars[w] is bounding upper bound of var */
175 if( implcoefs[w] < 0.0 )
176 {
177 /* update the counters and implied bounds */
178 idx += nvars;
179
180 if( counts[idx] == pos - nredvars )
181 {
182 if( SCIPvarIsBinary(implvars[w]) )
183 {
184 /* do not look at fixed variables */
185 if( SCIPvarGetLbGlobal(implvars[w]) > 0.5 || SCIPvarGetUbGlobal(implvars[w]) < 0.5 )
186 continue;
187
188 /* (implvars[w] = 1 ===> var <= implcoefs[w] + implconsts[w] and if implcoefs[w] +
189 * implconsts[w] < bounds[pos]) ===> (because var => bounds[v] ===> implvars[w] = 0)
190 */
191 if( SCIPisFeasLT(scip, implcoefs[w] + implconsts[w], bounds[pos]) )
192 {
193 /* set variable 'var' with bound implies other set variable 'implvars[w]' with corresponding bound
194 * so we can remove the set variable 'var'
195 */
196 if( issetvar[idx] > 0 )
197 {
198 SCIPdebugMsg(scip, "set variable <%s> %s %g implies other set variable <%s> %s %g\n",
199 SCIPvarGetName(var), ">=", bounds[pos], SCIPvarGetName(implvars[w]), "<=", 0.0);
200
201 issetvar[varidx] = -1;
202 break;
203 }
204
205 ++counts[idx];
206 *foundbin = MIN(*foundbin, idx);
207
208 if( counts[idx] == 1 )
209 {
210 assert(*ncountnonzeros < 2*nvars);
211 countnonzeros[*ncountnonzeros] = idx;
212 ++(*ncountnonzeros);
213 }
214
215 implidx[*nimplidx] = idx;
216 ++(*nimplidx);
217 }
218 }
219 /* if (implvars[w] = ub(implvars[w]) ==> var <= implcoefs[w]*SCIPvarGetUbGlobal(implvars[w]) +
220 * implconsts[w]) but (var >= bounds[pos] with bounds[pos] >
221 * implcoefs[w]*SCIPvarGetUbGlobal(implvars[w]) + implconsts[w]) it follows (new_ub(var) <
222 * ub(var))
223 */
224 else if( SCIPisFeasLT(scip, implcoefs[w] * SCIPvarGetUbGlobal(implvars[w]) + implconsts[w], bounds[pos]) )
225 {
226 SCIP_Real newub;
227
228 newub = (bounds[pos] - implconsts[w]) / implcoefs[w];
229
230 /* set variable 'var' with bound implies other set variable 'implvars[w]' with corresponding bound so
231 * we can remove the set variable 'var'
232 */
233 if( issetvar[idx] > 0 && newub <= bounds[issetvar[idx] - 1] )
234 {
235 SCIPdebugMsg(scip, "set variable <%s> %s %g implies other set variable <%s> %s %g (%g)\n",
236 SCIPvarGetName(var), ">=", bounds[pos], SCIPvarGetName(implvars[w]), "<=", newub, bounds[issetvar[idx] - 1] );
237
238 issetvar[varidx] = -1;
239 break;
240 }
241
242 ++counts[idx];
243
244 if( counts[idx] == 1 )
245 {
246 assert(*ncountnonzeros < 2*nvars);
247 countnonzeros[*ncountnonzeros] = idx;
248 ++(*ncountnonzeros);
249 newbounds[idx] = newub;
250 lastbounds[*nimplidx] = SCIP_INVALID;
251 }
252 else if( newbounds[idx] < newub )
253 {
254 lastbounds[*nimplidx] = newbounds[idx];
255 newbounds[idx] = newub;
256 }
257 else
258 lastbounds[*nimplidx] = SCIP_INVALID;
259
260 *foundnonbin = MIN(*foundnonbin, idx);
261
262 implidx[*nimplidx] = idx;
263 ++(*nimplidx);
264 }
265 }
266 }
267 else
268 {
269 assert(counts[varidx] <= pos - nredvars + 1);
270
271 /* update the counters and implied bounds */
272 if( counts[idx] == pos - nredvars )
273 {
274 if( SCIPvarIsBinary(implvars[w]) )
275 {
276 /* do not look at fixed variables */
277 if( SCIPvarGetLbGlobal(implvars[w]) > 0.5 || SCIPvarGetUbGlobal(implvars[w]) < 0.5 )
278 continue;
279
280 /* (implvars[w] = 0 ===> var <= implconsts[w] and if implconsts[w] < bounds[pos]) ===> (because
281 * var >= bounds[pos] ===> implvars[w] = 1)
282 */
283 if( SCIPisFeasLT(scip, implconsts[w], bounds[pos]) )
284 {
285 /* set variable 'var' with bound implies other set variable 'implvars[w]' with corresponding bound
286 * so we can remove the set variable 'var'
287 */
288 if( issetvar[idx] > 0 )
289 {
290 SCIPdebugMsg(scip, "set variable <%s> %s %g implies other set variable <%s> %s %g\n",
291 SCIPvarGetName(var), ">=", bounds[pos], SCIPvarGetName(implvars[w]), ">=", 1.0);
292
293 issetvar[varidx] = -1;
294 break;
295 }
296
297 ++counts[idx];
298 *foundbin = MIN(*foundbin, idx);
299
300 if( counts[idx] == 1 )
301 {
302 assert(*ncountnonzeros < 2*nvars);
303 countnonzeros[*ncountnonzeros] = idx;
304 ++(*ncountnonzeros);
305 }
306
307 implidx[*nimplidx] = idx;
308 ++(*nimplidx);
309 }
310 }
311 /* if (implvars[w] = lb(implvars[w]) => var <= implcoefs[w]*SCIPvarGetLbGlobal(implvars[w]) +
312 * implconsts[w]) but (var >= bounds[pos] with bounds[pos] >
313 * implcoefs[w]*SCIPvarGetLbGlobal(implvars[w]) + implconsts[w]) it follows (new_lb(var) >
314 * lb(var))
315 */
316 else if( SCIPisFeasLT(scip, implcoefs[w]*SCIPvarGetLbGlobal(implvars[w]) + implconsts[w], bounds[pos]) )
317 {
318 SCIP_Real newlb;
319
320 newlb = (bounds[pos] - implconsts[w]) / implcoefs[w];
321
322 /* set variable 'var' with bound implies other set variable 'implvars[w]' with corresponding bound so
323 * we can remove the set variable 'var'
324 */
325 if( issetvar[idx] > 0 && newlb >= bounds[issetvar[idx] - 1] )
326 {
327 SCIPdebugMsg(scip, "set variable <%s> %s %g implies other set variable <%s> %s %g (%g)\n",
328 SCIPvarGetName(var), ">=", bounds[pos], SCIPvarGetName(implvars[w]), ">=", newlb, bounds[issetvar[idx] - 1] );
329
330 issetvar[varidx] = -1;
331 break;
332 }
333
334 ++counts[idx];
335
336 if( counts[idx] == 1 )
337 {
338 assert(*ncountnonzeros < 2*nvars);
339 countnonzeros[*ncountnonzeros] = idx;
340 ++(*ncountnonzeros);
341 lastbounds[*nimplidx] = SCIP_INVALID;
342 newbounds[idx] = newlb;
343 }
344 else if( newbounds[idx] > newlb )
345 {
346 lastbounds[*nimplidx] = newbounds[idx];
347 newbounds[idx] = newlb;
348 }
349 else
350 lastbounds[*nimplidx] = SCIP_INVALID;
351
352 *foundnonbin = MIN(*foundnonbin, idx);
353
354 implidx[*nimplidx] = idx;
355 ++(*nimplidx);
356 }
357 }
358 }
359 }
360 }
361 /* 2.case: upper bound in set */
362 else
363 {
364 assert(boundtypes[pos]);
365 assert(counts[varidx] <= pos - nredvars + 1);
366
367 /* update implication counter of set variable */
368 if( counts[varidx] == pos - nredvars )
369 {
370 ++counts[varidx];
371
372 if( counts[varidx] == 1 )
373 {
374 assert(*ncountnonzeros < 2*nvars);
375 countnonzeros[*ncountnonzeros] = varidx;
376 ++(*ncountnonzeros);
377 newbounds[varidx] = bounds[pos];
378 lastbounds[*nimplidx] = SCIP_INVALID;
379 }
380 else if( newbounds[varidx] < bounds[pos] )
381 {
382 lastbounds[*nimplidx] = newbounds[varidx];
383 newbounds[varidx] = bounds[pos];
384 }
385 else
386 {
387 lastbounds[*nimplidx] = SCIP_INVALID;
388 }
389
390 *foundnonbin = MIN(*foundnonbin, varidx);
391
392 implidx[*nimplidx] = varidx;
393 ++(*nimplidx);
394 }
395
396 nimpls = SCIPvarGetNVlbs(var);
397 implvars = SCIPvarGetVlbVars(var);
398 implcoefs = SCIPvarGetVlbCoefs(var);
399 implconsts = SCIPvarGetVlbConstants(var);
400
401 for( w = nimpls - 1; w >= 0; --w )
402 {
403 assert(!SCIPisZero(scip, implcoefs[w]));
404 idx = SCIPvarGetProbindex(implvars[w]);
405
406 /* do not use inactive variables */
407 /* @todo if implvars[x] is aggregated, we could transform the variable into the active representation */
408 if( idx < 0 || SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(implvars[w]), SCIPvarGetUbGlobal(implvars[w])) )
409 continue;
410
411 /* the lower bound of implvars[w] is bounding lower bound of var */
412 if( implcoefs[w] < 0.0 )
413 {
414 assert(counts[idx] <= pos - nredvars + 1);
415
416 /* update the counters and implied bounds */
417 if( counts[idx] == pos - nredvars )
418 {
419 if( SCIPvarIsBinary(implvars[w]) )
420 {
421 /* do not look at fixed variables */
422 if( SCIPvarGetLbGlobal(implvars[w]) > 0.5 || SCIPvarGetUbGlobal(implvars[w]) < 0.5 )
423 continue;
424
425 /* (implvars[w] = 0 ===> var >= implconsts[w] and if implconsts[w] > bounds[pos]) ===> (because
426 * var <= bounds[pos] ===> implvars[w] = 1)
427 */
428 if( SCIPisFeasGT(scip, implconsts[w], bounds[pos]) )
429 {
430 if( issetvar[idx] > 0 )
431 {
432 SCIPdebugMsg(scip, "set variable <%s> %s %g implies other set variable <%s> %s %g\n",
433 SCIPvarGetName(var), "<=", bounds[pos], SCIPvarGetName(implvars[w]), ">=", 1.0);
434
435 issetvar[varidx] = -1;
436 break;
437 }
438
439 ++counts[idx];
440 *foundbin = MIN(*foundbin, idx);
441
442 if( counts[idx] == 1 )
443 {
444 assert(*ncountnonzeros < 2*nvars);
445 countnonzeros[*ncountnonzeros] = idx;
446 ++(*ncountnonzeros);
447 }
448
449 implidx[*nimplidx] = idx;
450 ++(*nimplidx);
451 }
452 }
453 /* if (implvars[w] = lb(implvars[w]) ==> var <= implcoefs[w]*SCIPvarGetLbGlobal(implvars[w]) +
454 * implconsts[w]) but (var <= bounds[pos] with bounds[pos] <
455 * implcoefs[w]*SCIPvarGetLbGlobal(implvars[w]) + implconsts[w]) it follows (new_lb(var) >
456 * ub(var))
457 */
458 else if( SCIPisFeasGT(scip, implcoefs[w]*SCIPvarGetLbGlobal(implvars[w]) + implconsts[w], bounds[pos]) )
459 {
460 SCIP_Real newlb;
461
462 newlb = (bounds[pos] - implconsts[w]) / implcoefs[w];
463
464 if( issetvar[idx] > 0 && newlb >= bounds[issetvar[idx] - 1] )
465 {
466 SCIPdebugMsg(scip, "set variable <%s> %s %g implies other set variable <%s> %s %g (%g)\n",
467 SCIPvarGetName(var), "<=", bounds[pos], SCIPvarGetName(implvars[w]), ">=", newlb, bounds[issetvar[idx] - 1]);
468
469 issetvar[varidx] = -1;
470 break;
471 }
472
473 ++counts[idx];
474
475 if( counts[idx] == 1 )
476 {
477 assert(*ncountnonzeros < 2*nvars);
478 countnonzeros[*ncountnonzeros] = idx;
479 ++(*ncountnonzeros);
480 lastbounds[*nimplidx] = SCIP_INVALID;
481 newbounds[idx] = newlb;
482 }
483 else if( newbounds[idx] > newlb )
484 {
485 lastbounds[*nimplidx] = newbounds[idx];
486 newbounds[idx] = newlb;
487 }
488 else
489 lastbounds[*nimplidx] = SCIP_INVALID;
490
491 *foundnonbin = MIN(*foundnonbin, idx);
492
493 implidx[*nimplidx] = idx;
494 ++(*nimplidx);
495 }
496 }
497 }
498 else
499 {
500 /* update the counters and implied bounds */
501 idx += nvars;
502
503 assert(counts[idx] <= pos - nredvars + 1);
504
505 if( counts[idx] == pos - nredvars )
506 {
507 if( SCIPvarIsBinary(implvars[w]) )
508 {
509 /* do not look at fixed variables */
510 if( SCIPvarGetLbGlobal(implvars[w]) > 0.5 || SCIPvarGetUbGlobal(implvars[w]) < 0.5 )
511 continue;
512
513 /* (implvars[w] = 1 ===> var >= implcoefs[w] + implconsts[w] and if implcoefs[w] +
514 * implconsts[w] > bounds[pos]) ===> (because var <= bounds[pos] ===> implvars[w] = 0)
515 */
516 if( SCIPisFeasGT(scip, implcoefs[w] + implconsts[w], bounds[pos]) )
517 {
518 if( issetvar[idx] > 0 )
519 {
520 SCIPdebugMsg(scip, "set variable <%s> %s %g implies other set variable <%s> %s %g\n",
521 SCIPvarGetName(var), "<=", bounds[pos], SCIPvarGetName(implvars[w]), "<=", 0.0);
522
523 issetvar[varidx] = -1;
524 break;
525 }
526
527 ++counts[idx];
528 *foundbin = MIN(*foundbin, idx);
529
530 if( counts[idx] == 1 )
531 {
532 assert(*ncountnonzeros < 2*nvars);
533 countnonzeros[*ncountnonzeros] = idx;
534 ++(*ncountnonzeros);
535 }
536
537 implidx[*nimplidx] = idx;
538 ++(*nimplidx);
539 }
540 }
541 /* if (implvars[w] = ub(implvars[w]) => var <= implcoefs[w]*SCIPvarGetUbGlobal(implvars[w]) +
542 * implconsts[w]) but (var <= bounds[pos] with bounds[pos] <
543 * implcoefs[w]*SCIPvarGetUbGlobal(implvars[w]) + implconsts[w]) it follows (new_ub(var) <
544 * ub(var))
545 */
546 else if( SCIPisFeasGT(scip, implcoefs[w]*SCIPvarGetUbGlobal(implvars[w]) + implconsts[w], bounds[pos]) )
547 {
548 SCIP_Real newub;
549
550 newub = (bounds[pos] - implconsts[w]) / implcoefs[w];
551
552 if( issetvar[idx] > 0 && newub <= bounds[issetvar[idx] - 1] )
553 {
554 SCIPdebugMsg(scip, "set variable <%s> %s %g implies other set variable <%s> %s %g (%g)\n",
555 SCIPvarGetName(var), "<=", bounds[pos], SCIPvarGetName(implvars[w]), "<=", newub, bounds[issetvar[idx] - 1]);
556
557 issetvar[varidx] = -1;
558 break;
559 }
560
561 ++counts[idx];
562
563 if( counts[idx] == 1 )
564 {
565 assert(*ncountnonzeros < 2*nvars);
566 countnonzeros[*ncountnonzeros] = idx;
567 ++(*ncountnonzeros);
568 lastbounds[*nimplidx] = SCIP_INVALID;
569 newbounds[idx] = newub;
570 }
571 else if( newbounds[idx] < newub )
572 {
573 lastbounds[*nimplidx] = newbounds[idx];
574 newbounds[idx] = newub;
575 }
576 else
577 lastbounds[*nimplidx] = SCIP_INVALID;
578
579 *foundnonbin = MIN(*foundnonbin, idx);
580
581 implidx[*nimplidx] = idx;
582 ++(*nimplidx);
583 }
584 }
585 }
586 }
587 }
588}
589
590
591/** collect non-binary implication data for variable set reduction and global bound implications; only variable which
592 * have the vartype SCIP_VARTYPE_BINARY have implications, otherwise the implications are saved as variable bounds
593 */
594static
595void collectNonBinaryImplicationData(
596 SCIP* scip, /**< SCIP data structure */
597 SCIP_VAR* var, /**< set variable */
598 int varidx, /**< for lower bound set variable index, for upper bound set
599 * variable index + number of variables
600 */
601 int pos, /**< variables's position in bdchinfos */
602 int nredvars, /**< number of reduced variables so far */
603 SCIP_Bool value, /**< value used for clique and implication info */
604 SCIP_Real* bounds, /**< array of bounds where one of them must be fullfilled */
605 SCIP_Bool* boundtypes, /**< array of bound types */
606 SCIP_Real* newbounds, /**< array of implied bounds(, size is two times number of variables, first
607 * half for implied lower bounds, second for implied upper bounds)
608 */
609 int* counts, /**< array of number of implication on a bound (, size is two times number
610 * of variables, first half for implied lower bounds, second for implied
611 * upper bounds)
612 */
613 int* countnonzeros, /**< array to store the indices of non-zero entries in the counts array */
614 int* ncountnonzeros, /**< pointer to store the number of non-zero entries in the counts array */
615 int* issetvar, /**< array containing for set variables the position in the current set, or
616 * 0 if it is not a set variable or -1, if it is a redundant(i.e. implies
617 * another set variable) set variables(, size is two times number of
618 * variables, first half for implied lower bounds, second for implied
619 * upper bounds) */
620 int nvars, /**< number of problem variables */
621 int* foundbin, /**< pointer to store the lowest index of a binary implication variable
622 * when found
623 */
624 int* foundnonbin, /**< pointer to store the lowest index of a non-binary implication variable
625 * when found
626 */
627 int* implidx, /**< array to store the variable indices (for upper bound 'nvars' is added
628 * to the index) which are implied
629 */
630 int* nimplidx, /**< pointer to store the number of implied variables */
631 SCIP_Real* lastbounds /**< array to remember last implied bounds before taken the current
632 * variable into account, first nvars for lower bound, second nvars for
633 * upper bound
634 *
635 * this array is used when a set variable got redundant, because it
636 * implies another set variable, and we need to correct the counts array
637 */
638 )
639{
640 assert(scip != NULL);
641 assert(var != NULL);
642 assert(SCIPvarGetType(var) == SCIP_VARTYPE_BINARY);
643 assert(varidx >= 0);
644 assert(pos >= 0);
645 assert(bounds != NULL);
646 assert(boundtypes != NULL);
647 assert(newbounds != NULL);
648 assert(counts != NULL);
649 assert(issetvar != NULL);
650 assert(2 * nvars > varidx);
651 assert(foundbin != NULL);
652 assert(foundnonbin != NULL);
653 assert(implidx != NULL);
654 assert(nimplidx != NULL);
655 assert(lastbounds != NULL);
656
657 if( issetvar[varidx] > 0 )
658 {
659 SCIP_VAR** implvars;
660 SCIP_Real* implbounds;
661 SCIP_BOUNDTYPE* implboundtypes;
662 int idx;
663 int w;
664
665 /* get implication information */
666 implvars = SCIPvarGetImplVars(var, value);
667 implboundtypes = SCIPvarGetImplTypes(var, value);
668 implbounds = SCIPvarGetImplBounds(var, value);
669
670 for( w = SCIPvarGetNImpls(var, value) - 1; w >= 0; --w )
671 {
672 assert(implvars != NULL);
673 assert(implboundtypes != NULL);
674
675 /* no self implication should exist in the implication data structure */
676 assert(implvars[w] != var);
677
678 idx = SCIPvarGetProbindex(implvars[w]);
679
680 /* do not use inactive variables */
681 /* @todo if implvars[x] is aggregated, we could transform the variable into the active representation */
682 if( idx < 0 || SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(implvars[w]), SCIPvarGetUbGlobal(implvars[w])) )
683 continue;
684
685 if( implboundtypes[w] == SCIP_BOUNDTYPE_UPPER )
686 {
687 SCIP_Bool redundant;
688
689 idx += nvars;
690
691 assert(counts[idx] <= pos - nredvars + 1);
692
693 /* set variable 'var' with bound implies other set variable 'implvars[w]' with a non-worse bound than the
694 * bound so we can remove the set variable 'var'
695 */
696 if( issetvar[idx] > 0 && bounds[issetvar[idx] - 1] >= implbounds[w] )
697 {
698 SCIPdebugMsg(scip, "set variable <%s> %s %g implies other set variable <%s> %s %g (%g)\n",
699 SCIPvarGetName(var), boundtypes[pos] ? "<=" : ">=", bounds[pos], SCIPvarGetName(implvars[w]),
700 "<=", implbounds[w], bounds[issetvar[idx] - 1]);
701
702 issetvar[varidx] = -1;
703 break;
704 }
705
706 /* ignore implications that are redundant with respect to the current global bounds (see #2888) */
707 redundant = SCIPisLE(scip, SCIPvarGetUbGlobal(implvars[w]), implbounds[w]);
708
709 /* update implication counter and implied upper bound */
710 if( counts[idx] == pos - nredvars && !redundant )
711 {
712 ++counts[idx];
713
714 if( SCIPvarIsBinary(implvars[w]) )
715 {
716 /* the implied upper bound on a binary variable should not be trivial, otherwise we might globally fix
717 * this variable to a wrong value
718 *
719 * @note it is possible that the implied bound is lower than zero, when the implied variable has
720 * become binary during the search
721 */
722 assert(SCIPisFeasLE(scip, implbounds[w], 0.0));
723 *foundbin = MIN(*foundbin, idx);
724
725 if( counts[idx] == 1 )
726 {
727 assert(*ncountnonzeros < 2*nvars);
728 countnonzeros[*ncountnonzeros] = idx;
729 ++(*ncountnonzeros);
730 }
731 }
732 else
733 {
734 *foundnonbin = MIN(*foundnonbin, idx);
735
736 if( counts[idx] == 1 )
737 {
738 assert(*ncountnonzeros < 2*nvars);
739 countnonzeros[*ncountnonzeros] = idx;
740 ++(*ncountnonzeros);
741 newbounds[idx] = implbounds[w];
742 lastbounds[*nimplidx] = SCIP_INVALID;
743 }
744 else if( newbounds[idx] < implbounds[w] )
745 {
746 lastbounds[*nimplidx] = newbounds[idx];
747 newbounds[idx] = implbounds[w];
748 }
749 else
750 lastbounds[*nimplidx] = SCIP_INVALID;
751 }
752
753 implidx[*nimplidx] = idx;
754 ++(*nimplidx);
755 }
756 }
757 else
758 {
759 SCIP_Bool redundant;
760
761 assert(counts[idx] <= pos - nredvars + 1);
762
763 /* set variable 'var' with bound implies other set variable 'implvars[w]' with a non-worse bound than the
764 * bound so we can remove the set variable 'var'
765 */
766 if( issetvar[idx] > 0 && bounds[issetvar[idx] - 1] <= implbounds[w] )
767 {
768 SCIPdebugMsg(scip, "set variable <%s> %s %g implies other set variable <%s> %s %g (%g)\n",
769 SCIPvarGetName(var), boundtypes[pos] ? "<=" : ">=", bounds[pos], SCIPvarGetName(implvars[w]),
770 ">=", implbounds[w], bounds[issetvar[idx] - 1]);
771
772 issetvar[varidx] = -1;
773 break;
774 }
775
776 /* ignore implications that are redundant with respect to the current global bounds (see #2888) */
777 redundant = SCIPisGE(scip, SCIPvarGetLbGlobal(implvars[w]), implbounds[w]);
778
779 /* update implication counter */
780 if( counts[idx] == pos - nredvars && !redundant )
781 {
782 ++counts[idx];
783
784 if( SCIPvarIsBinary(implvars[w]) )
785 {
786 /* the implied lower bound on a binary variable should not be trivial, otherwise we might globally fix
787 * this variable to a wrong value
788 *
789 * @note is is possible that the implied bound is greater than one, when the implied variable has
790 * become binary during the search
791 */
792 assert(SCIPisFeasGE(scip, implbounds[w], 1.0));
793 *foundbin = MIN(*foundbin, idx);
794
795 if( counts[idx] == 1 )
796 {
797 assert(*ncountnonzeros < 2*nvars);
798 countnonzeros[*ncountnonzeros] = idx;
799 ++(*ncountnonzeros);
800 }
801 }
802 else
803 {
804 *foundnonbin = MIN(*foundnonbin, idx);
805
806 if( counts[idx] == 1 )
807 {
808 assert(*ncountnonzeros < 2*nvars);
809 countnonzeros[*ncountnonzeros] = idx;
810 ++(*ncountnonzeros);
811 newbounds[idx] = implbounds[w];
812 lastbounds[*nimplidx] = SCIP_INVALID;
813 }
814 else if( newbounds[idx] > implbounds[w] )
815 {
816 lastbounds[*nimplidx] = newbounds[idx];
817 newbounds[idx] = implbounds[w];
818 }
819 else
820 lastbounds[*nimplidx] = SCIP_INVALID;
821 }
822
823 implidx[*nimplidx] = idx;
824 ++(*nimplidx);
825 }
826 }
827 }
828 }
829}
830
831/** collect clique data on binary variables for variable set reduction and global bound implications */
832static
833void collectBinaryCliqueData(
834 SCIP_VAR* var, /**< set variable */
835 int varidx, /**< for lower bound set variable index, for upper bound set variable index
836 * + number of variables
837 */
838 int pos, /**< variables's position in bdchinfos */
839 int nredvars, /**< number of reduced variables so far */
840 SCIP_Bool value, /**< value used for clique and implication info */
841 SCIP_Real* bounds, /**< array of bounds where one of them must be fullfilled */
842 SCIP_Bool* boundtypes, /**< array of bound types */
843 SCIP_Real* newbounds, /**< array of implied bounds(, size is two times number of variables, first
844 * half for implied lower bounds, second for implied upper bounds)
845 */
846 int* counts, /**< array of number of implication on a bound (, size is two times number of
847 * variables, first half for implied lower bounds, second for implied upper
848 * bounds)
849 */
850 int* countnonzeros, /**< array to store the indices of non-zero entries in the counts array */
851 int* ncountnonzeros, /**< pointer to store the number of non-zero entries in the counts array */
852 int* issetvar, /**< array containing for set variables the position in the current set, or
853 * 0 if it is not a set variable, or -1, if it is a redundant (i.e. implies
854 * another set variable) set variable
855 * (the size of the array is two times the number of variables, first half
856 * for implied lower bounds, second for implied upper bounds)
857 */
858 int nvars, /**< number of problem variables */
859 int* foundbin, /**< pointer to store the lowest index of a binary implication variable when found */
860 int* implidx, /**< array to store the variable indices (for upper bound 'nvars' is added
861 * to the index) which are implied
862 */
863 int* nimplidx /**< pointer to store the number of implied variables */
864 )
865{
866 SCIP_CLIQUE** cliques;
867 SCIP_VAR** clqvars;
868 SCIP_Bool* clqvalues;
869 int idx;
870 int c;
871 int w;
872
873 assert(var != NULL);
874 assert(SCIPvarIsBinary(var));
875 assert(varidx >= 0);
876 assert(pos >= 0);
877 assert(bounds != NULL);
878 assert(boundtypes != NULL);
879 assert(newbounds != NULL);
880 assert(counts != NULL);
881 assert(issetvar != NULL);
882 assert(2 * nvars > varidx);
883 assert(foundbin != NULL);
884 assert(implidx != NULL);
885 assert(nimplidx != NULL);
886
887 /* implication counter cannot exceed number implication variables */
888 assert(counts[varidx] <= pos - nredvars);
889
890 /* if the set variable is not yet redundant we might increase the self implication counter */
891 if( issetvar[varidx] > 0 )
892 {
893 /* update implication counter for set variables */
894 if( counts[varidx] == pos - nredvars )
895 {
896 ++counts[varidx];
897 *foundbin = MIN(*foundbin, varidx);
898
899 if( counts[varidx] == 1 )
900 {
901 assert(*ncountnonzeros < 2*nvars);
902 countnonzeros[*ncountnonzeros] = varidx;
903 ++(*ncountnonzeros);
904 }
905
906 implidx[*nimplidx] = varidx;
907 ++(*nimplidx);
908 }
909 }
910
911 cliques = SCIPvarGetCliques(var, value);
912
913 /* update implication counter on all by cliques implied variables */
914 for( c = SCIPvarGetNCliques(var, value) - 1; c >= 0; --c )
915 {
916 clqvars = SCIPcliqueGetVars(cliques[c]);
917 clqvalues = SCIPcliqueGetValues(cliques[c]);
918
919 for( w = SCIPcliqueGetNVars(cliques[c]) - 1; w >= 0; --w )
920 {
921 /* already handle self-implication and do not look at fixed variables */
922 if( clqvars[w] == var || SCIPvarGetLbGlobal(clqvars[w]) > 0.5 || SCIPvarGetUbGlobal(clqvars[w]) < 0.5 )
923 continue;
924
925 idx = SCIPvarGetProbindex(clqvars[w]);
926 assert(idx >= 0);
927
928 if( clqvalues[w] )
929 idx += nvars;
930
931 assert(counts[idx] <= pos - nredvars + 1);
932
933 /* set variable 'var' with bound implies other set variable 'clqvars[w]' with corresponding set bound so we can
934 * remove the set variable 'var'
935 */
936 if( issetvar[idx] > 0 )
937 {
938 SCIPdebugMessage("set variable <%s> %s %g implies other set variable <%s> %s %g\n",
939 SCIPvarGetName(var), boundtypes[pos] ? "<=" : ">=", bounds[pos], SCIPvarGetName(clqvars[w]),
940 clqvalues[w] ? "<=" : ">=", clqvalues[w] ? 0.0 : 1.0);
941
942 issetvar[varidx] = -1;
943 break;
944 }
945
946 /* update implication counter */
947 if( counts[idx] == pos - nredvars )
948 {
949 ++counts[idx];
950 *foundbin = MIN(*foundbin, idx);
951
952 if( counts[idx] == 1 )
953 {
954 assert(*ncountnonzeros < 2*nvars);
955 countnonzeros[*ncountnonzeros] = idx;
956 ++(*ncountnonzeros);
957 }
958
959 implidx[*nimplidx] = idx;
960 ++(*nimplidx);
961 }
962 }
963 }
964}
965
966
967
968/*
969 * presolving methods
970 */
971
972#define CLEARRATIO 0.8
973
974/** try to reduce the necessary variable in a set of variables with corresponding bounds and boundtypes for which one
975 * must be fulfilled
976 *
977 * e.g. a set of logicor or bounddisjunctive constraint variables would be such a set
978 *
979 * consider the following set:
980 *
981 * x1 >= 1, x2 >= 3, x3 >= 1, x4 <= 0
982 *
983 * by (global) implication data (cliques, implications, and variable bounds) we have also the following implications
984 * given:
985 *
986 * x1 >= 1 => x3 >= 1
987 * x2 >= 2 => x3 >= 1
988 * x4 <= 0 => x1 >= 1
989 *
990 * Because of the last implication x4 is redundant, because x1 >= 1 would also be fulfilled in the variable set, so we
991 * can reduce the set by x4.
992 * Also, the both other implications and x3 >= 1 (in the given variable set) all imply exactly x3 >= 1, so we tighten
993 * the global lower bound of x3 to 1 and the set of variables gets redundant.
994 */
995SCIP_RETCODE SCIPshrinkDisjunctiveVarSet(
996 SCIP* scip, /**< SCIP data structure */
997 SCIP_VAR** vars, /**< variables array for which at least one must be fulfilled in the
998 * following bounds and boundtypes */
999 SCIP_Real* bounds, /**< bounds array for which at least one must be fulfilled */
1000 SCIP_Bool* boundtypes, /**< boundtypes array (TRUE == SCIP_BOUNDTYPE_UPPER, FALSE == SCIP_BOUNDTYPE_LOWER)
1001 * for which at least one must be fulfilled */
1002 SCIP_Bool* redundants, /**< array which be filled and then indicate if a variable in the set is redundant */
1003 int nvars, /**< number of variables */
1004 int* nredvars, /**< pointer to store how many variables can be removed */
1005 int* nglobalred, /**< pointer to store number of global reductions on variable bounds found
1006 * through this set of variables */
1007 SCIP_Bool* setredundant, /**< pointer to store if we found a global reduction on a variable which was part
1008 * of the given set of variables, this makes this disjunction redundant */
1009 SCIP_Bool* glbinfeas, /**< pointer to store if global infeasibility was detected */
1010 SCIP_Bool fullshortening /**< do we want to try the shortening procedure over the whole set (which might be expensive) */
1011 )
1012{
1013 SCIP_Real* newbounds; /* array saving all overall implied global bounds, first nprobvars for lower bound, second
1014 * nprobvars for upper bound
1015 */
1016 SCIP_Real* lastbounds;/* temporary array to remember last implied bounds before taken the current variable into
1017 * account, first nprobvars for lower bound, second nprobvars for upper bound
1018 *
1019 * this array is used when a set variable got redundant, because it implies another set
1020 * variable, and we need to correct the counts array
1021 */
1022 int* issetvar; /* array for mapping from a problem variable to the position in the variable set (,pos + 1 in
1023 * the variable set, 0 for no set variable, and -1 if this variable was removed from the set),
1024 * first nprobvars for lower bound, second nprobvars for upper bound
1025 */
1026 int* counts; /* array saving number of implication by set variables, first nprobvars for lower bound, second
1027 * nprobvars for upper bound
1028 */
1029 int* implidx; /* temporary array to remember all indices of implied variables by the current set variable
1030 * looked at, first nprobvars for lower bound, second nprobvars for upper bound
1031 *
1032 * this array is used when a set variable got redundant, because it implies another set
1033 * variable, and we need to correct the counts array
1034 */
1035 int* countnonzeros;
1036
1037 SCIP_VAR* var;
1038 SCIP_Bool usebin = TRUE;
1039 SCIP_Bool usenonbin = TRUE;
1040 SCIP_Bool globalred = TRUE;
1041 SCIP_Bool reducedset;
1042 SCIP_Bool value;
1043 SCIP_Bool implbinvarsexist;
1044 int start = INT_MAX;
1045 int nimplidx;
1046 int foundbin;
1047 int foundnonbin;
1048 int varidx;
1049 int nprobvars;
1050 int ncountnonzeros;
1051 int maxcountnonzeros;
1052 int w;
1053 int v;
1054
1055 if( nvars == 0 )
1056 return SCIP_OKAY;
1057
1058 assert(scip != NULL);
1059 assert(vars != NULL);
1060 assert(bounds != NULL);
1061 assert(boundtypes != NULL);
1062 assert(redundants != NULL);
1063 assert(nredvars != NULL);
1064 assert(nglobalred != NULL);
1065 assert(setredundant != NULL);
1066 assert(glbinfeas != NULL);
1067 assert(scip->transprob != NULL);
1068 nprobvars = SCIPprobGetNVars(scip->transprob);
1069
1070 /* allocate temporary memory */
1071 SCIP_CALL( SCIPallocCleanBufferArray(scip, &issetvar, 2*nprobvars) ); /*lint !e647*/
1072 SCIP_CALL( SCIPallocCleanBufferArray(scip, &counts, 2*nprobvars) ); /*lint !e647*/
1073 SCIP_CALL( SCIPallocBufferArray(scip, &newbounds, 2*nprobvars) );
1074 SCIP_CALL( SCIPallocBufferArray(scip, &lastbounds, 2*nprobvars) );
1075 SCIP_CALL( SCIPallocBufferArray(scip, &implidx, 2*nprobvars) );
1076 SCIP_CALL( SCIPallocBufferArray(scip, &countnonzeros, 2*nprobvars) );
1077
1078 *nredvars = 0;
1079 *glbinfeas = FALSE;
1080 ncountnonzeros = 0;
1081
1082 maxcountnonzeros = (int)(2*nprobvars*CLEARRATIO); /*lint !e790*/
1083
1084 /* initialize variable indices data */
1085 for( v = 0; v < nvars; ++v )
1086 {
1087 varidx = SCIPvarGetProbindex(vars[v]);
1088 assert(varidx >= 0);
1089
1090 if( boundtypes[v] )
1091 varidx += nprobvars;
1092
1093 /* initialize issetvar array */
1094 issetvar[varidx] = v+1;
1095 }
1096
1097 /* check if implicit binary variables exist, because for these variables the implications can be stored in the
1098 * variable bounds instead of the 'normal' implications
1099 */
1100 implbinvarsexist = (SCIPprobGetNImplBinVars(scip->transprob) > 0);
1101
1102#if 0
1103 /* @todo do the cleanup here rather than before calling SCIPshrinkDisjunctiveVarSet()? */
1104 if( usebin )
1105 {
1106 SCIP_Bool infeasible;
1107
1108 SCIP_CALL( SCIPcleanupCliques(scip, &infeasible) );
1109 }
1110#endif
1111
1112 /* check for same implicit binary variables */
1113 for( v = 0; v < nvars; ++v )
1114 {
1115 var = vars[v];
1116
1117 foundbin = INT_MAX;
1118 foundnonbin = INT_MAX;
1119 reducedset = FALSE;
1120 nimplidx = 0;
1121
1122 value = (!boundtypes[v]);
1123
1124 varidx = SCIPvarGetProbindex(var);
1125 assert(varidx >= 0);
1126
1127 if( !value )
1128 varidx += nprobvars;
1129
1130 if( usebin )
1131 {
1132 /* collect clique data on binary variables */
1133 if( SCIPvarIsBinary(var) )
1134 {
1135 collectBinaryCliqueData(var, varidx, v, *nredvars, value, bounds, boundtypes, newbounds, counts, countnonzeros,
1136 &ncountnonzeros, issetvar, nprobvars, &foundbin, implidx, &nimplidx);
1137 }
1138 }
1139
1140 /* only variable which have the vartype SCIP_VARTYPE_BINARY have implications, otherwise the implications are
1141 * saved as variable bounds
1142 *
1143 * we only check binary to non-binary implications if we can detect further implications which either lead to
1144 * global reductions or to redundant set variables
1145 */
1146 if( SCIPvarGetType(var) == SCIP_VARTYPE_BINARY && ((usebin && implbinvarsexist) || usenonbin) )
1147 {
1148 collectNonBinaryImplicationData(scip, var, varidx, v, *nredvars, value, bounds, boundtypes, newbounds, counts,
1149 countnonzeros, &ncountnonzeros, issetvar, nprobvars, &foundbin, &foundnonbin, implidx, &nimplidx, lastbounds);
1150 }
1151 /* only variable which have the vartype != SCIP_VARTYPE_BINARY have variable bounds
1152 *
1153 * we only check the variable bounds if we can detect further implications which either lead to global reductions
1154 * or to redundant set variables
1155 */
1156 else if( SCIPvarGetType(var) != SCIP_VARTYPE_BINARY && ((usebin && implbinvarsexist) || usenonbin) )
1157 {
1158 collectNonBinaryVBoundData(scip, var, varidx, v, *nredvars, bounds, boundtypes, newbounds, counts, countnonzeros,
1159 &ncountnonzeros, issetvar, nprobvars, &foundbin, &foundnonbin, implidx, &nimplidx, lastbounds);
1160 }
1161
1162 /* reduce implication counters on all variables which are implied by a variable now marked as redundant */
1163 if( issetvar[varidx] < 0 )
1164 {
1165 SCIP_VAR** probvars;
1166 int probidx;
1167
1168 SCIPdebugMsg(scip, "marked variable <%s> as redundant variable in variable set\n", SCIPvarGetName(var));
1169
1170 probvars = SCIPprobGetVars(scip->transprob);
1171 assert(probvars != NULL);
1172
1173 /* correct implication counters and bounds, if the redundant variable implies other variables we need to reduce
1174 * the counter and get the last bounds before this implication
1175 */
1176 for( w = nimplidx - 1; w >= 0; --w )
1177 {
1178 assert(implidx[w] < 2 * nprobvars);
1179 assert(counts[implidx[w]] == v - (*nredvars) + 1);
1180
1181 --counts[implidx[w]];
1182
1183 if( implidx[w] == countnonzeros[ncountnonzeros-1] && counts[implidx[w]] == 0 )
1184 --ncountnonzeros;
1185
1186 probidx = implidx[w] < nprobvars ? implidx[w] : implidx[w] - nprobvars;
1187 /* only for non-binary variables we need to correct the bounds */
1188 if( !SCIPvarIsBinary(probvars[probidx]) && lastbounds[w] != SCIP_INVALID )/*lint !e777*/
1189 newbounds[implidx[w]] = lastbounds[w];
1190 }
1191
1192 reducedset = TRUE;
1193 ++(*nredvars);
1194 }
1195
1196 /* check if we want to shorten the whole set of variables, or terminate early if we did not find any further
1197 * implication
1198 */
1199 if( !fullshortening )
1200 {
1201 /* check if it makes sense to look for further binary implications */
1202 if( foundbin < INT_MAX && !reducedset )
1203 usebin = FALSE;
1204 /* check if it makes sense to look for further non-binary implications */
1205 if( foundnonbin < INT_MAX && !reducedset )
1206 usenonbin = FALSE;
1207 }
1208
1209 /* are global reductions still possible */
1210 globalred = globalred && (foundbin < INT_MAX || foundnonbin < INT_MAX);
1211
1212 /* remember the first possible position for a global bound change */
1213 if( globalred )
1214 {
1215 /* get correct variable index(, we added nprobvars for the upper bound implication) */
1216 if( foundbin < INT_MAX && foundbin >= nprobvars )
1217 foundbin -= nprobvars;
1218
1219 /* get correct variable index(, we added nprobvars for the upper bound implication) */
1220 if( foundnonbin < INT_MAX && foundnonbin >= nprobvars )
1221 foundnonbin -= nprobvars;
1222
1223 if( start > foundbin )
1224 start = foundbin;
1225
1226 if( start > foundnonbin )
1227 start = foundnonbin;
1228 }
1229 else
1230 start = INT_MAX;
1231
1232 /* check if it can find any global implications anymore */
1233 if( !usebin && !usenonbin )
1234 break;
1235 }
1236
1237 /* remove redundant set variables */
1238 if( *nredvars > 0 )
1239 {
1240#ifndef NDEBUG
1241 int nreds = 0;
1242#endif
1243
1244 for( v = nvars - 1; v >= 0; --v )
1245 {
1246 var = vars[v];
1247
1248 varidx = SCIPvarGetProbindex(var);
1249 assert(varidx >= 0);
1250
1251 if( boundtypes[v] )
1252 varidx += nprobvars;
1253
1254 /* if set variable was marked to be redundant remove it */
1255 if( issetvar[varidx] < 0 )
1256 {
1257 SCIPdebugMsg(scip, "mark redundant variable <%s> to be removed from variable set\n", SCIPvarGetName(var));
1258
1259 redundants[v] = TRUE;
1260#ifndef NDEBUG
1261 ++nreds;
1262#endif
1263 }
1264 }
1265 assert((*nredvars) == nreds);
1266 }
1267
1268 /* if we found some global boundchanges, we perform then now */
1269 if( globalred )
1270 {
1271 SCIP_VAR** probvars;
1272 SCIP_VAR* probvar;
1273
1274 SCIPdebugMsg(scip, "variable set led to global reductions (in %s)\n", SCIPprobGetName(scip->transprob));
1275
1276 probvars = SCIPprobGetVars(scip->transprob);
1277 assert(probvars != NULL);
1278
1279 assert(start < nprobvars);
1280
1281 /* check for same implicit binary variables */
1282 for( v = start; v < nprobvars; ++v )
1283 {
1284 probvar = probvars[v];
1285 assert(probvar != NULL);
1286
1287 assert(counts[v] <= nvars);
1288 assert(counts[nprobvars + v] <= nvars);
1289
1290 if( counts[v] + (*nredvars) == nvars )
1291 {
1292 if( SCIPvarIsBinary(probvar) )
1293 {
1294 SCIPdebugMsg(scip, "can fix variable %s [%g, %g] to 1.0\n", SCIPvarGetName(probvar),
1295 SCIPvarGetLbGlobal(probvar), SCIPvarGetUbGlobal(probvar));
1296
1297 if( SCIPvarGetLbGlobal(probvar) < 0.5 )
1298 {
1299 SCIP_CALL( SCIPnodeAddBoundchg(scip->tree->root, scip->mem->probmem, scip->set, scip->stat,
1300 scip->transprob, scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand,
1301 scip->eventqueue, scip->cliquetable, probvar, 1.0, SCIP_BOUNDTYPE_LOWER, FALSE) );
1302
1303 assert(SCIPvarGetLbGlobal(probvar) > 0.5 || scip->tree->npendingbdchgs > 0);
1304
1305 ++(*nglobalred);
1306
1307 if( issetvar[v] > 0 )
1308 *setredundant = TRUE;
1309 }
1310 }
1311 else
1312 {
1313 SCIPdebugMsg(scip, "can tighten lower bound variable %s [%g, %g] to %g\n", SCIPvarGetName(probvar),
1314 SCIPvarGetLbGlobal(probvar), SCIPvarGetUbGlobal(probvar), newbounds[v]);
1315
1316 /* the new lower bound is greater than the global upper bound => the problem is global infeasible */
1317 if( SCIPisLT(scip, SCIPvarGetUbGlobal(probvar), newbounds[v]) )
1318 {
1319 SCIPdebugMsg(scip, "-> global infeasibility proven.\n");
1320
1321 *glbinfeas = TRUE;
1322 break;
1323 }
1324
1325 if( SCIPisLT(scip, SCIPvarGetLbGlobal(probvar), newbounds[v]) )
1326 {
1327 SCIP_CALL( SCIPnodeAddBoundchg(scip->tree->root, scip->mem->probmem, scip->set, scip->stat,
1328 scip->transprob, scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand,
1329 scip->eventqueue, scip->cliquetable, probvar, newbounds[v], SCIP_BOUNDTYPE_LOWER, FALSE) );
1330
1331 ++(*nglobalred);
1332
1333 if( issetvar[v] > 0 && newbounds[v] >= bounds[issetvar[v] - 1] )
1334 *setredundant = TRUE;
1335 }
1336 }
1337 }
1338 else if( counts[nprobvars + v] + (*nredvars) == nvars )
1339 {
1340 if( SCIPvarIsBinary(probvar) )
1341 {
1342 SCIPdebugMsg(scip, "can fix variable %s [%g, %g] to 0.0\n", SCIPvarGetName(probvar),
1343 SCIPvarGetLbGlobal(probvar), SCIPvarGetUbGlobal(probvar));
1344
1345 if( SCIPvarGetUbGlobal(probvar) > 0.5 )
1346 {
1347 SCIP_CALL( SCIPnodeAddBoundchg(scip->tree->root, scip->mem->probmem, scip->set, scip->stat,
1348 scip->transprob, scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue,
1349 scip->cliquetable, probvar, 0.0, SCIP_BOUNDTYPE_UPPER, FALSE) );
1350
1351 assert(SCIPvarGetUbGlobal(probvar) < 0.5 || scip->tree->npendingbdchgs > 0);
1352
1353 ++(*nglobalred);
1354
1355 if( issetvar[nprobvars + v] > 0 )
1356 *setredundant = TRUE;
1357 }
1358 }
1359 else
1360 {
1361 int idx = nprobvars + v;
1362
1363 SCIPdebugMsg(scip, "can tighten upper bound variable %s [%g, %g] to %g\n", SCIPvarGetName(probvar),
1364 SCIPvarGetLbGlobal(probvar), SCIPvarGetUbGlobal(probvar), newbounds[idx]);
1365
1366 /* the new upper bound is small than the global upper bound => the problem is global infeasible */
1367 if( SCIPisGT(scip, SCIPvarGetLbGlobal(probvar), newbounds[idx]) )
1368 {
1369 SCIPdebugMsg(scip, "-> global infeasibility proven.\n");
1370
1371 *glbinfeas = TRUE;
1372 break;
1373 }
1374
1375 if( SCIPisGT(scip, SCIPvarGetUbGlobal(probvar), newbounds[idx]) )
1376 {
1377 SCIP_CALL( SCIPnodeAddBoundchg(scip->tree->root, scip->mem->probmem, scip->set, scip->stat,
1378 scip->transprob, scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue,
1379 scip->cliquetable, probvar, newbounds[idx], SCIP_BOUNDTYPE_UPPER, FALSE) );
1380
1381 ++(*nglobalred);
1382
1383 if( issetvar[idx] > 0 && newbounds[idx] <= bounds[issetvar[idx] - 1] )
1384 *setredundant = TRUE;
1385 }
1386 }
1387 }
1388 }
1389 }
1390
1391 /* reset issetvar array to 0 */
1392 for( v = 0; v < nvars; ++v )
1393 {
1394 varidx = SCIPvarGetProbindex(vars[v]);
1395 assert(varidx >= 0);
1396
1397 if( boundtypes[v] )
1398 varidx += nprobvars;
1399
1400 issetvar[varidx] = 0;
1401 }
1402
1403 if( ncountnonzeros >= maxcountnonzeros )
1404 {
1405 BMSclearMemoryArray(counts, 2*nprobvars);
1406 }
1407 else
1408 {
1409 while( --ncountnonzeros >= 0 )
1410 counts[countnonzeros[ncountnonzeros]] = 0;
1411 }
1412
1413 SCIPfreeBufferArray(scip, &countnonzeros);
1414 SCIPfreeBufferArray(scip, &implidx);
1415 SCIPfreeBufferArray(scip, &lastbounds);
1416 SCIPfreeBufferArray(scip, &newbounds);
1417 SCIPfreeCleanBufferArray(scip, &counts);
1418 SCIPfreeCleanBufferArray(scip, &issetvar);
1419
1420 return SCIP_OKAY;
1421}
w
SCIP_VAR * w
Definition: circlepacking.c:67
NULL
#define NULL
Definition: def.h:267
SCIP_INVALID
#define SCIP_INVALID
Definition: def.h:193
SCIP_Bool
#define SCIP_Bool
Definition: def.h:91
MIN
#define MIN(x, y)
Definition: def.h:243
SCIP_Real
#define SCIP_Real
Definition: def.h:173
TRUE
#define TRUE
Definition: def.h:93
FALSE
#define FALSE
Definition: def.h:94
SCIP_CALL
#define SCIP_CALL(x)
Definition: def.h:374
SCIPdebugMsg
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIPfreeCleanBufferArray
#define SCIPfreeCleanBufferArray(scip, ptr)
Definition: scip_mem.h:146
SCIPallocCleanBufferArray
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:142
SCIPallocBufferArray
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
SCIPfreeBufferArray
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
SCIPshrinkDisjunctiveVarSet
SCIP_RETCODE SCIPshrinkDisjunctiveVarSet(SCIP *scip, SCIP_VAR **vars, SCIP_Real *bounds, SCIP_Bool *boundtypes, SCIP_Bool *redundants, int nvars, int *nredvars, int *nglobalred, SCIP_Bool *setredundant, SCIP_Bool *glbinfeas, SCIP_Bool fullshortening)
Definition: presolve.c:995
SCIPisFeasGE
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:832
SCIPisGE
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:497
SCIPisFeasEQ
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:780
SCIPisLE
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:471
SCIPisFeasLT
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:793
SCIPisFeasLE
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:806
SCIPisGT
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:484
SCIPisFeasGT
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:819
SCIPisZero
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:558
SCIPisLT
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:458
SCIPvarGetNVlbs
int SCIPvarGetNVlbs(SCIP_VAR *var)
Definition: var.c:18270
SCIPvarGetVlbCoefs
SCIP_Real * SCIPvarGetVlbCoefs(SCIP_VAR *var)
Definition: var.c:18292
SCIPvarIsBinary
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17599
SCIPvarGetNImpls
int SCIPvarGetNImpls(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18356
SCIPvarGetType
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17584
SCIPvarGetUbGlobal
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18088
SCIPvarGetImplVars
SCIP_VAR ** SCIPvarGetImplVars(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18373
SCIPvarGetProbindex
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17768
SCIPvarGetName
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
SCIPcleanupCliques
SCIP_RETCODE SCIPcleanupCliques(SCIP *scip, SCIP_Bool *infeasible)
Definition: scip_var.c:7532
SCIPvarGetVlbConstants
SCIP_Real * SCIPvarGetVlbConstants(SCIP_VAR *var)
Definition: var.c:18302
SCIPvarGetNVubs
int SCIPvarGetNVubs(SCIP_VAR *var)
Definition: var.c:18312
SCIPvarGetImplBounds
SCIP_Real * SCIPvarGetImplBounds(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18402
SCIPvarGetNCliques
int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18430
SCIPvarGetVlbVars
SCIP_VAR ** SCIPvarGetVlbVars(SCIP_VAR *var)
Definition: var.c:18282
SCIPvarGetCliques
SCIP_CLIQUE ** SCIPvarGetCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18441
SCIPvarGetLbGlobal
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18078
SCIPvarGetVubConstants
SCIP_Real * SCIPvarGetVubConstants(SCIP_VAR *var)
Definition: var.c:18344
SCIPvarGetVubVars
SCIP_VAR ** SCIPvarGetVubVars(SCIP_VAR *var)
Definition: var.c:18324
SCIPvarGetVubCoefs
SCIP_Real * SCIPvarGetVubCoefs(SCIP_VAR *var)
Definition: var.c:18334
SCIPvarGetImplTypes
SCIP_BOUNDTYPE * SCIPvarGetImplTypes(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18388
SCIPcliqueGetVars
SCIP_VAR ** SCIPcliqueGetVars(SCIP_CLIQUE *clique)
Definition: implics.c:3380
SCIPcliqueGetNVars
int SCIPcliqueGetNVars(SCIP_CLIQUE *clique)
Definition: implics.c:3370
SCIPcliqueGetValues
SCIP_Bool * SCIPcliqueGetValues(SCIP_CLIQUE *clique)
Definition: implics.c:3392
memory.h
memory allocation routines
BMSclearMemoryArray
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:130
collectNonBinaryVBoundData
static void collectNonBinaryVBoundData(SCIP *scip, SCIP_VAR *var, int varidx, int pos, int nredvars, SCIP_Real *bounds, SCIP_Bool *boundtypes, SCIP_Real *newbounds, int *counts, int *countnonzeros, int *ncountnonzeros, int *issetvar, int nvars, int *foundbin, int *foundnonbin, int *implidx, int *nimplidx, SCIP_Real *lastbounds)
Definition: presolve.c:57
collectBinaryCliqueData
static void collectBinaryCliqueData(SCIP_VAR *var, int varidx, int pos, int nredvars, SCIP_Bool value, SCIP_Real *bounds, SCIP_Bool *boundtypes, SCIP_Real *newbounds, int *counts, int *countnonzeros, int *ncountnonzeros, int *issetvar, int nvars, int *foundbin, int *implidx, int *nimplidx)
Definition: presolve.c:833
CLEARRATIO
#define CLEARRATIO
Definition: presolve.c:972
collectNonBinaryImplicationData
static void collectNonBinaryImplicationData(SCIP *scip, SCIP_VAR *var, int varidx, int pos, int nredvars, SCIP_Bool value, SCIP_Real *bounds, SCIP_Bool *boundtypes, SCIP_Real *newbounds, int *counts, int *countnonzeros, int *ncountnonzeros, int *issetvar, int nvars, int *foundbin, int *foundnonbin, int *implidx, int *nimplidx, SCIP_Real *lastbounds)
Definition: presolve.c:595
presolve.h
methods commonly used for presolving
SCIPprobGetName
const char * SCIPprobGetName(SCIP_PROB *prob)
Definition: prob.c:2384
SCIPprobGetNImplBinVars
int SCIPprobGetNImplBinVars(SCIP_PROB *prob)
Definition: prob.c:2043
SCIPprobGetNVars
int SCIPprobGetNVars(SCIP_PROB *prob)
Definition: prob.c:2393
SCIPprobGetVars
SCIP_VAR ** SCIPprobGetVars(SCIP_PROB *prob)
Definition: prob.c:2438
prob.h
internal methods for storing and manipulating the main problem
pub_implics.h
public methods for implications, variable bounds, and cliques
pub_message.h
public methods for message output
SCIPdebugMessage
#define SCIPdebugMessage
Definition: pub_message.h:96
pub_var.h
public methods for problem variables
scip_mem.h
public methods for memory management
scip_message.h
public methods for message handling
scip_numerics.h
public methods for numerical tolerances
scip_tree.h
public methods for the branch-and-bound tree
SCIP_Clique
Definition: struct_implics.h:76
SCIP_Var
Definition: struct_var.h:208
struct_mem.h
datastructures for block memory pools and memory buffers
struct_scip.h
SCIP main data structure.
SCIPnodeAddBoundchg
SCIP_RETCODE SCIPnodeAddBoundchg(SCIP_NODE *node, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_CLIQUETABLE *cliquetable, SCIP_VAR *var, SCIP_Real newbound, SCIP_BOUNDTYPE boundtype, SCIP_Bool probingchange)
Definition: tree.c:2097
tree.h
internal methods for branch and bound tree
SCIP_BOUNDTYPE_UPPER
@ SCIP_BOUNDTYPE_UPPER
Definition: type_lp.h:57
SCIP_BOUNDTYPE_LOWER
@ SCIP_BOUNDTYPE_LOWER
Definition: type_lp.h:56
SCIP_BOUNDTYPE
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:59
SCIP_OKAY
@ SCIP_OKAY
Definition: type_retcode.h:42
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
SCIP_VARTYPE_BINARY
@ SCIP_VARTYPE_BINARY
Definition: type_var.h:62