SCIP 0.7.9

Features

aging and cleanup now only remove non-basic columns and basic rows, s.t. resolving can be applied with 0 simplex iterations
probing is now also possible in presolving stage
it is now possible to create subnodes in probing and use backtracking to undo probing changes
it is now possible to interrupt and continue presolving
bounds of variables are included in the feasibility checks for solutions
support for barrier algorithm
included debugging module to check whether cutting planes cut off the optimal solution
if verblevel is at least NORMAL, an automatical check of the best solution is performed in the original problem, and an error message is displayed, if it violates an original constraint
due to the new constraint handler "cons_cumulative.{c,h}" SCIP can resource-constraint scheduling problem
Plugins
- new implementation of the feasibility pump heuristic by Timo Berthold (replaces old implementation); old implementation is now called "objfeaspump"; parameter names have been changed accordingly
- diving heuristics now compare their number of LP iterations with the number of node LP iterations instead of the total number (including their own) LP iterations
- new plugin: probing presolver
- new plugin: clique separator for clique cuts with at least 3 elements
- changed implementation of reliability value calculation in reliability branching; slightly modified influence of maximal total number of strong branching LP iterations in reliability branching
- changed implementation of maximal strong branching iterations calculation in reliability branching
- modified the automatic objfactor setting of feaspump heuristic to let the objective function have stronger influence
- changed implementation of automatic minplungedepth and maxplungedepth calculation in bfs node selector
- new plugin: implied bound cuts separator
- during probing, propagation of bounds is now always performed in linear constraint handler, ignoring the parameter "tightenboundsfreq"
- new implementation of the clique graph construction method in clique separator
- new constraint handler "cons_cumulative.{c,h}"

Examples and applications

added TSP example in examples/TSP

Interface changes

New and changed callbacks

new callback methods INITSOL and EXITSOL for variable pricers, primal heuristics, conflict handlers, relaxators, separators, propagators, event handlers, node selectors and display columns
callback method CONFLICTEXEC of conflict handlers receive additional parameters "dynamic" and "removeable"
constraint handler callback methods CONSLOCK and CONSUNLOCK are replaced by a single method CONSLOCK with the number of locks being positive or negative

Deleted and changed API methods

