SCIP Doxygen Documentation
Loading...
Searching...
No Matches
presol_dualinfer.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/**@file presol_dualinfer.c
25 * @ingroup DEFPLUGINS_PRESOL
26 * @brief dual inference presolver
27 * @author Dieter Weninger
28 * @author Patrick Gemander
29 *
30 * This presolver does bound strengthening on continuous variables (columns) for getting bounds on dual variables y.
31 * The bounds of the dual variables are then used to fix primal variables or change the side of constraints.
32 * For ranged rows one needs to decide which side (rhs or lhs) determines the equality.
33 *
34 * We distinguish two cases concerning complementary slackness:
35 * i) reduced cost fixing: c_j - sup_y(y^T A_{.j}) > 0 => x_j = l_j
36 * c_j - inf_y(y^T A_{.j}) < 0 => x_j = u_j
37 * ii) positive dual lower bound: y_i > 0 => A_{i.}x = b_i
38 *
39 * Further information on this presolving approach are given in
40 * Achterberg et al. "Presolve reductions in mixed integer programming"
41 * and for a two-column extension in
42 * Chen et al. "Two-row and two-column mixed-integer presolve using hasing-based pairing methods".
43 */
44
45/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
46
47#include "scip/scipdefplugins.h"
48#include "scip/pub_matrix.h"
49#include "blockmemshell/memory.h"
50#include "scip/cons_linear.h"
51#include "scip/presol_dualinfer.h"
52#include "scip/pub_cons.h"
53#include "scip/pub_matrix.h"
54#include "scip/pub_message.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_numerics.h"
61#include "scip/scip_presol.h"
62#include "scip/scip_prob.h"
63#include "scip/scip_probing.h"
64#include "scip/scip_var.h"
65
66#define PRESOL_NAME "dualinfer"
67#define PRESOL_DESC "exploit dual information for fixings and side changes"
68#define PRESOL_PRIORITY (-3000) /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */
69#define PRESOL_MAXROUNDS 0 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
70#define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */
71
72#define DEFAULT_TWOCOLUMN_COMBINE TRUE /**< should two column convex combination be used per default */
73#define DEFAULT_MAXLOOPS_DUALBNDSTR 12 /**< default maximal number of loops for dual bound strengthening */
74#define DEFAULT_MAXCONSIDEREDNONZEROS 100 /**< default maximal number of considered non-zeros within one row */
75#define DEFAULT_MAXRETRIEVEFAILS 1000 /**< default maximal number of consecutive useless hashtable retrieves */
76#define DEFAULT_MAXCOMBINEFAILS 1000 /**< default maximal number of consecutive useless row combines */
77#define DEFAULT_MAXHASHFAC 10 /**< default maximal number of hashlist entries as multiple of number of rows in the problem */
78#define DEFAULT_MAXPAIRFAC 1 /**< default maximal number of processed row pairs as multiple of the number of rows in the problem */
79#define DEFAULT_MAXROWSUPPORT 3 /**< default maximal number of non-zeros in one row for turning an inequality into an equality */
80
81
82/*
83 * Data structures
84 */
85
86/** control parameters */
87struct SCIP_PresolData
88{
89 SCIP_Bool usetwocolcombine; /**< use convex combination of two columns */
90 int maxdualbndloops; /**< default number of dual bound strengthening loops */
91 int maxpairfac; /**< maximal number of processed row pairs as multiple of the number of rows in the problem (-1: no limit) */
92 int maxhashfac; /**< maximal number of hashlist entries as multiple of number of rows in the problem (-1: no limit) */
93 int maxretrievefails; /**< maximal number of consecutive useless hashtable retrieves */
94 int maxcombinefails; /**< maximal number of consecutive useless row combines */
95 int maxconsiderednonzeros; /**< maximal number of considered non-zeros within one row (-1: no limit) */
96 int maxrowsupport; /**< maximal number of non-zeros in one row for turning an inequality into an equality */
97};
98
99/** type of variable fixing direction */
100enum Fixingdirection
101{
102 FIXATLB = -1, /** fix variable at its lower bound */
103 NOFIX = 0, /** no fixing */
104 FIXATUB = 1 /** fix variable at its upper bound */
105};
106typedef enum Fixingdirection FIXINGDIRECTION;
107
108/** type of constraint side change */
109enum SideChange
110{
111 RHSTOLHS = -1, /** set rhs to value of lhs */
112 NOCHANGE = 0, /** no side change */
113 LHSTORHS = 1 /** set lhs to value of rhs */
114};
115typedef enum SideChange SIDECHANGE;
116
117/** Signum for convex-combined variable coefficients \f$(\lambda * A_{ri} + (1 - \lambda) * A_{si})\f$
118 * UP - Coefficient changes from negative to positive for increasing lambda
119 * DN - Coefficient changes from positive to negative for increasing lambda
120 * POS - Coefficient is positive for all lambda in (0,1)
121 * NEG - Coefficient is negative for all lambda in (0,1)
122 */
123enum signum {UP, DN, POS, NEG};
124
125/** structure representing a pair of column indices; used for lookup in a hashtable */
126struct ColPair
127{
128 int col1idx; /**< first row index */
129 int col2idx; /**< second row index */
130};
131typedef struct ColPair COLPAIR;
132
133/*
134 * Local methods
135 */
136
137/** encode contents of a colpair as void* pointer */
138static
139void*
140encodeColPair(
141 COLPAIR* colpair /**< pointer to colpair */
142 )
143{
144 uint64_t a;
145 uint64_t b;
146
147 assert(colpair->col1idx >= 0);
148 assert(colpair->col2idx >= 0);
149
150 a = (uint64_t)(long)colpair->col1idx;
151 b = (uint64_t)(long)colpair->col2idx;
152 return (void*)((a << 32) | b);
153}
154
155/** compute single positive int hashvalue for two ints */
156static
157int
158hashIndexPair(
159 int idx1, /**< first integer index */
160 int idx2 /**< second integer index */
161 )
162{
163 uint32_t hash = SCIPhashTwo(idx1, idx2);
164 return (int)(hash>>1);
165}
166
167/** add hash/rowidx pair to hashlist/rowidxlist **/
168static
169SCIP_RETCODE addEntry(
170 SCIP* scip, /**< SCIP datastructure */
171 int* pos, /**< position of last entry added */
172 int* listsize, /**< size of hashlist and rowidxlist */
173 int** hashlist, /**< block memory array containing hashes */
174 int** colidxlist, /**< block memory array containing column indices */
175 int hash, /**< hash to be inserted */
176 int colidx /**< column index to be inserted */
177 )
178{
179 if( (*pos) >= (*listsize) )
180 {
181 int newsize = SCIPcalcMemGrowSize(scip, (*pos) + 1);
182 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, hashlist, (*listsize), newsize) );
183 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, colidxlist, (*listsize), newsize) );
184 (*listsize) = newsize;
185 }
186
187 (*hashlist)[(*pos)] = hash;
188 (*colidxlist)[(*pos)] = colidx;
189 (*pos)++;
190
191 return SCIP_OKAY;
192}
193
194/** Within a sorted list, get next block with same value
195 * E.g. for [h1, h1, h1, h2, h2, h2, h2, h3,...] and end = 0
196 * returns start = 0, end = 3
197 * and on a second call with end = 3 on the same list
198 * returns start = 3, end = 7.
199 */
200static
201void findNextBlock(
202 const int* list, /**< list of integers */
203 int len, /**< length of list */
204 int* start, /**< variable to contain start index of found block */
205 int* end /**< variable to contain end index of found block */
206 )
207{
208 int i;
209 (*start) = (*end);
210 i = (*end) + 1;
211 while( i < len && list[i] == list[i - 1] )
212 i++;
213
214 (*end) = i;
215}
216
217/**
218 * The algorithm described in Belotti P. "Bound reduction using pairs of linear inequalities"
219 * tries to derive upper and lower bounds for all variables via convex combinations of linear inequalities
220 * We apply Belotti's algorithm to pairs of columns of continuous variables.
221 */
222static
223SCIP_RETCODE combineCols(
224 SCIP* scip, /**< SCIP datastructure */
225 int* row1idxptr, /**< indices specifying bound positions in lbs and ubs for first row */
226 int* row2idxptr, /**< indices specifying bound positions in lbs und ubs for second row */
227 SCIP_Real* row1valptr, /**< first row coefficients */
228 SCIP_Real* row2valptr, /**< second row coefficients */
229 SCIP_Real b1, /**< rhs of first row */
230 SCIP_Real b2, /**< rhs of second row*/
231 int row1len, /**< length of first row (e.g. row1idxptr and row1valptr)*/
232 int row2len, /**< length of second row (e.g. row2idxptr and row2valptr)*/
233 int ncols, /**< length of bound arrays lbs and ubs */
234 SCIP_Bool swaprow1, /**< should the sense of the first row be swapped to <= ? */
235 SCIP_Bool swaprow2, /**< should the sense of the second row be swapped to <= ? */
236 SCIP_Real* lbs, /**< lower bound array */
237 SCIP_Real* ubs, /**< upper bound array */
238 SCIP_Bool* success /**< we return (success || found better bounds") */
239 )
240{
241 int i;
242 int j;
243 int nvars;
244 int* varinds;
245 int nbreakpoints;
246 SCIP_Real* breakpoints;
247 int idx;
248 int idx1;
249 int idx2;
250 SCIP_Real* row1coefs;
251 SCIP_Real* row2coefs;
252 enum signum* signs;
253 int ninfs;
254 int l1infs;
255 SCIP_Real l1;
256 SCIP_Real l2;
257 SCIP_Real* newlbs;
258 SCIP_Real* newubs;
259 SCIP_Real coef;
260 int sign;
261 int shift;
262
263 SCIP_CALL( SCIPallocBufferArray(scip, &row1coefs, ncols) );
264 SCIP_CALL( SCIPallocBufferArray(scip, &row2coefs, ncols) );
265
266 SCIPsortIntReal(row1idxptr, row1valptr, row1len);
267 SCIPsortIntReal(row2idxptr, row2valptr, row2len);
268
269 /* swap rows if necessary */
270 if( swaprow1 )
271 {
272 for( i = 0; i < row1len; i++ )
273 row1coefs[row1idxptr[i]] = -row1valptr[i];
274 b1 = -b1;
275 }
276 else
277 {
278 for( i = 0; i < row1len; i++ )
279 row1coefs[row1idxptr[i]] = row1valptr[i];
280 }
281
282 if( swaprow2 )
283 {
284 for( i = 0; i < row2len; i++ )
285 row2coefs[row2idxptr[i]] = -row2valptr[i];
286 b2 = -b2;
287 }
288 else
289 {
290 for( i = 0; i < row2len; i++ )
291 row2coefs[row2idxptr[i]] = row2valptr[i];
292 }
293
294 SCIP_CALL( SCIPallocBufferArray(scip, &varinds, ncols) );
295 SCIP_CALL( SCIPallocBufferArray(scip, &signs, ncols) );
296 SCIP_CALL( SCIPallocBufferArray(scip, &breakpoints, ncols) );
297
298 /* calculate cancellation breakpoints and sign behaviour */
299 i = 0;
300 j = 0;
301 nvars = 0;
302 nbreakpoints = 0;
303 while( i < row1len && j < row2len )
304 {
305 assert(i + 1 == row1len || row1idxptr[i] < row1idxptr[i + 1]);
306 assert(j + 1 == row2len || row2idxptr[j] < row2idxptr[j + 1]);
307
308 idx1 = row1idxptr[i];
309 idx2 = row2idxptr[j];
310
311 /* We use 2.0 as default value for "no cancellation". For cancellations, this will be replaced by values in (0,1).
312 * A value larger than 1.0 is used because we sort the array and want to put non-cancellations to the end. */
313 breakpoints[nvars] = 2.0;
314
315 if( idx1 == idx2 )
316 {
317 if( (SCIPisNegative(scip, row1coefs[idx1]) && SCIPisPositive(scip, row2coefs[idx2])) ||
318 (SCIPisPositive(scip, row1coefs[idx1]) && SCIPisNegative(scip, row2coefs[idx2])) )
319 {
320 if( SCIPisNegative(scip, row2coefs[idx2]) )
321 signs[idx1] = UP;
322 else
323 signs[idx1] = DN;
324
325 breakpoints[nvars] = row2coefs[idx2] / (row2coefs[idx2] - row1coefs[idx1]);
326 nbreakpoints++;
327 }
328 else if( SCIPisPositive(scip, row1coefs[idx1]) )
329 signs[idx1] = POS;
330 else
331 signs[idx1] = NEG;
332
333 varinds[nvars] = idx1;
334 i++;
335 j++;
336 }
337 else if( idx1 < idx2 )
338 {
339 if( SCIPisPositive(scip, row1coefs[idx1]) )
340 signs[idx1] = POS;
341 else
342 signs[idx1] = NEG;
343
344 /* We will access this entry later on, so we explicitly write a zero here */
345 row2coefs[idx1] = 0.0;
346
347 varinds[nvars] = idx1;
348 i++;
349 }
350 else
351 {
352 assert(idx1 > idx2);
353 if( SCIPisPositive(scip, row2coefs[idx2]) )
354 signs[idx2] = POS;
355 else
356 signs[idx2] = NEG;
357
358 /* We will access this entry later on, so we explicitly write a zero here */
359 row1coefs[idx2] = 0.0;
360
361 varinds[nvars] = idx2;
362 j++;
363 }
364 nvars++;
365 }
366
367 while( i < row1len )
368 {
369 idx1 = row1idxptr[i];
370
371 if( SCIPisPositive(scip, row1coefs[idx1]) )
372 signs[idx1] = POS;
373 else
374 signs[idx1] = NEG;
375
376 /* We will access this entry later on, so we explicitly write a zero here */
377 row2coefs[idx1] = 0.0;
378
379 varinds[nvars] = idx1;
380 breakpoints[nvars] = 2.0;
381 nvars++;
382 i++;
383 }
384
385 while( j < row2len )
386 {
387 idx2 = row2idxptr[j];
388
389 if( SCIPisPositive(scip, row2coefs[idx2]) )
390 signs[idx2] = POS;
391 else
392 signs[idx2] = NEG;
393
394 /* We will access this entry later on, so we explicitly write a zero here */
395 row1coefs[idx2] = 0.0;
396
397 varinds[nvars] = idx2;
398 breakpoints[nvars] = 2.0;
399 nvars++;
400 j++;
401 }
402
403 SCIPsortRealInt(breakpoints, varinds, nvars);
404
405 /* The obvious preconditions for bound tightenings are met, so we try to calculate new bounds. */
406 if( nbreakpoints >= 1 )
407 {
408 SCIP_CALL( SCIPallocBufferArray(scip, &newlbs, nvars) );
409 SCIP_CALL( SCIPallocBufferArray(scip, &newubs, nvars) );
410
411 for( i = 0; i < nvars; i++)
412 {
413 idx = varinds[i];
414 newlbs[i] = lbs[idx];
415 newubs[i] = ubs[idx];
416 }
417
418 /* calculate activity contributions of each row */
419 l1 = b1;
420 l2 = b2;
421 l1infs = 0;
422 ninfs = 0;
423 for( i = 0; i < nvars; i++ )
424 {
425 idx = varinds[i];
426 if( !SCIPisZero(scip, row2coefs[idx]) )
427 {
428 if( SCIPisNegative(scip, row2coefs[idx]) )
429 {
430 if( !SCIPisInfinity(scip, -lbs[idx]) )
431 {
432 l1 -= row1coefs[idx] * lbs[idx];
433 l2 -= row2coefs[idx] * lbs[idx];
434 }
435 else
436 ninfs++;
437 }
438 else
439 {
440 /* coefficient of second row is positive */
441 if( !SCIPisInfinity(scip, ubs[idx]) )
442 {
443 l1 -= row1coefs[idx] * ubs[idx];
444 l2 -= row2coefs[idx] * ubs[idx];
445 }
446 else
447 ninfs++;
448 }
449 }
450 else
451 {
452 /* since row2coefs[idx] is zero, we have to choose the bound using row1coefs[idx] */
453 assert(!SCIPisZero(scip, row1coefs[idx]) && SCIPisZero(scip, row2coefs[idx]));
454 if( SCIPisNegative(scip, row1coefs[idx]) )
455 {
456 if( !SCIPisInfinity(scip, -lbs[idx]) )
457 l1 -= row1coefs[idx] * lbs[idx];
458 else
459 l1infs++;
460 }
461 else
462 {
463 /* coefficient of first row is positive */
464 if( !SCIPisInfinity(scip, ubs[idx]) )
465 l1 -= row1coefs[idx] * ubs[idx];
466 else
467 l1infs++;
468 }
469 }
470 }
471
472 /* Calculate bounds for lambda = 0 */
473#ifdef SCIP_MORE_DEBUG
474 SCIPdebugMsg(scip, "lambda = 0, l1 = %g, l2 = %g, ninfs = %d\n", i, breakpoints[i], l1, l2, ninfs);
475#endif
476
477 if( ninfs <= 1 )
478 {
479#ifdef SCIP_MORE_DEBUG
480 SCIP_Real oldlb;
481 SCIP_Real oldub;
482#endif
483 for( i = 0; i < nvars; i++ )
484 {
485#ifdef SCIP_MORE_DEBUG
486 oldlb = newlbs[i];
487 oldub = newubs[i];
488#endif
489 idx = varinds[i];
490 if( SCIPisPositive(scip, row2coefs[idx]) )
491 {
492 if( ninfs == 0 )
493 newlbs[i] = MAX(newlbs[i], (l2 + row2coefs[idx] * ubs[idx]) / row2coefs[idx]);
494 else if( SCIPisInfinity(scip, ubs[idx]) )
495 newlbs[i] = MAX(newlbs[i], l2 / row2coefs[idx]);
496 }
497 else if ( SCIPisNegative(scip, row2coefs[idx]) )
498 {
499 if( ninfs == 0 )
500 newubs[i] = MIN(newubs[i], (l2 + row2coefs[idx] * lbs[idx]) / row2coefs[idx]);
501 else if( SCIPisInfinity(scip, -lbs[idx]) )
502 newubs[i] = MIN(newubs[i], l2 / row2coefs[idx]);
503 }
504#ifdef SCIP_MORE_DEBUG
505 if( !SCIPisEQ(scip, oldlb, newlbs[i]) || !SCIPisEQ(scip, oldub, newubs[i]) )
506 SCIPdebugMsg(scip, "%g <= %g <= var_%d <= %g <= %g\n", oldlb, newlbs[i], i, newubs[i], oldub);
507#endif
508 }
509 }
510
511 ninfs += l1infs;
512
513 i = 0;
514 while( i < nbreakpoints )
515 {
516 int nnewinfs;
517 SCIP_Real l1update;
518 SCIP_Real l2update;
519 SCIP_Bool updated;
520
521 /* determine number of infinities and compute update for l1 and l2 */
522 shift = 0;
523 nnewinfs = 0;
524 l1update = 0.0;
525 l2update = 0.0;
526 updated = FALSE;
527 j = i;
528 while( !updated )
529 {
530 idx = varinds[j];
531 assert(signs[idx] == UP || signs[idx] == DN);
532 if( signs[idx] == UP )
533 sign = 1;
534 else
535 sign = -1;
536
537 if( !SCIPisInfinity(scip, -lbs[idx]) )
538 {
539 l1update += sign * row1coefs[idx] * lbs[idx];
540 l2update += sign * row2coefs[idx] * lbs[idx];
541 }
542 else
543 {
544 if( signs[idx] == UP )
545 ninfs--;
546 else
547 nnewinfs++;
548 }
549
550 if( !SCIPisInfinity(scip, ubs[idx]) )
551 {
552 l1update -= sign * row1coefs[idx] * ubs[idx];
553 l2update -= sign * row2coefs[idx] * ubs[idx];
554 }
555 else
556 {
557 if( signs[idx] == UP )
558 nnewinfs++;
559 else
560 ninfs--;
561 }
562
563 if( signs[idx] == UP )
564 signs[idx] = POS;
565 else
566 signs[idx] = NEG;
567
568 if( j + 1 >= nbreakpoints || !SCIPisEQ(scip, breakpoints[j], breakpoints[j + 1]) )
569 updated = TRUE;
570
571 shift++;
572 j++;
573 }
574
575#ifdef SCIP_MORE_DEBUG
576 SCIPdebugMsg(scip, "lambda_%d = %g, l1 = %g, l2 = %g, ninfs = %d\n", i, breakpoints[i], l1, l2, ninfs);
577#endif
578
579 assert(ninfs >= 0);
580
581 /* if more than one infinity destroys our bounds we cannot tighten anything */
582 if( ninfs <= 1 )
583 {
584 /* check for bounds to be tightened */
585 for( j = 0; j < nvars; j++ )
586 {
587#ifdef SCIP_MORE_DEBUG
588 SCIP_Real oldlb = newlbs[j];
589 SCIP_Real oldub = newubs[j];
590#endif
591
592 idx = varinds[j];
593 coef = breakpoints[i] * row1coefs[idx] + (1 - breakpoints[i]) * row2coefs[idx];
594 assert(!SCIPisEQ(scip, breakpoints[i], 2.0));
595
596 /* skip if the coefficient is too close to zero as it becomes numerically unstable */
597 if( SCIPisZero(scip, coef) )
598 continue;
599
600 if( signs[idx] == POS || signs[idx] == DN )
601 {
602 if( ninfs == 0 )
603 newlbs[j] = MAX(newlbs[j], (breakpoints[i] * l1 + (1 - breakpoints[i]) * l2 + coef * ubs[idx]) / coef);
604 else if( SCIPisInfinity(scip, ubs[idx]) )
605 newlbs[j] = MAX(newlbs[j], (breakpoints[i] * l1 + (1 - breakpoints[i]) * l2) / coef);
606 }
607 else if ( signs[idx] == NEG || signs[idx] == UP )
608 {
609 if( ninfs == 0 )
610 newubs[j] = MIN(newubs[j], (breakpoints[i] * l1 + (1 - breakpoints[i]) * l2 + coef * lbs[idx]) / coef);
611 else if( SCIPisInfinity(scip, -lbs[idx]) )
612 newubs[j] = MIN(newubs[j], (breakpoints[i] * l1 + (1 - breakpoints[i]) * l2) / coef);
613 }
614#ifdef SCIP_MORE_DEBUG
615 if( !SCIPisEQ(scip, oldlb, newlbs[j]) || !SCIPisEQ(scip, oldub, newubs[j]) )
616 SCIPdebugMsg(scip, "%g <= %g <= var_%d <= %g <= %g\n", oldlb, newlbs[j], j, newubs[j], oldub);
617#endif
618 }
619 }
620
621 i += shift;
622 ninfs += nnewinfs;
623 l1 += l1update;
624 l2 += l2update;
625 }
626
627 /* check infinities in first row */
628 ninfs = 0;
629 for( i = 0; i < nvars; i++ )
630 {
631 idx = varinds[i];
632 if( (SCIPisPositive(scip, row1coefs[idx]) && SCIPisInfinity(scip, ubs[idx]))
633 || (SCIPisNegative(scip, row1coefs[idx]) && SCIPisInfinity(scip, -lbs[idx])) )
634 ninfs++;
635 }
636
637 /* calculate bounds for lambda = 1 */
638#ifdef SCIP_MORE_DEBUG
639 SCIPdebugMsg(scip, "lambda = 1, l1 = %g, l2 = %g, ninfs = %d\n", i, breakpoints[i], l1, l2, ninfs);
640#endif
641 if( ninfs <= 1 )
642 {
643#ifdef SCIP_MORE_DEBUG
644 SCIP_Real oldlb;
645 SCIP_Real oldub;
646#endif
647 for( i = 0; i < nvars; i++ )
648 {
649#ifdef SCIP_MORE_DEBUG
650 oldlb = newlbs[i];
651 oldub = newubs[i];
652#endif
653 idx = varinds[i];
654 if( SCIPisPositive(scip, row1coefs[idx]) )
655 {
656 if( ninfs == 0 )
657 newlbs[i] = MAX(newlbs[i], (l1 + row1coefs[idx] * ubs[idx]) / row1coefs[idx]);
658 else if( SCIPisInfinity(scip, ubs[idx]) )
659 newlbs[i] = MAX(newlbs[i], l1 / row1coefs[idx]);
660 }
661 else if ( SCIPisNegative(scip, row1coefs[idx]) )
662 {
663 if( ninfs == 0 )
664 newubs[i] = MIN(newubs[i], (l1 + row1coefs[idx] * lbs[idx]) / row1coefs[idx]);
665 else if( SCIPisInfinity(scip, -lbs[idx]) )
666 newubs[i] = MIN(newubs[i], l1 / row1coefs[idx]);
667 }
668#ifdef SCIP_MORE_DEBUG
669 if( !SCIPisEQ(scip, oldlb, newlbs[i]) || !SCIPisEQ(scip, oldub, newubs[i]) )
670 SCIPdebugMsg(scip, "%g <= %g <= var_%i <= %g <= %g\n", oldlb, newlbs[i], i, newubs[i], oldub);
671#endif
672 }
673 }
674
675 /* update bound arrays and determine success */
676 for( i = 0; i < nvars; i++ )
677 {
678 idx = varinds[i];
679
680 assert(SCIPisLE(scip, lbs[idx], newlbs[i]));
681 assert(SCIPisGE(scip, ubs[idx], newubs[i]));
682
683 if( SCIPisGT(scip, newlbs[i], lbs[idx]) || SCIPisLT(scip, newubs[i], ubs[idx]) )
684 {
685 (*success) = TRUE;
686
687 lbs[idx] = newlbs[i];
688 ubs[idx] = newubs[i];
689 }
690 }
691 SCIPfreeBufferArray(scip, &newubs);
692 SCIPfreeBufferArray(scip, &newlbs);
693 }
694
695 SCIPfreeBufferArray(scip, &breakpoints);
696 SCIPfreeBufferArray(scip, &signs);
697 SCIPfreeBufferArray(scip, &varinds);
698 SCIPfreeBufferArray(scip, &row2coefs);
699 SCIPfreeBufferArray(scip, &row1coefs);
700
701 return SCIP_OKAY;
702}
703
704/** get minimal and maximal residual activities without one specific column */
705static
706void getMinMaxActivityResiduals(
707 SCIP* scip, /**< SCIP main data structure */
708 SCIP_MATRIX* matrix, /**< matrix containing the constraints */
709 int withoutcol, /**< exclude this column index */
710 int row, /**< row index */
711 SCIP_Real* lbs, /**< lower bounds */
712 SCIP_Real* ubs, /**< upper bounds */
713 SCIP_Real* minresactivity, /**< minimum residual activity of this row */
714 SCIP_Real* maxresactivity, /**< maximum residual activity of this row */
715 SCIP_Bool* isminsettoinfinity, /**< flag indicating if minresactiviy is set to infinity */
716 SCIP_Bool* ismaxsettoinfinity /**< flag indicating if maxresactiviy is set to infinity */
717 )
718{
719 SCIP_Real coef;
720 int* rowpnt;
721 int* rowend;
722 SCIP_Real* valpnt;
723 int nmaxactneginf;
724 int nmaxactposinf;
725 int nminactneginf;
726 int nminactposinf;
727 SCIP_Real maxresact;
728 SCIP_Real minresact;
729 int col;
730
731 assert(scip != NULL);
732 assert(matrix != NULL);
733 assert(minresactivity != NULL);
734 assert(maxresactivity != NULL);
735 assert(isminsettoinfinity != NULL);
736 assert(ismaxsettoinfinity != NULL);
737
738 *isminsettoinfinity = FALSE;
739 *ismaxsettoinfinity = FALSE;
740
741 nmaxactneginf = 0;
742 nmaxactposinf = 0;
743 nminactneginf = 0;
744 nminactposinf = 0;
745 maxresact = 0;
746 minresact = 0;
747
748 rowpnt = SCIPmatrixGetRowIdxPtr(matrix, row);
749 rowend = rowpnt + SCIPmatrixGetRowNNonzs(matrix, row);
750 valpnt = SCIPmatrixGetRowValPtr(matrix, row);
751
752 for( ; rowpnt < rowend; rowpnt++, valpnt++ )
753 {
754 col = *rowpnt;
755
756 if( col == withoutcol )
757 continue;
758
759 coef = *valpnt;
760
761 /* positive coefficient */
762 if( coef > 0.0 )
763 {
764 if( SCIPisInfinity(scip, ubs[col]) )
765 nmaxactposinf++;
766 else
767 maxresact += coef * ubs[col];
768
769 if( SCIPisInfinity(scip, -lbs[col]) )
770 nminactneginf++;
771 else
772 minresact += coef * lbs[col];
773 }
774 else /* negative coefficient */
775 {
776 if( SCIPisInfinity(scip, -lbs[col]) )
777 nmaxactneginf++;
778 else
779 maxresact += coef * lbs[col];
780
781 if( SCIPisInfinity(scip, ubs[col]) )
782 nminactposinf++;
783 else
784 minresact += coef * ubs[col];
785 }
786 }
787
788 if( (nmaxactneginf + nmaxactposinf) > 0 )
789 *ismaxsettoinfinity = TRUE;
790 else
791 *maxresactivity = maxresact;
792
793 if( (nminactneginf + nminactposinf) > 0 )
794 *isminsettoinfinity = TRUE;
795 else
796 *minresactivity = minresact;
797}
798
799/** calculate the upper and lower bound of one variable from one row */
800static
801void getVarBoundsOfRow(
802 SCIP* scip, /**< SCIP main data structure */
803 SCIP_MATRIX* matrix, /**< matrix containing the constraints */
804 int col, /**< column index of variable */
805 int row, /**< row index */
806 SCIP_Real val, /**< coefficient of this column in this row */
807 SCIP_Real* lbs, /**< lower bounds */
808 SCIP_Real* ubs, /**< upper bounds */
809 SCIP_Real* rowub, /**< upper bound of row */
810 SCIP_Bool* ubfound, /**< flag indicating that an upper bound was calculated */
811 SCIP_Real* rowlb, /**< lower bound of row */
812 SCIP_Bool* lbfound /**< flag indicating that a lower bound was caluclated */
813 )
814{
815 SCIP_Bool isminsettoinfinity;
816 SCIP_Bool ismaxsettoinfinity;
817 SCIP_Real minresactivity;
818 SCIP_Real maxresactivity;
819 SCIP_Real lhs;
820 SCIP_Real rhs;
821
822 assert(rowub != NULL);
823 assert(ubfound != NULL);
824 assert(rowlb != NULL);
825 assert(lbfound != NULL);
826
827 *rowub = SCIPinfinity(scip);
828 *ubfound = FALSE;
829 *rowlb = -SCIPinfinity(scip);
830 *lbfound = FALSE;
831
832 getMinMaxActivityResiduals(scip, matrix, col, row, lbs, ubs,
833 &minresactivity, &maxresactivity,
834 &isminsettoinfinity, &ismaxsettoinfinity);
835
836 lhs = SCIPmatrixGetRowLhs(matrix, row);
837 rhs = SCIPmatrixGetRowRhs(matrix, row);
838
839 if( val > 0.0 )
840 {
841 if( !isminsettoinfinity && !SCIPisInfinity(scip, rhs) )
842 {
843 *rowub = (rhs - minresactivity) / val; // maybe one wants some kind of numerical guard of check that values is not too small for all these
844 *ubfound = TRUE;
845 }
846
847 if( !ismaxsettoinfinity && !SCIPisInfinity(scip, -lhs) )
848 {
849 *rowlb = (lhs - maxresactivity) / val;
850 *lbfound = TRUE;
851 }
852 }
853 else
854 {
855 if( !ismaxsettoinfinity && !SCIPisInfinity(scip, -lhs) )
856 {
857 *rowub = (lhs - maxresactivity) / val;
858 *ubfound = TRUE;
859 }
860
861 if( !isminsettoinfinity && !SCIPisInfinity(scip, rhs) )
862 {
863 *rowlb = (rhs - minresactivity) / val;
864 *lbfound = TRUE;
865 }
866 }
867}
868
869
870/** detect implied variable bounds */
871static
872void getImpliedBounds(
873 SCIP* scip, /**< SCIP main data structure */
874 SCIP_MATRIX* matrix, /**< matrix containing the constraints */
875 int col, /**< column index for implied free test */
876 SCIP_Real* lbs, /**< lower bounds */
877 SCIP_Real* ubs, /**< upper bounds */
878 SCIP_Bool* ubimplied, /**< flag indicating an implied upper bound */
879 SCIP_Bool* lbimplied /**< flag indicating an implied lower bound */
880 )
881{
882 SCIP_Real impliedub;
883 SCIP_Real impliedlb;
884 int* colpnt;
885 int* colend;
886 SCIP_Real* valpnt;
887
888 assert(scip != NULL);
889 assert(matrix != NULL);
890 assert(lbs != NULL);
891 assert(ubs != NULL);
892 assert(ubimplied != NULL);
893 assert(lbimplied != NULL);
894
895 *ubimplied = FALSE;
896 impliedub = SCIPinfinity(scip);
897
898 *lbimplied = FALSE;
899 impliedlb = -SCIPinfinity(scip);
900
901 colpnt = SCIPmatrixGetColIdxPtr(matrix, col);
902 colend = colpnt + SCIPmatrixGetColNNonzs(matrix, col);
903 valpnt = SCIPmatrixGetColValPtr(matrix, col);
904 for( ; (colpnt < colend); colpnt++, valpnt++ )
905 {
906 SCIP_Real rowub;
907 SCIP_Bool ubfound;
908 SCIP_Real rowlb;
909 SCIP_Bool lbfound;
910
911 getVarBoundsOfRow(scip, matrix, col, *colpnt, *valpnt, lbs, ubs,
912 &rowub, &ubfound, &rowlb, &lbfound);
913
914 if( ubfound && (rowub < impliedub) )
915 impliedub = rowub;
916
917 if( lbfound && (rowlb > impliedlb) )
918 impliedlb = rowlb;
919 }
920
921 /* we consider +/-inf bounds as implied bounds */
922 if( SCIPisInfinity(scip, ubs[col]) ||
923 (!SCIPisInfinity(scip, ubs[col]) && SCIPisLE(scip, impliedub, ubs[col])) )
924 *ubimplied = TRUE;
925
926 if( SCIPisInfinity(scip, -lbs[col]) ||
927 (!SCIPisInfinity(scip, -lbs[col]) && SCIPisGE(scip, impliedlb, lbs[col])) )
928 *lbimplied = TRUE;
929}
930
931
932/** calculate minimal column activity from one variable without one row */
933static
934SCIP_Real getMinColActWithoutRow(
935 SCIP* scip, /**< SCIP main data structure */
936 SCIP_MATRIX* matrix, /**< matrix containing the constraints */
937 int col, /**< column index */
938 int withoutrow, /**< exclude this row index */
939 SCIP_Real* lbdual, /**< lower bounds of dual variables */
940 SCIP_Real* ubdual /**< upper bounds of dual variables */
941 )
942{
943 SCIP_Real* valpnt;
944 int* colpnt;
945 int* colend;
946 SCIP_Real val;
947 SCIP_Real mincolactivity;
948 int row;
949
950 assert(scip != NULL);
951 assert(matrix != NULL);
952 assert(lbdual != NULL);
953 assert(ubdual != NULL);
954
955 mincolactivity = 0;
956
957 colpnt = SCIPmatrixGetColIdxPtr(matrix, col);
958 colend = colpnt + SCIPmatrixGetColNNonzs(matrix, col);
959 valpnt = SCIPmatrixGetColValPtr(matrix, col);
960
961 for( ; colpnt < colend; colpnt++, valpnt++ )
962 {
963 row = *colpnt;
964 val = *valpnt;
965
966 if( row == withoutrow )
967 continue;
968
969 if( val > 0.0 )
970 {
971 assert(!SCIPisInfinity(scip, -lbdual[row]));
972 mincolactivity += val * lbdual[row];
973 }
974 else if( val < 0.0 )
975 {
976 assert(!SCIPisInfinity(scip, ubdual[row]));
977 mincolactivity += val * ubdual[row];
978 }
979 }
980
981 return mincolactivity;
982}
983
984
985/** In the primal the residual activity of a constraint w.r.t. a variable is the activity of the constraint without the variable.
986 * This function does the same but in the dual.
987 * It computes the residual activity of column 'col' w.r.t. variable 'row'
988 */
989static
990void calcMinColActResidual(
991 SCIP* scip, /**< SCIP main data structure */
992 SCIP_MATRIX* matrix, /**< matrix containing the constraints */
993 int col, /**< column index */
994 int row, /**< row index */
995 SCIP_Real val, /**< matrix coefficient */
996 SCIP_Real* lbdual, /**< lower bounds of the dual variables */
997 SCIP_Real* ubdual, /**< upper bounds of the dual variables */
998 const SCIP_Real* mincolact, /**< minimal column activities */
999 const int* mincolactinf, /**< number of infinite contributions to minimal column activity */
1000 SCIP_Real* mincolresact /**< minimal residual column activity */
1001 )
1002{
1003 assert(scip != NULL);
1004 assert(matrix != NULL);
1005 assert(lbdual != NULL);
1006 assert(ubdual != NULL);
1007 assert(mincolact != NULL);
1008 assert(mincolactinf != NULL);
1009 assert(mincolresact != NULL);
1010
1011 *mincolresact = -SCIPinfinity(scip);
1012
1013 if( val > 0.0 )
1014 {
1015 if( SCIPisInfinity(scip, -lbdual[row]) )
1016 {
1017 assert(mincolactinf[col] >= 1);
1018 if( mincolactinf[col] == 1 )
1019 *mincolresact = getMinColActWithoutRow(scip, matrix, col, row, lbdual, ubdual);
1020 else
1021 *mincolresact = -SCIPinfinity(scip);
1022 }
1023 else
1024 {
1025 if( mincolactinf[col] > 0 )
1026 *mincolresact = -SCIPinfinity(scip);
1027 else
1028 *mincolresact = mincolact[col] - val * lbdual[row];
1029 }
1030 }
1031 else if( val < 0.0 )
1032 {
1033 if( SCIPisInfinity(scip, ubdual[row]) )
1034 {
1035 assert(mincolactinf[col] >= 1);
1036 if( mincolactinf[col] == 1 )
1037 *mincolresact = getMinColActWithoutRow(scip, matrix, col, row, lbdual, ubdual);
1038 else
1039 *mincolresact = -SCIPinfinity(scip);
1040 }
1041 else
1042 {
1043 if( mincolactinf[col] > 0 )
1044 *mincolresact = -SCIPinfinity(scip);
1045 else
1046 *mincolresact = mincolact[col] - val * ubdual[row];
1047 }
1048 }
1049}
1050
1051/** calculate minimal column activity of one column */
1052static
1053void calcMinColActivity(
1054 SCIP* scip, /**< SCIP main data structure */
1055 SCIP_MATRIX* matrix, /**< matrix containing the constraints */
1056 int col, /**< column for activity calculations */
1057 SCIP_Real* lbdual, /**< lower bounds of dual variables */
1058 SCIP_Real* ubdual, /**< upper bounds of dual variables */
1059 SCIP_Real* mincolact, /**< minimal column activities */
1060 int* mincolactinf /**< number of -inf contributions to minimal column activity */
1061 )
1062{
1063 SCIP_Real* valpnt;
1064 int* colpnt;
1065 int* colend;
1066 SCIP_Real val;
1067 int row;
1068
1069 assert(scip != NULL);
1070 assert(matrix != NULL);
1071 assert(lbdual != NULL);
1072 assert(ubdual != NULL);
1073 assert(mincolact != NULL);
1074 assert(mincolactinf != NULL);
1075
1076 /* init activities */
1077 mincolact[col] = 0.0;
1078 mincolactinf[col] = 0;
1079
1080 colpnt = SCIPmatrixGetColIdxPtr(matrix, col);
1081 colend = colpnt + SCIPmatrixGetColNNonzs(matrix, col);
1082 valpnt = SCIPmatrixGetColValPtr(matrix, col);
1083
1084 /* calculate column activities */
1085 for( ; colpnt < colend; colpnt++, valpnt++ )
1086 {
1087 row = *colpnt;
1088 val = *valpnt;
1089
1090 if( val > 0.0 )
1091 {
1092 if(SCIPisInfinity(scip, -lbdual[row]))
1093 mincolactinf[col]++;
1094 else
1095 mincolact[col] += val * lbdual[row];
1096 }
1097 else if( val < 0.0 )
1098 {
1099 if(SCIPisInfinity(scip, ubdual[row]))
1100 mincolactinf[col]++;
1101 else
1102 mincolact[col] += val * ubdual[row];
1103 }
1104 }
1105
1106 /* update column activities if infinity counters are greater 0 */
1107 if( mincolactinf[col] > 0 )
1108 mincolact[col] = -SCIPinfinity(scip);
1109}
1110
1111/** calculate maximal column activity of one column */
1112static
1113void calcMaxColActivity(
1114 SCIP* scip, /**< SCIP main data structure */
1115 SCIP_MATRIX* matrix, /**< matrix containing the constraints */
1116 int col, /**< column for activity calculations */
1117 SCIP_Real* lbdual, /**< lower bounds of dual variables */
1118 SCIP_Real* ubdual, /**< upper bounds of dual variables */
1119 SCIP_Real* maxcolact, /**< minimal column activities */
1120 int* maxcolactinf /**< number of -inf contributions to minimal column activity */
1121 )
1122{
1123 SCIP_Real* valpnt;
1124 int* colpnt;
1125 int* colend;
1126 SCIP_Real val;
1127 int row;
1128
1129 assert(scip != NULL);
1130 assert(matrix != NULL);
1131 assert(lbdual != NULL);
1132 assert(ubdual != NULL);
1133 assert(maxcolact != NULL);
1134 assert(maxcolactinf != NULL);
1135
1136 /* init activities */
1137 maxcolact[col] = 0.0;
1138 maxcolactinf[col] = 0;
1139
1140 colpnt = SCIPmatrixGetColIdxPtr(matrix, col);
1141 colend = colpnt + SCIPmatrixGetColNNonzs(matrix, col);
1142 valpnt = SCIPmatrixGetColValPtr(matrix, col);
1143
1144 /* calculate column activities */
1145 for( ; colpnt < colend; colpnt++, valpnt++ )
1146 {
1147 row = *colpnt;
1148 val = *valpnt;
1149
1150 if( val > 0.0 )
1151 {
1152 if(SCIPisInfinity(scip, ubdual[row]))
1153 maxcolactinf[col]++;
1154 else
1155 maxcolact[col] += val * ubdual[row];
1156 }
1157 else if( val < 0.0 )
1158 {
1159 if(SCIPisInfinity(scip, -lbdual[row]))
1160 maxcolactinf[col]++;
1161 else
1162 maxcolact[col] += val * lbdual[row];
1163 }
1164 }
1165
1166 /* update column activities if infinity counters are greater 0 */
1167 if( maxcolactinf[col] > 0 )
1168 maxcolact[col] = SCIPinfinity(scip);
1169}
1170
1171
1172/** update minimal/maximal column activity infinity counters */
1173static
1174void infinityCountUpdate(
1175 SCIP* scip, /**< SCIP main data structure */
1176 SCIP_MATRIX* matrix, /**< matrix containing the constraints */
1177 int row, /**< row index */
1178 SCIP_Real* lbdual, /**< lower bounds of dual variables */
1179 SCIP_Real* ubdual, /**< upper bounds of dual variables */
1180 const SCIP_Bool* isubimplied, /**< flags indicating of the upper bound is implied */
1181 SCIP_Real* mincolact, /**< minimal column activities */
1182 int* mincolactinf, /**< number of infinity contributions to minimal column activity */
1183 SCIP_Bool ubinfchange, /**< flag indicating if the upper bound has changed from infinity to a finite value */
1184 SCIP_Bool lbinfchange /**< flag indicating if the lower bound has changed from -infinity to a finite value */
1185 )
1186{
1187 SCIP_Real* valpnt;
1188 int* rowpnt;
1189 int* rowend;
1190 SCIP_Real val;
1191 int col;
1192
1193 rowpnt = SCIPmatrixGetRowIdxPtr(matrix, row);
1194 rowend = rowpnt + SCIPmatrixGetRowNNonzs(matrix, row);
1195 valpnt = SCIPmatrixGetRowValPtr(matrix, row);
1196
1197 /* look at all column entries present within row and update the
1198 * corresponding infinity counters. if one counter gets to zero,
1199 * then calculate this column activity new.
1200 */
1201
1202 for(; (rowpnt < rowend); rowpnt++, valpnt++ )
1203 {
1204 col = *rowpnt;
1205 val = *valpnt;
1206
1207 if( isubimplied[col] )
1208 {
1209 if( val < 0 )
1210 {
1211 if( ubinfchange )
1212 {
1213 assert(mincolactinf[col] > 0);
1214 mincolactinf[col]--;
1215 }
1216 }
1217 else if( val > 0 )
1218 {
1219 if( lbinfchange )
1220 {
1221 assert(mincolactinf[col] > 0);
1222 mincolactinf[col]--;
1223 }
1224 }
1225
1226 if( mincolactinf[col] == 0 )
1227 calcMinColActivity(scip, matrix, col, lbdual, ubdual, mincolact, mincolactinf);
1228 }
1229 }
1230}
1231
1232#ifdef SCIP_DEBUG
1233/** use LP calculations for determining the best dual variable bounds from a specific row index */
1234static
1235SCIP_RETCODE determineBestBounds(
1236 SCIP* scip, /**< SCIP main data structure */
1237 SCIP_MATRIX* matrix, /**< matrix containing the constraints */
1238 int row, /**< row index for dual bound calculations */
1239 SCIP_Bool solveLP, /**< flag indicating to solve subscip LP */
1240 SCIP_Real* lowerbnddual, /**< lower bound of dual variable */
1241 SCIP_Real* upperbnddual /**< upper bound of dual variable */
1242 )
1243{
1244 int i;
1245 int nrows;
1246 int ncols;
1247 int numberconvars;
1248 SCIP_VAR* var;
1249 SCIP_VAR** variables;
1250 SCIP_VAR** tmpvars;
1251 SCIP_Real* tmpcoef;
1252 SCIP_CONS** constraints;
1253 int numDualVars;
1254 SCIP* subscip;
1255 SCIP_RETCODE retcode;
1256 char name[SCIP_MAXSTRLEN+3];
1257 int fillcnt;
1258 int* colpnt;
1259 int* colend;
1260 SCIP_Real* valpnt;
1261 int* colmap;
1262
1263 *lowerbnddual = -SCIPinfinity(scip);
1264 *upperbnddual = SCIPinfinity(scip);
1265
1266 nrows = SCIPmatrixGetNRows(matrix);
1267 assert(0 <= row && row < nrows);
1268 ncols = SCIPmatrixGetNColumns(matrix);
1269
1270 SCIP_CALL( SCIPcreate(&subscip) );
1271 SCIP_CALL( SCIPcreateProbBasic(subscip, "subscip") );
1272 SCIP_CALL( SCIPincludeDefaultPlugins(subscip) );
1273
1274 /* avoid recursive calls */
1275 SCIP_CALL( SCIPsetIntParam(subscip, "presolving/dualinfer/maxrounds", 0) );
1276 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
1277 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", TRUE) );
1278
1279 SCIP_CALL( SCIPallocBufferArray(scip, &colmap, ncols) );
1280 numberconvars = 0;
1281 for(i = 0; i < ncols; i++)
1282 {
1283 var = SCIPmatrixGetVar(matrix, i);
1284 if( !SCIPvarIsNonimpliedIntegral(var) )
1285 {
1286 colmap[i] = numberconvars; /* start numbering with 0 */
1287 numberconvars++;
1288 }
1289 else
1290 colmap[i] = -1;
1291 }
1292 numDualVars = nrows + 2 * numberconvars;
1293
1294 /* create dual variables */
1295 SCIP_CALL( SCIPallocBufferArray(scip, &variables, numDualVars) );
1296 for( i = 0; i < nrows; i++ )
1297 {
1298 variables[i] = NULL;
1299 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "y%d", i);
1300 if( !SCIPmatrixIsRowRhsInfinity(matrix, i ) )
1301 {
1302 /* dual variable for equation or ranged row */
1303 SCIP_CALL( SCIPcreateVarBasic(subscip, &variables[i], name,
1304 -SCIPinfinity(scip), SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
1305 }
1306 else
1307 {
1308 /* dual variable for >= inequality */
1309 SCIP_CALL( SCIPcreateVarBasic(subscip, &variables[i], name,
1310 0.0, SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
1311 }
1312 SCIP_CALL( SCIPaddVar(subscip, variables[i]) );
1313 assert( variables[i] != NULL );
1314 }
1315
1316 /* in addition, we introduce dual variables for the bounds,
1317 because we treat each continuous variable as a free variable */
1318 fillcnt = nrows;
1319 for( i = 0; i < numberconvars; i++ )
1320 {
1321 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "ylb%d", fillcnt);
1322 SCIP_CALL( SCIPcreateVarBasic(subscip, &variables[fillcnt], name,
1323 0.0, SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
1324 SCIP_CALL( SCIPaddVar(subscip, variables[fillcnt]) );
1325 assert( variables[fillcnt] != NULL );
1326 fillcnt++;
1327
1328 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "yub%d", fillcnt);
1329 SCIP_CALL( SCIPcreateVarBasic(subscip, &variables[fillcnt], name,
1330 0.0, SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
1331 SCIP_CALL( SCIPaddVar(subscip, variables[fillcnt]) );
1332 assert( variables[fillcnt] != NULL );
1333 fillcnt++;
1334 }
1335 assert(numDualVars == fillcnt);
1336
1337 SCIP_CALL( SCIPallocBufferArray(scip, &tmpvars, numDualVars) );
1338 SCIP_CALL( SCIPallocBufferArray(scip, &tmpcoef, numDualVars) );
1339
1340 SCIP_CALL( SCIPallocBufferArray(scip, &constraints, numberconvars) );
1341 for( i = 0; i <numberconvars; i++)
1342 constraints[i] = NULL;
1343
1344 for(i = 0; i < ncols; i++)
1345 {
1346 var = SCIPmatrixGetVar(matrix, i);
1347 if( !SCIPvarIsNonimpliedIntegral(var) )
1348 {
1349 SCIP_Real objval = SCIPvarGetObj(var);
1350 int cidx = colmap[i];
1351 assert(0 <= cidx && cidx < numberconvars);
1352
1353 colpnt = SCIPmatrixGetColIdxPtr(matrix, i);
1354 colend = colpnt + SCIPmatrixGetColNNonzs(matrix, i);
1355 valpnt = SCIPmatrixGetColValPtr(matrix, i);
1356 fillcnt = 0;
1357 for( ; colpnt < colend; colpnt++, valpnt++ )
1358 {
1359 assert(0 <= *colpnt && *colpnt < nrows);
1360 assert(variables[*colpnt] != NULL);
1361 tmpvars[fillcnt] = variables[*colpnt];
1362 tmpcoef[fillcnt] = *valpnt;
1363 fillcnt++;
1364 }
1365
1366 /* consider dual variable for a lower bound */
1367 if(SCIPisGT(scip, SCIPvarGetLbGlobal(var), -SCIPinfinity(scip)))
1368 {
1369 assert(variables[nrows + 2 * cidx] != NULL);
1370 tmpvars[fillcnt] = variables[nrows + 2 * cidx];
1371 tmpcoef[fillcnt] = 1.0;
1372 fillcnt++;
1373 }
1374
1375 /* consider dual variable for an upper bound */
1376 if(SCIPisLT(scip, SCIPvarGetUbGlobal(var), SCIPinfinity(scip)))
1377 {
1378 assert(variables[nrows + 2 * cidx + 1] != NULL);
1379 tmpvars[fillcnt] = variables[nrows + 2 * cidx + 1];
1380 tmpcoef[fillcnt] = -1.0;
1381 fillcnt++;
1382 }
1383
1384 /* because we treat the continuous columns as free variable,
1385 we need here an equality */
1386 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "c%d", cidx);
1387 SCIP_CALL( SCIPcreateConsBasicLinear(subscip, &constraints[cidx], name,
1388 fillcnt, tmpvars, tmpcoef, objval, objval) );
1389 SCIP_CALL( SCIPaddCons(subscip, constraints[cidx]) );
1390 }
1391 }
1392
1393 /* determine lower dual bound via a minimization problem */
1394 SCIP_CALL( SCIPsetObjsense(subscip,SCIP_OBJSENSE_MINIMIZE) );
1395 SCIP_CALL( SCIPchgVarObj(subscip, variables[row], 1.0) );
1396 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "dbg_min_%s.lp", SCIPvarGetName(variables[row]));
1397 SCIP_CALL( SCIPwriteOrigProblem(subscip, name, "lp", FALSE) );
1398 if( solveLP )
1399 {
1400 retcode = SCIPsolve(subscip);
1401 if( retcode != SCIP_OKAY )
1402 SCIPwarningMessage(scip, "Error subscip: <%d>\n", retcode);
1403 else
1404 {
1405 if( SCIPgetStatus(subscip) == SCIP_STATUS_OPTIMAL )
1406 {
1407 SCIP_SOL* sol;
1408 SCIP_Bool feasible;
1409 sol = SCIPgetBestSol(subscip);
1410 SCIP_CALL( SCIPcheckSolOrig(subscip, sol, &feasible, TRUE, TRUE) );
1411
1412 if(feasible)
1413 *lowerbnddual = SCIPgetSolOrigObj(subscip, sol);
1414 }
1415 }
1416 SCIP_CALL( SCIPfreeTransform(subscip) );
1417 }
1418
1419 /* determine upper dual bound via a maximization problem */
1420 SCIP_CALL( SCIPsetObjsense(subscip,SCIP_OBJSENSE_MAXIMIZE) );
1421 SCIP_CALL( SCIPchgVarObj(subscip, variables[row], 1.0) );
1422 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "dbg_max_%s.lp", SCIPvarGetName(variables[row]));
1423 SCIP_CALL( SCIPwriteOrigProblem(subscip, name, "lp", FALSE) );
1424 if( solveLP )
1425 {
1426 retcode = SCIPsolve(subscip);
1427 if( retcode != SCIP_OKAY )
1428 SCIPwarningMessage(scip, "Error subscip: <%d>\n", retcode);
1429 else
1430 {
1431 if( SCIPgetStatus(subscip) == SCIP_STATUS_OPTIMAL )
1432 {
1433 SCIP_SOL* sol;
1434 SCIP_Bool feasible;
1435 sol = SCIPgetBestSol(subscip);
1436 SCIP_CALL( SCIPcheckSolOrig(subscip, sol, &feasible, TRUE, TRUE) );
1437
1438 if(feasible)
1439 *upperbnddual = SCIPgetSolOrigObj(subscip, sol);
1440 }
1441 }
1442 SCIP_CALL( SCIPfreeTransform(subscip) );
1443 }
1444
1445 /* release variables and constraints */
1446 for( i = 0; i < numDualVars; i++ )
1447 {
1448 if(variables[i] != NULL)
1449 SCIP_CALL( SCIPreleaseVar(subscip, &variables[i]) );
1450 }
1451 for( i = 0; i < numberconvars; i++ )
1452 {
1453 if(constraints[i] != NULL)
1454 SCIP_CALL( SCIPreleaseCons(subscip, &constraints[i]) );
1455 }
1456
1457 SCIPfreeBufferArray(scip, &constraints);
1458 SCIPfreeBufferArray(scip, &tmpcoef);
1459 SCIPfreeBufferArray(scip, &tmpvars);
1460 SCIPfreeBufferArray(scip, &variables);
1461 SCIP_CALL( SCIPfree(&subscip) );
1462 SCIPfreeBufferArray(scip, &colmap);
1463
1464 return SCIP_OKAY;
1465}
1466#endif
1467
1468/** update bounds of the dual variables */
1469static
1470void updateDualBounds(
1471 SCIP* scip, /**< SCIP main data structure */
1472 SCIP_MATRIX* matrix, /**< matrix containing the constraints */
1473 SCIP_Real objval, /**< objective function value */
1474 SCIP_Real val, /**< matrix coefficient */
1475 int row, /**< row index */
1476 SCIP_Real mincolresact, /**< minimal column residual activity */
1477 SCIP_Real* lbdual, /**< dual lower bounds */
1478 SCIP_Real* ubdual, /**< dual upper bounds */
1479 int* boundchanges, /**< counter for the number of bound changes */
1480 SCIP_Bool* ubinfchange, /**< flag indicating an upper bound change from infinite to finite */
1481 SCIP_Bool* lbinfchange /**< flag indicating a lower bound change from infinite to finite */
1482 )
1483{
1484 SCIP_Real newlbdual;
1485 SCIP_Real newubdual;
1486
1487 assert(scip != NULL);
1488 assert(matrix != NULL);
1489 assert(lbdual != NULL);
1490 assert(ubdual != NULL);
1491 assert(boundchanges != NULL);
1492 assert(ubinfchange != NULL);
1493 assert(lbinfchange != NULL);
1494
1495 *ubinfchange = FALSE;
1496 *lbinfchange = FALSE;
1497
1498 if( !SCIPisInfinity(scip, -mincolresact) )
1499 {
1500 if( val > 0 )
1501 {
1502 newubdual = (objval - mincolresact) / val;
1503
1504 if( newubdual < ubdual[row] )
1505 {
1506 /* accept the new upper bound only if the numerics are reliable */
1507 if( SCIPisLE(scip,lbdual[row],newubdual) )
1508 {
1509 if( SCIPisInfinity(scip, ubdual[row]) )
1510 *ubinfchange = TRUE;
1511
1512 ubdual[row] = newubdual;
1513 (*boundchanges)++;
1514 }
1515 }
1516 }
1517 else if( val < 0 )
1518 {
1519 newlbdual = (objval - mincolresact) / val;
1520
1521 if( newlbdual > lbdual[row] )
1522 {
1523 /* accept the new lower bound only if the numerics are reliable */
1524 if( SCIPisLE(scip,newlbdual,ubdual[row]) )
1525 {
1526 if( SCIPisInfinity(scip, -lbdual[row]) )
1527 *lbinfchange = TRUE;
1528
1529 lbdual[row] = newlbdual;
1530 (*boundchanges)++;
1531 }
1532 }
1533 }
1534 }
1535}
1536
1537/** dual bound strengthening */
1538static
1539SCIP_RETCODE dualBoundStrengthening(
1540 SCIP* scip, /**< SCIP main data structure */
1541 SCIP_MATRIX* matrix, /**< matrix containing the constraints */
1542 SCIP_PRESOLDATA* presoldata, /**< presolver data structure */
1543 FIXINGDIRECTION* varstofix, /**< array holding information for later upper/lower bound fixing */
1544 int* npossiblefixings, /**< number of possible fixings */
1545 SIDECHANGE* sidestochange, /**< array holding if this is an implied equality */
1546 int* npossiblesidechanges/**< number of possible equality changes */
1547 )
1548{
1549 SCIP_Real* lbdual;
1550 SCIP_Real* ubdual;
1551 SCIP_Real* mincolact;
1552 int* mincolactinf;
1553 SCIP_Real* maxcolact;
1554 int* maxcolactinf;
1555 int* colpnt;
1556 int* colend;
1557 SCIP_Real* valpnt;
1558 int boundchanges;
1559 int loops;
1560 int i;
1561 int j;
1562 int k;
1563 int nrows;
1564 int ncols;
1565 SCIP_Bool* isubimplied;
1566 SCIP_Bool* islbimplied;
1567 SCIP_Real* tmplbs;
1568 SCIP_Real* tmpubs;
1569 SCIP_VAR* var;
1570 int* implubvars;
1571 int nimplubvars;
1572
1573 SCIP_Longint maxhashes;
1574 int maxlen;
1575 int pospp;
1576 int listsizepp;
1577 int posmm;
1578 int listsizemm;
1579 int pospm;
1580 int listsizepm;
1581 int posmp;
1582 int listsizemp;
1583
1584 int* hashlistpp;
1585 int* hashlistmm;
1586 int* hashlistpm;
1587 int* hashlistmp;
1588
1589 int* colidxlistpp;
1590 int* colidxlistmm;
1591 int* colidxlistpm;
1592 int* colidxlistmp;
1593
1594 int block1start;
1595 int block1end;
1596 int block2start;
1597 int block2end;
1598
1599 SCIP_HASHSET* pairhashset;
1600 SCIP_Real* colvalptr;
1601 int* colidxptr;
1602
1603 assert(scip != NULL);
1604 assert(matrix != NULL);
1605 assert(varstofix != NULL);
1606 assert(npossiblefixings != NULL);
1607 assert(sidestochange != NULL);
1608 assert(npossiblesidechanges != NULL);
1609
1610 nrows = SCIPmatrixGetNRows(matrix);
1611 ncols = SCIPmatrixGetNColumns(matrix);
1612
1613 SCIP_CALL( SCIPallocBufferArray(scip, &tmplbs, ncols) );
1614 SCIP_CALL( SCIPallocBufferArray(scip, &tmpubs, ncols) );
1615 for( i = 0; i < ncols; i++ )
1616 {
1617 var = SCIPmatrixGetVar(matrix, i);
1618 tmplbs[i] = SCIPvarGetLbLocal(var);
1619 tmpubs[i] = SCIPvarGetUbLocal(var);
1620 }
1621
1622 /* verify which bounds of continuous variables are implied */
1623 SCIP_CALL( SCIPallocBufferArray(scip, &isubimplied, ncols) );
1624 SCIP_CALL( SCIPallocBufferArray(scip, &islbimplied, ncols) );
1625 SCIP_CALL( SCIPallocBufferArray(scip, &implubvars, ncols) );
1626 nimplubvars = 0;
1627 for( i = 0; i < ncols; i++ )
1628 {
1629 var = SCIPmatrixGetVar(matrix, i);
1630
1631 if( SCIPmatrixUplockConflict(matrix, i) || SCIPmatrixDownlockConflict(matrix, i)
1632 || SCIPvarIsNonimpliedIntegral(var) )
1633 {
1634 /* we don't care about integral variables or variables that have conflicting locks */
1635 isubimplied[i] = FALSE;
1636 islbimplied[i] = FALSE;
1637 }
1638 else
1639 {
1640 getImpliedBounds(scip, matrix, i, tmplbs, tmpubs, &(isubimplied[i]), &(islbimplied[i]));
1641
1642 /* if a continuous variable has a not implied upper bound we can
1643 * not use this variable (column) for propagating dual bounds.
1644 * not implied lowers bound can usually be treated.
1645 */
1646
1647 /* collect continuous variables with implied upper bound */
1648 if( isubimplied[i] )
1649 {
1650 implubvars[nimplubvars] = i;
1651 nimplubvars++;
1652
1653 /* reset implied bounds for further detections of other implied bounds */
1654 tmpubs[i] = SCIPinfinity(scip);
1655 }
1656
1657 if( islbimplied[i] )
1658 tmplbs[i] = -SCIPinfinity(scip);
1659 }
1660 }
1661
1662 /* initialize bounds of the dual variables */
1663 SCIP_CALL( SCIPallocBufferArray(scip, &lbdual, nrows) );
1664 SCIP_CALL( SCIPallocBufferArray(scip, &ubdual, nrows) );
1665 for( i = 0; i < nrows; i++ )
1666 {
1667 if( !SCIPmatrixIsRowRhsInfinity(matrix, i) )
1668 {
1669 /* dual free variable for equation or ranged row */
1670 lbdual[i] = -SCIPinfinity(scip);
1671 ubdual[i] = SCIPinfinity(scip);
1672 }
1673 else
1674 {
1675 /* dual variable for >= inequality */
1676 lbdual[i] = 0.0;
1677 ubdual[i] = SCIPinfinity(scip);
1678 }
1679 }
1680
1681 /* run convex combination on pairs of continuous variables (columns) using Belotti's algorithm */
1682 if( nimplubvars >= 2 && presoldata->usetwocolcombine )
1683 {
1684 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &hashlistpp, ncols) );
1685 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &hashlistmm, ncols) );
1686 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &hashlistpm, ncols) );
1687 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &hashlistmp, ncols) );
1688
1689 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &colidxlistpp, ncols) );
1690 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &colidxlistmm, ncols) );
1691 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &colidxlistpm, ncols) );
1692 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &colidxlistmp, ncols) );
1693
1694 pospp = 0;
1695 posmm = 0;
1696 pospm = 0;
1697 posmp = 0;
1698 listsizepp = ncols;
1699 listsizemm = ncols;
1700 listsizepm = ncols;
1701 listsizemp = ncols;
1702 maxhashes = presoldata->maxhashfac == -1 ? SCIP_LONGINT_MAX : (((SCIP_Longint)ncols) * presoldata->maxhashfac);
1703
1704 for( i = 0; i < nimplubvars; i++)
1705 {
1706 if( ((SCIP_Longint)pospp) + posmm + pospm + posmp > maxhashes )
1707 break;
1708
1709 colvalptr = SCIPmatrixGetColValPtr(matrix, implubvars[i]);
1710 colidxptr = SCIPmatrixGetColIdxPtr(matrix, implubvars[i]);
1711 maxlen = MIN(presoldata->maxconsiderednonzeros, SCIPmatrixGetColNNonzs(matrix, implubvars[i])); /*lint !e666*/
1712 for( j = 0; j < maxlen; j++)
1713 {
1714 for( k = j + 1; k < maxlen; k++)
1715 {
1716 if( SCIPisPositive(scip, colvalptr[j]) )
1717 {
1718 if(SCIPisPositive(scip, colvalptr[k]) )
1719 {
1720 SCIP_CALL( addEntry(scip, &pospp, &listsizepp, &hashlistpp, &colidxlistpp,
1721 hashIndexPair(colidxptr[j], colidxptr[k]), implubvars[i]) );
1722 }
1723 else
1724 {
1725 SCIP_CALL( addEntry(scip, &pospm, &listsizepm, &hashlistpm, &colidxlistpm,
1726 hashIndexPair(colidxptr[j], colidxptr[k]), implubvars[i]) );
1727 }
1728 }
1729 else
1730 {
1731 if(SCIPisPositive(scip, colvalptr[k]) )
1732 {
1733 SCIP_CALL( addEntry(scip, &posmp, &listsizemp, &hashlistmp, &colidxlistmp,
1734 hashIndexPair(colidxptr[j], colidxptr[k]), implubvars[i]) );
1735 }
1736 else
1737 {
1738 SCIP_CALL( addEntry(scip, &posmm, &listsizemm, &hashlistmm, &colidxlistmm,
1739 hashIndexPair(colidxptr[j], colidxptr[k]), implubvars[i]) );
1740 }
1741 }
1742 }
1743 }
1744 }
1745#ifdef SCIP_MORE_DEBUG
1746 SCIPdebugMsg(scip, "hashlist sizes: pp %d, mm %d, pm %d, mp %d \n", pospp, posmm, pospm, posmp);
1747#endif
1748 SCIPsortIntInt(hashlistpp, colidxlistpp, pospp);
1749 SCIPsortIntInt(hashlistmm, colidxlistmm, posmm);
1750 SCIPsortIntInt(hashlistpm, colidxlistpm, pospm);
1751 SCIPsortIntInt(hashlistmp, colidxlistmp, posmp);
1752
1753 SCIP_CALL( SCIPhashsetCreate(&pairhashset, SCIPblkmem(scip), 1) );
1754
1755 /* Process pp and mm lists */
1756 if( pospp > 0 && posmm > 0 )
1757 {
1758 SCIP_Longint ncombines;
1759 SCIP_Longint maxcombines;
1760 SCIP_Bool finished;
1761 SCIP_Bool success;
1762 int combinefails;
1763 int retrievefails;
1764 COLPAIR colpair;
1765
1766 finished = FALSE;
1767 block1start = 0;
1768 block1end = 0;
1769 block2start = 0;
1770 block2end = 0;
1771
1772 maxcombines = presoldata->maxpairfac == -1 ? SCIP_LONGINT_MAX : (((SCIP_Longint)ncols) * presoldata->maxpairfac);
1773
1774 ncombines = 0;
1775 combinefails = 0;
1776 retrievefails = 0;
1777 findNextBlock(hashlistpp, pospp, &block1start, &block1end);
1778 findNextBlock(hashlistmm, posmm, &block2start, &block2end);
1779#ifdef SCIP_MORE_DEBUG
1780 SCIPdebugMsg(scip, "processing pp and mm\n");
1781#endif
1782
1783 // same as in the rworowbnd presolver - both while loops to basically the same with one using pp and mm and the other pm and mp
1784 // I would write an additional function and remove the code duplication
1785 while( !finished )
1786 {
1787 if( hashlistpp[block1start] == hashlistmm[block2start] )
1788 {
1789 for( i = block1start; i < block1end; i++ )
1790 {
1791 for( j = block2start; j < block2end; j++ )
1792 {
1793 if( colidxlistpp[i] != colidxlistmm[j] )
1794 {
1795 colpair.col1idx = MIN(colidxlistpp[i], colidxlistmm[j]);
1796 colpair.col2idx = MAX(colidxlistpp[i], colidxlistmm[j]);
1797
1798 if( !SCIPhashsetExists(pairhashset, encodeColPair(&colpair)) )
1799 {
1800 int* colpnt1 = SCIPmatrixGetColIdxPtr(matrix, colpair.col1idx);
1801 SCIP_Real* valpnt1 = SCIPmatrixGetColValPtr(matrix, colpair.col1idx);
1802 int* colpnt2 = SCIPmatrixGetColIdxPtr(matrix, colpair.col2idx);
1803 SCIP_Real* valpnt2 = SCIPmatrixGetColValPtr(matrix, colpair.col2idx);
1804 SCIP_Real obj1 = SCIPvarGetObj(SCIPmatrixGetVar(matrix, colpair.col1idx));
1805 SCIP_Real obj2 = SCIPvarGetObj(SCIPmatrixGetVar(matrix, colpair.col2idx));
1806 int collen1 = SCIPmatrixGetColNNonzs(matrix, colpair.col1idx);
1807 int collen2 = SCIPmatrixGetColNNonzs(matrix, colpair.col2idx);
1808
1809 success = FALSE;
1810
1811 SCIP_CALL( combineCols(scip, colpnt1, colpnt2, valpnt1, valpnt2, obj1, obj2, collen1,
1812 collen2, nrows, TRUE, TRUE, lbdual, ubdual, &success) );
1813
1814 if( success )
1815 combinefails = 0;
1816 else
1817 combinefails++;
1818
1819 SCIP_CALL( SCIPhashsetInsert(pairhashset, SCIPblkmem(scip), encodeColPair(&colpair)) );
1820 ncombines++;
1821 if( ncombines >= maxcombines || combinefails >= presoldata->maxcombinefails )
1822 finished = TRUE;
1823#ifdef SCIP_MORE_DEBUG
1824 SCIPdebugMsg(scip, "pm/mp: %d retrievefails before reset, %d combines\n", retrievefails, ncombines);
1825#endif
1826 retrievefails = 0;
1827 }
1828 else if( retrievefails < presoldata->maxretrievefails )
1829 retrievefails++;
1830 else
1831 finished = TRUE;
1832 }
1833 if( finished )
1834 break;
1835 }
1836 if( finished )
1837 break;
1838 }
1839
1840 if( block1end < pospp && block2end < posmm )
1841 {
1842 findNextBlock(hashlistpp, pospp, &block1start, &block1end);
1843 findNextBlock(hashlistmm, posmm, &block2start, &block2end);
1844 }
1845 else
1846 finished = TRUE;
1847 }
1848 else if( hashlistpp[block1start] < hashlistmm[block2start] && block1end < pospp )
1849 findNextBlock(hashlistpp, pospp, &block1start, &block1end);
1850 else if( hashlistpp[block1start] > hashlistmm[block2start] && block2end < posmm )
1851 findNextBlock(hashlistmm, posmm, &block2start, &block2end);
1852 else
1853 finished = TRUE;
1854 }
1855 }
1856
1857 /* Process pm and mp lists */
1858 if( pospm > 0 && posmp > 0 )
1859 {
1860 SCIP_Longint maxcombines;
1861 SCIP_Longint ncombines;
1862 SCIP_Bool finished;
1863 SCIP_Bool success;
1864 int combinefails;
1865 int retrievefails;
1866 COLPAIR colpair;
1867
1868 finished = FALSE;
1869 block1start = 0;
1870 block1end = 0;
1871 block2start = 0;
1872 block2end = 0;
1873
1874 maxcombines = presoldata->maxpairfac == -1 ? SCIP_LONGINT_MAX : (((SCIP_Longint)ncols) * presoldata->maxpairfac);
1875
1876 ncombines = 0;
1877 combinefails = 0;
1878 retrievefails = 0;
1879 findNextBlock(hashlistpm, pospm, &block1start, &block1end);
1880 findNextBlock(hashlistmp, posmp, &block2start, &block2end);
1881#ifdef SCIP_MORE_DEBUG
1882 SCIPdebugMsg(scip, "processing pm and mp\n");
1883#endif
1884
1885 while( !finished )
1886 {
1887 if( hashlistpm[block1start] == hashlistmp[block2start] )
1888 {
1889 for( i = block1start; i < block1end; i++ )
1890 {
1891 for( j = block2start; j < block2end; j++ )
1892 {
1893 if( colidxlistpm[i] != colidxlistmp[j] )
1894 {
1895 colpair.col1idx = MIN(colidxlistpm[i], colidxlistmp[j]);
1896 colpair.col2idx = MAX(colidxlistpm[i], colidxlistmp[j]);
1897
1898 if( !SCIPhashsetExists(pairhashset, encodeColPair(&colpair)) )
1899 {
1900 int* colpnt1 = SCIPmatrixGetColIdxPtr(matrix, colpair.col1idx);
1901 SCIP_Real* valpnt1 = SCIPmatrixGetColValPtr(matrix, colpair.col1idx);
1902 int* colpnt2 = SCIPmatrixGetColIdxPtr(matrix, colpair.col2idx);
1903 SCIP_Real* valpnt2 = SCIPmatrixGetColValPtr(matrix, colpair.col2idx);
1904 SCIP_Real obj1 = SCIPvarGetObj(SCIPmatrixGetVar(matrix, colpair.col1idx));
1905 SCIP_Real obj2 = SCIPvarGetObj(SCIPmatrixGetVar(matrix, colpair.col2idx));
1906 int collen1 = SCIPmatrixGetColNNonzs(matrix, colpair.col1idx);
1907 int collen2 = SCIPmatrixGetColNNonzs(matrix, colpair.col2idx);
1908
1909 success = FALSE;
1910
1911 SCIP_CALL( combineCols(scip, colpnt1, colpnt2, valpnt1, valpnt2, obj1, obj2, collen1,
1912 collen2, nrows, TRUE, TRUE, lbdual, ubdual, &success) );
1913
1914 if( success )
1915 combinefails = 0;
1916 else
1917 combinefails++;
1918
1919 SCIP_CALL( SCIPhashsetInsert(pairhashset, SCIPblkmem(scip), encodeColPair(&colpair)) );
1920 ncombines++;
1921 if( ncombines >= maxcombines || combinefails >= presoldata->maxcombinefails )
1922 finished = TRUE;
1923
1924 retrievefails = 0;
1925 }
1926 else if( retrievefails < presoldata->maxretrievefails )
1927 retrievefails++;
1928 else
1929 finished = TRUE;
1930 }
1931 if( finished )
1932 break;
1933 }
1934 if( finished )
1935 break;
1936 }
1937
1938 if( block1end < pospm && block2end < posmp )
1939 {
1940 findNextBlock(hashlistpm, pospm, &block1start, &block1end);
1941 findNextBlock(hashlistmp, posmp, &block2start, &block2end);
1942 }
1943 else
1944 finished = TRUE;
1945 }
1946 else if( hashlistpm[block1start] < hashlistmp[block2start] && block1end < pospm )
1947 findNextBlock(hashlistpm, pospm, &block1start, &block1end);
1948 else if( hashlistpm[block1start] > hashlistmp[block2start] && block2end < posmp )
1949 findNextBlock(hashlistmp, posmp, &block2start, &block2end);
1950 else
1951 finished = TRUE;
1952 }
1953 }
1954
1955 SCIPhashsetFree(&pairhashset, SCIPblkmem(scip));
1956 SCIPfreeBlockMemoryArray(scip, &colidxlistmp, listsizemp);
1957 SCIPfreeBlockMemoryArray(scip, &colidxlistpm, listsizepm);
1958 SCIPfreeBlockMemoryArray(scip, &colidxlistmm, listsizemm);
1959 SCIPfreeBlockMemoryArray(scip, &colidxlistpp, listsizepp);
1960 SCIPfreeBlockMemoryArray(scip, &hashlistmp, listsizemp);
1961 SCIPfreeBlockMemoryArray(scip, &hashlistpm, listsizepm);
1962 SCIPfreeBlockMemoryArray(scip, &hashlistmm, listsizemm);
1963 SCIPfreeBlockMemoryArray(scip, &hashlistpp, listsizepp);
1964
1965#ifdef SCIP_MORE_DEBUG
1966 SCIPdebugMsg(scip, "CombCols:\n");
1967 for( i = 0; i < nrows; i++ )
1968 {
1969 assert(SCIPisLE(scip,lbdual[i],ubdual[i]));
1970 SCIPdebugMsg(scip, "y%d=[%g,%g]\n",i,lbdual[i],ubdual[i]);
1971 }
1972 SCIPdebugMsg(scip,"\n");
1973#endif
1974 }
1975
1976 SCIP_CALL( SCIPallocBufferArray(scip, &mincolact, ncols) );
1977 SCIP_CALL( SCIPallocBufferArray(scip, &mincolactinf, ncols) );
1978
1979 /* apply dual bound strengthening */
1980 loops = 0;
1981 boundchanges = 1;
1982 while( 0 < boundchanges && loops < presoldata->maxdualbndloops )
1983 {
1984 loops++;
1985 boundchanges = 0;
1986
1987 for( i = 0; i < nimplubvars; i++ )
1988 {
1989 assert(!SCIPvarIsIntegral(SCIPmatrixGetVar(matrix, implubvars[i]))
1990 || SCIPvarIsImpliedIntegral(SCIPmatrixGetVar(matrix, implubvars[i])));
1991 calcMinColActivity(scip, matrix, implubvars[i], lbdual, ubdual, mincolact, mincolactinf);
1992 }
1993
1994 for( i = 0; i < nimplubvars; i++ )
1995 {
1996 SCIP_Real objval;
1997 SCIP_Bool ubinfchange;
1998 SCIP_Bool lbinfchange;
1999 int col;
2000
2001 col = implubvars[i];
2002 var = SCIPmatrixGetVar(matrix, col);
2003
2004 objval = SCIPvarGetObj(var);
2005 colpnt = SCIPmatrixGetColIdxPtr(matrix, col);
2006 colend = colpnt + SCIPmatrixGetColNNonzs(matrix, col);
2007 valpnt = SCIPmatrixGetColValPtr(matrix, col);
2008
2009 for( ; colpnt < colend; colpnt++, valpnt++ )
2010 {
2011 int row;
2012 SCIP_Real val;
2013 SCIP_Real mincolresact;
2014
2015 row = *colpnt;
2016 val = *valpnt;
2017
2018 calcMinColActResidual(scip, matrix, col, row, val, lbdual, ubdual,
2019 mincolact, mincolactinf, &mincolresact);
2020
2021 updateDualBounds(scip, matrix, objval, val, row, mincolresact,
2022 lbdual, ubdual, &boundchanges, &ubinfchange, &lbinfchange);
2023
2024 if( ubinfchange || lbinfchange )
2025 infinityCountUpdate(scip, matrix, row, lbdual, ubdual, isubimplied,
2026 mincolact, mincolactinf, ubinfchange, lbinfchange);
2027 }
2028 }
2029 }
2030
2031#ifdef SCIP_MORE_DEBUG
2032 SCIPdebugMsg(scip, "BndStr:\n");
2033 for( i = 0; i < nrows; i++ )
2034 {
2035 assert(SCIPisLE(scip,lbdual[i],ubdual[i]));
2036 SCIPdebugMsg(scip, "y%d=[%g,%g]\n",i,lbdual[i],ubdual[i]);
2037 }
2038 SCIPdebugMsg(scip,"\n");
2039#endif
2040
2041 SCIP_CALL( SCIPallocBufferArray(scip, &maxcolact, ncols) );
2042 SCIP_CALL( SCIPallocBufferArray(scip, &maxcolactinf, ncols) );
2043
2044 /* calculate final minimal and maximal column activities */
2045 for( i = 0; i < ncols; i++ )
2046 {
2047 calcMinColActivity(scip, matrix, i, lbdual, ubdual, mincolact, mincolactinf);
2048 calcMaxColActivity(scip, matrix, i, lbdual, ubdual, maxcolact, maxcolactinf);
2049 }
2050
2051 for( i = 0; i < ncols; i++ )
2052 {
2053 SCIP_Real objval;
2054
2055 var = SCIPmatrixGetVar(matrix, i);
2056
2057 /* do not fix variables if the locks do not match */
2058 if( SCIPmatrixUplockConflict(matrix, i) || SCIPmatrixDownlockConflict(matrix, i) )
2059 continue;
2060
2061 objval = SCIPvarGetObj(var);
2062
2063 /* c_j - sup(y^T A_{.j}) > 0 => fix x_j to its lower bound */
2064 if( SCIPisGT(scip, objval, maxcolact[i]) && varstofix[i] == NOFIX )
2065 {
2066 if( SCIPisGT(scip, SCIPvarGetLbGlobal(var), -SCIPinfinity(scip)) )
2067 {
2068 varstofix[i] = FIXATLB;
2069 (*npossiblefixings)++;
2070 }
2071 }
2072
2073 /* c_j - inf(y^T A_{.j}) < 0 => fix x_j to its upper bound */
2074 if( SCIPisLT(scip, objval, mincolact[i]) && varstofix[i] == NOFIX )
2075 {
2076 if( SCIPisLT(scip, SCIPvarGetUbGlobal(var), SCIPinfinity(scip)) )
2077 {
2078 varstofix[i] = FIXATUB;
2079 (*npossiblefixings)++;
2080 }
2081 }
2082 }
2083
2084 for( i = 0; i < nrows; i++ )
2085 {
2086 /* implied equality: y_i > 0 => A_{i.}x - b_i = 0 */
2087 if( SCIPmatrixIsRowRhsInfinity(matrix, i) )
2088 {
2089 if( SCIPisGT(scip, lbdual[i], 0.0) && (sidestochange[i] == NOCHANGE) )
2090 {
2091 /* change >= inequality to equality */
2092 sidestochange[i] = RHSTOLHS;
2093 (*npossiblesidechanges)++;
2094 }
2095 }
2096 else
2097 {
2098 if( !SCIPmatrixIsRowRhsInfinity(matrix, i) &&
2099 !SCIPisEQ(scip,SCIPmatrixGetRowLhs(matrix, i),SCIPmatrixGetRowRhs(matrix, i)) )
2100 {
2101 /* for ranged rows we have to decide which side (lhs or rhs) determines the equality */
2102 if( SCIPisGT(scip, lbdual[i], 0.0) && sidestochange[i]==NOCHANGE )
2103 {
2104 sidestochange[i] = RHSTOLHS;
2105 (*npossiblesidechanges)++;
2106 }
2107
2108 if( SCIPisLT(scip, ubdual[i], 0.0) && sidestochange[i]==NOCHANGE)
2109 {
2110 sidestochange[i] = LHSTORHS;
2111 (*npossiblesidechanges)++;
2112 }
2113 }
2114 }
2115 }
2116
2117 SCIPfreeBufferArray(scip, &maxcolactinf);
2118 SCIPfreeBufferArray(scip, &maxcolact);
2119 SCIPfreeBufferArray(scip, &mincolactinf);
2120 SCIPfreeBufferArray(scip, &mincolact);
2121
2122 SCIPfreeBufferArray(scip, &ubdual);
2123 SCIPfreeBufferArray(scip, &lbdual);
2124 SCIPfreeBufferArray(scip, &implubvars);
2125 SCIPfreeBufferArray(scip, &islbimplied);
2126 SCIPfreeBufferArray(scip, &isubimplied);
2127 SCIPfreeBufferArray(scip, &tmpubs);
2128 SCIPfreeBufferArray(scip, &tmplbs);
2129
2130 return SCIP_OKAY;
2131}
2132
2133/*
2134 * Callback methods of presolver
2135 */
2136
2137/** copy method for constraint handler plugins (called when SCIP copies plugins) */
2138static
2139SCIP_DECL_PRESOLCOPY(presolCopyDualinfer)
2140{ /*lint --e{715}*/
2141 assert(scip != NULL);
2142 assert(presol != NULL);
2143
2144 SCIP_STRINGEQ( SCIPpresolGetName(presol), PRESOL_NAME, SCIP_INVALIDCALL );
2145
2146 /* call inclusion method of presolver */
2147 SCIP_CALL( SCIPincludePresolDualinfer(scip) );
2148
2149 return SCIP_OKAY;
2150}
2151
2152/** destructor of presolver to free user data (called when SCIP is exiting) */
2153static
2154SCIP_DECL_PRESOLFREE(presolFreeDualinfer)
2155{ /*lint --e{715}*/
2156 SCIP_PRESOLDATA* presoldata;
2157
2158 /* free presolver data */
2159 presoldata = SCIPpresolGetData(presol);
2160 assert(presoldata != NULL);
2161
2162 SCIPfreeBlockMemory(scip, &presoldata);
2163 SCIPpresolSetData(presol, NULL);
2164
2165 return SCIP_OKAY;
2166}
2167
2168/** execution method of presolver */
2169static
2170SCIP_DECL_PRESOLEXEC(presolExecDualinfer)
2171{ /*lint --e{715}*/
2172 SCIP_MATRIX* matrix;
2173 SCIP_Bool initialized;
2174 SCIP_Bool complete;
2175 SCIP_Bool infeasible;
2176 SCIP_PRESOLDATA* presoldata;
2177 FIXINGDIRECTION* varstofix;
2178 int npossiblefixings;
2179 int nconvarsfixed;
2180 int nintvarsfixed;
2181 int nbinvarsfixed;
2182 SIDECHANGE* sidestochange;
2183 int npossiblesidechanges;
2184 int nsideschanged;
2185 int i;
2186 int nrows;
2187 int ncols;
2188 SCIP_VAR* var;
2189
2190 assert(result != NULL);
2191 *result = SCIP_DIDNOTRUN;
2192
2193 if( SCIPgetNContVars(scip) + SCIPgetNImplVars(scip) == 0 )
2194 return SCIP_OKAY;
2195
2196 /* the reductions made in this presolver apply to all optimal solutions because of complementary slackness */
2197 if( !SCIPallowWeakDualReds(scip) )
2198 return SCIP_OKAY;
2199
2200 *result = SCIP_DIDNOTFIND;
2201
2202 if( SCIPisInfinity(scip, -SCIPgetPseudoObjval(scip)) )
2203 {
2204 SCIPdebugMsg(scip, "DualInfer not executed because condition of existing dual solution is not fulfilled.\n");
2205 return SCIP_OKAY;
2206 }
2207
2208 presoldata = SCIPpresolGetData(presol);
2209 assert(presoldata != NULL);
2210
2211 matrix = NULL;
2212 SCIP_CALL( SCIPmatrixCreate(scip, &matrix, TRUE, &initialized, &complete, &infeasible,
2213 naddconss, ndelconss, nchgcoefs, nchgbds, nfixedvars) );
2214
2215 /* if infeasibility was detected during matrix creation, return here */
2216 if( infeasible )
2217 {
2218 if( initialized )
2219 SCIPmatrixFree(scip, &matrix);
2220
2221 *result = SCIP_CUTOFF;
2222 return SCIP_OKAY;
2223 }
2224
2225 if( !initialized )
2226 return SCIP_OKAY;
2227
2228 npossiblefixings = 0;
2229 nconvarsfixed = 0;
2230 nintvarsfixed = 0;
2231 nbinvarsfixed = 0;
2232 npossiblesidechanges = 0;
2233 nsideschanged = 0;
2234
2235 nrows = SCIPmatrixGetNRows(matrix);
2236 ncols = SCIPmatrixGetNColumns(matrix);
2237
2238 SCIP_CALL( SCIPallocBufferArray(scip, &varstofix, ncols) );
2239 SCIP_CALL( SCIPallocBufferArray(scip, &sidestochange, nrows) );
2240
2241 BMSclearMemoryArray(varstofix, ncols);
2242 BMSclearMemoryArray(sidestochange, nrows);
2243
2244 SCIP_CALL( dualBoundStrengthening(scip, matrix, presoldata,
2245 varstofix, &npossiblefixings, sidestochange, &npossiblesidechanges) );
2246
2247 if( npossiblefixings > 0 )
2248 {
2249 for( i = ncols - 1; i >= 0; --i )
2250 {
2251 SCIP_Bool fixed;
2252
2253 var = SCIPmatrixGetVar(matrix, i);
2254
2255 /* there should be no fixings for variables with inconsistent locks */
2256 assert(varstofix[i] == NOFIX || (!SCIPmatrixUplockConflict(matrix, i) && !SCIPmatrixDownlockConflict(matrix, i)));
2257
2258 fixed = FALSE;
2259
2260 if( varstofix[i] == FIXATLB )
2261 {
2262 SCIP_Real lb;
2263 lb = SCIPvarGetLbLocal(var);
2264
2265 /* fix at lower bound */
2266 SCIP_CALL( SCIPfixVar(scip, var, lb, &infeasible, &fixed) );
2267 if( infeasible )
2268 {
2269 SCIPdebugMsg(scip, " -> infeasible fixing\n");
2270 *result = SCIP_CUTOFF;
2271 break;
2272 }
2273 assert(fixed);
2274 (*nfixedvars)++;
2275 *result = SCIP_SUCCESS;
2276 }
2277 else if( varstofix[i] == FIXATUB )
2278 {
2279 SCIP_Real ub;
2280 ub = SCIPvarGetUbLocal(var);
2281
2282 /* fix at upper bound */
2283 SCIP_CALL( SCIPfixVar(scip, var, ub, &infeasible, &fixed) );
2284 if( infeasible )
2285 {
2286 SCIPdebugMsg(scip, " -> infeasible fixing\n");
2287 *result = SCIP_CUTOFF;
2288 break;
2289 }
2290 assert(fixed);
2291 (*nfixedvars)++;
2292 *result = SCIP_SUCCESS;
2293 }
2294
2295 /* keep a small statistic which types of variables are fixed */
2296 if( fixed )
2297 {
2298 if( !SCIPvarIsNonimpliedIntegral(var) )
2299 nconvarsfixed++;
2300 else if( SCIPvarGetType(var) == SCIP_VARTYPE_BINARY )
2301 nbinvarsfixed++;
2302 else
2303 nintvarsfixed++;
2304 }
2305 }
2306 }
2307
2308 if( npossiblesidechanges > 0 )
2309 {
2310 for( i = 0; i < nrows; i++ )
2311 {
2312 SCIP_CONS* cons;
2313 SCIP_CONSHDLR* conshdlr;
2314 const char* conshdlrname;
2315
2316 if( sidestochange[i] == NOCHANGE )
2317 continue;
2318
2319 if( presoldata->maxrowsupport < SCIPmatrixGetRowNNonzs(matrix, i) )
2320 continue;
2321
2322 cons = SCIPmatrixGetCons(matrix,i);
2323 conshdlr = SCIPconsGetHdlr(cons);
2324 conshdlrname = SCIPconshdlrGetName(conshdlr);
2325
2326 if( strcmp(conshdlrname, "linear") == 0 )
2327 {
2328 SCIP_Real lhs;
2329 SCIP_Real rhs;
2330 SCIP_Real matrixlhs;
2331 SCIP_Real matrixrhs;
2332
2333 lhs = SCIPgetLhsLinear(scip, cons);
2334 rhs = SCIPgetRhsLinear(scip, cons);
2335 matrixlhs = SCIPmatrixGetRowLhs(matrix, i);
2336 matrixrhs = SCIPmatrixGetRowRhs(matrix, i);
2337
2338 assert(!SCIPisEQ(scip, matrixlhs, matrixrhs));
2339
2340 /* when creating the matrix, constraints are multiplied if necessary by (-1)
2341 * to ensure that the following representation is obtained:
2342 * infty >= a x >= b
2343 * or
2344 * c >= ax >= b (ranged rows)
2345 */
2346
2347 /* for ranged constraints we have to distinguish between both sides */
2348 if( sidestochange[i] == RHSTOLHS )
2349 {
2350 if( SCIPisEQ(scip, matrixlhs, lhs) )
2351 {
2352 /* change rhs to lhs */
2353 SCIP_CALL( SCIPchgRhsLinear(scip, cons, matrixlhs) );
2354 }
2355 else
2356 {
2357 /* consider multiplication by (-1) in the matrix */
2358 SCIP_CALL( SCIPchgLhsLinear(scip, cons, -matrixlhs) );
2359 }
2360
2361 nsideschanged++;
2362 (*nchgsides)++;
2363 }
2364 else if( sidestochange[i] == LHSTORHS )
2365 {
2366 if( SCIPisEQ(scip, matrixrhs, rhs) )
2367 {
2368 /* change lhs to rhs */
2369 SCIP_CALL( SCIPchgLhsLinear(scip, cons, matrixrhs) );
2370 }
2371 else
2372 {
2373 /* consider multiplication by (-1) in the matrix */
2374 SCIP_CALL( SCIPchgRhsLinear(scip, cons, -matrixrhs) );
2375 }
2376
2377 nsideschanged++;
2378 (*nchgsides)++;
2379 }
2380 }
2381 }
2382 }
2383
2384 SCIPfreeBufferArray(scip, &sidestochange);
2385 SCIPfreeBufferArray(scip, &varstofix);
2386
2387 if( (nconvarsfixed + nintvarsfixed + nbinvarsfixed) > 0 || npossiblesidechanges > 0 )
2388 {
2389 SCIPdebugMsg(scip, "### fixed vars [cont: %d, int: %d, bin: %d], changed sides [%d]\n",
2390 nconvarsfixed, nintvarsfixed, nbinvarsfixed, nsideschanged);
2391 }
2392
2393 SCIPmatrixFree(scip, &matrix);
2394
2395 return SCIP_OKAY;
2396}
2397
2398
2399/*
2400 * presolver specific interface methods
2401 */
2402
2403/** creates the dual inference presolver and includes it in SCIP */
2404SCIP_RETCODE SCIPincludePresolDualinfer(
2405 SCIP* scip /**< SCIP data structure */
2406 )
2407{
2408 SCIP_PRESOL* presol;
2409 SCIP_PRESOLDATA* presoldata;
2410
2411 /* create presolver data */
2412 SCIP_CALL( SCIPallocBlockMemory(scip, &presoldata) );
2413
2414 /* include presolver */
2415 SCIP_CALL( SCIPincludePresolBasic(scip, &presol, PRESOL_NAME, PRESOL_DESC, PRESOL_PRIORITY, PRESOL_MAXROUNDS,
2416 PRESOL_TIMING, presolExecDualinfer, presoldata) );
2417 SCIP_CALL( SCIPsetPresolCopy(scip, presol, presolCopyDualinfer) );
2418 SCIP_CALL( SCIPsetPresolFree(scip, presol, presolFreeDualinfer) );
2419
2420 SCIP_CALL( SCIPaddBoolParam(scip,
2421 "presolving/dualinfer/twocolcombine",
2422 "use convex combination of columns for determining dual bounds",
2423 &presoldata->usetwocolcombine, FALSE, DEFAULT_TWOCOLUMN_COMBINE, NULL, NULL) );
2424
2425 SCIP_CALL( SCIPaddIntParam(scip,
2426 "presolving/dualinfer/maxdualbndloops",
2427 "maximal number of dual bound strengthening loops",
2428 &presoldata->maxdualbndloops, FALSE, DEFAULT_MAXLOOPS_DUALBNDSTR, -1, INT_MAX, NULL, NULL) );
2429
2430 SCIP_CALL( SCIPaddIntParam(scip,
2431 "presolving/dualinfer/maxconsiderednonzeros",
2432 "maximal number of considered non-zeros within one column (-1: no limit)",
2433 &presoldata->maxconsiderednonzeros, TRUE, DEFAULT_MAXCONSIDEREDNONZEROS, -1, INT_MAX, NULL, NULL) );
2434
2435 SCIP_CALL( SCIPaddIntParam(scip,
2436 "presolving/dualinfer/maxretrievefails",
2437 "maximal number of consecutive useless hashtable retrieves",
2438 &presoldata->maxretrievefails, TRUE, DEFAULT_MAXRETRIEVEFAILS, -1, INT_MAX, NULL, NULL) );
2439
2440 SCIP_CALL( SCIPaddIntParam(scip,
2441 "presolving/dualinfer/maxcombinefails",
2442 "maximal number of consecutive useless column combines",
2443 &presoldata->maxcombinefails, TRUE, DEFAULT_MAXCOMBINEFAILS, -1, INT_MAX, NULL, NULL) );
2444
2445 SCIP_CALL( SCIPaddIntParam(scip,
2446 "presolving/dualinfer/maxhashfac",
2447 "Maximum number of hashlist entries as multiple of number of columns in the problem (-1: no limit)",
2448 &presoldata->maxhashfac, TRUE, DEFAULT_MAXHASHFAC, -1, INT_MAX, NULL, NULL) );
2449
2450 SCIP_CALL( SCIPaddIntParam(scip,
2451 "presolving/dualinfer/maxpairfac",
2452 "Maximum number of processed column pairs as multiple of the number of columns in the problem (-1: no limit)",
2453 &presoldata->maxpairfac, TRUE, DEFAULT_MAXPAIRFAC, -1, INT_MAX, NULL, NULL) );
2454
2455 SCIP_CALL( SCIPaddIntParam(scip,
2456 "presolving/dualinfer/maxrowsupport",
2457 "Maximum number of row's non-zeros for changing inequality to equality",
2458 &presoldata->maxrowsupport, FALSE, DEFAULT_MAXROWSUPPORT, 2, INT_MAX, NULL, NULL) );
2459
2460 return SCIP_OKAY;
2461}
a
SCIP_VAR * a
Definition circlepacking.c:66
b
SCIP_VAR ** b
Definition circlepacking.c:65
cons_linear.h
Constraint handler for linear constraints in their most general form, .
determineBestBounds
static SCIP_RETCODE determineBestBounds(SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, MIR_DATA *data, SCIP_Real boundswitch, int usevbds, SCIP_Bool allowlocal, SCIP_Bool fixintegralrhs, SCIP_Bool ignoresol, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, SCIP_Real *bestlb, SCIP_Real *bestub, int *bestlbtype, int *bestubtype, SCIP_BOUNDTYPE *selectedbound, SCIP_Bool *freevariable)
Definition cuts.c:4814
NULL
#define NULL
Definition def.h:257
SCIP_MAXSTRLEN
#define SCIP_MAXSTRLEN
Definition def.h:278
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_MAX
#define SCIP_LONGINT_MAX
Definition def.h:151
SCIP_CALL
#define SCIP_CALL(x)
Definition def.h:364
SCIPgetRhsLinear
SCIP_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
Definition cons_linear.c:18345
SCIPchgRhsLinear
SCIP_RETCODE SCIPchgRhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real rhs)
Definition cons_linear.c:18381
SCIPgetLhsLinear
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
Definition cons_linear.c:18326
SCIPcreateConsBasicLinear
SCIP_RETCODE SCIPcreateConsBasicLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs)
Definition cons_linear.c:17924
SCIPchgLhsLinear
SCIP_RETCODE SCIPchgLhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs)
Definition cons_linear.c:18364
SCIPfree
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition scip_general.c:402
SCIPcreate
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition scip_general.c:370
SCIPgetStatus
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition scip_general.c:562
SCIPaddVar
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition scip_prob.c:1907
SCIPgetNImplVars
int SCIPgetNImplVars(SCIP *scip)
Definition scip_prob.c:2387
SCIPgetNContVars
int SCIPgetNContVars(SCIP *scip)
Definition scip_prob.c:2569
SCIPwriteOrigProblem
SCIP_RETCODE SCIPwriteOrigProblem(SCIP *scip, const char *filename, const char *extension, SCIP_Bool genericnames)
Definition scip_prob.c:742
SCIPaddCons
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition scip_prob.c:3274
SCIPsetObjsense
SCIP_RETCODE SCIPsetObjsense(SCIP *scip, SCIP_OBJSENSE objsense)
Definition scip_prob.c:1417
SCIPcreateProbBasic
SCIP_RETCODE SCIPcreateProbBasic(SCIP *scip, const char *name)
Definition scip_prob.c:182
SCIPhashsetFree
void SCIPhashsetFree(SCIP_HASHSET **hashset, BMS_BLKMEM *blkmem)
Definition misc.c:3833
SCIPhashsetExists
SCIP_Bool SCIPhashsetExists(SCIP_HASHSET *hashset, void *element)
Definition misc.c:3860
SCIPhashsetInsert
SCIP_RETCODE SCIPhashsetInsert(SCIP_HASHSET *hashset, BMS_BLKMEM *blkmem, void *element)
Definition misc.c:3843
SCIPhashsetCreate
SCIP_RETCODE SCIPhashsetCreate(SCIP_HASHSET **hashset, BMS_BLKMEM *blkmem, int size)
Definition misc.c:3802
SCIPhashTwo
#define SCIPhashTwo(a, b)
Definition pub_misc.h:568
SCIPdebugMsg
#define SCIPdebugMsg
Definition scip_message.h:78
SCIPwarningMessage
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition scip_message.c:120
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
SCIPsetIntParam
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition scip_param.c:487
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
SCIPsetBoolParam
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition scip_param.c:429
SCIPincludePresolDualinfer
SCIP_RETCODE SCIPincludePresolDualinfer(SCIP *scip)
Definition presol_dualinfer.c:2404
SCIPconshdlrGetName
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition cons.c:4320
SCIPconsGetHdlr
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition cons.c:8413
SCIPreleaseCons
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition scip_cons.c:1173
SCIPgetPseudoObjval
SCIP_Real SCIPgetPseudoObjval(SCIP *scip)
Definition scip_lp.c:339
SCIPfreeBlockMemoryArray
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition scip_mem.h:110
SCIPblkmem
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition scip_mem.c:57
SCIPcalcMemGrowSize
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition scip_mem.c:139
SCIPallocBufferArray
#define SCIPallocBufferArray(scip, ptr, num)
Definition scip_mem.h:124
SCIPfreeBufferArray
#define SCIPfreeBufferArray(scip, ptr)
Definition scip_mem.h:136
SCIPallocBlockMemoryArray
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition scip_mem.h:93
SCIPreallocBlockMemoryArray
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition scip_mem.h:99
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
SCIPcheckSolOrig
SCIP_RETCODE SCIPcheckSolOrig(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *feasible, SCIP_Bool printreason, SCIP_Bool completely)
Definition scip_sol.c:4385
SCIPgetBestSol
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition scip_sol.c:2986
SCIPgetSolOrigObj
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition scip_sol.c:1890
SCIPfreeTransform
SCIP_RETCODE SCIPfreeTransform(SCIP *scip)
Definition scip_solve.c:3475
SCIPsolve
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition scip_solve.c:2611
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
SCIPisInfinity
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition scip_numerics.c:512
SCIPisGT
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition scip_numerics.c:475
SCIPisNegative
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
Definition scip_numerics.c:573
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
SCIPvarIsImpliedIntegral
SCIP_Bool SCIPvarIsImpliedIntegral(SCIP_VAR *var)
Definition var.c:23530
SCIPvarGetUbLocal
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition var.c:24300
SCIPvarIsNonimpliedIntegral
SCIP_Bool SCIPvarIsNonimpliedIntegral(SCIP_VAR *var)
Definition var.c:23538
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
SCIPreleaseVar
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition scip_var.c:1887
SCIPvarIsIntegral
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition var.c:23522
SCIPvarGetLbLocal
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition var.c:24266
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
SCIPcreateVarBasic
SCIP_RETCODE SCIPcreateVarBasic(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype)
Definition scip_var.c:184
SCIPchgVarObj
SCIP_RETCODE SCIPchgVarObj(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition scip_var.c:5372
SCIPallowWeakDualReds
SCIP_Bool SCIPallowWeakDualReds(SCIP *scip)
Definition scip_var.c:10998
SCIPsortIntInt
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
SCIPsortIntReal
void SCIPsortIntReal(int *intarray, SCIP_Real *realarray, int len)
SCIPsortRealInt
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
SCIPsnprintf
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition misc.c:10827
result
* result
Definition heur_actconsdiving.c:297
SCIP_OKAY
return SCIP_OKAY
Definition heur_actconsdiving.c:237
objval
SCIP_Real objval
Definition heur_intdiving.c:208
sol
static SCIP_SOL * sol
Definition heur_intshifting.c:696
assert
assert(minobj< SCIPgetCutoffbound(scip))
nvars
int nvars
Definition heur_intshifting.c:711
var
SCIP_VAR * var
Definition heur_objpscostdiving.c:269
i
int i
Definition heur_rootsoldiving.c:216
solveLP
static SCIP_RETCODE solveLP(SCIP *scip, SCIP_DIVESET *diveset, SCIP_Longint maxnlpiterations, SCIP_DIVECONTEXT divecontext, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition heuristics.c:49
SCIPmatrixUplockConflict
SCIP_Bool SCIPmatrixUplockConflict(SCIP_MATRIX *matrix, int col)
Definition matrix.c:2201
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
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
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
SCIPmatrixGetCons
SCIP_CONS * SCIPmatrixGetCons(SCIP_MATRIX *matrix, int row)
Definition matrix.c:2189
SCIPmatrixFree
void SCIPmatrixFree(SCIP *scip, SCIP_MATRIX **matrix)
Definition matrix.c:1348
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
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
DEFAULT_TWOCOLUMN_COMBINE
#define DEFAULT_TWOCOLUMN_COMBINE
Definition presol_dualinfer.c:72
calcMaxColActivity
static void calcMaxColActivity(SCIP *scip, SCIP_MATRIX *matrix, int col, SCIP_Real *lbdual, SCIP_Real *ubdual, SCIP_Real *maxcolact, int *maxcolactinf)
Definition presol_dualinfer.c:1113
SideChange
SideChange
Definition presol_dualinfer.c:110
RHSTOLHS
@ RHSTOLHS
Definition presol_dualinfer.c:111
LHSTORHS
@ LHSTORHS
Definition presol_dualinfer.c:113
NOCHANGE
@ NOCHANGE
Definition presol_dualinfer.c:112
encodeColPair
static void * encodeColPair(COLPAIR *colpair)
Definition presol_dualinfer.c:140
calcMinColActResidual
static void calcMinColActResidual(SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real val, SCIP_Real *lbdual, SCIP_Real *ubdual, const SCIP_Real *mincolact, const int *mincolactinf, SCIP_Real *mincolresact)
Definition presol_dualinfer.c:990
DEFAULT_MAXCONSIDEREDNONZEROS
#define DEFAULT_MAXCONSIDEREDNONZEROS
Definition presol_dualinfer.c:74
getImpliedBounds
static void getImpliedBounds(SCIP *scip, SCIP_MATRIX *matrix, int col, SCIP_Real *lbs, SCIP_Real *ubs, SCIP_Bool *ubimplied, SCIP_Bool *lbimplied)
Definition presol_dualinfer.c:872
calcMinColActivity
static void calcMinColActivity(SCIP *scip, SCIP_MATRIX *matrix, int col, SCIP_Real *lbdual, SCIP_Real *ubdual, SCIP_Real *mincolact, int *mincolactinf)
Definition presol_dualinfer.c:1053
hashIndexPair
static int hashIndexPair(int idx1, int idx2)
Definition presol_dualinfer.c:158
signum
signum
Definition presol_dualinfer.c:123
DN
@ DN
Definition presol_dualinfer.c:123
POS
@ POS
Definition presol_dualinfer.c:123
UP
@ UP
Definition presol_dualinfer.c:123
NEG
@ NEG
Definition presol_dualinfer.c:123
COLPAIR
struct ColPair COLPAIR
Definition presol_dualinfer.c:131
getVarBoundsOfRow
static void getVarBoundsOfRow(SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real val, SCIP_Real *lbs, SCIP_Real *ubs, SCIP_Real *rowub, SCIP_Bool *ubfound, SCIP_Real *rowlb, SCIP_Bool *lbfound)
Definition presol_dualinfer.c:801
combineCols
static SCIP_RETCODE combineCols(SCIP *scip, int *row1idxptr, int *row2idxptr, SCIP_Real *row1valptr, SCIP_Real *row2valptr, SCIP_Real b1, SCIP_Real b2, int row1len, int row2len, int ncols, SCIP_Bool swaprow1, SCIP_Bool swaprow2, SCIP_Real *lbs, SCIP_Real *ubs, SCIP_Bool *success)
Definition presol_dualinfer.c:223
getMinColActWithoutRow
static SCIP_Real getMinColActWithoutRow(SCIP *scip, SCIP_MATRIX *matrix, int col, int withoutrow, SCIP_Real *lbdual, SCIP_Real *ubdual)
Definition presol_dualinfer.c:934
updateDualBounds
static void updateDualBounds(SCIP *scip, SCIP_MATRIX *matrix, SCIP_Real objval, SCIP_Real val, int row, SCIP_Real mincolresact, SCIP_Real *lbdual, SCIP_Real *ubdual, int *boundchanges, SCIP_Bool *ubinfchange, SCIP_Bool *lbinfchange)
Definition presol_dualinfer.c:1470
findNextBlock
static void findNextBlock(const int *list, int len, int *start, int *end)
Definition presol_dualinfer.c:201
dualBoundStrengthening
static SCIP_RETCODE dualBoundStrengthening(SCIP *scip, SCIP_MATRIX *matrix, SCIP_PRESOLDATA *presoldata, FIXINGDIRECTION *varstofix, int *npossiblefixings, SIDECHANGE *sidestochange, int *npossiblesidechanges)
Definition presol_dualinfer.c:1539
DEFAULT_MAXHASHFAC
#define DEFAULT_MAXHASHFAC
Definition presol_dualinfer.c:77
SIDECHANGE
enum SideChange SIDECHANGE
Definition presol_dualinfer.c:115
getMinMaxActivityResiduals
static void getMinMaxActivityResiduals(SCIP *scip, SCIP_MATRIX *matrix, int withoutcol, int row, SCIP_Real *lbs, SCIP_Real *ubs, SCIP_Real *minresactivity, SCIP_Real *maxresactivity, SCIP_Bool *isminsettoinfinity, SCIP_Bool *ismaxsettoinfinity)
Definition presol_dualinfer.c:706
DEFAULT_MAXCOMBINEFAILS
#define DEFAULT_MAXCOMBINEFAILS
Definition presol_dualinfer.c:76
DEFAULT_MAXRETRIEVEFAILS
#define DEFAULT_MAXRETRIEVEFAILS
Definition presol_dualinfer.c:75
DEFAULT_MAXLOOPS_DUALBNDSTR
#define DEFAULT_MAXLOOPS_DUALBNDSTR
Definition presol_dualinfer.c:73
DEFAULT_MAXPAIRFAC
#define DEFAULT_MAXPAIRFAC
Definition presol_dualinfer.c:78
infinityCountUpdate
static void infinityCountUpdate(SCIP *scip, SCIP_MATRIX *matrix, int row, SCIP_Real *lbdual, SCIP_Real *ubdual, const SCIP_Bool *isubimplied, SCIP_Real *mincolact, int *mincolactinf, SCIP_Bool ubinfchange, SCIP_Bool lbinfchange)
Definition presol_dualinfer.c:1174
DEFAULT_MAXROWSUPPORT
#define DEFAULT_MAXROWSUPPORT
Definition presol_dualinfer.c:79
addEntry
static SCIP_RETCODE addEntry(SCIP *scip, int *pos, int *listsize, int **hashlist, int **colidxlist, int hash, int colidx)
Definition presol_dualinfer.c:169
presol_dualinfer.h
dual inference presolver
pub_cons.h
public methods for managing constraints
pub_matrix.h
public methods for matrix
pub_message.h
public methods for message output
pub_presol.h
public methods for presolvers
pub_var.h
public methods for problem variables
scip_general.h
general public methods
scip_mem.h
public methods for memory management
scip_message.h
public methods for message handling
scip_numerics.h
public methods for numerical tolerances
scip_presol.h
public methods for presolving 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
SCIPincludeDefaultPlugins
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
Definition scipdefplugins.c:37
scipdefplugins.h
default SCIP plugins
SCIP_CONS
struct SCIP_Cons SCIP_CONS
Definition type_cons.h:63
SCIP_CONSHDLR
struct SCIP_Conshdlr SCIP_CONSHDLR
Definition type_cons.h:62
SCIP_MATRIX
struct SCIP_Matrix SCIP_MATRIX
Definition type_matrix.h:42
SCIP_HASHSET
struct SCIP_HashSet SCIP_HASHSET
Definition type_misc.h:112
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_OBJSENSE_MAXIMIZE
@ SCIP_OBJSENSE_MAXIMIZE
Definition type_prob.h:47
SCIP_OBJSENSE_MINIMIZE
@ SCIP_OBJSENSE_MINIMIZE
Definition type_prob.h:48
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_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_SOL
struct SCIP_Sol SCIP_SOL
Definition type_sol.h:57
SCIP_STATUS_OPTIMAL
@ SCIP_STATUS_OPTIMAL
Definition type_stat.h:43
SCIP_VAR
struct SCIP_Var SCIP_VAR
Definition type_var.h:166
SCIP_VARTYPE_CONTINUOUS
@ SCIP_VARTYPE_CONTINUOUS
Definition type_var.h:71
SCIP_VARTYPE_BINARY
@ SCIP_VARTYPE_BINARY
Definition type_var.h:64