Release notes for SCIP 5.0
SCIP 5.0.1
Features
- SCIP executable handles the
SIGTERM
signal. If the process receives aSIGTERM
, SCIP terminates the solution process with a newSCIP_STATUS
codeSCIP_STATUS_TERMINATE
and displays all relevant statistics before exiting. - add number of conflict constraints found by diving heuristics to statistics
- allow output of lower bounds for visualization
- added symmetry detection for linking constraints
Performance improvements
- disable disaggregation of quadratic constraints by changing the default for
constraints/quadratic/maxdisaggrsize
to 1 (disaggregation can still be very helpful on some instances, but also seems hurtful on others) - Cuts:
- increased threshold when to scale up cuts that are generated by nonlinear constraint handlers
- test additional scaling factors in CMIR cut generation heuristic
- cleaned up implementation of the cut selection procedure and added new cut quality measure
- use random tie-breaking in cut selection
Interface changes
New API functions
- new methods SCIPtryTerminate() and SCIPterminated() in scip/interrupt.h for handling of SIGTERM signals.
- new method SCIPselectCuts() to run SCIP's cut selection procedure on a given array of cuts
Changed parameters
- rename parameter
constraints/orbisack/orbisack/coverseparation
toconstraints/orbisack/coverseparation
New parameters
visual/displb
that enables output of lower bounds for visualizationpresolving/symmetry/displaynorbitvars
(whether we display the number of affected variables in the statistics)separating/efficacyfac
to change the weight of the efficacy in cut score calculationseparating/dircutoffdistfac
to change the weight of the directed cutoff distance in cut score calculation
Data structures
- new
SCIP_STATUS
codeSCIP_STATUS_TERMINATE
in scip/interrupt.h for handling of SIGTERM signals.
Unit tests
- expanded unit tests of the lpis
- added check to unit tests that problem is not solved after every change
Fixed bugs
- fixed LP status to unsolved when marking LP to be resolved if objective limit has changed
- copy parameter settings to sub-SCIPs in SCIPcopyLargeNeighborhoodSearch() also when copying only LP rows
- fixed a check for fixed variables in Binpacking example
- generate deprecation warnings when using SCIPaddCut
- fix bug in sepa_gomory if cut is a bound change
- fixed handling of infinite bounds in cons_sos1
- Constraints:
- fixed bug while scaling linear constraints
- don't delete conflict constraints that were transformed into model constraints during a restart
- fixed treatment of variable aggregations in knapsack constraint handler that led to wrong propagations
- LP Interface:
- fixed LPI status after changing objective in lpi_cpx, lpi_grb, lpi_xprs, lpi_msk
- fixed and unified asserts in LPIs
- retrieve interior solution instead of (possibly non-existing) basic solution from mosek after using barrier without crossover in lpi_msk
- fixed bug with
NULL
pointer handling in LPIs
- Heuristics:
- fixed wrong cast in LP iteration limit computation in proximity search heuristic
- fixed check for time limit in heur_nlpdiving
- improved numerics and fixed stop criterion in zirounding heuristic
SCIP 5.0.0
Features
- new numerical solution violations get printed when checksol is called
- added analysis of the clique table which identifies possible aggregations via the search for strongly connected components and may detect infeasible assignments on the way
- added macros to do computations with a higher precision by using double-double arithmetic
- extended conflict analysis by analyzing dual solutions of boundexceeding LPs
- revised internal debugging mechanism to check against a user given debug solution (debug.h)
- Heuristic:
- add new heuristic MPEC that solves a MPEC reformulation of a mixed-binary nonlinear problem by regularized NLP reformulations
- new primal heuristic ALNS that orchestrates eight different LNS heuristics adaptively using algorithms for the multi-armed bandit problem
- three bandit selection algorithms to face sequential decision problems under uncertainty
- Presolving and symmetry:
- added presol_symmetry.c for computing and storing symmetry information of a MIP
- added presol_symbreak.c to detect special symmetry structures and to add symmetry handling constraints
- SCIP can now automatically detect and compute symmetries in MIPs (if a graph automorphism code is linked in)
- added cons_symresack.c to handle permutation symmetries in a binary programs via inequalities and propagation
- added cons_orbisack.c to handle special permutation symmetries in a binary programs via inequalities and propagation
- cons_orbitope.c can now handle full orbitopes as well
- Propagator:
- added new propagator orbital fixing
- utilizing linear inequalities to compute stronger linearizations for bilinear terms; the inequalities are computed in the OBBT propagator
- Cuts:
- added API for aggregating rows for generating cuts which uses double-double arithmetic internally
- added filtering of parallel cuts in the cut pool
- Plugins:
- added new plugin type
table
for adding user-defined statistics tables - new presolving plugin presol_sparsify that tries to cancel nonzero coefficients in linear constraints by adding multiples of linear equalities
- added new plugin type
Performance improvements
- use disjoint set to reduce peak memory usage and time to compute of clique table connectedness information
- add and use RESTRICT macro for some pointers
- improved the implementation of SCIPvarGetActiveRepresentatives
- speed-up reverse propagation
- removed bestrelaxsol and directly access relaxation solution instead to decrease overhead when using relaxation handlers
- for fast presolving emphasis, disable use of implications in logicor presolving
- use limit on the total number of nonzeros added to the clique table during the greedyCliqueAlgorithm of cons_knapsack.c
- revised disaggregation of quadratic constraints: the number of created constraints can now be controlled and the disaggregated constraints are scaled in order to increase numerical accuracy
- disabled reformulation of products of a binary variable with a linear term that does not solely involve binary variables
- speed up creation of LP in the computation of relative interior points
- improved dual ray analysis
- drop events of disabled linear constraints to reduce event processing effort
- Separation:
- new implementation of zerohalf separator
- enabled cutting plane separation in the tree
- improved cut selection and management
- improved cut post-processing: apply coefficient tightening, enforce maximal dynamism
- Heuristics:
- improved selection of rows in CMIR aggregation heuristic
- generate lifted flowcover cuts in CMIR cut generation heuristic
- faster implementation of CMIR cut generation heuristic
- use LP solution polishing during probing and diving mode to activate it during many primal heuristics; remains disabled during strong branching and OBBT
- improved versions of the clique and variable bound pre-root heuristics that are often able to fix many more variables
Interface changes
New and changed callbacks
- New types:
- added new abstract selection algorithm
SCIP_BANDIT
together with callbacks - added new types for symmetry handling
- added new abstract selection algorithm
- NLP interface:
- dropped NLP termination status
SCIP_NLPTERMSTAT_UOBJLIM
- dropped NLP termination status
- NLP callbacks:
- added parameter
objval
toSCIP_DECL_NLPIGETSOLUTION
for returning the optimal objective value (can be set toNULL
)
- added parameter
- Separation callbacks:
- added parameter
allowlocal
toSCIP_DECL_SEPAEXECLP
andSCIP_DECL_SEPAEXECSOL
to switch generation of locally valid cuts - added parameter
dstatssize
toSCIP_DECL_NLPIDELVARSET
andSCIP_DECL_NLPIDELCONSSET
- added parameter
Deleted and changed API methods
- Branching rules:
- removed parameter
allowaddcons
from SCIPselectVarPseudoStrongBranching(), SCIPselectVarStrongBranching(), and SCIPincludeBranchruleRelpscost()
- removed parameter
- Constraint Handlers:
- generalized SCIPcreateConsOrbitope() and SCIPcreateConsBasicOrbitope() method to three orbitope types (full, partitioning, packing)
- Cutting plane separation methods:
- changed function signature of SCIPcalcMIR()
- changed function signature of SCIPcalcStrongCG()
- new method SCIPaddRow() to replace deprecated SCIPaddCut()
- removed parameter
scaling
from SCIPgetRowprepViolation() - added parameter
allowlocal
to SCIPseparateSol()
- LP interface:
- replaced LP parameters
SCIP_LPPARAM_LOBJLIM
andSCIP_LPPARAM_UOBJLIM
bySCIP_LPPARAM_OBJLIM
- replaced LP parameters
- NLP interface:
- SCIPnlpStatisticsCreate() and SCIPnlpStatisticsFree() now require a pointer to blockmemory as parameter
- added parameter
objval
to SCIPnlpiGetSolution() of NLPIs for returning the optimal objective value (can be set toNULL
) - added parameter
varnameslength
to SCIPexprParse() - added parameter
dstatssize
to SCIPnlpiDelVarSet() and SCIPnlpiDelConsSet() - added modifier const to
exprtree
parameter of SCIPnlpiChgExprtree()
- Primal heuristics:
- SCIPheurPassIndicator() has a new parameter which allows to pass the objective of the solution
- Relaxator methods:
- added parameter
includeslp
to SCIPmarkRelaxSolValid(), SCIPsetRelaxSolVals() and SCIPsetRelaxSolValsSol(); - removed parameter
includeslp
from SCIPrelaxCreate() and SCIPincludeRelax() - removed functions SCIPrelaxIncludesLp() and SCIPrelaxSetIncludesLp()
- replaced method SCIPgetRelaxFeastolFactor() by SCIPrelaxfeastol() and added SCIPchgRelaxfeastol()
- added parameter
- Misc:
- changed return type of SCIPcliqueGetId() from
int
tounsigned int
- SCIPsolveParallel() is deprecated; use SCIPsolveConcurrent() instead
- removed SCIPvarGetCliqueComponentIdx(); the connectedness information of the clique table is now stored as a
SCIP_DISJOINTSET
member of the clique table and cannot be publicly accessed - added parameter
copytables
to SCIPcopyPlugins() - SCIPsolveParallel() has been deprecated, use the new method SCIPsolveConcurrent() instead
- allowed SCIPgetNConss() in stage
SCIP_STAGE_INITSOLVE
- changed return type of SCIPcliqueGetId() from
New API functions
- SCIPaddRow() to replace deprecated SCIPaddCut()
- methods to display linear constraint classification types; use SCIPclassifyConstraintTypesLinear() after reading a problem to classify linear constraint types
- public methods SCIPvariableGraphBreadthFirst() and SCIPvariableGraph{Create,Free}() to perform breadth-first search on the variable constraint graph used by the GINS and ALNS heuristics
- SCIPsetProbingLPState() to install given LP state and/or norms at the current probing node
- SCIPbranchcandGetLPMaxPrio() and SCIPbranchcandGetExternMaxPrio() to query the maximal branching priority of given branching candidates; also added SCIPbranchcandGetNPrioLPCands() to access the number of LP candidates with this priority.
- SCIPupdateSolIntegralityViolation(), SCIPupdateSolBoundViolation(), SCIPupdateSolLPRowViolation(), SCIPupdateSolConsViolation() and SCIPupdateSolLPConsViolation() for updating numerical solution violations, as well as SCIPactivateSolViolationUpdates() and SCIPdeactivateSolViolationUpdates() for activating/deactivating violation updates globally
- SCIPsetSubscipDepth() to set the depth of SCIP as a copied subproblem during problem stage
- SCIPdivesetGetNSols() to query the number of found solutions from a diveset.
- SCIPnextafter() that wraps different nextafter methods to return the next representable value after a given value
- SCIPlinConsStats{Create,Free,GetTypeCount,GetSum}() and SCIPprintLinConsStats() to work with linear constraint classification through the C API
- SCIPgetRowNumIntCols() that returns the number of integer columns in a row
- SCIPsetSlackVarUb() to control upper bound of slack variable in cons_indicator
- Data structures:
- methods SCIPrandomCreate() and SCIPrandomFree() are no longer public and should be replaced by SCIPcreateRandom() and SCIPfreeRandom(), respectively (the new methods respect the global parameter
randomization/randomseedshift
automatically) - methods SCIPdigraphCreate() and SCIPdigraphCopy() are no longer public and should be replaced by SCIPcreateDigraph() and SCIPcopyDigraph(), respectively, which receive a SCIP argument and are more robust towards future interface changes
- methods SCIPrandomCreate() and SCIPrandomFree() are no longer public and should be replaced by SCIPcreateRandom() and SCIPfreeRandom(), respectively (the new methods respect the global parameter
- Bilinear:
- SCIPgetAllBilinearTermsQuadratic() to access data of all existing bilinear terms in quadratic constraints
- SCIPaddBilinearIneqQuadratic() to propose an inequality with two variables that appear in a bilinear term
- SCIPcomputeBilinEnvelope{1,2}() to compute a linearization of a bilinear term when considering at most two linear inequalities
- Clique:
- SCIPcliqueGetIndex() which returns the unique identifier for the given clique
- SCIPgetNCliquesCreated() which returns the number of cliques created so far
- Cutting plane separation methods:
- SCIPisCutNew() that returns whether a cut is already present in the global cut pool
- SCIPgetSepaMinEfficacy() to access separating/minefficacy(root)
- Interfaces:
- interface methods to create and use bandit algorithms implemented as SCIP core plugins
- interface methods for aggregating rows and computating MIP cuts, see cuts.h
- interface method SCIPsetRandomSeed() to (re)set a random number generator seed
Command line interface
- new interactive shell functionality to display linear constraint classification types; use
display linclass
after reading a problem to classify linear constraint types - new command line parameter
-r
to pass a nonnegative integer as random seed.
Interfaces to external software
- added interface to the NLP solver WORHP
- added interface to the NLP solver FilterSQP
- added interface to graph automorphism algorithms in
src/symmetry/
(initially only to BLISS) - unify handling of objective limit in LPIs by replacing LPI parameters
SCIP_LPPAR_LOBJLIM
andSCIP_LPPAR_UOBJLIM
bySCIP_LPPAR_OBJLIM
- dropped support for MOSEK < 7.0.0.0
Changed parameters
- changed and removed several parameters for zerohalf separator
- replaced
constraints/quadratic/disaggregate
byconstraints/quadratic/maxdisaggrsize
to bound the total number of created constraints when disaggregating a quadratic constraint - new value 3 for parameter
lp/solutionpolishing
to enable LP polishing only during probing and diving mode - parameter
conflict/useboundlp
has new valuesd
(only dual solution analysis) andb
(both, conflict and dual solution analysis) - Heuristics:
- fixed typo
heuristics/completesol/maxunkownrate
has changed toheuristics/completesol/maxunknownrate
- replaced parameter
heuristics/{clique,vbounds}/minfixingrate
byheuristics/{clique,vbounds}/minintfixingrate
andheuristics/{clique,vbounds}/minmipfixingrate
, which check the fixing rate before LP solving and after sub-MIP presolve
- fixed typo
- Separating:
- parameter
separating/maxstallrounds
only applies to nodes in the tree (not the root node, anymore); use the new parameterseparating/maxstallroundsroot
for the root node - moved parameters for flowcover and cmir separators to
separating/aggregation
- parameter
- Removed parameters:
constraints/{abspower,bivariate,nonlinear,quadratic,soc}/scaling
constraints/{abspower,bivariate,quadratic,nonlinear}/mincutefficacysepa
constraints/{abspower,bivariate,quadratic,nonlinear}/mincutefficacyenfofac
constraints/soc/minefficacy
conflict/usemir
conflict/prefermir
heuristics/clique/{multiplier,initseed}
separating/feastolfac
separating/orthofac
separating/cgmip/allowlocal
(use parameter passed to separation callback instead)separating/{gomory,strongcg}/maxweightrange
New parameters
conflict/prefinfproof
(prefer infeasibility proof to boundexceeding proof)conflict/sepaaltproofs
constraints/indicator/maxsepanonviolated
to stop separation after separation of non violated cutsconstraints/orbisack/coverseparation
(whether orbisack cover inequalities should be separated)constraints/orbisack/orbiSeparation
(whether facet defining inequalities for orbisack should be separated)constraints/orbisack/coeffbound
(maximal value of coefficients in orbisack facet inequalities)constraints/orbisack/checkpporbisack
(check whether orbisacks can be strengthened by packing/partitioning constraints)constraints/orbisack/checkalwaysfeas
(whether conscheck returns alwaysSCIP_FEASIBLE
)constraints/orbitope/checkpporbitope
(check packing/partitioning orbitopes)constraints/orbitope/sepafullorbitope
(separate full orbitopes)constraints/orbitope/checkalwaysfeas
(whether conscheck returns alwaysSCIP_FEASIBLE
)constraints/quadratic/{usebilinineqbranch,minscorebilinterms,bilinineqmaxseparounds}
constraints/quadratic/disaggrmergemethod
to change the strategy of how to merge independent blocks of quadratic constraintsconstraints/quadratic/mincurvcollectbilinterms
to change the minimal curvature of constraints to be considered when returning bilinear terms to other pluginsconstraints/quadratic/binreformbinaryonly
to disable reformulation of products of binary and non-binary variablesconstraints/symresack/ppsymresack
(check whether symresacks can be strengthend by packing/partitining constraints)constraints/symresack/checkalwaysfeas
(whether conscheck returns alwaysSCIP_FEASIBLE
)expbackoff
to all separators which increases the frequency exponentially over the depth in the treeheuristics/completesol/{beforepresol,maxlpiter,maxcontvars}
heuristics/{clique,vbounds}/maxbacktracks
to limit the number of backtracks in the fix-and-propagate phaseheuristics/{clique,vbounds}/uselockfixings
to enable fixing of additional variables based on variable locksheuristics/vbounds/{feasvariant,tightenvariant}
to specify the fixing variants used by the vbounds heuristiclp/refactorinterval
to change the refactorization interval of the LP solvermisc/debugsol
to specify a debug solution that should be checked during the solvemisc/usesymmetry
to determine whether symmetry handling should be usedpresolving/symbreak/conssaddlp
(whether symmetry handling inequalities should be added to the LP)presolving/symbreak/addsymresacks
(whether symresacks should be used to handle symmetries)presolving/symbreak/computeorbits
(whether symmetry orbits should be computed)presolving/symbreak/detectorbitopes
(whether it should be checked if some symmetries can be handled by orbitopes)presolving/symmetry/computepresolved
(Whether symmetries are computed after presolving)presolving/symmetry/maxgenerators
(maximal number of generators generated by symmetry detection)presolving/symmetry/checksymmetries
(whether validity of computed symmetries should be verified)propagating/obbt/{itlimitfactorbilin,minnonconvexity,createbilinineqs}
propagating/vbounds/minnewcliques
to specify the minimum number of new cliques to trigger another clique table analysispropagating/vbounds/{maxcliquesmedium,maxcliquesexhaustive}
to limit the number of cliques relative to the number of binary variable for performing clique table analysisseparating/maxincrounds
separating/maxlocalbounddist
,separating/maxcoefratio
andseparating/intsupportfac
- if PaPILO >= 2.1:
presolving/milp/maxbadgesizepar
to limit the maximal badge size if PaPILO is called in parallel mode - if PaPILO >= 2.1:
presolving/milp/maxbadgesizeseq
to limit the maximal badge size if PaPILO is called in sequential mode
Data structures
- new type
SCIP_Shortbool
(equal to uint8_t) for storing Boolean values in a more compact manner - new disjoint set data structure
SCIP_DISJOINTSET
to incrementally update connectedness information for a graph on nodes {0,...,n-1} - new red black tree data structure defined in
src/scip/rbtree.{c,h}
- new object
SCIP_LINCONSSTATS
, see type_cons.h, to work with linear constraint classification through the C API - added new type
SCIP_TABLE
together with callbacks to output SCIP statistics
Unit tests
- added several tests for the LP interface
- added tests that cover nonempty linear constraint classification types
- added tests for the double double arithmetic, the new red black tree data structure, the nlpi, obbt, interval arithmetics, symmetry computation, objective function changes in probing, computing envelopes of bilinear function, relaxation enforcement
Build system
- added interface to the NLP solver WORHP; set
WORHP=true
in order to link to WORHP - added interface to the NLP solver FilterSQP; set
FILTERSQP=true
in order to link to FilterSQP
Cmake
- added support for sanitizers in debug mode and options SANITIZE_ADDRESS, SANITIZE_MEMORY, SANITIZE_UNDEFINED, SANITIZE_THREAD
- added option SYM to specify which graph automorphism package (bliss, none) should be used, if available
- disable non-standard compliant floating point optimizations in combination with intel compilers
- improve Visual Studio compilation
- only accept IPOPT version 3.12.0 or higher
- preserve correct rpath in library (e.g. path to libipopt) when installing
Makefile
- new flag
DEBUGSOL={true,false}
to enable checks against a user given debug solution - added flag SYM to specify which graph automorphism package (bliss, none) should be used
- default value for ZIMPL in the Makefile is now
false
Fixed bugs
- fix wrong statistic display of diving leaf solutions
- fixed order of SCIPcalcCliquePartition() in corner case where no cliques are available
- fix treatment of infinite lower bound in proximity objective cutoff
- fixed minor issue in expression graph simplification
- Separator:
- fix linear knapsack relaxation during separation if a binary variable does not have a solution value in [0,1].
- fixed potential ressource leaks in SCIPsolveLinearProb(), expr.c, sepa_eccuts, cons_cumulative.c, cons_nonlinear.c
- fixed bug in cons_orbitope.c, where wrong terminating index in separation of SCIs was used
- fixed wrong mapping of permuted basis indices in gomory separator
- fixed integer objective separator for objective scales < 1
- Presolver:
- fixed numerical issues in boundshift presolver when aggregating integer variables
- fixed aggregation of variables in boundshift presolver that contain large variable bounds
- Heuristic:
- fixed bug in feasibility pump heuristic when switching on the
usefp20
parameter - fixed handling of LOOSE variables in locks heuristic
- fixed creation of conflicts in clique heuristic for incomplete LPs
- fixed bug in feasibility pump heuristic when switching on the
- Constraints:
- fixed bug in mps reader. Reader now prints
OBJSENSE
section and tries to generate unique names of constraints - fixed upgrade to a varbound constraint if abspower constraint contains a multi-aggregated variable
- fixed several bugs related to hashing of constraints/rows in cutpool.c and cons_linear.c
- fixed registration of almost fixed nonlinear variables in abspower constraints
- fixed bug in mps reader. Reader now prints
- Propagator:
- fixed releasing of variables in the genvbounds propagator in case the problem could be solved during presolving of a restart
- fixed numerical issues in bound widening of variable bound constraint handler and vbound propagator during conflict analysis