Release notes for SCIP 9

SCIP 9.0.0

Features

• added simplification of abs(x)^n to x^n when n is even (simplify rule POW12)
• in expression simplification, added possibility to expand power of sum with exponents larger than 2 (simplify rule POW7)
• in expression simplification, added possibility to expand products with sums as factor when there are more than two factors (simplify rule SP12b)
• in expression simplification, added possibility to allow expanding power of products with fractional exponent (simplify rule POW5a)
• can now build with Lapack (used for solving nonlinear problems) explicitly; if IPOPT is used, then Lapack is accessed through it; an interface to Lapack is available in lapack_calls.h
• added support for logical constraints in binary variables and basic logical operators (and, or, not, equal) to AMPL .nl reader
• indicator constraints now use the same slack variable for the linear constraints if binary variables are used multiple times for indicator constraints
• new diving heuristic indicatordiving that focuses on indicator variables which control semicontinuous variables
• updated statistics on NLP relaxation; information on convexity of NLP has been added
• added new bandit method (EXP.3-IX) that is the new default of the ALNS heuristic
• added dialog to display recognized permutation symmetries ("display symmetry")
• The symmetry detection code has been completely restructured. Instead of completely encoding symmetry information in prop_symmetry.c, there is a new callback for constraint handlers, which returns symmetry relevant information by encoding a constraint as a node and edge colored graph. This way, also custom constraint handlers can provide symmetry information.
• added special presolving step for logicor and set covering/packing for constraints with two variables and one independent variable
• increased the depth field of the tree structure from 16 to 30 bits and the max depth of the search tree from 65534 to 1073741822
• added new cut selector plugin called cutsel_ensemble. Performs a superset of hybrid cutsel. Implements new filtering methods and scoring options.
• added new branching rule based on Gomory mixed-integer cuts
• added new branching score to the reliability pseudo-cost branching rule
• added new cut selector plugin called cutsel_dynamic. Performs a superset of hybrid cutsel. Implements new filtering methods and scoring options.
• added monoidal strengthening to intersection cut generation of nlhdlr_quadratic
• extended heuristic dps to run after processing the node and to use strict limits for the reoptimization step
• extended obbt propagator to handle variables of the linear constraints corresponding to indicator constraints
• added new heuristic heur_scheduler that models the selection of LNS and diving heuristics as a multi-armed bandit problem
• added nonlinear handler for signomial expressions: adds cuts based on a difference of convex functions representation
• Delayed separators are now called if no other cuts have been found. Previously, such separators were only called near stalling or when the separation rounds limit was reached.
• added a new separator sepa_lagromory to generate Lagromory cuts in a relax-and-cut framework, i.e., GMI cuts generated at different bases that are explored in the process of solving the Lagrangian dual problem at a node. This separator is OFF by default.
• when parsing nonlinear constraints from CIP files, the * after the number in a term is now optional if followed by a variable, i.e., instead of 3*<x><y>, now also 3<x><y> can be read, but 3<x><y> is not supported; this allows to read some CIP files that were written with SCIP < 8
• when running bliss, we now limit the number of actually created generators and not the ones considered by bliss

Performance improvements

• Variable conflict-based addition of Schreier-Sims cuts for symmetry handling in prop_symmetry.c does no longer use an expensive explicit conflict graph construction.
• Only run propagation of indicator constraints if relevant variables have changed.
• Propagation of indicator constraints propagates maximal activity of linear constraint to upper bound of slack variable.
• Added initialization of LP relaxation for SOC constraints.
• Avoided some numerical issues when separating SOC constraints.
• If differentation of convex expression fails in convex nlhdlr, then a perturbed point is tried.
• Use sassy/bliss as default symmetry computation package.
• No longer linearize indicator constraints in undercover heuristic by default.
• Deactivate pre-root heuristic zeroobj in undercover heuristic.
• Added new branching score tiebreaker for reliability pseudo-cost branching rule
• Try nearest bound if zero solution value is out of bounds in heuristic trivial.

Examples and applications

Interface changes

New and changed callbacks

