Release notes for SCIP 1.0

# 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`

- new node selection rule
- 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*

- modified
- 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()

- new parameter
- 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

- removed parameter
- 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