Scippy

SCIP

Solving Constraint Integer Programs

presol_domcol.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_domcol.c
26 * @ingroup DEFPLUGINS_PRESOL
27 * @brief dominated column presolver
28 * @author Dieter Weninger
29 * @author Gerald Gamrath
30 *
31 * This presolver looks for dominance relations between variable pairs.
32 * From a dominance relation and certain bound/clique-constellations
33 * variable fixings mostly at the lower bound of the dominated variable can be derived.
34 * Additionally it is possible to improve bounds by predictive bound strengthening.
35 *
36 * @todo Also run on general CIPs, if the number of locks of the investigated variables comes only from (upgraded)
37 * linear constraints.
38 *
39 * @todo Instead of choosing variables for comparison out of one row, we should try to use 'hashvalues' for columns that
40 * indicate in which constraint type (<=, >=, or ranged row / ==) they are existing. Then sort the variables (and
41 * corresponding data) after the ranged row/equation hashvalue and only try to derive dominance on variables with
42 * the same hashvalue on ranged row/equation and fitting hashvalues for the other constraint types.
43 * @todo run on incomplete matrices; in order to do so, check at the time when dominance is detected that the locks are
44 * consistent; probably, it is sufficient to check one lock direction for each of the two variables
45 *
46 */
47
48/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
49
50#include "blockmemshell/memory.h"
51#include "scip/presol_domcol.h"
52#include "scip/pub_matrix.h"
53#include "scip/pub_message.h"
54#include "scip/pub_misc_sort.h"
55#include "scip/pub_presol.h"
56#include "scip/pub_var.h"
57#include "scip/scip_general.h"
58#include "scip/scip_mem.h"
59#include "scip/scip_message.h"
60#include "scip/scip_nlp.h"
61#include "scip/scip_numerics.h"
62#include "scip/scip_param.h"
63#include "scip/scip_presol.h"
64#include "scip/scip_pricer.h"
65#include "scip/scip_prob.h"
66#include "scip/scip_probing.h"
67#include "scip/scip_var.h"
68#include <string.h>
69
70#define PRESOL_NAME "domcol"
71#define PRESOL_DESC "dominated column presolver"
72#define PRESOL_PRIORITY -1000 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */
73#define PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
74#define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */
75
76#define DEFAULT_NUMMINPAIRS 1024 /**< minimal number of pair comparisons */
77#define DEFAULT_NUMMAXPAIRS 1048576 /**< maximal number of pair comparisons */
78
79#define DEFAULT_PREDBNDSTR FALSE /**< should predictive bound strengthening be applied? */
80#define DEFAULT_CONTINUOUS_RED TRUE /**< should reductions for continuous variables be carried out? */
81
82
83
84/*
85 * Data structures
86 */
87
88/** control parameters */
89struct SCIP_PresolData
90{
91 int numminpairs; /**< minimal number of pair comparisons */
92 int nummaxpairs; /**< maximal number of pair comparisons */
93 int numcurrentpairs; /**< current number of pair comparisons */
94 SCIP_Bool predbndstr; /**< flag indicating if predictive bound strengthening should be applied */
95 SCIP_Bool continuousred; /**< flag indicating if reductions for continuous variables should be performed */
96};
97
98/** type of fixing direction */
99enum Fixingdirection
100{
101 FIXATLB = -1, /**< fix variable at lower bound */
102 NOFIX = 0, /**< do not fix variable */
103 FIXATUB = 1 /**< fix variable at upper bound */
104};
105typedef enum Fixingdirection FIXINGDIRECTION;
106
107
108/*
109 * Local methods
110 */
111#ifdef SCIP_DEBUG
112/** print a row from the constraint matrix */
113static
114void printRow(
115 SCIP* scip, /**< SCIP main data structure */
116 SCIP_MATRIX* matrix, /**< matrix containing the constraints */
117 int row /**< row index for printing */
118 )
119{
120 int* rowpnt;
121 int* rowend;
122 int c;
123 SCIP_Real val;
124 SCIP_Real* valpnt;
125 char relation;
126 SCIP_VAR* var;
127
128 relation='-';
129 if( !SCIPmatrixIsRowRhsInfinity(matrix, row) &&
130 SCIPisEQ(scip, SCIPmatrixGetRowLhs(matrix, row), SCIPmatrixGetRowRhs(matrix, row)) )
131 {
132 relation='e';
133 }
134 else if( !SCIPmatrixIsRowRhsInfinity(matrix, row) &&
135 !SCIPisEQ(scip, SCIPmatrixGetRowLhs(matrix, row), SCIPmatrixGetRowRhs(matrix, row)) )
136 {
137 relation='r';
138 }
139 else
140 {
141 relation='g';
142 }
143
144 rowpnt = SCIPmatrixGetRowIdxPtr(matrix, row);
145 rowend = rowpnt + SCIPmatrixGetRowNNonzs(matrix, row);
146 valpnt = SCIPmatrixGetRowValPtr(matrix, row);
147
148 SCIPdebugMsgPrint(scip, "\n(L:%g) [%c] %g <=",
149 (SCIPmatrixGetRowNMinActPosInf(matrix, row) + SCIPmatrixGetRowNMinActNegInf(matrix,row) > 0) ?
150 -SCIPinfinity(scip) :
151 SCIPmatrixGetRowMinActivity(matrix, row), relation, SCIPmatrixGetRowLhs(matrix, row));
152 for(; (rowpnt < rowend); rowpnt++, valpnt++)
153 {
154 c = *rowpnt;
155 val = *valpnt;
156 var = SCIPmatrixGetVar(matrix, c);
157 SCIPdebugMsgPrint(scip, " %g{%s[idx:%d][bnd:%g,%g]}",
158 val, SCIPvarGetName(var), c, SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var));
159 }
160 SCIPdebugMsgPrint(scip, " <= %g (U:%g)", (SCIPmatrixGetRowNMaxActPosInf(matrix, row) + SCIPmatrixGetRowNMaxActNegInf(matrix, row) > 0) ?
161 SCIPinfinity(scip) :
162 SCIPmatrixGetRowRhs(matrix, row), SCIPmatrixGetRowMaxActivity(matrix , row));
163}
164
165/** print all rows from the constraint matrix containing a variable */
166static
167SCIP_RETCODE printRowsOfCol(
168 SCIP* scip, /**< SCIP main data structure */
169 SCIP_MATRIX* matrix, /**< matrix containing the constraints */
170 int col /**< column index for printing */
171 )
172{
173 int numrows;
174 int* rows;
175 int i;
176 int* colpnt;
177 int* colend;
178
179 numrows = SCIPmatrixGetColNNonzs(matrix, col);
180
181 SCIP_CALL( SCIPallocBufferArray(scip, &rows, numrows) );
182
183 colpnt = SCIPmatrixGetColIdxPtr(matrix, col);
184 colend = colpnt + SCIPmatrixGetColNNonzs(matrix, col);
185 for( i = 0; (colpnt < colend); colpnt++, i++ )
186 {
187 rows[i] = *colpnt;
188 }
189
190 SCIPdebugMsgPrint(scip, "\n-------");
191 SCIPdebugMsgPrint(scip, "\ncol %d number rows: %d",col,numrows);
192 for( i = 0; i < numrows; i++ )
193 {
194 printRow(scip, matrix, rows[i]);
195 }
196 SCIPdebugMsgPrint(scip, "\n-------");
197
198 SCIPfreeBufferArray(scip, &rows);
199
200 return SCIP_OKAY;
201}
202
203/** print information about a dominance relation */
204static
205SCIP_RETCODE printDomRelInfo(
206 SCIP* scip, /**< SCIP main data structure */
207 SCIP_MATRIX* matrix, /**< matrix containing the constraints */
208 SCIP_VAR* dominatingvar, /**< dominating variable */
209 int dominatingidx, /**< index of dominating variable */
210 SCIP_VAR* dominatedvar, /**< dominated variable */
211 int dominatedidx, /**< index of dominated variable */
212 SCIP_Real dominatingub, /**< predicted upper bound of dominating variable */
213 SCIP_Real dominatingwclb /**< worst case lower bound of dominating variable */
214 )
215{
216 char type;
217
218 assert(SCIPvarGetType(dominatingvar)==SCIPvarGetType(dominatedvar));
219
220 switch(SCIPvarGetType(dominatingvar))
221 {
222 case SCIP_VARTYPE_CONTINUOUS:
223 type='C';
224 break;
225 case SCIP_VARTYPE_BINARY:
226 type='B';
227 break;
228 case SCIP_VARTYPE_INTEGER:
229 case SCIP_VARTYPE_IMPLINT:
230 type='I';
231 break;
232 default:
233 SCIPerrorMessage("unknown variable type\n");
234 SCIPABORT();
235 return SCIP_INVALIDDATA; /*lint !e527*/
236 }
237
238 SCIPdebugMsgPrint(scip, "\n\n### [%c], obj:%g->%g,\t%s[idx:%d](nrows:%d)->%s[idx:%d](nrows:%d)\twclb=%g, ub'=%g, ub=%g",
239 type, SCIPvarGetObj(dominatingvar), SCIPvarGetObj(dominatedvar),
240 SCIPvarGetName(dominatingvar), dominatingidx, SCIPmatrixGetColNNonzs(matrix, dominatingidx),
241 SCIPvarGetName(dominatedvar), dominatedidx, SCIPmatrixGetColNNonzs(matrix, dominatedidx),
242 dominatingwclb, dominatingub, SCIPvarGetUbGlobal(dominatingvar));
243
244 SCIP_CALL( printRowsOfCol(scip, matrix, dominatingidx) );
245
246 return SCIP_OKAY;
247}
248#endif
249
250
251/** get minimum/maximum residual activity for the specified variable and with another variable set to its upper bound */
252static
253void getActivityResidualsUpperBound(
254 SCIP* scip,
255 SCIP_MATRIX* matrix,
256 int row,
257 int col,
258 SCIP_Real coef,
259 int upperboundcol,
260 SCIP_Real upperboundcoef,
261 SCIP_Real* minresactivity,
262 SCIP_Real* maxresactivity,
263 SCIP_Bool* success
264 )
265{
266 SCIP_VAR* var;
267 SCIP_VAR* upperboundvar;
268 SCIP_Real lb;
269 SCIP_Real ub;
270 SCIP_Real lbupperboundvar;
271 SCIP_Real ubupperboundvar;
272 SCIP_Real tmpmaxact;
273 SCIP_Real tmpminact;
274 int maxactinf;
275 int minactinf;
276
277 assert(scip != NULL);
278 assert(matrix != NULL);
279 assert(row < SCIPmatrixGetNRows(matrix));
280 assert(minresactivity != NULL);
281 assert(maxresactivity != NULL);
282
283 var = SCIPmatrixGetVar(matrix, col);
284 upperboundvar = SCIPmatrixGetVar(matrix, upperboundcol);
285 assert(var != NULL);
286 assert(upperboundvar != NULL);
287
288 lb = SCIPvarGetLbGlobal(var);
289 ub = SCIPvarGetUbGlobal(var);
290
291 maxactinf = SCIPmatrixGetRowNMaxActPosInf(matrix, row) + SCIPmatrixGetRowNMaxActNegInf(matrix, row);
292 minactinf = SCIPmatrixGetRowNMinActPosInf(matrix, row) + SCIPmatrixGetRowNMinActNegInf(matrix, row);
293
294 assert(!SCIPisInfinity(scip, lb));
295 assert(!SCIPisInfinity(scip, -ub));
296
297 lbupperboundvar = SCIPvarGetLbGlobal(upperboundvar);
298 ubupperboundvar = SCIPvarGetUbGlobal(upperboundvar);
299
300 assert(!SCIPisInfinity(scip, lbupperboundvar));
301 assert(!SCIPisInfinity(scip, -ubupperboundvar));
302
303 tmpminact = SCIPmatrixGetRowMinActivity(matrix, row);
304 tmpmaxact = SCIPmatrixGetRowMaxActivity(matrix, row);
305
306 /* first, adjust min and max activity such that upperboundvar is always set to its upper bound */
307
308 /* abort if the upper bound is infty */
309 if( SCIPisInfinity(scip, ubupperboundvar) )
310 {
311 *success = FALSE;
312 return;
313 }
314 else
315 {
316 /* coef > 0 --> the lower bound is used for the minactivity --> update the minactivity */
317 if( upperboundcoef > 0.0 )
318 {
319 if( SCIPisInfinity(scip, -lbupperboundvar) )
320 {
321 assert(minactinf > 0);
322 minactinf--;
323 tmpminact += (upperboundcoef * ubupperboundvar);
324 }
325 else
326 {
327 tmpminact = tmpminact - (upperboundcoef * lbupperboundvar) + (upperboundcoef * ubupperboundvar);
328 }
329 }
330 /* coef < 0 --> the lower bound is used for the maxactivity --> update the maxactivity */
331 else
332 {
333 if( SCIPisInfinity(scip, -lbupperboundvar) )
334 {
335 assert(maxactinf > 0);
336 maxactinf--;
337 tmpmaxact += (upperboundcoef * ubupperboundvar);
338 }
339 else
340 {
341 tmpmaxact = tmpmaxact - (upperboundcoef * lbupperboundvar) + (upperboundcoef * ubupperboundvar);
342 }
343 }
344 }
345
346 *success = TRUE;
347
348 /* the coefficient is positive, so the upper bound contributed to the maxactivity and the lower bound to the minactivity */
349 if( coef >= 0.0 )
350 {
351 if( SCIPisInfinity(scip, ub) )
352 {
353 assert(maxactinf >= 1);
354 if( maxactinf == 1 )
355 {
356 *maxresactivity = tmpmaxact;
357 }
358 else
359 *maxresactivity = SCIPinfinity(scip);
360 }
361 else
362 {
363 if( maxactinf > 0 )
364 *maxresactivity = SCIPinfinity(scip);
365 else
366 *maxresactivity = tmpmaxact - coef * ub;
367 }
368
369 if( SCIPisInfinity(scip, -lb) )
370 {
371 assert(minactinf >= 1);
372 if( minactinf == 1 )
373 {
374 *minresactivity = tmpminact;
375 }
376 else
377 *minresactivity = -SCIPinfinity(scip);
378 }
379 else
380 {
381 if( minactinf > 0 )
382 *minresactivity = -SCIPinfinity(scip);
383 else
384 *minresactivity = tmpminact - coef * lb;
385 }
386 }
387 /* the coefficient is negative, so the lower bound contributed to the maxactivity and the upper bound to the minactivity */
388 else
389 {
390 if( SCIPisInfinity(scip, -lb) )
391 {
392 assert(maxactinf >= 1);
393 if( maxactinf == 1 )
394 {
395 *maxresactivity = tmpmaxact;
396 }
397 else
398 *maxresactivity = SCIPinfinity(scip);
399 }
400 else
401 {
402 if( maxactinf > 0 )
403 *maxresactivity = SCIPinfinity(scip);
404 else
405 *maxresactivity = tmpmaxact - coef * lb;
406 }
407
408 if( SCIPisInfinity(scip, ub) )
409 {
410 assert(minactinf >= 1);
411 if( minactinf == 1 )
412 {
413 *minresactivity = tmpminact;
414 }
415 else
416 *minresactivity = -SCIPinfinity(scip);
417 }
418 else
419 {
420 if( minactinf > 0 )
421 *minresactivity = -SCIPinfinity(scip);
422 else
423 *minresactivity = tmpminact - coef * ub;
424 }
425 }
426}
427
428/** get minimum/maximum residual activity for the specified variable and with another variable set to its lower bound */
429static
430void getActivityResidualsLowerBound(
431 SCIP* scip, /**< SCIP main data structure */
432 SCIP_MATRIX* matrix, /**< matrix containing the constraints */
433 int row, /**< row index */
434 int col, /**< column index */
435 SCIP_Real coef, /**< coefficient of the column in this row */
436 int lowerboundcol, /**< column index of variable to set to its lower bound */
437 SCIP_Real lowerboundcoef, /**< coefficient in this row of the column to be set to its lower bound */
438 SCIP_Real* minresactivity, /**< minimum residual activity of this row */
439 SCIP_Real* maxresactivity, /**< maximum residual activity of this row */
440 SCIP_Bool* success /**< pointer to store whether the computation was successful */
441 )
442{
443 SCIP_VAR* var;
444 SCIP_VAR* lowerboundvar;
445 SCIP_Real lb;
446 SCIP_Real ub;
447 SCIP_Real lblowerboundvar;
448 SCIP_Real ublowerboundvar;
449 SCIP_Real tmpmaxact;
450 SCIP_Real tmpminact;
451 int maxactinf;
452 int minactinf;
453
454 assert(scip != NULL);
455 assert(matrix != NULL);
456 assert(row < SCIPmatrixGetNRows(matrix));
457 assert(minresactivity != NULL);
458 assert(maxresactivity != NULL);
459
460 var = SCIPmatrixGetVar(matrix, col);;
461 lowerboundvar = SCIPmatrixGetVar(matrix, lowerboundcol);
462 assert(var != NULL);
463 assert(lowerboundvar != NULL);
464
465 lb = SCIPvarGetLbGlobal(var);
466 ub = SCIPvarGetUbGlobal(var);
467
468 maxactinf = SCIPmatrixGetRowNMaxActPosInf(matrix, row) + SCIPmatrixGetRowNMaxActNegInf(matrix, row);
469 minactinf = SCIPmatrixGetRowNMinActPosInf(matrix, row) + SCIPmatrixGetRowNMinActNegInf(matrix, row);
470
471 assert(!SCIPisInfinity(scip, lb));
472 assert(!SCIPisInfinity(scip, -ub));
473
474 lblowerboundvar = SCIPvarGetLbGlobal(lowerboundvar);
475 ublowerboundvar = SCIPvarGetUbGlobal(lowerboundvar);
476
477 assert(!SCIPisInfinity(scip, lblowerboundvar));
478 assert(!SCIPisInfinity(scip, -ublowerboundvar));
479
480 tmpminact = SCIPmatrixGetRowMinActivity(matrix, row);
481 tmpmaxact = SCIPmatrixGetRowMaxActivity(matrix, row);
482
483 /* first, adjust min and max activity such that lowerboundvar is always set to its lower bound */
484
485 /* abort if the lower bound is -infty */
486 if( SCIPisInfinity(scip, -lblowerboundvar) )
487 {
488 *success = FALSE;
489 return;
490 }
491 else
492 {
493 /* coef > 0 --> the upper bound is used for the maxactivity --> update the maxactivity */
494 if( lowerboundcoef > 0.0 )
495 {
496 if( SCIPisInfinity(scip, ublowerboundvar) )
497 {
498 assert(maxactinf > 0);
499 maxactinf--;
500 tmpmaxact += (lowerboundcoef * lblowerboundvar);
501 }
502 else
503 {
504 tmpmaxact = tmpmaxact - (lowerboundcoef * ublowerboundvar) + (lowerboundcoef * lblowerboundvar);
505 }
506 }
507 /* coef < 0 --> the upper bound is used for the minactivity --> update the minactivity */
508 else
509 {
510 if( SCIPisInfinity(scip, ublowerboundvar) )
511 {
512 assert(minactinf > 0);
513 minactinf--;
514 tmpminact += (lowerboundcoef * lblowerboundvar);
515 }
516 else
517 {
518 tmpminact = tmpminact - (lowerboundcoef * ublowerboundvar) + (lowerboundcoef * lblowerboundvar);
519 }
520 }
521 }
522
523 *success = TRUE;
524
525 /* the coefficient is positive, so the upper bound contributed to the maxactivity and the lower bound to the minactivity */
526 if( coef >= 0.0 )
527 {
528 if( SCIPisInfinity(scip, ub) )
529 {
530 assert(maxactinf >= 1);
531 if( maxactinf == 1 )
532 {
533 *maxresactivity = tmpmaxact;
534 }
535 else
536 *maxresactivity = SCIPinfinity(scip);
537 }
538 else
539 {
540 if( maxactinf > 0 )
541 *maxresactivity = SCIPinfinity(scip);
542 else
543 *maxresactivity = tmpmaxact - coef * ub;
544 }
545
546 if( SCIPisInfinity(scip, -lb) )
547 {
548 assert(minactinf >= 1);
549 if( minactinf == 1 )
550 {
551 *minresactivity = tmpminact;
552 }
553 else
554 *minresactivity = -SCIPinfinity(scip);
555 }
556 else
557 {
558 if( minactinf > 0 )
559 *minresactivity = -SCIPinfinity(scip);
560 else
561 *minresactivity = tmpminact - coef * lb;
562 }
563 }
564 /* the coefficient is negative, so the lower bound contributed to the maxactivity and the upper bound to the minactivity */
565 else
566 {
567 if( SCIPisInfinity(scip, -lb) )
568 {
569 assert(maxactinf >= 1);
570 if( maxactinf == 1 )
571 {
572 *maxresactivity = tmpmaxact;
573 }
574 else
575 *maxresactivity = SCIPinfinity(scip);
576 }
577 else
578 {
579 if( maxactinf > 0 )
580 *maxresactivity = SCIPinfinity(scip);
581 else
582 *maxresactivity = tmpmaxact - coef * lb;
583 }
584
585 if( SCIPisInfinity(scip, ub) )
586 {
587 assert(minactinf >= 1);
588 if( minactinf == 1 )
589 {
590 *minresactivity = tmpminact;
591 }
592 else
593 *minresactivity = -SCIPinfinity(scip);
594 }
595 else
596 {
597 if( minactinf > 0 )
598 *minresactivity = -SCIPinfinity(scip);
599 else
600 *minresactivity = tmpminact - coef * ub;
601 }
602 }
603}
604
605/** Calculate bounds of the dominated variable by rowbound analysis.
606 * We use a special kind of predictive rowbound analysis by first setting the dominating variable to its upper bound.
607 */
608static
609SCIP_RETCODE calcVarBoundsDominated(
610 SCIP* scip, /**< SCIP main data structure */
611 SCIP_MATRIX* matrix, /**< matrix containing the constraints */
612 int row, /**< current row index */
613 int coldominating, /**< column index of dominating variable */
614 SCIP_Real valdominating, /**< row coefficient of dominating variable */
615 int coldominated, /**< column index of dominated variable */
616 SCIP_Real valdominated, /**< row coefficient of dominated variable */
617 SCIP_Bool* ubcalculated, /**< was a upper bound calculated? */
618 SCIP_Real* calculatedub, /**< predicted upper bound */
619 SCIP_Bool* wclbcalculated, /**< was a lower worst case bound calculated? */
620 SCIP_Real* calculatedwclb, /**< predicted worst case lower bound */
621 SCIP_Bool* lbcalculated, /**< was a lower bound calculated? */
622 SCIP_Real* calculatedlb, /**< predicted lower bound */
623 SCIP_Bool* wcubcalculated, /**< was a worst case upper bound calculated? */
624 SCIP_Real* calculatedwcub /**< calculated worst case upper bound */
625 )
626{
627 SCIP_Real minresactivity;
628 SCIP_Real maxresactivity;
629 SCIP_Real lhs;
630 SCIP_Real rhs;
631 SCIP_Bool success;
632
633 assert(scip != NULL);
634 assert(matrix != NULL);
635 assert(0 <= row && row < SCIPmatrixGetNRows(matrix));
636 assert(0 <= coldominating && coldominating < SCIPmatrixGetNColumns(matrix));
637 assert(0 <= coldominated && coldominated < SCIPmatrixGetNColumns(matrix));
638
639 assert(ubcalculated != NULL);
640 assert(calculatedub != NULL);
641 assert(wclbcalculated != NULL);
642 assert(calculatedwclb != NULL);
643 assert(lbcalculated != NULL);
644 assert(calculatedlb != NULL);
645 assert(wcubcalculated != NULL);
646 assert(calculatedwcub != NULL);
647
648 assert(!SCIPisZero(scip, valdominated));
649 assert(SCIPmatrixGetVar(matrix, coldominated) != NULL);
650
651 *ubcalculated = FALSE;
652 *wclbcalculated = FALSE;
653 *lbcalculated = FALSE;
654 *wcubcalculated = FALSE;
655
656 /* no rowbound analysis for multiaggregated variables, which should not exist, because the matrix only consists of
657 * active variables
658 */
659 assert(SCIPvarGetStatus(SCIPmatrixGetVar(matrix, coldominating)) != SCIP_VARSTATUS_MULTAGGR);
660 assert(SCIPvarGetStatus(SCIPmatrixGetVar(matrix, coldominated)) != SCIP_VARSTATUS_MULTAGGR);
661
662 lhs = SCIPmatrixGetRowLhs(matrix, row);
663 rhs = SCIPmatrixGetRowRhs(matrix, row);
664 assert(!SCIPisInfinity(scip, lhs));
665 assert(!SCIPisInfinity(scip, -rhs));
666
667 /* get minimum/maximum activity of this row without the dominated variable */
668 getActivityResidualsUpperBound(scip, matrix, row, coldominated, valdominated, coldominating, valdominating,
669 &minresactivity, &maxresactivity, &success);
670
671 if( !success )
672 return SCIP_OKAY;
673
674 assert(!SCIPisInfinity(scip, minresactivity));
675 assert(!SCIPisInfinity(scip, -maxresactivity));
676
677 *calculatedub = SCIPinfinity(scip);
678 *calculatedwclb = -SCIPinfinity(scip);
679 *calculatedlb = -SCIPinfinity(scip);
680 *calculatedwcub = SCIPinfinity(scip);
681
682 /* predictive rowbound analysis */
683
684 if( valdominated > 0.0 )
685 {
686 /* lower bound calculation */
687 if( !SCIPisInfinity(scip, maxresactivity) )
688 {
689 *calculatedlb = (lhs - maxresactivity)/valdominated;
690 *lbcalculated = TRUE;
691 }
692
693 /* worst case calculation of lower bound */
694 if( !SCIPisInfinity(scip, -minresactivity) )
695 {
696 *calculatedwclb = (lhs - minresactivity)/valdominated;
697 *wclbcalculated = TRUE;
698 }
699 else
700 {
701 /* worst case lower bound is infinity */
702 *calculatedwclb = SCIPinfinity(scip);
703 *wclbcalculated = TRUE;
704 }
705
706 /* we can only calculate upper bounds, of the right hand side is finite */
707 if( !SCIPmatrixIsRowRhsInfinity(matrix, row) )
708 {
709 /* upper bound calculation */
710 if( !SCIPisInfinity(scip, -minresactivity) )
711 {
712 *calculatedub = (rhs - minresactivity)/valdominated;
713 *ubcalculated = TRUE;
714 }
715
716 /* worst case calculation of upper bound */
717 if( !SCIPisInfinity(scip, maxresactivity) )
718 {
719 *calculatedwcub = (rhs - maxresactivity)/valdominated;
720 *wcubcalculated = TRUE;
721 }
722 else
723 {
724 /* worst case upper bound is -infinity */
725 *calculatedwcub = -SCIPinfinity(scip);
726 *wcubcalculated = TRUE;
727 }
728 }
729 }
730 else
731 {
732 /* upper bound calculation */
733 if( !SCIPisInfinity(scip, maxresactivity) )
734 {
735 *calculatedub = (lhs - maxresactivity)/valdominated;
736 *ubcalculated = TRUE;
737 }
738
739 /* worst case calculation of upper bound */
740 if( !SCIPisInfinity(scip, -minresactivity) )
741 {
742 *calculatedwcub = (lhs - minresactivity)/valdominated;
743 *wcubcalculated = TRUE;
744 }
745 else
746 {
747 /* worst case upper bound is -infinity */
748 *calculatedwcub = -SCIPinfinity(scip);
749 *wcubcalculated = TRUE;
750 }
751
752 /* we can only calculate lower bounds, of the right hand side is finite */
753 if( !SCIPmatrixIsRowRhsInfinity(matrix, row) )
754 {
755 /* lower bound calculation */
756 if( !SCIPisInfinity(scip, -minresactivity) )
757 {
758 *calculatedlb = (rhs - minresactivity)/valdominated;
759 *lbcalculated = TRUE;
760 }
761
762 /* worst case calculation of lower bound */
763 if( !SCIPisInfinity(scip, maxresactivity) )
764 {
765 *calculatedwclb = (rhs - maxresactivity)/valdominated;
766 *wclbcalculated = TRUE;
767 }
768 else
769 {
770 /* worst case lower bound is infinity */
771 *calculatedwclb = SCIPinfinity(scip);
772 *wclbcalculated = TRUE;
773 }
774 }
775 }
776
777 return SCIP_OKAY;
778}
779
780/** Calculate bounds of the dominating variable by rowbound analysis.
781 * We use a special kind of predictive rowbound analysis by first setting the dominated variable to its lower bound.
782 */
783static
784SCIP_RETCODE calcVarBoundsDominating(
785 SCIP* scip, /**< SCIP main data structure */
786 SCIP_MATRIX* matrix, /**< matrix containing the constraints */
787 int row, /**< current row index */
788 int coldominating, /**< column index of dominating variable */
789 SCIP_Real valdominating, /**< row coefficient of dominating variable */
790 int coldominated, /**< column index of dominated variable */
791 SCIP_Real valdominated, /**< row coefficient of dominated variable */
792 SCIP_Bool* ubcalculated, /**< was a upper bound calculated? */
793 SCIP_Real* calculatedub, /**< predicted upper bound */
794 SCIP_Bool* wclbcalculated, /**< was a lower worst case bound calculated? */
795 SCIP_Real* calculatedwclb, /**< predicted worst case lower bound */
796 SCIP_Bool* lbcalculated, /**< was a lower bound calculated? */
797 SCIP_Real* calculatedlb, /**< predicted lower bound */
798 SCIP_Bool* wcubcalculated, /**< was a worst case upper bound calculated? */
799 SCIP_Real* calculatedwcub /**< calculated worst case upper bound */
800 )
801{
802 SCIP_Real minresactivity;
803 SCIP_Real maxresactivity;
804 SCIP_Real lhs;
805 SCIP_Real rhs;
806 SCIP_Bool success;
807
808 assert(scip != NULL);
809 assert(matrix != NULL);
810 assert(0 <= row && row < SCIPmatrixGetNRows(matrix) );
811 assert(0 <= coldominating && coldominating < SCIPmatrixGetNColumns(matrix));
812 assert(0 <= coldominated && coldominated < SCIPmatrixGetNColumns(matrix));
813
814 assert(ubcalculated != NULL);
815 assert(calculatedub != NULL);
816 assert(wclbcalculated != NULL);
817 assert(calculatedwclb != NULL);
818 assert(lbcalculated != NULL);
819 assert(calculatedlb != NULL);
820 assert(wcubcalculated != NULL);
821 assert(calculatedwcub != NULL);
822
823 assert(!SCIPisZero(scip, valdominating));
824 assert(SCIPmatrixGetVar(matrix, coldominating) != NULL);
825
826 *ubcalculated = FALSE;
827 *wclbcalculated = FALSE;
828 *lbcalculated = FALSE;
829 *wcubcalculated = FALSE;
830
831 /* no rowbound analysis for multiaggregated variables, which should not exist, because the matrix only consists of
832 * active variables
833 */
834 assert(SCIPvarGetStatus(SCIPmatrixGetVar(matrix, coldominating)) != SCIP_VARSTATUS_MULTAGGR);
835 assert(SCIPvarGetStatus(SCIPmatrixGetVar(matrix, coldominated)) != SCIP_VARSTATUS_MULTAGGR);
836
837 lhs = SCIPmatrixGetRowLhs(matrix, row);
838 rhs = SCIPmatrixGetRowRhs(matrix, row);
839 assert(!SCIPisInfinity(scip, lhs));
840 assert(!SCIPisInfinity(scip, -rhs));
841
842 /* get minimum/maximum activity of this row without the dominating variable */
843 getActivityResidualsLowerBound(scip, matrix, row, coldominating, valdominating, coldominated, valdominated,
844 &minresactivity, &maxresactivity, &success);
845
846 if( !success )
847 return SCIP_OKAY;
848
849 assert(!SCIPisInfinity(scip, minresactivity));
850 assert(!SCIPisInfinity(scip, -maxresactivity));
851
852 *calculatedub = SCIPinfinity(scip);
853 *calculatedwclb = -SCIPinfinity(scip);
854 *calculatedlb = -SCIPinfinity(scip);
855 *calculatedwcub = SCIPinfinity(scip);
856
857 /* predictive rowbound analysis */
858
859 if( valdominating > 0.0 )
860 {
861 /* lower bound calculation */
862 if( !SCIPisInfinity(scip, maxresactivity) )
863 {
864 *calculatedlb = (lhs - maxresactivity)/valdominating;
865 *lbcalculated = TRUE;
866 }
867
868 /* worst case calculation of lower bound */
869 if( !SCIPisInfinity(scip, -minresactivity) )
870 {
871 *calculatedwclb = (lhs - minresactivity)/valdominating;
872 *wclbcalculated = TRUE;
873 }
874 else
875 {
876 /* worst case lower bound is infinity */
877 *calculatedwclb = SCIPinfinity(scip);
878 *wclbcalculated = TRUE;
879 }
880
881 /* we can only calculate upper bounds, of the right hand side is finite */
882 if( !SCIPmatrixIsRowRhsInfinity(matrix, row) )
883 {
884 /* upper bound calculation */
885 if( !SCIPisInfinity(scip, -minresactivity) )
886 {
887 *calculatedub = (rhs - minresactivity)/valdominating;
888 *ubcalculated = TRUE;
889 }
890
891 /* worst case calculation of upper bound */
892 if( !SCIPisInfinity(scip, maxresactivity) )
893 {
894 *calculatedwcub = (rhs - maxresactivity)/valdominating;
895 *wcubcalculated = TRUE;
896 }
897 else
898 {
899 /* worst case upper bound is -infinity */
900 *calculatedwcub = -SCIPinfinity(scip);
901 *wcubcalculated = TRUE;
902 }
903 }
904 }
905 else
906 {
907 /* upper bound calculation */
908 if( !SCIPisInfinity(scip, maxresactivity) )
909 {
910 *calculatedub = (lhs - maxresactivity)/valdominating;
911 *ubcalculated = TRUE;
912 }
913
914 /* worst case calculation of upper bound */
915 if( !SCIPisInfinity(scip, -minresactivity) )
916 {
917 *calculatedwcub = (lhs - minresactivity)/valdominating;
918 *wcubcalculated = TRUE;
919 }
920 else
921 {
922 /* worst case upper bound is -infinity */
923 *calculatedwcub = -SCIPinfinity(scip);
924 *wcubcalculated = TRUE;
925 }
926
927 /* we can only calculate lower bounds, of the right hand side is finite */
928 if( !SCIPmatrixIsRowRhsInfinity(matrix, row) )
929 {
930 /* lower bound calculation */
931 if( !SCIPisInfinity(scip, -minresactivity) )
932 {
933 *calculatedlb = (rhs - minresactivity)/valdominating;
934 *lbcalculated = TRUE;
935 }
936
937 /* worst case calculation of lower bound */
938 if( !SCIPisInfinity(scip, maxresactivity) )
939 {
940 *calculatedwclb = (rhs - maxresactivity)/valdominating;
941 *wclbcalculated = TRUE;
942 }
943 else
944 {
945 /* worst case lower bound is infinity */
946 *calculatedwclb = SCIPinfinity(scip);
947 *wclbcalculated = TRUE;
948 }
949 }
950 }
951
952 return SCIP_OKAY;
953}
954
955/** try to find new variable bounds and update them when they are better then the old bounds */
956static
957SCIP_RETCODE updateBounds(
958 SCIP* scip, /**< SCIP main data structure */
959 SCIP_MATRIX* matrix, /**< matrix containing the constraints */
960 int row, /**< row index */
961 int col1, /**< dominating variable index */
962 SCIP_Real val1, /**< dominating variable coefficient */
963 int col2, /**< dominated variable index */
964 SCIP_Real val2, /**< dominated variable coefficient */
965 SCIP_Bool predictdominating, /**< flag indicating if bounds of dominating or dominated variable are predicted */
966 SCIP_Real* upperbound, /**< predicted upper bound */
967 SCIP_Real* wclowerbound, /**< predicted worst case lower bound */
968 SCIP_Real* lowerbound, /**< predicted lower bound */
969 SCIP_Real* wcupperbound /**< predicted worst case upper bound */
970 )
971{
972 SCIP_Bool ubcalculated;
973 SCIP_Bool wclbcalculated;
974 SCIP_Bool lbcalculated;
975 SCIP_Bool wcubcalculated;
976 SCIP_Real newub;
977 SCIP_Real newwclb;
978 SCIP_Real newlb;
979 SCIP_Real newwcub;
980
981 assert(scip != NULL);
982 assert(matrix != NULL);
983 assert(upperbound != NULL);
984 assert(wclowerbound != NULL);
985 assert(lowerbound != NULL);
986 assert(wcupperbound != NULL);
987
988 newub = SCIPinfinity(scip);
989 newlb = -SCIPinfinity(scip);
990 newwcub = newub;
991 newwclb = newlb;
992
993 if( predictdominating )
994 {
995 /* do predictive rowbound analysis for the dominating variable */
996 SCIP_CALL( calcVarBoundsDominating(scip, matrix, row, col1, val1, col2, val2,
997 &ubcalculated, &newub, &wclbcalculated, &newwclb,
998 &lbcalculated, &newlb, &wcubcalculated, &newwcub) );
999 }
1000 else
1001 {
1002 /* do predictive rowbound analysis for the dominated variable */
1003 SCIP_CALL( calcVarBoundsDominated(scip, matrix, row, col1, val1, col2, val2,
1004 &ubcalculated, &newub, &wclbcalculated, &newwclb,
1005 &lbcalculated, &newlb, &wcubcalculated, &newwcub) );
1006 }
1007
1008 /* update bounds in case if they are better */
1009 if( ubcalculated )
1010 {
1011 if( newub < *upperbound )
1012 *upperbound = newub;
1013 }
1014 if( wclbcalculated )
1015 {
1016 if( newwclb > *wclowerbound )
1017 *wclowerbound = newwclb;
1018 }
1019 if( lbcalculated )
1020 {
1021 if( newlb > *lowerbound )
1022 *lowerbound = newlb;
1023 }
1024 if( wcubcalculated )
1025 {
1026 if( newwcub < *wcupperbound )
1027 *wcupperbound = newwcub;
1028 }
1029
1030 return SCIP_OKAY;
1031}
1032
1033/** detect parallel columns by using the algorithm of Bixby and Wagner
1034 * see paper: "A note on Detecting Simple Redundancies in Linear Systems", June 1986
1035 */
1036static
1037SCIP_RETCODE detectParallelCols(
1038 SCIP* scip, /**< SCIP main data structure */
1039 SCIP_MATRIX* matrix, /**< matrix containing the constraints */
1040 int* pclass, /**< parallel column classes */
1041 SCIP_Bool* varineq /**< indicating if variable is within an equation */
1042 )
1043{
1044 SCIP_Real* valpnt;
1045 SCIP_Real* values;
1046 SCIP_Real* scale;
1047 int* classsizes;
1048 int* pcset;
1049 int* rowpnt;
1050 int* rowend;
1051 int* colindices;
1052 int* pcs;
1053 SCIP_Real startval;
1054 SCIP_Real aij;
1055 int startpc;
1056 int startk;
1057 int startt;
1058 int pcsetfill;
1059 int colidx;
1060 int k;
1061 int t;
1062 int m;
1063 int i;
1064 int r;
1065 int newpclass;
1066 int pc;
1067 int nrows;
1068 int ncols;
1069
1070 assert(scip != NULL);
1071 assert(matrix != NULL);
1072 assert(pclass != NULL);
1073 assert(varineq != NULL);
1074
1075 nrows = SCIPmatrixGetNRows(matrix);
1076 ncols = SCIPmatrixGetNColumns(matrix);
1077
1078 SCIP_CALL( SCIPallocBufferArray(scip, &classsizes, ncols) );
1079 SCIP_CALL( SCIPallocBufferArray(scip, &scale, ncols) );
1080 SCIP_CALL( SCIPallocBufferArray(scip, &pcset, ncols) );
1081 SCIP_CALL( SCIPallocBufferArray(scip, &values, ncols) );
1082 SCIP_CALL( SCIPallocBufferArray(scip, &colindices, ncols) );
1083 SCIP_CALL( SCIPallocBufferArray(scip, &pcs, ncols) );
1084
1085 BMSclearMemoryArray(scale, ncols);
1086 BMSclearMemoryArray(pclass, ncols);
1087 BMSclearMemoryArray(classsizes, ncols);
1088
1089 classsizes[0] = ncols;
1090 pcsetfill = 0;
1091 for( t = 1; t < ncols; ++t )
1092 pcset[pcsetfill++] = t;
1093
1094 /* loop over all rows */
1095 for( r = 0; r < nrows; ++r )
1096 {
1097 /* we consider only non-empty equations or ranged rows */
1098 if( !SCIPmatrixIsRowRhsInfinity(matrix, r) && SCIPmatrixGetRowNNonzs(matrix, r) > 0 )
1099 {
1100 rowpnt = SCIPmatrixGetRowIdxPtr(matrix, r);
1101 rowend = rowpnt + SCIPmatrixGetRowNNonzs(matrix, r);
1102 valpnt = SCIPmatrixGetRowValPtr(matrix, r);
1103
1104 i = 0;
1105 for( ; (rowpnt < rowend); rowpnt++, valpnt++ )
1106 {
1107 aij = *valpnt;
1108 colidx = *rowpnt;
1109
1110 /* remember variable was part of an equation or ranged row */
1111 varineq[colidx] = TRUE;
1112
1113 if( scale[colidx] == 0.0 )
1114 scale[colidx] = aij;
1115 assert(scale[colidx] != 0.0);
1116
1117 colindices[i] = colidx;
1118 values[i] = aij / scale[colidx];
1119 pc = pclass[colidx];
1120 assert(pc < ncols);
1121
1122 /* update class sizes and pclass set */
1123 assert(classsizes[pc] > 0);
1124 classsizes[pc]--;
1125 if( classsizes[pc] == 0 )
1126 {
1127 assert(pcsetfill < ncols);
1128 pcset[pcsetfill++] = pc;
1129 }
1130 pcs[i] = pc;
1131
1132 i++;
1133 }
1134
1135 assert(i > 0);
1136
1137 /* sort on the pclass values */
1138 if( i > 1 )
1139 {
1140 SCIPsortIntIntReal(pcs, colindices, values, i);
1141 }
1142
1143 k = 0;
1144 while( TRUE ) /*lint !e716*/
1145 {
1146 assert(k < i);
1147 startpc = pcs[k];
1148 startk = k;
1149
1150 /* find pclass-sets */
1151 while( k < i && pcs[k] == startpc )
1152 k++;
1153
1154 /* sort on the A values which have equal pclass values */
1155 if( k - startk > 1 )
1156 SCIPsortRealInt(&(values[startk]), &(colindices[startk]), k - startk);
1157
1158 t = 0;
1159 while( TRUE ) /*lint !e716*/
1160 {
1161 assert(startk + t < i);
1162 startval = values[startk + t];
1163 startt = t;
1164
1165 /* find A-sets */
1166 while( t < k - startk && SCIPisEQ(scip, startval, values[startk + t]) )
1167 t++;
1168
1169 /* get new pclass */
1170 newpclass = pcset[0];
1171 assert(pcsetfill > 0);
1172 pcset[0] = pcset[--pcsetfill];
1173
1174 /* renumbering */
1175 for( m = startk + startt; m < startk + t; m++ )
1176 {
1177 assert(m < i);
1178 assert(colindices[m] < ncols);
1179 assert(newpclass < ncols);
1180
1181 pclass[colindices[m]] = newpclass;
1182 classsizes[newpclass]++;
1183 }
1184
1185 if( t == k - startk )
1186 break;
1187 }
1188
1189 if( k == SCIPmatrixGetRowNNonzs(matrix, r) )
1190 break;
1191 }
1192 }
1193 }
1194
1195 SCIPfreeBufferArray(scip, &pcs);
1196 SCIPfreeBufferArray(scip, &colindices);
1197 SCIPfreeBufferArray(scip, &values);
1198 SCIPfreeBufferArray(scip, &pcset);
1199 SCIPfreeBufferArray(scip, &scale);
1200 SCIPfreeBufferArray(scip, &classsizes);
1201
1202 return SCIP_OKAY;
1203}
1204
1205
1206/** try to improve variable bounds by predictive bound strengthening */
1207static
1208SCIP_RETCODE predBndStr(
1209 SCIP* scip, /**< SCIP main data structure */
1210 SCIP_VAR* dominatingvar, /**< dominating variable */
1211 int dominatingidx, /**< column index of the dominating variable */
1212 SCIP_Real dominatingub, /**< predicted upper bound of the dominating variable */
1213 SCIP_Real dominatinglb, /**< predicted lower bound of the dominating variable */
1214 SCIP_Real dominatingwcub, /**< predicted worst case upper bound of the dominating variable */
1215 SCIP_VAR* dominatedvar, /**< dominated variable */
1216 int dominatedidx, /**< column index of the dominated variable */
1217 SCIP_Real dominatedub, /**< predicted upper bound of the dominated variable */
1218 SCIP_Real dominatedwclb, /**< predicted worst case lower bound of the dominated variable */
1219 SCIP_Real dominatedlb, /**< predicted lower bound of the dominated variable */
1220 FIXINGDIRECTION* varstofix, /**< array holding fixing information */
1221 int* nchgbds /**< count number of bound changes */
1222 )
1223{
1224 /* we compare only variables from the same type */
1225 if( !(SCIPvarGetType(dominatingvar) == SCIPvarGetType(dominatedvar) ||
1226 SCIPvarIsBinary(dominatingvar) == SCIPvarIsBinary(dominatedvar) ||
1227 (SCIPvarGetType(dominatingvar) == SCIP_VARTYPE_INTEGER && SCIPvarGetType(dominatedvar) == SCIP_VARTYPE_IMPLINT) ||
1228 (SCIPvarGetType(dominatedvar) == SCIP_VARTYPE_INTEGER && SCIPvarGetType(dominatingvar) == SCIP_VARTYPE_IMPLINT)) )
1229 {
1230 return SCIP_OKAY;
1231 }
1232
1233 if( varstofix[dominatingidx] == NOFIX )
1234 {
1235 /* assume x dominates y (x->y). we get this bound from a positive coefficient
1236 * of the dominating variable. because x->y the dominated variable y has
1237 * a positive coefficient too. thus y contributes to the minactivity with its
1238 * lower bound. but this case is considered within predictive bound analysis.
1239 * thus the dominating upper bound is a common upper bound.
1240 */
1241 if( !SCIPisInfinity(scip, dominatingub) )
1242 {
1243 SCIP_Real newub;
1244 SCIP_Real oldub;
1245 SCIP_Real lb;
1246
1247 newub = dominatingub;
1248 oldub = SCIPvarGetUbGlobal(dominatingvar);
1249 lb = SCIPvarGetLbGlobal(dominatingvar);
1250
1251 /* if( SCIPvarGetType(dominatingvar) != SCIP_VARTYPE_CONTINUOUS )
1252 newub = SCIPceil(scip, newub); */
1253
1254 if( SCIPisLE(scip, lb, newub) && SCIPisLT(scip, newub, oldub) )
1255 {
1256 SCIPdebugMsg(scip, "[ub]\tupper bound for dominating variable <%s> changed: [%.17f,%.17f] -> [%.17f,%.17f]\n",
1257 SCIPvarGetName(dominatingvar), lb, oldub, lb, newub);
1258 SCIP_CALL( SCIPchgVarUb(scip, dominatingvar, newub) );
1259 (*nchgbds)++;
1260 }
1261 }
1262
1263 /* assume x dominates y (x->y). we get this lower bound of the dominating variable
1264 * from a negative coefficient within a <= relation. if y has a positive coefficient
1265 * we get a common lower bound of x from predictive bound analysis. if y has a
1266 * negative coefficient we get an improved lower bound of x because the minactivity
1267 * is greater. for discrete variables we have to round down the lower bound.
1268 */
1269 if( !SCIPisInfinity(scip, -dominatinglb) )
1270 {
1271 SCIP_Real newlb;
1272 SCIP_Real oldlb;
1273 SCIP_Real ub;
1274
1275 newlb = dominatinglb;
1276 oldlb = SCIPvarGetLbGlobal(dominatingvar);
1277 ub = SCIPvarGetUbGlobal(dominatingvar);
1278
1279 if( SCIPvarGetType(dominatingvar) != SCIP_VARTYPE_CONTINUOUS )
1280 newlb = SCIPfloor(scip, newlb);
1281
1282 if( SCIPisLT(scip, oldlb, newlb) && SCIPisLE(scip, newlb, ub) )
1283 {
1284 SCIPdebugMsg(scip, "[lb]\tlower bound of dominating variable <%s> changed: [%.17f,%.17f] -> [%.17f,%.17f]\n",
1285 SCIPvarGetName(dominatingvar), oldlb, ub, newlb, ub);
1286 SCIP_CALL( SCIPchgVarLb(scip, dominatingvar, newlb) );
1287 (*nchgbds)++;
1288 }
1289 }
1290
1291 /* assume x dominates y (x->y). we get this bound from a positive coefficient
1292 * of x within a <= relation. from x->y it follows, that y has a positive
1293 * coefficient in this row too. the worst case upper bound of x is an estimation
1294 * of how great x can be in every case. if the objective coefficient of x is
1295 * negative we get thus a lower bound of x. for discrete variables we have
1296 * to round down the lower bound before.
1297 */
1298 if( !SCIPisInfinity(scip, dominatingwcub) && SCIPisNegative(scip, SCIPvarGetObj(dominatingvar)))
1299 {
1300 SCIP_Real newlb;
1301 SCIP_Real oldlb;
1302 SCIP_Real ub;
1303
1304 newlb = dominatingwcub;
1305 oldlb = SCIPvarGetLbGlobal(dominatingvar);
1306 ub = SCIPvarGetUbGlobal(dominatingvar);
1307
1308 if( SCIPvarGetType(dominatingvar) != SCIP_VARTYPE_CONTINUOUS )
1309 newlb = SCIPfloor(scip, newlb);
1310
1311 if( SCIPisLT(scip, oldlb, newlb) && SCIPisLE(scip, newlb, ub) )
1312 {
1313 SCIPdebugMsg(scip, "[wcub]\tlower bound of dominating variable <%s> changed: [%.17f,%.17f] -> [%.17f,%.17f]\n",
1314 SCIPvarGetName(dominatingvar), oldlb, ub, newlb, ub);
1315 SCIP_CALL( SCIPchgVarLb(scip, dominatingvar, newlb) );
1316 (*nchgbds)++;
1317 }
1318 }
1319 }
1320
1321 if( varstofix[dominatedidx] == NOFIX )
1322 {
1323 /* assume x dominates y (x->y). we get this bound for a positive coefficient of y
1324 * within a <= relation. if x has a negative coefficient we get a common upper
1325 * bound of y. if x has a positive coefficient we get an improved upper bound
1326 * of y because the minactivity is greater.
1327 */
1328 if( !SCIPisInfinity(scip, dominatedub) )
1329 {
1330 SCIP_Real newub;
1331 SCIP_Real oldub;
1332 SCIP_Real lb;
1333
1334 newub = dominatedub;
1335 oldub = SCIPvarGetUbGlobal(dominatedvar);
1336 lb = SCIPvarGetLbGlobal(dominatedvar);
1337
1338 if( SCIPisLE(scip, lb, newub) && SCIPisLT(scip, newub, oldub) )
1339 {
1340 SCIPdebugMsg(scip, "[ub]\tupper bound of dominated variable <%s> changed: [%.17f,%.17f] -> [%.17f,%.17f]\n",
1341 SCIPvarGetName(dominatedvar), lb, oldub, lb, newub);
1342 SCIP_CALL( SCIPchgVarUb(scip, dominatedvar, newub) );
1343 (*nchgbds)++;
1344 }
1345 }
1346
1347 /* assume x dominates y (x->y). we get this bound only from a negative
1348 * coefficient of y within a <= relation. because of x->y then x has a negative
1349 * coefficient too. the worst case lower bound is an estimation what property
1350 * the dominated variable must have if the dominating variable is at its upper bound.
1351 * to get an upper bound of the dominated variable we need to consider a positive
1352 * objective coefficient. for discrete variables we have to round up the upper bound.
1353 */
1354 if( !SCIPisInfinity(scip, -dominatedwclb) && SCIPisPositive(scip, SCIPvarGetObj(dominatedvar)) )
1355 {
1356 SCIP_Real newub;
1357 SCIP_Real oldub;
1358 SCIP_Real lb;
1359
1360 newub = dominatedwclb;
1361 oldub = SCIPvarGetUbGlobal(dominatedvar);
1362 lb = SCIPvarGetLbGlobal(dominatedvar);
1363
1364 if( SCIPvarGetType(dominatedvar) != SCIP_VARTYPE_CONTINUOUS )
1365 newub = SCIPceil(scip, newub);
1366
1367 if( SCIPisLE(scip, lb, newub) && SCIPisLT(scip, newub, oldub) )
1368 {
1369 SCIPdebugMsg(scip, "[wclb]\tupper bound of dominated variable <%s> changed: [%.17f,%.17f] -> [%.17f,%.17f]\n",
1370 SCIPvarGetName(dominatedvar), lb, oldub, lb, newub);
1371 SCIP_CALL( SCIPchgVarUb(scip, dominatedvar, newub) );
1372 (*nchgbds)++;
1373 }
1374 }
1375
1376 /* assume x dominates y (x->y). we get a lower bound of y from a negative
1377 * coefficient within a <= relation. but if x->y then x has a negative
1378 * coefficient too and contributes with its upper bound to the minactivity.
1379 * thus in all we have a common lower bound calculation and no rounding is necessary.
1380 */
1381 if( !SCIPisInfinity(scip, -dominatedlb) )
1382 {
1383 SCIP_Real newlb;
1384 SCIP_Real oldlb;
1385 SCIP_Real ub;
1386
1387 newlb = dominatedlb;
1388 oldlb = SCIPvarGetLbGlobal(dominatedvar);
1389 ub = SCIPvarGetUbGlobal(dominatedvar);
1390
1391 if( SCIPisLT(scip, oldlb, newlb) && SCIPisLE(scip, newlb, ub) )
1392 {
1393 SCIPdebugMsg(scip, "[lb]\tlower bound of dominated variable <%s> changed: [%.17f,%.17f] -> [%.17f,%.17f]\n",
1394 SCIPvarGetName(dominatedvar), oldlb, ub, newlb, ub);
1395 SCIP_CALL( SCIPchgVarLb(scip, dominatedvar, newlb) );
1396 (*nchgbds)++;
1397 }
1398 }
1399 }
1400
1401 return SCIP_OKAY;
1402}
1403
1404/** try to find variable fixings */
1405static
1406SCIP_RETCODE findFixings(
1407 SCIP* scip, /**< SCIP main data structure */
1408 SCIP_MATRIX* matrix, /**< constraint matrix structure */
1409 SCIP_VAR* dominatingvar, /**< dominating variable */
1410 int dominatingidx, /**< column index of the dominating variable */
1411 SCIP_Real dominatingub, /**< predicted upper bound of the dominating variable */
1412 SCIP_Real dominatingwclb, /**< predicted worst case lower bound of the dominating variable */
1413 SCIP_Real dominatinglb, /**< predicted lower bound of the dominating variable */
1414 SCIP_Real dominatingwcub, /**< predicted worst case upper bound of the dominating variable */
1415 SCIP_VAR* dominatedvar, /**< dominated variable */
1416 int dominatedidx, /**< column index of the dominated variable */
1417 FIXINGDIRECTION* varstofix, /**< array holding fixing information */
1418 SCIP_Bool onlybinvars, /**< flag indicating only binary variables are present */
1419 SCIP_Bool onlyoneone, /**< when onlybinvars is TRUE, flag indicates if both binary variables are in clique */
1420 int* nfixings /**< counter for possible fixings */
1421 )
1422{
1423 /* we compare only variables from the same type */
1424 if( !(SCIPvarGetType(dominatingvar) == SCIPvarGetType(dominatedvar) ||
1425 SCIPvarIsBinary(dominatingvar) == SCIPvarIsBinary(dominatedvar) ||
1426 (SCIPvarGetType(dominatingvar) == SCIP_VARTYPE_INTEGER && SCIPvarGetType(dominatedvar) == SCIP_VARTYPE_IMPLINT) ||
1427 (SCIPvarGetType(dominatedvar) == SCIP_VARTYPE_INTEGER && SCIPvarGetType(dominatingvar) == SCIP_VARTYPE_IMPLINT)) )
1428 {
1429 return SCIP_OKAY;
1430 }
1431
1432 if( varstofix[dominatedidx] == NOFIX && SCIPmatrixGetColNNonzs(matrix, dominatingidx) == 1
1433 && SCIPmatrixGetColNNonzs(matrix, dominatedidx) == 1 )
1434 {
1435 /* We have a x->y dominance relation and only one equality constraint
1436 * where the dominating variable x with an infinity upper bound and the
1437 * dominated variable y are present. Then the dominated variable y
1438 * can be fixed at its lower bound.
1439 */
1440 int row;
1441 row = *(SCIPmatrixGetColIdxPtr(matrix, dominatedidx));
1442
1443 if( SCIPisEQ(scip, SCIPmatrixGetRowLhs(matrix, row), SCIPmatrixGetRowRhs(matrix, row)) &&
1444 SCIPisInfinity(scip, SCIPvarGetUbGlobal(dominatingvar)) )
1445 {
1446 varstofix[dominatedidx] = FIXATLB;
1447 (*nfixings)++;
1448
1449 return SCIP_OKAY;
1450 }
1451 }
1452
1453 if( varstofix[dominatedidx] == NOFIX && !SCIPisNegative(scip, SCIPvarGetObj(dominatedvar)) )
1454 {
1455 if( !SCIPisInfinity(scip, -dominatingwclb) &&
1456 SCIPisLE(scip, dominatingwclb, SCIPvarGetUbGlobal(dominatingvar)) )
1457 {
1458 /* we have a x->y dominance relation with a positive obj coefficient
1459 * of the dominated variable y. we need to secure feasibility
1460 * by testing if the predicted lower worst case bound is less equal the
1461 * current upper bound. it is possible, that the lower worst case bound
1462 * is infinity and the upper bound of the dominating variable x is
1463 * infinity too.
1464 */
1465 varstofix[dominatedidx] = FIXATLB;
1466 (*nfixings)++;
1467 }
1468 }
1469
1470 if( varstofix[dominatedidx] == NOFIX && !SCIPisInfinity(scip, dominatingub) &&
1471 SCIPisLE(scip, dominatingub, SCIPvarGetUbGlobal(dominatingvar)) )
1472 {
1473 /* we have a x->y dominance relation with an arbitrary obj coefficient
1474 * of the dominating variable x. in all cases we have to look
1475 * if the predicted upper bound of the dominating variable is great enough.
1476 * by testing, that the predicted upper bound is not infinity we avoid problems
1477 * with x->y e.g.
1478 * min -x -y
1479 * s.t. -x -y <= -1
1480 * 0<=x<=1, 0<=y<=1
1481 * where y is not at their lower bound.
1482 */
1483 varstofix[dominatedidx] = FIXATLB;
1484 (*nfixings)++;
1485 }
1486
1487 if( varstofix[dominatingidx] == NOFIX && !SCIPisPositive(scip, SCIPvarGetObj(dominatingvar)) )
1488 {
1489 /* we have a x->y dominance relation with a negative obj coefficient
1490 * of the dominating variable x. if the worst case upper bound is
1491 * greater equal than upper bound, we fix x at the upper bound
1492 */
1493 if( !SCIPisInfinity(scip, dominatingwcub) &&
1494 SCIPisGE(scip, dominatingwcub, SCIPvarGetUbGlobal(dominatingvar)) )
1495 {
1496 varstofix[dominatingidx] = FIXATUB;
1497 (*nfixings)++;
1498 }
1499 }
1500
1501 if( varstofix[dominatingidx] == NOFIX && !SCIPisInfinity(scip, -dominatinglb) &&
1502 SCIPisGE(scip, dominatinglb, SCIPvarGetUbGlobal(dominatingvar)) )
1503 {
1504 /* we have a x->y dominance relation with an arbitrary obj coefficient
1505 * of the dominating variable x. if the predicted lower bound is greater
1506 * equal than upper bound, we fix x at the upper bound.
1507 */
1508 varstofix[dominatingidx] = FIXATUB;
1509 (*nfixings)++;
1510 }
1511
1512 if( onlybinvars )
1513 {
1514 if( varstofix[dominatedidx] == NOFIX && (onlyoneone || SCIPvarsHaveCommonClique(dominatingvar, TRUE, dominatedvar, TRUE, TRUE)) )
1515 {
1516 /* We have a (1->1)-clique with dominance relation (x->y) (x dominates y).
1517 * From this dominance relation, we know (1->0) is possible and not worse than (0->1)
1518 * concerning the objective function. It follows that only (1->0) or (0->0) are possible,
1519 * but in both cases y has the value 0 => y=0.
1520 */
1521 varstofix[dominatedidx] = FIXATLB;
1522 (*nfixings)++;
1523 }
1524
1525 if( varstofix[dominatingidx] == NOFIX && SCIPvarsHaveCommonClique(dominatingvar, FALSE, dominatedvar, FALSE, TRUE) )
1526 {
1527 /* We have a (0->0)-clique with dominance relation x->y (x dominates y).
1528 * From this dominance relation, we know (1->0) is possible and not worse than (0->1)
1529 * concerning the objective function. It follows that only (1->0) or (1->1) are possible,
1530 * but in both cases x has the value 1 => x=1
1531 */
1532 varstofix[dominatingidx] = FIXATUB;
1533 (*nfixings)++;
1534 }
1535 }
1536 else
1537 assert(!onlyoneone);
1538
1539 return SCIP_OKAY;
1540}
1541
1542/** find dominance relation between variable pairs */
1543static
1544SCIP_RETCODE findDominancePairs(
1545 SCIP* scip, /**< SCIP main data structure */
1546 SCIP_MATRIX* matrix, /**< matrix containing the constraints */
1547 SCIP_PRESOLDATA* presoldata, /**< presolver data */
1548 int* searchcols, /**< indexes of variables for pair comparisons */
1549 int searchsize, /**< number of variables for pair comparisons */
1550 SCIP_Bool onlybinvars, /**< flag indicating searchcols contains only binary variable indexes */
1551 FIXINGDIRECTION* varstofix, /**< array holding information for later upper/lower bound fixing */
1552 int* nfixings, /**< found number of possible fixings */
1553 SCIP_Longint* ndomrelations, /**< found number of dominance relations */
1554 int* nchgbds /**< number of changed bounds */
1555 )
1556{
1557 SCIP_Real* vals1;
1558 SCIP_Real* vals2;
1559 SCIP_Real tmpupperbounddominatingcol1;
1560 SCIP_Real tmpupperbounddominatingcol2;
1561 SCIP_Real tmpwclowerbounddominatingcol1;
1562 SCIP_Real tmpwclowerbounddominatingcol2;
1563 SCIP_Real tmplowerbounddominatingcol1;
1564 SCIP_Real tmplowerbounddominatingcol2;
1565 SCIP_Real tmpwcupperbounddominatingcol1;
1566 SCIP_Real tmpwcupperbounddominatingcol2;
1567 int* rows1;
1568 int* rows2;
1569 int nrows1;
1570 int nrows2;
1571 SCIP_Real tmpupperbounddominatedcol1;
1572 SCIP_Real tmpupperbounddominatedcol2;
1573 SCIP_Real tmpwclowerbounddominatedcol1;
1574 SCIP_Real tmpwclowerbounddominatedcol2;
1575 SCIP_Real tmplowerbounddominatedcol1;
1576 SCIP_Real tmplowerbounddominatedcol2;
1577 SCIP_Real tmpwcupperbounddominatedcol1;
1578 SCIP_Real tmpwcupperbounddominatedcol2;
1579 SCIP_Real obj1;
1580 SCIP_Bool col1domcol2;
1581 SCIP_Bool col2domcol1;
1582 SCIP_Bool onlyoneone;
1583 int cnt1;
1584 int cnt2;
1585 int col1;
1586 int col2;
1587 int r1;
1588 int r2;
1589 int paircnt;
1590 int oldnfixings;
1591
1592 assert(scip != NULL);
1593 assert(matrix != NULL);
1594 assert(presoldata != NULL);
1595 assert(searchcols != NULL);
1596 assert(varstofix != NULL);
1597 assert(nfixings != NULL);
1598 assert(ndomrelations != NULL);
1599 assert(nchgbds != NULL);
1600
1601 paircnt = 0;
1602 oldnfixings = *nfixings;
1603
1604 /* pair comparisons */
1605 for( cnt1 = 0; cnt1 < searchsize; cnt1++ )
1606 {
1607 SCIP_VAR* varcol1;
1608 SCIP_VAR* varcol2;
1609
1610 /* get index of the first variable */
1611 col1 = searchcols[cnt1];
1612
1613 if( varstofix[col1] == FIXATLB )
1614 continue;
1615
1616 varcol1 = SCIPmatrixGetVar(matrix, col1);
1617 obj1 = SCIPvarGetObj(varcol1);
1618
1619 for( cnt2 = cnt1+1; cnt2 < searchsize; cnt2++ )
1620 {
1621 /* get index of the second variable */
1622 col2 = searchcols[cnt2];
1623 varcol2 = SCIPmatrixGetVar(matrix, col2);
1624 onlyoneone = FALSE;
1625
1626 /* we always have minimize as obj sense */
1627
1628 /* column 1 dominating column 2 */
1629 col1domcol2 = (obj1 <= SCIPvarGetObj(varcol2));
1630
1631 /* column 2 dominating column 1 */
1632 col2domcol1 = (SCIPvarGetObj(varcol2) <= obj1);
1633
1634 /* search only if nothing was found yet */
1635 col1domcol2 = col1domcol2 && (varstofix[col2] == NOFIX);
1636 col2domcol1 = col2domcol1 && (varstofix[col1] == NOFIX);
1637
1638 /* we only search for a dominance relation if the lower bounds are not negative */
1639 if( !onlybinvars )
1640 {
1641 if( SCIPisLT(scip, SCIPvarGetLbGlobal(varcol1), 0.0) ||
1642 SCIPisLT(scip, SCIPvarGetLbGlobal(varcol2), 0.0) )
1643 {
1644 col1domcol2 = FALSE;
1645 col2domcol1 = FALSE;
1646 }
1647 }
1648
1649 /* pair comparison control */
1650 if( paircnt == presoldata->numcurrentpairs )
1651 {
1652 assert(*nfixings >= oldnfixings);
1653 if( *nfixings == oldnfixings )
1654 {
1655 /* not enough fixings found, decrement number of comparisons */
1656 presoldata->numcurrentpairs >>= 1; /*lint !e702*/
1657 if( presoldata->numcurrentpairs < presoldata->numminpairs )
1658 presoldata->numcurrentpairs = presoldata->numminpairs;
1659
1660 /* stop searching in this row */
1661 return SCIP_OKAY;
1662 }
1663 oldnfixings = *nfixings;
1664 paircnt = 0;
1665
1666 /* increment number of comparisons */
1667 presoldata->numcurrentpairs <<= 1; /*lint !e701*/
1668 if( presoldata->numcurrentpairs > presoldata->nummaxpairs )
1669 presoldata->numcurrentpairs = presoldata->nummaxpairs;
1670 }
1671 paircnt++;
1672
1673 if( !col1domcol2 && !col2domcol1 )
1674 continue;
1675
1676 /* get the data for both columns */
1677 vals1 = SCIPmatrixGetColValPtr(matrix, col1);
1678 rows1 = SCIPmatrixGetColIdxPtr(matrix, col1);
1679 nrows1 = SCIPmatrixGetColNNonzs(matrix, col1);
1680 r1 = 0;
1681 vals2 = SCIPmatrixGetColValPtr(matrix, col2);
1682 rows2 = SCIPmatrixGetColIdxPtr(matrix, col2);
1683 nrows2 = SCIPmatrixGetColNNonzs(matrix, col2);
1684 r2 = 0;
1685
1686 /* do we have a obj constant? */
1687 if( nrows1 == 0 || nrows2 == 0 )
1688 continue;
1689
1690 /* initialize temporary bounds of dominating variable */
1691 tmpupperbounddominatingcol1 = SCIPinfinity(scip);
1692 tmpupperbounddominatingcol2 = tmpupperbounddominatingcol1;
1693 tmpwclowerbounddominatingcol1 = -SCIPinfinity(scip);
1694 tmpwclowerbounddominatingcol2 = tmpwclowerbounddominatingcol1;
1695 tmplowerbounddominatingcol1 = -SCIPinfinity(scip);
1696 tmplowerbounddominatingcol2 = tmplowerbounddominatingcol1;
1697 tmpwcupperbounddominatingcol1 = SCIPinfinity(scip);
1698 tmpwcupperbounddominatingcol2 = tmpwcupperbounddominatingcol1;
1699
1700 /* initialize temporary bounds of dominated variable */
1701 tmpupperbounddominatedcol1 = SCIPinfinity(scip);
1702 tmpupperbounddominatedcol2 = tmpupperbounddominatedcol1;
1703 tmpwclowerbounddominatedcol1 = -SCIPinfinity(scip);
1704 tmpwclowerbounddominatedcol2 = tmpwclowerbounddominatedcol1;
1705 tmplowerbounddominatedcol1 = -SCIPinfinity(scip);
1706 tmplowerbounddominatedcol2 = tmplowerbounddominatedcol1;
1707 tmpwcupperbounddominatedcol1 = SCIPinfinity(scip);
1708 tmpwcupperbounddominatedcol2 = tmpwcupperbounddominatedcol1;
1709
1710 /* compare rows of this column pair */
1711 while( (col1domcol2 || col2domcol1) && (r1 < nrows1 || r2 < nrows2) )
1712 {
1713 assert((r1 >= nrows1-1) || (rows1[r1] < rows1[r1+1]));
1714 assert((r2 >= nrows2-1) || (rows2[r2] < rows2[r2+1]));
1715
1716 /* there is a nonredundant row containing column 1 but not column 2 */
1717 if( r1 < nrows1 && (r2 == nrows2 || rows1[r1] < rows2[r2]) )
1718 {
1719 /* dominance depends on the type of relation */
1720 if( !SCIPmatrixIsRowRhsInfinity(matrix, rows1[r1]) )
1721 {
1722 /* no dominance relation for equations or ranged rows */
1723 col2domcol1 = FALSE;
1724 col1domcol2 = FALSE;
1725 }
1726 else
1727 {
1728 /* >= relation, larger coefficients dominate smaller ones */
1729 if( vals1[r1] > 0.0 )
1730 col2domcol1 = FALSE;
1731 else
1732 col1domcol2 = FALSE;
1733 }
1734
1735 r1++;
1736 }
1737 /* there is a nonredundant row containing column 2, but not column 1 */
1738 else if( r2 < nrows2 && (r1 == nrows1 || rows1[r1] > rows2[r2]) )
1739 {
1740 /* dominance depends on the type of relation */
1741 if( !SCIPmatrixIsRowRhsInfinity(matrix, rows2[r2]) )
1742 {
1743 /* no dominance relation for equations or ranged rows */
1744 col2domcol1 = FALSE;
1745 col1domcol2 = FALSE;
1746 }
1747 else
1748 {
1749 /* >= relation, larger coefficients dominate smaller ones */
1750 if( vals2[r2] < 0.0 )
1751 col2domcol1 = FALSE;
1752 else
1753 col1domcol2 = FALSE;
1754 }
1755
1756 r2++;
1757 }
1758 /* if both columns appear in a common row, compare the coefficients */
1759 else
1760 {
1761 assert(r1 < nrows1 && r2 < nrows2);
1762 assert(rows1[r1] == rows2[r2]);
1763
1764 /* if both columns are binary variables we check if they have a common clique
1765 * and do not calculate any bounds
1766 */
1767 if( onlybinvars && !onlyoneone )
1768 {
1769 if( vals1[r1] < 0 && vals2[r2] < 0 )
1770 {
1771 if( (SCIPmatrixGetRowNMaxActPosInf(matrix, rows1[r1]) + SCIPmatrixGetRowNMaxActNegInf(matrix, rows1[r1]) == 0)
1772 && SCIPisFeasLE(scip, SCIPmatrixGetRowMaxActivity(matrix, rows1[r1]) + MAX(vals1[r1], vals2[r2]),
1773 SCIPmatrixGetRowLhs(matrix, rows1[r1])) )
1774 {
1775 onlyoneone = TRUE;
1776 }
1777 }
1778
1779 if( !onlyoneone && !SCIPmatrixIsRowRhsInfinity(matrix, rows1[r1]) )
1780 {
1781 if ( vals1[r1] > 0 && vals2[r2] > 0 )
1782 {
1783 if( (SCIPmatrixGetRowNMinActPosInf(matrix, rows1[r1]) + SCIPmatrixGetRowNMinActNegInf(matrix, rows1[r1]) == 0)
1784 && SCIPisFeasGE(scip, SCIPmatrixGetRowMinActivity(matrix, rows1[r1]) + MIN(vals1[r1], vals2[r2]),
1785 SCIPmatrixGetRowRhs(matrix, rows1[r1])) )
1786 {
1787 onlyoneone = TRUE;
1788 }
1789 }
1790 }
1791
1792 if( onlyoneone )
1793 {
1794 /* reset bounds */
1795 tmpupperbounddominatingcol1 = SCIPinfinity(scip);
1796 tmpupperbounddominatingcol2 = tmpupperbounddominatingcol1;
1797 tmpwclowerbounddominatingcol1 = -SCIPinfinity(scip);
1798 tmpwclowerbounddominatingcol2 = tmpwclowerbounddominatingcol1;
1799 tmplowerbounddominatingcol1 = -SCIPinfinity(scip);
1800 tmplowerbounddominatingcol2 = tmplowerbounddominatingcol1;
1801 tmpwcupperbounddominatingcol1 = SCIPinfinity(scip);
1802 tmpwcupperbounddominatingcol2 = tmpwcupperbounddominatingcol1;
1803
1804 tmpupperbounddominatedcol1 = SCIPinfinity(scip);
1805 tmpupperbounddominatedcol2 = tmpupperbounddominatedcol1;
1806 tmpwclowerbounddominatedcol1 = -SCIPinfinity(scip);
1807 tmpwclowerbounddominatedcol2 = tmpwclowerbounddominatedcol1;
1808 tmplowerbounddominatedcol1 = -SCIPinfinity(scip);
1809 tmplowerbounddominatedcol2 = tmplowerbounddominatedcol1;
1810 tmpwcupperbounddominatedcol1 = SCIPinfinity(scip);
1811 tmpwcupperbounddominatedcol2 = tmpwcupperbounddominatedcol1;
1812 }
1813 }
1814
1815 /* dominance depends on the type of inequality */
1816 if( !SCIPmatrixIsRowRhsInfinity(matrix, rows1[r1]) )
1817 {
1818 /* no dominance relation if coefficients differ for equations or ranged rows */
1819 if( !SCIPisEQ(scip, vals1[r1], vals2[r2]) )
1820 {
1821 col2domcol1 = FALSE;
1822 col1domcol2 = FALSE;
1823 }
1824 }
1825 else
1826 {
1827 /* >= relation, larger coefficients dominate smaller ones */
1828 if( vals1[r1] > vals2[r2] )
1829 col2domcol1 = FALSE;
1830 else if( vals1[r1] < vals2[r2] )
1831 col1domcol2 = FALSE;
1832 }
1833
1834 /* we do not use bound calulations if two binary variable are in one common clique.
1835 * for the other cases we claim the same sign for the coefficients to
1836 * achieve monotonically decreasing predictive bound functions.
1837 */
1838 if( !onlyoneone &&
1839 ((vals1[r1] < 0 && vals2[r2] < 0) || (vals1[r1] > 0 && vals2[r2] > 0)) )
1840 {
1841 if( col1domcol2 )
1842 {
1843 /* update bounds of dominating variable for column 1 */
1844 SCIP_CALL( updateBounds(scip, matrix, rows1[r1],
1845 col1, vals1[r1], col2, vals2[r2], TRUE,
1846 &tmpupperbounddominatingcol1, &tmpwclowerbounddominatingcol1,
1847 &tmplowerbounddominatingcol1, &tmpwcupperbounddominatingcol1) );
1848
1849 /* update bounds of dominated variable for column 1 */
1850 SCIP_CALL( updateBounds(scip, matrix, rows1[r1],
1851 col1, vals1[r1], col2, vals2[r2], FALSE,
1852 &tmpupperbounddominatedcol1, &tmpwclowerbounddominatedcol1,
1853 &tmplowerbounddominatedcol1, &tmpwcupperbounddominatedcol1) );
1854 }
1855
1856 if( col2domcol1 )
1857 {
1858 /* update bounds of dominating variable for column 2 */
1859 SCIP_CALL( updateBounds(scip, matrix, rows2[r2],
1860 col2, vals2[r2], col1, vals1[r1], TRUE,
1861 &tmpupperbounddominatingcol2, &tmpwclowerbounddominatingcol2,
1862 &tmplowerbounddominatingcol2, &tmpwcupperbounddominatingcol2) );
1863
1864 /* update bounds of dominated variable for column 2 */
1865 SCIP_CALL( updateBounds(scip, matrix, rows2[r2],
1866 col2, vals2[r2], col1, vals1[r1], FALSE,
1867 &tmpupperbounddominatedcol2, &tmpwclowerbounddominatedcol2,
1868 &tmplowerbounddominatedcol2, &tmpwcupperbounddominatedcol2) );
1869 }
1870 }
1871
1872 r1++;
1873 r2++;
1874 }
1875 }
1876
1877 /* a column is only dominated, if there are no more rows in which it is contained */
1878 col1domcol2 = col1domcol2 && r2 == nrows2;
1879 col2domcol1 = col2domcol1 && r1 == nrows1;
1880
1881 if( !col1domcol2 && !col2domcol1 )
1882 continue;
1883
1884 /* no dominance relation for left equations or ranged rows */
1885 while( r1 < nrows1 )
1886 {
1887 if( !SCIPmatrixIsRowRhsInfinity(matrix, rows1[r1]) )
1888 {
1889 col2domcol1 = FALSE;
1890 col1domcol2 = FALSE;
1891 break;
1892 }
1893 r1++;
1894 }
1895 if( !col1domcol2 && !col2domcol1 )
1896 continue;
1897 while( r2 < nrows2 )
1898 {
1899 if( !SCIPmatrixIsRowRhsInfinity(matrix, rows2[r2]) )
1900 {
1901 col2domcol1 = FALSE;
1902 col1domcol2 = FALSE;
1903 break;
1904 }
1905 r2++;
1906 }
1907
1908 if( col1domcol2 || col2domcol1 )
1909 (*ndomrelations)++;
1910
1911 if( col1domcol2 && col2domcol1 )
1912 {
1913 /* prefer the variable as dominating variable with the greater upper bound */
1914 if( SCIPisGE(scip, SCIPvarGetUbGlobal(varcol1), SCIPvarGetUbGlobal(varcol2)) )
1915 col2domcol1 = FALSE;
1916 else
1917 col1domcol2 = FALSE;
1918 }
1919
1920 /* use dominance relation and clique/bound-information
1921 * to find variable fixings. additionally try to strengthen
1922 * variable bounds by predictive bound strengthening.
1923 */
1924 if( col1domcol2 )
1925 {
1926 SCIP_CALL( findFixings(scip, matrix, varcol1, col1,
1927 tmpupperbounddominatingcol1, tmpwclowerbounddominatingcol1,
1928 tmplowerbounddominatingcol1, tmpwcupperbounddominatingcol1,
1929 varcol2, col2,
1930 varstofix, onlybinvars, onlyoneone, nfixings) );
1931
1932 if( presoldata->predbndstr )
1933 {
1934 SCIP_CALL( predBndStr(scip, varcol1, col1,
1935 tmpupperbounddominatingcol1,
1936 tmplowerbounddominatingcol1, tmpwcupperbounddominatingcol1,
1937 varcol2, col2,
1938 tmpupperbounddominatedcol1, tmpwclowerbounddominatedcol1,
1939 tmplowerbounddominatedcol1,
1940 varstofix, nchgbds) );
1941 }
1942 }
1943 else if( col2domcol1 )
1944 {
1945 SCIP_CALL( findFixings(scip, matrix, varcol2, col2,
1946 tmpupperbounddominatingcol2, tmpwclowerbounddominatingcol2,
1947 tmplowerbounddominatingcol2, tmpwcupperbounddominatingcol2,
1948 varcol1, col1,
1949 varstofix, onlybinvars, onlyoneone, nfixings) );
1950
1951 if( presoldata->predbndstr )
1952 {
1953 SCIP_CALL( predBndStr(scip, varcol2, col2,
1954 tmpupperbounddominatingcol2,
1955 tmplowerbounddominatingcol2, tmpwcupperbounddominatingcol2,
1956 varcol1, col1,
1957 tmpupperbounddominatedcol2, tmpwclowerbounddominatedcol2,
1958 tmplowerbounddominatedcol2,
1959 varstofix, nchgbds) );
1960 }
1961 }
1962 if( varstofix[col1] == FIXATLB )
1963 break;
1964 }
1965 }
1966
1967 return SCIP_OKAY;
1968}
1969
1970
1971/*
1972 * Callback methods of presolver
1973 */
1974
1975
1976/** copy method for constraint handler plugins (called when SCIP copies plugins) */
1977static
1978SCIP_DECL_PRESOLCOPY(presolCopyDomcol)
1979{ /*lint --e{715}*/
1980 assert(scip != NULL);
1981 assert(presol != NULL);
1982 assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
1983
1984 /* call inclusion method of presolver */
1985 SCIP_CALL( SCIPincludePresolDomcol(scip) );
1986
1987 return SCIP_OKAY;
1988}
1989
1990/** destructor of presolver to free user data (called when SCIP is exiting) */
1991static
1992SCIP_DECL_PRESOLFREE(presolFreeDomcol)
1993{ /*lint --e{715}*/
1994 SCIP_PRESOLDATA* presoldata;
1995
1996 /* free presolver data */
1997 presoldata = SCIPpresolGetData(presol);
1998 assert(presoldata != NULL);
1999
2000 SCIPfreeBlockMemory(scip, &presoldata);
2001 SCIPpresolSetData(presol, NULL);
2002
2003 return SCIP_OKAY;
2004}
2005
2006/** execution method of presolver */
2007static
2008SCIP_DECL_PRESOLEXEC(presolExecDomcol)
2009{ /*lint --e{715}*/
2010 SCIP_PRESOLDATA* presoldata;
2011 SCIP_MATRIX* matrix;
2012 SCIP_Bool initialized;
2013 SCIP_Bool complete;
2014 SCIP_Bool infeasible;
2015 int nfixings;
2016 SCIP_Longint ndomrelations;
2017 int v;
2018 int r;
2019 FIXINGDIRECTION* varstofix;
2020 SCIP_Bool* varsprocessed;
2021 int nrows;
2022 int ncols;
2023 int* rowidxsorted;
2024 int* rowsparsity;
2025 int varcount;
2026 int* consearchcols;
2027 int* intsearchcols;
2028 int* binsearchcols;
2029 int nconfill;
2030 int nintfill;
2031 int nbinfill;
2032#ifdef SCIP_DEBUG
2033 int nconvarsfixed = 0;
2034 int nintvarsfixed = 0;
2035 int nbinvarsfixed = 0;
2036#endif
2037 int* pclass;
2038 int* colidx;
2039 int pclassstart;
2040 int pc;
2041 SCIP_Bool* varineq;
2042
2043 assert(result != NULL);
2044 *result = SCIP_DIDNOTRUN;
2045
2046 if( !SCIPallowStrongDualReds(scip) || SCIPisStopped(scip) )
2047 return SCIP_OKAY;
2048
2049 presoldata = SCIPpresolGetData(presol);
2050 assert(presoldata != NULL);
2051
2052 /* don't run for pure LPs */
2053 if( !presoldata->continuousred && (SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip) == 0) )
2054 return SCIP_OKAY;
2055
2056 *result = SCIP_DIDNOTFIND;
2057
2058 matrix = NULL;
2059 SCIP_CALL( SCIPmatrixCreate(scip, &matrix, TRUE, &initialized, &complete, &infeasible,
2060 naddconss, ndelconss, nchgcoefs, nchgbds, nfixedvars) );
2061
2062 /* if infeasibility was detected during matrix creation, return here */
2063 if( infeasible )
2064 {
2065 if( initialized )
2066 SCIPmatrixFree(scip, &matrix);
2067
2068 *result = SCIP_CUTOFF;
2069 return SCIP_OKAY;
2070 }
2071
2072 if( !initialized )
2073 return SCIP_OKAY;
2074
2075 nfixings = 0;
2076 ndomrelations = 0;
2077 nrows = SCIPmatrixGetNRows(matrix);
2078 ncols = SCIPmatrixGetNColumns(matrix);
2079 assert(SCIPgetNVars(scip) == ncols);
2080
2081 SCIP_CALL( SCIPallocBufferArray(scip, &varstofix, ncols) );
2082 BMSclearMemoryArray(varstofix, ncols);
2083
2084 SCIP_CALL( SCIPallocBufferArray(scip, &varsprocessed, ncols) );
2085
2086 /* do not process columns that do not have all locks represented in the matrix */
2087 for( v = 0; v < ncols; ++v )
2088 varsprocessed[v] = SCIPmatrixUplockConflict(matrix, v) || SCIPmatrixDownlockConflict(matrix, v);
2089
2090 SCIP_CALL( SCIPallocBufferArray(scip, &consearchcols, ncols) );
2091 SCIP_CALL( SCIPallocBufferArray(scip, &intsearchcols, ncols) );
2092 SCIP_CALL( SCIPallocBufferArray(scip, &binsearchcols, ncols) );
2093
2094 SCIP_CALL( SCIPallocBufferArray(scip, &rowidxsorted, nrows) );
2095 SCIP_CALL( SCIPallocBufferArray(scip, &rowsparsity, nrows) );
2096 for( r = 0; r < nrows; ++r )
2097 {
2098 rowidxsorted[r] = r;
2099 rowsparsity[r] = SCIPmatrixGetRowNNonzs(matrix, r);
2100 }
2101
2102 SCIP_CALL( SCIPallocBufferArray(scip, &pclass, ncols) );
2103 SCIP_CALL( SCIPallocBufferArray(scip, &colidx, ncols) );
2104 SCIP_CALL( SCIPallocBufferArray(scip, &varineq, ncols) );
2105 for( v = 0; v < ncols; v++ )
2106 {
2107 colidx[v] = v;
2108 varineq[v] = FALSE;
2109 }
2110
2111 /* init pair comparision control */
2112 presoldata->numcurrentpairs = presoldata->nummaxpairs;
2113
2114 varcount = 0;
2115
2116 /* 1.stage: search dominance relations of parallel columns
2117 * within equalities and ranged rows
2118 */
2119 if( (presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 )
2120 {
2121 SCIP_CALL( detectParallelCols(scip, matrix, pclass, varineq) );
2122 SCIPsortIntInt(pclass, colidx, ncols);
2123
2124 pc = 0;
2125 while( pc < ncols )
2126 {
2127 int varidx;
2128
2129 varidx = 0;
2130 nconfill = 0;
2131 nintfill = 0;
2132 nbinfill = 0;
2133
2134 pclassstart = pclass[pc];
2135 while( pc < ncols && pclassstart == pclass[pc] )
2136 {
2137 SCIP_VAR* var;
2138
2139 varidx = colidx[pc];
2140 var = SCIPmatrixGetVar(matrix, varidx);
2141
2142 /* we only regard variables which were not processed yet and
2143 * are present within equalities or ranged rows
2144 */
2145 if( !varsprocessed[varidx] && varineq[varidx] )
2146 {
2147 /* we search only for dominance relations between the same variable type */
2148 if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS )
2149 {
2150 consearchcols[nconfill++] = varidx;
2151 }
2152 else if( SCIPvarIsBinary(var) )
2153 {
2154 binsearchcols[nbinfill++] = varidx;
2155 }
2156 else
2157 {
2158 assert(SCIPvarGetType(var) == SCIP_VARTYPE_INTEGER || SCIPvarGetType(var) == SCIP_VARTYPE_IMPLINT);
2159 intsearchcols[nintfill++] = varidx;
2160 }
2161 }
2162 ++pc;
2163 }
2164
2165 /* continuous variables */
2166 if( nconfill > 1 && presoldata->continuousred )
2167 {
2168 SCIP_CALL( findDominancePairs(scip, matrix, presoldata, consearchcols, nconfill, FALSE,
2169 varstofix, &nfixings, &ndomrelations, nchgbds) );
2170
2171 for( v = 0; v < nconfill; ++v )
2172 varsprocessed[consearchcols[v]] = TRUE;
2173
2174 varcount += nconfill;
2175 }
2176 else if( nconfill == 1 )
2177 {
2178 if( varineq[varidx] )
2179 varsprocessed[consearchcols[0]] = TRUE;
2180 }
2181
2182 /* integer and impl-integer variables */
2183 if( nintfill > 1 )
2184 {
2185 SCIP_CALL( findDominancePairs(scip, matrix, presoldata, intsearchcols, nintfill, FALSE,
2186 varstofix, &nfixings, &ndomrelations, nchgbds) );
2187
2188 for( v = 0; v < nintfill; ++v )
2189 varsprocessed[intsearchcols[v]] = TRUE;
2190
2191 varcount += nintfill;
2192 }
2193 else if( nintfill == 1 )
2194 {
2195 if( varineq[varidx] )
2196 varsprocessed[intsearchcols[0]] = TRUE;
2197 }
2198
2199 /* binary variables */
2200 if( nbinfill > 1 )
2201 {
2202 SCIP_CALL( findDominancePairs(scip, matrix, presoldata, binsearchcols, nbinfill, TRUE,
2203 varstofix, &nfixings, &ndomrelations, nchgbds) );
2204
2205 for( v = 0; v < nbinfill; ++v )
2206 varsprocessed[binsearchcols[v]] = TRUE;
2207
2208 varcount += nbinfill;
2209 }
2210 else if( nbinfill == 1 )
2211 {
2212 if( varineq[varidx] )
2213 varsprocessed[binsearchcols[0]] = TRUE;
2214 }
2215
2216 if( varcount >= ncols )
2217 break;
2218 }
2219 }
2220
2221 /* 2.stage: search dominance relations for the remaining columns
2222 * by increasing row-sparsity
2223 */
2224 if( (presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 )
2225 {
2226 SCIPsortIntInt(rowsparsity, rowidxsorted, nrows);
2227
2228 for( r = 0; r < nrows; ++r )
2229 {
2230 int rowidx;
2231 int* rowpnt;
2232 int* rowend;
2233
2234 /* break if the time limit was reached; since the check is expensive,
2235 * we only check all 1000 constraints
2236 */
2237 if( (r % 1000 == 0) && SCIPisStopped(scip) )
2238 break;
2239
2240 rowidx = rowidxsorted[r];
2241 rowpnt = SCIPmatrixGetRowIdxPtr(matrix, rowidx);
2242 rowend = rowpnt + SCIPmatrixGetRowNNonzs(matrix, rowidx);
2243
2244 if( SCIPmatrixGetRowNNonzs(matrix, rowidx) == 1 )
2245 continue;
2246
2247 nconfill = 0;
2248 nintfill = 0;
2249 nbinfill = 0;
2250
2251 for( ; rowpnt < rowend; rowpnt++ )
2252 {
2253 if( !(varsprocessed[*rowpnt]) )
2254 {
2255 int varidx;
2256 SCIP_VAR* var;
2257
2258 varidx = *rowpnt;
2259 var = SCIPmatrixGetVar(matrix, varidx);
2260
2261 /* we search only for dominance relations between the same variable type */
2262 if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS )
2263 {
2264 consearchcols[nconfill++] = varidx;
2265 }
2266 else if( SCIPvarIsBinary(var) )
2267 {
2268 binsearchcols[nbinfill++] = varidx;
2269 }
2270 else
2271 {
2272 assert(SCIPvarGetType(var) == SCIP_VARTYPE_INTEGER || SCIPvarGetType(var) == SCIP_VARTYPE_IMPLINT);
2273 intsearchcols[nintfill++] = varidx;
2274 }
2275 }
2276 }
2277
2278 /* continuous variables */
2279 if( nconfill > 1 && presoldata->continuousred )
2280 {
2281 SCIP_CALL( findDominancePairs(scip, matrix, presoldata, consearchcols, nconfill, FALSE,
2282 varstofix, &nfixings, &ndomrelations, nchgbds) );
2283
2284 for( v = 0; v < nconfill; ++v )
2285 varsprocessed[consearchcols[v]] = TRUE;
2286
2287 varcount += nconfill;
2288 }
2289
2290 /* integer and impl-integer variables */
2291 if( nintfill > 1 )
2292 {
2293 SCIP_CALL( findDominancePairs(scip, matrix, presoldata, intsearchcols, nintfill, FALSE,
2294 varstofix, &nfixings, &ndomrelations, nchgbds) );
2295
2296 for( v = 0; v < nintfill; ++v )
2297 varsprocessed[intsearchcols[v]] = TRUE;
2298
2299 varcount += nintfill;
2300 }
2301
2302 /* binary variables */
2303 if( nbinfill > 1 )
2304 {
2305 SCIP_CALL( findDominancePairs(scip, matrix, presoldata, binsearchcols, nbinfill, TRUE,
2306 varstofix, &nfixings, &ndomrelations, nchgbds) );
2307
2308 for( v = 0; v < nbinfill; ++v )
2309 varsprocessed[binsearchcols[v]] = TRUE;
2310
2311 varcount += nbinfill;
2312 }
2313
2314 if( varcount >= ncols )
2315 break;
2316 }
2317 }
2318
2319 if( nfixings > 0 )
2320 {
2321 int oldnfixedvars;
2322
2323 oldnfixedvars = *nfixedvars;
2324
2325 for( v = ncols - 1; v >= 0; --v )
2326 {
2327 SCIP_Bool fixed;
2328 SCIP_VAR* var;
2329
2330 var = SCIPmatrixGetVar(matrix,v);
2331
2332 /* there should be no fixings for variables with lock conflicts,
2333 * since they where marked as processed and therefore should be skipped
2334 */
2335 assert(varstofix[v] == NOFIX || (!SCIPmatrixUplockConflict(matrix, v) && !SCIPmatrixDownlockConflict(matrix, v)) );
2336
2337 if( varstofix[v] == FIXATLB )
2338 {
2339 SCIP_Real lb;
2340
2341 lb = SCIPvarGetLbGlobal(var);
2342 assert(SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS || SCIPisFeasIntegral(scip, lb));
2343
2344 /* fix at lower bound */
2345 SCIP_CALL( SCIPfixVar(scip, var, lb, &infeasible, &fixed) );
2346 if( infeasible )
2347 {
2348 SCIPdebugMsg(scip, " -> infeasible fixing\n");
2349 *result = SCIP_CUTOFF;
2350
2351 break;
2352 }
2353 assert(fixed);
2354 (*nfixedvars)++;
2355
2356#ifdef SCIP_DEBUG
2357 if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS )
2358 nconvarsfixed++;
2359 else if( SCIPvarIsBinary(var) )
2360 nbinvarsfixed++;
2361 else
2362 nintvarsfixed++;
2363#endif
2364 }
2365 else if( varstofix[v] == FIXATUB )
2366 {
2367 SCIP_Real ub;
2368
2369 ub = SCIPvarGetUbGlobal(var);
2370 assert(SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS || SCIPisFeasIntegral(scip, ub));
2371
2372 /* fix at upper bound */
2373 SCIP_CALL( SCIPfixVar(scip, var, ub, &infeasible, &fixed) );
2374 if( infeasible )
2375 {
2376 SCIPdebugMsg(scip, " -> infeasible fixing\n");
2377 *result = SCIP_CUTOFF;
2378
2379 break;
2380 }
2381 assert(fixed);
2382 (*nfixedvars)++;
2383
2384#ifdef SCIP_DEBUG
2385 if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS )
2386 nconvarsfixed++;
2387 else if( SCIPvarIsBinary(var) )
2388 nbinvarsfixed++;
2389 else
2390 nintvarsfixed++;
2391#endif
2392 }
2393 }
2394
2395 if( *result != SCIP_CUTOFF && *nfixedvars > oldnfixedvars )
2396 *result = SCIP_SUCCESS;
2397 }
2398
2399 SCIPfreeBufferArray(scip, &varineq);
2400 SCIPfreeBufferArray(scip, &colidx);
2401 SCIPfreeBufferArray(scip, &pclass);
2402 SCIPfreeBufferArray(scip, &rowsparsity);
2403 SCIPfreeBufferArray(scip, &rowidxsorted);
2404 SCIPfreeBufferArray(scip, &binsearchcols);
2405 SCIPfreeBufferArray(scip, &intsearchcols);
2406 SCIPfreeBufferArray(scip, &consearchcols);
2407 SCIPfreeBufferArray(scip, &varsprocessed);
2408 SCIPfreeBufferArray(scip, &varstofix);
2409
2410#ifdef SCIP_DEBUG
2411 if( (nconvarsfixed + nintvarsfixed + nbinvarsfixed) > 0 )
2412 {
2413 SCIPdebugMsg(scip, "### %d vars [%" SCIP_LONGINT_FORMAT " dom] => fixed [cont: %d, int: %d, bin: %d], %scutoff detected\n",
2414 ncols, ndomrelations, nconvarsfixed, nintvarsfixed, nbinvarsfixed, (*result != SCIP_CUTOFF) ? "no " : "");
2415 }
2416#endif
2417
2418 SCIPmatrixFree(scip, &matrix);
2419
2420 return SCIP_OKAY;
2421}
2422
2423/*
2424 * presolver specific interface methods
2425 */
2426
2427/** creates the domcol presolver and includes it in SCIP */
2428SCIP_RETCODE SCIPincludePresolDomcol(
2429 SCIP* scip /**< SCIP data structure */
2430 )
2431{
2432 SCIP_PRESOLDATA* presoldata;
2433 SCIP_PRESOL* presol;
2434
2435 /* create domcol presolver data */
2436 SCIP_CALL( SCIPallocBlockMemory(scip, &presoldata) );
2437
2438 /* include presolver */
2439 SCIP_CALL( SCIPincludePresolBasic(scip, &presol, PRESOL_NAME, PRESOL_DESC, PRESOL_PRIORITY, PRESOL_MAXROUNDS,
2440 PRESOL_TIMING, presolExecDomcol, presoldata) );
2441 SCIP_CALL( SCIPsetPresolCopy(scip, presol, presolCopyDomcol) );
2442 SCIP_CALL( SCIPsetPresolFree(scip, presol, presolFreeDomcol) );
2443
2444 SCIP_CALL( SCIPaddIntParam(scip,
2445 "presolving/domcol/numminpairs",
2446 "minimal number of pair comparisons",
2447 &presoldata->numminpairs, FALSE, DEFAULT_NUMMINPAIRS, 100, DEFAULT_NUMMAXPAIRS, NULL, NULL) );
2448
2449 SCIP_CALL( SCIPaddIntParam(scip,
2450 "presolving/domcol/nummaxpairs",
2451 "maximal number of pair comparisons",
2452 &presoldata->nummaxpairs, FALSE, DEFAULT_NUMMAXPAIRS, DEFAULT_NUMMINPAIRS, 1000000000, NULL, NULL) );
2453
2454 SCIP_CALL( SCIPaddBoolParam(scip,
2455 "presolving/domcol/predbndstr",
2456 "should predictive bound strengthening be applied?",
2457 &presoldata->predbndstr, FALSE, DEFAULT_PREDBNDSTR, NULL, NULL) );
2458
2459 SCIP_CALL( SCIPaddBoolParam(scip,
2460 "presolving/domcol/continuousred",
2461 "should reductions for continuous variables be performed?",
2462 &presoldata->continuousred, FALSE, DEFAULT_CONTINUOUS_RED, NULL, NULL) );
2463
2464 return SCIP_OKAY;
2465}
r
SCIP_Real * r
Definition: circlepacking.c:59
NULL
#define NULL
Definition: def.h:266
SCIP_Longint
#define SCIP_Longint
Definition: def.h:157
SCIP_Bool
#define SCIP_Bool
Definition: def.h:91
MIN
#define MIN(x, y)
Definition: def.h:242
SCIP_Real
#define SCIP_Real
Definition: def.h:172
TRUE
#define TRUE
Definition: def.h:93
FALSE
#define FALSE
Definition: def.h:94
MAX
#define MAX(x, y)
Definition: def.h:238
SCIP_LONGINT_FORMAT
#define SCIP_LONGINT_FORMAT
Definition: def.h:164
SCIPABORT
#define SCIPABORT()
Definition: def.h:345
SCIP_CALL
#define SCIP_CALL(x)
Definition: def.h:373
SCIPisStopped
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:734
SCIPgetNIntVars
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2082
SCIPgetNVars
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1992
SCIPgetNBinVars
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2037
SCIPdebugMsgPrint
#define SCIPdebugMsgPrint
Definition: scip_message.h:79
SCIPdebugMsg
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIPaddIntParam
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:83
SCIPaddBoolParam
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:57
SCIPincludePresolDomcol
SCIP_RETCODE SCIPincludePresolDomcol(SCIP *scip)
Definition: presol_domcol.c:2428
SCIPallocBufferArray
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
SCIPfreeBufferArray
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
SCIPfreeBlockMemory
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
SCIPallocBlockMemory
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
SCIPpresolSetData
void SCIPpresolSetData(SCIP_PRESOL *presol, SCIP_PRESOLDATA *presoldata)
Definition: presol.c:522
SCIPpresolGetData
SCIP_PRESOLDATA * SCIPpresolGetData(SCIP_PRESOL *presol)
Definition: presol.c:512
SCIPsetPresolFree
SCIP_RETCODE SCIPsetPresolFree(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLFREE((*presolfree)))
Definition: scip_presol.c:156
SCIPsetPresolCopy
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLCOPY((*presolcopy)))
Definition: scip_presol.c:140
SCIPincludePresolBasic
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
SCIPpresolGetName
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
Definition: presol.c:599
SCIPisFeasGE
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:832
SCIPinfinity
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip_numerics.c:510
SCIPisGE
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:497
SCIPisPositive
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:570
SCIPisLE
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:471
SCIPfloor
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:631
SCIPisInfinity
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:521
SCIPisFeasLE
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:806
SCIPisFeasIntegral
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:881
SCIPisNegative
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:582
SCIPceil
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:643
SCIPisEQ
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:445
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
SCIPvarIsBinary
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17598
SCIPchgVarLb
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4799
SCIPvarGetStatus
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17537
SCIPchgVarUb
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4889
SCIPvarGetObj
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17925
SCIPvarGetType
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17583
SCIPvarGetUbGlobal
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18087
SCIPvarGetName
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17418
SCIPvarGetLbGlobal
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18077
SCIPfixVar
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip_var.c:8399
SCIPvarsHaveCommonClique
SCIP_Bool SCIPvarsHaveCommonClique(SCIP_VAR *var1, SCIP_Bool value1, SCIP_VAR *var2, SCIP_Bool value2, SCIP_Bool regardimplics)
Definition: var.c:11474
SCIPallowStrongDualReds
SCIP_Bool SCIPallowStrongDualReds(SCIP *scip)
Definition: scip_var.c:8752
SCIPsortIntInt
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
SCIPsortRealInt
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
SCIPsortIntIntReal
void SCIPsortIntIntReal(int *intarray1, int *intarray2, SCIP_Real *realarray, int len)
SCIPmatrixUplockConflict
SCIP_Bool SCIPmatrixUplockConflict(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1872
SCIPmatrixGetRowNMinActNegInf
int SCIPmatrixGetRowNMinActNegInf(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1812
SCIPmatrixGetColIdxPtr
int * SCIPmatrixGetColIdxPtr(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1580
SCIPmatrixGetRowNNonzs
int SCIPmatrixGetRowNNonzs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1708
SCIPmatrixGetColNNonzs
int SCIPmatrixGetColNNonzs(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1592
SCIPmatrixIsRowRhsInfinity
SCIP_Bool SCIPmatrixIsRowRhsInfinity(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1766
SCIPmatrixGetRowMaxActivity
SCIP_Real SCIPmatrixGetRowMaxActivity(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1800
SCIPmatrixGetRowLhs
SCIP_Real SCIPmatrixGetRowLhs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1742
SCIPmatrixGetRowValPtr
SCIP_Real * SCIPmatrixGetRowValPtr(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1684
SCIPmatrixDownlockConflict
SCIP_Bool SCIPmatrixDownlockConflict(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1884
SCIPmatrixGetRowRhs
SCIP_Real SCIPmatrixGetRowRhs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1754
SCIPmatrixGetColValPtr
SCIP_Real * SCIPmatrixGetColValPtr(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1568
SCIPmatrixGetRowNMinActPosInf
int SCIPmatrixGetRowNMinActPosInf(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1824
SCIPmatrixCreate
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
SCIPmatrixGetNColumns
int SCIPmatrixGetNColumns(SCIP_MATRIX *matrix)
Definition: matrix.c:1604
SCIPmatrixGetRowMinActivity
SCIP_Real SCIPmatrixGetRowMinActivity(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1788
SCIPmatrixFree
void SCIPmatrixFree(SCIP *scip, SCIP_MATRIX **matrix)
Definition: matrix.c:1072
SCIPmatrixGetRowNMaxActPosInf
int SCIPmatrixGetRowNMaxActPosInf(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1848
SCIPmatrixGetRowNMaxActNegInf
int SCIPmatrixGetRowNMaxActNegInf(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1836
SCIPmatrixGetVar
SCIP_VAR * SCIPmatrixGetVar(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1660
SCIPmatrixGetRowIdxPtr
int * SCIPmatrixGetRowIdxPtr(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1696
SCIPmatrixGetNRows
int SCIPmatrixGetNRows(SCIP_MATRIX *matrix)
Definition: matrix.c:1732
memory.h
memory allocation routines
BMSclearMemoryArray
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:130
getActivityResidualsUpperBound
static void getActivityResidualsUpperBound(SCIP *scip, SCIP_MATRIX *matrix, int row, int col, SCIP_Real coef, int upperboundcol, SCIP_Real upperboundcoef, SCIP_Real *minresactivity, SCIP_Real *maxresactivity, SCIP_Bool *success)
Definition: presol_domcol.c:253
findFixings
static SCIP_RETCODE findFixings(SCIP *scip, SCIP_MATRIX *matrix, SCIP_VAR *dominatingvar, int dominatingidx, SCIP_Real dominatingub, SCIP_Real dominatingwclb, SCIP_Real dominatinglb, SCIP_Real dominatingwcub, SCIP_VAR *dominatedvar, int dominatedidx, FIXINGDIRECTION *varstofix, SCIP_Bool onlybinvars, SCIP_Bool onlyoneone, int *nfixings)
Definition: presol_domcol.c:1406
predBndStr
static SCIP_RETCODE predBndStr(SCIP *scip, SCIP_VAR *dominatingvar, int dominatingidx, SCIP_Real dominatingub, SCIP_Real dominatinglb, SCIP_Real dominatingwcub, SCIP_VAR *dominatedvar, int dominatedidx, SCIP_Real dominatedub, SCIP_Real dominatedwclb, SCIP_Real dominatedlb, FIXINGDIRECTION *varstofix, int *nchgbds)
Definition: presol_domcol.c:1208
PRESOL_NAME
#define PRESOL_NAME
Definition: presol_domcol.c:70
Fixingdirection
Fixingdirection
Definition: presol_domcol.c:100
FIXATUB
@ FIXATUB
Definition: presol_domcol.c:103
FIXATLB
@ FIXATLB
Definition: presol_domcol.c:101
NOFIX
@ NOFIX
Definition: presol_domcol.c:102
SCIP_DECL_PRESOLEXEC
static SCIP_DECL_PRESOLEXEC(presolExecDomcol)
Definition: presol_domcol.c:2008
FIXINGDIRECTION
enum Fixingdirection FIXINGDIRECTION
Definition: presol_domcol.c:105
updateBounds
static SCIP_RETCODE updateBounds(SCIP *scip, SCIP_MATRIX *matrix, int row, int col1, SCIP_Real val1, int col2, SCIP_Real val2, SCIP_Bool predictdominating, SCIP_Real *upperbound, SCIP_Real *wclowerbound, SCIP_Real *lowerbound, SCIP_Real *wcupperbound)
Definition: presol_domcol.c:957
DEFAULT_CONTINUOUS_RED
#define DEFAULT_CONTINUOUS_RED
Definition: presol_domcol.c:80
DEFAULT_NUMMINPAIRS
#define DEFAULT_NUMMINPAIRS
Definition: presol_domcol.c:76
DEFAULT_NUMMAXPAIRS
#define DEFAULT_NUMMAXPAIRS
Definition: presol_domcol.c:77
PRESOL_PRIORITY
#define PRESOL_PRIORITY
Definition: presol_domcol.c:72
SCIP_DECL_PRESOLFREE
static SCIP_DECL_PRESOLFREE(presolFreeDomcol)
Definition: presol_domcol.c:1992
detectParallelCols
static SCIP_RETCODE detectParallelCols(SCIP *scip, SCIP_MATRIX *matrix, int *pclass, SCIP_Bool *varineq)
Definition: presol_domcol.c:1037
calcVarBoundsDominated
static SCIP_RETCODE calcVarBoundsDominated(SCIP *scip, SCIP_MATRIX *matrix, int row, int coldominating, SCIP_Real valdominating, int coldominated, SCIP_Real valdominated, SCIP_Bool *ubcalculated, SCIP_Real *calculatedub, SCIP_Bool *wclbcalculated, SCIP_Real *calculatedwclb, SCIP_Bool *lbcalculated, SCIP_Real *calculatedlb, SCIP_Bool *wcubcalculated, SCIP_Real *calculatedwcub)
Definition: presol_domcol.c:609
calcVarBoundsDominating
static SCIP_RETCODE calcVarBoundsDominating(SCIP *scip, SCIP_MATRIX *matrix, int row, int coldominating, SCIP_Real valdominating, int coldominated, SCIP_Real valdominated, SCIP_Bool *ubcalculated, SCIP_Real *calculatedub, SCIP_Bool *wclbcalculated, SCIP_Real *calculatedwclb, SCIP_Bool *lbcalculated, SCIP_Real *calculatedlb, SCIP_Bool *wcubcalculated, SCIP_Real *calculatedwcub)
Definition: presol_domcol.c:784
findDominancePairs
static SCIP_RETCODE findDominancePairs(SCIP *scip, SCIP_MATRIX *matrix, SCIP_PRESOLDATA *presoldata, int *searchcols, int searchsize, SCIP_Bool onlybinvars, FIXINGDIRECTION *varstofix, int *nfixings, SCIP_Longint *ndomrelations, int *nchgbds)
Definition: presol_domcol.c:1544
PRESOL_MAXROUNDS
#define PRESOL_MAXROUNDS
Definition: presol_domcol.c:73
SCIP_DECL_PRESOLCOPY
static SCIP_DECL_PRESOLCOPY(presolCopyDomcol)
Definition: presol_domcol.c:1978
PRESOL_TIMING
#define PRESOL_TIMING
Definition: presol_domcol.c:74
getActivityResidualsLowerBound
static void getActivityResidualsLowerBound(SCIP *scip, SCIP_MATRIX *matrix, int row, int col, SCIP_Real coef, int lowerboundcol, SCIP_Real lowerboundcoef, SCIP_Real *minresactivity, SCIP_Real *maxresactivity, SCIP_Bool *success)
Definition: presol_domcol.c:430
DEFAULT_PREDBNDSTR
#define DEFAULT_PREDBNDSTR
Definition: presol_domcol.c:79
PRESOL_DESC
#define PRESOL_DESC
Definition: presol_domcol.c:71
presol_domcol.h
dominated column presolver
pub_matrix.h
public methods for matrix
pub_message.h
public methods for message output
SCIPerrorMessage
#define SCIPerrorMessage
Definition: pub_message.h:64
pub_misc_sort.h
methods for sorting joint arrays of various types
pub_presol.h
public methods for presolvers
pub_var.h
public methods for problem variables
printRow
static SCIP_RETCODE printRow(SCIP *scip, FZNOUTPUT *fznoutput, const char *type, SCIP_VAR **vars, SCIP_Real *vals, int nvars, SCIP_Real rhs, SCIP_Bool hasfloats)
Definition: reader_fzn.c:3996
scip_general.h
general public methods
scip_mem.h
public methods for memory management
scip_message.h
public methods for message handling
scip_nlp.h
public methods for nonlinear relaxation
scip_numerics.h
public methods for numerical tolerances
scip_param.h
public methods for SCIP parameter handling
scip_presol.h
public methods for presolving plugins
scip_pricer.h
public methods for variable pricer plugins
scip_prob.h
public methods for global and local (sub)problems
scip_probing.h
public methods for the probing mode
scip_var.h
public methods for SCIP variables
SCIP_Matrix
Definition: struct_matrix.h:48
SCIP_Presol
Definition: struct_presol.h:47
SCIP_Var
Definition: struct_var.h:208
SCIP_PRESOLDATA
struct SCIP_PresolData SCIP_PRESOLDATA
Definition: type_presol.h:51
SCIP_DIDNOTRUN
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
SCIP_CUTOFF
@ SCIP_CUTOFF
Definition: type_result.h:48
SCIP_DIDNOTFIND
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
SCIP_SUCCESS
@ SCIP_SUCCESS
Definition: type_result.h:58
SCIP_INVALIDDATA
@ SCIP_INVALIDDATA
Definition: type_retcode.h:52
SCIP_OKAY
@ SCIP_OKAY
Definition: type_retcode.h:42
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
SCIP_PRESOLTIMING_EXHAUSTIVE
#define SCIP_PRESOLTIMING_EXHAUSTIVE
Definition: type_timing.h:54
SCIP_VARTYPE_INTEGER
@ SCIP_VARTYPE_INTEGER
Definition: type_var.h:63
SCIP_VARTYPE_CONTINUOUS
@ SCIP_VARTYPE_CONTINUOUS
Definition: type_var.h:71
SCIP_VARTYPE_IMPLINT
@ SCIP_VARTYPE_IMPLINT
Definition: type_var.h:64
SCIP_VARTYPE_BINARY
@ SCIP_VARTYPE_BINARY
Definition: type_var.h:62
SCIP_VARSTATUS_MULTAGGR
@ SCIP_VARSTATUS_MULTAGGR
Definition: type_var.h:54