Scippy

SCIP

Solving Constraint Integer Programs

Release notes for SCIP 3.2

SCIP 3.2.1

Features

  • new force parameter in (root)redcost propagator to run the propagator also with active pricers

Performance improvements

  • do not transfer solutions to original space, if SCIP is being freed
  • modified implication graph analysis of SOS1 constraint handler; a new component allows to deduce zero fixings of variables
  • made SOS1 constraint handler specific diving selection rule faster for the case that the SOS1 constraints do not overlap
  • improved disjunctive cuts by the monoidal cut strengthening procedure of Balas and Jeroslow

Examples and applications

  • several improvements of SCIP-Jack (STP application): extended presolving for STP variants, STP-specific branching rule, dual heuristic to generate initial LP relaxation SCIP-Jack is now competitive with problem specific state-of-the-art solvers on several well-known STP variants, e.g., the (rooted) prize-collecting Steiner tree problem.
  • MultiObjective application renamed to PolySCIP; several improvements: better command line argument processing, overhaul of much of the source code, installation via CMake

Interface changes

  • made debug solution functionality thread safe (see debug.h for further information)

Deleted and changed API methods

Command line interface

  • added interactive shell command display finitesolution to print solution with infinite fixings removed, added reference to that method to display solution output if there are infinite fixings
  • new interactive shell command write history to write the command line history (only when compiled with Readline)

Interfaces to external software

  • significantly improved Python interface to support user callbacks as well as linear and quadratic expressions

New parameters

  • constraints/sos1/branchingrule to decide whether to use neighborhood, bipartite, or SOS1 branching (this parameter replaces the old parameters constraints/sos1/neighbranch, constraints/sos1/bipbranch, and constraints/sos1/sos1branch)
  • constraints/sos1/depthimplanalysis to limit the number of recursive calls of implication graph analysis
  • constraints/sos1/perfimplanalysis to perform an implication graph analysis to deduce variable fixings and additional SOS1 constraints (this parameter replaces the old parameter constraints/sos1/updateconflpresol)
  • misc/transsolorig for transfering transformed solutions to the original space (default: true)
  • propagating/rootredcost/onlybinary to propagate root reduced costs of binary variables only

Data structures

  • renamed MIP matrix structure to SCIP_MATRIX
  • changed the numeric values for PRESOLTIMING flags

Build system

Makefile

  • new target dll to build Windows dlls with MSVC
  • add new compiling flag OPENSOURCE to allow/forbid the usage of third party software

