SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
presol_milp.cpp
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_milp.cpp
26 * @brief MILP presolver
27 * @author Leona Gottwald
28 *
29 * Calls the presolve library and communicates (multi-)aggregations, fixings, and bound
30 * changes to SCIP by utilizing the postsolve information. Constraint changes can currently
31 * only be communicated by deleting all constraints and adding new ones.
32 *
33 * @todo add infrastructure to SCIP for handling parallel columns
34 * @todo better communication of constraint changes by adding more information to the postsolve structure
35 * @todo allow to pass additional external locks to the presolve library that are considered when doing reductions
36 *
37 */
38
39/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
40
41#include "scip/presol_milp.h"
42
43#ifndef SCIP_WITH_PAPILO
44
45/** creates the MILP presolver and includes it in SCIP */
47 SCIP* scip /**< SCIP data structure */
48 )
49{
50 assert(scip != NULL);
51 return SCIP_OKAY;
52}
53
54#else
55
56/* disable some warnings that come up in header files of PAPILOs dependencies */
57#ifdef __GNUC__
58#pragma GCC diagnostic ignored "-Wshadow"
59#pragma GCC diagnostic ignored "-Wctor-dtor-privacy"
60#pragma GCC diagnostic ignored "-Wredundant-decls"
61
62/* disable false warning, !3076, https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106199 */
63#if __GNUC__ == 12 && __GNUC__MINOR__ <= 2
64#pragma GCC diagnostic ignored "-Wstringop-overflow"
65#endif
66#endif
67
68#include <assert.h>
69#include "scip/cons_linear.h"
70#include "scip/pub_matrix.h"
71#include "scip/pub_presol.h"
72#include "scip/pub_var.h"
73#include "scip/pub_cons.h"
74#include "scip/pub_message.h"
75#include "scip/scip_general.h"
76#include "scip/scip_presol.h"
77#include "scip/scip_var.h"
78#include "scip/scip_mem.h"
79#include "scip/scip_prob.h"
80#include "scip/scip_param.h"
81#include "scip/scip_cons.h"
82#include "scip/scip_numerics.h"
83#include "scip/scip_timing.h"
84#include "scip/scip_message.h"
86#include "papilo/core/Presolve.hpp"
87#include "papilo/core/ProblemBuilder.hpp"
88#include "papilo/Config.hpp"
89
90#define PRESOL_NAME "milp"
91#define PRESOL_DESC "MILP specific presolving methods"
92#define PRESOL_PRIORITY 9999999 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers); combined with propagators */
93#define PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
94#define PRESOL_TIMING SCIP_PRESOLTIMING_MEDIUM /* timing of the presolver (fast, medium, or exhaustive) */
95
96/* default parameter values */
97#define DEFAULT_THREADS 1 /**< maximum number of threads presolving may use (0: automatic) */
98#define DEFAULT_MAXFILLINPERSUBST 3 /**< maximal possible fillin for substitutions to be considered */
99#define DEFAULT_MAXSHIFTPERROW 10 /**< maximal amount of nonzeros allowed to be shifted to make space for substitutions */
100#define DEFAULT_DETECTLINDEP 0 /**< should linear dependent equations and free columns be removed? (0: never, 1: for LPs, 2: always) */
101#define DEFAULT_MAXBADGESIZE_SEQ 15000 /**< the max badge size in Probing if PaPILO is executed in sequential mode*/
102#define DEFAULT_MAXBADGESIZE_PAR -1 /**< the max badge size in Probing if PaPILO is executed in parallel mode*/
103#define DEFAULT_RANDOMSEED 0 /**< the random seed used for randomization of tie breaking */
104#define DEFAULT_MODIFYCONSFAC 0.8 /**< modify SCIP constraints when the number of nonzeros or rows is at most this
105 * factor times the number of nonzeros or rows before presolving */
106#define DEFAULT_MARKOWITZTOLERANCE 0.01 /**< the markowitz tolerance used for substitutions */
107#define DEFAULT_VERBOSITY 0
108#define DEFAULT_HUGEBOUND 1e8 /**< absolute bound value that is considered too huge for activitity based calculations */
109#define DEFAULT_ENABLEPARALLELROWS TRUE /**< should the parallel rows presolver be enabled within the presolve library? */
110#define DEFAULT_ENABLEDOMCOL TRUE /**< should the dominated column presolver be enabled within the presolve library? */
111#define DEFAULT_ENABLEDUALINFER TRUE /**< should the dualinfer presolver be enabled within the presolve library? */
112#define DEFAULT_ENABLEMULTIAGGR TRUE /**< should the multi-aggregation presolver be enabled within the presolve library? */
113#define DEFAULT_ENABLEPROBING TRUE /**< should the probing presolver be enabled within the presolve library? */
114#define DEFAULT_ENABLESPARSIFY FALSE /**< should the sparsify presolver be enabled within the presolve library? */
115#define DEFAULT_FILENAME_PROBLEM "-" /**< default filename to store the instance before presolving */
116
117/*
118 * Data structures
119 */
120
121/** presolver data */
122struct SCIP_PresolData
123{
124 int lastncols; /**< the number of columns from the last call */
125 int lastnrows; /**< the number of rows from the last call */
126 int threads; /**< maximum number of threads presolving may use (0: automatic) */
127 int maxfillinpersubstitution; /**< maximal possible fillin for substitutions to be considered */
128 int maxbadgesizeseq; /**< the max badge size in Probing if PaPILO is called in sequential mode*/
129 int maxbadgesizepar; /**< the max badge size in Probing if PaPILO is called in parallel mode */
130 int maxshiftperrow; /**< maximal amount of nonzeros allowed to be shifted to make space for substitutions */
131 int detectlineardependency; /**< should linear dependent equations and free columns be removed? (0: never, 1: for LPs, 2: always) */
132 int randomseed; /**< the random seed used for randomization of tie breaking */
133 int verbosity;
134
135 SCIP_Bool enablesparsify; /**< should the sparsify presolver be enabled within the presolve library? */
136 SCIP_Bool enabledomcol; /**< should the dominated column presolver be enabled within the presolve library? */
137 SCIP_Bool enableprobing; /**< should the probing presolver be enabled within the presolve library? */
138 SCIP_Bool enabledualinfer; /**< should the dualinfer presolver be enabled within the presolve library? */
139 SCIP_Bool enablemultiaggr; /**< should the multi-aggregation presolver be enabled within the presolve library? */
140 SCIP_Bool enableparallelrows; /**< should the parallel rows presolver be enabled within the presolve library? */
141 SCIP_Real modifyconsfac; /**< modify SCIP constraints when the number of nonzeros or rows is at most this
142 * factor times the number of nonzeros or rows before presolving */
143 SCIP_Real markowitztolerance; /**< the markowitz tolerance used for substitutions */
144 SCIP_Real hugebound; /**< absolute bound value that is considered too huge for activitity based calculations */
145
146 char* filename = NULL; /**< filename to store the instance before presolving */
147};
148
149using namespace papilo;
150
151/*
152 * Local methods
153 */
154
155/** builds the presolvelib problem datastructure from the matrix */
156static
157Problem<SCIP_Real> buildProblem(
158 SCIP* scip, /**< SCIP data structure */
159 SCIP_MATRIX* matrix /**< initialized SCIP_MATRIX data structure */
160 )
161{
163
164 /* build problem from matrix */
165 int nnz = SCIPmatrixGetNNonzs(matrix);
166 int ncols = SCIPmatrixGetNColumns(matrix);
167 int nrows = SCIPmatrixGetNRows(matrix);
168 builder.reserve(nnz, nrows, ncols);
169
170 /* set up columns */
171 builder.setNumCols(ncols);
172 for(int i = 0; i != ncols; ++i)
173 {
174 SCIP_VAR* var = SCIPmatrixGetVar(matrix, i);
175 SCIP_Real lb = SCIPvarGetLbGlobal(var);
176 SCIP_Real ub = SCIPvarGetUbGlobal(var);
177 builder.setColLb(i, lb);
178 builder.setColUb(i, ub);
179 builder.setColLbInf(i, SCIPisInfinity(scip, -lb));
180 builder.setColUbInf(i, SCIPisInfinity(scip, ub));
181#if PAPILO_VERSION_MAJOR > 2 || (PAPILO_VERSION_MAJOR == 2 && PAPILO_VERSION_MINOR >= 1)
183 builder.setColImplInt(i, TRUE);
184 else
185 builder.setColIntegral(i, SCIPvarIsIntegral(var));
186#else
187 builder.setColIntegral(i, SCIPvarIsIntegral(var));
188#endif
189 builder.setObj(i, SCIPvarGetObj(var));
190 }
191
192 /* set up rows */
193 builder.setNumRows(nrows);
194 for(int i = 0; i != nrows; ++i)
195 {
196 int* rowcols = SCIPmatrixGetRowIdxPtr(matrix, i);
197 SCIP_Real* rowvals = SCIPmatrixGetRowValPtr(matrix, i);
198 int rowlen = SCIPmatrixGetRowNNonzs(matrix, i);
199 builder.addRowEntries(i, rowlen, rowcols, rowvals);
200
201 SCIP_Real lhs = SCIPmatrixGetRowLhs(matrix, i);
202 SCIP_Real rhs = SCIPmatrixGetRowRhs(matrix, i);
203 builder.setRowLhs(i, lhs);
204 builder.setRowRhs(i, rhs);
205 builder.setRowLhsInf(i, SCIPisInfinity(scip, -lhs));
206 builder.setRowRhsInf(i, SCIPisInfinity(scip, rhs));
207 }
208
209 /* init objective offset - the value itself is irrelevant */
210 builder.setObjOffset(0);
211
212 return builder.build();
213}
214
215/*
216 * Callback methods of presolver
217 */
218
219/** copy method for constraint handler plugins (called when SCIP copies plugins) */
220static
222{ /*lint --e{715}*/
224
225 return SCIP_OKAY;
226}
227
228/** destructor of presolver to free user data (called when SCIP is exiting) */
229static
231{ /*lint --e{715}*/
233 assert(data != NULL);
234
237 return SCIP_OKAY;
238}
239
240/** initialization method of presolver (called after problem was transformed) */
241static
243{ /*lint --e{715}*/
245 assert(data != NULL);
246
247 data->lastncols = -1;
248 data->lastnrows = -1;
249
250 return SCIP_OKAY;
251}
252
253/** execution method of presolver */
254static
256{ /*lint --e{715}*/
257 SCIP_MATRIX* matrix;
258 SCIP_PRESOLDATA* data;
259 SCIP_Bool initialized;
260 SCIP_Bool complete;
261 SCIP_Bool infeasible;
262 SCIP_Real timelimit;
263
265
267
268 int nvars = SCIPgetNVars(scip);
269 int nconss = SCIPgetNConss(scip);
270
271 /* run only if the problem size reduced by some amount since the last call or if it is the first call */
272 if( data->lastncols != -1 && data->lastnrows != -1 &&
273 nvars > data->lastncols * 0.85 &&
274 nconss > data->lastnrows * 0.85 )
275 return SCIP_OKAY;
276
277 SCIP_CALL( SCIPmatrixCreate(scip, &matrix, TRUE, &initialized, &complete, &infeasible,
278 naddconss, ndelconss, nchgcoefs, nchgbds, nfixedvars) );
279
280 /* if infeasibility was detected during matrix creation, return here */
281 if( infeasible )
282 {
283 if( initialized )
284 SCIPmatrixFree(scip, &matrix);
285
287 return SCIP_OKAY;
288 }
289
290 /* we only work on pure MIPs, also disable to try building the matrix again if it failed once */
291 if( !initialized || !complete )
292 {
293 data->lastncols = 0;
294 data->lastnrows = 0;
295
296 if( initialized )
297 SCIPmatrixFree(scip, &matrix);
298
299 return SCIP_OKAY;
300 }
301
302 /* only allow communication of constraint modifications by deleting all constraints when they have not been upgraded yet */
306
307 Problem<SCIP_Real> problem = buildProblem(scip, matrix);
309
310 /* store current numbers of aggregations, fixings, and changed bounds for statistics */
311 int oldnaggrvars = *naggrvars;
312 int oldnfixedvars = *nfixedvars;
313 int oldnchgbds = *nchgbds;
314
315 /* important so that SCIP does not throw an error, e.g. when an integer variable is substituted
316 * into a knapsack constraint */
317 presolve.getPresolveOptions().substitutebinarieswithints = false;
318
319 /* currently these changes cannot be communicated to SCIP correctly since a constraint needs
320 * to be modified in the cases where slackvariables are removed from constraints but for the
321 * presolve library those look like normal substitution on the postsolve stack */
322 presolve.getPresolveOptions().removeslackvars = false;
323
324 /* communicate the SCIP parameters to the presolve library */
325 presolve.getPresolveOptions().maxfillinpersubstitution = data->maxfillinpersubstitution;
326 presolve.getPresolveOptions().markowitz_tolerance = data->markowitztolerance;
327 presolve.getPresolveOptions().maxshiftperrow = data->maxshiftperrow;
328 presolve.getPresolveOptions().hugeval = data->hugebound;
329
330 /* removal of linear dependent equations has only an effect when constraint modifications are communicated */
331 presolve.getPresolveOptions().detectlindep = allowconsmodification ? data->detectlineardependency : 0;
332
333 /* communicate the random seed */
334 presolve.getPresolveOptions().randomseed = SCIPinitializeRandomSeed(scip, (unsigned int)data->randomseed);
335
336#ifdef PAPILO_TBB
337 /* set number of threads to be used for presolve */
338 presolve.getPresolveOptions().threads = data->threads;
339#else
340 if (data->threads != DEFAULT_THREADS)
342 "PaPILO can utilize only multiple threads if it is build with TBB.\n");
343 presolve.getPresolveOptions().threads = 1;
344#endif
345
346
347 /* disable dual reductions that are not permitted */
348 if( !complete )
349 presolve.getPresolveOptions().dualreds = 0;
350 else if( SCIPallowStrongDualReds(scip) )
351 presolve.getPresolveOptions().dualreds = 2;
352 else if( SCIPallowWeakDualReds(scip) )
353 presolve.getPresolveOptions().dualreds = 1;
354 else
355 presolve.getPresolveOptions().dualreds = 0;
356
357 /* set up the presolvers that shall participate */
358 using uptr = std::unique_ptr<PresolveMethod<SCIP_Real>>;
359
360 /* fast presolvers*/
361 presolve.addPresolveMethod( uptr( new SingletonCols<SCIP_Real>() ) );
362 presolve.addPresolveMethod( uptr( new CoefficientStrengthening<SCIP_Real>() ) );
363 presolve.addPresolveMethod( uptr( new ConstraintPropagation<SCIP_Real>() ) );
364
365 /* medium presolver */
366 presolve.addPresolveMethod( uptr( new SimpleProbing<SCIP_Real>() ) );
367 if( data->enableparallelrows )
368 presolve.addPresolveMethod( uptr( new ParallelRowDetection<SCIP_Real>() ) );
369 /* todo: parallel cols cannot be handled by SCIP currently
370 * addPresolveMethod( uptr( new ParallelColDetection<SCIP_Real>() ) ); */
371 presolve.addPresolveMethod( uptr( new SingletonStuffing<SCIP_Real>() ) );
372#if PAPILO_VERSION_MAJOR > 2 || (PAPILO_VERSION_MAJOR == 2 && PAPILO_VERSION_MINOR >= 1)
374 dualfix->set_fix_to_infinity_allowed(false);
375 presolve.addPresolveMethod( uptr( dualfix ) );
376#else
377 presolve.addPresolveMethod( uptr( new DualFix<SCIP_Real>() ) );
378#endif
379 presolve.addPresolveMethod( uptr( new FixContinuous<SCIP_Real>() ) );
380 presolve.addPresolveMethod( uptr( new SimplifyInequalities<SCIP_Real>() ) );
381 presolve.addPresolveMethod( uptr( new SimpleSubstitution<SCIP_Real>() ) );
382
383 /* exhaustive presolvers*/
384 presolve.addPresolveMethod( uptr( new ImplIntDetection<SCIP_Real>() ) );
385 if( data->enabledualinfer )
386 presolve.addPresolveMethod( uptr( new DualInfer<SCIP_Real>() ) );
387 if( data->enableprobing )
388 {
389#if PAPILO_VERSION_MAJOR > 2 || (PAPILO_VERSION_MAJOR == 2 && PAPILO_VERSION_MINOR >= 1)
390 Probing<SCIP_Real> *probing = new Probing<SCIP_Real>();
391 if( presolve.getPresolveOptions().runs_sequential() )
392 {
393 probing->set_max_badge_size( data->maxbadgesizeseq );
394 }
395 else
396 {
397 probing->set_max_badge_size( data->maxbadgesizepar );
398 }
399 presolve.addPresolveMethod( uptr( probing ) );
400
401#else
402 presolve.addPresolveMethod( uptr( new Probing<SCIP_Real>() ) );
403 if( data->maxbadgesizeseq != DEFAULT_MAXBADGESIZE_SEQ )
405 " The parameter 'presolving/milp/maxbadgesizeseq' can only be used with PaPILO 2.1.0 or later versions.\n");
406
407 if( data->maxbadgesizepar != DEFAULT_MAXBADGESIZE_PAR )
409 " The parameter 'presolving/milp/maxbadgesizepar' can only be used with PaPILO 2.1.0 or later versions.\n");
410
411#endif
412 }
413 if( data->enabledomcol )
414 presolve.addPresolveMethod( uptr( new DominatedCols<SCIP_Real>() ) );
415 if( data->enablemultiaggr )
416 presolve.addPresolveMethod( uptr( new Substitution<SCIP_Real>() ) );
417 if( data->enablesparsify )
418 presolve.addPresolveMethod( uptr( new Sparsify<SCIP_Real>() ) );
419
420 /* set tolerances */
421 presolve.getPresolveOptions().feastol = SCIPfeastol(scip);
422 presolve.getPresolveOptions().epsilon = SCIPepsilon(scip);
423
424 /* adjust output settings of presolve library */
425#ifdef SCIP_PRESOLLIB_ENABLE_OUTPUT
426 problem.setName(SCIPgetProbName(scip));
427#else
428 presolve.setVerbosityLevel((VerbosityLevel) data->verbosity);
429#endif
430
431 /* communicate the time limit */
432 SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
433 if( !SCIPisInfinity(scip, timelimit) )
434 presolve.getPresolveOptions().tlim = timelimit - SCIPgetSolvingTime(scip);
435
437 {
439 " writing transformed problem to %s (only enforced constraints)\n", data->filename);
440 SCIP_CALL(SCIPwriteTransProblem(scip, data->filename, NULL, FALSE));
441 }
442
443 /* call the presolving */
445 " (%.1fs) running MILP presolver\n", SCIPgetSolvingTime(scip));
446 int oldnnz = problem.getConstraintMatrix().getNnz();
447
448 /*call presolving without storing information for dual postsolve*/
449#if (PAPILO_VERSION_MAJOR >= 2)
450 PresolveResult<SCIP_Real> res = presolve.apply(problem, false);
451#else
452 PresolveResult<SCIP_Real> res = presolve.apply(problem);
453#endif
454 data->lastncols = problem.getNCols();
455 data->lastnrows = problem.getNRows();
456
457 /* evaluate the result */
458 switch(res.status)
459 {
460 case PresolveStatus::kInfeasible:
463 " (%.1fs) MILP presolver detected infeasibility\n",
465 SCIPmatrixFree(scip, &matrix);
466 return SCIP_OKAY;
467 case PresolveStatus::kUnbndOrInfeas:
468 case PresolveStatus::kUnbounded:
471 " (%.1fs) MILP presolver detected unboundedness\n",
473 SCIPmatrixFree(scip, &matrix);
474 return SCIP_OKAY;
475 case PresolveStatus::kUnchanged:
477 data->lastncols = nvars;
478 data->lastnrows = nconss;
480 " (%.1fs) MILP presolver found nothing\n",
482 SCIPmatrixFree(scip, &matrix);
483 return SCIP_OKAY;
484 case PresolveStatus::kReduced:
485 data->lastncols = problem.getNCols();
486 data->lastnrows = problem.getNRows();
488 }
489
490 /* result indicated success, now populate the changes into the SCIP structures */
491 std::vector<SCIP_VAR*> tmpvars;
492 std::vector<SCIP_Real> tmpvals;
493
494 /* if the number of nonzeros decreased by a sufficient factor, rather create all constraints from scratch */
495 int newnnz = problem.getConstraintMatrix().getNnz();
496 bool constraintsReplaced = false;
497 if( newnnz == 0 || (allowconsmodification &&
498 (problem.getNRows() <= data->modifyconsfac * data->lastnrows ||
500 {
501 int oldnrows = SCIPmatrixGetNRows(matrix);
502 int newnrows = problem.getNRows();
503
504 constraintsReplaced = true;
505
506 /* capture constraints that are still present in the problem after presolve */
507 for( int i = 0; i < newnrows; ++i )
508 {
509 SCIP_CONS* c = SCIPmatrixGetCons(matrix, res.postsolve.origrow_mapping[i]);
511 }
512
513 /* delete all constraints */
514 *ndelconss += oldnrows;
515 *naddconss += newnrows;
516
517 for( int i = 0; i < oldnrows; ++i )
518 {
520 }
521
522 /* now loop over rows of presolved problem and create them as new linear constraints,
523 * then release the old constraint after its name was passed to the new constraint */
524 const Vec<RowFlags>& rflags = problem.getRowFlags();
525 const auto& consmatrix = problem.getConstraintMatrix();
526 for( int i = 0; i < newnrows; ++i )
527 {
528 auto rowvec = consmatrix.getRowCoefficients(i);
529 const int* rowcols = rowvec.getIndices();
530 /* SCIPcreateConsBasicLinear() requires a non const pointer */
531 SCIP_Real* rowvals = const_cast<SCIP_Real*>(rowvec.getValues());
532 int rowlen = rowvec.getLength();
533
534 /* retrieve SCIP compatible left and right hand sides */
535 SCIP_Real lhs = rflags[i].test(RowFlag::kLhsInf) ? - SCIPinfinity(scip) : consmatrix.getLeftHandSides()[i];
536 SCIP_Real rhs = rflags[i].test(RowFlag::kRhsInf) ? SCIPinfinity(scip) : consmatrix.getRightHandSides()[i];
537
538 /* create variable array matching the value array */
539 tmpvars.clear();
540 tmpvars.reserve(rowlen);
541 for( int j = 0; j < rowlen; ++j )
542 tmpvars.push_back(SCIPmatrixGetVar(matrix, res.postsolve.origcol_mapping[rowcols[j]]));
543
544 /* create and add new constraint with name of old constraint */
545 SCIP_CONS* oldcons = SCIPmatrixGetCons(matrix, res.postsolve.origrow_mapping[i]);
546 SCIP_CONS* cons;
547 SCIP_CALL( SCIPcreateConsBasicLinear(scip, &cons, SCIPconsGetName(oldcons), rowlen, tmpvars.data(), rowvals, lhs, rhs) );
548 SCIP_CALL( SCIPaddCons(scip, cons) );
549
550 /* release old and new constraint */
552 SCIP_CALL( SCIPreleaseCons(scip, &cons) );
553 }
554 }
555
556 /* loop over res.postsolve and add all fixed variables and aggregations to scip */
557 for( std::size_t i = 0; i != res.postsolve.types.size(); ++i )
558 {
559 ReductionType type = res.postsolve.types[i];
560 int first = res.postsolve.start[i];
561 int last = res.postsolve.start[i + 1];
562
563 switch( type )
564 {
565 case ReductionType::kFixedCol:
566 {
567 SCIP_Bool infeas;
568 SCIP_Bool fixed;
569 int col = res.postsolve.indices[first];
570
571 SCIP_VAR* var = SCIPmatrixGetVar(matrix, col);
572
573 SCIP_Real value = res.postsolve.values[first];
574
575 SCIP_CALL( SCIPfixVar(scip, var, value, &infeas, &fixed) );
576 *nfixedvars += 1;
577
578 assert(!infeas);
579 /* SCIP has different rules for aggregating variables than PaPILO: therefore the variable PaPILO
580 * tries to fix now may have been aggregated by SCIP before. Additionally, after aggregation SCIP
581 * sometimes performs bound tightening resulting in possible fixings. These cases need to be excluded. */
584 break;
585 }
586/*
587 * Dual-postsolving in PaPILO required introducing a postsolve-type for substitution with additional information.
588 * Further, the different Substitution-postsolving types store the required postsolving data differently (in different order) in the postsolving stack.
589 * Therefore, we need to distinguish how to parse the required data (rowLength, col, side, startRowCoefficients, lastRowCoefficients) from the postsolving stack.
590 * If these values are accessed, the procedure is the same for both.
591 */
592#if (PAPILO_VERSION_MAJOR >= 2)
593 case ReductionType::kSubstitutedColWithDual:
594#endif
595 case ReductionType::kSubstitutedCol:
596 {
597 int col = 0;
598 SCIP_Real side = 0;
599
600 int rowlen = 0;
601 int startRowCoefficients = 0;
602 int lastRowCoefficients = 0;
603
604 if( type == ReductionType::kSubstitutedCol )
605 {
606 rowlen = last - first - 1;
607 col = res.postsolve.indices[first];
608 side = res.postsolve.values[first];
609
610 startRowCoefficients = first + 1;
611 lastRowCoefficients = last;
612 }
613#if (PAPILO_VERSION_MAJOR >= 2)
614 if( type == ReductionType::kSubstitutedColWithDual )
615 {
616 rowlen = (int) res.postsolve.values[first];
617 col = res.postsolve.indices[first + 3 + rowlen];
618 side = res.postsolve.values[first + 1];
619
620 startRowCoefficients = first + 3;
621 lastRowCoefficients = first + 3 + rowlen;
622
623 assert(side == res.postsolve.values[first + 2]);
624 assert(res.postsolve.indices[first + 1] == 0);
625 assert(res.postsolve.indices[first + 2] == 0);
626 }
627 assert( type == ReductionType::kSubstitutedCol || type == ReductionType::kSubstitutedColWithDual );
628#else
629 assert( type == ReductionType::kSubstitutedCol );
630#endif
631 SCIP_Bool infeas;
632 SCIP_Bool aggregated;
633 SCIP_Bool redundant = FALSE;
634 SCIP_Real constant = 0.0;
635 if( rowlen == 2 )
636 {
637 SCIP_Real updatedSide;
638 SCIP_VAR* varx = SCIPmatrixGetVar(matrix, res.postsolve.indices[startRowCoefficients]);
639 SCIP_VAR* vary = SCIPmatrixGetVar(matrix, res.postsolve.indices[startRowCoefficients + 1]);
640 SCIP_Real scalarx = res.postsolve.values[startRowCoefficients];
641 SCIP_Real scalary = res.postsolve.values[startRowCoefficients + 1];
642
643 SCIP_CALL( SCIPgetProbvarSum(scip, &varx, &scalarx, &constant) );
645
646 SCIP_CALL( SCIPgetProbvarSum(scip, &vary, &scalary, &constant) );
648
649 updatedSide = side - constant;
650
652 }
653 else
654 {
655 SCIP_Real colCoef = 0.0;
656 SCIP_Real updatedSide;
657
658 for( int j = startRowCoefficients; j < lastRowCoefficients; ++j )
659 {
660 if( res.postsolve.indices[j] == col )
661 {
662 colCoef = res.postsolve.values[j];
663 break;
664 }
665 }
666
667 tmpvars.clear();
668 tmpvals.clear();
669 tmpvars.reserve(rowlen);
670 tmpvals.reserve(rowlen);
671
672 assert(colCoef != 0.0);
673 SCIP_VAR* aggrvar = SCIPmatrixGetVar(matrix, col);
674
677
678 updatedSide = side - constant;
679
680 for( int j = startRowCoefficients; j < lastRowCoefficients; ++j )
681 {
682 if( res.postsolve.indices[j] == col )
683 continue;
684
685 tmpvars.push_back(SCIPmatrixGetVar(matrix, res.postsolve.indices[j]));
686 tmpvals.push_back(- res.postsolve.values[j] / colCoef);
687 }
688
690 tmpvars.data(), tmpvals.data(), updatedSide / colCoef, &infeas, &aggregated) );
691 }
692
693 if( aggregated )
694 *naggrvars += 1;
695 else if( constraintsReplaced && !redundant )
696 {
697 /* if the constraints where replaced, we need to add the failed substitution as an equality to SCIP */
698 tmpvars.clear();
699 tmpvals.clear();
700 for( int j = startRowCoefficients; j < lastRowCoefficients; ++j )
701 {
702 tmpvars.push_back(SCIPmatrixGetVar(matrix, res.postsolve.indices[j]));
703 tmpvals.push_back(res.postsolve.values[j]);
704 }
705
706 SCIP_CONS* cons;
707 String name = fmt::format("{}_failed_aggregation_equality", SCIPvarGetName(SCIPmatrixGetVar(matrix, col)));
708 SCIP_CALL( SCIPcreateConsBasicLinear(scip, &cons, name.c_str(),
709 tmpvars.size(), tmpvars.data(), tmpvals.data(), side, side ) );
710 SCIP_CALL( SCIPaddCons(scip, cons) );
711 SCIP_CALL( SCIPreleaseCons(scip, &cons) );
712 *naddconss += 1;
713 }
714
715 if( infeas )
716 {
718 break;
719 }
720
721 break;
722 }
723 case ReductionType::kParallelCol:
724 return SCIP_INVALIDRESULT;
725#if (PAPILO_VERSION_MAJOR <= 1 && PAPILO_VERSION_MINOR==0)
726#else
727 case ReductionType::kFixedInfCol: {
728 /* todo: currently SCIP can not handle this kind of reduction (see issue #3391) */
729 assert(false);
731 continue;
732 SCIP_Bool infeas;
733 SCIP_Bool fixed;
734 SCIP_Real value = SCIPinfinity(scip);
735
736 int column = res.postsolve.indices[first];
737 bool is_negative_infinity = res.postsolve.values[first] < 0;
739
741 {
742 value = -SCIPinfinity(scip);
743 }
744
746 *nfixedvars += 1;
747
748 assert(!infeas);
749 assert(fixed);
750 break;
751 }
752#endif
753#if (PAPILO_VERSION_MAJOR >= 2)
754 case ReductionType::kVarBoundChange :
755 case ReductionType::kRedundantRow :
756 case ReductionType::kRowBoundChange :
757 case ReductionType::kReasonForRowBoundChangeForcedByRow :
758 case ReductionType::kRowBoundChangeForcedByRow :
759 case ReductionType::kSaveRow :
760 case ReductionType::kReducedBoundsCost :
761 case ReductionType::kColumnDualValue :
762 case ReductionType::kRowDualValue :
763 case ReductionType::kCoefficientChange :
764 // dual ReductionTypes should be only calculated for dual reductions and should not appear for MIP
765 SCIPerrorMessage("PaPILO: PaPILO should not return dual postsolving reductions in SCIP!!\n");
766 SCIPABORT(); /*lint --e{527}*/
767 break;
768#endif
769 default:
770 SCIPdebugMsg(scip, "PaPILO returned unknown data type: \n" );
771 continue;
772 }
773 }
774
775 /* tighten bounds of variables that are still present after presolving */
776 if( *result != SCIP_CUTOFF )
777 {
778 VariableDomains<SCIP_Real>& varDomains = problem.getVariableDomains();
779 for( int i = 0; i != problem.getNCols(); ++i )
780 {
781 assert( ! varDomains.flags[i].test(ColFlag::kInactive) );
782 SCIP_VAR* var = SCIPmatrixGetVar(matrix, res.postsolve.origcol_mapping[i]);
783 if( !varDomains.flags[i].test(ColFlag::kLbInf) )
784 {
785 SCIP_Bool infeas;
786 SCIP_Bool tightened;
787 SCIP_CALL( SCIPtightenVarLb(scip, var, varDomains.lower_bounds[i], TRUE, &infeas, &tightened) );
788
789 if( tightened )
790 *nchgbds += 1;
791
792 if( infeas )
793 {
795 break;
796 }
797 }
798
799 if( !varDomains.flags[i].test(ColFlag::kUbInf) )
800 {
801 SCIP_Bool infeas;
802 SCIP_Bool tightened;
803 SCIP_CALL( SCIPtightenVarUb(scip, var, varDomains.upper_bounds[i], TRUE, &infeas, &tightened) );
804
805 if( tightened )
806 *nchgbds += 1;
807
808 if( infeas )
809 {
811 break;
812 }
813 }
814 }
815 }
816
817 /* finish with a final verb message and return */
819 " (%.1fs) MILP presolver (%d rounds): %d aggregations, %d fixings, %d bound changes\n",
820 SCIPgetSolvingTime(scip), presolve.getStatistics().nrounds, *naggrvars - oldnaggrvars,
821 *nfixedvars - oldnfixedvars, *nchgbds - oldnchgbds);
822
823 /* free the matrix */
824 assert(initialized);
825 SCIPmatrixFree(scip, &matrix);
826
827 return SCIP_OKAY;
828}
829
830
831/*
832 * presolver specific interface methods
833 */
834
835/** creates the xyz presolver and includes it in SCIP */
837 SCIP* scip /**< SCIP data structure */
838 )
839{
840 SCIP_PRESOLDATA* presoldata;
842
843#if defined(PAPILO_VERSION_TWEAK) && PAPILO_VERSION_TWEAK != 0
845#else
846 String name = fmt::format("PaPILO {}.{}.{}", PAPILO_VERSION_MAJOR, PAPILO_VERSION_MINOR, PAPILO_VERSION_PATCH);
847#endif
848
849#if defined(PAPILO_GITHASH_AVAILABLE) && defined(PAPILO_TBB)
850 String desc = fmt::format("parallel presolve for integer and linear optimization (github.com/scipopt/papilo) (built with TBB) [GitHash: {}]", PAPILO_GITHASH);
851#elif !defined(PAPILO_GITHASH_AVAILABLE) && !defined(PAPILO_TBB)
852 String desc("parallel presolve for integer and linear optimization (github.com/scipopt/papilo)");
853#elif defined(PAPILO_GITHASH_AVAILABLE) && !defined(PAPILO_TBB)
854 String desc = fmt::format("parallel presolve for integer and linear optimization (github.com/scipopt/papilo) [GitHash: {}]", PAPILO_GITHASH);
855#elif !defined(PAPILO_GITHASH_AVAILABLE) && defined(PAPILO_TBB)
856 String desc = fmt::format("parallel presolve for integer and linear optimization (github.com/scipopt/papilo) (built with TBB)");
857#endif
858
859 /* add external code info for the presolve library */
860 SCIP_CALL( SCIPincludeExternalCodeInformation(scip, name.c_str(), desc.c_str()) );
861
862 /* create MILP presolver data */
863 presoldata = NULL;
864 SCIP_CALL( SCIPallocBlockMemory(scip, &presoldata) );
865 BMSclearMemory(presoldata);
866
867 presol = NULL;
868
869 /* include presolver */
872 presoldata) );
873
874 assert(presol != NULL);
875
876 /* set non fundamental callbacks via setter functions */
880
881 /* add MILP presolver parameters */
883 "presolving/" PRESOL_NAME "/threads",
884 "maximum number of threads presolving may use (0: automatic)",
885 &presoldata->threads, FALSE, DEFAULT_THREADS, 0, INT_MAX, NULL, NULL) );
886
888 "presolving/" PRESOL_NAME "/maxfillinpersubstitution",
889 "maximal possible fillin for substitutions to be considered",
890 &presoldata->maxfillinpersubstitution, FALSE, DEFAULT_MAXFILLINPERSUBST, INT_MIN, INT_MAX, NULL, NULL) );
891
893 "presolving/" PRESOL_NAME "/maxshiftperrow",
894 "maximal amount of nonzeros allowed to be shifted to make space for substitutions",
895 &presoldata->maxshiftperrow, TRUE, DEFAULT_MAXSHIFTPERROW, 0, INT_MAX, NULL, NULL) );
896
898 "presolving/" PRESOL_NAME "/randomseed",
899 "the random seed used for randomization of tie breaking",
900 &presoldata->randomseed, FALSE, DEFAULT_RANDOMSEED, INT_MIN, INT_MAX, NULL, NULL) );
901
902 if( DependentRows<double>::Enabled )
903 {
905 "presolving/" PRESOL_NAME "/detectlineardependency",
906 "should linear dependent equations and free columns be removed? (0: never, 1: for LPs, 2: always)",
907 &presoldata->detectlineardependency, TRUE, DEFAULT_DETECTLINDEP, 0, 2, NULL, NULL) );
908 }
909 else
910 presoldata->detectlineardependency = 0;
911
913 "presolving/" PRESOL_NAME "/modifyconsfac",
914 "modify SCIP constraints when the number of nonzeros or rows is at most this factor "
915 "times the number of nonzeros or rows before presolving",
916 &presoldata->modifyconsfac, FALSE, DEFAULT_MODIFYCONSFAC, 0.0, 1.0, NULL, NULL) );
917
919 "presolving/" PRESOL_NAME "/markowitztolerance",
920 "the markowitz tolerance used for substitutions",
921 &presoldata->markowitztolerance, FALSE, DEFAULT_MARKOWITZTOLERANCE, 0.0, 1.0, NULL, NULL) );
922
924 "presolving/" PRESOL_NAME "/hugebound",
925 "absolute bound value that is considered too huge for activitity based calculations",
926 &presoldata->hugebound, FALSE, DEFAULT_HUGEBOUND, 0.0, SCIP_REAL_MAX, NULL, NULL) );
927
928#if PAPILO_VERSION_MAJOR > 2 || (PAPILO_VERSION_MAJOR == 2 && PAPILO_VERSION_MINOR >= 1)
929 SCIP_CALL(SCIPaddIntParam(scip, "presolving/" PRESOL_NAME "/maxbadgesizeseq",
930 "maximal badge size in Probing in PaPILO if PaPILO is executed in sequential mode",
931 &presoldata->maxbadgesizeseq, FALSE, DEFAULT_MAXBADGESIZE_SEQ, -1, INT_MAX, NULL, NULL));
932
933 SCIP_CALL(SCIPaddIntParam(scip, "presolving/" PRESOL_NAME "/maxbadgesizepar",
934 "maximal badge size in Probing in PaPILO if PaPILO is executed in parallel mode",
935 &presoldata->maxbadgesizepar, FALSE, DEFAULT_MAXBADGESIZE_PAR, -1, INT_MAX, NULL, NULL));
936#else
937 presoldata->maxbadgesizeseq = DEFAULT_MAXBADGESIZE_SEQ;
938 presoldata->maxbadgesizepar = DEFAULT_MAXBADGESIZE_PAR;
939#endif
940
942 "presolving/" PRESOL_NAME "/enableparallelrows",
943 "should the parallel rows presolver be enabled within the presolve library?",
944 &presoldata->enableparallelrows, TRUE, DEFAULT_ENABLEPARALLELROWS, NULL, NULL) );
945
947 "presolving/" PRESOL_NAME "/enabledomcol",
948 "should the dominated column presolver be enabled within the presolve library?",
949 &presoldata->enabledomcol, TRUE, DEFAULT_ENABLEDOMCOL, NULL, NULL) );
950
952 "presolving/" PRESOL_NAME "/enabledualinfer",
953 "should the dualinfer presolver be enabled within the presolve library?",
954 &presoldata->enabledualinfer, TRUE, DEFAULT_ENABLEDUALINFER, NULL, NULL) );
955
957 "presolving/" PRESOL_NAME "/enablemultiaggr",
958 "should the multi-aggregation presolver be enabled within the presolve library?",
959 &presoldata->enablemultiaggr, TRUE, DEFAULT_ENABLEMULTIAGGR, NULL, NULL) );
960
962 "presolving/" PRESOL_NAME "/enableprobing",
963 "should the probing presolver be enabled within the presolve library?",
964 &presoldata->enableprobing, TRUE, DEFAULT_ENABLEPROBING, NULL, NULL) );
965
967 "presolving/" PRESOL_NAME "/enablesparsify",
968 "should the sparsify presolver be enabled within the presolve library?",
969 &presoldata->enablesparsify, TRUE, DEFAULT_ENABLESPARSIFY, NULL, NULL) );
970
971 SCIP_CALL( SCIPaddStringParam(scip, "presolving/" PRESOL_NAME "/probfilename",
972 "filename to store the problem before MILP presolving starts (only enforced constraints)",
973 &presoldata->filename, TRUE, DEFAULT_FILENAME_PROBLEM, NULL, NULL) );
974
975 SCIP_CALL(SCIPaddIntParam(scip, "presolving/" PRESOL_NAME "/verbosity",
976 "verbosity level of PaPILO (0: quiet, 1: errors, 2: warnings, 3: normal, 4: detailed)",
977 &presoldata->verbosity, FALSE, DEFAULT_VERBOSITY, 0, 4, NULL, NULL));
978
979 return SCIP_OKAY;
980}
981
982#endif
Constraint handler for linear constraints in their most general form, .
#define NULL
Definition def.h:267
#define SCIP_REAL_MAX
Definition def.h:174
#define TRUE
Definition def.h:93
#define FALSE
Definition def.h:94
#define SCIPABORT()
Definition def.h:346
#define SCIP_CALL(x)
Definition def.h:374
SCIP_RETCODE SCIPcreateConsBasicLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs)
const char * SCIPgetProbName(SCIP *scip)
Definition scip_prob.c:1067
int SCIPgetNVars(SCIP *scip)
Definition scip_prob.c:1992
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
SCIP_RETCODE SCIPwriteTransProblem(SCIP *scip, const char *filename, const char *extension, SCIP_Bool genericnames)
Definition scip_prob.c:648
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
#define SCIPdebugMsg
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 SCIPaddStringParam(SCIP *scip, const char *name, const char *desc, char **valueptr, SCIP_Bool isadvanced, const char *defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition scip_param.c:194
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 SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition scip_param.c:307
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
SCIP_RETCODE SCIPincludePresolMILP(SCIP *scip)
int SCIPconshdlrGetNCheckConss(SCIP_CONSHDLR *conshdlr)
Definition cons.c:4656
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition scip_cons.c:941
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition cons.c:8214
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition scip_cons.c:1174
SCIP_RETCODE SCIPcaptureCons(SCIP *scip, SCIP_CONS *cons)
Definition scip_cons.c:1139
SCIP_RETCODE SCIPincludeExternalCodeInformation(SCIP *scip, const char *name, const char *description)
#define SCIPfreeBlockMemory(scip, ptr)
Definition scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition scip_mem.h:89
SCIP_RETCODE SCIPsetPresolFree(SCIP *scip, SCIP_PRESOL *presol,)
void SCIPpresolSetData(SCIP_PRESOL *presol, SCIP_PRESOLDATA *presoldata)
Definition presol.c:522
SCIP_PRESOLDATA * SCIPpresolGetData(SCIP_PRESOL *presol)
Definition presol.c:512
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol,)
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)
SCIP_RETCODE SCIPsetPresolInit(SCIP *scip, SCIP_PRESOL *presol,)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeastol(SCIP *scip)
SCIP_Real SCIPepsilon(SCIP *scip)
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition scip_var.c:5205
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition var.c:17538
SCIP_RETCODE SCIPaggregateVars(SCIP *scip, SCIP_VAR *varx, SCIP_VAR *vary, SCIP_Real scalarx, SCIP_Real scalary, SCIP_Real rhs, SCIP_Bool *infeasible, SCIP_Bool *redundant, SCIP_Bool *aggregated)
Definition scip_var.c:8403
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition var.c:17926
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition scip_var.c:5322
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition var.c:17584
SCIP_RETCODE SCIPgetProbvarSum(SCIP *scip, SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
Definition scip_var.c:1796
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition var.c:18088
const char * SCIPvarGetName(SCIP_VAR *var)
Definition var.c:17419
SCIP_RETCODE SCIPmultiaggregateVar(SCIP *scip, SCIP_VAR *var, int naggvars, SCIP_VAR **aggvars, SCIP_Real *scalars, SCIP_Real constant, SCIP_Bool *infeasible, SCIP_Bool *aggregated)
Definition scip_var.c:8537
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition var.c:17610
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition var.c:18078
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition scip_var.c:8278
SCIP_Bool SCIPallowWeakDualReds(SCIP *scip)
Definition scip_var.c:8658
SCIP_Bool SCIPallowStrongDualReds(SCIP *scip)
Definition scip_var.c:8631
unsigned int SCIPinitializeRandomSeed(SCIP *scip, unsigned int initialseedvalue)
return SCIP_OKAY
int c
assert(minobj< SCIPgetCutoffbound(scip))
int nvars
SCIP_VAR * var
int SCIPmatrixGetNNonzs(SCIP_MATRIX *matrix)
Definition matrix.c:1778
int SCIPmatrixGetRowNNonzs(SCIP_MATRIX *matrix, int row)
Definition matrix.c:1708
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
int SCIPmatrixGetNRows(SCIP_MATRIX *matrix)
Definition matrix.c:1732
#define BMSclearMemory(ptr)
Definition memory.h:129
#define PRESOL_NAME
#define PRESOL_PRIORITY
#define PRESOL_MAXROUNDS
#define PRESOL_TIMING
#define PRESOL_DESC
MILP presolver that calls the presolve library on the constraint matrix.
public methods for managing constraints
public methods for matrix
public methods for message output
#define SCIPerrorMessage
Definition pub_message.h:64
public methods for presolvers
public methods for problem variables
#define DEFAULT_RANDOMSEED
public methods for constraint handler plugins and constraints
general public methods
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for presolving plugins
public methods for global and local (sub)problems
public methods for random numbers
static SCIP_RETCODE presolve(SCIP *scip, SCIP_Bool *unbounded, SCIP_Bool *infeasible, SCIP_Bool *vanished)
public methods for timing
public methods for SCIP variables
@ SCIP_VERBLEVEL_HIGH
#define SCIP_DECL_PRESOLCOPY(x)
Definition type_presol.h:60
struct SCIP_PresolData SCIP_PRESOLDATA
Definition type_presol.h:51
#define SCIP_DECL_PRESOLFREE(x)
Definition type_presol.h:68
#define SCIP_DECL_PRESOLINIT(x)
Definition type_presol.h:76
#define SCIP_DECL_PRESOLEXEC(x)
@ SCIP_DIDNOTRUN
Definition type_result.h:42
@ SCIP_CUTOFF
Definition type_result.h:48
@ SCIP_DIDNOTFIND
Definition type_result.h:44
@ SCIP_UNBOUNDED
Definition type_result.h:47
@ SCIP_SUCCESS
Definition type_result.h:58
@ SCIP_INVALIDRESULT
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_VARTYPE_IMPLINT
Definition type_var.h:64
@ SCIP_VARSTATUS_FIXED
Definition type_var.h:52
@ SCIP_VARSTATUS_MULTAGGR
Definition type_var.h:54
@ SCIP_VARSTATUS_NEGATED
Definition type_var.h:55
@ SCIP_VARSTATUS_AGGREGATED
Definition type_var.h:53