calling SCIPaddCut() with forcecut=TRUE will add the cut to the LP even if it is redundant
SCIPaddVarImplication() now also adds variable lower and upper bounds, if the implied variable is non-binary
SCIPvarLock(), SCIPvarLockDown(), SCIPvarLockUp(), SCIPvarLockBoth(), SCIPvarUnlock(), SCIPvarUnlockDown(), SCIPvarUnlockUp() and SCIPvarUnlockBoth() are replaced by SCIPaddVarLocks() which returns a RETCODE
SCIPvarLockDownCons(), SCIPvarLockUpCons(), SCIPvarUnlockDownCons() and SCIPvarUnlockUpCons() are replaced by SCIPlockVarCons() and SCIPunlockVarCons() which return a RETCODE
SCIPlockConsVars() and SCIPunlockConsVars() replaced with method SCIPaddConsLocks()
SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), SCIPvarGetLbLocal() and SCIPvarGetUbLocal() now return the corresponding values of the transformed problem or current subproblem even for original problem variables
removed method SCIPsolGetObj() - use SCIPgetSolOrigObj() or SCIPgetSolTransObj() instead
SCIPreadProb() does not free the current problem - this is done in SCIPcreateProb() now, which is usually called by a problem reader; in this way, a reader can generate "extra information" for the current problem, s.t. the full problem information can be distributed to different files read by different readers
SCIPgetVarStrongbranch() and SCIPgetVarStrongbranchLast() now have two additional parameters that can be used to check, whether the returned values are correct dual bounds
SCIPconshdlrGetNConss() is replaced by SCIPconshdlrGetNActiveConss() (returning the number of active constraints); method SCIPconshdlrGetNConss() does now return the total number of existing constraints, active and inactive
SCIPconshdlrGetStartNConss() is now called SCIPconshdlrGetStartNActiveConss()
SCIPconshdlrGetMaxNConss() is now called SCIPconshdlrGetMaxNActiveConss()
SCIPdisableConsNode() is replaced by SCIPdelConsNode()
SCIPdisableConsLocal() is replaced by SCIPdelConsLocal()
added new parameter "dynamic" to SCIPcreateCons() and all plugin methods SCIPcreateCons...()
SCIPvarGetProbvar(), SCIPvarGetProbvarBinary() now return the fixed or multi-aggregated variable instead of returning NULL or aborting with an error message; in SCIPvarGetProbvarBinary(), the fixing of a fixed variable does not influence the negation status anymore
SCIPvarGetProbvarBound() returns the multi-aggregated variable instead of aborting with an error message
SCIPvarGetProbvarSum() does not set *var to NULL for fixed variables anymore; it may also return a multi-aggregated variable instead of aborting with an error message
SCIPgetBinvarRepresentative() now returns the fixed or multi-aggregated variable instead of returning NULL or aborting with an error message
SCIPdispDecimal() is replaced by SCIPdispInt() and SCIPdispLongint()
additional parameter "maxproprounds" in SCIPpropagateProbing()
changed memory interface (see memory.h), MEMHDR is now called BLKMEM
additional parameter "aggregated" in SCIPmultiaggregateVars()
additional parameter "checkbounds" for SCIPtrySol(), SCIPtrySolFree(), SCIPcheckSol()
source code was moved into subdirectories: replace includes "scip.h" by "scip/scip.h" and "objscip.h" by "objscip/objscip.h"; This should allow a user to have include files of the same name as the ones of SCIP, e.g. "tree.h" or "var.h".
event handlers are now available as C++ wrapper class
new flag "afterrelaxation" for primal heuristics

New API functions

SCIPgetObjNorm()
SCIPvarGetLbOriginal() and SCIPvarGetUbOriginal() for original problem variables
SCIPcreateOrigSol()
SCIPwriteImplicationConflictGraph()
SCIPsepaIsDelayed(), SCIPsepaWasDelayed(), SCIPpropIsDelayed(), SCIPpropWasDelayed(), SCIPpresolIsDelayed(), SCIPpresolWasDelayed(), SCIPconshdlrIsSeparationDelayed(), SCIPconshdlrIsPropagationDelayed(), SCIPconshdlrIsPresolvingDelayed(), SCIPconshdlrWasSeparationDelayed(), SCIPconshdlrWasPropagationDelayed(), and SCIPconshdlrWasPresolvingDelayed()
SCIPinProbing()
SCIPgetProbName()
SCIPisLPSolBasic() to check, whether the current LP solution is basic (i.e. due to a simplex algorithm or barrier with crossover)
SCIPenableCons()
SCIPdisableCons()
SCIPenableConsSeparation()
SCIPdisableConsSeparation()
SCIPconsIsSeparationEnabled()
SCIPgetAvgPseudocost(), SCIPgetAvgPseudocostCurrentRun(), SCIPgetAvgPseudocostCount(), SCIPgetAvgPseudocostCountCurrentRun(), SCIPgetAvgInferences(), SCIPgetAvgInferencesCurrentRun(), SCIPgetAvgCutoffs(), SCIPgetAvgCutoffsCurrentRun(),
SCIPgetNPrimalLPs(), SCIPgetNPrimalLPIterations(), SCIPgetNDualLPs(), SCIPgetNDualLPIterations(), SCIPgetNBarrierLPs(), SCIPgetNBarrierLPIterations()
SCIPgetNPrimalResolveLPs(), SCIPgetNPrimalResolveLPIterations(), SCIPgetNDualResolveLPs(), SCIPgetNDualResolveLPIterations()
SCIPgetVarNStrongbranchs(), SCIPcolGetNStrongbranchs()
SCIPfindSimpleRational(), SCIPselectSimpleValue()
SCIPvarGetImplIds()
SCIPvarGetOrigvarSum()

