Scippy

SCIP

Solving Constraint Integer Programs

presol_sparsify.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-2019 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file presol_sparsify.c
17  * @brief cancel non-zeros of the constraint matrix
18  * @author Dieter Weninger
19  * @author Robert Lion Gottwald
20  * @author Ambros Gleixner
21  *
22  * This presolver attempts to cancel non-zero entries of the constraint
23  * matrix by adding scaled equalities to other constraints.
24  */
25 
26 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
27 
28 #include "blockmemshell/memory.h"
29 #include "scip/cons_linear.h"
30 #include "scip/presol_sparsify.h"
31 #include "scip/pub_cons.h"
32 #include "scip/pub_matrix.h"
33 #include "scip/pub_message.h"
34 #include "scip/pub_misc.h"
35 #include "scip/pub_misc_sort.h"
36 #include "scip/pub_presol.h"
37 #include "scip/pub_var.h"
38 #include "scip/scip_cons.h"
39 #include "scip/scip_general.h"
40 #include "scip/scip_mem.h"
41 #include "scip/scip_message.h"
42 #include "scip/scip_nlp.h"
43 #include "scip/scip_numerics.h"
44 #include "scip/scip_param.h"
45 #include "scip/scip_presol.h"
46 #include "scip/scip_pricer.h"
47 #include "scip/scip_prob.h"
48 #include "scip/scip_probing.h"
49 #include "scip/scip_timing.h"
50 #include <string.h>
51 
52 #define PRESOL_NAME "sparsify"
53 #define PRESOL_DESC "eliminate non-zero coefficients"
54 
55 #define PRESOL_PRIORITY -24000 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */
56 #define PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
57 #define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */
58 
59 #define DEFAULT_ENABLECOPY TRUE /**< should sparsify presolver be copied to sub-SCIPs? */
60 #define DEFAULT_CANCELLINEAR TRUE /**< should we cancel nonzeros in constraints of the linear constraint handler? */
61 #define DEFAULT_PRESERVEINTCOEFS TRUE /**< should we forbid cancellations that destroy integer coefficients? */
62 #define DEFAULT_MAX_CONT_FILLIN 0 /**< default value for the maximal fillin for continuous variables */
63 #define DEFAULT_MAX_BIN_FILLIN 0 /**< default value for the maximal fillin for binary variables */
64 #define DEFAULT_MAX_INT_FILLIN 0 /**< default value for the maximal fillin for integer variables (including binary) */
65 #define DEFAULT_MAXNONZEROS -1 /**< maximal support of one equality to be used for cancelling (-1: no limit) */
66 #define DEFAULT_MAXCONSIDEREDNONZEROS 70 /**< maximal number of considered non-zeros within one row (-1: no limit) */
67 #define DEFAULT_ROWSORT 'd' /**< order in which to process inequalities ('n'o sorting, 'i'ncreasing nonzeros, 'd'ecreasing nonzeros) */
68 #define DEFAULT_MAXRETRIEVEFAC 100.0 /**< limit on the number of useless vs. useful hashtable retrieves as a multiple of the number of constraints */
69 #define DEFAULT_WAITINGFAC 2.0 /**< number of calls to wait until next execution as a multiple of the number of useless calls */
70 
71 #define MAXSCALE 1000.0 /**< maximal allowed scale for cancelling non-zeros */
72 
73 
74 /*
75  * Data structures
76  */
77 
78 /** presolver data */
79 struct SCIP_PresolData
80 {
81  int ncancels; /**< total number of canceled nonzeros (net value, i.e., removed minus added nonzeros) */
82  int nfillin; /**< total number of added nonzeros */
83  int nfailures; /**< number of calls to presolver without success */
84  int nwaitingcalls; /**< number of presolver calls until next real execution */
85  int maxcontfillin; /**< maximal fillin for continuous variables */
86  int maxintfillin; /**< maximal fillin for integer variables*/
87  int maxbinfillin; /**< maximal fillin for binary variables */
88  int maxnonzeros; /**< maximal support of one equality to be used for cancelling (-1: no limit) */
89  int maxconsiderednonzeros;/**< maximal number of considered non-zeros within one row (-1: no limit) */
90  SCIP_Real maxretrievefac; /**< limit on the number of useless vs. useful hashtable retrieves as a multiple of the number of constraints */
91  SCIP_Real waitingfac; /**< number of calls to wait until next execution as a multiple of the number of useless calls */
92  char rowsort; /**< order in which to process inequalities ('n'o sorting, 'i'ncreasing nonzeros, 'd'ecreasing nonzeros) */
93  SCIP_Bool enablecopy; /**< should sparsify presolver be copied to sub-SCIPs? */
94  SCIP_Bool cancellinear; /**< should we cancel nonzeros in constraints of the linear constraint handler? */
95  SCIP_Bool preserveintcoefs; /**< should we forbid cancellations that destroy integer coefficients? */
96 };
97 
98 /** structure representing a pair of variables in a row; used for lookup in a hashtable */
99 struct RowVarPair
100 {
101  int rowindex;
106 };
107 
108 typedef struct RowVarPair ROWVARPAIR;
109 
110 /*
111  * Local methods
112  */
113 
114 /** returns TRUE iff both keys are equal */
115 static
116 SCIP_DECL_HASHKEYEQ(varPairsEqual)
117 { /*lint --e{715}*/
118  SCIP* scip;
119  ROWVARPAIR* varpair1;
120  ROWVARPAIR* varpair2;
121  SCIP_Real ratio1;
122  SCIP_Real ratio2;
123 
124  scip = (SCIP*) userptr;
125  varpair1 = (ROWVARPAIR*) key1;
126  varpair2 = (ROWVARPAIR*) key2;
127 
128  if( varpair1->varindex1 != varpair2->varindex1 )
129  return FALSE;
130 
131  if( varpair1->varindex2 != varpair2->varindex2 )
132  return FALSE;
133 
134  ratio1 = varpair1->varcoef2 / varpair1->varcoef1;
135  ratio2 = varpair2->varcoef2 / varpair2->varcoef1;
136 
137  return SCIPisEQ(scip, ratio1, ratio2);
138 }
139 
140 /** returns the hash value of the key */
141 static
142 SCIP_DECL_HASHKEYVAL(varPairHashval)
143 { /*lint --e{715}*/
144  ROWVARPAIR* varpair;
145 
146  varpair = (ROWVARPAIR*) key;
147 
148  return SCIPhashTwo(SCIPcombineTwoInt(varpair->varindex1, varpair->varindex2),
149  SCIPrealHashCode(varpair->varcoef2 / varpair->varcoef1));
150 }
151 
152 /** try non-zero cancellation for given row */
153 static
155  SCIP* scip, /**< SCIP datastructure */
156  SCIP_MATRIX* matrix, /**< the constraint matrix */
157  SCIP_HASHTABLE* pairtable, /**< the hashtable containing ROWVARPAIR's of equations */
158  int rowidx, /**< index of row to try non-zero cancellation for */
159  int maxcontfillin, /**< maximal fill-in allowed for continuous variables */
160  int maxintfillin, /**< maximal fill-in allowed for integral variables */
161  int maxbinfillin, /**< maximal fill-in allowed for binary variables */
162  int maxconsiderednonzeros, /**< maximal number of non-zeros to consider for cancellation */
163  SCIP_Bool preserveintcoefs, /**< only perform non-zero cancellation if integrality of coefficients is preserved? */
164  SCIP_Longint* nuseless, /**< pointer to update number of useless hashtable retrieves */
165  int* nchgcoefs, /**< pointer to update number of changed coefficients */
166  int* ncanceled, /**< pointer to update number of canceled nonzeros */
167  int* nfillin /**< pointer to update the produced fill-in */
168  )
169 {
170  int* cancelrowinds;
171  SCIP_Real* cancelrowvals;
172  SCIP_Real cancellhs;
173  SCIP_Real cancelrhs;
174  SCIP_Real bestcancelrate;
175  int* tmpinds;
176  int* locks;
177  SCIP_Real* tmpvals;
178  int cancelrowlen;
179  int* rowidxptr;
180  SCIP_Real* rowvalptr;
181  int nchgcoef;
182  int nretrieves;
183  int bestnfillin;
184  SCIP_Real mincancelrate;
185  SCIP_Bool rowiseq;
186  SCIP_Bool swapped = FALSE;
187  SCIP_CONS* cancelcons;
188 
189  rowiseq = SCIPisEQ(scip, SCIPmatrixGetRowLhs(matrix, rowidx), SCIPmatrixGetRowRhs(matrix, rowidx));
190 
191  cancelrowlen = SCIPmatrixGetRowNNonzs(matrix, rowidx);
192  rowidxptr = SCIPmatrixGetRowIdxPtr(matrix, rowidx);
193  rowvalptr = SCIPmatrixGetRowValPtr(matrix, rowidx);
194 
195  cancelcons = SCIPmatrixGetCons(matrix, rowidx);
196 
197  mincancelrate = 0.0;
198 
199  /* for set packing and logicor constraints, only accept equalities where all modified coefficients are cancelled */
200  if( SCIPconsGetHdlr(cancelcons) == SCIPfindConshdlr(scip, "setppc") ||
201  SCIPconsGetHdlr(cancelcons) == SCIPfindConshdlr(scip, "logicor") )
202  mincancelrate = 1.0;
203 
204  SCIP_CALL( SCIPduplicateBufferArray(scip, &cancelrowinds, rowidxptr, cancelrowlen) );
205  SCIP_CALL( SCIPduplicateBufferArray(scip, &cancelrowvals, rowvalptr, cancelrowlen) );
206  SCIP_CALL( SCIPallocBufferArray(scip, &tmpinds, cancelrowlen) );
207  SCIP_CALL( SCIPallocBufferArray(scip, &tmpvals, cancelrowlen) );
208  SCIP_CALL( SCIPallocBufferArray(scip, &locks, cancelrowlen) );
209 
210  cancellhs = SCIPmatrixGetRowLhs(matrix, rowidx);
211  cancelrhs = SCIPmatrixGetRowRhs(matrix, rowidx);
212 
213  nchgcoef = 0;
214  nretrieves = 0;
215  while( TRUE ) /*lint !e716 */
216  {
217  SCIP_Real bestscale;
218  int bestcand;
219  int i;
220  int j;
221  ROWVARPAIR rowvarpair;
222  int maxlen;
223 
224  bestscale = 1.0;
225  bestcand = -1;
226  bestnfillin = 0;
227  bestcancelrate = 0.0;
228 
229  for( i = 0; i < cancelrowlen; ++i )
230  {
231  tmpinds[i] = i;
232  locks[i] = SCIPmatrixGetColNDownlocks(matrix, cancelrowinds[i]) + SCIPmatrixGetColNUplocks(matrix, cancelrowinds[i]);
233  }
234 
235  SCIPsortIntInt(locks, tmpinds, cancelrowlen);
236 
237  maxlen = cancelrowlen;
238  if( maxconsiderednonzeros >= 0 )
239  maxlen = MIN(cancelrowlen, maxconsiderednonzeros);
240 
241  for( i = 0; i < maxlen; ++i )
242  {
243  for( j = i + 1; j < maxlen; ++j )
244  {
245  int a,b;
246  int ncancel;
247  int ncontfillin;
248  int nintfillin;
249  int nbinfillin;
250  int ntotfillin;
251  int eqrowlen;
252  ROWVARPAIR* eqrowvarpair;
253  SCIP_Real* eqrowvals;
254  int* eqrowinds;
255  SCIP_Real scale;
256  SCIP_Real cancelrate;
257  int i1,i2;
258  SCIP_Bool abortpair;
259 
260  i1 = tmpinds[i];
261  i2 = tmpinds[j];
262 
263  assert(cancelrowinds[i] < cancelrowinds[j]);
264 
265  if( cancelrowinds[i1] < cancelrowinds[i2] )
266  {
267  rowvarpair.varindex1 = cancelrowinds[i1];
268  rowvarpair.varindex2 = cancelrowinds[i2];
269  rowvarpair.varcoef1 = cancelrowvals[i1];
270  rowvarpair.varcoef2 = cancelrowvals[i2];
271  }
272  else
273  {
274  rowvarpair.varindex1 = cancelrowinds[i2];
275  rowvarpair.varindex2 = cancelrowinds[i1];
276  rowvarpair.varcoef1 = cancelrowvals[i2];
277  rowvarpair.varcoef2 = cancelrowvals[i1];
278  }
279 
280  eqrowvarpair = (ROWVARPAIR*)SCIPhashtableRetrieve(pairtable, (void*) &rowvarpair);
281  nretrieves++;
282 
283  if( eqrowvarpair == NULL || eqrowvarpair->rowindex == rowidx )
284  continue;
285 
286  /* if the row we want to cancel is an equality, we will only use equalities
287  * for canceling with less non-zeros and if the number of non-zeros is equal we use the
288  * rowindex as tie-breaker to avoid cyclic non-zero cancellation
289  */
290  eqrowlen = SCIPmatrixGetRowNNonzs(matrix, eqrowvarpair->rowindex);
291  if( rowiseq && (cancelrowlen < eqrowlen || (cancelrowlen == eqrowlen && rowidx < eqrowvarpair->rowindex)) )
292  continue;
293 
294  eqrowvals = SCIPmatrixGetRowValPtr(matrix, eqrowvarpair->rowindex);
295  eqrowinds = SCIPmatrixGetRowIdxPtr(matrix, eqrowvarpair->rowindex);
296 
297  scale = -rowvarpair.varcoef1 / eqrowvarpair->varcoef1;
298 
299  if( REALABS(scale) > MAXSCALE )
300  continue;
301 
302  a = 0;
303  b = 0;
304  ncancel = 0;
305 
306  ncontfillin = 0;
307  nintfillin = 0;
308  nbinfillin = 0;
309  abortpair = FALSE;
310  while( a < cancelrowlen && b < eqrowlen )
311  {
312  if( cancelrowinds[a] == eqrowinds[b] )
313  {
314  SCIP_Real newcoef;
315 
316  newcoef = cancelrowvals[a] + scale * eqrowvals[b];
317 
318  /* check if coefficient is cancelled */
319  if( SCIPisZero(scip, newcoef) )
320  {
321  ++ncancel;
322  }
323  /* otherwise, check if integral coefficients are preserved if the column is integral */
324  else if( (preserveintcoefs && SCIPvarIsIntegral(SCIPmatrixGetVar(matrix, cancelrowinds[a])) &&
325  SCIPisIntegral(scip, cancelrowvals[a]) && !SCIPisIntegral(scip, newcoef)) )
326  {
327  abortpair = TRUE;
328  break;
329  }
330  /* finally, check if locks could be modified in a bad way due to flipped signs */
331  else if( (SCIPisInfinity(scip, cancelrhs) || SCIPisInfinity(scip, -cancellhs)) &&
332  COPYSIGN(1.0, newcoef) != COPYSIGN(1.0, cancelrowvals[a]) ) /*lint !e777*/
333  {
334  /* do not flip signs for non-canceled coefficients if this adds a lock to a variable that had at most one lock
335  * in that direction before, except if the other direction gets unlocked
336  */
337  if( (cancelrowvals[a] > 0.0 && ! SCIPisInfinity(scip, cancelrhs)) ||
338  (cancelrowvals[a] < 0.0 && ! SCIPisInfinity(scip, -cancellhs)) )
339  {
340  /* if we get into this case the variable had a positive coefficient in a <= constraint or a negative
341  * coefficient in a >= constraint, e.g. an uplock. If this was the only uplock we do not abort their
342  * cancelling, otherwise we abort if we had a single or no downlock and add one
343  */
344  if( SCIPmatrixGetColNUplocks(matrix, cancelrowinds[a]) > 1 &&
345  SCIPmatrixGetColNDownlocks(matrix, cancelrowinds[a]) <= 1 )
346  {
347  abortpair = TRUE;
348  break;
349  }
350  }
351 
352  if( (cancelrowvals[a] < 0.0 && ! SCIPisInfinity(scip, cancelrhs)) ||
353  (cancelrowvals[a] > 0.0 && ! SCIPisInfinity(scip, -cancellhs)) )
354  {
355  /* symmetric case where the variable had a downlock */
356  if( SCIPmatrixGetColNDownlocks(matrix, cancelrowinds[a]) > 1 &&
357  SCIPmatrixGetColNUplocks(matrix, cancelrowinds[a]) <= 1 )
358  {
359  abortpair = TRUE;
360  break;
361  }
362  }
363  }
364 
365  ++a;
366  ++b;
367  }
368  else if( cancelrowinds[a] < eqrowinds[b] )
369  {
370  ++a;
371  }
372  else
373  {
374  SCIP_Real newcoef;
375  SCIP_VAR* var;
376 
377  var = SCIPmatrixGetVar(matrix, eqrowinds[b]);
378  newcoef = scale * eqrowvals[b];
379 
380  if( (newcoef > 0.0 && ! SCIPisInfinity(scip, cancelrhs)) ||
381  (newcoef < 0.0 && ! SCIPisInfinity(scip, -cancellhs)) )
382  {
383  if( SCIPmatrixGetColNUplocks(matrix, eqrowinds[b]) <= 1 )
384  {
385  abortpair = TRUE;
386  ++b;
387  break;
388  }
389  }
390 
391  if( (newcoef < 0.0 && ! SCIPisInfinity(scip, cancelrhs)) ||
392  (newcoef > 0.0 && ! SCIPisInfinity(scip, -cancellhs)) )
393  {
394  if( SCIPmatrixGetColNDownlocks(matrix, eqrowinds[b]) <= 1 )
395  {
396  abortpair = TRUE;
397  ++b;
398  break;
399  }
400  }
401 
402  ++b;
403 
404  if( SCIPvarIsIntegral(var) )
405  {
406  if( SCIPvarIsBinary(var) && ++nbinfillin > maxbinfillin )
407  {
408  abortpair = TRUE;
409  break;
410  }
411 
412  if( ++nintfillin > maxintfillin )
413  {
414  abortpair = TRUE;
415  break;
416  }
417  }
418  else
419  {
420  if( ++ncontfillin > maxcontfillin )
421  {
422  abortpair = TRUE;
423  break;
424  }
425  }
426  }
427  }
428 
429  if( abortpair )
430  continue;
431 
432  while( b < eqrowlen )
433  {
434  SCIP_VAR* var = SCIPmatrixGetVar(matrix, eqrowinds[b]);
435  ++b;
436  if( SCIPvarIsIntegral(var) )
437  {
438  if( SCIPvarIsBinary(var) && ++nbinfillin > maxbinfillin )
439  break;
440  if( ++nintfillin > maxintfillin )
441  break;
442  }
443  else
444  {
445  if( ++ncontfillin > maxcontfillin )
446  break;
447  }
448  }
449 
450  if( ncontfillin > maxcontfillin || nbinfillin > maxbinfillin || nintfillin > maxintfillin )
451  continue;
452 
453  ntotfillin = nintfillin + ncontfillin;
454 
455  if( ntotfillin >= ncancel )
456  continue;
457 
458  cancelrate = (ncancel - ntotfillin) / (SCIP_Real) eqrowlen;
459 
460  if( cancelrate < mincancelrate )
461  continue;
462 
463  if( cancelrate > bestcancelrate )
464  {
465  bestnfillin = ntotfillin;
466  bestcand = eqrowvarpair->rowindex;
467  bestscale = scale;
468  bestcancelrate = cancelrate;
469 
470  /* stop looking if the current candidate does not create any fill-in or alter coefficients */
471  if( cancelrate == 1.0 )
472  break;
473  }
474 
475  /* we accept the best candidate immediately if it does not create any fill-in or alter coefficients */
476  if( bestcand != -1 && bestcancelrate == 1.0 )
477  break;
478  }
479  }
480 
481  if( bestcand != -1 )
482  {
483  int a;
484  int b;
485  SCIP_Real* eqrowvals;
486  int* eqrowinds;
487  int eqrowlen;
488  int tmprowlen;
489  SCIP_Real eqrhs;
490 
491  eqrowvals = SCIPmatrixGetRowValPtr(matrix, bestcand);
492  eqrowinds = SCIPmatrixGetRowIdxPtr(matrix, bestcand);
493  eqrowlen = SCIPmatrixGetRowNNonzs(matrix, bestcand);
494  eqrhs = SCIPmatrixGetRowRhs(matrix, bestcand);
495 
496  a = 0;
497  b = 0;
498  tmprowlen = 0;
499 
500  if( !SCIPisZero(scip, eqrhs) )
501  {
502  if( !SCIPisInfinity(scip, -cancellhs) )
503  cancellhs += bestscale * eqrhs;
504  if( !SCIPisInfinity(scip, cancelrhs) )
505  cancelrhs += bestscale * eqrhs;
506  }
507 
508  while( a < cancelrowlen && b < eqrowlen )
509  {
510  if( cancelrowinds[a] == eqrowinds[b] )
511  {
512  SCIP_Real val = cancelrowvals[a] + bestscale * eqrowvals[b];
513 
514  if( !SCIPisZero(scip, val) )
515  {
516  tmpinds[tmprowlen] = cancelrowinds[a];
517  tmpvals[tmprowlen] = val;
518  ++tmprowlen;
519  }
520  ++nchgcoef;
521 
522  ++a;
523  ++b;
524  }
525  else if( cancelrowinds[a] < eqrowinds[b] )
526  {
527  tmpinds[tmprowlen] = cancelrowinds[a];
528  tmpvals[tmprowlen] = cancelrowvals[a];
529  ++tmprowlen;
530  ++a;
531  }
532  else
533  {
534  tmpinds[tmprowlen] = eqrowinds[b];
535  tmpvals[tmprowlen] = eqrowvals[b] * bestscale;
536  ++nchgcoef;
537  ++tmprowlen;
538  ++b;
539  }
540  }
541 
542  while( a < cancelrowlen )
543  {
544  tmpinds[tmprowlen] = cancelrowinds[a];
545  tmpvals[tmprowlen] = cancelrowvals[a];
546  ++tmprowlen;
547  ++a;
548  }
549 
550  while( b < eqrowlen )
551  {
552  tmpinds[tmprowlen] = eqrowinds[b];
553  tmpvals[tmprowlen] = eqrowvals[b] * bestscale;
554  ++nchgcoef;
555  ++tmprowlen;
556  ++b;
557  }
558 
559  /* update fill-in counter */
560  *nfillin += bestnfillin;
561 
562  /* swap the temporary arrays so that the cancelrowinds and cancelrowvals arrays, contain the new
563  * changed row, and the tmpinds and tmpvals arrays can be overwritten in the next iteration
564  */
565  SCIPswapPointers((void**) &tmpinds, (void**) &cancelrowinds);
566  SCIPswapPointers((void**) &tmpvals, (void**) &cancelrowvals);
567  cancelrowlen = tmprowlen;
568  swapped = !swapped;
569  }
570  else
571  break;
572  }
573 
574  if( nchgcoef != 0 )
575  {
576  SCIP_CONS* cons;
577  SCIP_VAR** consvars;
578 
579  int i;
580 
581  SCIP_CALL( SCIPallocBufferArray(scip, &consvars, cancelrowlen) );
582 
583  for( i = 0; i < cancelrowlen; ++i )
584  consvars[i] = SCIPmatrixGetVar(matrix, cancelrowinds[i]);
585 
586  /* create sparsified constraint and add it to scip */
587  SCIP_CALL( SCIPcreateConsLinear(scip, &cons, SCIPmatrixGetRowName(matrix, rowidx), cancelrowlen, consvars, cancelrowvals,
588  cancellhs, cancelrhs, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
589  SCIP_CALL( SCIPdelCons(scip, SCIPmatrixGetCons(matrix, rowidx)) );
590  SCIP_CALL( SCIPaddCons(scip, cons) );
591 
592 #ifdef SCIP_MORE_DEBUG
593  SCIPdebugMsg(scip, "########\n");
594  SCIPdebugMsg(scip, "old:\n");
595  SCIPmatrixPrintRow(scip, matrix, rowidx);
596  SCIPdebugMsg(scip, "new:\n");
597  SCIPdebugPrintCons(scip, cons, NULL);
598  SCIPdebugMsg(scip, "########\n");
599 #endif
600 
601  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
602 
603  /* update counters */
604  *nchgcoefs += nchgcoef;
605  *ncanceled += SCIPmatrixGetRowNNonzs(matrix, rowidx) - cancelrowlen;
606 
607  /* if successful, decrease the useless hashtable retrieves counter; the rationale here is that we want to keep
608  * going if, after many useless calls that almost exceeded the budget, we finally reach a useful section; but we
609  * don't allow a negative build-up for the case that the useful section is all at the beginning and we just want
610  * to quit quickly afterwards
611  */
612  *nuseless -= nretrieves;
613  *nuseless = MAX(*nuseless, 0);
614 
615  SCIPfreeBufferArray(scip, &consvars);
616  }
617  else
618  {
619  /* if not successful, increase useless hashtable retrieves counter */
620  *nuseless += nretrieves;
621  }
622 
623  SCIPfreeBufferArray(scip, &locks);
624  if( !swapped )
625  {
626  SCIPfreeBufferArray(scip, &tmpvals);
627  SCIPfreeBufferArray(scip, &tmpinds);
628  SCIPfreeBufferArray(scip, &cancelrowvals);
629  SCIPfreeBufferArray(scip, &cancelrowinds);
630  }
631  else
632  {
633  SCIPfreeBufferArray(scip, &cancelrowvals);
634  SCIPfreeBufferArray(scip, &cancelrowinds);
635  SCIPfreeBufferArray(scip, &tmpvals);
636  SCIPfreeBufferArray(scip, &tmpinds);
637  }
638 
639  return SCIP_OKAY;
640 }
641 
642 /** updates failure counter after one execution */
643 static
645  SCIP_PRESOLDATA* presoldata, /**< presolver data */
646  SCIP_Bool success /**< was this execution successful? */
647  )
648 {
649  assert(presoldata != NULL);
650 
651  if( success )
652  {
653  presoldata->nfailures = 0;
654  presoldata->nwaitingcalls = 0;
655  }
656  else
657  {
658  presoldata->nfailures++;
659  presoldata->nwaitingcalls = (int)(presoldata->waitingfac*(SCIP_Real)presoldata->nfailures);
660  }
661 }
662 
663 
664 /*
665  * Callback methods of presolver
666  */
667 
668 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
669 static
670 SCIP_DECL_PRESOLCOPY(presolCopySparsify)
671 {
672  SCIP_PRESOLDATA* presoldata;
673 
674  assert(scip != NULL);
675  assert(presol != NULL);
676  assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
677 
678  /* call inclusion method of presolver if copying is enabled */
679  presoldata = SCIPpresolGetData(presol);
680  assert(presoldata != NULL);
681  if( presoldata->enablecopy )
682  {
684  }
685 
686  return SCIP_OKAY;
687 }
688 
689 /** execution method of presolver */
690 static
691 SCIP_DECL_PRESOLEXEC(presolExecSparsify)
692 { /*lint --e{715}*/
693  SCIP_MATRIX* matrix;
694  SCIP_Bool initialized;
695  SCIP_Bool complete;
696  int nrows;
697  int r;
698  int i;
699  int j;
700  int numcancel;
701  int oldnchgcoefs;
702  int nfillin;
703  int* locks;
704  int* perm;
705  int* rowidxsorted;
706  int* rowsparsity;
707  SCIP_HASHTABLE* pairtable;
708  ROWVARPAIR* varpairs;
709  int nvarpairs;
710  int varpairssize;
711  SCIP_PRESOLDATA* presoldata;
712  SCIP_Longint maxuseless;
713  SCIP_Longint nuseless;
714  SCIP_CONSHDLR* linearhdlr;
715 
716  assert(result != NULL);
717 
718  *result = SCIP_DIDNOTRUN;
719 
721  return SCIP_OKAY;
722 
724  return SCIP_OKAY;
725 
726  presoldata = SCIPpresolGetData(presol);
727 
728  if( presoldata->nwaitingcalls > 0 )
729  {
730  presoldata->nwaitingcalls--;
731  SCIPdebugMsg(scip, "skipping sparsify: nfailures=%d, nwaitingcalls=%d\n", presoldata->nfailures,
732  presoldata->nwaitingcalls);
733  return SCIP_OKAY;
734  }
735 
736  /* if we want to cancel only from specialized constraints according to the parameter, then we can skip execution if
737  * only linear constraints are present
738  */
739  linearhdlr = SCIPfindConshdlr(scip, "linear");
740  if( !presoldata->cancellinear && linearhdlr != NULL && SCIPconshdlrGetNConss(linearhdlr) >= SCIPgetNConss(scip) )
741  {
742  SCIPdebugMsg(scip, "skipping sparsify: only linear constraints found\n");
743  return SCIP_OKAY;
744  }
745 
746  SCIPdebugMsg(scip, "starting sparsify. . .\n");
747  *result = SCIP_DIDNOTFIND;
748 
749  matrix = NULL;
750  SCIP_CALL( SCIPmatrixCreate(scip, &matrix, &initialized, &complete) );
751 
752  /* we only work on pure MIPs currently */
753  if( initialized && complete )
754  {
755  nrows = SCIPmatrixGetNRows(matrix);
756 
757  /* sort rows by column indices */
758  for( i = 0; i < nrows; i++ )
759  {
760  int* rowpnt = SCIPmatrixGetRowIdxPtr(matrix, i);
761  SCIP_Real* valpnt = SCIPmatrixGetRowValPtr(matrix, i);
762  SCIPsortIntReal(rowpnt, valpnt, SCIPmatrixGetRowNNonzs(matrix, i));
763  }
764 
767 
768  /* loop over all rows and create var pairs */
769  numcancel = 0;
770  nfillin = 0;
771  varpairssize = 0;
772  nvarpairs = 0;
773  varpairs = NULL;
774  SCIP_CALL( SCIPhashtableCreate(&pairtable, SCIPblkmem(scip), 1, SCIPhashGetKeyStandard, varPairsEqual, varPairHashval, (void*) scip) );
775 
776  /* collect equalities and their number of non-zeros */
777  for( r = 0; r < nrows; r++ )
778  {
779  int nnonz;
780 
781  nnonz = SCIPmatrixGetRowNNonzs(matrix, r);
782 
783  /* consider equalities with support at most maxnonzeros; skip singleton equalities, because these are faster
784  * processed by trivial presolving
785  */
786  if( nnonz >= 2 && (presoldata->maxnonzeros < 0 || nnonz <= presoldata->maxnonzeros)
787  && SCIPisEQ(scip, SCIPmatrixGetRowRhs(matrix, r), SCIPmatrixGetRowLhs(matrix, r)) )
788  {
789  int* rowinds;
790  SCIP_Real* rowvals;
791  int npairs;
792  int failshift;
793 
794  rowinds = SCIPmatrixGetRowIdxPtr(matrix, r);
795  rowvals = SCIPmatrixGetRowValPtr(matrix, r);
796 
797  for( i = 0; i < nnonz; ++i )
798  {
799  perm[i] = i;
800  locks[i] = SCIPmatrixGetColNDownlocks(matrix, rowinds[i]) + SCIPmatrixGetColNUplocks(matrix, rowinds[i]);
801  }
802 
803  SCIPsortIntInt(locks, perm, nnonz);
804 
805  if( presoldata->maxconsiderednonzeros >= 0 )
806  nnonz = MIN(nnonz, presoldata->maxconsiderednonzeros);
807 
808  npairs = (nnonz * (nnonz - 1)) / 2;
809  if( nvarpairs + npairs > varpairssize )
810  {
811  int newsize = SCIPcalcMemGrowSize(scip, nvarpairs + npairs);
812  SCIP_CALL( SCIPreallocBufferArray(scip, &varpairs, newsize) );
813  varpairssize = newsize;
814  }
815 
816  /* if we are called after one or more failures, i.e., executions without finding cancellations, then we
817  * shift the section of nonzeros considered; in the case that the maxconsiderednonzeros limit is hit, this
818  * results in different variable pairs being tried and avoids trying the same useless cancellations
819  * repeatedly
820  */
821  failshift = presoldata->nfailures*presoldata->maxconsiderednonzeros;
822 
823  for( i = 0; i < nnonz; ++i )
824  {
825  for( j = i + 1; j < nnonz; ++j )
826  {
827  int i1;
828  int i2;
829 
830  assert(nvarpairs < varpairssize);
831  assert(varpairs != NULL);
832 
833  i1 = perm[(i + failshift) % nnonz];
834  i2 = perm[(j + failshift) % nnonz];
835  varpairs[nvarpairs].rowindex = r;
836 
837  if( rowinds[i1] < rowinds[i2])
838  {
839  varpairs[nvarpairs].varindex1 = rowinds[i1];
840  varpairs[nvarpairs].varindex2 = rowinds[i2];
841  varpairs[nvarpairs].varcoef1 = rowvals[i1];
842  varpairs[nvarpairs].varcoef2 = rowvals[i2];
843  }
844  else
845  {
846  varpairs[nvarpairs].varindex1 = rowinds[i2];
847  varpairs[nvarpairs].varindex2 = rowinds[i1];
848  varpairs[nvarpairs].varcoef1 = rowvals[i2];
849  varpairs[nvarpairs].varcoef2 = rowvals[i1];
850  }
851  ++nvarpairs;
852  }
853  }
854  }
855  }
856 
857  /* insert varpairs into hash table */
858  for( r = 0; r < nvarpairs; ++r )
859  {
860  SCIP_Bool insert;
861  ROWVARPAIR* othervarpair;
862 
863  assert(varpairs != NULL);
864 
865  insert = TRUE;
866 
867  /* check if this pair is already contained in the hash table;
868  * The loop is required due to the non-transitivity of the hash functions
869  */
870  while( (othervarpair = (ROWVARPAIR*)SCIPhashtableRetrieve(pairtable, (void*) &varpairs[r])) != NULL )
871  {
872  /* if the previous variable pair has fewer or the same number of non-zeros in the attached row
873  * we keep that pair and skip this one
874  */
875  if( SCIPmatrixGetRowNNonzs(matrix, othervarpair->rowindex) <= SCIPmatrixGetRowNNonzs(matrix, varpairs[r].rowindex) )
876  {
877  insert = FALSE;
878  break;
879  }
880 
881  /* this pairs row has fewer non-zeros, so remove the other pair from the hash table and loop */
882  SCIP_CALL( SCIPhashtableRemove(pairtable, (void*) othervarpair) );
883  }
884 
885  if( insert )
886  {
887  SCIP_CALL( SCIPhashtableInsert(pairtable, (void*) &varpairs[r]) );
888  }
889  }
890 
891  /* sort rows according to parameter value */
892  if( presoldata->rowsort == 'i' || presoldata->rowsort == 'd' )
893  {
894  SCIP_CALL( SCIPallocBufferArray(scip, &rowidxsorted, nrows) );
895  SCIP_CALL( SCIPallocBufferArray(scip, &rowsparsity, nrows) );
896  for( r = 0; r < nrows; ++r )
897  rowidxsorted[r] = r;
898  if( presoldata->rowsort == 'i' )
899  {
900  for( r = 0; r < nrows; ++r )
901  rowsparsity[r] = SCIPmatrixGetRowNNonzs(matrix, r);
902  }
903  else if( presoldata->rowsort == 'd' )
904  {
905  for( r = 0; r < nrows; ++r )
906  rowsparsity[r] = -SCIPmatrixGetRowNNonzs(matrix, r);
907  }
908  SCIPsortIntInt(rowsparsity, rowidxsorted, nrows);
909  }
910  else
911  {
912  assert(presoldata->rowsort == 'n');
913  rowidxsorted = NULL;
914  rowsparsity = NULL;
915  }
916 
917  /* loop over the rows and cancel non-zeros until maximum number of retrieves is reached */
918  maxuseless = (SCIP_Longint)(presoldata->maxretrievefac * (SCIP_Real)nrows);
919  nuseless = 0;
920  oldnchgcoefs = *nchgcoefs;
921  for( r = 0; r < nrows && nuseless <= maxuseless; r++ )
922  {
923  int rowidx;
924 
925  rowidx = rowidxsorted != NULL ? rowidxsorted[r] : r;
926 
927  /* check whether we want to cancel only from specialized constraints; one reasoning behind this may be that
928  * cancelling fractional coefficients requires more numerical care than is currently implemented in method
929  * cancelRow()
930  */
931  assert(SCIPmatrixGetCons(matrix, rowidx) != NULL);
932  if( !presoldata->cancellinear && SCIPconsGetHdlr(SCIPmatrixGetCons(matrix, rowidx)) == linearhdlr )
933  continue;
934 
935  /* since the function parameters for the max fillin are unsigned we do not need to handle the
936  * unlimited (-1) case due to implicit conversion rules */
937  SCIP_CALL( cancelRow(scip, matrix, pairtable, rowidx, \
938  presoldata->maxcontfillin == -1 ? INT_MAX : presoldata->maxcontfillin, \
939  presoldata->maxintfillin == -1 ? INT_MAX : presoldata->maxintfillin, \
940  presoldata->maxbinfillin == -1 ? INT_MAX : presoldata->maxbinfillin, \
941  presoldata->maxconsiderednonzeros, presoldata->preserveintcoefs, \
942  &nuseless, nchgcoefs, &numcancel, &nfillin) );
943  }
944 
945  SCIPfreeBufferArrayNull(scip, &rowsparsity);
946  SCIPfreeBufferArrayNull(scip, &rowidxsorted);
947 
948  SCIPhashtableFree(&pairtable);
949  SCIPfreeBufferArrayNull(scip, &varpairs);
950 
951  SCIPfreeBufferArray(scip, &perm);
952  SCIPfreeBufferArray(scip, &locks);
953 
954  /* update result */
955  presoldata->ncancels += numcancel;
956  presoldata->nfillin += nfillin;
957 
958  if( numcancel > 0 )
959  {
961  " (%.1fs) sparsify %s: %d/%d (%.1f%%) nonzeros canceled"
962  " - in total %d canceled nonzeros, %d changed coefficients, %d added nonzeros\n",
963  SCIPgetSolvingTime(scip), (nuseless > maxuseless ? "aborted" : "finished"), numcancel,
964  SCIPmatrixGetNNonzs(matrix), 100.0*(SCIP_Real)numcancel/(SCIP_Real)SCIPmatrixGetNNonzs(matrix),
965  presoldata->ncancels, SCIPpresolGetNChgCoefs(presol) + *nchgcoefs - oldnchgcoefs, presoldata->nfillin);
966  *result = SCIP_SUCCESS;
967  }
968 
969  updateFailureStatistic(presoldata, numcancel > 0);
970 
971  SCIPdebugMsg(scip, "sparsify failure statistic: nfailures=%d, nwaitingcalls=%d\n", presoldata->nfailures,
972  presoldata->nwaitingcalls);
973  }
974  /* if matrix construction fails once, we do not ever want to be called again */
975  else
976  {
977  updateFailureStatistic(presoldata, FALSE);
978  presoldata->nwaitingcalls = INT_MAX;
979  }
980 
981  SCIPmatrixFree(scip, &matrix);
982 
983  return SCIP_OKAY;
984 }
985 
986 /*
987  * presolver specific interface methods
988  */
989 
990 /** destructor of presolver to free user data (called when SCIP is exiting) */
991 static
992 SCIP_DECL_PRESOLFREE(presolFreeSparsify)
993 { /*lint --e{715}*/
994  SCIP_PRESOLDATA* presoldata;
995 
996  /* free presolver data */
997  presoldata = SCIPpresolGetData(presol);
998  assert(presoldata != NULL);
999 
1000  SCIPfreeBlockMemory(scip, &presoldata);
1001  SCIPpresolSetData(presol, NULL);
1002 
1003  return SCIP_OKAY;
1004 }
1005 
1006 /** initialization method of presolver (called after problem was transformed) */
1007 static
1008 SCIP_DECL_PRESOLINIT(presolInitSparsify)
1009 {
1010  SCIP_PRESOLDATA* presoldata;
1011 
1012  /* set the counters in the init (and not in the initpre) callback such that they persist across restarts */
1013  presoldata = SCIPpresolGetData(presol);
1014  presoldata->ncancels = 0;
1015  presoldata->nfillin = 0;
1016  presoldata->nfailures = 0;
1017  presoldata->nwaitingcalls = 0;
1018 
1019  return SCIP_OKAY;
1020 }
1021 
1022 /** creates the sparsify presolver and includes it in SCIP */
1024  SCIP* scip /**< SCIP data structure */
1025  )
1026 {
1027  SCIP_PRESOLDATA* presoldata;
1028  SCIP_PRESOL* presol;
1029 
1030  /* create sparsify presolver data */
1031  SCIP_CALL( SCIPallocBlockMemory(scip, &presoldata) );
1032 
1033  /* include presolver */
1035  PRESOL_TIMING, presolExecSparsify, presoldata) );
1036 
1037  SCIP_CALL( SCIPsetPresolCopy(scip, presol, presolCopySparsify) );
1038  SCIP_CALL( SCIPsetPresolFree(scip, presol, presolFreeSparsify) );
1039  SCIP_CALL( SCIPsetPresolInit(scip, presol, presolInitSparsify) );
1040 
1042  "presolving/sparsify/enablecopy",
1043  "should sparsify presolver be copied to sub-SCIPs?",
1044  &presoldata->enablecopy, TRUE, DEFAULT_ENABLECOPY, NULL, NULL) );
1045 
1047  "presolving/sparsify/cancellinear",
1048  "should we cancel nonzeros in constraints of the linear constraint handler?",
1049  &presoldata->cancellinear, TRUE, DEFAULT_CANCELLINEAR, NULL, NULL) );
1050 
1052  "presolving/sparsify/preserveintcoefs",
1053  "should we forbid cancellations that destroy integer coefficients?",
1054  &presoldata->preserveintcoefs, TRUE, DEFAULT_PRESERVEINTCOEFS, NULL, NULL) );
1055 
1056  SCIP_CALL( SCIPaddIntParam(scip,
1057  "presolving/sparsify/maxcontfillin",
1058  "maximal fillin for continuous variables (-1: unlimited)",
1059  &presoldata->maxcontfillin, FALSE, DEFAULT_MAX_CONT_FILLIN, -1, INT_MAX, NULL, NULL) );
1060 
1061  SCIP_CALL( SCIPaddIntParam(scip,
1062  "presolving/sparsify/maxbinfillin",
1063  "maximal fillin for binary variables (-1: unlimited)",
1064  &presoldata->maxbinfillin, FALSE, DEFAULT_MAX_BIN_FILLIN, -1, INT_MAX, NULL, NULL) );
1065 
1066  SCIP_CALL( SCIPaddIntParam(scip,
1067  "presolving/sparsify/maxintfillin",
1068  "maximal fillin for integer variables including binaries (-1: unlimited)",
1069  &presoldata->maxintfillin, FALSE, DEFAULT_MAX_INT_FILLIN, -1, INT_MAX, NULL, NULL) );
1070 
1071  SCIP_CALL( SCIPaddIntParam(scip,
1072  "presolving/sparsify/maxnonzeros",
1073  "maximal support of one equality to be used for cancelling (-1: no limit)",
1074  &presoldata->maxnonzeros, TRUE, DEFAULT_MAXNONZEROS, -1, INT_MAX, NULL, NULL) );
1075 
1076  SCIP_CALL( SCIPaddIntParam(scip,
1077  "presolving/sparsify/maxconsiderednonzeros",
1078  "maximal number of considered non-zeros within one row (-1: no limit)",
1079  &presoldata->maxconsiderednonzeros, TRUE, DEFAULT_MAXCONSIDEREDNONZEROS, -1, INT_MAX, NULL, NULL) );
1080 
1082  "presolving/sparsify/rowsort",
1083  "order in which to process inequalities ('n'o sorting, 'i'ncreasing nonzeros, 'd'ecreasing nonzeros)",
1084  &presoldata->rowsort, TRUE, DEFAULT_ROWSORT, "nid", NULL, NULL) );
1085 
1087  "presolving/sparsify/maxretrievefac",
1088  "limit on the number of useless vs. useful hashtable retrieves as a multiple of the number of constraints",
1089  &presoldata->maxretrievefac, TRUE, DEFAULT_MAXRETRIEVEFAC, 0.0, SCIP_REAL_MAX, NULL, NULL) );
1090 
1092  "presolving/sparsify/waitingfac",
1093  "number of calls to wait until next execution as a multiple of the number of useless calls",
1094  &presoldata->waitingfac, TRUE, DEFAULT_WAITINGFAC, 0.0, SCIP_REAL_MAX, NULL, NULL) );
1095 
1096  return SCIP_OKAY;
1097 }
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
void SCIPmatrixPrintRow(SCIP *scip, SCIP_MATRIX *matrix, int row)
Definition: matrix.c:927
struct SCIP_PresolData SCIP_PRESOLDATA
Definition: type_presol.h:37
SCIP_VAR * SCIPmatrixGetVar(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1407
#define NULL
Definition: def.h:253
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:686
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2364
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:876
int SCIPmatrixGetNRows(SCIP_MATRIX *matrix)
Definition: matrix.c:1479
public methods for SCIP parameter handling
public methods for memory management
#define DEFAULT_MAXRETRIEVEFAC
SCIP_CONS * SCIPmatrixGetCons(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1607
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition: misc.c:2425
SCIP_Bool SCIPisNLPEnabled(SCIP *scip)
Definition: scip_nlp.c:171
public methods for timing
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4593
void SCIPmatrixFree(SCIP *scip, SCIP_MATRIX **matrix)
Definition: matrix.c:864
SCIP_EXPORT SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16918
int SCIPgetNConss(SCIP *scip)
Definition: scip_prob.c:3037
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:359
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:215
#define FALSE
Definition: def.h:73
public methods for presolving plugins
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_Real varcoef2
public methods for problem variables
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:47
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
SCIP_RETCODE SCIPhashtableRemove(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2494
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:119
static SCIP_DECL_HASHKEYEQ(varPairsEqual)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
#define DEFAULT_ENABLECOPY
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
#define SCIPdebugPrintCons(x, y, z)
Definition: pub_message.h:83
#define DEFAULT_WAITINGFAC
SCIP_RETCODE SCIPmatrixCreate(SCIP *scip, SCIP_MATRIX **matrixptr, SCIP_Bool *initialized, SCIP_Bool *complete)
Definition: matrix.c:437
#define SCIPdebugMsg
Definition: scip_message.h:69
#define DEFAULT_PRESERVEINTCOEFS
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
public methods for numerical tolerances
SCIP_RETCODE SCIPhashtableCreate(SCIP_HASHTABLE **hashtable, BMS_BLKMEM *blkmem, int tablesize, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr)
Definition: misc.c:2113
int SCIPmatrixGetRowNNonzs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1455
cancel non-zeros of the constraint matrix
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2838
#define DEFAULT_MAXCONSIDEREDNONZEROS
SCIP_Real SCIPmatrixGetRowLhs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1489
public methods for managing constraints
#define DEFAULT_ROWSORT
SCIP_EXPORT SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:16929
SCIP_PRESOLDATA * SCIPpresolGetData(SCIP_PRESOL *presol)
Definition: presol.c:502
#define COPYSIGN
Definition: def.h:244
#define MAXSCALE
#define DEFAULT_CANCELLINEAR
static INLINE uint32_t SCIPrealHashCode(double x)
Definition: pub_misc.h:509
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:124
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:47
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
int * SCIPmatrixGetRowIdxPtr(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1443
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:87
static SCIP_RETCODE cancelRow(SCIP *scip, SCIP_MATRIX *matrix, SCIP_HASHTABLE *pairtable, int rowidx, int maxcontfillin, int maxintfillin, int maxbinfillin, int maxconsiderednonzeros, SCIP_Bool preserveintcoefs, SCIP_Longint *nuseless, int *nchgcoefs, int *ncanceled, int *nfillin)
#define DEFAULT_MAX_BIN_FILLIN
#define REALABS(x)
Definition: def.h:188
const char * SCIPmatrixGetRowName(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1467
static SCIP_DECL_PRESOLCOPY(presolCopySparsify)
#define SCIP_CALL(x)
Definition: def.h:365
#define SCIPhashTwo(a, b)
Definition: pub_misc.h:493
SCIP_Real * SCIPmatrixGetRowValPtr(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1431
Definition: grphload.c:88
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLCOPY((*presolcopy)))
Definition: scip_presol.c:129
void SCIPpresolSetData(SCIP_PRESOL *presol, SCIP_PRESOLDATA *presoldata)
Definition: presol.c:512
public methods for constraint handler plugins and constraints
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:129
public data structures and miscellaneous methods
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
Definition: misc.c:2163
#define SCIP_Bool
Definition: def.h:70
#define DEFAULT_MAX_CONT_FILLIN
SCIP_EXPORT void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
#define PRESOL_PRIORITY
#define PRESOL_NAME
SCIP_RETCODE SCIPsetPresolInit(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLINIT((*presolinit)))
Definition: scip_presol.c:161
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
Definition: presol.c:589
static SCIP_DECL_HASHKEYVAL(varPairHashval)
#define MIN(x, y)
Definition: def.h:223
SCIP_EXPORT void SCIPsortIntReal(int *intarray, SCIP_Real *realarray, int len)
static SCIP_DECL_PRESOLINIT(presolInitSparsify)
Constraint handler for linear constraints in their most general form, .
int SCIPgetNActivePricers(SCIP *scip)
Definition: scip_pricer.c:338
public methods for matrix
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:129
void SCIPswapPointers(void **pointer1, void **pointer2)
Definition: misc.c:9891
public methods for variable pricer plugins
SCIP_RETCODE SCIPsetPresolFree(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLFREE((*presolfree)))
Definition: scip_presol.c:145
#define SCIP_REAL_MAX
Definition: def.h:165
public methods for nonlinear relaxations
SCIP_Real * r
Definition: circlepacking.c:50
methods for sorting joint arrays of various types
#define PRESOL_MAXROUNDS
SCIP_VAR ** b
Definition: circlepacking.c:56
public methods for presolvers
general public methods
#define MAX(x, y)
Definition: def.h:222
SCIP_Real SCIPmatrixGetRowRhs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1501
public methods for the probing mode
static void updateFailureStatistic(SCIP_PRESOLDATA *presoldata, SCIP_Bool success)
public methods for message output
int SCIPpresolGetNChgCoefs(SCIP_PRESOL *presol)
Definition: presol.c:787
SCIP_VAR * a
Definition: circlepacking.c:57
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:73
#define SCIP_Real
Definition: def.h:164
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:94
SCIP_Real varcoef1
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8096
public methods for message handling
#define DEFAULT_MAX_INT_FILLIN
int SCIPmatrixGetColNDownlocks(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1395
#define PRESOL_TIMING
#define SCIP_Longint
Definition: def.h:149
#define DEFAULT_MAXNONZEROS
static SCIP_DECL_PRESOLFREE(presolFreeSparsify)
int SCIPmatrixGetNNonzs(SCIP_MATRIX *matrix)
Definition: matrix.c:1525
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2765
int SCIPmatrixGetColNUplocks(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1383
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1109
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:355
SCIP_RETCODE SCIPincludePresolSparsify(SCIP *scip)
#define SCIPcombineTwoInt(a, b)
Definition: pub_misc.h:499
public methods for global and local (sub)problems
SCIP_RETCODE SCIPaddCharParam(SCIP *scip, const char *name, const char *desc, char *valueptr, SCIP_Bool isadvanced, char defaultvalue, const char *allowedvalues, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:157
int SCIPmatrixGetNColumns(SCIP_MATRIX *matrix)
Definition: matrix.c:1351
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
static SCIP_DECL_PRESOLEXEC(presolExecSparsify)
memory allocation routines
#define PRESOL_DESC