SCIP 4.0.1

Features

added parsing functionality to cardinality constraint handler for CIP format
allow to relax objective limit in reoptimization in presolved stage
suppress excessive printing about numerical troubles in LP on default verblevel (high)

Performance improvements

stop separation in cons_indicator after maxsepanonviolated many non violated separated cuts
improve choice of variable to enter support in separation of cons_indicator
only accept passed improving solutions in heur_indicator
add and use RESTRICT macro for some pointers
widened a bottleneck in simplifying long signomial sums in a nonlinear constraint
sorting of parents and children for some expression types is now independent of memory layout
unified and extended code that improves numerics of cuts generated by nonlinear constraint handlers

Interface changes

New API functions

SCIPvalidateSolve() to compare solving result with an external primal and dual reference value
SCIPisObjChangedProbing() to check whether the objective function has changed during probing mode
SCIPgetDualSolVal() to get the dual solution value of a constraint
SCIPisLPPrimalReliable() and SCIPisLPDualReliable() to check whether the current primal / dual LP solution were successfully checked for feasibility

Command line interface

New option in the interactive shell to validate the solution against an external primal and dual reference value
added command line option '-o' and command 'validatesolve' in interactive shell to validate the solution against an external primal and dual reference value.

Interfaces to external software

Updated and new interfaces to Mosek 8.1, GAMS, Gurobi and Glop (Google OR tools)
new LP interface to Glop (Google OR tools); CMake only

Changed parameters

renamed parameter "heuristics/completesol/maxunkownrate" to "heuristics/completesol/maxunknownrate"

Testing

add options to make test target (see Makefile section)

Build system

Cmake

New CMake build system alongside the usual Makefile setup

Makefile

added make options for specifying EXECUTABLE and OUTPUTDIR variables for the make test target

Fixed bugs

fixed bug in shift and propagate–variable information with a negation transformation is correctly reset after backtracking
fixed bug in genvbounds propagator when applying a restart after the root node
fixed unintended behavior of interrupt signal handler inside SCIP copies
fixed uninitialized values in SCIP's digraph data structure after calling SCIPdigraphResize()
fixed memory leak in OSiL reader when using SOS constraints
fixed issue related to SCIPcreateFiniteSolCopy not being able to remove all infinite fixings
fixed issue in SCIPcopyLimits() w.r.t. soft time limit
improved handling of infinite values in a primal solution in quadratic and nonlinear constraints
fixed bug in dynamic resizing of hashtables and hashmaps
fixed bug in computing violation and cut for certain nonlinear constraints when LP solution is slightly out of bounds
added workaround for bug in primal simplex of cplex 12.7.1.0 occuring when attempting to solve LPs without rows without presolving
fixed bug in binpacking example that might have led to doing the same branching several times
fixed memory issue in binpacking example
in GAMS writer, forbid also various parenthesis characters in gams symbol names
fixed debug solution check that appeared in probing mode when the objective function has changed
added missing definition of SCIP_UNUSED in memory.h if def.h is not included
relaxed a too strong assert concerning solutions close to the objective limit
fixed guard against using old Gurobi versions in lpi_grb.c: Gurobi 7.5 was not permitted
treat reopt bugs: Avoid numerical problems with changing objective; fix check for changed objective
fixed reading issue in mps reader: integer variables fixed to 0 or 1 are treated as binaries now, allowing to use them as indicator variables
afternode heuristics are now called even if the node limit was reached and the solving process will be stopped after the current node
fixed bug when activating probing mode with a non-empty separation storage
fixed bug in varbound coefficient tightening: if a varbound constraint only contained one variable afterwards, it may have been deleted without applying the induced bound, if the change was too small, this is now forced
fixed potential wrong locks update after a varbound constraint became redundant in coefficient tightening
fixed potentially wrong cleanup of fixed variables in nonlinear constraint handler
fixed wrong handling of unboundedness status in lpi_grb.c
fixed wrong handling of row basis status in lpi_grb.c

SCIP 4.0.0

Features