Fixed bugs

  • fixed wrong objective sense when copying the original problem
  • fixed a bug in merge step of cliques during clean up phase; method did not correctly handle infeasibility in the case of multiple variable-negation pairs
  • fixed a previously untreated case in the linear cons simplification where coefficients only differ by slightly more than an epsilon
  • fixed bug in parsing emphasis parameters which formerly led to completely wrong results
  • fixed bug in the computation of the Wilcoxon test
  • do not use the relative and absolute gap limit if no primal solution has been found so far
  • fixed bug in conflict.c with wrong reset of bounds used
  • fixed bug with transferring solutions to new runs (need to recompute objective before checking)
  • fixed issue with infinite values when checking cuts for redundancy
  • fixed library problems on Windows operating systems
  • Variables:
    • fixed wrong check when computing cuts for factorable quadratic functions bound tightening of a single variable
    • fixed wrong handling of loose variables in OBBT
    • fixed freeing of hash for binary variables
    • fixed bug during the computation of branching points for continuous variables which are almost fixed to +/- SCIPinfinity()
    • treated the case of integer variables as intermediate variables in the process of obtaining the active variable for a given binary variable
  • LP:
    • fixed a bug in dive.c that occurred when lpsolvefreq was set to 1; after a cutoff, the solution values of the linked LP solution might have become invalid
    • do not analyse an infeasible LP for conflicts during diving mode when LHS/RHS of rows were changed
    • use LPi infinity when reverting bound changes in conflict analysis
  • Heuristics:
    • fixed bug in heur_simplerounding in connection with relaxators
    • fixed bug in feaspump heuristic where last solution candidates were not updated correctly
    • fixed bug with infinite shift values in heur_shifting
    • fixed bug in shiftandpropagate heuristic: the heuristic did not correctly handle intermediate, global bound changes of the selected variable after its tentative fixing led to a cutoff.
  • Propagator:
    • (root) reduced cost propagators are not run anymore when doing branch-and-price, since they may install upper bounds on variables which might interfere with the pricing (they may be enabled again by their force parameters)
    • fixed too hard assertion in pseudoobj propagator
    • fixed a bug in shiftandpropagate where column positions after sorting are now correctly linked to their variables after sorting
    • fixed potential memory leak in genvbound propagator
  • Presolving:
    • fixed inconsistency in knapsack constraint handler data during presolving
    • fixed some problem with reoptimization when the problems are infeasible or have been solved in presolving
    • fixed endless loop in knapsack constraint handler when continuous variables change their types to binary during presolving
    • squares of binary variables might not have been replaced by the binary variable itself in presolve, if the variable was originally general integer and only became binary during presolve (due to bound tightening)
    • fixed bug in dive.c avoiding a check of constraints in the presence of indicator constraints
  • Constraints:
    • fixed numerical problems in computation of cuts for bivariate functions in quadratic constraint handler
    • fixed bug in quadratic constraint handler when computing lifted-tangent inequalities
    • fixed bug in nonlinear constraint handler when replacing a violated nonlinear constraint leads to an infinite
    • fixed bug in SOS1 constraint handler with inconsistent data structure after restart
    • fixed wrong handling of negated variables in bound tightening procedure of SOS1 constraint handler
    • fixed bug in simple fixing heuristic of SOS1 constraint handler
    • fixed two bugs in pseudoboolean constraint handler with wrong sorting of and constraints
    • fixed issue: constraints being parallel to objective function (after restart) sometimes led to wrongly stating infeasible
    • fixed bug during coefficient tightening in varbound constraint handler
    • handle cutoffs in cons_indicator detected by infeasible inequalities
    • fixed late change of type of slack variables in cons_indicator, if the bounds are not integral
    • fixed initsol and exitsol of cons_indicator, if problem has already been solved
    • fixed bug in cons_indicator with changing type of slackvariable

SCIP 3.2.0