• Added solution linearization callback for nonlinear handlers. The nonlinear handler may use this callback to add tight cuts that use the given solution as reference point to the cutpool. The callback is called if option constraints/nonlinear/linearizeheursol is enabled.
• The callback for copying problem data SCIP_DECL_PROBCOPY() now has a parameter "original" indicating whether the original or transformed problem should be copied. Similarly, SCIPprobCopy() in prob.h/c has such a parameter.
• Added CONSGETPERMSYMGRAPH and CONSGETSIGNEDPERMSYMGRAPH callback for constraint handlers, which provides symmetry information about constraints to SCIP.

Deleted and changed API methods

• SCIPtpiInitLock(), SCIPtpiDestroyLock(), SCIPtpiInitCondition(), SCIPtpiDestroyCondition() now take a double pointer to SCIP_LOCK/SCIP_CONDITION, respectively.
• Renamed SCIPtpiSumbitJob() to SCIPtpiSubmitJob().
• SCIPcreateConsIndicatorLinCons(), SCIPcreateConsIndicatorGenericLinCons() do not allow binvar to be NULL anymore
• Replaced SCIPnlrowSetCurvature() by SCIPsetNlRowCurvature().
• SCIPsnprintf() now returns the required string length in case reallocation is necessary.
• SCIPcomputeCoverUndercover() receives three more arguments which nonlinearities to cover
• removed definition of SQRT
• SCIPincludeObjConshdlr(), SCIPincludeConshdlr(), SCIPconshdlrCreate() receive two more arguments for the conshdlr callbacks CONSGETPERMSYMGRAPH and CONSGETSIGNEDPERMSYMGRAPH
• removed SYM_VARTYPE, SYM_OPTYPE, SYM_CONSTTYPE, SYM_RHSTYPE, SYM_MATRIXDATA
• new parameter issigned for SCIPcomputeOrbitsSym()
• new parameter symtype for SCIPcomputeComponentsSym()
• new parameter symtype and permvardomaincenter for SCIPlexicographicReductionAddPermutation()
• replaced parameters matrixdata and exprdata of SYMcomputeSymmetryGenerators() by graph

New API functions

