Scippy

SCIP

Solving Constraint Integer Programs

Release notes for SCIP 6.0

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.

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

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

New API functions

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