Solving Constraint Integer Programs

Release notes for SCIP 6.0

SCIP 6.0.0


  • 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

New API functions

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


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