Features

  • added reoptimization feature for optimization problems with changed objective function or tighter feasible region
  • the original problem can now be permuted directly after reading (if misc/permutationseed has value >= 0)
  • added methods to compute strongly connected components with Tarjan's Algorithm
  • added method to propagate implications of SOS1 variables
  • convex quadratic contraints can now generate gradient cuts which are supporting to the feasible region
  • SoPlex interface can now (re)store dual steepest edge weights
  • extended expression parsing to support power, realpower and signpower operators; started support for user-defined operators in expression trees/graphs
  • possibility to set a soft time limit which becomes active only after the first primal solution was found
  • added matrix module for getting access to the internal mixed inter linear problem matrix
  • better handling of large values returned by the LP solver
  • added more checks to SCIP{alloc,realloc,duplicate}BufferArray() to handle overflows properly
  • new plugin for reoptimizing a sequence of optimization problem that differ in the objective function, e.g., sequences arising from column generation
  • new plugin compr for rearranging the search tree, currently this only works on the reoptimization tree
  • moved assertions in comparison methods from scip.c to set.c
  • Constraints:
    • we can now upgrade quadratic constraints with one bilinear term to SOC constraints
    • we can also upgrade general quadratic constraints with a single negative eigenvalue to SOC constraints
  • Branching:
    • tighter reliability notions introduced for reliability branching, based on pseudo-cost relative errors and comparing candidates with the best pseudo-candidate using a 2-sample student-T test. These methods are used in disjunction with the existing reliability notion that uses a fixed number as reliability threshold for every variable before turning off strong-branching. This means, the classical method must be turned off by setting parameters minreliable and maxreliable to 0. The behavior is controlled through several parameters.
    • new distribution branching rule to base decisions on row activity (normal) distribution over domain space
    • can now output information for BAK: Branch-and-bound Analysis Kit
    • new score in hybrid reliability pseudocost branching that prefers nonlinear variables when solving MINLPs
    • new branching rule multaggr which allows to branch on general disjunctions defined by fractional multi-aggregated variables
    • new branching rules for SOS1 constraints for branching on a neighborhood or a complete bipartite subgraph of the conflict graph. In addition to variable domain fixings, it is sometimes also possible to add complementarity constraints to the branching nodes. This results in a nonstatic conflict graph, which may change dynamically with every branching node.
    • new branching rule nodereopt to reconstruct the tree after changing the objective function
  • Reader:
    • the MPS reader can now read semi-integer variables, they are handled by creating bound disjunction constraints
    • the MPS reader can now handle objective constants given as (the negation of) the RHS of the objective row
  • Separation:
    • obbt propagator applies now additional separation and propagation in order to learn stronger and more bound tightenings
    • extended probing mode to allow separation and objective coefficient changes
    • improved separation procedure of SOS1 constraint handler, including bound (clique) cuts and implied bound cuts
    • new disjunctive cut separator for SOS1 constraints
    • new edge-concave cut separator for quadratic constraints
  • Presolver:
    • Improved coordination of presolvers. There are three timings for presolvers now, FAST, MEDIUM and EXHAUSTIVE. Each presolving callback can specify one or more of these timings in which it will be called later. Within a presolving method, the current timing can be checked and the algorithms to be performed selected based on the timing. In one presolving round, first all presolving methods with timing FAST are called, sorted by priority. If they found enough reductions, a new round is started, otherwise, all presolving methods with timing MEDIUM are called. Again, with enough reductions, a new presolving round is started, too few reductions lead to running the EXHAUSTIVE presolvers. Similar to the delay concept used before, we are not neccessarily running all EXHAUSTIVE presolvers but stop as soon as one of them found enough reductions, starting a new presolving round immediately.
    • new presolving components for SOS1 constraints, including bound tightening and clique extension
    • new presolver tworowbnd for improving variable bounds and detecting redundant constraints added
    • new presolver dualagg for aggregating single up-/downlocked variables by a binary variable added
    • new presolver implfree for aggregating implied free variables added
    • new presolver redvub which can detect redundant variable upper bound constraints added
    • new presolver stuffing for fixing of singleton continuous variables added
  • Heuristic:
    • improved clique and variable bound heuristics
    • new heuristic distribution diving that bases its score function on the changes regarding solution density
    • variable histories can be transferred between sub-SCIPs solved by LNS heuristics and the component presolver and the main SCIP to reuse this information.
    • new heuristic heur_indicator that tries to make partial solutions with indicator constraints feasible. It also tries to improve them (or external solutions) by a one-opt local search.
    • new heuristic (heur_bound) which fixes all integer variables to their lower/upper bounds and solves the remaining LP
    • modified diving heuristics to handle SOS1 constraints
    • new primal heuristic for reoptimization 'ofins': objective function induced neighborhood heuristic
    • new heuristic for reoptimization which constructs solutions based in the changes between the objective function and the optimal solution before changing the objective function
  • Statistic:
    • extended variable branching statistics in the interactive shell by sample variance of unit gains
    • extended statistic output of interactive shell by more information on diving heuristic behavior

Performance improvements

  • improved treatment of nonlinearities in hybrid reliability pseudo cost branching
  • using sparsity information of the SoPlex LP
  • Constraints:
    • improved vartype upgradability from continuous to implicit variables in cons_linear.c, depending on their objective coefficients
    • improved propagation of SOS1 constraint handler using the information from a conflict
  • Heuristics:
    • zi rounding heuristic uses buffer data structures, thereby decreasing total memory usage of SCIP
    • adjusted (hard) diving heuristics to solve fewer LPs. LP's are resolved only if a parameter-defined percentage of the variable bounds changed through domain propagation or at a predefined frequency.
    • some of the diving heuristics additionally consider indicator variables and SOS1 variables as candidate variables and try to make these constraint types feasible before passing a rounded solution to SCIPtrySol()
  • Presolving:
    • new presolving/propagation algorithm using the gcd for ranged rows and equations in cons_linear
    • added presolving levels (FAST, MEDIUM and EXHAUSTIVE) to allow better balancing of presolvers
  • Separation:
    • improved separation procedure of SOS1 constraint handler
    • improved separation procedure for convex quadratic constraints

Examples and applications

  • two new applications for multi-objective optimization (PolySCIP) and the Steiner Tree Problem in Graphs
  • new application for solving Steiner tree problems: SCIP-Jack can handle both the classical Steiner tree problem in graphs and 10 of its variants

Interface changes

