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 and Gurobi
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 unintended behavior of interrupt signal handler inside SCIP copies
fixed uninitialized values in SCIP's digraph data structure after calling SCIPdigraphResize()
fixed bug in dynamic resizing of hashtables and hashmaps
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
added missing definition of SCIP_UNUSED in memory.h if def.h is not included
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
LP interfaces:
fixed guard against using old Gurobi versions in lpi_grb.c: Gurobi 7.5 was not permitted
fixed wrong handling of unboundedness status in lpi_grb.c
fixed wrong handling of row basis status in lpi_grb.c
Propagator:
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
Constraints:
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 memory leak in OSiL reader when using SOS constraints
Solution:
improved handling of infinite values in a primal solution in quadratic and nonlinear constraints
fixed bug in computing violation and cut for certain nonlinear constraints when LP solution is slightly out of bounds
fixed debug solution check that appeared in probing mode when the objective function has changed
relaxed a too strong assert concerning solutions close to the objective limit
SCIP 4.0.0
Features
Introduced support for partial or infeasible user solutions, which SCIP tries to complete/repair heuristically
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
can now solve relaxations within probing
in case of multiple relaxators the best solution is saved instead of the last one
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.
added reading capabilities for partial solutions with extension *.mst
new global shift off all random seeds (randomization/randomseedshift) and unification of all existing random seeds
add check whether variables have been released when freeing SCIP
a print callback can now be specified for user expressions
LP Solutions:
will now enforce relaxation solution instead of lp or pseudosolution if lowerbound is better and the whole lp is included in the relaxation
new feature solution polishing to improve integrality of LP solutions
Constraints:
new constraint handler for cardinality constraints
added interval-evaluation of sine and cosine
allow to create constraints of constraint handlers that don't need constraints
New constraint handlers cardinality and components
Conflicts:
implement a storage for conflicts to have more control over active conflicts
Improved conflict analysis through central conflict pool and dual ray analysis for primal infeasible LPs; can now analyze dual unbounded rays of primal infeasible LPs
Presolving:
New presolvers that disaggregate SOC constraints and reformulate QP's by adding KKT conditions
new presolving step for variables contained in a single quadratic constraint with proper square coefficients
add new presolving step to disaggregate second order cone constraints
new presolving method presol_qpkktref to add the KKT conditions of a QP
implemented and extended stuffing presolving in linear constraint handler
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
Separation and Cuts:
can now separate perspective cuts for indicator constraints
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
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
Heuristics:
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.
new heuristic that tries to complete partial solutions
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
new multistart heuristic for NLPs
Propagator:
add prop_nlobbt, a nonlinear optimization-based bound propagator solving two convex NLP relaxations for each variable
nodes can now be postponed; currently, this can only be triggered by BEFORELP propagation callbacks
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
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
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
knapsack approximation algorithms use linear-time weighted median selection instead of sorting
reduce performance variability by using random numbers as tie-breaker for external branching candidates
Heuristics:
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.
reduce performance variability by using a small perturbation in the undercover heuristic
1-opt heuristic can now be repeatedly executed as long as new incumbents are found
Constraints:
Improved and extended stuffing inside of linear constraint handler
Changed handling of coupling constraints in cons_indicator
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.
Propagation:
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
improve propagation of absolute-value expression in the case that the sign of the argument is fixed
CONSINITLP callback now has a new parameter infeasible, which is a pointer to store whether infeasibility was detected while building the initial LP relaxation
Deleted and changed API methods
setting a parameter to a non-valid value now produces an error message instead of a warning
bound reader uses angle bracket around variable names
added parameters conftype and iscutoffinvolved to SCIPinitConflictAnalysis() that indicate the type of the conflict and whether the current cutoff bound is used or not
based on the initial size SCIP_HASHTABLE and SCIP_HASHMAP choose an appropriate size internally to allow insertion of that many elements without resizing
the following 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
in param.c/h: 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
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)
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.
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
Improved Gurobi interface that can handle ranged rows (requires Gurobi >= 7.0.2)
the CPLEX LPI now also compiles with CPLEX 12.7.0.0
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())
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
link binary to shared libs when compiling with SHARED=true
External projects (including make.project) can use the makefile variable LINKCXXSCIPALL or LINKCCSCIPALL to link all SCIP libraries.
Building with SHARED=true automatically generates the combined library libscipsolver.so for easier linking
Targets:
Running make help lists all makefile options.
make install copies now all header files
new target dll to build Windows dlls with MSVC
rename dll target to windowslib
Fixed bugs
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
avoid numerically unstable (multi-)aggregations
fixed bug in XML reader concerning comments
the AMPL interface now writes a solve status (solve_result_num) into the .sol file
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.
writing of solutions or parameters to a file now works also with the message handler set to quiet
ignore lower and upper bound tightenigs beyond +/-infinity during solving
time limit of SCIP-infinity is converted to LPI-infinity when setting it
fix LP activity of a row that has been modified
Propagation:
fixed possible segmentation fault in genvbounds propagator
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
added missing capturing and releasing mechanism in genvbounds propagator
fix wrong propagation of product expressions
Constraints:
fixed wrong representation of SOC constraints in NLP
fixed a few issues within redundant constraint detection of (specialized) linear constraint handlers
fixed issue in reader_opb concerning writing of fixed variables contained in no constraints