Release notes for SCIP 6.0

SCIP 6.0.1

Features

• when using a debug solution every (multi-)aggregation will be checked w.r.t. this solution

Performance improvements

• try greedy solution first before solving knapsack exactly using dynamic programming in SCIPsolveKnapsackExactly, compute greedy solution by weighted median selection.

Interface changes

Deleted and changed API methods and macros

• The preprocessor macro NO_CONFIG_HEADER now needs to be defined when including SCIP header files from a SCIP build or installation that has been build via the Makefile-only build system.
• The following preprocessor macros have been renamed: WITH_ZLIB to SCIP_WITH_ZLIB, WITH_GMP to SCIP_WITH_GMP, WITH_READLINE to SCIP_WITH_READLINE, NO_SIGACTION to SCIP_NO_SIGACTION, NO_STRTOK_R to SCIP_NO_STRTOK_R, ROUNDING_FE to SCIP_ROUNDING_FE, ROUNDING_FP to SCIP_ROUNDING_FP, ROUNDING_MS to SCIP_ROUNDING_MS. Note, however, that the names of macros NO_RAND_R and NO_STRERROR_R have not been changed so far.

New API functions

• SCIPhashmapInsertInt(), SCIPhashmapSetImageInt(), and SCIPhashmapGetImageInt() to use integer values as images in hashmaps

Command line interface

• warn about coefficients in MPS files with absolute value larger than SCIP's value for infinity

Changed parameters

• default clock type for timing is now wallclock

Unit tests

• added unit tests for exact knapsack solving and (weighted) median selection algorithms

Build system

Cmake

• add missing GMP dependency when compiling with SYM=bliss
• add DL library when linking to CPLEX to avoid linker errors
• new config.h header defining the current build configuration, e.g. SCIP_WITH_GMP

Fixed bugs

• fixed handling of weights in cons_sos1 and cons_sos2 (NULL pointer to weights)
• fixed handling of unbounded LPs in SCIP and in several LPIs; added heuristic method to guess solution
• the STO reader is capable of handling scenarios defined using lower case "rhs"
• fixed OPB reader for instances without explicit plus signs
• correct dual solution values for bound constraints
• fixed recognition of variable with only one lock in cons_bivariate, cons_quadratic, and cons_nonlinear
• fixed update of constraint violations in solution repair in cons_bivariate, cons_quadratic, and cons_nonlinear
• print error message and terminate if matrix entries of a column are not consecutive in mps format
• fixed incorrect handling of fixed variables when transfer of cuts from LNS heuristic for Benders' decomposition
• fix returning local infeasible status by Ipopt interface if Ipopt finds problem locally infeasible
• skip attempt to apply fixings in linear constraint handler during solving stage as LP rows cannot change anymore
• fixed bug when reading >= indicator constraints in MPS format
• fix issue with nodes without domain changes if we ran into solution limit in prop_orbitalfixing
• fixed unresolved reference to CppAD's microsoft_timer() function on builds with MS/Intel compilers on Windows
• ignore implications added through SCIPaddVarImplication() that are redundant to global bounds also in the special case of an implication between two binary variables; also, use implications instead of cliques in the case of a binary implied variable with nonbinary active representative
• fixed bug with aggregated variables that are aggregated in propagation of cons_sos1
• fixed some special cases in SCIPselect/SCIPselectWeighted methods
• relaxed too strict assertion in Zirounding heuristic
• fixed the upgrade routine to XOR constraints: aggregate integer variable if its coefficient has the wrong sign
• fixed handling of nonartificial parity variables when deleting redundant XOR constraints
• earlier deletion of trivial XOR constraints (at most 1 operator left)
• fixed wrong hashmap accesses and added sanity check for the correct hashmap type
• avoid copying of unbounded solutions from sub-SCIPs as those cannot be checked completely
• corrected the output of the first LP value in case of branch-and-price

Miscellaneous

• do not scale linear constraints to integral coefficients

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 SCIPgetGeneratorsSymmetry() 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 parameters:
  • heuristics/alns/stallnodefactor as the stall nodes are now controlled directly by the target node limit within the heuristic
  • presolving/symmetry/computepresolved since this presolver does not compute symmetries independent of other components anymore
  • 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/<decompname>/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