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