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
SCIPvarLock(), SCIPvarLockDown(), SCIPvarLockUp(), SCIPvarLockBoth(), SCIPvarUnlock(), SCIPvarUnlockDown(), SCIPvarUnlockUp() and SCIPvarUnlockBoth() are replaced by SCIPaddVarLocks() which returns a RETCODE
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()
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
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()
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)
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
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
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
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)
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
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?