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
add SCIPcomputeHyperplaneThreePoints() to compute a hyperplane containing three given 3-dimensional points
SCIPsolveLinearProb() now uses a 1-dimensional matrix representation
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
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
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
avoid potential comparisons of different infinity values by adjusting the LP solution value
started support for user-defined operators in expression trees/graphs (see SCIPexprCreateUser()), interface will likely change again in future SCIP versions
new methods for mixed inter linear matrix access (see pub_matrix.h) added
SCIPaddDiveBoundChange() to add a diving bound change to the diving bound change storage of SCIP together with the information if this is a bound change for the preferred direction or not, to be used by constraint handlers inside the getDiveBdChgs-callback
SCIPcheckParam{Bool,Char,...}() to check whether a parameter value is within the feasible domain
Quadratic:
SCIPchgLhsQuadratic(), SCIPchgRhsQuadratic(), SCIPchgLinearCoefQuadratic(), SCIPchgSquareCoefQuadratic(), and SCIPchgBilinCoefQuadratic() to modify quadratic constraints during problem creation
SCIPgetFeasibilityQuadratic() and SCIPgetActivityQuadratic() to get the feasibility and activity of a quadratic constraint in a given solution
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