Scippy

SCIP

Solving Constraint Integer Programs

Release notes for SCIP 4.0

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

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

New API functions

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