Scippy

SCIP

Solving Constraint Integer Programs

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