Command line interface

command line history in interactive shell now only stores "useful" commands

Interfaces to external software

removed storing of dual norms in LPI state of CPLEX interface (too memory consuming)

Changed parameters

default frequency offset of fracdiving heuristic changed to 3
default frequency offset of (new) feaspump heuristic changed to 0
default frequency offset of objfeaspump heuristic changed to 8
changed default priority of primal heuristics
renamed parameter "limits/sol" to "limits/solutions"
changed default check priority of knapsack constraint handler to -600000
changed default priority of Gomory cut separator to -1000 (will now be called after constraint handlers!)
changed default priority of strong CG cut separator to -2000
changed default priority of cmir cut separator to -3000
changed default of parameter "lp/pricing" to 's'teepest edge pricing
default parameter "branching/relpscost/minreliable" changed to 1.0
default parameter "branching/relpscost/maxlookahead" changed to 8
default parameter "branching/relpscost/sbiterofs" changed to 100000
default parameter "heuristics/coefdiving/maxlpiterquot" changed to 0.05
default parameter "heuristics/fracdiving/maxlpiterquot" changed to 0.05
default parameter "heuristics/guideddiving/maxlpiterquot" changed to 0.05
default parameter "heuristics/linesearchdiving/maxlpiterquot" changed to 0.05
default parameter "heuristics/pscostdiving/maxlpiterquot" changed to 0.05
default parameter "heuristics/feaspump/freq" changed to 20
default parameter "heuristics/objfeaspump/freq" changed to 20
default parameter "heuristics/objpscostdiving/freq" changed to 20
default parameter "heuristics/rootsoldiving/freq" changed to 20
default parameter "separating/clique/maxtreenodes" changed to -1

New parameters

new parameter delay for presolvers
new parameter delaypresol for constraint handlers
"lp/cleanupcolsroot" and "lp/cleanuprowsroot" to distinguish cleanup settings between root node and other nodes
"heuristics/fixandinfer/proprounds" and "heuristics/fixandinfer/minfixings"
"separating/.../delay"
"presolving/.../delay"
"propagating/.../delay"
"constraints/.../delaysepa"
"constraints/.../delayprop"
"constraints/.../delaypresol"
"lp/initalgorithm" and "lp/resolvealgorithm" for switching between simplex and barrier algorithm
"numerics/barrierconvtol" to set the convergence tolerance in the barrier algorithm
"lp/pricing" to set the pricing strategy used in the LP solver
"lp/checkstability" to disable stability check of LP solver's result code
"conflict/dynamic"
"conflict/removeable"
"reading/mpsreader/dynamicconss"
"reading/cnfreader/dynamicconss"
"heuristics/coefdiving/maxlpiterofs"
"heuristics/feaspump/maxlpiterofs"
"heuristics/fracdiving/maxlpiterofs"
"heuristics/guideddiving/maxlpiterofs"
"heuristics/linesearchdiving/maxlpiterofs"
"heuristics/objfeaspump/maxlpiterofs"
"heuristics/objpscostdiving/maxlpiterofs"
"heuristics/pscostdiving/maxlpiterofs"
"heuristics/rootsoldiving/maxlpiterofs"
"heuristics/feaspump/maxsols"
"heuristics/objfeaspump/maxsols"
"heuristics/objpscostdiving/maxsols"
"heuristics/rootsoldiving/maxsols"
"branching/scorefunc"

Data structures

new possible result SCIP_DELAYED for EXEC method of separators, presolvers and propagators and SEPA, PROP, and PRESOL methods of constraint handlers

Fixed bugs

