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-2022 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 %s <= %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  SCIP_Bool swapped = FALSE;
733  int cancelcollen;
734  int bestnfillin;
735  int nretrieves;
736  int maxfillin;
737  int bestcand;
738  int nchgcoef;
739 
740  ncols = SCIPmatrixGetNColumns(matrix);
741  colishashing = ishashingcols[colidx];
742  cancelcollen = SCIPmatrixGetColNNonzs(matrix, colidx);
743  colidxptr = SCIPmatrixGetColIdxPtr(matrix, colidx);
744  colvalptr = SCIPmatrixGetColValPtr(matrix, colidx);
745  cancelvar = vars[colidx];
746 
747  if( SCIPvarIsIntegral(cancelvar) )
748  {
749  if( SCIPvarIsBinary(cancelvar) )
750  maxfillin = maxbinfillin;
751  else
752  maxfillin = maxintfillin;
753  }
754  else
755  maxfillin = maxcontfillin;
756 
757  SCIP_CALL( SCIPduplicateBufferArray(scip, &cancelcolinds, colidxptr, cancelcollen) );
758  SCIP_CALL( SCIPduplicateBufferArray(scip, &cancelcolvals, colvalptr, cancelcollen) );
759  SCIP_CALL( SCIPallocBufferArray(scip, &tmpinds, cancelcollen) );
760  SCIP_CALL( SCIPallocBufferArray(scip, &tmpvals, cancelcollen) );
761  SCIP_CALL( SCIPallocBufferArray(scip, &scores, cancelcollen) );
762 
763  nchgcoef = 0;
764  nretrieves = 0;
765  while( TRUE ) /*lint !e716 */
766  {
767  COLCONSPAIR colconspair;
768  int maxlen;
769  int i;
770  int j;
771 
772  bestcand = -1;
773  bestnfillin = 0;
774  bestscale = 1.0;
775  bestcancelrate = 0.0;
776 
777  /* sort the rows non-decreasingly by number of nonzeros
778  * if the number of nonzeros, we use the colindex as tie-breaker
779  */
780  for( i = 0; i < cancelcollen; ++i )
781  {
782  tmpinds[i] = i;
783  scores[i] = -SCIPmatrixGetRowNNonzs(matrix, cancelcolinds[i]) - 1.0 * cancelcolinds[i] / (ncols);
784  }
785  SCIPsortRealInt(scores, tmpinds, cancelcollen);
786 
787  maxlen = cancelcollen;
788  if( maxconsiderednonzeros >= 0 )
789  maxlen = MIN(cancelcollen, maxconsiderednonzeros);
790 
791  for( i = 0; i < maxlen; ++i )
792  {
793  for( j = i + 1; j < maxlen; ++j )
794  {
795  COLCONSPAIR* hashingcolconspair;
796  SCIP_VAR* hashingcolvar;
797  SCIP_Real* hashingcolvals;
798  int* hashingcolinds;
799  SCIP_Real hashingcollb;
800  SCIP_Real hashingcolub;
801  SCIP_Real cancelrate;
802  SCIP_Real rowlhs;
803  SCIP_Real rowrhs;
804  SCIP_Real scale;
805  SCIP_Bool hashingcolisbin;
806  SCIP_Bool abortpair;
807  int hashingcollen;
808  int ntotfillin;
809  int ncancel;
810  int a,b;
811  int i1,i2;
812 
813  i1 = tmpinds[i];
814  i2 = tmpinds[j];
815 
816  assert(cancelcolinds[i] < cancelcolinds[j]);
817 
818  if( cancelcolinds[i1] < cancelcolinds[i2] )
819  {
820  colconspair.consindex1 = cancelcolinds[i1];
821  colconspair.consindex2 = cancelcolinds[i2];
822  colconspair.conscoef1 = cancelcolvals[i1];
823  colconspair.conscoef2 = cancelcolvals[i2];
824  }
825  else
826  {
827  colconspair.consindex1 = cancelcolinds[i2];
828  colconspair.consindex2 = cancelcolinds[i1];
829  colconspair.conscoef1 = cancelcolvals[i2];
830  colconspair.conscoef2 = cancelcolvals[i1];
831  }
832 
833  hashingcolconspair = (COLCONSPAIR*)SCIPhashtableRetrieve(pairtable, (void*) &colconspair);
834  nretrieves++;
835 
836  if( hashingcolconspair == NULL ||
837  hashingcolconspair->colindex == colidx || isblockedvar[hashingcolconspair->colindex] )
838  continue;
839 
840  /* if the column we want to cancel is a hashing column (which we stored for canceling other columns),
841  * we will only use the hashing columns for canceling with less nonzeros and if the number of nonzeros
842  * is equal we use the colindex as tie-breaker to avoid cyclic nonzero cancellation
843  */
844  hashingcollen = SCIPmatrixGetColNNonzs(matrix, hashingcolconspair->colindex);
845  if( colishashing && (cancelcollen < hashingcollen ||
846  (cancelcollen == hashingcollen && colidx < hashingcolconspair->colindex)) )
847  continue;
848 
849  hashingcolvals = SCIPmatrixGetColValPtr(matrix, hashingcolconspair->colindex);
850  hashingcolinds = SCIPmatrixGetColIdxPtr(matrix, hashingcolconspair->colindex);
851  hashingcolvar = vars[hashingcolconspair->colindex];
852  hashingcollb = SCIPvarGetLbGlobal(hashingcolvar);
853  hashingcolub = SCIPvarGetUbGlobal(hashingcolvar);
854  hashingcolisbin = (SCIPvarGetType(hashingcolvar) == SCIP_VARTYPE_BINARY) ||
855  (SCIPvarIsIntegral(hashingcolvar) && SCIPisZero(scip, hashingcollb) &&
856  SCIPisEQ(scip, hashingcolub, 1.0));
857  scale = -colconspair.conscoef1 / hashingcolconspair->conscoef1;
858 
859  if( SCIPisZero(scip, scale) )
860  continue;
861 
862  if( REALABS(scale) > MAXSCALE )
863  continue;
864 
865  /* @todo do more reduction if knspsack constraint handler supports downgrading constraint,
866  * i.e., converting into a linear constraint
867  */
868  if( hashingcolisbin )
869  continue;
870  else if( SCIPvarIsIntegral(hashingcolvar) )
871  {
872  if( SCIPvarIsIntegral(cancelvar) )
873  {
874  /* skip if the hashing variable is an integer variable and
875  * the canceled variable is an implied integer variable
876  */
877  if( (SCIPvarGetType(hashingcolvar) != SCIP_VARTYPE_IMPLINT) &&
878  (SCIPvarGetType(cancelvar) == SCIP_VARTYPE_IMPLINT) )
879  continue;
880 
881  /* skip if the scale is non-integral */
882  if( !SCIPisIntegral(scip, scale) )
883  continue;
884 
885  /* round scale to be exactly integral */
886  scale = floor(scale + 0.5);
887  }
888  /* skip if the canceled variable is a continuous variable */
889  else
890  continue;
891  }
892 
893  a = 0;
894  b = 0;
895  ncancel = 0;
896  ntotfillin = 0;
897  abortpair = FALSE;
898 
899  while( a < cancelcollen && b < hashingcollen )
900  {
901  if( cancelcolinds[a] == hashingcolinds[b] )
902  {
903  SCIP_Real newcoef;
904 
905  newcoef = cancelcolvals[a] + scale * hashingcolvals[b];
906 
907  /* check if coefficient is canceled */
908  if( SCIPisZero(scip, newcoef) )
909  {
910  ++ncancel;
911  }
912  /* otherwise, check if integral coefficients are preserved if the column is integral */
913  else if( (preserveintcoefs && SCIPvarIsIntegral(cancelvar) &&
914  SCIPisIntegral(scip, cancelcolvals[a]) && !SCIPisIntegral(scip, newcoef)) )
915  {
916  abortpair = TRUE;
917  break;
918  }
919  /* finally, check if locks could be modified in a bad way due to flipped signs */
920  else if( COPYSIGN(1.0, newcoef) != COPYSIGN(1.0, cancelcolvals[a]) ) /*lint !e777*/
921  {
922  /* do not flip signs for non-canceled coefficients if this adds a lock to a variable that
923  * had at most one lock in that direction before, except if the other direction gets unlocked
924  */
925  rowrhs = SCIPmatrixGetRowRhs(matrix, cancelcolinds[a]);
926  rowlhs = SCIPmatrixGetRowLhs(matrix, cancelcolinds[a]);
927  if( (cancelcolvals[a] > 0.0 && ! SCIPisInfinity(scip, rowrhs)) ||
928  (cancelcolvals[a] < 0.0 && ! SCIPisInfinity(scip, -rowlhs)) )
929  {
930  /* if we get into this case the variable had a positive coefficient in a <= constraint or
931  * a negative coefficient in a >= constraint, e.g. an uplock. If this was the only uplock
932  * we do not abort their cancelling, otherwise we abort if we had a single or no downlock
933  * and add one
934  */
935  if( presoldata->preservegoodlocks && (SCIPmatrixGetColNUplocks(matrix, colidx) > 1 &&
936  SCIPmatrixGetColNDownlocks(matrix, colidx) <= 1) )
937  {
938  abortpair = TRUE;
939  break;
940  }
941  }
942 
943  if( (cancelcolvals[a] < 0.0 && ! SCIPisInfinity(scip, rowrhs)) ||
944  (cancelcolvals[a] > 0.0 && ! SCIPisInfinity(scip, -rowlhs)) )
945  {
946  /* symmetric case where the variable had a downlock */
947  if( presoldata->preservegoodlocks && (SCIPmatrixGetColNDownlocks(matrix, colidx) > 1 &&
948  SCIPmatrixGetColNUplocks(matrix, colidx) <= 1) )
949  {
950  abortpair = TRUE;
951  break;
952  }
953  }
954  }
955 
956  ++a;
957  ++b;
958  }
959  else if( cancelcolinds[a] < hashingcolinds[b] )
960  {
961  ++a;
962  }
963  else
964  {
965  SCIP_Real newcoef;
966 
967  newcoef = scale * hashingcolvals[b];
968  rowrhs = SCIPmatrixGetRowRhs(matrix, hashingcolinds[b]);
969  rowlhs = SCIPmatrixGetRowLhs(matrix, hashingcolinds[b]);
970 
971  if( (newcoef > 0.0 && ! SCIPisInfinity(scip, rowrhs)) ||
972  (newcoef < 0.0 && ! SCIPisInfinity(scip, -rowlhs)) )
973  {
974  if( presoldata->preservegoodlocks && SCIPmatrixGetColNUplocks(matrix, colidx) <= 1 )
975  {
976  abortpair = TRUE;
977  ++b;
978  break;
979  }
980  }
981 
982  if( (newcoef < 0.0 && ! SCIPisInfinity(scip, rowrhs)) ||
983  (newcoef > 0.0 && ! SCIPisInfinity(scip, -rowlhs)) )
984  {
985  if( presoldata->preservegoodlocks && SCIPmatrixGetColNDownlocks(matrix, colidx) <= 1 )
986  {
987  abortpair = TRUE;
988  ++b;
989  break;
990  }
991  }
992 
993  ++b;
994 
995  if( ++ntotfillin > maxfillin )
996  {
997  abortpair = TRUE;
998  break;
999  }
1000  }
1001  }
1002 
1003  if( abortpair )
1004  continue;
1005 
1006  while( b < hashingcollen )
1007  {
1008  ++b;
1009 
1010  if( ++ntotfillin > maxfillin )
1011  break;
1012  }
1013 CHECKFILLINAGAIN:
1014  if( ntotfillin > maxfillin || ntotfillin >= ncancel )
1015  continue;
1016 
1017  cancelrate = (ncancel - ntotfillin) / (SCIP_Real) cancelcollen;
1018 
1019  /* if a linear constraint is needed to keep the validity, we require a large nonzero cancellation */
1020  if( isaddedcons && (ncancel - ntotfillin < presoldata->mineliminatednonzeros) )
1021  continue;
1022 
1023  if( cancelrate > bestcancelrate )
1024  {
1025  if( ishashingcols[hashingcolconspair->colindex] )
1026  {
1027  SCIP_Bool lbimplied;
1028  SCIP_Bool ubimplied;
1029 
1030  /* recompute whether a variable is still implied free; after some previous multi-aggregations of
1031  * some variables, it might be that other variables that are contained in the same linear rows of the
1032  * matrix are not implied free anymore (see #2971)
1033  */
1034  getImpliedBounds(scip, matrix, hashingcolconspair->colindex, &ubimplied, &lbimplied);
1035 
1036  if( !lbimplied || !ubimplied )
1037  {
1038  ishashingcols[hashingcolconspair->colindex] = FALSE;
1039  ntotfillin += 2;
1040  goto CHECKFILLINAGAIN;
1041  }
1042  }
1043 
1044  bestnfillin = ntotfillin;
1045  bestcand = hashingcolconspair->colindex;
1046  bestscale = scale;
1047  bestcancelrate = cancelrate;
1048 
1049  /* stop looking if the current candidate does not create any fill-in or alter coefficients */
1050  if( cancelrate == 1.0 )
1051  break;
1052  }
1053 
1054  /* we accept the best candidate immediately if it does not create any fill-in or alter coefficients */
1055  if( bestcand != -1 && bestcancelrate == 1.0 )
1056  break;
1057  }
1058  }
1059 
1060  if( bestcand != -1 )
1061  {
1062  SCIP_Real* hashingcolvals;
1063  int* hashingcolinds;
1064  int hashingcollen;
1065  int tmpcollen;
1066  int a;
1067  int b;
1068 
1069  SCIPdebugMsg(scip, "cancelcol %d (%s) candidate column %d (%s) (bestcancelrate = %g, bestscale = %g)\n",
1070  colidx, SCIPvarGetName(cancelvar), bestcand, SCIPvarGetName(vars[bestcand]), bestcancelrate, bestscale);
1071 
1072  hashingcolvals = SCIPmatrixGetColValPtr(matrix, bestcand);
1073  hashingcolinds = SCIPmatrixGetColIdxPtr(matrix, bestcand);
1074  hashingcollen = SCIPmatrixGetColNNonzs(matrix, bestcand);
1075 
1076  a = 0;
1077  b = 0;
1078  tmpcollen = 0;
1079 
1080  while( a < cancelcollen && b < hashingcollen )
1081  {
1082  if( cancelcolinds[a] == hashingcolinds[b] )
1083  {
1084  SCIP_Real val = cancelcolvals[a] + bestscale * hashingcolvals[b];
1085 
1086  if( !SCIPisZero(scip, val) )
1087  {
1088  tmpinds[tmpcollen] = cancelcolinds[a];
1089  tmpvals[tmpcollen] = val;
1090  ++tmpcollen;
1091  }
1092  ++nchgcoef;
1093 
1094  ++a;
1095  ++b;
1096  }
1097  else if( cancelcolinds[a] < hashingcolinds[b] )
1098  {
1099  tmpinds[tmpcollen] = cancelcolinds[a];
1100  tmpvals[tmpcollen] = cancelcolvals[a];
1101  ++tmpcollen;
1102  ++a;
1103  }
1104  else
1105  {
1106  tmpinds[tmpcollen] = hashingcolinds[b];
1107  tmpvals[tmpcollen] = hashingcolvals[b] * bestscale;
1108  ++nchgcoef;
1109  ++tmpcollen;
1110  ++b;
1111  }
1112  }
1113 
1114  while( a < cancelcollen )
1115  {
1116  tmpinds[tmpcollen] = cancelcolinds[a];
1117  tmpvals[tmpcollen] = cancelcolvals[a];
1118  ++tmpcollen;
1119  ++a;
1120  }
1121 
1122  while( b < hashingcollen )
1123  {
1124  tmpinds[tmpcollen] = hashingcolinds[b];
1125  tmpvals[tmpcollen] = hashingcolvals[b] * bestscale;
1126  ++nchgcoef;
1127  ++tmpcollen;
1128  ++b;
1129  }
1130 
1131  /* update fill-in counter */
1132  *nfillin += bestnfillin;
1133 
1134  /* swap the temporary arrays so that the cancelcolinds and cancelcolvals arrays, contain the new
1135  * changed column, and the tmpinds and tmpvals arrays can be overwritten in the next iteration
1136  */
1137  SCIPswapPointers((void**) &tmpinds, (void**) &cancelcolinds);
1138  SCIPswapPointers((void**) &tmpvals, (void**) &cancelcolvals);
1139  swapped = ! swapped;
1140  cancelcollen = tmpcollen;
1141  SCIP_CALL( aggregation(scip, matrix, presoldata, vars, colidx, bestcand, ishashingcols[bestcand], -bestscale) );
1142 
1143  /* the newly created variable is now at the position bestcand and is assumed to have the same coefficients.
1144  * this is not the case if the variable is not implied free since then a new constraint was added and the
1145  * nonzero fillin would not be counted correctly if we do not block this variable
1146  */
1147  if( !ishashingcols[bestcand] )
1148  isblockedvar[bestcand] = TRUE;
1149  }
1150  else
1151  break;
1152  }
1153 
1154  if( nchgcoef != 0 )
1155  {
1156  /* update counters */
1157  *nchgcoefs += nchgcoef;
1158  *ncanceled += SCIPmatrixGetColNNonzs(matrix, colidx) - cancelcollen;
1159 
1160  isblockedvar[colidx] = TRUE;
1161 
1162  /* if successful, decrease the useless hashtable retrieves counter; the rationale here is that we want to keep
1163  * going if, after many useless calls that almost exceeded the budget, we finally reach a useful section; but we
1164  * don't allow a negative build-up for the case that the useful section is all at the beginning and we just want
1165  * to quit quickly afterwards
1166  */
1167  *nuseless -= nretrieves;
1168  *nuseless = MAX(*nuseless, 0);
1169  }
1170  else
1171  {
1172  /* if not successful, increase useless hashtable retrieves counter */
1173  *nuseless += nretrieves;
1174  }
1175 
1176  SCIPfreeBufferArray(scip, &scores);
1177  if( swapped )
1178  {
1179  SCIPfreeBufferArray(scip, &cancelcolvals);
1180  SCIPfreeBufferArray(scip, &cancelcolinds);
1181  SCIPfreeBufferArray(scip, &tmpvals);
1182  SCIPfreeBufferArray(scip, &tmpinds);
1183  }
1184  else
1185  {
1186  SCIPfreeBufferArray(scip, &tmpvals);
1187  SCIPfreeBufferArray(scip, &tmpinds);
1188  SCIPfreeBufferArray(scip, &cancelcolvals);
1189  SCIPfreeBufferArray(scip, &cancelcolinds);
1190  }
1191 
1192  return SCIP_OKAY;
1193 }
1194 
1195 /** updates failure counter after one execution */
1196 static
1198  SCIP_PRESOLDATA* presoldata, /**< presolver data */
1199  SCIP_Bool success /**< was this execution successful? */
1200  )
1201 {
1202  assert(presoldata != NULL);
1203 
1204  if( success )
1205  {
1206  presoldata->nfailures = 0;
1207  presoldata->nwaitingcalls = 0;
1208  }
1209  else
1210  {
1211  presoldata->nfailures++;
1212  presoldata->nwaitingcalls = (int)(presoldata->waitingfac*(SCIP_Real)presoldata->nfailures);
1213  }
1214 }
1215 
1216 /*
1217  * Callback methods of presolver
1218  */
1219 
1220 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
1221 static
1222 SCIP_DECL_PRESOLCOPY(presolCopyDualsparsify)
1223 {
1224  SCIP_PRESOLDATA* presoldata;
1225 
1226  assert(scip != NULL);
1227  assert(presol != NULL);
1228  assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
1229 
1230  /* call inclusion method of presolver if copying is enabled */
1231  presoldata = SCIPpresolGetData(presol);
1232  assert(presoldata != NULL);
1233  if( presoldata->enablecopy )
1234  {
1236  }
1237 
1238  return SCIP_OKAY;
1239 }
1240 
1241 
1242 /** execution method of presolver */
1243 static
1244 SCIP_DECL_PRESOLEXEC(presolExecDualsparsify)
1245 { /*lint --e{715}*/
1246  SCIP_MATRIX* matrix;
1247  int* perm;
1248  int* colidxsorted;
1249  int* colsparsity;
1250  SCIP_Real* scores;
1251  COLCONSPAIR* conspairs;
1252  SCIP_HASHTABLE* pairtable;
1253  SCIP_PRESOLDATA* presoldata;
1254  SCIP_Bool* ishashingcols;
1255  SCIP_Bool* isblockedvar;
1256  SCIP_VAR** vars;
1257  SCIP_Longint maxuseless;
1258  SCIP_Longint nuseless;
1259  SCIP_Bool initialized;
1260  SCIP_Bool complete;
1261  SCIP_Bool infeasible;
1262  int ncols;
1263  int c;
1264  int i;
1265  int j;
1266  int conspairssize;
1267  int nconspairs;
1268  int numcancel;
1269  int nfillin;
1270 
1271  assert(result != NULL);
1272 
1273  *result = SCIP_DIDNOTRUN;
1274 
1275  if( SCIPdoNotAggr(scip) )
1276  return SCIP_OKAY;
1277 
1278  /* If restart is performed, some cuts will be tranformed into linear constraints.
1279  * However, SCIPmatrixCreate() only collects the original constraints (not the constraints transformed from cuts)
1280  * For this reason, we only perform this method in the first run of branch-and-cut.
1281  * */
1282  if( SCIPgetNRuns(scip) > 1 )
1283  return SCIP_OKAY;
1284 
1285  presoldata = SCIPpresolGetData(presol);
1286 
1287  if( presoldata->nwaitingcalls > 0 )
1288  {
1289  presoldata->nwaitingcalls--;
1290  SCIPdebugMsg(scip, "skipping dualsparsify: nfailures=%d, nwaitingcalls=%d\n", presoldata->nfailures,
1291  presoldata->nwaitingcalls);
1292  return SCIP_OKAY;
1293  }
1294 
1295  SCIPdebugMsg(scip, "starting dualsparsify. . .\n");
1296  *result = SCIP_DIDNOTFIND;
1297 
1298  matrix = NULL;
1299  SCIP_CALL( SCIPmatrixCreate(scip, &matrix, TRUE, &initialized, &complete, &infeasible,
1300  naddconss, ndelconss, nchgcoefs, nchgbds, nfixedvars) );
1301 
1302  /* if infeasibility was detected during matrix creation, return here */
1303  if( infeasible )
1304  {
1305  if( initialized )
1306  SCIPmatrixFree(scip, &matrix);
1307 
1308  *result = SCIP_CUTOFF;
1309  return SCIP_OKAY;
1310  }
1311 
1312  if( !initialized )
1313  return SCIP_OKAY;
1314 
1315  ncols = SCIPmatrixGetNColumns(matrix);
1316 
1317  /* sort columns by row indices */
1318  for( i = 0; i < ncols; i++ )
1319  {
1320  int* colpnt = SCIPmatrixGetColIdxPtr(matrix, i);
1321  SCIP_Real* valpnt = SCIPmatrixGetColValPtr(matrix, i);
1322  SCIPsortIntReal(colpnt, valpnt, SCIPmatrixGetColNNonzs(matrix, i));
1323  }
1324 
1325  SCIP_CALL( SCIPallocBufferArray(scip, &scores, SCIPmatrixGetNRows(matrix)) );
1327  SCIP_CALL( SCIPallocBufferArray(scip, &ishashingcols, SCIPmatrixGetNColumns(matrix)) );
1329  SCIP_CALL( SCIPallocBufferArray(scip, &isblockedvar, SCIPmatrixGetNColumns(matrix)) );
1330 
1331  /* loop over all columns and create cons pairs */
1332  conspairssize = 0;
1333  nconspairs = 0;
1334  conspairs = NULL;
1335  SCIP_CALL( SCIPhashtableCreate(&pairtable, SCIPblkmem(scip), 1,
1336  SCIPhashGetKeyStandard, consPairsEqual, consPairHashval, (void*) scip) );
1337 
1338  /* collect implied free variables and their number of nonzeros */
1339  for( c = 0; c < ncols; c++ )
1340  {
1341  SCIP_Bool lbimplied;
1342  SCIP_Bool ubimplied;
1343  int nnonz;
1344 
1345  vars[c] = SCIPmatrixGetVar(matrix, c);
1346 
1347  /* if the locks do not match do not consider the column for sparsification */
1348  if( SCIPmatrixDownlockConflict(matrix, c) || SCIPmatrixUplockConflict(matrix, c) )
1349  {
1350  isblockedvar[c] = TRUE;
1351  ishashingcols[c] = FALSE;
1352  continue;
1353  }
1354 
1355  /* skip if the variable is not allowed to be multi-aggregated */
1356  if( SCIPdoNotMultaggrVar(scip, vars[c]) )
1357  {
1358  isblockedvar[c] = TRUE;
1359  ishashingcols[c] = FALSE;
1360  continue;
1361  }
1362 
1363  nnonz = SCIPmatrixGetColNNonzs(matrix, c);
1364 
1365  getImpliedBounds(scip, matrix, c, &ubimplied, &lbimplied);
1366 
1367  ishashingcols[c] = FALSE;
1368 
1369  if( lbimplied && ubimplied )
1370  ishashingcols[c] = TRUE;
1371 
1372  isblockedvar[c] = FALSE;
1373 
1374  /* only consider implied free variables
1375  * skip singleton variables, because either the constraint is redundant
1376  * or the variables can be canceled by variable substitution
1377  */
1378  if( nnonz >= 2 && (lbimplied && ubimplied) )
1379  {
1380  SCIP_Real* colvals;
1381  int* colinds;
1382  int failshift;
1383  int npairs;
1384 
1385  colinds = SCIPmatrixGetColIdxPtr(matrix, c);
1386  colvals = SCIPmatrixGetColValPtr(matrix, c);
1387 
1388  /* sort the rows non-decreasingly by number of nonzeros
1389  * if the number of nonzeros is equal, we use the colindex as tie-breaker
1390  */
1391  for( i = 0; i < nnonz; ++i )
1392  {
1393  perm[i] = i;
1394  scores[i] = -SCIPmatrixGetRowNNonzs(matrix, colinds[i]) - 1.0 *colinds[i] / ncols;
1395  }
1396  SCIPsortRealInt(scores, perm, nnonz);
1397 
1398  if( presoldata->maxconsiderednonzeros >= 0 )
1399  nnonz = MIN(nnonz, presoldata->maxconsiderednonzeros);
1400 
1401  npairs = (nnonz * (nnonz - 1)) / 2;
1402  if( nconspairs + npairs > conspairssize )
1403  {
1404  int newsize = SCIPcalcMemGrowSize(scip, nconspairs + npairs);
1405  SCIP_CALL( SCIPreallocBufferArray(scip, &conspairs, newsize) );
1406  conspairssize = newsize;
1407  }
1408 
1409  /* if we are called after one or more failures, i.e., executions without finding cancellations, then we
1410  * shift the section of nonzeros considered; in the case that the maxconsiderednonzeros limit is hit, this
1411  * results in different constraint pairs being tried and avoids trying the same useless cancellations
1412  * repeatedly
1413  */
1414  failshift = presoldata->nfailures*presoldata->maxconsiderednonzeros;
1415 
1416  for( i = 0; i < nnonz; ++i )
1417  {
1418  for( j = i + 1; j < nnonz; ++j )
1419  {
1420  int i1;
1421  int i2;
1422 
1423  assert(nconspairs < conspairssize);
1424  assert(conspairs != NULL);
1425 
1426  i1 = perm[(i + failshift) % nnonz];
1427  i2 = perm[(j + failshift) % nnonz];
1428  /* coverity[var_deref_op] */
1429  conspairs[nconspairs].colindex = c;
1430 
1431  if( colinds[i1] < colinds[i2])
1432  {
1433  conspairs[nconspairs].consindex1 = colinds[i1];
1434  conspairs[nconspairs].consindex2 = colinds[i2];
1435  conspairs[nconspairs].conscoef1 = colvals[i1];
1436  conspairs[nconspairs].conscoef2 = colvals[i2];
1437  }
1438  else
1439  {
1440  conspairs[nconspairs].consindex1 = colinds[i2];
1441  conspairs[nconspairs].consindex2 = colinds[i1];
1442  conspairs[nconspairs].conscoef1 = colvals[i2];
1443  conspairs[nconspairs].conscoef2 = colvals[i1];
1444  }
1445  ++nconspairs;
1446  }
1447  }
1448  }
1449  }
1450 
1451  /* insert conspairs into hash table */
1452  for( c = 0; c < nconspairs; ++c )
1453  {
1454  COLCONSPAIR* otherconspair;
1455  SCIP_Bool insert;
1456 
1457  assert(conspairs != NULL);
1458 
1459  insert = TRUE;
1460 
1461  /* check if this pair is already contained in the hash table;
1462  * The loop is required due to the non-transitivity of the hash functions
1463  */
1464  while( (otherconspair = (COLCONSPAIR*)SCIPhashtableRetrieve(pairtable, (void*) &conspairs[c])) != NULL )
1465  {
1466  /* if the previous constraint pair has fewer or the same number of nonzeros in the attached column
1467  * we keep that pair and skip this one
1468  */
1469  if( SCIPmatrixGetColNNonzs(matrix, otherconspair->colindex) <=
1470  SCIPmatrixGetColNNonzs(matrix, conspairs[c].colindex) )
1471  {
1472  insert = FALSE;
1473  break;
1474  }
1475 
1476  /* this pairs column has fewer nonzeros, so remove the other pair from the hash table and loop */
1477  SCIP_CALL( SCIPhashtableRemove(pairtable, (void*) otherconspair) );
1478  }
1479 
1480  if( insert )
1481  {
1482  SCIP_CALL( SCIPhashtableInsert(pairtable, (void*) &conspairs[c]) );
1483  }
1484  }
1485 
1486  /* sort cols according to decreasing sparsity */
1487  SCIP_CALL( SCIPallocBufferArray(scip, &colidxsorted, ncols) );
1488  SCIP_CALL( SCIPallocBufferArray(scip, &colsparsity, ncols) );
1489  for( c = 0; c < ncols; ++c )
1490  {
1491  colidxsorted[c] = c;
1492  colsparsity[c] = -SCIPmatrixGetColNNonzs(matrix, c);
1493  }
1494  SCIPsortIntInt(colsparsity, colidxsorted, ncols);
1495 
1496  /* loop over the columns and cancel nonzeros until maximum number of retrieves is reached */
1497  maxuseless = (SCIP_Longint)(presoldata->maxretrievefac * (SCIP_Real)ncols);
1498  nuseless = 0;
1499  numcancel = 0;
1500  for( c = 0; c < ncols && nuseless <= maxuseless && !SCIPisStopped(scip); c++ )
1501  {
1502  int colidx;
1503 
1504  colidx = colidxsorted[c];
1505 
1506  if( isblockedvar[colidx] )
1507  continue;
1508 
1509  /* since the function parameters for the max fillin are unsigned we do not need to handle the
1510  * unlimited (-1) case due to implicit conversion rules */
1511  SCIP_CALL( cancelCol(scip, matrix, presoldata, pairtable, ishashingcols, vars, isblockedvar, colidx, \
1512  presoldata->maxcontfillin == -1 ? INT_MAX : presoldata->maxcontfillin, \
1513  presoldata->maxintfillin == -1 ? INT_MAX : presoldata->maxintfillin, \
1514  presoldata->maxbinfillin == -1 ? INT_MAX : presoldata->maxbinfillin, \
1515  presoldata->maxconsiderednonzeros, presoldata->preserveintcoefs, \
1516  &nuseless, nchgcoefs, &numcancel, &nfillin, FALSE) );
1517  }
1518 
1519  if( numcancel > 0 )
1520  *result = SCIP_SUCCESS;
1521  else /* do reductions on variables that contain larger nonzero entries */
1522  {
1523  SCIPhashtableRemoveAll(pairtable);
1524  nconspairs = 0;
1525 
1526  /* collect large nonzero entries variables and their number of nonzeros */
1527  for( c = 0; c < ncols; c++ )
1528  {
1529  int nnonz;
1530 
1531  nnonz = SCIPmatrixGetColNNonzs(matrix, c);
1532  vars[c] = SCIPmatrixGetVar(matrix, c);
1533 
1534  /* if the locks do not match do not consider the column for sparsification */
1535  if( SCIPmatrixDownlockConflict(matrix, c) || SCIPmatrixUplockConflict(matrix, c) )
1536  {
1537  isblockedvar[c] = TRUE;
1538  ishashingcols[c] = FALSE;
1539  continue;
1540  }
1541 
1542  isblockedvar[c] = FALSE;
1543 
1544  /* only consider nonimplied free variables, i.e., non-hashing columns in the previous step,
1545  * with large nonzero entries
1546  * skip singleton variables, because either the constraint is redundant
1547  * or the variables can be canceled by variables substitution
1548  */
1549  if( nnonz >= presoldata->mineliminatednonzeros && !ishashingcols[c] )
1550  {
1551  int* colinds;
1552  SCIP_Real* colvals;
1553  int npairs;
1554  int failshift;
1555 
1556  ishashingcols[c] = TRUE;
1557  colinds = SCIPmatrixGetColIdxPtr(matrix, c);
1558  colvals = SCIPmatrixGetColValPtr(matrix, c);
1559 
1560  /* sort the rows non-decreasingly by number of nonzeros
1561  * if the number of nonzeros, we use the colindex as tie-breaker
1562  */
1563  for( i = 0; i < nnonz; ++i )
1564  {
1565  perm[i] = i;
1566  scores[i] = -SCIPmatrixGetRowNNonzs(matrix, colinds[i]) - 1.0 * colinds[i] / ncols;
1567  }
1568  SCIPsortRealInt(scores, perm, nnonz);
1569 
1570  if( presoldata->maxconsiderednonzeros >= 0 )
1571  nnonz = MIN(nnonz, presoldata->maxconsiderednonzeros);
1572 
1573  npairs = (nnonz * (nnonz - 1)) / 2;
1574  if( nconspairs + npairs > conspairssize )
1575  {
1576  int newsize = SCIPcalcMemGrowSize(scip, nconspairs + npairs);
1577  SCIP_CALL( SCIPreallocBufferArray(scip, &conspairs, newsize) );
1578  conspairssize = newsize;
1579  }
1580 
1581  /* if we are called after one or more failures, i.e., executions without finding cancellations, then we
1582  * shift the section of nonzeros considered; in the case that the maxconsiderednonzeros limit is hit,
1583  * this results in different constraint pairs being tried and avoids trying the same useless
1584  * cancellations repeatedly
1585  */
1586  failshift = presoldata->nfailures*presoldata->maxconsiderednonzeros;
1587 
1588  for( i = 0; i < nnonz; ++i )
1589  {
1590  for( j = i + 1; j < nnonz; ++j )
1591  {
1592  int i1;
1593  int i2;
1594 
1595  assert(nconspairs < conspairssize);
1596  assert(conspairs != NULL);
1597 
1598  i1 = perm[(i + failshift) % nnonz];
1599  i2 = perm[(j + failshift) % nnonz];
1600  conspairs[nconspairs].colindex = c;
1601 
1602  if( colinds[i1] < colinds[i2])
1603  {
1604  conspairs[nconspairs].consindex1 = colinds[i1];
1605  conspairs[nconspairs].consindex2 = colinds[i2];
1606  conspairs[nconspairs].conscoef1 = colvals[i1];
1607  conspairs[nconspairs].conscoef2 = colvals[i2];
1608  }
1609  else
1610  {
1611  conspairs[nconspairs].consindex1 = colinds[i2];
1612  conspairs[nconspairs].consindex2 = colinds[i1];
1613  conspairs[nconspairs].conscoef1 = colvals[i2];
1614  conspairs[nconspairs].conscoef2 = colvals[i1];
1615  }
1616  ++nconspairs;
1617  }
1618  }
1619  }
1620  else
1621  {
1622  ishashingcols[c] = FALSE;
1623  }
1624  }
1625 
1626  /* insert conspairs into hash table */
1627  for( c = 0; c < nconspairs; ++c )
1628  {
1629  SCIP_Bool insert;
1630  COLCONSPAIR* otherconspair;
1631 
1632  assert(conspairs != NULL);
1633 
1634  insert = TRUE;
1635 
1636  /* check if this pair is already contained in the hash table;
1637  * The loop is required due to the non-transitivity of the hash functions
1638  */
1639  while( (otherconspair = (COLCONSPAIR*)SCIPhashtableRetrieve(pairtable, (void*) &conspairs[c])) != NULL )
1640  {
1641  /* if the previous constraint pair has fewer or the same number of nonzeros in the attached column
1642  * we keep that pair and skip this one
1643  */
1644  if( SCIPmatrixGetColNNonzs(matrix, otherconspair->colindex) <=
1645  SCIPmatrixGetColNNonzs(matrix, conspairs[c].colindex) )
1646  {
1647  insert = FALSE;
1648  break;
1649  }
1650 
1651  /* this pairs column has fewer nonzeros, so remove the other pair from the hash table and loop */
1652  SCIP_CALL( SCIPhashtableRemove(pairtable, (void*) otherconspair) );
1653  }
1654 
1655  if( insert )
1656  {
1657  SCIP_CALL( SCIPhashtableInsert(pairtable, (void*) &conspairs[c]) );
1658  }
1659  }
1660 
1661  /* sort rows according to decreasingly sparsity */
1662  assert(colidxsorted != NULL);
1663  assert(colsparsity != NULL);
1664  for( c = 0; c < ncols; ++c )
1665  {
1666  colidxsorted[c] = c;
1667  colsparsity[c] = -SCIPmatrixGetColNNonzs(matrix, c);
1668  }
1669  SCIPsortIntInt(colsparsity, colidxsorted, ncols);
1670 
1671  /* loop over the columns and cancel nonzeros until maximum number of retrieves is reached */
1672  maxuseless = (SCIP_Longint)(presoldata->maxretrievefac * (SCIP_Real)ncols);
1673  nuseless = 0;
1674  for( c = 0; c < ncols && nuseless <= maxuseless; c++ )
1675  {
1676  int colidx;
1677  int nnonz;
1678 
1679  colidx = colidxsorted[c];
1680  nnonz = SCIPmatrixGetColNNonzs(matrix, colidx);
1681 
1682  if( isblockedvar[colidx] || nnonz < presoldata->mineliminatednonzeros )
1683  continue;
1684 
1685  /* since the function parameters for the max fillin are unsigned we do not need to handle the
1686  * unlimited (-1) case due to implicit conversion rules */
1687  SCIP_CALL( cancelCol(scip, matrix, presoldata, pairtable, ishashingcols, vars, isblockedvar, colidx, \
1688  presoldata->maxcontfillin == -1 ? INT_MAX : presoldata->maxcontfillin, \
1689  presoldata->maxintfillin == -1 ? INT_MAX : presoldata->maxintfillin, \
1690  presoldata->maxbinfillin == -1 ? INT_MAX : presoldata->maxbinfillin, \
1691  presoldata->maxconsiderednonzeros, presoldata->preserveintcoefs, \
1692  &nuseless, nchgcoefs, &numcancel, &nfillin, TRUE) );
1693  }
1694 
1695  if( numcancel > 0 )
1696  {
1697  *result = SCIP_SUCCESS;
1698  }
1699  }
1700 
1701  updateFailureStatistic(presoldata, numcancel > 0);
1702 
1703  SCIPfreeBufferArray(scip, &colsparsity);
1704  SCIPfreeBufferArray(scip, &colidxsorted);
1705 
1706  SCIPhashtableFree(&pairtable);
1707  SCIPfreeBufferArrayNull(scip, &conspairs);
1708 
1709  SCIPfreeBufferArray(scip, &isblockedvar);
1710  SCIPfreeBufferArray(scip, &vars);
1711  SCIPfreeBufferArray(scip, &ishashingcols);
1712  SCIPfreeBufferArray(scip, &perm);
1713  SCIPfreeBufferArray(scip, &scores);
1714 
1715  SCIPmatrixFree(scip, &matrix);
1716 
1717  return SCIP_OKAY;
1718 }
1719 
1720 /*
1721  * presolver specific interface methods
1722  */
1723 
1724 /** destructor of presolver to free user data (called when SCIP is exiting) */
1725 static
1726 SCIP_DECL_PRESOLFREE(presolFreeDualsparsify)
1727 { /*lint --e{715}*/
1728  SCIP_PRESOLDATA* presoldata;
1729 
1730  /* free presolver data */
1731  presoldata = SCIPpresolGetData(presol);
1732  assert(presoldata != NULL);
1733 
1734  SCIPfreeBlockMemory(scip, &presoldata);
1735  SCIPpresolSetData(presol, NULL);
1736 
1737  return SCIP_OKAY;
1738 }
1739 
1740 /** initialization method of presolver (called after problem was transformed) */
1741 static
1742 SCIP_DECL_PRESOLINIT(presolInitDualsparsify)
1743 {
1744  SCIP_PRESOLDATA* presoldata;
1745 
1746  /* set the counters in the init (and not in the initpre) callback such that they persist across restarts */
1747  presoldata = SCIPpresolGetData(presol);
1748  presoldata->ncancels = 0;
1749  presoldata->nfillin = 0;
1750  presoldata->nfailures = 0;
1751  presoldata->nwaitingcalls = 0;
1752  presoldata->naggregated = 0;
1753 
1754  return SCIP_OKAY;
1755 }
1756 
1757 /** creates the dualsparsify presolver and includes it in SCIP */
1759  SCIP* scip /**< SCIP data structure */
1760  )
1761 {
1762  SCIP_PRESOLDATA* presoldata;
1763  SCIP_PRESOL* presol;
1764 
1765  /* create dualsparsify presolver data */
1766  SCIP_CALL( SCIPallocBlockMemory(scip, &presoldata) );
1767 
1768  /* include presolver */
1770  PRESOL_TIMING, presolExecDualsparsify, presoldata) );
1771 
1772  SCIP_CALL( SCIPsetPresolCopy(scip, presol, presolCopyDualsparsify) );
1773  SCIP_CALL( SCIPsetPresolFree(scip, presol, presolFreeDualsparsify) );
1774  SCIP_CALL( SCIPsetPresolInit(scip, presol, presolInitDualsparsify) );
1775 
1777  "presolving/dualsparsify/enablecopy",
1778  "should dualsparsify presolver be copied to sub-SCIPs?",
1779  &presoldata->enablecopy, TRUE, DEFAULT_ENABLECOPY, NULL, NULL) );
1780 
1782  "presolving/dualsparsify/preserveintcoefs",
1783  "should we forbid cancellations that destroy integer coefficients?",
1784  &presoldata->preserveintcoefs, TRUE, DEFAULT_PRESERVEINTCOEFS, NULL, NULL) );
1785 
1787  "presolving/dualsparsify/preservegoodlocks",
1788  "should we preserve good locked properties of variables (at most one lock in one direction)?",
1789  &presoldata->preservegoodlocks, TRUE, DEFAULT_PRESERVEGOODLOCKS, NULL, NULL) );
1790 
1791  SCIP_CALL( SCIPaddIntParam(scip,
1792  "presolving/dualsparsify/maxcontfillin",
1793  "maximal fillin for continuous variables (-1: unlimited)",
1794  &presoldata->maxcontfillin, FALSE, DEFAULT_MAX_CONT_FILLIN, -1, INT_MAX, NULL, NULL) );
1795 
1796  SCIP_CALL( SCIPaddIntParam(scip,
1797  "presolving/dualsparsify/maxbinfillin",
1798  "maximal fillin for binary variables (-1: unlimited)",
1799  &presoldata->maxbinfillin, FALSE, DEFAULT_MAX_BIN_FILLIN, -1, INT_MAX, NULL, NULL) );
1800 
1801  SCIP_CALL( SCIPaddIntParam(scip,
1802  "presolving/dualsparsify/maxintfillin",
1803  "maximal fillin for integer variables including binaries (-1: unlimited)",
1804  &presoldata->maxintfillin, FALSE, DEFAULT_MAX_INT_FILLIN, -1, INT_MAX, NULL, NULL) );
1805 
1806  SCIP_CALL( SCIPaddIntParam(scip,
1807  "presolving/dualsparsify/maxconsiderednonzeros",
1808  "maximal number of considered nonzeros within one column (-1: no limit)",
1809  &presoldata->maxconsiderednonzeros, TRUE, DEFAULT_MAXCONSIDEREDNONZEROS, -1, INT_MAX, NULL, NULL) );
1810 
1811  SCIP_CALL( SCIPaddIntParam(scip,
1812  "presolving/dualsparsify/mineliminatednonzeros",
1813  "minimal eliminated nonzeros within one column if we need to add a constraint to the problem",
1814  &presoldata->mineliminatednonzeros, FALSE, DEFAULT_MINELIMINATEDNONZEROS, 0, INT_MAX, NULL, NULL) );
1815 
1817  "presolving/dualsparsify/maxretrievefac",
1818  "limit on the number of useless vs. useful hashtable retrieves as a multiple of the number of constraints",
1819  &presoldata->maxretrievefac, TRUE, DEFAULT_MAXRETRIEVEFAC, 0.0, SCIP_REAL_MAX, NULL, NULL) );
1820 
1822  "presolving/dualsparsify/waitingfac",
1823  "number of calls to wait until next execution as a multiple of the number of useless calls",
1824  &presoldata->waitingfac, TRUE, DEFAULT_WAITINGFAC, 0.0, SCIP_REAL_MAX, NULL, NULL) );
1825 
1826  return SCIP_OKAY;
1827 }
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
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:96
struct SCIP_PresolData SCIP_PRESOLDATA
Definition: type_presol.h:42
SCIP_VAR * SCIPmatrixGetVar(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1620
int SCIPmatrixGetNRows(SCIP_MATRIX *matrix)
Definition: matrix.c:1692
SCIP_RETCODE SCIPsetPresolFree(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLFREE((*presolfree)))
Definition: scip_presol.c:147
public methods for SCIP parameter handling
#define DEFAULT_MINELIMINATEDNONZEROS
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2487
#define PRESOL_TIMING
public methods for memory management
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17910
#define SCIP_MAXSTRLEN
Definition: def.h:293
SCIP_Bool SCIPvarIsInitial(SCIP_VAR *var)
Definition: var.c:17452
void SCIPmatrixRemoveColumnBounds(SCIP *scip, SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1129
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:130
cancel nonzeros of the constraint matrix based on the columns
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for timing
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1245
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17431
void SCIPmatrixFree(SCIP *scip, SCIP_MATRIX **matrix)
Definition: matrix.c:1032
void SCIPswapPointers(void **pointer1, void **pointer2)
Definition: misc.c:10291
#define FALSE
Definition: def.h:87
public methods for presolving plugins
static SCIP_DECL_PRESOLINIT(presolInitDualsparsify)
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10755
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
static SCIP_Real getMinActivitySingleRowWithoutCol(SCIP *scip, SCIP_MATRIX *matrix, int row, int col)
SCIP_PRESOLDATA * SCIPpresolGetData(SCIP_PRESOL *presol)
Definition: presol.c:503
#define DEFAULT_MAX_CONT_FILLIN
public methods for problem variables
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:99
#define DEFAULT_PRESERVEINTCOEFS
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:123
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
SCIP_Real SCIPmatrixGetRowMaxActivity(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1760
SCIP_Bool SCIPvarIsRemovable(SCIP_VAR *var)
Definition: var.c:17462
#define SCIPhashThree(a, b, c)
Definition: pub_misc.h:512
#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
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
static SCIP_DECL_PRESOLEXEC(presolExecDualsparsify)
static SCIP_DECL_HASHKEYVAL(consPairHashval)
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:2236
int SCIPmatrixGetRowNNonzs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1668
public methods for querying solving statistics
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17920
SCIP_Real SCIPmatrixGetRowLhs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1702
SCIP_RETCODE SCIPincludePresolDualsparsify(SCIP *scip)
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:8532
public methods for managing constraints
#define DEFAULT_MAXCONSIDEREDNONZEROS
SCIP_Real * SCIPmatrixGetColValPtr(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1528
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2769
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
#define DEFAULT_MAXRETRIEVEFAC
SCIP_Bool SCIPdoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:8595
void SCIPpresolSetData(SCIP_PRESOL *presol, SCIP_PRESOLDATA *presoldata)
Definition: presol.c:513
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:535
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:128
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:48
SCIP_RETCODE SCIPsetPresolInit(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLINIT((*presolinit)))
Definition: scip_presol.c:163
int * SCIPmatrixGetRowIdxPtr(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1656
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17251
#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
#define REALABS(x)
Definition: def.h:201
int SCIPmatrixGetRowNMaxActNegInf(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1796
#define SCIP_CALL(x)
Definition: def.h:384
#define DEFAULT_PRESERVEGOODLOCKS
void SCIPhashtableRemoveAll(SCIP_HASHTABLE *hashtable)
Definition: misc.c:2695
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_RETCODE SCIPhashtableRemove(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2617
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: graph_load.c:93
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:281
public methods for constraint handler plugins and constraints
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
public data structures and miscellaneous methods
#define PRESOL_MAXROUNDS
#define SCIP_Bool
Definition: def.h:84
#define MAX(x, y)
Definition: tclique_def.h:83
int * SCIPmatrixGetColIdxPtr(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1540
methods for debugging
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
Definition: presol.c:590
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
int SCIPgetNRuns(SCIP *scip)
Constraint handler for linear constraints in their most general form, .
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition: misc.c:2548
int SCIPmatrixGetRowNMinActNegInf(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1772
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
public methods for matrix
#define DEFAULT_ENABLECOPY
public methods for variable pricer plugins
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
Definition: misc.c:2286
#define SCIP_REAL_MAX
Definition: def.h:178
public methods for nonlinear relaxation
#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_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_VAR ** b
Definition: circlepacking.c:56
public methods for presolvers
general public methods
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1667
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)
public methods for the probing mode
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLCOPY((*presolcopy)))
Definition: scip_presol.c:131
public methods for message output
#define DEFAULT_WAITINGFAC
SCIP_VAR * a
Definition: circlepacking.c:57
static void updateFailureStatistic(SCIP_PRESOLDATA *presoldata, SCIP_Bool success)
#define SCIP_Real
Definition: def.h:177
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:694
public methods for message handling
SCIP_Bool SCIPdoNotAggr(SCIP *scip)
Definition: scip_var.c:8562
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:162
#define SCIPdebugAddSolVal(scip, var, val)
Definition: debug.h:280
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17416
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
int SCIPmatrixGetRowNMinActPosInf(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1784
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
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
SCIPallocBlockMemory(scip, subsol))
static SCIP_DECL_HASHKEYEQ(consPairsEqual)
public methods for global and local (sub)problems
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:17442
#define DEFAULT_MAX_INT_FILLIN
static SCIP_DECL_PRESOLFREE(presolFreeDualsparsify)
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
int SCIPmatrixGetNColumns(SCIP_MATRIX *matrix)
Definition: matrix.c:1564
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 DEFAULT_MAX_BIN_FILLIN
void SCIPsortIntReal(int *intarray, SCIP_Real *realarray, int len)
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:119
int SCIPmatrixGetColNNonzs(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1552
memory allocation routines