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
- 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 todisplay 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 parametersconstraints/sos1/neighbranch
,constraints/sos1/bipbranch
, andconstraints/sos1/sos1branch
)constraints/sos1/depthimplanalysis
to limit the number of recursive calls of implication graph analysisconstraints/sos1/perfimplanalysis
to perform an implication graph analysis to deduce variable fixings and additional SOS1 constraints (this parameter replaces the old parameterconstraints/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
- avoid potential comparisons of different infinity values by adjusting the LP solution value
- SCIPintervalSign(), SCIPintervalAbs(), SCIPintervalMax(), SCIPintervalMin(), SCIPexprgraphGetNodePolynomialMonomialCurvature(), and SCIPexprgraphTightenNodeBounds() need an infinity value to decide whether an interval is empty or not
- SCIPgetFeasibilityQuadratic() and SCIPgetActivityQuadratic() returns now a
SCIP_RETCODE
and needs an additionalSCIP_Real*
to store the result - methods which support statistical tests in pub_misc.h, SCIPstudentTGetCriticalValue(), SCIPcomputeTwoSampleTTestValue() etc.
- SCIPsolveLinearProb() solves a linear problem of the form Ax=b for a regular square matrix A
- Added parameter
freesubscip
to SCIPapplyProximity() - Data structures:
- Renamed method SCIPdigraphGetSuccessorsDatas() to SCIPdigraphGetSuccessorsData()
- Renamed method SCIPdigraphGetNodeDatas() to SCIPdigraphGetNodeData()
- Renamed method SCIPdigraphSetNodeDatas() to SCIPdigraphSetNodeData()
- Constraint Handlers:
- Renamed method SCIPconshdlrGetPropTimingmask() to SCIPconshdlrGetPropTiming()
- new method SCIPconshdlrSetPropTiming()
- Removed method SCIPconshdlrIsPresolvingDelayed()
- Removed method SCIPconshdlrWasPresolvingDelayed()
- SCIPmakeSOS1sFeasible() based on solution values, fixes variables to zero to turn all SOS1 constraints feasible
- removed
delay(presol)
parameter from SCIPinclude{Conshdlr,Presol,Prop}() and added(presol)timing
parameter - new parameter
presoltiming
for method SCIPpresolCons() - SCIPvarIsSOS1() returns whether some variable is involved in an SOS1 constraint
- SCIPgetConflictgraphSOS1() gets conflict graph of SOS1 constraints
- Added parameter
presoltiming
to SCIPpropCumulativeCondition() - Removed parameter
delaypos
from SCIPsetConshdlrPresol() - Added parameter
presoltiming
to SCIPsetConshdlrPresol() - Removed parameter
delaypos
from SCIPincludeConshdlr() - Added parameter
presoltiming
to SCIPincludeConshdlr() - Added parameter
consgetdivebdchgs
to SCIPincludeConshdlr() to provide a divebdchg-callback for the constraint handler to include
- Branching Rules:
- Added parameter
forcestrongbranch
to SCIPselectVarStrongBranching() - Added parameter
executebranching
SCIPexecRelpscostBranching() - Added parameters
ndomredsdown
andndomredsup
to SCIPgetVarStrongbranchWithPropagation()
- Added parameter
- LP and Cutting Planes:
- Added parameters
inds
andninds
to SCIPgetLPBInvRow(), SCIPgetLPBInvCol(), SCIPgetLPBInvARow(), SCIPgetLPBInvACol(), and SCIPcalcStrongCG() - Added parameters
maxweight
,weightinds
,nweightinds
, androwlensum
to SCIPcalcMIR()
- Added parameters
- Variables:
- SCIPvarGetNodeSOS1() returns node of SOS1 variable in the conflict graph
- SCIPnodeGetVarSOS1() returns SOS1 variable associated to some given node in the conflict graph
- Removed method SCIPvarGetNBinImpls()
- Presolving:
- Removed parameter
delaypos
from SCIPincludePresolBasic() - Added parameter
presoltiming
to SCIPincludePresolBasic() - Removed parameter
delaypos
from SCIPincludePresol() - Added parameter
presoltiming
to SCIPincludePresol() - Removed parameters
presoldelay
andpresoltiming
from SCIPincludePresol() - Removed parameters
presoldelay
andpresoltiming
from SCIPsetPropPresol()
- Removed parameter
- Misc:
- Added parameter
isequation
to SCIPaddClique() - Removed parameter
writeimplications
from SCIPwriteCliqueGraph() - Removed method SCIPallocBufferSize()
- Removed method SCIPduplicateBufferSize()
- Removed method SCIPreallocBufferSize()
- Removed method SCIPfreeBufferSize()
- Removed method callback SCIPdialogExecConflictgraph()
- Added parameter
New API functions
- 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
- SCIPcomputeArraysIntersection() to compute the set intersection of two ordered arrays
- SCIPcomputeArraysSetminus() to compute the set difference of two ordered arrays
- SCIPcutGetLPActivityQuot() in pub_cutpool.h to get the potion of LP's where this cut was sharp in an optimal basis.
- SCIPpresolGetTiming(), SCIPpresolSetTiming(), SCIP{conshdlr,prop}GetPresolTiming(), and SCIP{conshdlr,prop}SetPresolTiming()
- SCIPdigraphSetNSuccessors() sets the number of successors of some digraph node to a given value
- Diving:
- SCIPcreateDiveset() to add a diveset to a heuristic. Heuristics may have multiple divesets under different names
- SCIPperformGenericDivingAlgorithm() that performs diving with periodic LP resolve according to the diveset argument.
- Constraints:
- new setter function SCIPsetConshdlrGetDiveBdChgs() in scip.h to set dive bound change callback for this constraint handler
- 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
- SCIPchgCoefLinear() and SCIPdelCoefLinear() to modify linear constraint during problem creation
- Memory:
- BMSallocClearBlockMemoryArray()/SCIPallocClearBlockMemoryArray() and BMSallocClearBufferMemoryArray(), SCIPallocClearBufferArray() to allocate arrays that are initialized to 0
- SCIPbuffermem() to get buffer memory;
- Sort:
- added new sorting functions SCIPsortRealRealRealBoolBoolPtr(), SCIPsortDownRealRealRealBoolBoolPtr()
- added new sorting functions SCIPsortIntIntIntReal(), SCIPsortDownIntIntIntReal(), SCIPsortRealIntInt(), SCIPsortDownRealIntInt()
- Param:
- SCIPwriteParam() to write a single parameter to a file
- 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
- SCIPaddSquareLinearization(), SCIPaddSquareSecant(), SCIPaddBilinLinearization() and SCIPaddBilinMcCormick() in cons_quadratic.h to compute linear under- and overestimation for bilinear and quadratic terms
Command line interface
- extended variable branching statistics and statistic output in the interactive shell (see Statistic section)
- submenu for setting
vbc
settings renamed tovisual
- 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
andremovable
are recognized; for constraints,initial
,separate
,enforce
,check
,propagate
,dynamic
andremovable
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
oremphasis: heuristics off
. - Renamed parameters:
vbc/filename
tovisual/vbcfilename
vbc/realtime
tovisual/realtime
vbc/dispsols
tovisual/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 testsbranching/relpscost/higherrortol
to define the highest reliability threshold for relative error based reliabilitybranching/relpscost/lowerrortol
to define a lower reliability threshold for relative error based reliabilitybranching/relpscost/nlscoreweight
for weight of nonlinear score when branching on MINLPsbranching/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 appliedbranching/relpscost/userelerrorreliability
to enable relative error based reliabilitybranching/relpscost/skipbadinitcands
for skipping strong-branching candidates whose estimated gain is significantly worse than the one of the locally best (sb or pseudo) candidateconstraints/linear/multaggrremove
to perform multi-aggregations in linear constraint handler only if the constraint can be removed afterwardsconstraints/linear/rangedrowpropagation
to disabled newly implemented propagtion algorithm for ranged rows and equationsconstraints/quadratic/advanced/interiorcomputation
to select the way of computing and interior point for gauge cutsconstraints/quadratic/gaugecuts
to enable convex quadratics to generate gradients cuts which are supportingconstraints/soc/generalsocupgrade
to allow general quadratics to be upgraded to socconstraints/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 nodeconstraints/SOS1/addcompsdepth
to define the maximal depth for adding complementarity constraintsconstraints/SOS1/addcompsfeas
to define a minimal feasibility value for local complementarity constraints in order to be added to the branching nodeconstraints/SOS1/autocutsfromsos1
to automatically switch to separating bound cuts from SOS1 constraints if the SOS1 constraints do not overlapconstraints/SOS1/autosos1branch
to switch to SOS1 branching if the SOS1 constraints do not overlapconstraints/SOS1/conflictprop
to define whether to use conflict graph propagationconstraints/SOS1/bipbranch
to branch on a complete bipartite subgraph of the conflict graphconstraints/SOS1/boundcutsdepth
to define the node depth of separating bound (clique) cutsconstraints/SOS1/boundcutsfreq
to define the frequency for separating bound (clique) cutsconstraints/SOS1/boundcutsfromgraph
to define whether to separate bound (clique) inequalities from the conflict graphconstraints/SOS1/boundcutsfromsos1
to define whether to separate bound (clique) inequalities from SOS1 constraintsconstraints/SOS1/fixnonzero
: If neighborhood branching is used, then fix the branching variable (if positive in sign) to the value of the feasibility toleranceconstraints/SOS1/implcutsdepth
to define the node depth of separating implied bound cutsconstraints/SOS1/implcutsfreq
to define the frequency for separating implied bound cutsconstraints/SOS1/implprop
to define whether to use implication graph propagationconstraints/SOS1/maxaddcomps
to define the maximal number of complementarity constraints added per branching nodeconstraints/SOS1/maxboundcuts
to define the maximal number of bound (clique) cuts separated per branching nodeconstraints/SOS1/maxboundcutsroot
to define the maximal number of bound (clique) cuts separated per iteration in the root nodeconstraints/SOS1/maximplcuts
to define the maximal number of implied bound cuts separated per branching nodeconstraints/SOS1/maximplcutsroot
to define the maximal number of implied bound cuts separated per iteration in the root nodeconstraints/SOS1/maxextensions
to define maximal number of extensions that will be computed for each SOS1 constraint in presolvingconstraints/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 largeconstraints/SOS1/maxtightenbds
to define the maximal number of bound tightening rounds per presolving roundconstraints/SOS1/neighbranch
to branch on a neighborhood of the conflict graphconstraints/SOS1/nstrongiter
to define the maximal number LP iterations to perform for each strong branching roundconstraints/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 graphconstraints/SOS1/sosconsprop
to define whether to use SOS1 constraint propagationconstraints/SOS1/strthenboundcuts
to define whether to strengthen bound (clique) cuts in case bound variables are availableconstraints/SOS1/updateconflpresol
to update the conflict graph during the presolving proceduredisplay/allviols
to print all violated constraints of the best solution during checksol in the scip shellheuristics/indicator/improvesols
that turns on the improvement of external solutions by one-optheuristics/∗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 orderingheuristics/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 propagationmisc/allowdualreds
to allow dual reductionsmisc/outputorigsol
to control whether at the end of a command line run the solution should be output in the orignal spacenumerics/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 (a
ge, activityq
uotient) [default isa
]separating/cutselsubscip
for cut selection for sub SCIPs (a
ge, activityq
uotient) [default isa
]separating/disjunctive/maxconsdelay
to delay separation of disjunctive cuts if number of SOS1 constraints is larger than predefined valueseparating/disjunctive/maxdepth
to define the node depth of separating disjunctive cutsseparating/disjunctive/maxinvcuts
to define the maximal number of disjunctive cuts investigated per iteration in a branching nodeseparating/disjunctive/maxinvcutsroot
to define the maximal number of disjunctive cuts investigated per iteration in the root nodeseparating/disjunctive/maxrank
to define the maximal permissible rank of a disjunctive cut that could not be scaled to integral coefficientsseparating/disjunctive/maxrankintegral
to define the maximal permissible rank of a disjunctive cut that could be scaled to integral coefficientsseparating/disjunctive/maxrounds
to define the maximal number of separation rounds of disjunctive cuts in a branching nodeseparating/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 withoutobj
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
foruninstall
-target: scip headers are only removed when invokingmake uninstall DELHEADERS=true
- added scripts check_xpress.awk, check_xpress.sh, evalcheck_xpress.sh and check_cluster_xpress.sh and target
testclusterxpress
andtestxpress
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
- fixed bug in prop_symmetry.c, where an incorrect weak symmetry handling constraint got added.
- 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:
- fix potential memory leak in SoPlex LP interfaces when setting invalid basis
- fix potential memory leak in method SCIPgetConsCopy()
- fix potential memory leak in method detectRedundantConstraints() of the knapsack constraint handler
- 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