Release notes for SCIP 0.7

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
• it is now possible to create subnodes in probing and use backtracking to undo probing changes
• bounds of variables are included in the feasibility checks for solutions
• support for barrier algorithm
• changed implementation of automatic minplungedepth and maxplungedepth calculation in bfs node selector
• Presolving:
  • new plugin: probing presolver
  • probing is now also possible in presolving stage
  • it is now possible to interrupt and continue presolving
• Separation and Cuts:
  • new plugin: clique separator for clique cuts with at least 3 elements
  • new plugin: implied bound cuts separator
  • included debugging module to check whether cutting planes cut off the optimal solution
• Branching:
  • 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
• Constraints:
  • 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
  • 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}
• Heuristics:
  • 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
  • modified the automatic objfactor setting of feaspump heuristic to let the objective function have stronger influence

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
• 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
• 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
• 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
• Solution:
  • removed method SCIPsolGetObj(), use SCIPgetSolOrigObj() or SCIPgetSolTransObj() instead
  • additional parameter checkbounds for SCIPtrySol(), SCIPtrySolFree(), SCIPcheckSol()
• Variables:
  • SCIPvarLock(), SCIPvarLockDown(), SCIPvarLockUp(), SCIPvarLockBoth(), SCIPvarUnlock(), SCIPvarUnlockDown(), SCIPvarUnlockUp() and SCIPvarUnlockBoth() are replaced by SCIPaddVarLocks() which returns a RETCODE
  • SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), SCIPvarGetLbLocal() and SCIPvarGetUbLocal() now return the corresponding values of the transformed problem or current subproblem even for original problem variables
  • 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
  • SCIPaddVarImplication() now also adds variable lower and upper bounds, if the implied variable is non-binary
  • additional parameter aggregated in SCIPmultiaggregateVars()
• Constraints:
  • SCIPvarLockDownCons(), SCIPvarLockUpCons(), SCIPvarUnlockDownCons() and SCIPvarUnlockUpCons() are replaced by SCIPlockVarCons() and SCIPunlockVarCons() which return a RETCODE
  • SCIPlockConsVars() and SCIPunlockConsVars() replaced with method SCIPaddConsLocks()
  • 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...()

New API functions

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

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

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
• removed bug with applying reduced cost strengthening before pricing in all necessary variables
• negated variables must also be reset in SCIPvarInitSolve()
• fixed documentation of CONSLOCK-method (missing parameter scip in SCIPaddVarLocks())
• included missing objrelax.h in includes of objscip.h
• 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)
• 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 in SCIPisObjIntegral()
• fixed bug in SCIPprintError() with file == NULL
• 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 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
• LP:
  • removed bug with objective norm calculation and column variables not in the LP (pricing)
  • 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 CPLEX LP interface with dual norms
• Presolving:
  • 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
  • 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
• Numerics:
  • fixed bug with unresolved numerical troubles in LP that don't render the LP useless at the current node
  • fixed numerical bugs in rounding heuristic and rootsoldiving heuristic
• Separator:
  • 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
  • fixed bug in SCIProwCalcIntegralScalar() with rows consisting of only continuous variables (appeared in gomory cut separator on miplib/dcmulti.mps)
  • fixed bug in linear constraint handler's knapsack relaxation separator
  • fixed bugs in intobj separator
  • fixed bug in cmir separator with empty rows
  • fixed bug in implied bound cut separator: only implications between binary variables were generated before
• Constraint Handlers:
  • removed bug in knapsack constraint handler with merging multiple items if more than two items of the same variable appear in the constraint
  • removed bug in knapsack constraint handler with merging negated variables of equal weight at the end of the variables' array
  • fixed bug in linear constraint handler with eventdatas, if the original constraint has no variables
  • fixed bug that CONSLOCK method of constraint handlers that don't need constraints is not called
  • fixeg bug in setppc constraint handler with pairs of aggregated variables in the same constraint
  • fixed bug with globally deleting constraints, that have attached rows which are therefore not released in exitsol methods
• Conflict analysis:
  • removed conflict analysis of infeasible diving LP if pricing is activated
  • made conflict analysis available in presolving stage (for probing conflicts)

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

• 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
• removed bug in SCIPisScalingIntegral()
• removed bugs with calling SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPinferVarLbCons(), SCIPinferVarUbCons(), SCIPinferVarLbProp() and SCIPinferVarUbProp() in PROBLEM stage
• (Re)solving:
  • 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 with aborted solving in root node (e.g. due to time limit) that is tagged to be restarted
• Branching:
  • fixed bug in all-fullstrong branching with getting strong branching information for columns not in current LP
  • implemented missing case in solve.c with branching rules that add constraints
• Numerics:
  • 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)
  • 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
• Constraint handlers:
  • fixed bugs in consdataSwitchWatchedVars() of or and and constraint handlers
  • fixed wrong assertion in xor constraint handler with switching both watched variables to unwatched
  • fixed bugs in constraint handlers (and, logicor, or, setppc, xor) with calling conflict analysis during presolving
  • 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
• Presolving:
  • removed bug in knapsack presolver
  • 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-<version>/
• 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
• Asserts:
  • removed wrong assert assert(eventfilter->len == 0 || eventfilter->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)
• Variables:
  • 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