Introduced support for partial or infeasible user solutions, which SCIP tries to complete/repair heuristically
Improved conflict analysis through central conflict pool and dual ray analysis for primal infeasible LPs
New presolvers that disaggregate SOC constraints and reformulate QP's by adding KKT conditions
new Graph induced neighborhood search (GINS) primal heuristic that uses neighborhoods based on distances in the variable constraint connectivity graph. In addition, the heuristic supports a rolling horizon-like procedure to solve auxiliary problems for neighborhoods with increasing distance from the starting neighborhood.
new primal heuristic LP face that tries to find an integer solution inside the optimal LP face.
implemented linear time methods for (weighted) median selection for joint arrays of various types
added adaptive solving behavior of SCIP based on solving phases and heuristic transitions, if enabled via "solvingphases/enabled"
new presolving step for variables contained in a single quadratic constraint with proper square coefficients
can now solve relaxations within probing
will now enforce relaxation solution instead of lp or pseudosolution if lowerbound is better and the whole lp is included in the relaxation
in case of multiple relaxators the best solution is saved instead of the last one
can now separate perspective cuts for indicator constraints
added write callback for reader_bnd
added possibility to use a reference value for advanced analysis of the tree search. If a finite reference value (an objective value in original objective space) is passed via misc/referencevalue, SCIP keeps track of the number of nodes exceeding the reference value and the number of early backtracks – path switches in the tree when a child node with lower bound smaller than the reference value was available.
add new presolving step to disaggregate second order cone constraints
added reading capabilities for partial solutions with extension *.mst
new heuristic that tries to complete partial solutions
new global shift off all random seeds (randomization/randomseedshift) and unification of all existing random seeds
use new macros SCIPdebugMsg/SCIPsetDebugMsg/SCIPstatDebugMsg at all places where it makes sense
new feature solution polishing to improve integrality of LP solutions
new random number generator in pub_misc.h
the subnlp heuristic now gives ownership of a found solution to the heuristic that constructed the starting point, if any; as a consequence, MIP heuristics may now be shown more frequently for having found a solution when solving MINLPs, even though the solutions required an additional NLP solve
add check whether variables have been released when freeing SCIP
new constraint handler for cardinality constraints
implement a storage for conflicts to have more control over active conflicts
can now analyze dual unbounded rays of primal infeasible LPs
a print callback can now be specified for user expressions
added interval-evaluation of sine and cosine
add prop_nlobbt, a nonlinear optimization-based bound propagator solving two convex NLP relaxations for each variable
add sepa_convexproj, a separator which projects onto convex relaxation and build gradient cuts at the projection
add sepa_gauge, a separator which computes an interior point of a convex relaxation and performs a binary search in the segment joining the interior point and the point to separate until it finds a point in the boundary of the feasible region where to build a gradient cut
new presolving method presol_qpkktref to add the KKT conditions of a QP
implemented and extended stuffing presolving in linear constraint handler
allow to create constraints of constraint handlers that don't need constraints
New constraint handlers cardinality and components
nodes can now be postponed; currently, this can only be triggered by BEFORELP propagation callbacks
new components constraint handler which replaces the components presolver; it searches for independent subproblems and solves small ones as sub-SCIPs during presolve, larger ones are solved alternatingly during the main solving process
new presolving timing FINAL: presolving methods with this timing are only called once after all other presolvers with timings FAST, MEDIUM and EXHAUSTIVE are finished; during this timing only reductions are allowed that are self-contained, e.g., fixing all variables and deleting all constraints of an independent component; note that reductions found in this timing do not trigger a new presolving round
changed handling of coupling constraints in cons_indicator; the cuts will not be added to the pool, but are separated by default
concurrent solving mode that allows to run multiple SCIP instances, that share solutions and global variable bounds, in parallel
Revised pseudo random number generation and introduced central random seed for all plugins
Statistic
- Extended statistic output displayable via the interactive shell
- new statistic computed: "Root LP Estimate" that shows the root LP best-estimate with every pseudo-cost update
- added leaf statistics about LP objective limit|feasible|infeasible leaves to the statistics output and to the callable library: SCIPgetNObjlimLeaves(), SCIPgetNFeasibleLeaves(), SCIPgetNInfeasibleLeaves()
- next to the number of found solution, also the number of new best solutions is now printed for each heuristic (and relaxation solutions) in the statistics in the "Primal Heuristic" section.

Performance improvements

Extended the presolving timings by an additional timing FINAL for self-contained reductions
Improved and extended stuffing inside of linear constraint handler
Changed handling of coupling constraints in cons_indicator
Randomized tie-breaking in different parts of the code to reduce performance variability
use connectedness information of the clique table to speed up the clique partitioning algorithm
rewrote the propagate-and-cut-and-price loop so that successful propagations with DURINGLPLOOP timing, bound changes found by separation, and new primal solutions now trigger a new round of node solving, starting with propagation; improved tuning of propagation and heuristic timings
tuned propagation methods of several constraint handlers
make more use of SCIPmarkConsPropagate() to mark constraints for propagation and improved the internal handling of marked constraints
knapsack approximation algorithms use linear-time weighted median selection instead of sorting
improved greedy solution in SCIPsolveKnapsackApproximatelyLT() for the flow cover separation
adjusted most Large Neighborhood Search heuristics such that they collect their variable fixings first in an array, and only create and populate a sub-SCIP if enough variables will be fixed.
SCIP supports constraint compression for problem copies; constraint compression denotes the immediate removal of fixed variables from constraint data at creation time to reduce memory requirements.
reduce performance variability by using a small perturbation in the undercover heuristic
reduce performance variability by using random numbers as tie-breaker for external branching candidates
1-opt heuristic can now be repeatedly executed as long as new incumbents are found
improve propagation of absolute-value expression in the case that the sign of the argument is fixed

