Release notes for SCIP 5

# SCIP 5.0.1

## Features

- 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
- 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`

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 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`

to`SCIP_DECL_NLPIGETSOLUTION`

for returning the optimal objective value (can be set to`NULL`

)

- added parameter
- Separation callbacks:
- added parameter
`allowlocal`

to`SCIP_DECL_SEPAEXECLP`

and`SCIP_DECL_SEPAEXECSOL`

to switch generation of locally valid cuts - added parameter
`dstatssize`

to`SCIP_DECL_NLPIDELVARSET`

and`SCIP_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`

and`SCIP_LPPARAM_UOBJLIM`

by`SCIP_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 to`NULL`

) - 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`

to`unsigned int`

- 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`

and`SCIP_LPPAR_UOBJLIM`

by`SCIP_LPPAR_OBJLIM`

- dropped support for MOSEK < 7.0.0.0

### Changed parameters

- changed and removed several parameters for zerohalf separator
- replaced
`constraints/quadratic/disaggregate`

by`constraints/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 values`d`

(only dual solution analysis) and`b`

(both, conflict and dual solution analysis) - Heuristics:
- 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

- fixed typo
- Separating:
- 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 - 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 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`

- 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