New and changed callbacks

  • new callback function SCIP_DECL_CONSGETDIVEBDCHGS to provide constraint handler method to suggest dive bound changes during the generic diving algorithm, see type_cons.h for details
  • new callback SCIP_DECL_DIVESETGETSCORE to implement scoring function to guide diving

Deleted and changed API methods

New API functions

Command line interface

  • extended variable branching statistics and statistic output in the interactive shell (see Statistic section)
  • submenu for setting vbc settings renamed to visual
  • at the end of a command line run the best solution can now be output in the orignal space

Interfaces to external software

  • in the AMPL interface, variable and constraint attributes (flags) can now be set via suffixes, where 0 (unset) stands for the default, 1 for TRUE and other values for FALSE; see SCIPcreateVar() and SCIPcreateCons() for their meaning; for variables, initial and removable are recognized; for constraints, initial, separate, enforce, check, propagate, dynamic and removable are recognized
  • the AMPL interface now passes an initial guess, if specified, as a solution (that will be checked for feasibility) to SCIP

Changed parameters

  • rowrepswitch set to 2.0, so row representation is activated if LP has at least 2 times more rows than columns
  • one can now set emphasis parameters at the beginning of a settings file; it should start with emphasis: and the contain the emphasis string, e.g., emphasis: feasibility or emphasis: heuristics off.
  • Renamed parameters:
    • vbc/filename to visual/vbcfilename
    • vbc/realtime to visual/realtime
    • vbc/dispsols to visual/dispsols