fixed bug in MPS file reader
fixed bugs in separation store with single coefficient cuts that are converted into bound changes
at least one cut per separation round is added to the LP to avoid cycling, even if the cut is redundant
removed bug with applying reduced cost strengthening before pricing in all necessary variables
negated variables must also be reset in SCIPvarInitSolve()
removed bug with objective norm calculation and column variables not in the LP (pricing)
removed conflict analysis of infeasible diving LP if pricing is activated
removed bug in knapsack constraint handler with merging multiple items if more than two items of the same variable appear in the constraint
fixed bug in SCIProwCalcIntegralScalar() with rows consisting of only continuous variables (appeared in gomory cut separator on miplib/dcmulti.mps)
fixed documentation of CONSLOCK-method (missing parameter "scip" in SCIPaddVarLocks())
included missing "objrelax.h" in includes of objscip.h
fixed bug that presolving time is not counted to solving time, if presolving is called explicitly with SCIPpresolve()
fixed bug where presolving fixings are counted even if the variable was already fixed
fixed bug that CONSLOCK method of constraint handlers that don't need constraints is not called
fixed bug that after a resolve and further preprocessing, existing primal solutions may get corrupted due to aggregations or fixings that are possible due to the primal bound (given by the best solution)
fixeg bug in setppc constraint handler with pairs of aggregated variables in the same constraint
removed bug with dual presolver, that declared a problem to be unbounded or infeasible, if it could fix a variable to infinity even if its objective value is zero
fixed bug in knapsack constraint handler that fixed variables are sometimes not removed in presolving
made conflict analysis available in presolving stage (for probing conflicts)
removed bug in knapsack constraint handler with merging negated variables of equal weight at the end of the variables' array
fixed bug with primal bound becoming wrong, if in a prior run the optimal solution was found and the cutoff bound was thereby reduced due to further domain propagation w.r.t. the objective function
fixed bug with unresolved numerical troubles in LP that don't render the LP useless at the current node
fixed bug in SCIPisObjIntegral()
LP error on forced LP resolve (due to 0 unfixed integers) now leads to an error (instead of accepting the pseudo solution as feasible)
fixed bug in SCIPprintError() with file == NULL
fixed bug with globally deleting constraints, that have attached rows which are therefore not released in exitsol methods
fixed bugs in intobj separator
fixed bug in CPLEX LP interface with dual norms
heuristic's display character is now only shown the first time, the new solution was found
fixed bug that SCIPreadProb() doesn't discard the transformed problem
fixed bug in cmir separator with empty rows
fixed bug in linear constraint handler's knapsack relaxation separator
fixed numerical bugs in rounding heuristic and rootsoldiving heuristic
fixed bug in implied bound cut separator: only implications between binary variables were generated before
fixed bug in linear constraint handler with eventdatas, if the original constraint has no variables
fixed bug with wrong euclidean norm calculation of row, if multiple coefficients for the same variable are added and the sorting of the row was delayed with SCIProwDelaySort()
fixed bug with adding implications: wrong insertion position, if only the lower bound change was present but not the upper bound change
fixed bug in SCIPvarAddImplics() with wrong variable used in varAdjustBd()
fixed bug in method reduced() of tclique_branch.c with sorting nodes in V

SCIP 0.7.8

Features

changed SCIProwCalcIntegralScalar() to a slightly different algorithm
improved knapsack relaxation in linear constraint handler separator to scale the constraint in order to get integral coefficients instead of just rounding down all coefficients
improved presolving of linear constraint handler: aggregation of two constraints with equal coefficient vector into single constraint
improved presolving of knapsack constraint handler: aggregation of equal or negated variables in same constraint
Plugins
- priority of separators, propagators and presolvers decide whether the plugin is called before the corresponding constraint handler methods or after: plugins with nonnegative priorities are called before, plugins with negative priorities are called after the constraint handlers
- new plugin class for relaxators (external relaxations, that can be used in parallel with LP relaxations)
- if more than one result code applies to a plugin's execution, it should return the one that is higher in the call's documentation list

