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