Interface changes

separated header pub_misc.h from repeated methods for sorting and (weighted) median selection; those are also available in separate headers pub_misc_sort.h and pub_misc_select.h, but included into pub_misc.h
new files heuristics.c/heuristics.h to collect methods that are frequently used by heuristics
merged dive.c/pub_dive.h with heuristics.c/heuristics.h, removed dive.c/pub_dive.h
spx2 is the new default LP solver interface
setting a parameter to a non-valid value now produces an error message instead of a warning
the CPLEX LPI now also compiles with CPLEX 12.7.0.0
major update ot the Gurobi LPI, which supports ranged rows now and several performance improvements, but only works with Gurobi version >gt;= 7.0.2
bound reader uses angle bracket around variable names

New and changed callbacks

CONSINITLP callback now has a new parameter 'infeasible', which is a pointer to store whether infeasibility was detected while building the initial LP relaxation
new optional callback CONSENFORELAX for enforcement of relaxation solutions

Deleted and changed API methods

add new parameter to SCIPtrySolFree, SCIPtryCurrentSol and SCIPcheckSol to check all constraints when printing violations
SCIPinitConflictAnalysis() gets now 2 additional values: the type of the conflict and whether the current cutoff bound is used or not
SCIPcreateNlRow() gets an additional argument "curvature"
added argument "initialseed" to SCIPcreateDiveset()
new parameter "includeslp" for SCIPincludeRelax() and SCIPincludeRelaxBasic() to indicate whether relaxation includes all linear rows and can be enforced
changed type of argument "timingmask" from unsigned int to SCIP_HEURTIMING in SCIPincludeHeur(), SCIPincludeHeurBasic()
methods SCIPrandomGet{Int,Real}() substitutes SCIPgetRandom{Int,Real}() (marked to be deprecated)
methods SCIPrandomPermute{Int}Array() substitutes SCIPpermuteRandom{Int}Array() (marked to be deprecated)
method SCIPrandomGetSubset() substitutes SCIPgetRandomSubset() (marked to be deprecated)
rename method SCIPgetReopSolsRun() to SCIPgetReoptSolsRun()
the parameters of SCIPlpiChgObj(), SCIPlpiSetBase(), SCIPlpiSetState(), SCIPlpiSetNorms() have been declared as const
SCIPapplyHeurSubNlp() can now return the solution found by the sub-NLP heuristic
in param.c/h: rename SCIPparamCheckBool() to SCIPparamIsValidBool(), SCIPparamCheckString() to SCIPparamIsValidString(), SCIPparamCheckChar() to SCIPparamIsValidChar(), SCIPparamCheckLongint() to SCIPparamIsValidLongint(); the new methods return a bool whether the given value is valid for the parameter instead of printing a warning message and returning an error code if the value is invalid
add SCIPparamIsValidInt() and SCIPparamIsValidReal() to param.c/h
in scip.c/h: rename SCIPcheckBoolParam() to SCIPisBoolParamValid(), SCIPcheckLongintParam() to SCIPisLongintParamValid(), SCIPcheckCharParam() to SCIPisCharParamValid(), SCIPcheckStringParam() to SCIPisStringParamValid(); the new methods return a bool indicating whether the given value is valid for the parameter instead of printing a warning message and returning an error code if the value is invalid
add missing functions SCIPisIntParamValid() and SCIPisRealParamValid() to scip.c/h
removed SCIPvarGetLbAtIndex() and added SCIPgetVarLbAtIndex()
removed SCIPvarGetUbAtIndex() and added SCIPgetVarUbAtIndex()
removed SCIPVarGetBdAtIndex() and added SCIPgetVarBdAtIndex()
removed SCIPvarWasFixedAtIndex() and added SCIPgetVarWasFixedAtIndex()

New API functions

