SCIP 5.0.1

Features

allow output of lower bounds for visualization
added symmetry detection for linking constraints
SCIP executable handles the SIGTERM signal. If the process receives a SIGTERM, SCIP terminates the solution process with a new SCIP_STATUS code "SCIP_STATUS_TERMINATE" and displays all relevant statistics before exiting.
add number of conflict constraints found by diving heuristics to statistics

Performance improvements

increased threshold when to scale up cuts that are generated by nonlinear constraint handlers
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)
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

methods SCIPtryTerminate() and SCIPterminated() in scip/interrupt.h for handling of SIGTERM signals.
SCIPselectCuts() to run SCIP's cut selection procedure on a given array of cuts

Changed parameters

rename parameter "constraints/orbisack/orbisack/coverseparation" to "constraints/orbisack/coverseparation"

New parameters

"visual/displb" that enables output of lower bounds for visualization
"presolving/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 calculation
"separating/dircutoffdistfac" to change the weight of the directed cutoff distance in cut score calculation

Data structures

new SCIP_STATUS code "SCIP_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 wrong cast in LP iteration limit computation in proximity search heuristic
fixed check for time limit in heur_nlpdiving
fixed LP status to unsolved when marking LP to be resolved if objective limit has changed
improved numerics and fixed stop criterion in zirounding heuristic
fixed treatment of variable aggregations in knapsack constraint handler that led to wrong propagations
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
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 bug with NULL pointer handling in LPIs
fixed handling of infinite bounds in cons_sos1
fixed bug while scaling linear constraints
don't delete conflict constraints that were transformed into model constraints during a restart

SCIP 5.0.0

Features

add new heuristic MPEC that solves a MPEC reformulation of a mixed-binary nonlinear problem by regularized NLP reformulations
new numerical solution violations get printed when checksol is called
three bandit selection algorithms to face sequential decision problems under uncertainty
new primal heuristic ALNS that orchestrates eight different LNS heuristics adaptively using algorithms for the multi-armed bandit problem
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
SCIP can now automatically detect and compute symmetries in MIPs (if a graph automorphism code is linked in)
added presol_symmetry.c for computing and storing symmetry information of a MIP
added new propagator orbital fixing
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
added presol_symbreak.c to detect special symmetry structures and to add symmetry handling constraints
cons_orbitope.c can now handle full orbitopes as well
utilizing linear inequalities to compute stronger linearizations for bilinear terms; the inequalities are computed in the OBBT propagator
added macros to do computations with a higher precision by using double-double arithmetic
added API for aggregating rows for generating cuts which uses double-double arithmetic internally
added filtering of parallel cuts in the cut pool
extended conflict analysis by analyzing dual solutions of boundexceeding LPs
revised internal debugging mechanism to check against a user given debug solution (debug.h)
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

Performance improvements

new implementation of zerohalf separator
enabled cutting plane separation in the tree
improved selection of rows in CMIR aggregation heuristic
generate lifted flowcover cuts in CMIR cut generation heuristic
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
use LP solution polishing during probing and diving mode to activate it during many primal heuristics; remains disabled during strong branching and OBBT
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
faster implementation of CMIR cut generation heuristic
improved cut selection and management
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
improved cut post-processing: apply coefficient tightening, enforce maximal dynamism
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 parameter "allowlocal" for SEPAEXEC{LP,SOL} callbacks to switch generation of locally valid cuts
added parameter "dstatssize" to NLPIDELVARSET and NLPIDELCONSSET callbacks of NLPIs
added parameter "objval" to the NLPIGETSOLUTION callback of NLPIs for returning the optimal objective value (can be set to NULL)

Deleted and changed API methods

generalized SCIPcreate{Cons,ConsBasic}Orbitope() method to three orbitope types (full, partitioning, packing)
return type of SCIPcliqueGetId() changed from int to unsigned int
SCIPnlpStatisticsCreate() and SCIPnlpStatisticsFree() now require a pointer to blockmemory as argument
changed function signature of SCIPcalcMIR()
changed function signature of SCIPcalcStrongCG()
removed argument "includeslp" from SCIPrelaxCreate() and added it to SCIPmarkRelaxSolValid(), SCIPsetRelaxSolVals() and SCIPsetRelaxSolValsSol(); removed functions SCIPrelaxIncludesLp() and SCIPrelaxSetIncludesLp()
removed parameter "scaling" from SCIPgetRowprepViolation()
removed parameter "allowaddcons" from SCIPselectVarPseudoStrongBranching(), SCIPselectVarStrongBranching(), and SCIPincludeBranchruleRelpscost()
SCIPheurPassIndicator() has a new parameter which allows to pass the objective of the solution
added parameter for statistics tables to SCIPcopyPlugins()
added parameter "objval" to SCIPnlpiGetSolution() of NLPIs for returning the optimal objective value (can be set to NULL)
added argument "varnameslength" to SCIPexprParse()
deprecated SCIPaddCut(), use SCIPaddRow() instead
SCIPsolveParallel() has been deprecated, use the new method SCIPsolveConcurrent() instead
replaced method SCIPgetRelaxFeastolFactor() by SCIPrelaxfeastol() and added SCIPchgRelaxfeastol()
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

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
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
new interface methods SCIPcreateRandom(), SCIPfreeRandom() that replace SCIPrandomCreate() and SCIPrandomFree() in the public SCIP API
new interface methods SCIPcreateDigraph(), SCIPcopyDigraph() that replace SCIPdigraphCreate() and SCIPdigraphCopy() in the public SCIP API
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
SCIPcliqueGetIndex() which returns the unique identifier for the given clique
SCIPgetNCliquesCreated() which returns the number of cliques created so far
SCIPsetSubscipDepth() to set the depth of SCIP as a copied subproblem during problem stage
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
SCIPgetSepaMinEfficacy() to access separating/minefficacy(root)
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
SCIPisCutNew() that returns whether a cut is already present in the global cut pool
SCIPsetSlackVarUb() to control upper bound of slack variable in cons_indicator

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 and SCIP_LPPAR_UOBJLIM by SCIP_LPPAR_OBJLIM
dropped support for MOSEK <lt; 7.0.0.0