• new functions for interfacing with Lapack: SCIPlapackIsAvailable(), SCIPlapackIsAvailable(), SCIPlapackComputeEigenvalues(), and SCIPlapackSolveLinearEquations These functions should be used instead of SCIPisIpoptAvailableIpopt(), SCIPcallLapackDsyevIpopt(), and SCIPsolveLinearEquationsIpopt() in the context of computing eigenvalues or solving linear equations. If IPOPT is available, the calls will be passed on to Ipopt's interface to Lapack.
• SCIPmultiplyBySumExprSum(), SCIPpowerExprSum()
• SCIPsetParam()
• SCIPgetPrimalDualIntegral() returns the primal dual integral stored in the statistics
• new functions SCIPcreateConsIndicatorLinConsPure() and SCIPcreateConsIndicatorGenericLinConsPure() that create indicator constraints from a linear constraint without a slack variable
• SCIPgetNLPNlRowsStat() to retrieve counts on linear, convex, and nonconvex rows in NLP
• SCIPnlhdlrSetSollinearize(), SCIPnlhdlrHasSollinearize()
• SCIPbendersGetNLPParam()
• new API functions SCIPlexicographicReductionGetStatistics(), SCIPlexicographicReductionPrintStatistics(), SCIPlexicographicReductionPropagate(), SCIPlexicographicReductionAddPermutation(), SCIPlexicographicReductionReset(), SCIPlexicographicReductionFree(), SCIPincludeLexicographicReduction(), for lexicographic reduction.
• new API functions SCIPorbitopalReductionGetStatistics(), SCIPorbitopalReductionPrintStatistics(), SCIPorbitopalReductionPropagate(), SCIPorbitopalReductionAddOrbitope(), SCIPorbitopalReductionReset(), SCIPorbitopalReductionFree(), SCIPincludeOrbitopalReduction(), SCIPorbitopalReductionGetDefaultColumnOrdering(), for orbitopal fixing.
• new API functions SCIPorbitalReductionGetStatistics(), SCIPorbitalReductionPrintStatistics(), SCIPorbitalReductionPropagate(), SCIPorbitalReductionAddComponent(), SCIPorbitalReductionReset(), SCIPorbitalReductionFree(), SCIPincludeOrbitalReduction(), for orbital fixing.
• new API functions SCIPgetShadowTreeEventHandlerExecutionTime(), SCIPshadowTreeGetShadowNodeFromNodeNumber(), SCIPshadowTreeGetShadowNode(), SCIPgetShadowTree(), SCIPactivateShadowTree(), SCIPincludeEventHdlrShadowTree(), for managing a copy of the branch-and-bound tree for symmetry handling purposes.
• SCIPdotWriteOpening(), SCIPdotWriteNode(), SCIPdotWriteArc(), SCIPdotWriteClosing()
• SCIPincludeCutselEnsemble(), SCIPselectCutsEnsemble() to include cutsel_ensemble or use the selection algorithm
• SCIPincludeBranchruleGomory() includes new gomory cut based branching rule
• SCIPgetVarAvgGMIScore(), SCIPincVarGMISumScore(), SCIPgetVarLastGMIScore(), SCIPsetVarLastGMIScore() set historical values used by SCIP's default branching rule
• SCIPincludeNlhdlrSignomial() includes the signomial nonlinear handler
• SCIPgetExprMonomialData() returns a monomial representation of a product expression
• SCIPestimateRoot() computes estimators for roots with exponent in [0,1]
• SCIPincludeCutselDynamic(), SCIPselectCutsDynamic() to include cutsel_dynamic or use the selection algorithm
• SCIPincludeSepaLagromory() to include the new Lagromory separator
• SCIPconsCompCheck() to compare two constraints based on their check priority
• SCIPgetConsPermsymGraph() and SCIPgetConsSignedPermsymGraph() to access the (signed) permutation symmetry detection graph of a constraint
• SCIPsetConshdlrGetPermsymGraph() and SCIPsetConshdlrGetSignedPermsymGraph() to set the (signed) permutation symmetry detection graph of a constraint
• SCIPconshdlrSupportsPermsymDetection() and SCIPconshdlrSupportsSignedPermsymDetection() to access whether a conshdlr supports detection of (signed) permutation symmetries
• new API functions for creating and manipulating a symmetry detection graph: SCIPcreateSymgraph(), SCIPfreeSymgraph(), SCIPcopySymgraph(), SCIPextendPermsymDetectionGraphLinear(), SCIPaddSymgraphVarAggregation(), SCIPaddSymgraphOpnode(), SCIPaddSymgraphValnode(), SCIPaddSymgraphConsnode(), SCIPgetSymgraphVarnodeidx(), SCIPgetSymgraphNegatedVarnodeidx(), SCIPupdateSymgraphLhs(), SCIPupdateSymgraphRhs(), SCIPfixSymgraphVarnode(), SCIPaddSymgraphEdge(), SCIPcomputeSymgraphColors(), SCIPgetSymgraphSymtype(), SCIPgetSymgraphVars(), SCIPgetSymgraphNVars(), SCIPgetSymgraphNConsnodes(), SCIPgetSymgraphNNodes(), SCIPgetSymgraphNEdges(), SCIPgetSymgraphEdgeFirst(), SCIPgetSymgraphEdgeSecond(), SCIPgetSymgraphVarnodeColor(), SCIPgetSymgraphNodeType(), SCIPgetSymgraphNodeColor(), SCIPisSymgraphEdgeColored(), SCIPgetSymgraphEdgeColor(), SCIPgetSymgraphNVarcolors(), SCIPhasGraphUniqueEdgetype(), SCIPallocateSymgraphConsnodeperm(), SCIPcreateSymgraphConsnodeperm(), SCIPgetSymgraphConsnodeperm(), SCIPfreeSymgraphConsnodeperm(), SCIPgetSymActiveVariables(), SCIPfreeSymDataExpr(), SCIPgetSymExprdataNConstants(), SCIPgetSymExprdataConstants(), SCIPgetCoefSymData(), SCIPcreateSymOpNodeType(), SCIPgetSymOpNodeType()
• SCIPexprhdlrSetGetSymdata(), SCIPexprhdlrHasGetSymData(), SCIPgetSymDataExpr(), SCIPcallExprGetSymData() to access symmetry data of expressions
• SYMcheckGraphsAreIdentical() to check whether two symmetry detection graphs are identical
• new functions SYMbuildSassyGraph(), SYMbuildSassyGraphCheck()
• new type SYM_GRAPH
• new definitions SCIP_DECL_CONSGETPERMSYMGRAPH, SCIP_DECL_EXPRGETSYMDATA
• new member SYM_NODETYPE_CONS in SYM_NODETYPE enum
• new members SYM_CONSOPTYPE_SUM, SYM_CONSOPTYPE_SLACK, SYM_CONSOPTYPE_COEF, SYM_CONSOPTYPE_RHS, SYM_CONSOPTYPE_LAST in SYM_CONSOPTYPE enum
• new defintion SCIP_DECL_EXPRGETSYMDATA
• new function SCIPdetectSingleOrDoubleLexMatrices()