New parameters

  • added parameter to switch pseudo cost update in diving heuristics (enabled by default)
  • branching/relpscost/confidencelevel to set the confidence level to be used by statistical tests
  • branching/relpscost/higherrortol to define the highest reliability threshold for relative error based reliability
  • branching/relpscost/lowerrortol to define a lower reliability threshold for relative error based reliability
  • branching/relpscost/nlscoreweight for weight of nonlinear score when branching on MINLPs
  • branching/relpscost/usedynamicconfidence to use a dynamic confidence level based on the amount of strong-branching simplex-iterations compared to the overall simplex iterations (default is FALSE)
  • branching/relpscost/usehyptestforreliability to enable strong branching decisions based on a 2-sample student-T test of all prior pseudo-cost observations between the best pseudo-candidate and the candidate for which to decide whether strong-branching should be applied
  • branching/relpscost/userelerrorreliability to enable relative error based reliability
  • branching/relpscost/skipbadinitcands for skipping strong-branching candidates whose estimated gain is significantly worse than the one of the locally best (sb or pseudo) candidate
  • constraints/linear/multaggrremove to perform multi-aggregations in linear constraint handler only if the constraint can be removed afterwards
  • constraints/linear/rangedrowpropagation to disabled newly implemented propagtion algorithm for ranged rows and equations
  • constraints/quadratic/advanced/interiorcomputation to select the way of computing and interior point for gauge cuts
  • constraints/quadratic/gaugecuts to enable convex quadratics to generate gradients cuts which are supporting
  • constraints/soc/generalsocupgrade to allow general quadratics to be upgraded to soc
  • constraints/SOS1/addcomps to add local complementarity constraints to the branching nodes (can be used in combination with neighborhood or bipartite branching)
  • constraints/SOS1/addbdsfeas to define a minimal feasibility value for local bound (clique) inequalities in order to be added to the branching node
  • constraints/SOS1/addcompsdepth to define the maximal depth for adding complementarity constraints
  • constraints/SOS1/addcompsfeas to define a minimal feasibility value for local complementarity constraints in order to be added to the branching node
  • constraints/SOS1/autocutsfromsos1 to automatically switch to separating bound cuts from SOS1 constraints if the SOS1 constraints do not overlap
  • constraints/SOS1/autosos1branch to switch to SOS1 branching if the SOS1 constraints do not overlap
  • constraints/SOS1/conflictprop to define whether to use conflict graph propagation
  • constraints/SOS1/bipbranch to branch on a complete bipartite subgraph of the conflict graph
  • constraints/SOS1/boundcutsdepth to define the node depth of separating bound (clique) cuts
  • constraints/SOS1/boundcutsfreq to define the frequency for separating bound (clique) cuts
  • constraints/SOS1/boundcutsfromgraph to define whether to separate bound (clique) inequalities from the conflict graph
  • constraints/SOS1/boundcutsfromsos1 to define whether to separate bound (clique) inequalities from SOS1 constraints
  • constraints/SOS1/fixnonzero: If neighborhood branching is used, then fix the branching variable (if positive in sign) to the value of the feasibility tolerance
  • constraints/SOS1/implcutsdepth to define the node depth of separating implied bound cuts
  • constraints/SOS1/implcutsfreq to define the frequency for separating implied bound cuts
  • constraints/SOS1/implprop to define whether to use implication graph propagation
  • constraints/SOS1/maxaddcomps to define the maximal number of complementarity constraints added per branching node
  • constraints/SOS1/maxboundcuts to define the maximal number of bound (clique) cuts separated per branching node
  • constraints/SOS1/maxboundcutsroot to define the maximal number of bound (clique) cuts separated per iteration in the root node
  • constraints/SOS1/maximplcuts to define the maximal number of implied bound cuts separated per branching node
  • constraints/SOS1/maximplcutsroot to define the maximal number of implied bound cuts separated per iteration in the root node
  • constraints/SOS1/maxextensions to define maximal number of extensions that will be computed for each SOS1 constraint in presolving
  • constraints/SOS1/maxsosadjacency to define that the adjacency matrix of the conflict graph is not created in presolving if the number of SOS1 variables is too large
  • constraints/SOS1/maxtightenbds to define the maximal number of bound tightening rounds per presolving round
  • constraints/SOS1/neighbranch to branch on a neighborhood of the conflict graph
  • constraints/SOS1/nstrongiter to define the maximal number LP iterations to perform for each strong branching round
  • constraints/SOS1/nstrongrounds to define the maximal number of strong branching rounds to perform for each node (only available for neighborhood and bipartite branching)
  • constraints/SOS1/sos1branch to branch on a single SOS1 constraint, i.e., a clique of the conflict graph
  • constraints/SOS1/sosconsprop to define whether to use SOS1 constraint propagation
  • constraints/SOS1/strthenboundcuts to define whether to strengthen bound (clique) cuts in case bound variables are available
  • constraints/SOS1/updateconflpresol to update the conflict graph during the presolving procedure
  • display/allviols to print all violated constraints of the best solution during checksol in the scip shell
  • heuristics/indicator/improvesols that turns on the improvement of external solutions by one-opt
  • heuristics/∗diving/lpresolvedomchgquot to determine the percentage of changed domains since previous LP to trigger an LP resolve [default: 0.15] (* stands for eight diving heuristics to support this feature)
  • heuristics/∗diving/lpsolvefreq to determine the frequency for resolving LP's during the execution of this heuristic [default: 1, use 0 for a dynamic setting based on the number of domain reductions] (* stands for eight diving heuristics to support this feature)
  • heuristics/shiftandpropagate/binlocksfirst to set if binaries without locks should be preferred in ordering
  • heuristics/shiftandpropagate/maxcutoffquot to select a maximum percentage of allowed cutoffs before stopping the heuristic (default is 0.0)
  • heuristics/shiftandpropagate/selectbest to trigger if shiftandpropagate should select the best candidate in every round (set to FALSE for static order) (default is FALSE)
  • limits/autororestart for triggering an automatic restart after this many nodes, or -1 for no auto restart [default is -1]
  • limits/softtime to set a soft time limit (active only after first primal solution was found)
  • misc/allowobjprop to allow objective function propagation
  • misc/allowdualreds to allow dual reductions
  • misc/outputorigsol to control whether at the end of a command line run the solution should be output in the orignal space
  • numerics/checkfeastolfac to scale feasibility tolerance when checking the feasibility of best found solution after the solving process finished (e.g., checksol in scip shell)
  • separating/cutselrestart for cut selection during restart copy process (age, activity quotient) [default is a]
  • separating/cutselsubscip for cut selection for sub SCIPs (age, activity quotient) [default is a]
  • separating/disjunctive/maxconsdelay to delay separation of disjunctive cuts if number of SOS1 constraints is larger than predefined value
  • separating/disjunctive/maxdepth to define the node depth of separating disjunctive cuts
  • separating/disjunctive/maxinvcuts to define the maximal number of disjunctive cuts investigated per iteration in a branching node
  • separating/disjunctive/maxinvcutsroot to define the maximal number of disjunctive cuts investigated per iteration in the root node
  • separating/disjunctive/maxrank to define the maximal permissible rank of a disjunctive cut that could not be scaled to integral coefficients
  • separating/disjunctive/maxrankintegral to define the maximal permissible rank of a disjunctive cut that could be scaled to integral coefficients
  • separating/disjunctive/maxrounds to define the maximal number of separation rounds of disjunctive cuts in a branching node
  • separating/disjunctive/maxweightrange to define the maximal valid range of simplex tableau row weights

