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-2024 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file presol_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
39#include "scip/cons_linear.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 */
89struct 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{
116};
117
118typedef struct RowVarPair ROWVARPAIR;
119
120/*
121 * Local methods
122 */
123
124/** returns TRUE iff both keys are equal */
125static
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 */
151static
152SCIP_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 */
163static
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");
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 */
653static
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) */
679static
680SCIP_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 */
700static
701SCIP_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
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) */
1021static
1022SCIP_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) */
1037static
1038SCIP_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
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
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
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
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
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_VAR * a
Definition: circlepacking.c:66
SCIP_VAR ** b
Definition: circlepacking.c:65
SCIP_Real * r
Definition: circlepacking.c:59
Constraint handler for linear constraints in their most general form, .
#define NULL
Definition: def.h:267
#define COPYSIGN
Definition: def.h:258
#define SCIP_Longint
Definition: def.h:158
#define SCIP_REAL_MAX
Definition: def.h:174
#define SCIP_Bool
Definition: def.h:91
#define MIN(x, y)
Definition: def.h:243
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define MAX(x, y)
Definition: def.h:239
#define REALABS(x)
Definition: def.h:197
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:724
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:380
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2770
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2843
int SCIPgetNConss(SCIP *scip)
Definition: scip_prob.c:3042
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
Definition: misc.c:2346
int SCIPhashtableGetNEntries(SCIP_HASHTABLE *hashtable)
Definition: misc.c:2777
#define SCIPhashThree(a, b, c)
Definition: pub_misc.h:553
SCIP_RETCODE SCIPhashtableCreate(SCIP_HASHTABLE **hashtable, BMS_BLKMEM *blkmem, int tablesize, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr)
Definition: misc.c:2296
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition: misc.c:2608
static INLINE uint32_t SCIPrealHashCode(double x)
Definition: pub_misc.h:576
SCIP_RETCODE SCIPhashtableRemove(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2677
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2547
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:225
#define SCIPdebugMsg
Definition: scip_message.h:78
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_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
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
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 SCIPswapPointers(void **pointer1, void **pointer2)
Definition: misc.c:10396
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4636
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:941
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8234
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1174
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:139
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:128
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:132
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:137
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
SCIP_Bool SCIPisNLPEnabled(SCIP *scip)
Definition: scip_nlp.c:74
int SCIPpresolGetNChgCoefs(SCIP_PRESOL *presol)
Definition: presol.c:797
void SCIPpresolSetData(SCIP_PRESOL *presol, SCIP_PRESOLDATA *presoldata)
Definition: presol.c:522
SCIP_PRESOLDATA * SCIPpresolGetData(SCIP_PRESOL *presol)
Definition: presol.c:512
SCIP_RETCODE SCIPsetPresolInit(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLINIT((*presolinit)))
Definition: scip_presol.c:172
SCIP_RETCODE SCIPsetPresolFree(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLFREE((*presolfree)))
Definition: scip_presol.c:156
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLCOPY((*presolcopy)))
Definition: scip_presol.c:140
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
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
Definition: presol.c:599
int SCIPgetNActivePricers(SCIP *scip)
Definition: scip_pricer.c:348
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:97
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:378
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17599
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:17610
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
void SCIPsortIntReal(int *intarray, SCIP_Real *realarray, int len)
int SCIPmatrixGetNNonzs(SCIP_MATRIX *matrix)
Definition: matrix.c:1778
int SCIPmatrixGetRowNNonzs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1708
const char * SCIPmatrixGetRowName(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1720
int SCIPmatrixGetColNDownlocks(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1648
int SCIPmatrixGetColNUplocks(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1636
SCIP_Real SCIPmatrixGetRowLhs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1742
SCIP_Real * SCIPmatrixGetRowValPtr(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1684
SCIP_Real SCIPmatrixGetRowRhs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1754
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
int SCIPmatrixGetNColumns(SCIP_MATRIX *matrix)
Definition: matrix.c:1604
SCIP_CONS * SCIPmatrixGetCons(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1860
void SCIPmatrixFree(SCIP *scip, SCIP_MATRIX **matrix)
Definition: matrix.c:1072
SCIP_VAR * SCIPmatrixGetVar(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1660
int * SCIPmatrixGetRowIdxPtr(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1696
void SCIPmatrixPrintRow(SCIP *scip, SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1135
int SCIPmatrixGetNRows(SCIP_MATRIX *matrix)
Definition: matrix.c:1732
memory allocation routines
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:57
#define DEFAULT_ROWSORT
static SCIP_DECL_PRESOLEXEC(presolExecSparsify)
#define DEFAULT_MAXCONSIDEREDNONZEROS
static SCIP_DECL_PRESOLFREE(presolFreeSparsify)
#define DEFAULT_MAXNONZEROS
#define PRESOL_NAME
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)
static SCIP_DECL_HASHKEYEQ(varPairsEqual)
#define MAXSCALE
#define DEFAULT_MAX_INT_FILLIN
static void updateFailureStatistic(SCIP_PRESOLDATA *presoldata, SCIP_Bool success)
SCIP_RETCODE SCIPincludePresolSparsify(SCIP *scip)
#define PRESOL_PRIORITY
#define DEFAULT_CANCELLINEAR
static SCIP_DECL_PRESOLINIT(presolInitSparsify)
#define DEFAULT_ENABLECOPY
static SCIP_DECL_HASHKEYVAL(varPairHashval)
#define DEFAULT_MAX_CONT_FILLIN
#define DEFAULT_WAITINGFAC
#define DEFAULT_MAXRETRIEVEFAC
static SCIP_DECL_PRESOLCOPY(presolCopySparsify)
#define PRESOL_MAXROUNDS
#define PRESOL_TIMING
#define DEFAULT_MAX_BIN_FILLIN
#define DEFAULT_PRESERVEINTCOEFS
#define PRESOL_DESC
cancel non-zeros of the constraint matrix
public methods for managing constraints
public methods for matrix
public methods for message output
#define SCIPdebugPrintCons(x, y, z)
Definition: pub_message.h:102
public data structures and miscellaneous methods
methods for sorting joint arrays of various types
public methods for presolvers
public methods for problem variables
public methods for constraint handler plugins and constraints
general public methods
public methods for memory management
public methods for message handling
public methods for nonlinear relaxation
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for presolving plugins
public methods for variable pricer plugins
public methods for global and local (sub)problems
public methods for the probing mode
public methods for timing
SCIP_Real varcoef2
SCIP_Real varcoef1
@ SCIP_VERBLEVEL_HIGH
Definition: type_message.h:56
struct SCIP_PresolData SCIP_PRESOLDATA
Definition: type_presol.h:51
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_CUTOFF
Definition: type_result.h:48
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_SUCCESS
Definition: type_result.h:58
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_STAGE_PRESOLVING
Definition: type_set.h:49