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

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
• NLP interface:
  • dropped NLP termination status SCIP_NLPTERMSTAT_UOBJLIM
• NLP callbacks:
  • added parameter objval to SCIP_DECL_NLPIGETSOLUTION for returning the optimal objective value (can be set to NULL)
• 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

Deleted and changed API methods

• Branching rules:
  • removed parameter allowaddcons from SCIPselectVarPseudoStrongBranching(), SCIPselectVarStrongBranching(), and SCIPincludeBranchruleRelpscost()
• 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
• 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()
• 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

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