Changed parameters

changed and removed several parameters for zerohalf separator
fixed typo "heuristics/completesol/maxunkownrate" has changed to "heuristics/completesol/maxunknownrate"
replaced parameter "heuristics/{clique,vbounds}/minfixingrate" by "heuristics/{clique,vbounds}/minintfixingrate" and "heuristics/{clique,vbounds}/minmipfixingrate", which check the fixing rate before LP solving and after sub-MIP presolve
replaced "constraints/quadratic/disaggregate" by "constraints/quadratic/maxdisaggrsize" to bound the total number of created constraints when disaggregating a quadratic constraint
parameter "separating/maxstallrounds" only applies to nodes in the tree (not the root node, anymore); use the new parameter "separating/maxstallroundsroot" for the root node
new value 3 for parameter "lp/solutionpolishing" to enable LP polishing only during probing and diving mode
parameter "conflict/useboundlp" has new values 'd' (only dual solution analysis) and 'b' (both, conflict and dual solution analysis)
moved parameters for flowcover and cmir separators to "separating/aggregation"
removed parameters "constraints/{abspower,bivariate,nonlinear,quadratic,soc}/scaling"
removed parameters "constraints/{abspower,bivariate,quadratic,nonlinear}/mincutefficacysepa", "constraints/{abspower,bivariate,quadratic,nonlinear}/mincutefficacyenfofac" and "constraints/soc/minefficacy"
removed parameters "conflict/usemir" and "conflict/prefermir"
removed parameters "heuristics/clique/{multiplier,initseed}"
removed parameter "separating/feastolfac"
removed parameter "separating/orthofac"
removed parameter "separating/cgmip/allowlocal" (use parameter passed to separation callback instead)
removed parameter "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 cuts
"constraints/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 always SCIP_FEASIBLE)
"constraints/orbitope/checkpporbitope" (check packing/partitioning orbitopes)
"constraints/orbitope/sepafullorbitope" (separate full orbitopes)
"constraints/orbitope/checkalwaysfeas" (whether conscheck returns always SCIP_FEASIBLE)
"constraints/quadratic/{usebilinineqbranch,minscorebilinterms,bilinineqmaxseparounds}"
"constraints/quadratic/disaggrmergemethod" to change the strategy of how to merge independent blocks of quadratic constraints
"constraints/quadratic/mincurvcollectbilinterms" to change the minimal curvature of constraints to be considered when returning bilinear terms to other plugins
"constraints/quadratic/binreformbinaryonly" to disable reformulation of products of binary and non-binary variables
"constraints/symresack/ppsymresack" (check whether symresacks can be strengthend by packing/partitining constraints)
"constraints/symresack/checkalwaysfeas" (whether conscheck returns always SCIP_FEASIBLE)
"expbackoff" to all separators which increases the frequency exponentially over the depth in the tree
"heuristics/completesol/{beforepresol,maxlpiter,maxcontvars}"
"heuristics/{clique,vbounds}/maxbacktracks" to limit the number of backtracks in the fix-and-propagate phase
"heuristics/{clique,vbounds}/uselockfixings" to enable fixing of additional variables based on variable locks
"heuristics/vbounds/{feasvariant,tightenvariant} to specify the fixing variants used by the vbounds heuristic
"lp/refactorinterval" to change the refactorization interval of the LP solver
"misc/debugsol" to specify a debug solution that should be checked during the solve
"misc/usesymmetry" to determine whether symmetry handling should be used
"presolving/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 analysis
"propagating/vbounds/{maxcliquesmedium,maxcliquesexhaustive}" to limit the number of cliques relative to the number of binary variable for performing clique table analysis
"separating/maxincrounds"
"separating/maxlocalbounddist", "separating/maxcoefratio" and "separating/intsupportfac"

Data structures

new object SCIP_LINCONSSTATS, see type_cons.h, to work with linear constraint classification through the C API
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}

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
fix linear knapsack relaxation during separation if a binary variable does not have a solution value in [0,1].
fixed bug in feasibility pump heuristic when switching on the usefp20 parameter
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 order of SCIPcalcCliquePartition in corner case where no cliques are available
fixed bug in mps reader. Reader now prints OBJSENSE section and tries to generate unique names of constraints
fixed handling of LOOSE variables in locks heuristic
fixed upgrade to a varbound constraint if abspower constraint contains a multi-aggregated variable
fixed numerical issues in boundshift presolver when aggregating integer variables
fixed minor issue in expression graph simplification
fixed several bugs related to hashing of constraints/rows in cutpool.c and cons_linear.c
fixed aggregation of variables in boundshift presolver that contain large variable bounds
fixed releasing of variables in the genvbounds propagator in case the problem could be solved during presolving of a restart
fix treatment of infinite lower bound in proximity objective cutoff
fixed wrong mapping of permuted basis indices in gomory separator
fixed integer objective separator for objective scales <lt; 1
fixed registration of almost fixed nonlinear variables in abspower constraints
fixed creation of conflicts in clique heuristic for incomplete LPs
fixed numerical issues in bound widening of variable bound constraint handler and vbound propagator during conflict analysis