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

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

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 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 issue related to SCIPcreateFiniteSolCopy() not being able to remove all infinite fixings
  • fixed issue in SCIPcopyLimits() w.r.t. soft time limit
  • 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
  • use new macros SCIPdebugMsg(), SCIPsetDebugMsg(), SCIPstatDebugMsg() at all places where it makes sense
  • new random number generator in pub_misc.h
  • 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
  • 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
    • 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
  • 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
  • improved greedy solution in SCIPsolveKnapsackApproximatelyLT() for the flow cover separation
  • 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

Interface changes

New and changed callbacks

  • Concurrent SCIP:
    • extended interface to support concurrent solving mode
  • Constraint Handlers:
    • new optional callback CONSENFORELAX to enforce a relaxation solution, see How to add constraint handlers
    • 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

New API functions

Command line interface

  • new command line parameter -v to print detailed build options

Interfaces to external software

  • Interfaces for Python and Java are, among others, now available via http://www.github.com/scip-interfaces
  • Revised documentation of the SCIP C-API to group methods more comprehensively by topics
  • dropped support for Ipopt < 3.11
  • Additional I/O-functionalities for debugging and logging in SCIP and in the AMPL interface
  • updated CppAD to 20160000
  • 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)
  • LP Interfaces:
    • SCIP uses the lpi_spx2 interface by default
    • 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
  • 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

Unit tests

  • New unit testing system built on the Criterion framework

Build system

Makefile

  • All makefiles in examples/ and applications/ have been updated.
  • make.project defines a variable SCIP_VERSION containing the SCIP version number
  • revise sub-makefiles for MSVC on MinGW
  • make shared libraries aware of their dependencies
  • sub-makefile for CrayXC systems added
  • Places:
    • 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.
    • The binaries now contain an rpath to the SCIP directory, such that shared libraries are found.
  • Linking:
    • 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
  • Memory:
    • fixed memory bug in SCIP_DIGRAPH
    • improved counting of memory consumption by using more block memory and counting all allocated memory
    • fix memory leaks in TSP example
    • return SCIP_ERROR when a memory exception is caught in SoPlex (was SCIP_LPERROR)
    • fixed memory leak in OSiL reader
  • Objective:
    • fixed bug while changing the objective value of an original value after transforming the problem
    • fixed bug with solutions from previous runs not satisfying an objective limit
    • SCIPisObjIntegral() now works correctly in SCIP_STAGE_PROBLEM
  • Heuristics:
    • fixed two bugs in heur_indicator: use improvesols parameter now and update pointer to indicator constraint handler
    • fix wrong NLP representation of logic-or constraints in the dual value heuristic
    • correct handling of implicit integer variables with fractional solution value in simplerounding heuristic
    • fixed bug in heur_octane with uninitialized ray direction