SCIP 6.0.2

Features

The abspower constraint handler now passes more accurate convexity information to the NLP relaxation.

Examples and applications

added parsing functionality for optcumulative constraints in CIP format

Interface changes

Interfaces to external software

Updated the Mosek LP solver interface to support Mosek 9.0.

Build system

Cmake

new target to 'doc' to build documentation
ctests now fail if parameter file not found
add flag STATIC_GMP and improve GMP find module
remove non-API methods from library (API methods use new macro SCIP_EXPORT)
increase minimal required CMake version to 3.3
correct paths and dependency information when installing SCIP

Fixed bugs

fixed SCIP-Jack presolving bug that could lead to wrong results for Steiner arborescence problems
fixed wrong unboundedness result in case not all constraints were already in the LP and enforcement was skipped because an optimal solution was found
fixed wrong enforcement of constraints in the disjunction constraint handler
fixed wrong behavior of concurrent solve ignoring initial solutions
fixed bug in concurrent solve when problem was already solved in presolving
aggregate non-artificial integer variable for XOR constraints with two binary variables and delete constraint
copy the objective offset when copying the original problem
fixed bug in SCIPlpiGetBInvARow in lpi_cpx using wrong size of resulting vector
fixed quadratic runtime behavior in sepa_aggregation
fixed statistics of separators
improve numerical stability in varbound constraint handler by using double-double arithmetic
fixed bug in propagation of dual proofs
fixed bugs that arise for multiaggregated indicator variables by disallowing multiaggregation for them
improve numerical stability in SCIPcomputeBilinEnvelope* by using double-double arithmetic
fixed bug related to releasing pending bound changes in tree.c
set STD FENV_ACCESS pragma to on in code that changes floating-point rounding mode
disable GCC optimizations in main interval arithmetic code to prevent wrong optimizations
fixed wrong assert in cons_xor concerning the variable type
fixed different behavior of SCIPisLbBetter and SCIPisUbBetter between having NDEBUG defined or not
correctly handle bound disjunctions in symmetry detection
fixed issue in reliability branching related to the LP error flag not being reset
fixed treatment of near-infinite bounds in shiftandpropagate's problem transformation
fixed handling of infinite values in SCIPcomputeHyperplaneThreePoints()
fixed comparisons of infinite values in heur_intshifting.c and heur_shifting.c
fixed bug related to updating unprocessed cuts in the cutpool
fixed bug related to enabling quadratic constraints during CONSINITLP
add missing SCIP_EXPORT for functions used by GCG
fixed memory leak and wrong initialization for trival cases in cons_symresack.c
fixed bug with upgrading to packing/partitioning orbitopes
fixed bug with the status while upgrading in presol_symbreak.c
fixed wrong stage while clearing the conflict store
fixed behavior of SCIPfixVar() by setting infeasible pointer to TRUE if fixval lies outside variable domain
allow tightenVar() in SCIP_STAGE_PROBLEM stage
fixed bug in cumulative constraint handler when separating the LP solution
fixed issues with integer overflow in cumulative constraint handler
fixed bug where the convexity of Benders' decomposition subproblems was checked even when users defined subproblem solving methods. Now, as per the documentation, the user must explicitly state whether the subproblem is convex
fixed wrong indexing in heur_dualval
fixed issue with basis status in SoPlex LPi

Miscellaneous

statistics now output primal/dual bounds if objective limit is reached
memory check in debug mode is now disabled by default
message is now provided to the user to inform that automatic Benders' auxiliary variable lower bound computations are not activated when user defined subproblem solving methods are present
corrected documentation of the primalgap in SCIP; describe when it will be infinite

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.
don't consider implied redcost by default in the reduced cost propagator

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
fixed possible integer overflow, which led to wrong conclusion of infeasibility, in energetic reasoning of cons_cumulative.c

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