library methods SCIPcopyConsCompression(), SCIPcopyOrigConsCompression() that accept an array of variables that are immediately fixed in the copy. Alternatively, local instead of global bounds can be used for compression.
library methods SCIPenableConsCompression(), SCIPisConsCompressionEnabled(), SCIPcopyConsCompression(), SCIPcopyOrigConsCompression()
added functions for concurrent solving mode (see concurrent.h, concsolver.h)
SCIPcreateNlpiProb(), SCIPupdateNlpiProb() and SCIPaddNlpiProbRows() to create and update a nonlinear relaxation
SCIPgetNObjlimLeaves(), SCIPgetNFeasibleLeaves(), SCIPgetNInfeasibleLeaves() for statistics output about LP objective leaves
SCIPcheckCopyLimits() which can be used to check that enough time and memory is left to run a sub-SCIP after subtracting time and memory used by the main-SCIP and SCIPcopyLimits() which copies these limits accordingly and disables all other limits (need to be set by the plugin, if needed)
SCIPcopyLargeNeighborhoodSearch() in heuristics.h that supports compressed copying and two kinds of problem copy: the MIP-relaxation or a 1-1 problem copy (by copying the constraints and not the LP relaxation)
SCIPsolveProbingRelax() to solve a relaxation within probing
SCIPgetIntVarXor() to access integer variable of XOR constraints
SCIPgetLastStrongbranchingLPSolstat() to query the LP statuses after strong branching on a variable
SCIPisDualSolAvailable() to query the dual solution availability
SCIPinitializeRandomSeed()
SCIPprintDebugMessage(), SCIPsetPrintDebugMessage(), SCIPstatPrintDebugMessage() that output debug messages and also print the subscip depth; the first two output via the message handler; also added macros SCIPdebugMsg(), SCIPsetDebugMsg(), SCIPstatDebugMsg()
SCIPdebugMsgPrint()/SCIPsetDebugMsgPrint() that output a message without "[debug]" prefix via the message handler (compare SCIPdebugPrinf())
SCIPlpiSetIntegralityInformation() to improve SoPlex' solution polishing
SCIPcreateConsCardinality() to create a cardinality constraint
SCIPcreateConsBasicCardinality() to create a basic cardinality constraint
SCIPchgCardvalCardinality() to changes cardinality value of cardinality constraint (i.e., right hand side of cardinality constraint)
SCIPaddVarCardinality() to add a variable to a cardinality constraint
SCIPappendVarCardinality() to append a variable to a cardinality constraint
SCIPgetNVarsCardinality() to get the number of variables in a cardinality constraint
SCIPgetVarsCardinality() to get the array of variables in a cardinality constraint
SCIPgetCardvalCardinality() to get the cardinality value of a cardinality constraint (i.e., right hand side of cardinality constraint)
SCIPgetWeightsCardinality() to get the array of weights of a cardinality constraint
SCIPgetLinvarMay{Decrease,Increase}Quadratic() to get index of a variable in linear term of quadratic constraint that may be decreased without making any other constraint infeasible
SCIPswapReals() to swap two real values
SCIPgetNNZs() to get the number of active non-zeros in the transformed/presolved problem

Command line interface

new command line parameter -v to print detailed build options

Interfaces to external software

SCIP uses the lpi_spx2 interface by default
Improved Gurobi interface that can handle ranged rows (requires Gurobi >gt;= 7.0.2)
Revised documentation of the SCIP C-API to group methods more comprehensively by topics
dropped support for Ipopt <lt; 3.11
updated CppAD to 20160000
Interfaces for Python and Java are, among others, now available via http://www.github.com/scip-interfaces
Additional I/O-functionalities for debugging and logging in SCIP and in the AMPL interface
for users of the ampl interface, the display/logfile option has been added to set the name of a file to write the SCIP log to (additionally to stdout)

Changed parameters

setting a value for a fixed parameter will no longer return with an error, if the new value equals the one to which the parameter is fixed
changed value of parameter "separating/clique/cliquedensity" to 0.0 such that the separator always constructs a dense clique table which proved to be faster on the benchmarks MMM and stableset.
parameters "misc/permutationseed", "misc/permuteconss" and "misc/permutevars" changed to "randomization/permutationseed", "randomization/permuteconss" and "randomization/permutevars"
parameters "conflict/useinflp" and "conflict/useboundlp" are now of type char (before bool)
all parameters of the components presolver (starting with "presolving/components/") are now parameters of the components constraint handler (starting with "constraints/components/")

New parameters

