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