Scippy

SCIP

Solving Constraint Integer Programs

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
  • 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:
  • 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:

New API functions

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