43#ifndef SCIP_WITH_PAPILO
58#pragma GCC diagnostic ignored "-Wshadow"
59#pragma GCC diagnostic ignored "-Wctor-dtor-privacy"
60#pragma GCC diagnostic ignored "-Wredundant-decls"
63#if __GNUC__ == 12 && __GNUC__MINOR__ <= 2
64#pragma GCC diagnostic ignored "-Wstringop-overflow"
86#include "papilo/core/Presolve.hpp"
87#include "papilo/core/ProblemBuilder.hpp"
88#include "papilo/Config.hpp"
90#define PRESOL_NAME "milp"
91#define PRESOL_DESC "MILP specific presolving methods"
92#define PRESOL_PRIORITY 9999999
93#define PRESOL_MAXROUNDS -1
94#define PRESOL_TIMING SCIP_PRESOLTIMING_MEDIUM
97#define DEFAULT_THREADS 1
98#define DEFAULT_MAXFILLINPERSUBST 3
99#define DEFAULT_MAXSHIFTPERROW 10
100#define DEFAULT_DETECTLINDEP 0
101#define DEFAULT_MAXBADGESIZE_SEQ 15000
102#define DEFAULT_MAXBADGESIZE_PAR -1
103#define DEFAULT_RANDOMSEED 0
104#define DEFAULT_MODIFYCONSFAC 0.8
106#define DEFAULT_MARKOWITZTOLERANCE 0.01
107#define DEFAULT_VERBOSITY 0
108#define DEFAULT_HUGEBOUND 1e8
109#define DEFAULT_ENABLEPARALLELROWS TRUE
110#define DEFAULT_ENABLEDOMCOL TRUE
111#define DEFAULT_ENABLEDUALINFER TRUE
112#define DEFAULT_ENABLEMULTIAGGR TRUE
113#define DEFAULT_ENABLEPROBING TRUE
114#define DEFAULT_ENABLESPARSIFY FALSE
115#define DEFAULT_FILENAME_PROBLEM "-"
122struct SCIP_PresolData
146 char* filename =
NULL;
168 builder.reserve(nnz, nrows, ncols);
172 for(
int i = 0;
i != ncols; ++
i)
181#if PAPILO_VERSION_MAJOR > 2 || (PAPILO_VERSION_MAJOR == 2 && PAPILO_VERSION_MINOR >= 1)
194 for(
int i = 0;
i != nrows; ++
i)
247 data->lastncols = -1;
248 data->lastnrows = -1;
259 SCIP_Bool initialized;
261 SCIP_Bool infeasible;
272 if( data->lastncols != -1 && data->lastnrows != -1 &&
273 nvars > data->lastncols * 0.85 &&
274 nconss > data->lastnrows * 0.85 )
278 naddconss, ndelconss, nchgcoefs, nchgbds, nfixedvars) );
317 presolve.getPresolveOptions().substitutebinarieswithints =
false;
322 presolve.getPresolveOptions().removeslackvars =
false;
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;
338 presolve.getPresolveOptions().threads = data->threads;
342 "PaPILO can utilize only multiple threads if it is build with TBB.\n");
343 presolve.getPresolveOptions().threads = 1;
349 presolve.getPresolveOptions().dualreds = 0;
351 presolve.getPresolveOptions().dualreds = 2;
353 presolve.getPresolveOptions().dualreds = 1;
355 presolve.getPresolveOptions().dualreds = 0;
358 using uptr = std::unique_ptr<PresolveMethod<SCIP_Real>>;
367 if( data->enableparallelrows )
372#if PAPILO_VERSION_MAJOR > 2 || (PAPILO_VERSION_MAJOR == 2 && PAPILO_VERSION_MINOR >= 1)
374 dualfix->set_fix_to_infinity_allowed(
false);
385 if( data->enabledualinfer )
387 if( data->enableprobing )
389#if PAPILO_VERSION_MAJOR > 2 || (PAPILO_VERSION_MAJOR == 2 && PAPILO_VERSION_MINOR >= 1)
391 if(
presolve.getPresolveOptions().runs_sequential() )
393 probing->set_max_badge_size( data->maxbadgesizeseq );
397 probing->set_max_badge_size( data->maxbadgesizepar );
405 " The parameter 'presolving/milp/maxbadgesizeseq' can only be used with PaPILO 2.1.0 or later versions.\n");
409 " The parameter 'presolving/milp/maxbadgesizepar' can only be used with PaPILO 2.1.0 or later versions.\n");
413 if( data->enabledomcol )
415 if( data->enablemultiaggr )
417 if( data->enablesparsify )
425#ifdef SCIP_PRESOLLIB_ENABLE_OUTPUT
444 int oldnnz = problem.getConstraintMatrix().getNnz();
447#if (PAPILO_VERSION_MAJOR >= 2)
452 data->lastncols = problem.getNCols();
453 data->lastnrows = problem.getNRows();
458 case PresolveStatus::kInfeasible:
461 " (%.1fs) MILP presolver detected infeasibility\n",
465 case PresolveStatus::kUnbndOrInfeas:
466 case PresolveStatus::kUnbounded:
469 " (%.1fs) MILP presolver detected unboundedness\n",
473 case PresolveStatus::kUnchanged:
475 data->lastncols =
nvars;
476 data->lastnrows = nconss;
478 " (%.1fs) MILP presolver found nothing\n",
482 case PresolveStatus::kReduced:
483 data->lastncols = problem.getNCols();
484 data->lastnrows = problem.getNRows();
489 std::vector<SCIP_VAR*> tmpvars;
490 std::vector<SCIP_Real> tmpvals;
493 int newnnz = problem.getConstraintMatrix().getNnz();
496 (problem.getNRows() <= data->modifyconsfac * data->lastnrows ||
523 const auto&
consmatrix = problem.getConstraintMatrix();
529 SCIP_Real*
rowvals =
const_cast<SCIP_Real*
>(
rowvec.getValues());
555 for( std::size_t
i = 0;
i !=
res.postsolve.types.size(); ++
i )
558 int first =
res.postsolve.start[
i];
559 int last =
res.postsolve.start[
i + 1];
563 case ReductionType::kFixedCol:
567 int col =
res.postsolve.indices[first];
571 SCIP_Real value =
res.postsolve.values[first];
590#if (PAPILO_VERSION_MAJOR >= 2)
591 case ReductionType::kSubstitutedColWithDual:
593 case ReductionType::kSubstitutedCol:
602 if( type == ReductionType::kSubstitutedCol )
604 rowlen = last - first - 1;
605 col =
res.postsolve.indices[first];
606 side =
res.postsolve.values[first];
611#if (PAPILO_VERSION_MAJOR >= 2)
612 if( type == ReductionType::kSubstitutedColWithDual )
614 rowlen = (int)
res.postsolve.values[first];
615 col =
res.postsolve.indices[first + 3 +
rowlen];
616 side =
res.postsolve.values[first + 1];
621 assert(side ==
res.postsolve.values[first + 2]);
622 assert(
res.postsolve.indices[first + 1] == 0);
623 assert(
res.postsolve.indices[first + 2] == 0);
625 assert( type == ReductionType::kSubstitutedCol || type == ReductionType::kSubstitutedColWithDual );
627 assert( type == ReductionType::kSubstitutedCol );
631 SCIP_Bool redundant =
FALSE;
632 SCIP_Real constant = 0.0;
658 if(
res.postsolve.indices[
j] == col )
680 if(
res.postsolve.indices[
j] == col )
684 tmpvals.push_back(-
res.postsolve.values[
j] /
colCoef);
701 tmpvals.push_back(
res.postsolve.values[
j]);
707 tmpvars.size(), tmpvars.data(), tmpvals.data(), side, side ) );
721 case ReductionType::kParallelCol:
723#if (PAPILO_VERSION_MAJOR <= 1 && PAPILO_VERSION_MINOR==0)
725 case ReductionType::kFixedInfCol: {
734 int column =
res.postsolve.indices[first];
751#if (PAPILO_VERSION_MAJOR >= 2)
752 case ReductionType::kVarBoundChange :
753 case ReductionType::kRedundantRow :
754 case ReductionType::kRowBoundChange :
755 case ReductionType::kReasonForRowBoundChangeForcedByRow :
756 case ReductionType::kRowBoundChangeForcedByRow :
757 case ReductionType::kSaveRow :
758 case ReductionType::kReducedBoundsCost :
759 case ReductionType::kColumnDualValue :
760 case ReductionType::kRowDualValue :
761 case ReductionType::kCoefficientChange :
763 SCIPerrorMessage(
"PaPILO: PaPILO should not return dual postsolving reductions in SCIP!!\n");
777 for(
int i = 0;
i != problem.getNCols(); ++
i )
817 " (%.1fs) MILP presolver (%d rounds): %d aggregations, %d fixings, %d bound changes\n",
841#if defined(PAPILO_VERSION_TWEAK) && PAPILO_VERSION_TWEAK != 0
847#if defined(PAPILO_GITHASH_AVAILABLE) && defined(PAPILO_TBB)
848 String desc = fmt::format(
"parallel presolve for integer and linear optimization (github.com/scipopt/papilo) (built with TBB) [GitHash: {}]",
PAPILO_GITHASH);
849#elif !defined(PAPILO_GITHASH_AVAILABLE) && !defined(PAPILO_TBB)
850 String desc(
"parallel presolve for integer and linear optimization (github.com/scipopt/papilo)");
851#elif defined(PAPILO_GITHASH_AVAILABLE) && !defined(PAPILO_TBB)
852 String desc = fmt::format(
"parallel presolve for integer and linear optimization (github.com/scipopt/papilo) [GitHash: {}]",
PAPILO_GITHASH);
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) (built with TBB)");
882 "maximum number of threads presolving may use (0: automatic)",
886 "presolving/" PRESOL_NAME "/maxfillinpersubstitution",
887 "maximal possible fillin for substitutions to be considered",
892 "maximal amount of nonzeros allowed to be shifted to make space for substitutions",
897 "the random seed used for randomization of tie breaking",
900 if( DependentRows<double>::Enabled )
903 "presolving/" PRESOL_NAME "/detectlineardependency",
904 "should linear dependent equations and free columns be removed? (0: never, 1: for LPs, 2: always)",
908 presoldata->detectlineardependency = 0;
912 "modify SCIP constraints when the number of nonzeros or rows is at most this factor "
913 "times the number of nonzeros or rows before presolving",
918 "the markowitz tolerance used for substitutions",
923 "absolute bound value that is considered too huge for activitity based calculations",
926#if PAPILO_VERSION_MAJOR > 2 || (PAPILO_VERSION_MAJOR == 2 && PAPILO_VERSION_MINOR >= 1)
928 "maximal badge size in Probing in PaPILO if PaPILO is executed in sequential mode",
932 "maximal badge size in Probing in PaPILO if PaPILO is executed in parallel mode",
941 "should the parallel rows presolver be enabled within the presolve library?",
946 "should the dominated column presolver be enabled within the presolve library?",
951 "should the dualinfer presolver be enabled within the presolve library?",
956 "should the multi-aggregation presolver be enabled within the presolve library?",
961 "should the probing presolver be enabled within the presolve library?",
966 "should the sparsify presolver be enabled within the presolve library?",
970 "filename to store the problem before MILP presolving starts",
974 "verbosity level of PaPILO (0: quiet, 1: errors, 2: warnings, 3: normal, 4: detailed)",
Constraint handler for linear constraints in their most general form, .
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)
int SCIPgetNVars(SCIP *scip)
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
int SCIPgetNConss(SCIP *scip)
SCIP_RETCODE SCIPwriteTransProblem(SCIP *scip, const char *filename, const char *extension, SCIP_Bool genericnames)
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
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)
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)
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)
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
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)
SCIP_RETCODE SCIPincludePresolMILP(SCIP *scip)
int SCIPconshdlrGetNCheckConss(SCIP_CONSHDLR *conshdlr)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
const char * SCIPconsGetName(SCIP_CONS *cons)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
SCIP_RETCODE SCIPcaptureCons(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPincludeExternalCodeInformation(SCIP *scip, const char *name, const char *description)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_RETCODE SCIPsetPresolFree(SCIP *scip, SCIP_PRESOL *presol,)
void SCIPpresolSetData(SCIP_PRESOL *presol, SCIP_PRESOLDATA *presoldata)
SCIP_PRESOLDATA * SCIPpresolGetData(SCIP_PRESOL *presol)
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)
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
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)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
SCIP_RETCODE SCIPgetProbvarSum(SCIP *scip, SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
const char * SCIPvarGetName(SCIP_VAR *var)
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)
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
SCIP_Bool SCIPallowWeakDualReds(SCIP *scip)
SCIP_Bool SCIPallowStrongDualReds(SCIP *scip)
unsigned int SCIPinitializeRandomSeed(SCIP *scip, unsigned int initialseedvalue)
assert(minobj< SCIPgetCutoffbound(scip))
int SCIPmatrixGetNNonzs(SCIP_MATRIX *matrix)
int SCIPmatrixGetRowNNonzs(SCIP_MATRIX *matrix, int row)
SCIP_Real SCIPmatrixGetRowLhs(SCIP_MATRIX *matrix, int row)
SCIP_Real * SCIPmatrixGetRowValPtr(SCIP_MATRIX *matrix, int row)
SCIP_Real SCIPmatrixGetRowRhs(SCIP_MATRIX *matrix, int row)
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)
int SCIPmatrixGetNColumns(SCIP_MATRIX *matrix)
SCIP_CONS * SCIPmatrixGetCons(SCIP_MATRIX *matrix, int row)
void SCIPmatrixFree(SCIP *scip, SCIP_MATRIX **matrix)
SCIP_VAR * SCIPmatrixGetVar(SCIP_MATRIX *matrix, int col)
int * SCIPmatrixGetRowIdxPtr(SCIP_MATRIX *matrix, int row)
int SCIPmatrixGetNRows(SCIP_MATRIX *matrix)
#define BMSclearMemory(ptr)
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
public methods for presolvers
public methods for problem variables
#define DEFAULT_RANDOMSEED
public methods for constraint handler plugins and constraints
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
#define SCIP_DECL_PRESOLCOPY(x)
struct SCIP_PresolData SCIP_PRESOLDATA
#define SCIP_DECL_PRESOLFREE(x)
#define SCIP_DECL_PRESOLINIT(x)
#define SCIP_DECL_PRESOLEXEC(x)
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_VARSTATUS_MULTAGGR
@ SCIP_VARSTATUS_AGGREGATED