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