class randomization
"branching/sumadjustweight" to adjust branching scores by adding a sum epsilon in order to keep score differences near zero, which are otherwise completely disregarded (they are adjusted to at least sum epsilon)
"concurrent/∗" and "parallel/∗" for configuring the concurrent solving mode
"constraints/cardinality/branchbalanced" to decide whether to use a balanced branching scheme in the enforcing of cardinality constraints
"constraints/cardinality/balanceddepth" to set the maximal depth until balanced branching is turned off
"constraints/cardinality/balancedcutoff" to determine that balanced branching is only used if the branching cut off value w.r.t. the current LP solution is greater than a given value
"constraints/indicator/sepaperspective" to turn on separation of perspective cuts for indicator constraints
"constraints/indicator/sepapersplocal" to decide whether local cuts can be used for perspective cuts for indicator constraints
"constraints/quadratic/projectedcuts" to enable convex quadratics to generate gradients cuts at the projection of the point onto the region described by the constraint, which is supporting
"lp/solutionpolishing" to enable LP polishing only at the root LP or always
"misc/referencevalue" to pass a reference value for further analysis of the tree search, see also in 'features'
"presolving/qpkktref/addkktbinary" to allow the presence of binary variables for the KKT update
"presolving/qpkktref/updatequadbounded" to add the KKT conditions to QPs only if all variables are bounded
"presolving/qpkktref/updatequadindef" to add the KKT conditions to QPs only if the quadratic matrix is indefinite
"randomization/lpseed" to set the initial seed of the LP solver
"solvingphases/enabled" to activate adaptive behavior during the solution process; several further parameters in the solvingphases-section to control how to switch the parameters and whether a restart should be performed between the phases.

Data structures

new SCIP_REGRESSION data structure in pub_misc.h to incrementally compute a best-fit line through pairs of observations
add maximum branch-and-bound tree depth constant SCIP_MAXTREEDEPTH (replaces SCIPgetDepthLimit and SCIPtreeGetDepthLimit)

Unit tests

New unit testing system built on the Criterion framework

Build system

Makefile

Building with SHARED=true automatically generates the combined library libscipsolver.so for easier linking
All objective files are now placed in obj/static or obj/shared, depending on SHARED=false or SHARED=true, respectively.
All internal and external libraries are placed in lib/static and lib/shared, the include files are in lib/include.
External projects (including make.project) can use the makefile variable LINKCXXSCIPALL or LINKCCSCIPALL to link all SCIP libraries.
Running "make help" lists all makefile options.
All makefiles in examples/ and applications/ have been updated.
The binaries now contain an rpath to the SCIP directory, such that shared libraries are found.
make.project defines a variable SCIP_VERSION containing the SCIP version number
revise sub-makefiles for MSVC on MinGW
new target "dll" to build Windows dlls with MSVC
make shared libraries aware of their dependencies
link binary to shared libs when compiling with SHARED=true
'make install' copies now all header files
sub-makefile for CrayXC systems added
rename dll target to windowslib

Fixed bugs

correct handling of implicit integer variables with fractional solution value in simplerounding heuristic
avoid numerically troublesome aggregations
fixed bug in event system: bound change events of the new focus node must be processed, even if the bound is the same as at the last focus node
fixed memory bug in SCIP_DIGRAPH
fixed bug while changing the objective value of an original value after transforming the problem
fixed bug with sorting of propagators in presolving: the order can be changed by calling probing; thus, there is a copy of the propagators, which is sorted by presolving priority
avoid numerically unstable (multi-)aggregations
added missing capturing and releasing mechanism in genvbounds propagator
improved counting of memory consumption by using more block memory and counting all allocated memory
fixed bug in XML reader concerning comments
fixed wrong representation of SOC constraints in NLP
fixed possible segmentation fault in genvbounds propagator
fixed bug with solutions from previous runs not satisfying an objective limit
the AMPL interface now writes a solve status (solve_result_num) into the .sol file
fix wrong propagation of product expressions
fix memory leaks in TSP example
return SCIP_ERROR when a memory exception is caught in SoPlex (was SCIP_LPERROR)
in the cmpres.awk (allcmpres.sh) output, the counts in the time column are now with respect to the whole set of processed instances (as with fail and solv), while before it was with respect to the set of instances where no solver failed (eval set); thus, now proc = fail + time + solv.
fixed memory leak in OSiL reader
writing of solutions or parameters to a file now works also with the message handler set to quiet
fixed bug in heur_octane with uninitialized ray direction
fixed a few issues within redundant constraint detection of (specialized) linear constraint handlers
SCIPisObjIntegral() now works correctly in SCIP_STAGE_PROBLEM
ignore lower and upper bound tightenigs beyond +/-infinity during solving
fix wrong NLP representation of logic-or constraints in the dual value heuristic
time limit of SCIP-infinity is converted to LPI-infinity when setting it
fix LP activity of a row that has been modified
fixed issue in reader_opb concerning writing of fixed variables contained in no constraints
fixed two bugs in heur_indicator: use improvesols parameter now and update pointer to indicator constraint handler