SCIP 1.0.0

Features

SCIP now has a couple of specialized settings, all called scip_*.set
SCIP is now compatible to the Exception branch of SoPlex
if possible, objective function is scaled to make objective value integral with gcd 1
slightly modified automatic constraint aging strategy
new C templates disp_xxx.h and dialog_xxx.h and C++ wrapper classes objdisp.h and objdialog.h, respectively
modified reader sol, st. files which where created via typing the order of commands set log *.sol, disp sol var -, set log cplex.log in Cplex can now be read
new dummy LP interface lpi_none.c; useful for running SCIP without a LP solver
Presolver:
- modified probing presolver to do multiple cycles if called in subsequent runs
- changed sort algorithm in probing presolver
Node selection:
- new node selection rule estimate (best estimate search)
- new node selection rule hybridestim
Documentation:
- the doxygen documentation now has HowTo's for all plugin types
- the doxygen documentation now contains a FAQ
- the documentation has now a TAB Modules; there you can find list of available constraint handles, presolvers, propagators, lpi interfaces, file readers and so on
Time:
- time limit is now forwarded to lp solving algorithm
- presolving, cut separation, primal heuristics and strong branching now better respect time limit
Heuristics:
- best estimate search is now used in all large neighborhood search heuristics
- new improvement heuristic oneopt
- new heuristic actconsdiving following an idea of John Chinneck
Separation and Cuts:
- modified cut selection code
- cut conversion into linear constraints after a restart now works better
- added flow cover separator
- gomory cuts are now also separated for integral slack variables
- less aggressive in Gomory cut separation
- strong CG cuts are now also separated for integral slack variables

Performance improvements

greatly improved performance of LP file reader by replacing string copies with pointer copies
removed performance bottleneck with non-bfs based node selectors and large leaf queues at the cost of a small memory overhead (2 ints per node in the leaf queue); this improves performance quite a bit on instances that take a large number of branching nodes
improved performance of linear constraint propagation by delaying some floor/ceil calculations
improved performance of clique cut separator

Interface changes

New and changed callbacks

new callback method SCIPdialogFree()

Deleted and changed API methods

slightly modified bound substitution heuristic in SCIPcalcMIR() and SCIPcalcStrongCG()
slightly less conservative in numerics for SCIPmakeRowIntegral()
linear and knapsack constraint handler may now deal with coefficients of value zero
new parameter maxbounddist for SCIPincludeSepa() and constructor ObjSepa()
new parameter restart for method SCIPfreeSolve()
calling SCIPwriteLP() is now possible in Solved Stage
SCIPwrite{LP,MIP} may no longer be called after solving, since the LP data structures may not be valid
All functions SCIP<datatype>Param() got a new parameter isadvanced. This does not influence the performance of SCIP, but the position of the parameter in the settings menu. Hence, if you do not care about this, you can assign any value to it. You should add the corresponding flag to the SCIP<datatype>Param() calls in your own source code.
Version:
- modified SCIP_SUBVERSION to be a number instead of a string (to be able to use SCIP_SUBVERSION >= ...)
- SCIPsubversion() now returns an int instead of a const char*
Tree and Nodes:
- new parameter estimate for SCIPcreateChild() giving an estimate for value of best feasible solution in the subtree to be created. One possibility is to use SCIPgetLocalOrigEstimate() for this value.
- removed method SCIPnodeGetPriority()
- removed parameter lowestboundfirst from SCIPincludeNodesel()
Branching:
- removed parameter branchdir from SCIPbranchVar()
- new parameters leftchild, eqchild and downchild for SCIPbranchVar()
- SCIPgetVarStrongbranch() now also returns lperror == TRUE if the solving process should be stopped, e.g., because of a time limit
Variable tightening:
- replaced methods SCIPvarGetClosestVlb() and SCIPvarGetClosestVub() from pub_var.h by new methods SCIPgetVarClosestVlb() and SCIPgetVarClosestVlb() in scip.h
- new parameter force for SCIPtightenVarLb() and SCIPtightenVarUb()

New API functions

SCIPreadSol()
SCIPwriteMIP()
SCIPgetLocalOrigEstimate() and SCIPgetLocalTransEstimate()
SCIPisStopped()
SCIProwIsInGlobalCutpool()
SCIPresetParams()
SCIPgetVarRedcost()
SCIPtightenVarLbGlobal() and SCIPtightenVarUbGlobal()
SCIPsepaGetMaxbounddist()
SCIPboundchgGetNewbound(), SCIPboundchgGetVar(), SCIPboundchgGetBoundchgtype(), SCIPboundchgGetBoundtype(), SCIPboundchgIsRedundant(), SCIPdomchgGetNBoundchgs(), SCIPdomchgGetBoundchg()
SCIPnodeUpdateLowerboundLP()
SCIPcalcNodeselPriority()
SCIPnodeGetEstimate()
SCIPnodeGetDomchg()
SCIPgetRootNode() (in combination with SCIPcutoffNode(), this allows the immediate finishing of the optimization)

Command line interface

default dialog menu now includes the commands set default and display parameters
added option to write node LP and MIP relaxations to LP file from interactive shell

Changed parameters