Data structures

  • new enum SCIP_CONFIDENCE_LEVEL for different levels of confidence for statistical tests.
  • new struct SCIP_DIVESET that bundles options for SCIP's diving heuristics; all hard diving heuristics (those without obj at the beginning) include diveset and implement only the scoring callback.
  • rename all file *_vbc.? to the more generic *_visual.?
  • moved buffer memory handling to blockmemory/memory.?; remove files type_buffer.h, struct_buffer.h buffer.h buffer.c; removed functions SCIP*buffer*() from scip.? and replaced them by macros; redesigned buffer interface to be similar to block memory; added checks for strange sizes

Testing

  • added scripts and targets for testing with xpress (see Makefile section)

Build system

Makefile

  • new parameter DELHEADERS for uninstall-target: scip headers are only removed when invoking make uninstall DELHEADERS=true
  • added scripts check_xpress.awk, check_xpress.sh, evalcheck_xpress.sh and check_cluster_xpress.sh and target testclusterxpress and testxpress

Fixed bugs

  • fixed bug in primal.c and tree.c by using SCIPinfinity() as a cutoffbound to delete child nodes
  • fixed bug in lp.c which leads to wrong primal and dual feasibility
  • fixed wrong handling of infinite activities and primal values in sepastore.c and lp.c
  • fixed bug that led to an erroneous warning about the clock type
  • fix behavior of make install which now sets symbolic links and short links to binaries and libraries
  • fix bug which lead to wrong global bound tightenings in prop_genvbounds.c
  • fix call to random generator for Windows operating systems in misc.c
  • fixed again a bug in backward propagation of linear expressions in expression graph
  • NLP:
    • fixed bug in heur_nlpdiving.c: wrong counting of fix variables
    • fix wrong handling of SCIP_NLPSOLSTAT_LOCALINFEASIBLE solution status in nlp.c
    • fix characterization of logic or constraints in SCIP's NLP relaxation
  • Branching:
    • fixed wrong comparison when executing branching rule for external branching candidates
    • fix spatial branching on implicit integer variables
    • fix wrong comparisons of values larger/less than +/- SCIPinfinity() in branch.c, lp.c and sol.c
    • fixed problem with lpisrelax flag in probing mode when doing branch-and-price
  • Constraint Handlers:
    • try to handle fixings of multi-aggregated variable in cons_sos1 presolving and avoid error
    • fixed bug in pseudoboolean constraint handler about negated variables
    • fixed assert in cons_soc.c: now soc with 1 lhs variable are allowed
    • fixed wrong assert in cons_indicator (slack variables might be replaced by active variables that have nonzero objective)
    • fix late creation of auxiliary LP in cons_nonlinear.c, which lead to a segmentation fault with lpi_spx2.cpp
    • fixed bug in cons_abspower.c: do not generate cuts with infinity right-hand-side anymore
    • fixed setting of enforcement flag for constraints created by reformulation in nonlinear constraint handlers
    • fixed bug in cons_indicator with handling local bounds
  • Memory:
  • Interval arithmetic:
    • fix handling of infinite intervals in SCIPintervalIsEmpty()
    • fixed bug in intervalarith.c: bivariate quadratic equations may have been solved wrongly if second variable is unbounded
  • Quadratic Constraints:
    • fix wrong sorting of bilinear terms in cons_quadratic
    • fix potentially tightening of LB/UB of a variable to +/- infinity in cons_quadratic
    • fixed bug in cons_quadratic.c which leads to an overflow when SCIP allocates memory for a dense matrix
    • fixed bug in cons_quadratic.c: do not generate linearization cuts for disabled constraints
    • fix missing clean phase of bilinear terms with zero coefficient in cons_quadratic.c