Release notes for SCIP 0.9

SCIP 0.9.0

Features

• the EXITSOL callback of the plugins is now called before the LP and the global cut pool are freed
• Primal Heuristics:
  • new primal heuristics rens, mutation and veclendiving
  • primal heuristics that run before the node is solved now know already whether the LP will be solved at the current node or not
• Heuristics:
  • new heuristic intshifting (ID character i)
  • 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
  • slightly modified crossover and rins heuristics
  • improved performance of intdiving heuristic
  • improved heuristic octane and 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)
  • ID character for intdiving heuristic is now I
• Separation and Cuts:
  • c-MIR cuts try now to scale the cut to integral values; however, cuts are still generated if this fails
  • 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
  • modified c-MIR cut separator to more closely resemble the original version of Marchand and Wolsey
• Constraint:
  • possibility of SAT-like restarts after a number of conflict constraints have been found
  • improved presolving of and, or and xor constraints
  • implemented additional dual presolving in linear constraint handler
  • slightly modified presolving of varbound constraint handler

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

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

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 <= n, instead of maxsols < 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 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 <= 10*z + 5 and x <= -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
• 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 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 infeasible/bound-exceeding LP conflict analysis if the bounds were relaxed in diving (happens in intshifting heuristic)
• Separation:
  • 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
  • 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
• Cmir Cut Separator:
  • too large deltas are now also rejected in c-MIR cut separation
  • 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 in cmir cut separator with weights fixed to zero, thus making the current aggregation invalid
  • fixed bug in cmir cut separator with wrong calculation of cut efficacies