SCIP
Solving Constraint Integer Programs
Release notes for SCIP 0.9
SCIP 0.9.0
Features
- primal heuristics that run before the node is solved now know already whether the LP will be solved at the current node or not
- the EXITSOL callback of the plugins is now called before the LP and the global cut pool are freed
- possibility of SAT-like restarts after a number of conflict constraints have been found
- in the root node of the very first run, heuristics with timing AFTERNODELPNODE, AFTERLPPLUNGE, AFTERPSEUDONODE, and AFTERPSEUDOPLUNGE are now called before the enforcement of the constraint handlers, in particular before the branching rules; in this way, the branching rule can already benefit from a tighter primal bound
- if a heuristic found a better solution after the LP loop (and in particular the AFTERNODE heuristics in the root node of the very first run, see above), domain propagation and LP solving is triggered again; this allows for additional reduced cost tightening and other dual propagations
- hard-coded relative objective gain to consider a separation loop to be stalling is now changed from 1e-3 to 1e-4, which means that separation is not aborted as early as before
- Plugins
- new primal heuristic "rens"
- new primal heuristic "mutation"
- slightly modified crossover and rins heuristics
- improved presolving of and, or and xor constraints
- improved performance of intdiving heuristic
- new primal heuristic "veclendiving"
- improved heuristic "octane"
- improved heuristic "shifting"
- slightly modified rens and localbranching heuristics
- modified guided diving heuristic such that it equals the original version of the heuristic (i.e., round in direction of the current incumbent solution instead of the average of all primal feasible solutions)
- modified c-MIR cut separator to more closely resemble the original version of Marchand and Wolsey
- implemented additional dual presolving in linear constraint handler
- slightly modified presolving of varbound constraint handler
- c-MIR cuts try now to scale the cut to integral values; however, cuts are still generated if this fails
- ID character for intdiving heuristic is now 'I'
- new heuristic "intshifting" (ID character 'i')
Interface changes
New and changed callbacks
- new parameter "solinfeasible" for constraint handler callback methods ENFOLP and ENFOPS
- replaced callback parameter "inlploop" and "inplunging" by "heurtiming" in SCIP_DECL_HEUREXEC
- slightly changed the meaning of the result codes returned by external relaxators: if they modify the LP or tighten bounds of variables, they are not automatically be called again (it is assumed that they already made use of these changes). They are only called again, if they returned SCIP_SUSPENDED or if some other plugin modified the LP.
Deleted and changed API methods
- new parameter "escapecommand" for SCIPdialoghdlrAddHistory()
- renamed all occurences of "removeable" by the correct English word "removable": SCIPconsIsRemovable(), SCIPsetConsRemovable(), SCIPvarIsRemovable(), SCIPcolIsRemovable(), SCIProwIsRemovable()
- new parameter "sticktonode" in SCIPcreateCons(), SCIPcreateConsAnd(), SCIPcreateConsBounddisjunction(), SCIPcreateConsKnapsack(), SCIPcreateConsLinear(), SCIPcreateConsLogicor(), SCIPcreateConsOr(), SCIPcreateConsVarbound(), SCIPcreateConsXor(), SCIPcreateConsSetpart(), SCIPcreateConsSetpack(), SCIPcreateConsSetcover(): usually, you should set this to FALSE; if you want to add constraints as node markers with node data and, e.g., use the "activate" and "deactivate" callbacks to get informed about the activation and deactivation of the node, you should set this flag to TRUE in order to make sure, that the constraint will always be associated to the node and not moved to a more global node if this would be possible
- removed method SCIPgetVarData(); use SCIPvarGetData() from pub_var.h instead
- new calls SCIPgetLPBInvCol() and SCIPgetLPBInvACol() to access the basis inverse and simplex tableau columnwise
- new parameter "ndomredsfound" of SCIPpropagateProbing()
- new parameters "fixintegralrhs", "maxfrac", "mksetcoefs" and "fracnotinrange" in SCIPcalcMIR()
- modified SCIPfixVar() such that in problem creation stage it will change the bounds as requested even if the fixing value is outside of the current bounds
- slightly changed semantics of SCIPaddConsNode() and SCIPaddConsLocal(), such that a constraint which is added to the root node now enters the global problem (and is still existing after a restart)
- replaced parameters "pseudonodes", "duringplunging", "duringlploop" and "afternode" by "timingmask" in SCIPincludeHeur() and constructor of ObjHeur() class use the following table to translate old settings into the new timingmask:
| PSEUDONODES | DURINGPLUNGING | DURINGLPLOOP | AFTERNODE | timingmask |
|---|---|---|---|---|
| FALSE | FALSE | FALSE | FALSE | SCIP_HEURTIMING_BEFORENODE |
| TRUE | FALSE | FALSE | FALSE | SCIP_HEURTIMING_BEFORENODE |
| FALSE | TRUE | FALSE | FALSE | SCIP_HEURTIMING_BEFORENODE |
| TRUE | TRUE | FALSE | FALSE | SCIP_HEURTIMING_BEFORENODE |
| FALSE | FALSE | TRUE | FALSE | SCIP_HEURTIMING_BEFORENODE | SCIP_HEURTIMING_DURINGLPLOOP |
| TRUE | FALSE | TRUE | FALSE | SCIP_HEURTIMING_BEFORENODE | SCIP_HEURTIMING_DURINGLPLOOP |
| FALSE | TRUE | TRUE | FALSE | SCIP_HEURTIMING_BEFORENODE | SCIP_HEURTIMING_DURINGLPLOOP |
| TRUE | TRUE | TRUE | FALSE | SCIP_HEURTIMING_BEFORENODE | SCIP_HEURTIMING_DURINGLPLOOP |
| FALSE | FALSE | FALSE | TRUE | SCIP_HEURTIMING_AFTERLPPLUNGE |
| TRUE | FALSE | FALSE | TRUE | SCIP_HEURTIMING_AFTERPLUNGE |
| FALSE | TRUE | FALSE | TRUE | SCIP_HEURTIMING_AFTERLPNODE |
| TRUE | TRUE | FALSE | TRUE | SCIP_HEURTIMING_AFTERNODE |
| FALSE | FALSE | TRUE | TRUE | SCIP_HEURTIMING_AFTERLPPLUNGE | SCIP_HEURTIMING_DURINGLPLOOP |
| TRUE | FALSE | TRUE | TRUE | SCIP_HEURTIMING_AFTERPLUNGE | SCIP_HEURTIMING_DURINGLPLOOP |
| FALSE | TRUE | TRUE | TRUE | SCIP_HEURTIMING_AFTERLPNODE | SCIP_HEURTIMING_DURINGLPLOOP |
| TRUE | TRUE | TRUE | TRUE | SCIP_HEURTIMING_AFTERNODE | SCIP_HEURTIMING_DURINGLPLOOP |
New API functions
- SCIPgetVerbLevel()
- SCIPescapeString()
- SCIPgetGlobalCutpool(), SCIPgetPoolCuts(), SCIPcutpoolGetCuts(), SCIPcutGetRow() and SCIPcutGetAge()
- SCIPconsGetNLocksPos() and SCIPconsGetNLocksNeg()
Command line interface
- command shell now understands escape characters ",' and \ which makes it possible to read in files with spaces in the name
Interfaces to external software
- updated XPress interface to XPress-MP 17 (contributed by Michael Perregaard)
Changed parameters
- changed default value of "heuristics/octane/usediffray" to FALSE
- removed parameter "heuristics/octane/usediffbwray"
- renamed parameter "heuristics/octane/useavgray" to "heuristics/octane/useavgnbray"
- changed default value of "heuristics/rens/binarybounds" to TRUE
- changed default value of "heuristics/octane/freq" to -1 in order to deactivate Octane
- parameter "heuristics/feaspump/maxsols" is now strict, i.e., if n solutions were already found, the feasibility pump starts to work only if maxsols <lt;= n, instead of maxsols <lt; n
New parameters
- "conflict/restartnum" and "conflict/restartfac"
- "heuristics/octane/useavgray"
- "heuristics/octane/useavgwgtray"
- "limits/absgap" to define an absolute gap limit
- "separating/cmir/aggrtol"
- "separating/cmir/densityscore"
- "separating/cmir/fixintegralrhs"
- "separating/maxruns"
- "presolving/restartminred" which forbids another restart if the last one was not successful enough
- "propagating/abortoncutoff"
- "reading/zplreader/changedir" to control behavior of path switching of ZIMPL file reader
- "reading/zplreader/parameters" to pass additional parameters to ZIMPL
Build system
Makefile
- added ncurses to the readline entries in the make/make.* files
- added quotes to sed expressions in Makefile (needed under Windows)
- modified makefiles for Windows/Intel
- added automatic query script in the Makefile for soft-link names
Fixed bugs
- fixed bug with adding constraints with INITIAL=true and separating them afterwards, which lead to a second addition of the constraint's relaxation in the child node
- fixed bug in cmir cut separator, that 8*delta was not tried
- fixed bug in cmir cut separator with wrong sign of slack in row score function
- fixed bug with string pointer copy instead of string content duplication in constructors of C++ wrapper classes
- fixed bug in CPLEX interface with basis access methods that dualopt has to be called for more error status codes
- fixed bug with inserting two variable bounds of the same type on the same variable with the same bounding variable but with different sign of coefficient (e.g., x <lt;= 10*z + 5 and x <lt;= -5*z + 10); in previous version, one of the two was removed, although both have a useful meaning; now, we keep both and detect a stronger global bound in the implication graph presolving
- fixed bug in cmir cut separator with weights fixed to zero, thus making the current aggregation invalid
- fixed bug that SCIPvarGetAvgSol() always returned the upper bound (affected guided diving heuristic)
- fixed bug in RENS, RINS, Local Branching, Crossover and Mutation heuristics with wrong variable - subvariable assignments
- fixed bug in cmir cut separator with wrong calculation of cut efficacies
- objective function is now also checked for integrality after problem transformation (fixed a bug that a solution which was generated between transformation and presolving for an integral objective function did not reduce the cutoff bound by one)
- fixed a bug with cmir cut efficacy calculation (however, on my first tests, the performance reduced slightly!)
- fixed bug in infeasible/bound-exceeding LP conflict analysis if the bounds were relaxed in diving (happens in intshifting heuristic)
- too large deltas are now also rejected in c-MIR cut separation
- separation LPs are now immediately resolved after a bound change was generated by a cut separator; before, the separation round was prematurely aborted, which means that a separation round limit was sometimes reached very quickly and some of the separators were not even called a single time