Command line interface

• Added optional parameter -i when calling SCIP in AMPL-mode (-AMPL parameter). If -i is specified, a SCIP shell is started where normally SCIPsolve() would be called.

Interfaces to external software

• added interface to nauty/traces for symmetry computation
• added interface to sassy, a preprocessor for symmetry computation
• The directory src/sassy contains the source code of sassy.
• Added interface to Lapack (used for solving nonlinear problems).
• The AMPL interface now supports parameters specified in AMPL command scripts via option scip_options. The value of scip_options is expected to be a sequence of parameter names and values, separated by a space, e.g., `option scip_options 'limits/time 10 display/verblevel 1';`. String values should not be quoted and spaces in string values are not supported.
• sassy can be used now as preprocessor for nauty/traces
• The solution status codes written to AMPL solution files now match those from https://mp.ampl.com/details.html#_CPPv4N2mp3sol6StatusE.

Changed parameters

• change default value of parameter separating/filtercutpoolrel to FALSE
• Shrunk range of parameter "propagating/symmetry/sstleaderrule" from [0,3] to [0,2], removed "MAXCONFLICTS"-option.
• Removed reading/gmsreader/freeints. A default upper bound of +inf is now assumed for integer variables in GAMS (which is the case since GAMS 23.1).
• Disabled "propagating/symmetry/symfixnonbinaryvars" since it is not used in the new symmetry code.
• Replaced "propagating/symmetry/onlybinarysymmetry" with "propagating/symmetry/enforcecomputesymmetry" and set to FALSE by default.
• Disabled "propagating/symmetry/performpresolving" since running orbital reduction during presolving is not effective.
• Repurposed "propagating/symmetry/usedynamicprop" since it now also applies to lexicographic reduction.
• Changed default value of parameter "propagating/symmetry/addsymresacks" from FALSE to TRUE.

New parameters

• separating/maxcutsgenfactor and separating/maxcutsrootgenfactor as factors (w.r.t. separating/maxcuts and separating/maxcutsroot) for limits on the number of cuts generated (which used to be constants '2')
• expr/pow/expandmaxexponent to specify limit on exponent when to expand power of sum
• expr/pow/distribfracexponent to enable expanding power of products with fractional exponents
• expr/product/expandalways to enable expanding any product with sums as factor (that is, also when more than two factors)
• nlhdlr/convex/maxperturb to specify maximal perturbation of non-differential reference points
• benders/default/nlpiterlimit to adjust iteration limit for NLP solver for Benders' decomposition NLP subproblems
• limits/objectivestop to interrupt the solve as soon as a primal solution is found that is at least as good as the given value
• heuristics/undercover/{coverand,coverind,covernl} to control which nonlinearities to consider (by default only "and" and nonlinear constraints)
• cutselection/ensemble/∗ all parameters for new ensemble cut selector
• cutselection/dynamic/∗ all parameters for new dynamic cut selector
• branching/relpscost/gmiavgeffweight specifies the weight in the relpscost branching score of the normalized efficacy of all generated GMI cuts (for a variable) branching/relpscost/gmilasteffweight specifies the weight in the elpscost branching score of the normalized efficacy of the last generated GMI cut (for a variable)
• nlhdlr/quadratic/usemonoidal to enable monoidal strengthening when separating quadratics with intersection cuts
• nlhdlr/quadratic/trackmore to collect more statistics for monoidal strengthening when separating quadratics with intersection cuts
• nlhdlr/quadratic/useminrep to use the minimal representation to compute cut coefficients when separating quadratics with intersection cuts
• nlhdlr/quadratic/sparsifycuts to enable sparsification of intersection cuts for quadratics
• heuristics/dps/reoptlimits to set strict limits for the reoptimization step in dps
• heuristics/dps/timing to run dps after processing the node
• heuristics/scheduler/∗ all parameters for new scheduler heuristic
• nlhdlr/signomial/enabled, nlhdlr/signomial/maxnundervars, nlhdlr/signomial/mincutscale: parameters for the signomial nonlinear handler
• separating/lagromory/freq to denote the frequency for calling Lagromory separator
• separating/lagromory/away to denote the minimal integrality violation of a basis variable to try separation
• separating/lagromory/dynamiccuts to denote whether the generated cuts be removed from LP if they are no longer tight
• separating/lagromory/maxroundsroot to denote the maximal number of separation rounds in the root node
• separating/lagromory/maxrounds to denote the maximal number of separation rounds in a non-root node
• separating/lagromory/nmaxcutsperlproot to denote, in the root node, the maximal number of Lagromory cuts that can be separated per explored basis of the Lagrangian dual
• separating/lagromory/nmaxcutsperlp to denote, in a non-root node, the maximal number of Lagromory cuts that can be separated per explored basis of the Lagrangian dual
• separating/lagromory/perroundnmaxlpiters to denote the maximal number of separating LP iterations that are allowed per separation round
• separating/lagromory/dualdegeneracyratethreshold to denote the minimum dual degeneracy rate for the separator execution
• separating/lagromory/varconsratiothreshold to denote the minimum variable-constraint ratio on the optimal face for the separator execution
• many other advanced parameters for the Lagromory separator, which are also mentioned under separating/lagromory/∗

