SCIP 6.0.0

Features

new diving heuristic farkasdiving that dives into the direction of the pseudosolution and tries to construct Farkas-proofs
new diving heuristic conflictdiving that considers locks from conflict constraints
restructuring of timing of symmetry computation that allows to add symmetry handling components within presolving
"lp/checkstability" is properly implemented for SoPlex LPI (spx2)
new branching rule lookahead that evaluates potential child and grandchild nodes to determine a branching decision
limits on the number of presolving rounds a presolver (maxrounds) or propagator/constraint handler (maxprerounds) participates in are now compared to the number of calls of the particular presolving method, not the number of presolving rounds in general, anymore
new miscellaneous methods for constraints that have a one-row linear representation in pub_misc_linear.h
a Benders' decomposition framework has been added. This framework provides the functionality for a user to solve a decomposed problem using Benders' decomposition. The framework includes classical optimality and feasibility cuts, integer optimality cuts and no-good cuts.
add statistic that presents the number of resolves for instable LPs
new readers for stochastic programming problems in SMPS format (reader_sto.h, reader_smps.h)

Performance improvements

cuts generated from certain quadratic constraints with convex feasible region are now global
performance improvements for Adaptive Large Neighborhood Search heur_alns.c:
- all neighborhoods now start conservatively from maximum fixing rate
- new default parameter settings for bandit selection parameters
- no adjustment of minimum improvement by default
improved bound tightening for some quadratic equations
constraint handler checking order for original solutions has been modified to check those with negative check priority that don't need constraints after all other constraint handlers and constraints have been checked
deactivate gauge cuts

Examples and applications

new example "brachistochrone" in CallableLibrary examples collection; this example implements a discretized model to obtain the trajectory associated with the shortest time to go from point A to B for a particle under gravity only
new example "circlepacking" in CallableLibrary examples collection; this example models two problems about packing circles of given radii into a rectangle
new price-and-branch application for the ringpacking problem
new stochastic capacitated facility location example demonstrating the use of the Benders' decomposition framework

Interface changes

New and changed callbacks

added parameter locktype to SCIP_DECL_CONSLOCK callback to indicate the type of variable locks

Deleted and changed API methods

Symmetry
- removed function SCIPgetTimingSymmetry() in presol_symmetry.h since this presolver does not compute symmetries independent of other components anymore
- additional argument "recompute" to SCIPgetGeneratorsSymmetyr() to allow recomputation of symmetries
Random generators
- the seed of SCIPinitializeRandomSeed() is now an unsigned int
- the seed of SCIPsetInitializeRandomSeed() is now an unsigned int and it returns an unsigned int
- new parameter for SCIPcreateRandom() to specify whether the global random seed shift should be used in the creation of the random number generator
Miscellaneous
- additional arguments "preferrecent", "decayfactor" and "avglim" to SCIPcreateBanditEpsgreedy() to choose between weights that are simple averages or higher weights for more recent observations (the previous default). The last two parameters are used for a finer control of the exponential decay.
- functions SCIPintervalSolveUnivariateQuadExpression(), SCIPintervalSolveUnivariateQuadExpressionPositive(), and SCIPintervalSolveUnivariateQuadExpressionPositiveAllScalar() now take an additional argument to specify already existing bounds on x, providing an entire interval ([-infinity,infinity]) gives previous behavior

New API functions

SCIPintervalSolveUnivariateQuadExpressionNegative()
SCIPvarGetNLocksDownType() and SCIPvarGetNLocksUpType()
SCIPaddConsLocksType()
SCIPconsIsLockedTypePos(), SCIPconsIsLockedTypeNeg(), SCIPconsIsLockedType(), SCIPconsGetNLocksTypePos() and SCIPconsGetNLocksTypeNeg()
SCIPstrncpy(), a safe version of strncpy()

Changed parameters

removed parameter "heuristics/alns/stallnodefactor" as the stall nodes are now controlled directly by the target node limit within the heuristic
removed parameter "presolving/symmetry/computepresolved" since this presolver does not compute symmetries independent of other components anymore
removed parameter "separating/maxincrounds"

New parameters

"lp/checkfarkas" that enables the check of infeasibility proofs from the LP
"heuristics/alns/unfixtol" to specify tolerance to exceed the target fixing rate before unfixing variables, (default: 0.1)
"propagating/orbitalfixing/symcomptiming" to change the timining of symmetry computation for orbital fixing
"lp/alwaysgetduals" ensure that the dual solutions are always computed from the recent LP solve
"display/relevantstats" indicates whether the small relevant statistics are displayed at the end of solving
"propagating/orbitalfixing/performpresolving" that enables orbital fixing in presolving
"presolving/symbreak/addconsstiming" to change the timining of symmetry computation for symmetry handling inequalities
"propagating/orbitalfixing/enabledafterrestarts" to control whether orbital fixing is enabled after restarts
"benders/∗" new submenu for Benders' decomposition related settings. This includes the settings related to the included Benders' decompositions and the general Benders' decomposition settings.
"benders/<lt;decompname>gt;/benderscuts/∗" submenu within each included Benders' decomposition to control the Benders' decomposition cuts. The cuts are added to each decomposition separately, so the setting are unique to each decomposition.

Data structures

new enum SCIP_LOCKTYPE to distinguish between variable locks implied by model (check) constraints (SCIP_LOCKYPE_MODEL) and variable locks implied by conflict constraints (SCIP_LOCKYPE_CONFLICT)
expression interpreter objects are now stored in the block memory

Deleted files

removed presolving plugin presol_implfree
separated scip.c into several smaller implementation files scip_*.c for better code overview; scip.c was removed, but the central user header scip.h remains, which contains includes of the separated headers

Fixed bugs

fixed bug in gcd reductions of cons_linear regarding an outdated flag for variable types
fixed bug in heur_dualval regarding fixing routine for integer variables
suppress debug solution warnings during problem creation stage
fixed check for activated debugging solution in components constraint handler
fixed potential bug concerning solution linking to LP in SCIPperformGenericDivingAlgorithm()
fixed reward computation in ALNS on continuous, especially nonlinear, problems
fixed bug in freeing reoptimization data if problem was solved during presolving
fixed check of timing in heur_completesol
fixed wrong propagation in optcumulative constraint handler
fixed non-deterministic behavior in OBBT propagator
don't disable LP presolving when using Xpress as LP solver
fixed possible NULL pointer usage in cons_pseudoboolean
ensured that SCIPgetDualbound() returns global dual bound instead of the dual bound of the remaining search tree
fixed rare division-by-zero when solving bivariate quadratic interval equation
use total memory for triggering memory saving mode
fix parsing of version number in the CMake module for Ipopt
fixed handling of implicit integer variables when attempting to solve sub-MIP in nlpdiving heuristic
added workaround for bug when solving certain bivariate quadratic interval equations with unbounded second variable
fixed bug with releasing slack variable and linear constraint in cons_indicator
fixed problem when writing MPS file with indicator constraints with corresponding empty linear constraints
fixed bug in heur_vbound triggered when new variables were added while constructing the LP
fixed bug with unlinked columns in SCIProwGetLPSolCutoffDistance()

Miscellaneous

updated CppAD to version 20180000.0
remove LEGACY mode, compiler needs to be C++11-compliant