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_HUGEBOUND 1e8
108#define DEFAULT_ENABLEPARALLELROWS TRUE
109#define DEFAULT_ENABLEDOMCOL TRUE
110#define DEFAULT_ENABLEDUALINFER TRUE
111#define DEFAULT_ENABLEMULTIAGGR TRUE
112#define DEFAULT_ENABLEPROBING TRUE
113#define DEFAULT_ENABLESPARSIFY FALSE
114#define DEFAULT_FILENAME_PROBLEM "-"
121struct SCIP_PresolData
143 char* filename =
NULL;
165 builder.reserve(nnz, nrows, ncols);
169 for(
int i = 0;
i != ncols; ++
i)
178#if PAPILO_VERSION_MAJOR > 2 || (PAPILO_VERSION_MAJOR == 2 && PAPILO_VERSION_MINOR >= 1)
191 for(
int i = 0;
i != nrows; ++
i)
244 data->lastncols = -1;
245 data->lastnrows = -1;
256 SCIP_Bool initialized;
258 SCIP_Bool infeasible;
269 if( data->lastncols != -1 && data->lastnrows != -1 &&
270 nvars > data->lastncols * 0.85 &&
271 nconss > data->lastnrows * 0.85 )
275 naddconss, ndelconss, nchgcoefs, nchgbds, nfixedvars) );
314 presolve.getPresolveOptions().substitutebinarieswithints =
false;
319 presolve.getPresolveOptions().removeslackvars =
false;
322 presolve.getPresolveOptions().maxfillinpersubstitution = data->maxfillinpersubstitution;
323 presolve.getPresolveOptions().markowitz_tolerance = data->markowitztolerance;
324 presolve.getPresolveOptions().maxshiftperrow = data->maxshiftperrow;
325 presolve.getPresolveOptions().hugeval = data->hugebound;
334 presolve.getPresolveOptions().threads = data->threads;
338 presolve.getPresolveOptions().dualreds = 0;
340 presolve.getPresolveOptions().dualreds = 2;
342 presolve.getPresolveOptions().dualreds = 1;
344 presolve.getPresolveOptions().dualreds = 0;
347 using uptr = std::unique_ptr<PresolveMethod<SCIP_Real>>;
356 if( data->enableparallelrows )
361#if PAPILO_VERSION_MAJOR > 2 || (PAPILO_VERSION_MAJOR == 2 && PAPILO_VERSION_MINOR >= 1)
363 dualfix->set_fix_to_infinity_allowed(
false);
374 if( data->enabledualinfer )
376 if( data->enableprobing )
378#if PAPILO_VERSION_MAJOR > 2 || (PAPILO_VERSION_MAJOR == 2 && PAPILO_VERSION_MINOR >= 1)
380 if(
presolve.getPresolveOptions().runs_sequential() )
382 probing->set_max_badge_size( data->maxbadgesizeseq );
386 probing->set_max_badge_size( data->maxbadgesizepar );
394 " The parameter 'presolving/milp/maxbadgesizeseq' can only be used with PaPILO 2.1.0 or later versions.\n");
398 " The parameter 'presolving/milp/maxbadgesizepar' can only be used with PaPILO 2.1.0 or later versions.\n");
402 if( data->enabledomcol )
404 if( data->enablemultiaggr )
406 if( data->enablesparsify )
414#ifdef SCIP_PRESOLLIB_ENABLE_OUTPUT
417 presolve.setVerbosityLevel(VerbosityLevel::kQuiet);
433 int oldnnz = problem.getConstraintMatrix().getNnz();
436#if (PAPILO_VERSION_MAJOR >= 2)
441 data->lastncols = problem.getNCols();
442 data->lastnrows = problem.getNRows();
447 case PresolveStatus::kInfeasible:
450 " (%.1fs) MILP presolver detected infeasibility\n",
454 case PresolveStatus::kUnbndOrInfeas:
455 case PresolveStatus::kUnbounded:
458 " (%.1fs) MILP presolver detected unboundedness\n",
462 case PresolveStatus::kUnchanged:
464 data->lastncols =
nvars;
465 data->lastnrows = nconss;
467 " (%.1fs) MILP presolver found nothing\n",
471 case PresolveStatus::kReduced:
472 data->lastncols = problem.getNCols();
473 data->lastnrows = problem.getNRows();
478 std::vector<SCIP_VAR*> tmpvars;
479 std::vector<SCIP_Real> tmpvals;
482 int newnnz = problem.getConstraintMatrix().getNnz();
485 (problem.getNRows() <= data->modifyconsfac * data->lastnrows ||
512 const auto&
consmatrix = problem.getConstraintMatrix();
518 SCIP_Real*
rowvals =
const_cast<SCIP_Real*
>(
rowvec.getValues());
544 for( std::size_t
i = 0;
i !=
res.postsolve.types.size(); ++
i )
547 int first =
res.postsolve.start[
i];
548 int last =
res.postsolve.start[
i + 1];
552 case ReductionType::kFixedCol:
556 int col =
res.postsolve.indices[first];
560 SCIP_Real value =
res.postsolve.values[first];
579#if (PAPILO_VERSION_MAJOR >= 2)
580 case ReductionType::kSubstitutedColWithDual:
582 case ReductionType::kSubstitutedCol:
591 if( type == ReductionType::kSubstitutedCol )
593 rowlen = last - first - 1;
594 col =
res.postsolve.indices[first];
595 side =
res.postsolve.values[first];
600#if (PAPILO_VERSION_MAJOR >= 2)
601 if( type == ReductionType::kSubstitutedColWithDual )
603 rowlen = (int)
res.postsolve.values[first];
604 col =
res.postsolve.indices[first + 3 +
rowlen];
605 side =
res.postsolve.values[first + 1];
610 assert(side ==
res.postsolve.values[first + 2]);
611 assert(
res.postsolve.indices[first + 1] == 0);
612 assert(
res.postsolve.indices[first + 2] == 0);
614 assert( type == ReductionType::kSubstitutedCol || type == ReductionType::kSubstitutedColWithDual );
616 assert( type == ReductionType::kSubstitutedCol );
620 SCIP_Bool redundant =
FALSE;
621 SCIP_Real constant = 0.0;
647 if(
res.postsolve.indices[
j] == col )
669 if(
res.postsolve.indices[
j] == col )
673 tmpvals.push_back(-
res.postsolve.values[
j] /
colCoef);
690 tmpvals.push_back(
res.postsolve.values[
j]);
696 tmpvars.size(), tmpvars.data(), tmpvals.data(), side, side ) );
710 case ReductionType::kParallelCol:
712#if (PAPILO_VERSION_MAJOR <= 1 && PAPILO_VERSION_MINOR==0)
714 case ReductionType::kFixedInfCol: {
723 int column =
res.postsolve.indices[first];
740#if (PAPILO_VERSION_MAJOR >= 2)
741 case ReductionType::kVarBoundChange :
742 case ReductionType::kRedundantRow :
743 case ReductionType::kRowBoundChange :
744 case ReductionType::kReasonForRowBoundChangeForcedByRow :
745 case ReductionType::kRowBoundChangeForcedByRow :
746 case ReductionType::kSaveRow :
747 case ReductionType::kReducedBoundsCost :
748 case ReductionType::kColumnDualValue :
749 case ReductionType::kRowDualValue :
750 case ReductionType::kCoefficientChange :
752 SCIPerrorMessage(
"PaPILO: PaPILO should not return dual postsolving reductions in SCIP!!\n");
766 for(
int i = 0;
i != problem.getNCols(); ++
i )
806 " (%.1fs) MILP presolver (%d rounds): %d aggregations, %d fixings, %d bound changes\n",
830#if defined(PAPILO_VERSION_TWEAK) && PAPILO_VERSION_TWEAK != 0
836#ifdef PAPILO_GITHASH_AVAILABLE
837 String desc = fmt::format(
"parallel presolve for integer and linear optimization (github.com/scipopt/papilo) [GitHash: {}]",
PAPILO_GITHASH);
839 String desc(
"parallel presolve for integer and linear optimization (github.com/scipopt/papilo)");
867 "maximum number of threads presolving may use (0: automatic)",
871 "presolving/" PRESOL_NAME "/maxfillinpersubstitution",
872 "maximal possible fillin for substitutions to be considered",
877 "maximal amount of nonzeros allowed to be shifted to make space for substitutions",
882 "the random seed used for randomization of tie breaking",
885 if( DependentRows<double>::Enabled )
888 "presolving/" PRESOL_NAME "/detectlineardependency",
889 "should linear dependent equations and free columns be removed? (0: never, 1: for LPs, 2: always)",
893 presoldata->detectlineardependency = 0;
897 "modify SCIP constraints when the number of nonzeros or rows is at most this factor "
898 "times the number of nonzeros or rows before presolving",
903 "the markowitz tolerance used for substitutions",
908 "absolute bound value that is considered too huge for activitity based calculations",
911#if PAPILO_VERSION_MAJOR > 2 || (PAPILO_VERSION_MAJOR == 2 && PAPILO_VERSION_MINOR >= 1)
913 "maximal badge size in Probing in PaPILO if PaPILO is executed in sequential mode",
917 "maximal badge size in Probing in PaPILO if PaPILO is executed in parallel mode",
926 "should the parallel rows presolver be enabled within the presolve library?",
931 "should the dominated column presolver be enabled within the presolve library?",
936 "should the dualinfer presolver be enabled within the presolve library?",
941 "should the multi-aggregation presolver be enabled within the presolve library?",
946 "should the probing presolver be enabled within the presolve library?",
951 "should the sparsify presolver be enabled within the presolve library?",
955 "filename to store the problem before MILP presolving starts",
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