Data structures

• new data structure SYM_GRAPH to encode symmetry information from a constraint
• new data structure SYM_EXPRDATA to encode symmetry information from expressions
• replaced enum SYM_SYMTYPE by a complete new one; removed SYM_RHSSENSE, added SYM_NODETYPE and SYM_CONSOPTYPE

Deleted files

• deleted the now unused files: tpi_none.h, tpi_openmp.h, tpi_tnycthrd.h, type_tpi_none.h, type_tpi_openmp.h, type_tpi_tnycthrd.h

Unit tests

• new unittests for nlhdlr_quadratic that test monoidal strengthening and the use of the minimal representation to compute cut coefficients
• unittests for nlhdlr_signomial

Testing

• changed set lim obj to set lim objective in ctest since obj is no longer unambiguous
• flush changes at the end of SCIPlpiSetBase() in lpi_grb.c to apply the newly set basis correctly

Build system

Cmake

• New flag -DLAPACK=on for linking with Lapack (must be available in the system)
• added flag option "SYM=sbliss" for using sassy/bliss as a graph automorphism package
• use SYM=sbliss by default, since sassy and bliss are now shipped with SCIP.
• added flag option "SYM=snauty" for using sassy/nauty as a graph automorphism package

Makefile

• added flag option "nauty" for SYM variable to specify which graph automorphism package should be used
• added flag option "sbliss" (sassy/bliss) for SYM variable to specify which graph automorphism package should be used
• added flag option "snauty" (sassy/nauty) for SYM variable to specify which graph automorphism package should be used
• use SYM=sbliss by default, since sassy and bliss are now shipped with SCIP
• New flag LAPACK for linking with Lapack (must be available in the system)
• A file scip/config.h is created in the build directory (/include) now. Defining NO_CONFIG_HEADER is no longer necessary and has no effect anymore.

Fixed bugs

• Number of runs in which separation is enabled will now be correct as per "separating/maxruns" parameter. Earlier, separation was enabled for "maxruns + 1" number of runs, i.e., separation was enabled even when "maxruns = 0" was set.
• add safeguard for number of selected cuts
• use double double precision for delta in activity updates of cons_linear.c
• sort constraints in checkSolOrig() to keep the logic of constraint handlers intact
• fixed make install when SHARED=no and make uninstall
• check absolute coefficients relative to extremal average to avoid invalid unifications in normalizeCons()
• enforce and check symmetry-based constraints to take their locks (in dual reductions) into account

Miscellaneous

• The TPI has been changed to become mostly independent from the actual parallel interface during compile time. For this, the locks and conditions are now pointers to abstract structs.
• fixed that scip/def.h, the header for C preprocessor definition (#define's), included headers for some SCIP type and function definitions (scip/type_retcode.h, scip/type_message.h, scip/pub_message.h)

Known bugs