Scippy

SCIP

Solving Constraint Integer Programs

presol_dualsparsify.c
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the program and library */
4/* SCIP --- Solving Constraint Integer Programs */
5/* */
6/* Copyright (c) 2002-2024 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file presol_dualsparsify.c
26 * @brief cancel nonzeros of the constraint matrix based on the columns
27 * @author Dieter Weninger
28 * @author Leona Gottwald
29 * @author Ambros Gleixner
30 * @author Weikun Chen
31 *
32 * This presolver attempts to cancel non-zero entries of the constraint
33 * matrix by adding scaled columns to other columns.
34 *
35 * In more detail, for two columns A_{j.} and A_{k.}, suppose for a given value s, we have
36 *
37 * | A_{j.} | - | A_{j.} - s*A_{k.} | > eta,
38 *
39 * where eta is an nonnegative integer. Then we introduce a new variable y := s*x_j + x_k
40 * and aggregate the variable x_k = y - s*x_j. After aggregation, the column of the variable
41 * x_j is A_{j.} + s*A_{j.} which is sparser than A_{j.}. In the case that x_k is nonimplied
42 * free variable, we need to add a new constraint l_k <= y - weight*x_j <= u_k into the problem
43 * to keep the bounds constraints of variable x_k.
44 *
45 * Further information can be found in
46 * Chen et al. "Two-row and two-column mixed-integer presolve using hasing-based pairing methods".
47 *
48 * @todo add infrastructure to SCIP for handling aggregated binary variables
49 */
50
51/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
52
54#include "scip/cons_linear.h"
55#include "scip/debug.h"
57#include "scip/pub_cons.h"
58#include "scip/pub_matrix.h"
59#include "scip/pub_message.h"
60#include "scip/pub_misc.h"
61#include "scip/pub_misc_sort.h"
62#include "scip/pub_presol.h"
63#include "scip/pub_var.h"
64#include "scip/scip_cons.h"
65#include "scip/scip_general.h"
66#include "scip/scip_mem.h"
67#include "scip/scip_message.h"
68#include "scip/scip_nlp.h"
69#include "scip/scip_numerics.h"
70#include "scip/scip_param.h"
71#include "scip/scip_presol.h"
72#include "scip/scip_pricer.h"
73#include "scip/scip_prob.h"
74#include "scip/scip_probing.h"
76#include "scip/scip_timing.h"
77#include "scip/scip_var.h"
78#include <string.h>
79
80#define PRESOL_NAME "dualsparsify"
81#define PRESOL_DESC "eliminate non-zero coefficients"
82
83#define PRESOL_PRIORITY -240000 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */
84#define PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
85#define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */
86
87#define DEFAULT_ENABLECOPY TRUE /**< should dualsparsify presolver be copied to sub-SCIPs? */
88#define DEFAULT_PRESERVEINTCOEFS FALSE /**< should we forbid cancellations that destroy integer coefficients? */
89#define DEFAULT_PRESERVEGOODLOCKS FALSE /**< should we preserve good locked properties of variables (at most one lock in one direction)? */
90#define DEFAULT_MAX_CONT_FILLIN 1 /**< default value for the maximal fillin for continuous variables */
91#define DEFAULT_MAX_BIN_FILLIN 1 /**< default value for the maximal fillin for binary variables */
92#define DEFAULT_MAX_INT_FILLIN 1 /**< default value for the maximal fillin for integer variables (including binary) */
93#define DEFAULT_MAXCONSIDEREDNONZEROS 70 /**< maximal number of considered nonzeros within one column (-1: no limit) */
94#define DEFAULT_MINELIMINATEDNONZEROS 100 /**< minimal eleminated nonzeros within one column if we need to add a constraint to the problem */
95#define DEFAULT_MAXRETRIEVEFAC 100.0 /**< limit on the number of useless vs. useful hashtable retrieves as a multiple of the number of constraints */
96#define DEFAULT_WAITINGFAC 2.0 /**< number of calls to wait until next execution as a multiple of the number of useless calls */
97
98#define MAXSCALE 1000.0 /**< maximal allowed scale for cancelling nonzeros */
99
100
101/*
102 * Data structures
103 */
104
105/** presolver data */
106struct SCIP_PresolData
107{
108 int nfailures; /**< number of calls to presolver without success */
109 int nwaitingcalls; /**< number of presolver calls until next real execution */
110 int naggregated; /**< number of aggregated variables */
111 int maxcontfillin; /**< maximal fillin for continuous variables */
112 int maxintfillin; /**< maximal fillin for integer variables*/
113 int maxbinfillin; /**< maximal fillin for binary variables */
114 int maxconsiderednonzeros;/**< maximal number of considered nonzeros within one column (-1: no limit) */
115 int mineliminatednonzeros;/**< minimal eliminated nonzeros within one column if we need to add a constraint to the problem */
116 SCIP_Real maxretrievefac; /**< limit on the number of useless vs. useful hashtable retrieves as a multiple of the number of constraints */
117 SCIP_Real waitingfac; /**< number of calls to wait until next execution as a multiple of the number of useless calls */
118 SCIP_Bool enablecopy; /**< should dualsparsify presolver be copied to sub-SCIPs? */
119 SCIP_Bool preserveintcoefs; /**< should we forbid cancellations that destroy integer coefficients? */
120 SCIP_Bool preservegoodlocks; /**< should we preserve good locked properties of variables (at most one lock in one direction)? */
121};
122
123/** structure representing a pair of constraints in a column; used for lookup in a hashtable */
125{
126 int colindex; /**< index of the column */
127 int consindex1; /**< index of the first constraint */
128 int consindex2; /**< index of the second constraint */
129 SCIP_Real conscoef1; /**< coefficient of the first constraint */
130 SCIP_Real conscoef2; /**< coefficient of the second constriant */
131};
132
134
135/*
136 * Local methods
137 */
138
139/** returns TRUE iff both keys are equal */
140static
141SCIP_DECL_HASHKEYEQ(consPairsEqual)
142{ /*lint --e{715}*/
143 SCIP* scip;
144 COLCONSPAIR* conspair1;
145 COLCONSPAIR* conspair2;
146 SCIP_Real ratio1;
147 SCIP_Real ratio2;
148
149 scip = (SCIP*) userptr;
150 conspair1 = (COLCONSPAIR*) key1;
151 conspair2 = (COLCONSPAIR*) key2;
152
153 if( conspair1->consindex1 != conspair2->consindex1 )
154 return FALSE;
155
156 if( conspair1->consindex2 != conspair2->consindex2 )
157 return FALSE;
158
159 ratio1 = conspair1->conscoef2 / conspair1->conscoef1;
160 ratio2 = conspair2->conscoef2 / conspair2->conscoef1;
161
162 return SCIPisEQ(scip, ratio1, ratio2);
163}
164
165/** returns the hash value of the key */
166static
167SCIP_DECL_HASHKEYVAL(consPairHashval)
168{ /*lint --e{715}*/
169 COLCONSPAIR* conspair;
170
171 conspair = (COLCONSPAIR*) key;
172
173 return SCIPhashThree(conspair->consindex1, conspair->consindex2, SCIPrealHashCode(conspair->conscoef2 / conspair->conscoef1));
174}
175
176/** calculate maximal activity of one row without one specific column */
177static
179 SCIP* scip, /**< SCIP main data structure */
180 SCIP_MATRIX* matrix, /**< matrix containing the constraints */
181 int row, /**< row index */
182 int col /**< column index */
183 )
184{
185 SCIP_Real* valpnt;
186 int* rowpnt;
187 int* rowend;
188 SCIP_Real maxactivity;
189 SCIP_Real val;
190 SCIP_Real lb;
191 SCIP_Real ub;
192 int c;
193
194 assert(scip != NULL);
195 assert(matrix != NULL);
196
197 maxactivity = 0;
198
199 rowpnt = SCIPmatrixGetRowIdxPtr(matrix, row);
200 rowend = rowpnt + SCIPmatrixGetRowNNonzs(matrix, row);
201 valpnt = SCIPmatrixGetRowValPtr(matrix, row);
202
203 for( ; (rowpnt < rowend); rowpnt++, valpnt++ )
204 {
205 c = *rowpnt;
206 val = *valpnt;
207
208 if( c == col )
209 continue;
210
211 if( val > 0.0 )
212 {
213 ub = SCIPmatrixGetColUb(matrix, c);
214 assert(!SCIPisInfinity(scip, ub));
215
216 maxactivity += val * ub;
217 }
218 else if( val < 0.0 )
219 {
220 lb = SCIPmatrixGetColLb(matrix, c);
221 assert(!SCIPisInfinity(scip, -lb));
222
223 maxactivity += val * lb;
224 }
225 }
226
227 return maxactivity;
228}
229
230/** calculate minimal activity of one row without one specific column */
231static
233 SCIP* scip, /**< SCIP main data structure */
234 SCIP_MATRIX* matrix, /**< matrix containing the constraints */
235 int row, /**< row index */
236 int col /**< column index */
237 )
238{
239 SCIP_Real* valpnt;
240 int* rowpnt;
241 int* rowend;
242 SCIP_Real minactivity;
243 SCIP_Real val;
244 SCIP_Real lb;
245 SCIP_Real ub;
246 int c;
247
248 assert(scip != NULL);
249 assert(matrix != NULL);
250
251 minactivity = 0;
252
253 rowpnt = SCIPmatrixGetRowIdxPtr(matrix, row);
254 rowend = rowpnt + SCIPmatrixGetRowNNonzs(matrix, row);
255 valpnt = SCIPmatrixGetRowValPtr(matrix, row);
256
257 for( ; (rowpnt < rowend); rowpnt++, valpnt++ )
258 {
259 c = *rowpnt;
260 val = *valpnt;
261
262 if( c == col )
263 continue;
264
265 if( val > 0.0 )
266 {
267 lb = SCIPmatrixGetColLb(matrix, c);
268 assert(!SCIPisInfinity(scip, -lb));
269
270 minactivity += val * lb;
271 }
272 else if( val < 0.0 )
273 {
274 ub = SCIPmatrixGetColUb(matrix, c);
275 assert(!SCIPisInfinity(scip, ub));
276
277 minactivity += val * ub;
278 }
279 }
280
281 return minactivity;
282}
283
284/** get minimal and maximal residual activity without one specified column */
285static
287 SCIP* scip, /**< SCIP main data structure */
288 SCIP_MATRIX* matrix, /**< matrix containing the constraints */
289 int col, /**< column index */
290 int row, /**< row index */
291 SCIP_Real val, /**< coefficient of this variable in this row */
292 SCIP_Real* minresactivity, /**< minimum residual activity of this row */
293 SCIP_Real* maxresactivity, /**< maximum residual activity of this row */
294 SCIP_Bool* isminsettoinfinity, /**< flag indicating if minresactiviy is set to infinity */
295 SCIP_Bool* ismaxsettoinfinity /**< flag indicating if maxresactiviy is set to infinity */
296 )
297{
298 SCIP_Real lb;
299 SCIP_Real ub;
300 int nmaxactneginf;
301 int nmaxactposinf;
302 int nminactneginf;
303 int nminactposinf;
304 SCIP_Real maxactivity;
305 SCIP_Real minactivity;
306
307 assert(scip != NULL);
308 assert(matrix != NULL);
309 assert(minresactivity != NULL);
310 assert(maxresactivity != NULL);
311 assert(isminsettoinfinity != NULL);
312 assert(ismaxsettoinfinity != NULL);
313
314 lb = SCIPmatrixGetColLb(matrix, col);
315 ub = SCIPmatrixGetColUb(matrix, col);
316
317 *isminsettoinfinity = FALSE;
318 *ismaxsettoinfinity = FALSE;
319
320 nmaxactneginf = SCIPmatrixGetRowNMaxActNegInf(matrix, row);
321 nmaxactposinf = SCIPmatrixGetRowNMaxActPosInf(matrix, row);
322 nminactneginf = SCIPmatrixGetRowNMinActNegInf(matrix, row);
323 nminactposinf = SCIPmatrixGetRowNMinActPosInf(matrix, row);
324
325 maxactivity = SCIPmatrixGetRowMaxActivity(matrix, row);
326 minactivity = SCIPmatrixGetRowMinActivity(matrix, row);
327
328 if( val >= 0.0 )
329 {
330 if( SCIPisInfinity(scip, ub) )
331 {
332 assert(nmaxactposinf >= 1);
333 if( nmaxactposinf == 1 && nmaxactneginf == 0 )
334 *maxresactivity = getMaxActivitySingleRowWithoutCol(scip, matrix, row, col);
335 else
336 {
337 *maxresactivity = SCIPinfinity(scip);
338 *ismaxsettoinfinity = TRUE;
339 }
340 }
341 else
342 {
343 if( (nmaxactneginf + nmaxactposinf) > 0 )
344 {
345 *maxresactivity = SCIPinfinity(scip);
346 *ismaxsettoinfinity = TRUE;
347 }
348 else
349 *maxresactivity = maxactivity - val * ub;
350 }
351
352 if( SCIPisInfinity(scip, -lb) )
353 {
354 assert(nminactneginf >= 1);
355 if( nminactneginf == 1 && nminactposinf == 0 )
356 *minresactivity = getMinActivitySingleRowWithoutCol(scip, matrix, row, col);
357 else
358 {
359 *minresactivity = -SCIPinfinity(scip);
360 *isminsettoinfinity = TRUE;
361 }
362 }
363 else
364 {
365 if( (nminactneginf + nminactposinf) > 0 )
366 {
367 *minresactivity = -SCIPinfinity(scip);
368 *isminsettoinfinity = TRUE;
369 }
370 else
371 *minresactivity = minactivity - val * lb;
372 }
373 }
374 else
375 {
376 if( SCIPisInfinity(scip, -lb) )
377 {
378 assert(nmaxactneginf >= 1);
379 if( nmaxactneginf == 1 && nmaxactposinf == 0 )
380 *maxresactivity = getMaxActivitySingleRowWithoutCol(scip, matrix, row, col);
381 else
382 {
383 *maxresactivity = SCIPinfinity(scip);
384 *ismaxsettoinfinity = TRUE;
385 }
386 }
387 else
388 {
389 if( (nmaxactneginf + nmaxactposinf) > 0 )
390 {
391 *maxresactivity = SCIPinfinity(scip);
392 *ismaxsettoinfinity = TRUE;
393 }
394 else
395 *maxresactivity = maxactivity - val * lb;
396 }
397
398 if( SCIPisInfinity(scip, ub) )
399 {
400 assert(nminactposinf >= 1);
401 if( nminactposinf == 1 && nminactneginf == 0 )
402 *minresactivity = getMinActivitySingleRowWithoutCol(scip, matrix, row, col);
403 else
404 {
405 *minresactivity = -SCIPinfinity(scip);
406 *isminsettoinfinity = TRUE;
407 }
408 }
409 else
410 {
411 if( (nminactneginf + nminactposinf) > 0 )
412 {
413 *minresactivity = -SCIPinfinity(scip);
414 *isminsettoinfinity = TRUE;
415 }
416 else
417 *minresactivity = minactivity - val * ub;
418 }
419 }
420}
421
422/** calculate the upper and lower bound of one variable from one row */
423static
425 SCIP* scip, /**< SCIP main data structure */
426 SCIP_MATRIX* matrix, /**< matrix containing the constraints */
427 int col, /**< column index of variable */
428 int row, /**< row index */
429 SCIP_Real val, /**< coefficient of this column in this row */
430 SCIP_Real* rowub, /**< upper bound of row */
431 SCIP_Bool* ubfound, /**< flag indicating that an upper bound was calculated */
432 SCIP_Real* rowlb, /**< lower bound of row */
433 SCIP_Bool* lbfound /**< flag indicating that a lower bound was caluclated */
434 )
435{
436 SCIP_Bool isminsettoinfinity;
437 SCIP_Bool ismaxsettoinfinity;
438 SCIP_Real minresactivity;
439 SCIP_Real maxresactivity;
440 SCIP_Real lhs;
441 SCIP_Real rhs;
442
443 assert(rowub != NULL);
444 assert(ubfound != NULL);
445 assert(rowlb != NULL);
446 assert(lbfound != NULL);
447
448 *rowub = SCIPinfinity(scip);
449 *ubfound = FALSE;
450 *rowlb = -SCIPinfinity(scip);
451 *lbfound = FALSE;
452
453 getMinMaxActivityResiduals(scip, matrix, col, row, val,
454 &minresactivity, &maxresactivity,
455 &isminsettoinfinity, &ismaxsettoinfinity);
456
457 lhs = SCIPmatrixGetRowLhs(matrix, row);
458 rhs = SCIPmatrixGetRowRhs(matrix, row);
459
460 if( val > 0.0 )
461 {
462 if( !isminsettoinfinity && !SCIPisInfinity(scip, rhs) )
463 {
464 *rowub = (rhs - minresactivity) / val;
465 *ubfound = TRUE;
466 }
467
468 if( !ismaxsettoinfinity && !SCIPisInfinity(scip, -lhs) )
469 {
470 *rowlb = (lhs - maxresactivity) / val;
471 *lbfound = TRUE;
472 }
473 }
474 else
475 {
476 if( !ismaxsettoinfinity && !SCIPisInfinity(scip, -lhs) )
477 {
478 *rowub = (lhs - maxresactivity) / val;
479 *ubfound = TRUE;
480 }
481
482 if( !isminsettoinfinity && !SCIPisInfinity(scip, rhs) )
483 {
484 *rowlb = (rhs - minresactivity) / val;
485 *lbfound = TRUE;
486 }
487 }
488}
489
490/** detect implied variable bounds */
491static
493 SCIP* scip, /**< SCIP main data structure */
494 SCIP_MATRIX* matrix, /**< matrix containing the constraints */
495 int col, /**< column index for implied free test */
496 SCIP_Bool* ubimplied, /**< flag indicating an implied upper bound */
497 SCIP_Bool* lbimplied /**< flag indicating an implied lower bound */
498 )
499{
500 SCIP_Real* valpnt;
501 int* colpnt;
502 int* colend;
503 SCIP_Real impliedub;
504 SCIP_Real impliedlb;
505 SCIP_Real ub;
506 SCIP_Real lb;
507
508 assert(scip != NULL);
509 assert(matrix != NULL);
510 assert(ubimplied != NULL);
511 assert(lbimplied != NULL);
512
513 *ubimplied = FALSE;
514 impliedub = SCIPinfinity(scip);
515
516 *lbimplied = FALSE;
517 impliedlb = -SCIPinfinity(scip);
518
519 ub = SCIPmatrixGetColUb(matrix, col);
520 lb = SCIPmatrixGetColLb(matrix, col);
521
522 colpnt = SCIPmatrixGetColIdxPtr(matrix, col);
523 colend = colpnt + SCIPmatrixGetColNNonzs(matrix, col);
524 valpnt = SCIPmatrixGetColValPtr(matrix, col);
525 for( ; (colpnt < colend); colpnt++, valpnt++ )
526 {
527 SCIP_Real rowub;
528 SCIP_Bool ubfound;
529 SCIP_Real rowlb;
530 SCIP_Bool lbfound;
531
532 getVarBoundsOfRow(scip, matrix, col, *colpnt, *valpnt, &rowub, &ubfound, &rowlb, &lbfound);
533
534 if( ubfound && (rowub < impliedub) )
535 impliedub = rowub;
536
537 if( lbfound && (rowlb > impliedlb) )
538 impliedlb = rowlb;
539 }
540
541 /* we consider +/-inf bounds as implied bounds */
542 if( SCIPisInfinity(scip, ub) ||
543 (!SCIPisInfinity(scip, ub) && SCIPisLE(scip, impliedub, ub)) )
544 *ubimplied = TRUE;
545
546 if( SCIPisInfinity(scip, -lb) ||
547 (!SCIPisInfinity(scip, -lb) && SCIPisGE(scip, impliedlb, lb)) )
548 *lbimplied = TRUE;
549}
550
551/** y = weight1 * var[colidx1] + var[colidx2] */
552static
554 SCIP* scip, /**< SCIP datastructure */
555 SCIP_MATRIX* matrix, /**< matrix datastructure */
556 SCIP_PRESOLDATA* presoldata, /**< presolver data */
557 SCIP_VAR** vars, /**< the current variables */
558 int colidx1, /**< one of the indexes of column to try nonzero cancellation for */
559 int colidx2, /**< one of the indexes of column to try nonzero cancellation for */
560 SCIP_Bool isimpliedfree, /**< is the aggregated variable implied free? */
561 SCIP_Real weight1 /**< weight variable one in the aggregated expression */
562 )
563{
564 SCIP_VAR* tmpvars[2];
565 SCIP_Real coefs[2];
566 char newvarname[SCIP_MAXSTRLEN];
567 char newconsname[SCIP_MAXSTRLEN];
568 SCIP_CONS* newcons;
569 SCIP_VAR* aggregatedvar;
570 SCIP_VAR* newvar;
571 SCIP_VARTYPE newvartype;
572 SCIP_Real constant;
573 SCIP_Real newlb;
574 SCIP_Real newub;
575 SCIP_Real lhs;
576 SCIP_Real rhs;
577 SCIP_Bool infeasible;
578 SCIP_Bool aggregated;
579#ifndef NDEBUG
580 if( isimpliedfree )
581 {
582 SCIP_Bool lbimplied;
583 SCIP_Bool ubimplied;
584
585 getImpliedBounds(scip, matrix, colidx2, &ubimplied, &lbimplied);
586 assert(lbimplied && ubimplied);
587 }
588#endif
589
590 assert( !SCIPisZero(scip, weight1) );
591
592 presoldata->naggregated += 1;
593 aggregatedvar = vars[colidx2];
594
595 /* if the variable is implied free, we make sure that the columns bounds are removed,
596 * so that subsequent checks for implied bounds do not interfere with the exploitation
597 * of this variables implied bounds
598 */
599 if( isimpliedfree )
600 {
601 SCIPdebugMsg(scip, "remove column bounds of column %d\n", colidx2);
602 SCIPmatrixRemoveColumnBounds(scip, matrix, colidx2);
603 }
604
605 assert(!SCIPdoNotMultaggrVar(scip, aggregatedvar));
606
607 (void) SCIPsnprintf(newvarname, SCIP_MAXSTRLEN, "dualsparsifyvar_%d", presoldata->naggregated);
608
609 constant = 0.0;
610
611 if( weight1 > 0.0 )
612 {
613 if( SCIPisInfinity(scip, -SCIPvarGetLbGlobal(vars[colidx1])) ||
614 SCIPisInfinity(scip, -SCIPvarGetLbGlobal(vars[colidx2])) )
615 newlb = -SCIPinfinity(scip);
616 else
617 newlb = weight1 * SCIPvarGetLbGlobal(vars[colidx1]) + SCIPvarGetLbGlobal(vars[colidx2]);
618
619 if( SCIPisInfinity(scip, SCIPvarGetUbGlobal(vars[colidx1])) ||
620 SCIPisInfinity(scip, SCIPvarGetUbGlobal(vars[colidx2])) )
621 newub = SCIPinfinity(scip);
622 else
623 newub = weight1 * SCIPvarGetUbGlobal(vars[colidx1]) + SCIPvarGetUbGlobal(vars[colidx2]);
624 }
625 else
626 {
627 if( SCIPisInfinity(scip, SCIPvarGetUbGlobal(vars[colidx1])) ||
628 SCIPisInfinity(scip, -SCIPvarGetLbGlobal(vars[colidx2])) )
629 newlb = -SCIPinfinity(scip);
630 else
631 newlb = weight1 * SCIPvarGetUbGlobal(vars[colidx1]) + SCIPvarGetLbGlobal(vars[colidx2]);
632
633 if( SCIPisInfinity(scip, SCIPvarGetLbGlobal(vars[colidx1])) ||
634 SCIPisInfinity(scip, SCIPvarGetUbGlobal(vars[colidx2])) )
635 newub = SCIPinfinity(scip);
636 else
637 newub = weight1 * SCIPvarGetLbGlobal(vars[colidx1]) + SCIPvarGetUbGlobal(vars[colidx2]);
638 }
639
640 if( SCIPvarIsIntegral(aggregatedvar) )
641 newvartype = (SCIPvarGetType(aggregatedvar) == SCIP_VARTYPE_IMPLINT) ?
643 else
644 newvartype = SCIP_VARTYPE_CONTINUOUS;
645
646 lhs = SCIPvarGetLbGlobal(vars[colidx2]);
647 rhs = SCIPvarGetUbGlobal(vars[colidx2]);
648
649 SCIP_CALL( SCIPcreateVar(scip, &newvar, newvarname, newlb, newub, 0.0, newvartype,
650 SCIPvarIsInitial(aggregatedvar), SCIPvarIsRemovable(aggregatedvar), NULL, NULL, NULL, NULL, NULL) );
651 SCIP_CALL( SCIPaddVar(scip, newvar) );
652
653 /* set the debug solution value for the new variable */
654#ifdef WITH_DEBUG_SOLUTION
655 if( SCIPdebugIsMainscip(scip) )
656 {
657 SCIP_Real val1;
658 SCIP_Real val2;
659
660 SCIP_CALL( SCIPdebugGetSolVal(scip, vars[colidx1], &val1) );
661 SCIP_CALL( SCIPdebugGetSolVal(scip, vars[colidx2], &val2) );
662 SCIP_CALL( SCIPdebugAddSolVal(scip, newvar, weight1 * val1 + val2) );
663
664 SCIPdebugMsg(scip, "set debug solution value of %s to %g\n", SCIPvarGetName(newvar), weight1 * val1 + val2);
665 }
666#endif
667
668 tmpvars[0] = vars[colidx1];
669 tmpvars[1] = newvar;
670 coefs[0] = -weight1;
671 coefs[1] = 1.0;
672
673 SCIP_CALL( SCIPmultiaggregateVar(scip, aggregatedvar, 2, tmpvars, coefs, constant, &infeasible, &aggregated) );
674
675 assert(!infeasible);
676 assert(aggregated);
677
678 vars[colidx2] = newvar;
679
680 /* create a linear constraint that ensures that var[colidx2].lb <= y - weight1 * var[colidx1] <= var[colidx2].ub;
681 * note that it might happen that vars[colidx2] is not implied free even though it has infinite bounds because
682 * getImpliedBounds() considers infinite bounds to be implied
683 */
684 if( !isimpliedfree && (!SCIPisInfinity(scip, rhs) || !SCIPisInfinity(scip, -lhs)) )
685 {
686 SCIPdebugMsg(scip, "create a linear constraint to ensure %g <= %g %s + %g %s <= %g\n", lhs, coefs[0], SCIPvarGetName(tmpvars[0]),
687 coefs[1], SCIPvarGetName(tmpvars[1]), rhs);
688 (void) SCIPsnprintf(newconsname, SCIP_MAXSTRLEN, "dualsparsifycons_%d", presoldata->naggregated);
689
690 SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, newconsname, 2, tmpvars, coefs,
691 lhs, rhs, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
692 SCIP_CALL( SCIPaddCons(scip, newcons) );
693
694 SCIPdebugPrintCons(scip, newcons, NULL);
695
696 SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
697 }
698
699 SCIP_CALL( SCIPreleaseVar(scip, &newvar) );
700
701 return SCIP_OKAY;
702}
703
704/** try nonzero cancellation for given column */
705static
707 SCIP* scip, /**< SCIP datastructure */
708 SCIP_MATRIX* matrix, /**< the constraint matrix */
709 SCIP_PRESOLDATA* presoldata, /**< presolver data */
710 SCIP_HASHTABLE* pairtable, /**< the hashtable containing COLCONSPAIR's of equations */
711 SCIP_Bool* ishashingcols, /**< array to indicates whether it is impliedfree or not */
712 SCIP_VAR** vars, /**< array to store the current variables */
713 SCIP_Bool* isblockedvar, /**< array to indicates whether it is blocked or not */
714 int colidx, /**< index of column to try nonzero cancellation for */
715 int maxcontfillin, /**< maximal fill-in allowed for continuous variables */
716 int maxintfillin, /**< maximal fill-in allowed for integral variables */
717 int maxbinfillin, /**< maximal fill-in allowed for binary variables */
718 int maxconsiderednonzeros, /**< maximal number of nonzeros to consider for cancellation */
719 SCIP_Bool preserveintcoefs, /**< only perform nonzero cancellation if integrality of coefficients is preserved? */
720 SCIP_Longint* nuseless, /**< pointer to update number of useless hashtable retrieves */
721 int* nchgcoefs, /**< pointer to update number of changed coefficients */
722 int* ncanceled, /**< pointer to update number of canceled nonzeros */
723 int* nfillin, /**< pointer to update the produced fill-in */
724 SCIP_Bool isaddedcons /**< whether a linear constraint required to added to keep the validity */
725 )
726{
727 SCIP_VAR* cancelvar;
728 SCIP_Real* cancelcolvals;
729 SCIP_Real* colvalptr;
730 SCIP_Real* tmpvals;
731 SCIP_Real* scores;
732 int* cancelcolinds;
733 int* colidxptr;
734 int* tmpinds;
735 SCIP_Real bestcancelrate;
736 SCIP_Real bestscale;
737 SCIP_Real ncols;
738 SCIP_Bool colishashing;
739 SCIP_Bool swapped = FALSE;
740 int cancelcollen;
741 int bestnfillin;
742 int nretrieves;
743 int maxfillin;
744 int bestcand;
745 int nchgcoef;
746
747 ncols = SCIPmatrixGetNColumns(matrix);
748 colishashing = ishashingcols[colidx];
749 cancelcollen = SCIPmatrixGetColNNonzs(matrix, colidx);
750 colidxptr = SCIPmatrixGetColIdxPtr(matrix, colidx);
751 colvalptr = SCIPmatrixGetColValPtr(matrix, colidx);
752 cancelvar = vars[colidx];
753
754 if( SCIPvarIsIntegral(cancelvar) )
755 {
756 if( SCIPvarIsBinary(cancelvar) )
757 maxfillin = maxbinfillin;
758 else
759 maxfillin = maxintfillin;
760 }
761 else
762 maxfillin = maxcontfillin;
763
764 SCIP_CALL( SCIPduplicateBufferArray(scip, &cancelcolinds, colidxptr, cancelcollen) );
765 SCIP_CALL( SCIPduplicateBufferArray(scip, &cancelcolvals, colvalptr, cancelcollen) );
766 SCIP_CALL( SCIPallocBufferArray(scip, &tmpinds, cancelcollen) );
767 SCIP_CALL( SCIPallocBufferArray(scip, &tmpvals, cancelcollen) );
768 SCIP_CALL( SCIPallocBufferArray(scip, &scores, cancelcollen) );
769
770 nchgcoef = 0;
771 nretrieves = 0;
772 while( TRUE ) /*lint !e716 */
773 {
774 COLCONSPAIR colconspair;
775 int maxlen;
776 int i;
777 int j;
778
779 bestcand = -1;
780 bestnfillin = 0;
781 bestscale = 1.0;
782 bestcancelrate = 0.0;
783
784 /* sort the rows non-decreasingly by number of nonzeros
785 * if the number of nonzeros, we use the colindex as tie-breaker
786 */
787 for( i = 0; i < cancelcollen; ++i )
788 {
789 tmpinds[i] = i;
790 scores[i] = -SCIPmatrixGetRowNNonzs(matrix, cancelcolinds[i]) - 1.0 * cancelcolinds[i] / (ncols);
791 }
792 SCIPsortRealInt(scores, tmpinds, cancelcollen);
793
794 maxlen = cancelcollen;
795 if( maxconsiderednonzeros >= 0 )
796 maxlen = MIN(cancelcollen, maxconsiderednonzeros);
797
798 for( i = 0; i < maxlen; ++i )
799 {
800 for( j = i + 1; j < maxlen; ++j )
801 {
802 COLCONSPAIR* hashingcolconspair;
803 SCIP_VAR* hashingcolvar;
804 SCIP_Real* hashingcolvals;
805 int* hashingcolinds;
806 SCIP_Real hashingcollb;
807 SCIP_Real hashingcolub;
808 SCIP_Real cancelrate;
809 SCIP_Real rowlhs;
810 SCIP_Real rowrhs;
811 SCIP_Real scale;
812 SCIP_Bool hashingcolisbin;
813 SCIP_Bool abortpair;
814 int hashingcollen;
815 int ntotfillin;
816 int ncancel;
817 int a,b;
818 int i1,i2;
819
820 i1 = tmpinds[i];
821 i2 = tmpinds[j];
822
823 assert(cancelcolinds[i] < cancelcolinds[j]);
824
825 if( cancelcolinds[i1] < cancelcolinds[i2] )
826 {
827 colconspair.consindex1 = cancelcolinds[i1];
828 colconspair.consindex2 = cancelcolinds[i2];
829 colconspair.conscoef1 = cancelcolvals[i1];
830 colconspair.conscoef2 = cancelcolvals[i2];
831 }
832 else
833 {
834 colconspair.consindex1 = cancelcolinds[i2];
835 colconspair.consindex2 = cancelcolinds[i1];
836 colconspair.conscoef1 = cancelcolvals[i2];
837 colconspair.conscoef2 = cancelcolvals[i1];
838 }
839
840 hashingcolconspair = (COLCONSPAIR*)SCIPhashtableRetrieve(pairtable, (void*) &colconspair);
841 nretrieves++;
842
843 if( hashingcolconspair == NULL ||
844 hashingcolconspair->colindex == colidx || isblockedvar[hashingcolconspair->colindex] )
845 continue;
846
847 /* if the column we want to cancel is a hashing column (which we stored for canceling other columns),
848 * we will only use the hashing columns for canceling with less nonzeros and if the number of nonzeros
849 * is equal we use the colindex as tie-breaker to avoid cyclic nonzero cancellation
850 */
851 hashingcollen = SCIPmatrixGetColNNonzs(matrix, hashingcolconspair->colindex);
852 if( colishashing && (cancelcollen < hashingcollen ||
853 (cancelcollen == hashingcollen && colidx < hashingcolconspair->colindex)) )
854 continue;
855
856 hashingcolvals = SCIPmatrixGetColValPtr(matrix, hashingcolconspair->colindex);
857 hashingcolinds = SCIPmatrixGetColIdxPtr(matrix, hashingcolconspair->colindex);
858 hashingcolvar = vars[hashingcolconspair->colindex];
859 hashingcollb = SCIPvarGetLbGlobal(hashingcolvar);
860 hashingcolub = SCIPvarGetUbGlobal(hashingcolvar);
861 hashingcolisbin = (SCIPvarGetType(hashingcolvar) == SCIP_VARTYPE_BINARY) ||
862 (SCIPvarIsIntegral(hashingcolvar) && SCIPisZero(scip, hashingcollb) &&
863 SCIPisEQ(scip, hashingcolub, 1.0));
864 scale = -colconspair.conscoef1 / hashingcolconspair->conscoef1;
865
866 if( SCIPisZero(scip, scale) )
867 continue;
868
869 if( REALABS(scale) > MAXSCALE )
870 continue;
871
872 /* @todo do more reduction if knspsack constraint handler supports downgrading constraint,
873 * i.e., converting into a linear constraint
874 */
875 if( hashingcolisbin )
876 continue;
877 else if( SCIPvarIsIntegral(hashingcolvar) )
878 {
879 if( SCIPvarIsIntegral(cancelvar) )
880 {
881 /* skip if the hashing variable is an integer variable and
882 * the canceled variable is an implicit integer variable
883 */
884 if( (SCIPvarGetType(hashingcolvar) != SCIP_VARTYPE_IMPLINT) &&
885 (SCIPvarGetType(cancelvar) == SCIP_VARTYPE_IMPLINT) )
886 continue;
887
888 /* skip if the scale is non-integral */
889 if( !SCIPisIntegral(scip, scale) )
890 continue;
891
892 /* round scale to be exactly integral */
893 scale = floor(scale + 0.5);
894 }
895 /* skip if the canceled variable is a continuous variable */
896 else
897 continue;
898 }
899
900 a = 0;
901 b = 0;
902 ncancel = 0;
903 ntotfillin = 0;
904 abortpair = FALSE;
905
906 while( a < cancelcollen && b < hashingcollen )
907 {
908 if( cancelcolinds[a] == hashingcolinds[b] )
909 {
910 SCIP_Real newcoef;
911
912 newcoef = cancelcolvals[a] + scale * hashingcolvals[b];
913
914 /* check if coefficient is canceled */
915 if( SCIPisZero(scip, newcoef) )
916 {
917 ++ncancel;
918 }
919 /* otherwise, check if integral coefficients are preserved if the column is integral */
920 else if( (preserveintcoefs && SCIPvarIsIntegral(cancelvar) &&
921 SCIPisIntegral(scip, cancelcolvals[a]) && !SCIPisIntegral(scip, newcoef)) )
922 {
923 abortpair = TRUE;
924 break;
925 }
926 /* finally, check if locks could be modified in a bad way due to flipped signs */
927 else if( COPYSIGN(1.0, newcoef) != COPYSIGN(1.0, cancelcolvals[a]) ) /*lint !e777*/
928 {
929 /* do not flip signs for non-canceled coefficients if this adds a lock to a variable that
930 * had at most one lock in that direction before, except if the other direction gets unlocked
931 */
932 rowrhs = SCIPmatrixGetRowRhs(matrix, cancelcolinds[a]);
933 rowlhs = SCIPmatrixGetRowLhs(matrix, cancelcolinds[a]);
934 if( (cancelcolvals[a] > 0.0 && ! SCIPisInfinity(scip, rowrhs)) ||
935 (cancelcolvals[a] < 0.0 && ! SCIPisInfinity(scip, -rowlhs)) )
936 {
937 /* if we get into this case the variable had a positive coefficient in a <= constraint or
938 * a negative coefficient in a >= constraint, e.g. an uplock. If this was the only uplock
939 * we do not abort their cancelling, otherwise we abort if we had a single or no downlock
940 * and add one
941 */
942 if( presoldata->preservegoodlocks && (SCIPmatrixGetColNUplocks(matrix, colidx) > 1 &&
943 SCIPmatrixGetColNDownlocks(matrix, colidx) <= 1) )
944 {
945 abortpair = TRUE;
946 break;
947 }
948 }
949
950 if( (cancelcolvals[a] < 0.0 && ! SCIPisInfinity(scip, rowrhs)) ||
951 (cancelcolvals[a] > 0.0 && ! SCIPisInfinity(scip, -rowlhs)) )
952 {
953 /* symmetric case where the variable had a downlock */
954 if( presoldata->preservegoodlocks && (SCIPmatrixGetColNDownlocks(matrix, colidx) > 1 &&
955 SCIPmatrixGetColNUplocks(matrix, colidx) <= 1) )
956 {
957 abortpair = TRUE;
958 break;
959 }
960 }
961 }
962
963 ++a;
964 ++b;
965 }
966 else if( cancelcolinds[a] < hashingcolinds[b] )
967 {
968 ++a;
969 }
970 else
971 {
972 SCIP_Real newcoef;
973
974 newcoef = scale * hashingcolvals[b];
975 rowrhs = SCIPmatrixGetRowRhs(matrix, hashingcolinds[b]);
976 rowlhs = SCIPmatrixGetRowLhs(matrix, hashingcolinds[b]);
977
978 if( (newcoef > 0.0 && ! SCIPisInfinity(scip, rowrhs)) ||
979 (newcoef < 0.0 && ! SCIPisInfinity(scip, -rowlhs)) )
980 {
981 if( presoldata->preservegoodlocks && SCIPmatrixGetColNUplocks(matrix, colidx) <= 1 )
982 {
983 abortpair = TRUE;
984 ++b;
985 break;
986 }
987 }
988
989 if( (newcoef < 0.0 && ! SCIPisInfinity(scip, rowrhs)) ||
990 (newcoef > 0.0 && ! SCIPisInfinity(scip, -rowlhs)) )
991 {
992 if( presoldata->preservegoodlocks && SCIPmatrixGetColNDownlocks(matrix, colidx) <= 1 )
993 {
994 abortpair = TRUE;
995 ++b;
996 break;
997 }
998 }
999
1000 ++b;
1001
1002 if( ++ntotfillin > maxfillin )
1003 {
1004 abortpair = TRUE;
1005 break;
1006 }
1007 }
1008 }
1009
1010 if( abortpair )
1011 continue;
1012
1013 while( b < hashingcollen )
1014 {
1015 ++b;
1016
1017 if( ++ntotfillin > maxfillin )
1018 break;
1019 }
1020CHECKFILLINAGAIN:
1021 if( ntotfillin > maxfillin || ntotfillin >= ncancel )
1022 continue;
1023
1024 cancelrate = (ncancel - ntotfillin) / (SCIP_Real) cancelcollen;
1025
1026 /* if a linear constraint is needed to keep the validity, we require a large nonzero cancellation */
1027 if( isaddedcons && (ncancel - ntotfillin < presoldata->mineliminatednonzeros) )
1028 continue;
1029
1030 if( cancelrate > bestcancelrate )
1031 {
1032 if( ishashingcols[hashingcolconspair->colindex] )
1033 {
1034 SCIP_Bool lbimplied;
1035 SCIP_Bool ubimplied;
1036
1037 /* recompute whether a variable is still implied free; after some previous multi-aggregations of
1038 * some variables, it might be that other variables that are contained in the same linear rows of the
1039 * matrix are not implied free anymore (see #2971)
1040 */
1041 getImpliedBounds(scip, matrix, hashingcolconspair->colindex, &ubimplied, &lbimplied);
1042
1043 if( !lbimplied || !ubimplied )
1044 {
1045 ishashingcols[hashingcolconspair->colindex] = FALSE;
1046 ntotfillin += 2;
1047 goto CHECKFILLINAGAIN;
1048 }
1049 }
1050
1051 bestnfillin = ntotfillin;
1052 bestcand = hashingcolconspair->colindex;
1053 bestscale = scale;
1054 bestcancelrate = cancelrate;
1055
1056 /* stop looking if the current candidate does not create any fill-in or alter coefficients */
1057 if( cancelrate == 1.0 )
1058 break;
1059 }
1060
1061 /* we accept the best candidate immediately if it does not create any fill-in or alter coefficients */
1062 if( bestcand != -1 && bestcancelrate == 1.0 )
1063 break;
1064 }
1065 }
1066
1067 if( bestcand != -1 )
1068 {
1069 SCIP_Real* hashingcolvals;
1070 int* hashingcolinds;
1071 int hashingcollen;
1072 int tmpcollen;
1073 int a;
1074 int b;
1075
1076 SCIPdebugMsg(scip, "cancelcol %d (%s) candidate column %d (%s) (bestcancelrate = %g, bestscale = %g)\n",
1077 colidx, SCIPvarGetName(cancelvar), bestcand, SCIPvarGetName(vars[bestcand]), bestcancelrate, bestscale);
1078
1079 hashingcolvals = SCIPmatrixGetColValPtr(matrix, bestcand);
1080 hashingcolinds = SCIPmatrixGetColIdxPtr(matrix, bestcand);
1081 hashingcollen = SCIPmatrixGetColNNonzs(matrix, bestcand);
1082
1083 a = 0;
1084 b = 0;
1085 tmpcollen = 0;
1086
1087 while( a < cancelcollen && b < hashingcollen )
1088 {
1089 if( cancelcolinds[a] == hashingcolinds[b] )
1090 {
1091 SCIP_Real val = cancelcolvals[a] + bestscale * hashingcolvals[b];
1092
1093 if( !SCIPisZero(scip, val) )
1094 {
1095 tmpinds[tmpcollen] = cancelcolinds[a];
1096 tmpvals[tmpcollen] = val;
1097 ++tmpcollen;
1098 }
1099 ++nchgcoef;
1100
1101 ++a;
1102 ++b;
1103 }
1104 else if( cancelcolinds[a] < hashingcolinds[b] )
1105 {
1106 tmpinds[tmpcollen] = cancelcolinds[a];
1107 tmpvals[tmpcollen] = cancelcolvals[a];
1108 ++tmpcollen;
1109 ++a;
1110 }
1111 else
1112 {
1113 tmpinds[tmpcollen] = hashingcolinds[b];
1114 tmpvals[tmpcollen] = hashingcolvals[b] * bestscale;
1115 ++nchgcoef;
1116 ++tmpcollen;
1117 ++b;
1118 }
1119 }
1120
1121 while( a < cancelcollen )
1122 {
1123 tmpinds[tmpcollen] = cancelcolinds[a];
1124 tmpvals[tmpcollen] = cancelcolvals[a];
1125 ++tmpcollen;
1126 ++a;
1127 }
1128
1129 while( b < hashingcollen )
1130 {
1131 tmpinds[tmpcollen] = hashingcolinds[b];
1132 tmpvals[tmpcollen] = hashingcolvals[b] * bestscale;
1133 ++nchgcoef;
1134 ++tmpcollen;
1135 ++b;
1136 }
1137
1138 /* update fill-in counter */
1139 *nfillin += bestnfillin;
1140
1141 /* swap the temporary arrays so that the cancelcolinds and cancelcolvals arrays, contain the new
1142 * changed column, and the tmpinds and tmpvals arrays can be overwritten in the next iteration
1143 */
1144 SCIPswapPointers((void**) &tmpinds, (void**) &cancelcolinds);
1145 SCIPswapPointers((void**) &tmpvals, (void**) &cancelcolvals);
1146 swapped = ! swapped;
1147 cancelcollen = tmpcollen;
1148 SCIP_CALL( aggregation(scip, matrix, presoldata, vars, colidx, bestcand, ishashingcols[bestcand], -bestscale) );
1149
1150 /* the newly created variable is now at the position bestcand and is assumed to have the same coefficients.
1151 * this is not the case if the variable is not implied free since then a new constraint was added and the
1152 * nonzero fillin would not be counted correctly if we do not block this variable
1153 */
1154 if( !ishashingcols[bestcand] )
1155 isblockedvar[bestcand] = TRUE;
1156 }
1157 else
1158 break;
1159 }
1160
1161 if( nchgcoef != 0 )
1162 {
1163 /* update counters */
1164 *nchgcoefs += nchgcoef;
1165 *ncanceled += SCIPmatrixGetColNNonzs(matrix, colidx) - cancelcollen;
1166
1167 isblockedvar[colidx] = TRUE;
1168
1169 /* if successful, decrease the useless hashtable retrieves counter; the rationale here is that we want to keep
1170 * going if, after many useless calls that almost exceeded the budget, we finally reach a useful section; but we
1171 * don't allow a negative build-up for the case that the useful section is all at the beginning and we just want
1172 * to quit quickly afterwards
1173 */
1174 *nuseless -= nretrieves;
1175 *nuseless = MAX(*nuseless, 0);
1176 }
1177 else
1178 {
1179 /* if not successful, increase useless hashtable retrieves counter */
1180 *nuseless += nretrieves;
1181 }
1182
1183 SCIPfreeBufferArray(scip, &scores);
1184 if( swapped )
1185 {
1186 SCIPfreeBufferArray(scip, &cancelcolvals);
1187 SCIPfreeBufferArray(scip, &cancelcolinds);
1188 SCIPfreeBufferArray(scip, &tmpvals);
1189 SCIPfreeBufferArray(scip, &tmpinds);
1190 }
1191 else
1192 {
1193 SCIPfreeBufferArray(scip, &tmpvals);
1194 SCIPfreeBufferArray(scip, &tmpinds);
1195 SCIPfreeBufferArray(scip, &cancelcolvals);
1196 SCIPfreeBufferArray(scip, &cancelcolinds);
1197 }
1198
1199 return SCIP_OKAY;
1200}
1201
1202/** updates failure counter after one execution */
1203static
1205 SCIP_PRESOLDATA* presoldata, /**< presolver data */
1206 SCIP_Bool success /**< was this execution successful? */
1207 )
1208{
1209 assert(presoldata != NULL);
1210
1211 if( success )
1212 {
1213 presoldata->nfailures = 0;
1214 presoldata->nwaitingcalls = 0;
1215 }
1216 else
1217 {
1218 presoldata->nfailures++;
1219 presoldata->nwaitingcalls = (int)(presoldata->waitingfac*(SCIP_Real)presoldata->nfailures);
1220 }
1221}
1222
1223/*
1224 * Callback methods of presolver
1225 */
1226
1227/** copy method for constraint handler plugins (called when SCIP copies plugins) */
1228static
1229SCIP_DECL_PRESOLCOPY(presolCopyDualsparsify)
1230{
1231 SCIP_PRESOLDATA* presoldata;
1232
1233 assert(scip != NULL);
1234 assert(presol != NULL);
1235 assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
1236
1237 /* call inclusion method of presolver if copying is enabled */
1238 presoldata = SCIPpresolGetData(presol);
1239 assert(presoldata != NULL);
1240 if( presoldata->enablecopy )
1241 {
1243 }
1244
1245 return SCIP_OKAY;
1246}
1247
1248
1249/** execution method of presolver */
1250static
1251SCIP_DECL_PRESOLEXEC(presolExecDualsparsify)
1252{ /*lint --e{715}*/
1253 SCIP_MATRIX* matrix;
1254 int* perm;
1255 int* colidxsorted;
1256 int* colsparsity;
1257 SCIP_Real* scores;
1258 COLCONSPAIR* conspairs;
1259 SCIP_HASHTABLE* pairtable;
1260 SCIP_PRESOLDATA* presoldata;
1261 SCIP_Bool* ishashingcols;
1262 SCIP_Bool* isblockedvar;
1263 SCIP_VAR** vars;
1264 SCIP_Longint maxuseless;
1265 SCIP_Longint nuseless;
1266 SCIP_Bool initialized;
1267 SCIP_Bool complete;
1268 SCIP_Bool infeasible;
1269 int ncols;
1270 int c;
1271 int i;
1272 int j;
1273 int conspairssize;
1274 int nconspairs;
1275 int numcancel;
1276 int nfillin;
1277
1278 assert(result != NULL);
1279
1280 *result = SCIP_DIDNOTRUN;
1281
1282 if( SCIPdoNotAggr(scip) )
1283 return SCIP_OKAY;
1284
1285 /* If restart is performed, some cuts will be tranformed into linear constraints.
1286 * However, SCIPmatrixCreate() only collects the original constraints (not the constraints transformed from cuts)
1287 * For this reason, we only perform this method in the first run of branch-and-cut.
1288 * */
1289 if( SCIPgetNRuns(scip) > 1 )
1290 return SCIP_OKAY;
1291
1292 presoldata = SCIPpresolGetData(presol);
1293
1294 if( presoldata->nwaitingcalls > 0 )
1295 {
1296 presoldata->nwaitingcalls--;
1297 SCIPdebugMsg(scip, "skipping dualsparsify: nfailures=%d, nwaitingcalls=%d\n", presoldata->nfailures,
1298 presoldata->nwaitingcalls);
1299 return SCIP_OKAY;
1300 }
1301
1302 SCIPdebugMsg(scip, "starting dualsparsify. . .\n");
1303 *result = SCIP_DIDNOTFIND;
1304
1305 matrix = NULL;
1306 SCIP_CALL( SCIPmatrixCreate(scip, &matrix, TRUE, &initialized, &complete, &infeasible,
1307 naddconss, ndelconss, nchgcoefs, nchgbds, nfixedvars) );
1308
1309 /* if infeasibility was detected during matrix creation or
1310 * matrix creation is incomplete, return here.
1311 */
1312 if( infeasible || !complete )
1313 {
1314 if( initialized )
1315 SCIPmatrixFree(scip, &matrix);
1316
1317 if( infeasible )
1318 *result = SCIP_CUTOFF;
1319
1320 return SCIP_OKAY;
1321 }
1322
1323 if( !initialized )
1324 return SCIP_OKAY;
1325
1326 ncols = SCIPmatrixGetNColumns(matrix);
1327
1328 /* sort columns by row indices */
1329 for( i = 0; i < ncols; i++ )
1330 {
1331 int* colpnt = SCIPmatrixGetColIdxPtr(matrix, i);
1332 SCIP_Real* valpnt = SCIPmatrixGetColValPtr(matrix, i);
1333 SCIPsortIntReal(colpnt, valpnt, SCIPmatrixGetColNNonzs(matrix, i));
1334 }
1335
1338 SCIP_CALL( SCIPallocBufferArray(scip, &ishashingcols, SCIPmatrixGetNColumns(matrix)) );
1340 SCIP_CALL( SCIPallocBufferArray(scip, &isblockedvar, SCIPmatrixGetNColumns(matrix)) );
1341
1342 /* loop over all columns and create cons pairs */
1343 conspairssize = 0;
1344 nconspairs = 0;
1345 conspairs = NULL;
1347 SCIPhashGetKeyStandard, consPairsEqual, consPairHashval, (void*) scip) );
1348
1349 /* collect implied free variables and their number of nonzeros */
1350 for( c = 0; c < ncols; c++ )
1351 {
1352 SCIP_Bool lbimplied;
1353 SCIP_Bool ubimplied;
1354 int nnonz;
1355
1356 vars[c] = SCIPmatrixGetVar(matrix, c);
1357
1358 /* if the locks do not match do not consider the column for sparsification */
1359 if( SCIPmatrixDownlockConflict(matrix, c) || SCIPmatrixUplockConflict(matrix, c) )
1360 {
1361 isblockedvar[c] = TRUE;
1362 ishashingcols[c] = FALSE;
1363 continue;
1364 }
1365
1366 /* skip if the variable is not allowed to be multi-aggregated */
1367 if( SCIPdoNotMultaggrVar(scip, vars[c]) )
1368 {
1369 isblockedvar[c] = TRUE;
1370 ishashingcols[c] = FALSE;
1371 continue;
1372 }
1373
1374 nnonz = SCIPmatrixGetColNNonzs(matrix, c);
1375
1376 getImpliedBounds(scip, matrix, c, &ubimplied, &lbimplied);
1377
1378 ishashingcols[c] = FALSE;
1379
1380 if( lbimplied && ubimplied )
1381 ishashingcols[c] = TRUE;
1382
1383 isblockedvar[c] = FALSE;
1384
1385 /* only consider implied free variables
1386 * skip singleton variables, because either the constraint is redundant
1387 * or the variables can be canceled by variable substitution
1388 */
1389 if( nnonz >= 2 && (lbimplied && ubimplied) )
1390 {
1391 SCIP_Real* colvals;
1392 int* colinds;
1393 int failshift;
1394 int npairs;
1395
1396 colinds = SCIPmatrixGetColIdxPtr(matrix, c);
1397 colvals = SCIPmatrixGetColValPtr(matrix, c);
1398
1399 /* sort the rows non-decreasingly by number of nonzeros
1400 * if the number of nonzeros is equal, we use the colindex as tie-breaker
1401 */
1402 for( i = 0; i < nnonz; ++i )
1403 {
1404 perm[i] = i;
1405 scores[i] = -SCIPmatrixGetRowNNonzs(matrix, colinds[i]) - 1.0 *colinds[i] / ncols;
1406 }
1407 SCIPsortRealInt(scores, perm, nnonz);
1408
1409 if( presoldata->maxconsiderednonzeros >= 0 )
1410 nnonz = MIN(nnonz, presoldata->maxconsiderednonzeros);
1411
1412 npairs = (nnonz * (nnonz - 1)) / 2;
1413 if( nconspairs + npairs > conspairssize )
1414 {
1415 int newsize = SCIPcalcMemGrowSize(scip, nconspairs + npairs);
1416 SCIP_CALL( SCIPreallocBufferArray(scip, &conspairs, newsize) );
1417 conspairssize = newsize;
1418 }
1419
1420 /* if we are called after one or more failures, i.e., executions without finding cancellations, then we
1421 * shift the section of nonzeros considered; in the case that the maxconsiderednonzeros limit is hit, this
1422 * results in different constraint pairs being tried and avoids trying the same useless cancellations
1423 * repeatedly
1424 */
1425 failshift = presoldata->nfailures*presoldata->maxconsiderednonzeros;
1426
1427 for( i = 0; i < nnonz; ++i )
1428 {
1429 for( j = i + 1; j < nnonz; ++j )
1430 {
1431 int i1;
1432 int i2;
1433
1434 assert(nconspairs < conspairssize);
1435 assert(conspairs != NULL);
1436
1437 i1 = perm[(i + failshift) % nnonz];
1438 i2 = perm[(j + failshift) % nnonz];
1439 /* coverity[var_deref_op] */
1440 conspairs[nconspairs].colindex = c;
1441
1442 if( colinds[i1] < colinds[i2])
1443 {
1444 conspairs[nconspairs].consindex1 = colinds[i1];
1445 conspairs[nconspairs].consindex2 = colinds[i2];
1446 conspairs[nconspairs].conscoef1 = colvals[i1];
1447 conspairs[nconspairs].conscoef2 = colvals[i2];
1448 }
1449 else
1450 {
1451 conspairs[nconspairs].consindex1 = colinds[i2];
1452 conspairs[nconspairs].consindex2 = colinds[i1];
1453 conspairs[nconspairs].conscoef1 = colvals[i2];
1454 conspairs[nconspairs].conscoef2 = colvals[i1];
1455 }
1456 ++nconspairs;
1457 }
1458 }
1459 }
1460 }
1461
1462 /* insert conspairs into hash table */
1463 for( c = 0; c < nconspairs; ++c )
1464 {
1465 COLCONSPAIR* otherconspair;
1466 SCIP_Bool insert;
1467
1468 assert(conspairs != NULL);
1469
1470 insert = TRUE;
1471
1472 /* check if this pair is already contained in the hash table;
1473 * The loop is required due to the non-transitivity of the hash functions
1474 */
1475 while( (otherconspair = (COLCONSPAIR*)SCIPhashtableRetrieve(pairtable, (void*) &conspairs[c])) != NULL )
1476 {
1477 /* if the previous constraint pair has fewer or the same number of nonzeros in the attached column
1478 * we keep that pair and skip this one
1479 */
1480 if( SCIPmatrixGetColNNonzs(matrix, otherconspair->colindex) <=
1481 SCIPmatrixGetColNNonzs(matrix, conspairs[c].colindex) )
1482 {
1483 insert = FALSE;
1484 break;
1485 }
1486
1487 /* this pairs column has fewer nonzeros, so remove the other pair from the hash table and loop */
1488 SCIP_CALL( SCIPhashtableRemove(pairtable, (void*) otherconspair) );
1489 }
1490
1491 if( insert )
1492 {
1493 SCIP_CALL( SCIPhashtableInsert(pairtable, (void*) &conspairs[c]) );
1494 }
1495 }
1496
1497 /* sort cols according to decreasing sparsity */
1498 SCIP_CALL( SCIPallocBufferArray(scip, &colidxsorted, ncols) );
1499 SCIP_CALL( SCIPallocBufferArray(scip, &colsparsity, ncols) );
1500 for( c = 0; c < ncols; ++c )
1501 {
1502 colidxsorted[c] = c;
1503 colsparsity[c] = -SCIPmatrixGetColNNonzs(matrix, c);
1504 }
1505 SCIPsortIntInt(colsparsity, colidxsorted, ncols);
1506
1507 /* loop over the columns and cancel nonzeros until maximum number of retrieves is reached */
1508 maxuseless = (SCIP_Longint)(presoldata->maxretrievefac * (SCIP_Real)ncols);
1509 nuseless = 0;
1510 numcancel = 0;
1511 nfillin = 0;
1512 for( c = 0; c < ncols && nuseless <= maxuseless && !SCIPisStopped(scip); c++ )
1513 {
1514 int colidx;
1515
1516 colidx = colidxsorted[c];
1517
1518 if( isblockedvar[colidx] )
1519 continue;
1520
1521 /* since the function parameters for the max fillin are unsigned we do not need to handle the
1522 * unlimited (-1) case due to implicit conversion rules */
1523 SCIP_CALL( cancelCol(scip, matrix, presoldata, pairtable, ishashingcols, vars, isblockedvar, colidx, \
1524 presoldata->maxcontfillin == -1 ? INT_MAX : presoldata->maxcontfillin, \
1525 presoldata->maxintfillin == -1 ? INT_MAX : presoldata->maxintfillin, \
1526 presoldata->maxbinfillin == -1 ? INT_MAX : presoldata->maxbinfillin, \
1527 presoldata->maxconsiderednonzeros, presoldata->preserveintcoefs, \
1528 &nuseless, nchgcoefs, &numcancel, &nfillin, FALSE) );
1529 }
1530
1531 if( numcancel > 0 )
1532 {
1534 " (%.1fs) dualsparsify: %d nonzeros canceled\n", SCIPgetSolvingTime(scip), numcancel);
1535 *result = SCIP_SUCCESS;
1536 }
1537 else /* do reductions on variables that contain larger nonzero entries */
1538 {
1539 SCIPhashtableRemoveAll(pairtable);
1540 nconspairs = 0;
1541
1542 /* collect large nonzero entries variables and their number of nonzeros */
1543 for( c = 0; c < ncols; c++ )
1544 {
1545 int nnonz;
1546
1547 nnonz = SCIPmatrixGetColNNonzs(matrix, c);
1548 vars[c] = SCIPmatrixGetVar(matrix, c);
1549
1550 /* if the locks do not match do not consider the column for sparsification
1551 * also skip if the variable is not allowed to be multi-aggregated
1552 */
1553 if( SCIPmatrixDownlockConflict(matrix, c) || SCIPmatrixUplockConflict(matrix, c) || SCIPdoNotMultaggrVar(scip, vars[c]) )
1554 {
1555 isblockedvar[c] = TRUE;
1556 ishashingcols[c] = FALSE;
1557 continue;
1558 }
1559
1560 isblockedvar[c] = FALSE;
1561
1562 /* only consider nonimplied free variables, i.e., non-hashing columns in the previous step,
1563 * with large nonzero entries
1564 * skip singleton variables, because either the constraint is redundant
1565 * or the variables can be canceled by variables substitution
1566 */
1567 if( nnonz >= presoldata->mineliminatednonzeros && !ishashingcols[c] )
1568 {
1569 int* colinds;
1570 SCIP_Real* colvals;
1571 int npairs;
1572 int failshift;
1573
1574 ishashingcols[c] = TRUE;
1575 colinds = SCIPmatrixGetColIdxPtr(matrix, c);
1576 colvals = SCIPmatrixGetColValPtr(matrix, c);
1577
1578 /* sort the rows non-decreasingly by number of nonzeros
1579 * if the number of nonzeros, we use the colindex as tie-breaker
1580 */
1581 for( i = 0; i < nnonz; ++i )
1582 {
1583 perm[i] = i;
1584 scores[i] = -SCIPmatrixGetRowNNonzs(matrix, colinds[i]) - 1.0 * colinds[i] / ncols;
1585 }
1586 SCIPsortRealInt(scores, perm, nnonz);
1587
1588 if( presoldata->maxconsiderednonzeros >= 0 )
1589 nnonz = MIN(nnonz, presoldata->maxconsiderednonzeros);
1590
1591 npairs = (nnonz * (nnonz - 1)) / 2;
1592 if( nconspairs + npairs > conspairssize )
1593 {
1594 int newsize = SCIPcalcMemGrowSize(scip, nconspairs + npairs);
1595 SCIP_CALL( SCIPreallocBufferArray(scip, &conspairs, newsize) );
1596 conspairssize = newsize;
1597 }
1598
1599 /* if we are called after one or more failures, i.e., executions without finding cancellations, then we
1600 * shift the section of nonzeros considered; in the case that the maxconsiderednonzeros limit is hit,
1601 * this results in different constraint pairs being tried and avoids trying the same useless
1602 * cancellations repeatedly
1603 */
1604 failshift = presoldata->nfailures*presoldata->maxconsiderednonzeros;
1605
1606 for( i = 0; i < nnonz; ++i )
1607 {
1608 for( j = i + 1; j < nnonz; ++j )
1609 {
1610 int i1;
1611 int i2;
1612
1613 assert(nconspairs < conspairssize);
1614 assert(conspairs != NULL);
1615
1616 i1 = perm[(i + failshift) % nnonz];
1617 i2 = perm[(j + failshift) % nnonz];
1618 conspairs[nconspairs].colindex = c;
1619
1620 if( colinds[i1] < colinds[i2])
1621 {
1622 conspairs[nconspairs].consindex1 = colinds[i1];
1623 conspairs[nconspairs].consindex2 = colinds[i2];
1624 conspairs[nconspairs].conscoef1 = colvals[i1];
1625 conspairs[nconspairs].conscoef2 = colvals[i2];
1626 }
1627 else
1628 {
1629 conspairs[nconspairs].consindex1 = colinds[i2];
1630 conspairs[nconspairs].consindex2 = colinds[i1];
1631 conspairs[nconspairs].conscoef1 = colvals[i2];
1632 conspairs[nconspairs].conscoef2 = colvals[i1];
1633 }
1634 ++nconspairs;
1635 }
1636 }
1637 }
1638 else
1639 {
1640 ishashingcols[c] = FALSE;
1641 }
1642 }
1643
1644 /* insert conspairs into hash table */
1645 for( c = 0; c < nconspairs; ++c )
1646 {
1647 SCIP_Bool insert;
1648 COLCONSPAIR* otherconspair;
1649
1650 assert(conspairs != NULL);
1651
1652 insert = TRUE;
1653
1654 /* check if this pair is already contained in the hash table;
1655 * The loop is required due to the non-transitivity of the hash functions
1656 */
1657 while( (otherconspair = (COLCONSPAIR*)SCIPhashtableRetrieve(pairtable, (void*) &conspairs[c])) != NULL )
1658 {
1659 /* if the previous constraint pair has fewer or the same number of nonzeros in the attached column
1660 * we keep that pair and skip this one
1661 */
1662 if( SCIPmatrixGetColNNonzs(matrix, otherconspair->colindex) <=
1663 SCIPmatrixGetColNNonzs(matrix, conspairs[c].colindex) )
1664 {
1665 insert = FALSE;
1666 break;
1667 }
1668
1669 /* this pairs column has fewer nonzeros, so remove the other pair from the hash table and loop */
1670 SCIP_CALL( SCIPhashtableRemove(pairtable, (void*) otherconspair) );
1671 }
1672
1673 if( insert )
1674 {
1675 SCIP_CALL( SCIPhashtableInsert(pairtable, (void*) &conspairs[c]) );
1676 }
1677 }
1678
1679 /* sort rows according to decreasingly sparsity */
1680 assert(colidxsorted != NULL);
1681 assert(colsparsity != NULL);
1682 for( c = 0; c < ncols; ++c )
1683 {
1684 colidxsorted[c] = c;
1685 colsparsity[c] = -SCIPmatrixGetColNNonzs(matrix, c);
1686 }
1687 SCIPsortIntInt(colsparsity, colidxsorted, ncols);
1688
1689 /* loop over the columns and cancel nonzeros until maximum number of retrieves is reached */
1690 maxuseless = (SCIP_Longint)(presoldata->maxretrievefac * (SCIP_Real)ncols);
1691 nuseless = 0;
1692 for( c = 0; c < ncols && nuseless <= maxuseless; c++ )
1693 {
1694 int colidx;
1695 int nnonz;
1696
1697 colidx = colidxsorted[c];
1698 nnonz = SCIPmatrixGetColNNonzs(matrix, colidx);
1699
1700 if( isblockedvar[colidx] || nnonz < presoldata->mineliminatednonzeros )
1701 continue;
1702
1703 /* since the function parameters for the max fillin are unsigned we do not need to handle the
1704 * unlimited (-1) case due to implicit conversion rules */
1705 SCIP_CALL( cancelCol(scip, matrix, presoldata, pairtable, ishashingcols, vars, isblockedvar, colidx, \
1706 presoldata->maxcontfillin == -1 ? INT_MAX : presoldata->maxcontfillin, \
1707 presoldata->maxintfillin == -1 ? INT_MAX : presoldata->maxintfillin, \
1708 presoldata->maxbinfillin == -1 ? INT_MAX : presoldata->maxbinfillin, \
1709 presoldata->maxconsiderednonzeros, presoldata->preserveintcoefs, \
1710 &nuseless, nchgcoefs, &numcancel, &nfillin, TRUE) );
1711 }
1712
1713 if( numcancel > 0 )
1714 {
1716 " (%.1fs) dualsparsify: %d nonzeros canceled\n", SCIPgetSolvingTime(scip), numcancel);
1717 *result = SCIP_SUCCESS;
1718 }
1719 }
1720
1721 updateFailureStatistic(presoldata, numcancel > 0);
1722
1723 SCIPfreeBufferArrayNull(scip, &conspairs);
1724 SCIPfreeBufferArray(scip, &colsparsity);
1725 SCIPfreeBufferArray(scip, &colidxsorted);
1726
1727 SCIPhashtableFree(&pairtable);
1728
1729 SCIPfreeBufferArray(scip, &isblockedvar);
1730 SCIPfreeBufferArray(scip, &vars);
1731 SCIPfreeBufferArray(scip, &ishashingcols);
1732 SCIPfreeBufferArray(scip, &perm);
1733 SCIPfreeBufferArray(scip, &scores);
1734
1735 SCIPmatrixFree(scip, &matrix);
1736
1737 return SCIP_OKAY;
1738}
1739
1740/*
1741 * presolver specific interface methods
1742 */
1743
1744/** destructor of presolver to free user data (called when SCIP is exiting) */
1745static
1746SCIP_DECL_PRESOLFREE(presolFreeDualsparsify)
1747{ /*lint --e{715}*/
1748 SCIP_PRESOLDATA* presoldata;
1749
1750 /* free presolver data */
1751 presoldata = SCIPpresolGetData(presol);
1752 assert(presoldata != NULL);
1753
1754 SCIPfreeBlockMemory(scip, &presoldata);
1755 SCIPpresolSetData(presol, NULL);
1756
1757 return SCIP_OKAY;
1758}
1759
1760/** initialization method of presolver (called after problem was transformed) */
1761static
1762SCIP_DECL_PRESOLINIT(presolInitDualsparsify)
1763{
1764 SCIP_PRESOLDATA* presoldata;
1765
1766 /* set the counters in the init (and not in the initpre) callback such that they persist across restarts */
1767 presoldata = SCIPpresolGetData(presol);
1768 presoldata->nfailures = 0;
1769 presoldata->nwaitingcalls = 0;
1770 presoldata->naggregated = 0;
1771
1772 return SCIP_OKAY;
1773}
1774
1775/** creates the dualsparsify presolver and includes it in SCIP */
1777 SCIP* scip /**< SCIP data structure */
1778 )
1779{
1780 SCIP_PRESOLDATA* presoldata;
1781 SCIP_PRESOL* presol;
1782
1783 /* create dualsparsify presolver data */
1784 SCIP_CALL( SCIPallocBlockMemory(scip, &presoldata) );
1785
1786 /* include presolver */
1788 PRESOL_TIMING, presolExecDualsparsify, presoldata) );
1789
1790 SCIP_CALL( SCIPsetPresolCopy(scip, presol, presolCopyDualsparsify) );
1791 SCIP_CALL( SCIPsetPresolFree(scip, presol, presolFreeDualsparsify) );
1792 SCIP_CALL( SCIPsetPresolInit(scip, presol, presolInitDualsparsify) );
1793
1795 "presolving/dualsparsify/enablecopy",
1796 "should dualsparsify presolver be copied to sub-SCIPs?",
1797 &presoldata->enablecopy, TRUE, DEFAULT_ENABLECOPY, NULL, NULL) );
1798
1800 "presolving/dualsparsify/preserveintcoefs",
1801 "should we forbid cancellations that destroy integer coefficients?",
1802 &presoldata->preserveintcoefs, TRUE, DEFAULT_PRESERVEINTCOEFS, NULL, NULL) );
1803
1805 "presolving/dualsparsify/preservegoodlocks",
1806 "should we preserve good locked properties of variables (at most one lock in one direction)?",
1807 &presoldata->preservegoodlocks, TRUE, DEFAULT_PRESERVEGOODLOCKS, NULL, NULL) );
1808
1810 "presolving/dualsparsify/maxcontfillin",
1811 "maximal fillin for continuous variables (-1: unlimited)",
1812 &presoldata->maxcontfillin, FALSE, DEFAULT_MAX_CONT_FILLIN, -1, INT_MAX, NULL, NULL) );
1813
1815 "presolving/dualsparsify/maxbinfillin",
1816 "maximal fillin for binary variables (-1: unlimited)",
1817 &presoldata->maxbinfillin, FALSE, DEFAULT_MAX_BIN_FILLIN, -1, INT_MAX, NULL, NULL) );
1818
1820 "presolving/dualsparsify/maxintfillin",
1821 "maximal fillin for integer variables including binaries (-1: unlimited)",
1822 &presoldata->maxintfillin, FALSE, DEFAULT_MAX_INT_FILLIN, -1, INT_MAX, NULL, NULL) );
1823
1825 "presolving/dualsparsify/maxconsiderednonzeros",
1826 "maximal number of considered nonzeros within one column (-1: no limit)",
1827 &presoldata->maxconsiderednonzeros, TRUE, DEFAULT_MAXCONSIDEREDNONZEROS, -1, INT_MAX, NULL, NULL) );
1828
1830 "presolving/dualsparsify/mineliminatednonzeros",
1831 "minimal eliminated nonzeros within one column if we need to add a constraint to the problem",
1832 &presoldata->mineliminatednonzeros, FALSE, DEFAULT_MINELIMINATEDNONZEROS, 0, INT_MAX, NULL, NULL) );
1833
1835 "presolving/dualsparsify/maxretrievefac",
1836 "limit on the number of useless vs. useful hashtable retrieves as a multiple of the number of constraints",
1837 &presoldata->maxretrievefac, TRUE, DEFAULT_MAXRETRIEVEFAC, 0.0, SCIP_REAL_MAX, NULL, NULL) );
1838
1840 "presolving/dualsparsify/waitingfac",
1841 "number of calls to wait until next execution as a multiple of the number of useless calls",
1842 &presoldata->waitingfac, TRUE, DEFAULT_WAITINGFAC, 0.0, SCIP_REAL_MAX, NULL, NULL) );
1843
1844 return SCIP_OKAY;
1845}
SCIP_VAR * a
Definition: circlepacking.c:66
SCIP_VAR ** b
Definition: circlepacking.c:65
Constraint handler for linear constraints in their most general form, .
methods for debugging
#define SCIPdebugGetSolVal(scip, var, val)
Definition: debug.h:299
#define SCIPdebugAddSolVal(scip, var, val)
Definition: debug.h:298
#define NULL
Definition: def.h:267
#define SCIP_MAXSTRLEN
Definition: def.h:288
#define COPYSIGN
Definition: def.h:258
#define SCIP_Longint
Definition: def.h:158
#define SCIP_REAL_MAX
Definition: def.h:174
#define SCIP_Bool
Definition: def.h:91
#define MIN(x, y)
Definition: def.h:243
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define MAX(x, y)
Definition: def.h:239
#define REALABS(x)
Definition: def.h:197
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:724
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1668
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2770
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
Definition: misc.c:2346
#define SCIPhashThree(a, b, c)
Definition: pub_misc.h:553
SCIP_RETCODE SCIPhashtableCreate(SCIP_HASHTABLE **hashtable, BMS_BLKMEM *blkmem, int tablesize, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr)
Definition: misc.c:2296
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition: misc.c:2608
void SCIPhashtableRemoveAll(SCIP_HASHTABLE *hashtable)
Definition: misc.c:2755
static INLINE uint32_t SCIPrealHashCode(double x)
Definition: pub_misc.h:576
SCIP_RETCODE SCIPhashtableRemove(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2677
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2547
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:225
#define SCIPdebugMsg
Definition: scip_message.h:78
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
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:139
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
void SCIPswapPointers(void **pointer1, void **pointer2)
Definition: misc.c:10396
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1174
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:139
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:128
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:132
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:137
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
void SCIPpresolSetData(SCIP_PRESOL *presol, SCIP_PRESOLDATA *presoldata)
Definition: presol.c:522
SCIP_PRESOLDATA * SCIPpresolGetData(SCIP_PRESOL *presol)
Definition: presol.c:512
SCIP_RETCODE SCIPsetPresolInit(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLINIT((*presolinit)))
Definition: scip_presol.c:172
SCIP_RETCODE SCIPsetPresolFree(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLFREE((*presolfree)))
Definition: scip_presol.c:156
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLCOPY((*presolcopy)))
Definition: scip_presol.c:140
SCIP_RETCODE SCIPincludePresolBasic(SCIP *scip, SCIP_PRESOL **presolptr, const char *name, const char *desc, int priority, int maxrounds, SCIP_PRESOLTIMING timing, SCIP_DECL_PRESOLEXEC((*presolexec)), SCIP_PRESOLDATA *presoldata)
Definition: scip_presol.c:105
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
Definition: presol.c:599
int SCIPgetNRuns(SCIP *scip)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:378
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPvarIsInitial(SCIP_VAR *var)
Definition: var.c:17620
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17599
SCIP_Bool SCIPdoNotAggr(SCIP *scip)
Definition: scip_var.c:8565
SCIP_Bool SCIPdoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:8598
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17584
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18088
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
SCIP_RETCODE SCIPmultiaggregateVar(SCIP *scip, SCIP_VAR *var, int naggvars, SCIP_VAR **aggvars, SCIP_Real *scalars, SCIP_Real constant, SCIP_Bool *infeasible, SCIP_Bool *aggregated)
Definition: scip_var.c:8535
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1248
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:17610
SCIP_Bool SCIPvarIsRemovable(SCIP_VAR *var)
Definition: var.c:17630
SCIP_RETCODE SCIPcreateVar(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype, SCIP_Bool initial, SCIP_Bool removable, SCIP_DECL_VARDELORIG((*vardelorig)), SCIP_DECL_VARTRANS((*vartrans)), SCIP_DECL_VARDELTRANS((*vardeltrans)), SCIP_DECL_VARCOPY((*varcopy)), SCIP_VARDATA *vardata)
Definition: scip_var.c:114
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18078
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
void SCIPsortIntReal(int *intarray, SCIP_Real *realarray, int len)
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10877
SCIP_Bool SCIPmatrixUplockConflict(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1872
int SCIPmatrixGetRowNMinActNegInf(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1812
int * SCIPmatrixGetColIdxPtr(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1580
int SCIPmatrixGetRowNNonzs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1708
int SCIPmatrixGetColNDownlocks(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1648
int SCIPmatrixGetColNNonzs(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1592
int SCIPmatrixGetColNUplocks(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1636
SCIP_Real SCIPmatrixGetRowMaxActivity(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1800
SCIP_Real SCIPmatrixGetColLb(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1625
SCIP_Real SCIPmatrixGetRowLhs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1742
SCIP_Real * SCIPmatrixGetRowValPtr(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1684
SCIP_Bool SCIPmatrixDownlockConflict(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1884
SCIP_Real SCIPmatrixGetRowRhs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1754
SCIP_Real * SCIPmatrixGetColValPtr(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1568
int SCIPmatrixGetRowNMinActPosInf(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1824
SCIP_RETCODE SCIPmatrixCreate(SCIP *scip, SCIP_MATRIX **matrixptr, SCIP_Bool onlyifcomplete, SCIP_Bool *initialized, SCIP_Bool *complete, SCIP_Bool *infeasible, int *naddconss, int *ndelconss, int *nchgcoefs, int *nchgbds, int *nfixedvars)
Definition: matrix.c:454
int SCIPmatrixGetNColumns(SCIP_MATRIX *matrix)
Definition: matrix.c:1604
SCIP_Real SCIPmatrixGetRowMinActivity(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1788
void SCIPmatrixFree(SCIP *scip, SCIP_MATRIX **matrix)
Definition: matrix.c:1072
int SCIPmatrixGetRowNMaxActPosInf(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1848
int SCIPmatrixGetRowNMaxActNegInf(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1836
SCIP_VAR * SCIPmatrixGetVar(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1660
int * SCIPmatrixGetRowIdxPtr(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1696
int SCIPmatrixGetNRows(SCIP_MATRIX *matrix)
Definition: matrix.c:1732
void SCIPmatrixRemoveColumnBounds(SCIP *scip, SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1169
SCIP_Real SCIPmatrixGetColUb(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1614
memory allocation routines
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:57
static SCIP_RETCODE cancelCol(SCIP *scip, SCIP_MATRIX *matrix, SCIP_PRESOLDATA *presoldata, SCIP_HASHTABLE *pairtable, SCIP_Bool *ishashingcols, SCIP_VAR **vars, SCIP_Bool *isblockedvar, int colidx, int maxcontfillin, int maxintfillin, int maxbinfillin, int maxconsiderednonzeros, SCIP_Bool preserveintcoefs, SCIP_Longint *nuseless, int *nchgcoefs, int *ncanceled, int *nfillin, SCIP_Bool isaddedcons)
#define DEFAULT_MAXCONSIDEREDNONZEROS
SCIP_RETCODE SCIPincludePresolDualsparsify(SCIP *scip)
static SCIP_DECL_PRESOLINIT(presolInitDualsparsify)
static SCIP_DECL_PRESOLFREE(presolFreeDualsparsify)
#define PRESOL_NAME
#define MAXSCALE
#define DEFAULT_MAX_INT_FILLIN
static void getVarBoundsOfRow(SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real val, SCIP_Real *rowub, SCIP_Bool *ubfound, SCIP_Real *rowlb, SCIP_Bool *lbfound)
static SCIP_RETCODE aggregation(SCIP *scip, SCIP_MATRIX *matrix, SCIP_PRESOLDATA *presoldata, SCIP_VAR **vars, int colidx1, int colidx2, SCIP_Bool isimpliedfree, SCIP_Real weight1)
static void updateFailureStatistic(SCIP_PRESOLDATA *presoldata, SCIP_Bool success)
#define DEFAULT_PRESERVEGOODLOCKS
#define DEFAULT_MINELIMINATEDNONZEROS
#define PRESOL_PRIORITY
static SCIP_Real getMinActivitySingleRowWithoutCol(SCIP *scip, SCIP_MATRIX *matrix, int row, int col)
#define DEFAULT_ENABLECOPY
static SCIP_DECL_PRESOLEXEC(presolExecDualsparsify)
static SCIP_DECL_PRESOLCOPY(presolCopyDualsparsify)
#define DEFAULT_MAX_CONT_FILLIN
#define DEFAULT_WAITINGFAC
static void getImpliedBounds(SCIP *scip, SCIP_MATRIX *matrix, int col, SCIP_Bool *ubimplied, SCIP_Bool *lbimplied)
#define DEFAULT_MAXRETRIEVEFAC
static SCIP_DECL_HASHKEYVAL(consPairHashval)
static SCIP_DECL_HASHKEYEQ(consPairsEqual)
#define PRESOL_MAXROUNDS
#define PRESOL_TIMING
#define DEFAULT_MAX_BIN_FILLIN
static SCIP_Real getMaxActivitySingleRowWithoutCol(SCIP *scip, SCIP_MATRIX *matrix, int row, int col)
static void getMinMaxActivityResiduals(SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real val, SCIP_Real *minresactivity, SCIP_Real *maxresactivity, SCIP_Bool *isminsettoinfinity, SCIP_Bool *ismaxsettoinfinity)
#define DEFAULT_PRESERVEINTCOEFS
#define PRESOL_DESC
cancel nonzeros of the constraint matrix based on the columns
public methods for managing constraints
public methods for matrix
public methods for message output
#define SCIPdebugPrintCons(x, y, z)
Definition: pub_message.h:102
public data structures and miscellaneous methods
methods for sorting joint arrays of various types
public methods for presolvers
public methods for problem variables
public methods for constraint handler plugins and constraints
general public methods
public methods for memory management
public methods for message handling
public methods for nonlinear relaxation
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for presolving plugins
public methods for variable pricer plugins
public methods for global and local (sub)problems
public methods for the probing mode
public methods for querying solving statistics
public methods for timing
public methods for SCIP variables
@ SCIP_VERBLEVEL_HIGH
Definition: type_message.h:56
struct SCIP_PresolData SCIP_PRESOLDATA
Definition: type_presol.h:51
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_CUTOFF
Definition: type_result.h:48
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_SUCCESS
Definition: type_result.h:58
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_VARTYPE_INTEGER
Definition: type_var.h:63
@ SCIP_VARTYPE_CONTINUOUS
Definition: type_var.h:71
@ SCIP_VARTYPE_IMPLINT
Definition: type_var.h:64
@ SCIP_VARTYPE_BINARY
Definition: type_var.h:62
enum SCIP_Vartype SCIP_VARTYPE
Definition: type_var.h:73