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
439 " writing transformed problem to %s (only enforced constraints)\n", data->filename);
446 int oldnnz = problem.getConstraintMatrix().getNnz();
449#if (PAPILO_VERSION_MAJOR >= 2)
454 data->lastncols = problem.getNCols();
455 data->lastnrows = problem.getNRows();
460 case PresolveStatus::kInfeasible:
463 " (%.1fs) MILP presolver detected infeasibility\n",
467 case PresolveStatus::kUnbndOrInfeas:
468 case PresolveStatus::kUnbounded:
471 " (%.1fs) MILP presolver detected unboundedness\n",
475 case PresolveStatus::kUnchanged:
477 data->lastncols =
nvars;
478 data->lastnrows = nconss;
480 " (%.1fs) MILP presolver found nothing\n",
484 case PresolveStatus::kReduced:
485 data->lastncols = problem.getNCols();
486 data->lastnrows = problem.getNRows();
491 std::vector<SCIP_VAR*> tmpvars;
492 std::vector<SCIP_Real> tmpvals;
495 int newnnz = problem.getConstraintMatrix().getNnz();
498 (problem.getNRows() <= data->modifyconsfac * data->lastnrows ||
525 const auto&
consmatrix = problem.getConstraintMatrix();
531 SCIP_Real*
rowvals =
const_cast<SCIP_Real*
>(
rowvec.getValues());
557 for( std::size_t
i = 0;
i !=
res.postsolve.types.size(); ++
i )
560 int first =
res.postsolve.start[
i];
561 int last =
res.postsolve.start[
i + 1];
565 case ReductionType::kFixedCol:
569 int col =
res.postsolve.indices[first];
573 SCIP_Real value =
res.postsolve.values[first];
592#if (PAPILO_VERSION_MAJOR >= 2)
593 case ReductionType::kSubstitutedColWithDual:
595 case ReductionType::kSubstitutedCol:
604 if( type == ReductionType::kSubstitutedCol )
606 rowlen = last - first - 1;
607 col =
res.postsolve.indices[first];
608 side =
res.postsolve.values[first];
613#if (PAPILO_VERSION_MAJOR >= 2)
614 if( type == ReductionType::kSubstitutedColWithDual )
616 rowlen = (int)
res.postsolve.values[first];
617 col =
res.postsolve.indices[first + 3 +
rowlen];
618 side =
res.postsolve.values[first + 1];
623 assert(side ==
res.postsolve.values[first + 2]);
624 assert(
res.postsolve.indices[first + 1] == 0);
625 assert(
res.postsolve.indices[first + 2] == 0);
627 assert( type == ReductionType::kSubstitutedCol || type == ReductionType::kSubstitutedColWithDual );
629 assert( type == ReductionType::kSubstitutedCol );
633 SCIP_Bool redundant =
FALSE;
634 SCIP_Real constant = 0.0;
660 if(
res.postsolve.indices[
j] == col )
682 if(
res.postsolve.indices[
j] == col )
686 tmpvals.push_back(-
res.postsolve.values[
j] /
colCoef);
703 tmpvals.push_back(
res.postsolve.values[
j]);
709 tmpvars.size(), tmpvars.data(), tmpvals.data(), side, side ) );
723 case ReductionType::kParallelCol:
725#if (PAPILO_VERSION_MAJOR <= 1 && PAPILO_VERSION_MINOR==0)
727 case ReductionType::kFixedInfCol: {
736 int column =
res.postsolve.indices[first];
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 :
765 SCIPerrorMessage(
"PaPILO: PaPILO should not return dual postsolving reductions in SCIP!!\n");
779 for(
int i = 0;
i != problem.getNCols(); ++
i )
819 " (%.1fs) MILP presolver (%d rounds): %d aggregations, %d fixings, %d bound changes\n",
843#if defined(PAPILO_VERSION_TWEAK) && PAPILO_VERSION_TWEAK != 0
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)");
884 "maximum number of threads presolving may use (0: automatic)",
888 "presolving/" PRESOL_NAME "/maxfillinpersubstitution",
889 "maximal possible fillin for substitutions to be considered",
894 "maximal amount of nonzeros allowed to be shifted to make space for substitutions",
899 "the random seed used for randomization of tie breaking",
902 if( DependentRows<double>::Enabled )
905 "presolving/" PRESOL_NAME "/detectlineardependency",
906 "should linear dependent equations and free columns be removed? (0: never, 1: for LPs, 2: always)",
910 presoldata->detectlineardependency = 0;
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",
920 "the markowitz tolerance used for substitutions",
925 "absolute bound value that is considered too huge for activitity based calculations",
928#if PAPILO_VERSION_MAJOR > 2 || (PAPILO_VERSION_MAJOR == 2 && PAPILO_VERSION_MINOR >= 1)
930 "maximal badge size in Probing in PaPILO if PaPILO is executed in sequential mode",
934 "maximal badge size in Probing in PaPILO if PaPILO is executed in parallel mode",
943 "should the parallel rows presolver be enabled within the presolve library?",
948 "should the dominated column presolver be enabled within the presolve library?",
953 "should the dualinfer presolver be enabled within the presolve library?",
958 "should the multi-aggregation presolver be enabled within the presolve library?",
963 "should the probing presolver be enabled within the presolve library?",
968 "should the sparsify presolver be enabled within the presolve library?",
972 "filename to store the problem before MILP presolving starts (only enforced constraints)",
976 "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