parameters are now separated into basic and advanced, the latter ones have been moved to extra submenus
priority parameters are now restricted to be in [INT_MIN/4,INT_MAX/4] to avoid overflow errors in comparison methods
increased priority of estimate node selector, such that this is the new default node selector
changed meaning of parameter setting nodeselection/childsel = l; old meaning is now called r
changed default value of conflict/maxvarsfac to 0.1
changed default value of conflict/useprop to TRUE
changed default value of conflict/useinflp to TRUE
changed default value of conflict/usepseudo to TRUE
changed default value of conflict/maxlploops to 2
changed default value of conflict/lpiterations to 10
changed default value of conflict/interconss to -1
changed default value of conflict/reconvlevels to -1
changed default value of conflict/settlelocal to FALSE
changed default value of constraints/linear/propfreq to 1
changed default values of heuristics/∗diving/backtrack to TRUE
changed default value of nodeselection/restartdfs/stdpriority to 10000
changed default value of numerics/boundstreps to 0.05 in order to avoid very long propagation loops on continuous variables
changed default value of presolving/restartfac to 0.05
changed default value of presolving/restartminred to 0.10
changed default value of separating/objparalfac to 0.01 for performance reasons
changed default value of global separating/maxbounddist to 1.0
changed default value of separating/objparalfac to 0.0001

New parameters

conflict/enable to globally enable or disable conflict analysis
constraints/linear/maxcardbounddist and constraints/knapsack/maxcardbounddist
heuristics/∗diving/backtrack to activate 1-level backtracking for most of the diving heuristics
heuristics/feaspump/maxstallloops
nodeselection/childsel to control the child selection
presolving/immrestartfac
separating/∗/maxbounddist to have individual maxbounddist parameters per separator
separating/clique/backtrackfreq to speed up clique cut separation in heuristic fashion
separating/redcost/continuous

Build system

Makefile

added version numbers to library files (There will be a softlink generated in the lib/ and bin/ directories without version number that point to the latest compiled version.)
added .exe extension to binaries of MinGW
removed the .static extension associated to the LINK variable from the Makefile system (If you want to build makefiles for shared library generation, use the OPT variable. For example, you could create a makefile make/make.linux.x86.gnu.opt-shared and compile it with make OPT=opt-shared.)
Defaults and Options:
- modified the default LP solver to be SoPlex instead of CPLEX
- added LPS=none for compiling SCIP without a LP solver
- made ZIMPL=true the default; if you do not want to include ZIMPL support, call make ZIMPL=false

Fixed bugs

fixed bug in rowScale() concerning deletion of almost zero coefficients
weakened assert in primal.c in order to avoid numerical troubles
fixed bug with too long variable names
fixed bug with strange user descriptions of plugins
changed position of some asserts to prevent segmentation faults
SCIPgetAvgPseudocostCount() and SCIPgetAvgPseudocostCountCurrentRun() now return the average over all integer variables instead of all variables, since pseudo costs are not recorded for continuous variables
fixed wrong sorting of plugins with priorities close to INT_MIN or INT_MAX
replaced line by read in Makefile, since line is non-standard
fixed bug with branching rules that produce only one child with no changes to the problem
fixed bug that external relaxator is not reset appropriately for a new problem instance
removed wrong assert in function paramWrite()
fixed bug with uninitialized in check.awk
fixed bug in ZIMPL file reader for multiple occurrences of a single variable in the objective function
fixed bug with deleting variables from the transformed problem that are contained in the implication graph
fixed bug in root reduced cost fixing propagator that leads to an empty domain for a variable as a proof of optimality of the current incumbent
fixed bug with fractional coefficients of binary variables in cont –> impl int upgrading
Solution:
- fixed bug with aggregated variables in debug solution test
- now it is possible to add original solutions
- fixed bugs with SCIPgetBestsol() returning NULL after a restart with user objective limit
- fixed wrong status code in presence of user objective limit and a feasible solution that is not better than the limit
Bounds:
- fixed bug with wrong bound changes of loose variables
- changed wrong assert in SCIPnodeAddBoundinfer()
- fixed bug in variable bounds search and insertion method
- fixed bug regarding modifying bounds in original problem if negated original variables exist
- fixed bug with multiple pending bound changes on some variable
Separator:
- fixed bug in integer objective separator with restarts
- fixed bug in integer objective separator with dynamic columns
Cuts:
- fixed bug that cut age was not reset to zero for violated cuts
- fixed bug in SCIPcutpoolAddNewRow() concerning update of minidx and maxidx of added row
- fixed numerical bug in rowScaling of lp.c, which possibly cut off feasible solutions
- significantly improved performance of c-MIR and Gomory cuts by caching closest VLB and VUB info
LP:
- fixed numerical buf with slightly different LP optimum after resolving due to probing/diving
- fixed bug in cmir and flowcover separator with variables which are currently not in the LP
- fixed bug with LP size management in probing if column generation is used
- fixed bug in LP file reader with row names identical to section keywords
- fixed potential bugs due to errors in resolving the LP after diving or probing
- fixed potential bugs in SCIPpriceLoop() and priceAndCutLoop(), st. now all LP solution stati are handled appropriately
- fixed potential bug with non-existent LP in SCIPwrite{LP,MIP}
Constraint handler:
- removed wrong assert in bounddisjunction constraint enforcement
- fixed numerical bug in propagator of varbound constraint handler
- fixed bug in variable bound constraint handler with changing bounds on multi-aggregated variables
- fixed bug in linear constraint handler: only tight cuts are transformed into linear constraints after restart
- fixed bug in bounddisjunction constraint handler with propagation of multi-aggregated variables
- fixed bug with numerics in linear constraint handler due to non-representable BOUNDSCALETOL
- fixed bug with almost integral multi-aggregation in dual presolve of linear constraint handler
- fixed bug with numerics in update of min/maxactivity in linear constraint handler
Heuristics:
- fixed bug in intshifting and oneopt heuristic with variables which are currently not in the LP
- fixed bug with primal heuristics reducing the cutoff bound such that the current node is cut off
- fixed bug in oneopt heuristic: must not be called on pseudo nodes if continuous variables are present