Interface changes

even in optimized mode, the simple functions that are implemented as defines in the include files exist in the library, s.t. one can include the include files without NDEBUG and use the optimized library

New and changed callbacks

new branching rule plugin methods INITSOL and EXITSOL

Deleted and changed API methods

removed SCIPisFeasible(); use !SCIPisFeasNegative() instead
SCIPisIntegral(), SCIPisFracIntegral(), SCIPfloor(), SCIPceil() and SCIPfrac() don't use the feasibility tolerance anymore (default: 1e-06); instead, they are using epsilon (default: 1e-09); instead, for handling integrality of a variable "in feasibility tolerances", new methods SCIPisFeasIntegral(), SCIPisFeasFracIntegral(), SCIPfeasFloor(), SCIPfeasCeil() and SCIPfeasFrac() should be used
in LPI, the semantics of SCIPlpiHasPrimalRay() and SCIPlpiHasDualRay() changed: methods return TRUE, if a ray exists and the solver can return it; new methods SCIPlpiExistsPrimalRay() and SCIPlpiExistsDualRay() check whether a ray exists without checking, if the solver knows and can return the ray

New API functions

SCIPvarIsInLP()
SCIPgetLPColumnObjval() and SCIPgetLPLooseObjval()
SCIPcalcIntegralScalar() with arbitrary array of Real values
SCIPaddCoefKnapsack() in knapsack constraint handler
SCIPisScalingIntegral() to check, whether the scaling of a value would lead to an integral value, measured against epsilon which is also scaled by the same scalar
SCIPgetRealarrayMinIdx(), SCIPgetRealarrayMaxIdx(), SCIPgetIntarrayMinIdx(), SCIPgetIntarrayMaxIdx(), SCIPgetBoolarrayMinIdx(), SCIPgetBoolarrayMaxIdx(), SCIPgetPtrarrayMinIdx() and SCIPgetPtrarrayMaxIdx()
SCIPbsortPtrInt() and SCIPbsortPtrIntInt()
SCIPvarWasFixedAtIndex()
SCIPaddConflictBd()
SCIPprintMemoryDiagnostic()
SCIPfindObj...() and SCIPgetObj...() in C++ wrapper interface to get the corresponding plugin object

Changed parameters

slightly changed the meaning of parameter "presolving/abortfac" a value of 0 now means to abort presolving only after no more change has been found

Fixed bugs

removed bug in knapsack constraint handler that appears if a variable is fixed to zero in knapsack presolving, which triggers a variable of the same knapsack to be fixed to one due to aggregation
fixed bugs in consdataSwitchWatchedVars() of "or" and "and" constraint handlers
fixed bug in all-fullstrong branching with getting strong branching information for columns not in current LP
assigning a value to a fixed variable in a solution with SCIPsetSolVal() does not return an error anymore, if the value is equal to the fixed value of the variable
implemented missing case in solve.c with branching rules that add constraints
solving loop is now immediately aborted, if a node on the active path is marked to be cut off
removed bug in resolving an interrupted problem, after the last solved node was cut off
removed bug with infinite solving loop if LP solving is turned off
removed bug in knapsack presolver
removed bug with aborted solving in root node (e.g. due to time limit) that is tagged to be restarted
changed numerics for integrality check of coefficients (fixed bug with accumulated errors in rows s.t. the row's activity is no longer integral although the row is marked being integer)
fixed bugs in constraint handlers (and, logicor, or, setppc, xor) with calling conflict analysis during presolving
slightly changed numerics in linear constraint handler presolving to fix a bug with coefficients detected to be scaled to an integral value, that are not integral after scaling due to a large scalar that increased the integrality gap to a value larger than epsilon
fixed wrong assertion in xor constraint handler with switching both watched variables to unwatched
removed bug in SCIPisScalingIntegral()
removed bugs with calling SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPinferVarLbCons(), SCIPinferVarUbCons(), SCIPinferVarLbProp() and SCIPinferVarUbProp() in PROBLEM stage
fixed bug in presolving with wrong number of newly fixed/aggregated/... variables/bounds/... after a restart

SCIP 0.7.7

Features

infeasible LPs in diving now produce conflict clauses (if LP conflict analysis is enabled)
conflict analysis was slightly modified
slightly changed aging strategy of logic or constraint handler

Interface changes

Deleted and changed API methods

method SCIPgetGap() and SCIPgetTransGap() now return infinity, if primal and dual bound have opposite sign (this removes the oddness with the gap increasing while the dual bound approaches zero)

New API functions

added methods SCIPgetVarsLogicor() and SCIPgetNVarsLogicor() in logic or constraint handler

Changed parameters

"lp/colagelimit" and "lp/rowagelimit" may now be set to -1 to disable deletion of columns/rows due to aging

Build system

Makefile

the file names in the archive file are now preceeded with a directory "scip-<lt;version>gt;/"
the compiler is now also represented in the LP solver library names (e.g. you have to rename the softlink "libcplex.linux.x86.a" to "libcplex.linux.x86.gnu.a")

Fixed bugs

removed bug in conflict analysis that appears if the conflict is only active at the current depth level
missing SCIPlpiIsPrimalFeasible() and SCIPlpiIsDualFeasible() implemented in lpi_spx.cpp and lpi_spx121.cpp
removed preprocessing of linear constraint pairs with modifiable constraints
removed wrong assert "assert(eventfilter->gt;len == 0 || eventfilter->gt;eventmask != 0x00000000)" from event.c
removed wrong assert in conflict analysis (appeared on analyzing diving LP conflicts with both bounds of a non-binary variable changed)

SCIP 0.7.6

Features

creation of reconvergence clauses in conflict analysis
first node of each plunging is not treated as plunging node w.r.t. calling primal heuristics
improved performance of logic or constraint handler due to better watched variables handling

Interface changes

Deleted and changed API methods

changed SCIPcatchVarEvent() and SCIPdropVarEvent()
SCIPstage() is now called SCIPgetStage()
SCIPprintStatus() is now called SCIPprintStage()

New API functions

SCIPgetActivityLinear() in linear constraint handler
SCIPgetFeasibilityLinear() in linear constraint handler
SCIPchgVarBranchDirection()
SCIPvarGetBranchDirection()
SCIPgetStatus() returns the solution status
SCIPprintStatus() outputs the solution status (beware, that the old SCIPprintStatus() method is now called SCIPprintStage())

Changed parameters

changed default frequency offset of pscostdiving "heuristics/pscostdiving/freqofs" to 2 and frequency offset of fracdiving "heuristics/feaspump/freqofs" to 0 in order to not call pscostdiving in root node, where nearly all pseudo costs are uninitialized

New parameters

new parameter "separating/efficacynorm" to choose between Euclidean, maximum, sum and discrete norm in efficacy calculation

Data structures

new possible result code SCIP_DELAYED for primal heuristics

Fixed bugs

removed bugs in CLP Solver interface
SCIP returned "gap limit reached" even if the problem was solved to optimality, if the optimal solution was found at a node with lower bound equal to the global lower bound
after conversion of the focus node into a junction (e.g. in case of numerical troubles while solving the node's LP), the child nodes got the wrong LP fork attached (the common LP fork of the old and new focus node instead of the old focus node's LP fork)
bug reconvergence clauses in conflict analysis if bounds on non-binary variables were the reason for the fixing of the uip to create a reconvergence clause for
wrong sub calls in SCIPvarGet...CurrentRun() for aggregated variables
variables' conflict set counter was not reset when the problem was resolved again

Known bugs

unbounded models lead to an error
air04 and air05 return wrong optimal value (1 too large): possibly due to strong branching or setppc propagation?

SCIP 0.7.5

Miscellaneous

started change log