Release notes for SCIP 3.0
SCIP 3.0.2
Features
- reading erroneous CIP files can now output some indication of syntax errors
- can now run splint on core files
- cons_xor now uses the integral variable in propagation
- allowed to switch on/off the solution debugging
Performance improvements
- improved SCIPlpiAdd{Cols,Rows}() in SoPlex LPi
Examples and applications
Interface changes
New API functions
- SCIPmarkColNotRemovableLocal() and SCIPmarkRowNotRemovableLocal() to forbid removal of an column/row from the LP in the current node
- SCIPmessageVPrintError()
Command line interface
- can now output the solutions in the solution pool in the interactive shell
Interfaces to external software
- updated Mosek LP interface to compile with Mosek 7
Fixed bugs
- fixed bugs in solution counting
- fixed fieldtypes in sorting template
- fixed bug concerning the userinterrupt flag, which was not reset
- fixed solution collection when counting solutions
- fixed bug with storing original solutions
- fixed bug with infinite multi-aggregation constants
- fixed bug that removing reverse implication did not reset closestvblpcount
- fixed bug that duplicate solutions stopped copying of solutions to original solution candidate store
- forbid branching on variables with huge bounds; such huge values cannot be enumerated with fixed precision floating point arithmetics
- fixed bug that Ipopt's error message was not fully shown due to exiting before the message handler buffer was emptied
- unlinking a solution now copies solution values smaller than SCIPepsilon() avoiding some feasible solution in the transformed problem to be infeasible in the original problem
- allow to add columns (rows) with nonzero indices beyond current number of rows (columns) in SoPlex LPi
- updated get.ASL script to cope with broken ftp access to netlib server
- Memory:
- fixed bugs with freeing C++ object data for problem and variables
- fixed memory leak in lp.c (probably never occurred so far since array was not used)
- fixed bug in sepa_zerohalf.c where the maxcuts(root) parameters led to an invalid memory allocation call
- LP:
- fixed assert in solve.c with branched status and LP reached the objective limit
- fixed bug in heur_oneopt.c and heur_clique.c which was caused by side-effects when calling SCIPconstructLP(); when adding new variables in this method (e.g. adding new variables needed for a relaxation), this changes the variables array of SCIP
- fixed problem that diving did not save status for infeasible LPs
- fixed bug in SCIPlpComputeRelIntPoint() with wrong iteration limit and with wrong recompution
- fixed bug that old LP size was not updated for deadend if no LP was solved
- Expressions:
- fixed issues with ungraceful termination when encountering unsupported expression operands in AMPL interface
- fixed bug in backward propagation of linear expressions in expression graph
- Propagation:
- fixed potential performance issue with tree depth always assumed to be zero when propagating in probing mode
- fixed bug in prop_vbound w.r.t. creation of variables during the search
- fixed several bugs in propagation of cons_xor: need to take integral variables into account
- fixed bug in cons_abspower.c handling infinity values in propagation
- fixed bug in cons_and.c when a constraint was not correctly propagated which led to wrong dual-presolve reductions
- fixed bug in cons_abspower: wrong infinity check when propagating bounds
- Presolving:
- fixed bug that the number aggregated variables were not counted in presol_inttobinary.c
- fixed bug in presol_domcol: locks are now checked to see whether rounding was forbidden for a variable
- Reader:
- fixed bug in reader_gms.c w.r.t. writing nonlinear expressions with polynomials with constants
- fixed bugs in parsing bounds from CIP-files, in reader_gms and AMPL interface
- fixed bug when reading a mps formated file with a missing bound in the bound section
- Constraints:
- fixed bug in cons_bounddisjunction with satisfied literal of multi-aggregated variable
- fixed bug in upgrade method of cons_soc
- fixed issue with negated variables in cons_xor.c
- fixed several asserts in cons_xor presolving
- fixed bug in cons_xor.c calling method on null pointer row
- fixed bug using a too hard comparison on the objective-infeasible-decision in constraint enforcement
- fixed possible cycling in enforcement of nonlinear constraints due to too early removal of newly added cuts from LP
- fixed bug wrongly removing constraints locally while counting
- fixed bugs in cons_bivariate.c when the nonlinear function is not differentiable on the boundary of the domain
- fixed bug in cons_indicator.c:SCIPmakeIndicatorFeasible() with handling fixed variables
- fixed bug in cons_integral: check integrality of implicit integer variables when a solution is checked for feasibility
- fixed bug in Undercover with
pseudo-
quadratic constraints - fixed bug with quadratic constraints not being upgraded
- fixed bug in intervalarith.c: bivariate quad. equations may have been solved wrongly if second variable is unbounded
- Separation:
- fixed bug in sepa_zerohalf.c not copying the displays to the subscip, but still changing a display parameter there
- fixed iteration limit determination in sepa_closecuts
- fixed bug in sepa_closecuts: need to make sure that variable values of separation point satisfy bounds
- fixed bugs in sepa_oddcylce: number of arcs have to be adjusted, handle implicit binary variables, fixed bug in heuristic separation method, fixed asserts
- fixed wrong bound calculation in sepa_rapidlearning
SCIP 3.0.1
Features
- added delayed cutpool which only gets separated if the sepastore is empty after a separation round
- sepa_cgmip can now take the objective row into account
- added possibility to run clang compiler
- statistics now include output on number of solutions that respect objective limit
Performance improvements
- also copying active tight cuts from the delayed cut pool when calling SCIPcopyCuts()
- sort genvbounds only when root node is finished; apply more often
Examples and applications
Interface changes
- when using an objective limit, heuristic characters are not displayed any longer for worse solutions
Deleted and changed API methods
- fixed spelling in the method name SCIPgmlWriteClosing()
New API functions
- SCIPgetNLimSolsFound() to get number of solutions that respect the objective limit
Fixed bugs
- fixed issue with applying the effective root depth during the search
- fixed bug concerning usage of dualbound and lowerbound
- fixed bug trying to color probing nodes, which are not added to the vbc output anymore
- fixed bug in sorting template
- fixed bug leading to removing a ranged row parallel to the objective function, although one of the sides was still needed
- fixed a bug correcting the binvarssorted flag in cons_linear.c
- fixed bug in cons_varbound.c not resolving multi-aggregated variables
- relaxed assert in SCIPvarCh{Lb,Ub}{Global,Local} that new bound must be tighter to feastol
- fixed contra-intuitive behavior when using SCIP with objective limits and solution limit at the same time; SCIP now only stops when sufficiently many solutions better than the objective limit have been found
- fixed bug when adding binary implications with non-vartype binary variables
- fixed bug adding binary implications on binary variables with type !=
SCIP_VARTYPE_BINARY
- fixed bug concerning different tolerances for reached objective limit in case of pricing with fastmip
- LP:
- fixed bug which disabled iteration limit in SCIPlpSolveAndEval()
- ensure consistency of LP bounds during OBBT diving, i.e., that lower <= upper holds exactly
- set lpsolstat to
SCIP_LPSOLSTAT_NOTSOLVED
in SCIPchg{Lp,Dual}feastol() - use tighter dual feasibility tolerance for LPs solved during optimization-based bound tightening
- fixed bug with unflushed LP arising from global bound changes in strong branching
- Constraints:
- fixed issue with deleting varbound constraints in case the bound change was not applied
- fixed bugs in parsing dis-/conjunctive constraints
- fixed bug with handling of empty logicor and bounddisjunction constraints
- fixed issue in cumulative constraint and separation
- fixed bug when sorting knapsack constraints with the same weights
- fixed bug resulting in trying to delete an upgraded linear constraint a second time in exitpre callback
- fixed minor bug in conjunctive constraint handler printing wrong constraint
- fixed bug in disjunctive constraint handler when enforcing a constraint
- fixed behaviour change of indicator constraint handler when solving another instance after solving one using the interactive shell
- fixed several issues in cumulative constraint handler
- fixed bug in cumulative constraint handler w.r.t. getting active variables
- fixed bug in cumulative constraint handler concerning conflict analysis
- LPI and Interfaces:
- fixed bug in CppAD in connection with abspower constraints
- fixed bug in CppAD when using signpower functions with expression pointers that do not fit into an unsigned int
- better handling of generalized (Lagrangian) variable bounds that are not in the LPI
- fixed wrong basis rstat values in CPLEX LPI
- fixed bug with LP not being flushed after bound changes on columns that are not in the LPI
- methods SCIPlpiIs{PrimalFeasible,DualFeasible,DualUnbounded}() in SoPlex LPi now check that the LP is not perturbed, which may happen when stopping due to iteration or time limit
- fixed inconsistencies between methods SCIPlpiIs{PrimalFeasible,DualFeasible,Optimal,...} in SoPlex LPi
- Propagation:
- fixed bug when adding linear constraints with non active variables in solving process, during propagation this resulted in changing the row, which is not possible for unmodifiable constraints/locked rows
- fixed small issue in pseudo objective propagator w.r.t. propagating the lower bound globally
- fixed bug in cons_orbitope: in rare cases one cannot repropagate
- fixed bug of wrong result code in propagation in prop_genvbound.c
- Presolve:
- fixed bug in copying nonlinear constraints during presolve (resulted in wrongly declaring instances as infeasible when using component presolve)
- fixed bug in copying nonlinear constraints during presolve (nonlinear part was not copied)
- Heuristics:
- fixed wrong solving status (OPTIMAL) in case an unbounded solution was provided or found by heuristic before presolve
- fixed bug in heur_subnlp running with tightened tolerances: sumepsilon must be tightened like feastol and epsilon
- fixed bug in nlp diving heuristic for fractional variables with values slightly outside of their domain
- Numerics:
- fixed several numeric issues
- fixed numerical bug in conflict.c relaxing bounds while keeping an infeasibility proof
- fixed feasibility decision bug when replacing inactive variables by their active counterparts, which might change the redundancy status of a bounddisjunction constraint due to numerics
- fixed numerical bug adding a relaxed bound for conflict analysis in cons_varbound
- fixed numerical bug in conflict analysis of genvbounds propagator
SCIP 3.0.0
Features
- SCIPcomputeLPRelIntPoint() with normtype=
s
now uses homogenized LP for computing rel.int. point too and allow to set relaxrows = FALSE - new column showing the pseudo objective value
- digraph structure added to misc.c and pub_misc.h that can be used to handle directed graphs, compute undirected components in the graph and sort these components (almost) topologically
- SCIP does now print an info message when the root LP could not be solved or is unbounded
- added counter and clock for SCIPcopy() calls
- correct initialization of steepest edge weights with SoPlex 1.6.0.4
- parameters can now be fixed, which means that their value cannot be changed unless they are unfixed, first; the fixing status of a parameter is copied to sub-SCIPs, which allows to ensure that certain parameters are also not changed when, e.g., heuristics change emphasis settings or also specific parameters
- automatic transfer of original solutions (e.g., provided by the user, from solution pool, after restart, from heuristic adding original solution during solve) to the transformed space (might fail due to, e.g., dual fixings)
- added possibility to use GUBs for lifting knapsack cuts (disabled)
- added pre- and post-conditions in doxygen documentation for all methods of scip.{c,h}
- added zeroobj heuristic that solves a copy of the problem without an objective function and with quite strict limits on the number of nodes and LP iterations
- complete reworking of the vbounds propagator: it now takes into account variable bounds, cliques and implications, stores bounds of variables which were changed and performs a forward propagation from these bounds, i.e., tries to derive new bounds for other variables; during propagation, bound changes are propagated in an (almost) topological order
- Constraints:
- full version of cumulative constraint handler
- new constraint handler
superindicator
for indicator constraints with slack constraints of arbitrary type - implemented first clique lifting procedure in cons_setppc.c (by default is off)
- the conjunction and disjunction constraint handlers are now able to parse their CIP output format
- Memory:
- better handling of memory limits, in particular for large problems
- estimate memory consumption for sub-SCIP and do not copy them if close to memory limit
- Presolve:
- time for initpre and exitpre methods is now also measured in presolving time
- added dual presolving for and-constraints difficult instances (no guarantees)
- oneopt can now be called before presolving
- added a presolving step in the disjunctive constraint handler, removing disjunction, where a sub-constraint was deleted, which means this sub-constraint is redundant, which again means it is always TRUE or will be enforced by another constraint
- added new presolver convertinttobin, which converts bounded integer variables to their binary representation, e.g. for integer variable 0 <= x <= 10 the binary variables y0, y1, y2 and y3 are created, such that 1 y0 + 2 y1 + 4 y2 + 8 y3 <= 10 and x = 1 y0 + 2 y1 + 4 y2 + 8 y3
- added new presolver gateextraction, which tries to find and-gates/constraints which are linearized e.g. (x + y + z >= 1, x + y <= 1 and x + z <= 1 => x == AND(~y,~z)), in special cases it also detects set-partitioning constraints e.g. (x + y + z >= 1, x + y <= 1, x + z <= 1 and y + z <= 1 => x + y + z == 1)); gate-extractor is also able to detect logicor constraints and set-packing/-partitioning constraints with the same variables, to upgrade these both constraints to a set-partitioning constraint
- added new presolver components, that searches for independent components in the problem structure and solves these components as sub-SCIPs when they are small enough (per default <= 20 discrete variables, nodelimit of 10000)
- added new presolver domcol that looks for dominated columns in a MIP and tries to fix them
- Reader:
- CNF reader now creates feasibility instances per default, usage of an objective has to be set by a parameter
- added reader for MI(NL)Ps in OSiL (Optimization Services Instance Language) format
- Statistic:
- new statistics and new statistic output messages
- number of presolving calls of plugins is counted and displayed in the statistics, can be accessed via SCIPpresolGetNCalls() and SCIP{prop/conshdlr}getNPresolCalls()
- the statistics shows for a branching rule the number of calls for LP, extern and pseudo candidates
- new switch
SCIP_STATISTIC
and new macros SCIPstatisticMessage(), SCIPstatisticPrintf() and SCIPstatistic() to output statistic and execute code lines which are only needed therefor. Works asSCIP_DEBUG
and SCIPdebugXyz() - added statistics on the number of cuts/rows that have actually been applied to the lp for each constraint handler and separator; use SCIPcreate(Empty)RowCons() and SCIPcreate(Empty)RowSepa() to support the statistics.
- NLP:
- new propagators obbt and genvbounds for MINLP
- new NLPI parameter
SCIP_NLPPAR_FASTFAIL
to enable convergence checks in NLP solver to stop early on seemingly - added nlpdiving heuristic that comprises several diving heuristics using an NLP relaxation
Performance improvements
- improved scaling by choosing the smallest scaler
- if first root lp is solved and the optimality is rejected by SCIP, there won't be an unnecessary solving of the lp from scratch again
- several performance improvements for Pseudo-Boolean optimization, pseudo objective propagator
- streamlined initlp functions in cons_indicator, cons_sos1, cons_sos2 (add rows only if needed)
- improved time used for adding implications
- speed up in SCIPboolarrayExtend() in misc.c replacing a for loop with BMSmoveMemoryArray() call
- speed up in var.c changing some recursive calls into iterative calls and reducing the number of VARFIX event that are thrown for fixation, aggregation or multi-aggregations
- revised reduced cost propagator
- increased performance in SCIPcliqueAddVar(), adding a variable to a clique
- tighten primal and dual feasibility tolerances independently if they are not reached in LP solving
- Probing:
- if probing reached the end of all variables it will restart the probing cycle correctly
- improved probing by ordering the variables differently and applying the one-branch before the zero-branch
- Constraints:
- improved scaling of linear constraints, linear constraints with integral variables will now be scale with 1e+06/MAX(maximal absolute coefficient, 1.0) instead of 1e+03/MAX(maximal absolute coefficient, 1.0); if all coefficients are in absolute value equal they will be scaled by that
- added clique presolving for and-constraints, which checks if two operands or one operand and the resultant are in a clique and then fixes the resultant to 0 and in the former case we can delete the and-constraint too
- speed up in linear constraint handler replacing aggregated variables
- when all nonlinearities have been fixed and the number of nonfixed variables is 1 in cons_nonlinear/cons_quadratic/ cons_bivariate, handle it by a bound change instead of adding a linear constraint
- Separation:
- automatically turn off separation in sepa_oddcycle if it was too unsuccessful within the last calls
- use faster Dijkstra variants in sepa_oddcycle
- improved tcliquegraphAddImplicsVars() in sepa_clique.c to faster add possible variables
- changed emphasis settings: knapsack disaggregation is now allowed in fast presolving, CG-MIP separator disabled in aggressive separation
- Reader:
- improved lp-, mps-, opb-reading time
- speed up mps reader asking parameters only once
- Heuristics:
- added parameters mincoveredrel and mincoveredabs to heur_undercover to only run if problem is sufficiently nonlinear
- improved intdiving heuristic by activating backtracking to a different fixing value
- heur_undercover treats indicator constraints as nonlinear and fixes the binary variable for linearization
Examples and applications
- new examples for scheduling and usage of the callable library with nonlinear problems
- the error messages are not handled via the message handler anymore; per default the error message a written to stderr
Interface changes
- introduced basic inclusion and creation methods to simplify usage of the SCIP library
- allowed to start diving mode even if LP is not flushed, not solved, or not solved to optimality
- changed the message handler system within SCIP heavily such that it is thread save
- the resolve propagation methods for the constraint handler and propagator getting a new parameter called relaxedbd; explaining/resolving this relaxed bound is sufficient
- default integer comparer SCIPsortCompInt() (see pub_misc.h)
- LP interface:
- Problem:
- Forbid problem modifications in
SCIP_STAGE_{INIT,EXIT}PRESOLVE
(see pre-conditions for corresponding methods in scip.h).
- Forbid problem modifications in
- Miscellaneous:
- New macro SCIPdebugPrintCons() to print constraint only if
SCIP_DEBUG
flag is set. - all objscip *.h file now use the default SCIP interface macros (this should avoid errors when changing the interface)
- New macro SCIPdebugPrintCons() to print constraint only if
New and changed callbacks
- Constraint Handler:
- Added a propagation timing parameter
proptiming
to SCIP_DECL_CONSPROP(), giving the current timing at which this method is called (also to the corresponding c++ wrapper classes). - New optional callback methods in constraint handlers:
SCIP_DECL_CONSGETVARS
andSCIP_DECL_CONSGETNVARS
. These callbacks, if implemented, should return an array of all variables and the number of all variables used by the given constraint, respectively. (This method might, e.g., be called by a presolver)
- Added a propagation timing parameter
- NLP Solver Interface:
- New NLPI callback SCIP_DECL_NLPISETMESSAGEHDLR() to set message handler in NLP solver interfaces.
- Propagator:
- Added a propagation timing parameter
proptiming
to SCIP_DECL_PROPEXEC(), giving the current timing at which this method is called (also to the corresponding c++ wrapper classes).
- Added a propagation timing parameter
- Plugin management:
- added
basic
inclusion methods which have only fundamental data of the plug-ins as arguments; added setter functions for all non-fundamental callbacks of the plug-ins; the plug-in types with basic inclusion functions are: readers, constraint handlers, conflict handlers, presolvers, propagators, heuristics, separators, relaxation handlers, branching rules, node selectors and pricers; these methods should make the usage easier, sparing out optional callbacks and parameters: e.g., SCIPincludeConshdlrBasic(); - To extend the basic functionalities, there are setter method to add optional callbacks. For example SCIPsetConshdlrParse(), SCIPsetPropCopy() or SCIPsetHeurInitsol().
- added
- Constraint Handlers:
- Added basic creation methods for all constraints types, e.g., SCIPcreateConsBasicLinear(); these methods should make the usage easier, sparing out optional callbacks and parameters.
Deleted and changed API methods
- SCIPcomputeCoverUndercover() now has an additional parameter coverbd
- tcliqueMaxClique has an additional parameter to store the number of used branch-and-bound nodes
- the code in
src/dijkstra
andsrc/xml
has been changed to (increasingly) conform to the SCIP coding style; all function (and variable) names have been changed (do not contain_
anymore). - renamed SCIPstairmap*Core() to SCIPstairmap*Stair()
- Conflict Analysis:
- Added parameter
relaxedbds
to conflict handler callback method SCIP_DECL_CONFLICTEXEC(). This array contains bounds which are sufficient to create a valid conflict
- Added parameter
- Constraint Handler:
- Added a parameter
restart
to the SCIP_DECL_CONSEXITSOL() callback method, indicating whether this call was triggered by a restart. - Added a parameter
relaxedbd
to SCIP_DECL_CONSRESPROP() callback method. If explaining a given bound change (index), it is sufficient to explain the reason for reaching therelaxedbd
value, see above - Removed parameters
isunbounded
,isinfeasible
andresult
from SCIP_DECL_CONSINITPRE() and SCIP_DECL_CONSEXITPRE() callback methods. It is not allowed to determine unboundedness or infeasibility in these callbacks, anymore. - added a
SCIP_CONS*
parameter to SCIPcreateConsDisjunction() which can represent the linear relaxation of the whole disjunction constraint as a conjunction constraint, orNULL
- remove problematic function cons_indicator:SCIPsetSlackVarIndicator()
- Renamed SCIPgetCountedSparseSolutions() to SCIPgetCountedSparseSols() in cons_countsols.{c,h}.
- Added a parameter
- Counting:
- Changed the counting system within SCIP heavily. New method for
SCIP_SPARSESOL
usage, SCIPsparseSolCreate(), SCIPsparseSolFree(), SCIPsparseSolGetVars(), SCIPsparseSolGetNVars(), SCIPsparseSolGetLbs(), SCIPsparseSolGetUbs() in (pub_)misc.{c,h}.
- Changed the counting system within SCIP heavily. New method for
- Cuts and Separation:
- removed
targetscip
parameter from SCIPconvertCutsToConss(), now this function can only convert cuts on one instance, otherwise use SCIPcopyCuts() - added
ncutsadded
parameter to SCIPcopyCuts() to be able to store the number of copied/converted cuts - New functions SCIPcreateEmptyRowCons(), SCIPcreateEmptyRowSepa(), SCIPcreateRowCons(), and SCIPcreateRowSepa() that allow to set the originating constraint handler or separator of a row respectively; this is, for instance, needed for statistics on the number of applied cuts. If rows are created outside a constraint handler or separator use SCIPcreateRowUnspec() and SCIPcreateEmptyRowUnspec(). The use of SCIPcreateEmptyRow() and SCIPcreateRow() is deprecated.
- New functions SCIProwGetOrigintype(), SCIProwGetOriginCons(), and SCIProwGetOriginSepa() to obtain the originator that created a row.
- removed
- LP:
- new parameter numerics/lpfeastol for primal feasibility tolerance used in LP solver
- SCIPcomputeLPRelIntPoint() takes two new arguments giving a time and iteration limit
- SCIPcolGetStrongbranchLPAge(), SCIPgetVarStrongbranchLPAge(), SCIPgetNLPs(), SCIPgetNPrimalLPs(), SCIPgetNDualLPs(), SCIPgetNBarrierLPs(), SCIPgetNResolveLPs(), SCIPgetNPrimalResolveLPs(), SCIPgetNDualResolveLPs(), SCIPgetNNodeLPs(), SCIPgetNNodeInitLPs(), SCIPgetNDivingLPs(), SCIPgetNStrongbranchs(), SCIPgetNRootStrongbranchs() now return a longint instead of an integer
- Message Handler and Printing:
- New callback method SCIP_DECL_MESSAGEHDLRFREE() which is called when the message handler is freed.
- The old callback method SCIP_DECL_MESSAGEERROR() was replaced by the callback method SCIP_DECL_ERRORPRINTING().
- the follwing methods additionally need the SCIP pointer as parameter to make the output thread save: SCIPprintVersion(), SCIPsetMessagehdlr(), SCIPgetMessagehdlr() and SCIPwarningMessage()
- the error printing method can be replaced using the method SCIPmessageSetErrorPrinting(); the default error message printing can be recoverd via SCIPmessageSetErrorPrintingDefault() (see pub_message.h)
- Changed the message handler system within SCIP heavily such that it is thread-safe. SCIPcreateMessagehdlr() in scip.{c,h} was replaced by SCIPmessagehdlrCreate() in pub_message.h/message.c with a changed parameter list; see pub_message.h and type_message.h.
- removed method SCIPcreateMesshdlr(), please use SCIPmessagehdlrCreate() (see pub_message.c)
- removed method SCIPfreeMesshdlr(), please use SCIPmessagehdlrRelease() (see pub_message.c)
- Error messages (SCIPerrorMessage()) are not handled via the message handler anymore; per default the error message is written to stderr.
- the following methods need an additional message handler: SCIPdispLongint(), SCIPdispInt(), SCIPdispTime(), all message handler methods (see pub_message.h), SCIPhashtablePrintStatistics(), SCIPhashmapPrintStatistics(), SCIPlpiCreate()
- SCIPprintCons() does not print termination symbol
;\n
anymore; if wanted, use SCIPinfoMessage() to print;\n
manually - remove SCIPcolPrint() and SCIProwPrint(), please use SCIPprintCol() SCIPprintRow() see scip.h
- method SCIPprintError() does not need the file stream anymore. The error is written via the error message callback.
- Nonlinear expressions, relaxation, and solver interface:
- Method SCIPexprtreeRemoveFixedVars() is not public anymore.
- Renamed SCIPmarkNonlinearitiesPresent() to SCIPenableNLP()
- Renamed SCIPhasNonlinearitiesPresent() to SCIPisNLPEnabled().
- removed SCIPmarkContinuousNonlinearitiesPresent(), renamed SCIPhasContinuousNonlinearitiesPresent() to SCIPhasNLPContinuousNonlinearity() and allow call only during initsolve and solve,
- Parameters:
- Replaced SCIPparamSet*() by SCIPchg*Param()
- replaced SCIPparamSetBool() by SCIPchgBoolParam()
- replaced SCIPparamSetInt() by SCIPchgIntParam()
- replaced SCIPparamSetLongint() by SCIPchgLongintParam()
- replaced SCIPparamSetReal() by SCIPchgRealParam()
- replaced SCIPparamSetChar() by SCIPchgCharParam()
- replaced SCIPparamSetString() by SCIPchgStringParam()
- Replaced SCIPparamSet*() by SCIPchg*Param()
- Presolving:
- Removed parameters
isunbounded
,isinfeasible
andresult
from SCIP_DECL_PRESOLINITPRE() and SCIP_DECL_PRESOLSEXITPRE(). It is not allowed to determine unboundedness or infeasibility in these callbacks, anymore.
- Removed parameters
- Propagator:
- changed parameters of function SCIPpropagateCutoffboundVar() in prop_pseudoobj.{c,h}
- Added a parameter
restart
to SCIP_DECL_PROPEXITSOL() callback method, indicating whether this call was triggered by a restart. - Added a parameter
relaxedbd
to SCIP_DECL_PROPRESPROP() callback method. If explaining a given bound change (index), it is sufficient to explain the reason for reaching therelaxedbd
value. - Removed parameters
isunbounded
,isinfeasible
andresult
from SCIP_DECL_PROPINITPRE() and SCIP_DECL_PROPEXITPRE() callback methods. It is not allowed to determined unboundedness or infeasibility in these callbacks, anymore.
- Sort and Copy:
- The methods SCIPsortedvecInsert*() have an additional parameter which can be used to receive the position where the new element was inserted, if this is not of interest a
NULL
pointer can be given - new parameter in SCIPcopyPlugins() to indicate whether the message handler from the source SCIP should be passed to the target SCIP (only the pointer is copied and the usage counter of the message handler is increased)
- New parameter in SCIPcopy() to indicate whether the message handler from the source SCIP should be passed to the target SCIP (only the pointer is copied and the usage counter of the message handler is increased). In multi theaded enviroment this parameter needs to be set to FALSE.
- The methods SCIPsortedvecInsert*() have an additional parameter which can be used to receive the position where the new element was inserted, if this is not of interest a
- Variable usage:
- rename SCIPvarGetBestBound() to SCIPvarGetBestBoundLocal()
- rename SCIPvarGetWorstBound() to SCIPvarGetWorstBoundLocal()
- Method SCIPvarGetProbvarSum() is not public anymore, use SCIPgetProbvarSum() instead.
- Replaced method SCIPvarGetRootRedcost() by SCIPvarGetBestRootRedcost().
New API functions
- setup timer to all plugins and therefore SCIP<plugin-type>GetSetupTime() methods in all pub_plugin-type.h to ask for this time (, e.g. SCIPeventhdlrGetSetupTime() in pub_event.h)
- new GML(Graph Modeling Language) methods SCIPgmlWriteOpening(), SCIPgmlWriteCosing(), SCIPgmlWriteArc(), SCIPgmlWriteEdge(), SCIPgmlWriteNode() that write to a given GML file
- new LPI method SCIPlpiGetObjsen() to query objective sense
- SCIPpermuteIntArray() in pub_misc.h and misc.c for permuting an integer array
- SCIPcalcBinomCoef() in pub_misc.h and misc.c which calculates a binomial coefficient up to 33 over 16
- SCIPheurPassSolAddSol() in heur_trysol.c; solution which are passed via this method are just without any feasibility check
- SCIPgetGlobalPseudoObjval() which returns the global pseudo objective value which is all variables set to their best (w.r.t. the objective function) global bound
- SCIPhashGetKeyStandard() which returns the element itself as the key, SCIPhashKeyEqPtr(), SCIPhashKeyValPtr() which do the hash-comparison/-conversion on a pointer in pub_misc.h
- SCIPhashtableClear() which removes all elements of a hash table
- SCIPisUpdateUnreliable() to check whether an iteratively updated value should be recomputed from scratch (e.g., for activities; uses new parameter
misc/num_recompfac
) - SCIPisHugeValue() to check whether a value is huge and should be handled separately from other values (e.g., in activity computations) and SCIPgetHugeValue() to get the smallest value counting as huge
- SCIPfixParam() and SCIPunfixParam() to fix and unfix a parameter, respectively; the fixing status of a parameter can be requested by SCIPparamIsFixed();
- SCIPsetBasePointClosecuts() to set the base point for close cut separation
- SCIPchgCutoffboundDive() to change the cutoffbound in diving mode
- SCIPupdateCutoffbound() which can be used to pass a cutoff bound
- Presolving:
- SCIPpropIsPresolDelayed() which return if a propagator is delay during presolving
- Added method SCIPisPresolveFinished() which returns whether the presolving process would be stopped after the current presolving round, given no further reductions will be found, can be used to ensure that a presolver is called very late
- Memory:
- added forgotten implementation of SCIPfreeMemorySize(), SCIPfreeMemorySizeNull() in scip.h and BMSfreeMemorySize(), BMSfreeMemorySizeNull() in memory.h
- SCIPmemccpy() in pub_misc.h and misc.c which copies either a specified number of charcters of a source string to a destination string or until it hits a stoping character
- BMSmoveMemory(), BMSmoveMemoryArray(), BMSmoveMemorySize() and corresponding BMSmoveMemory_call() in memory.{h,c} too move memory elements
- Conflict Analysis:
- SCIPisConflictAnalysisApplicable() which return FALSE is the conflict will not runs; can be used to avoid unnecessary initialization of the conflict analysis
- SCIPaddConflictRelaxedLb(), SCIPaddConflictRelaxedUb() and SCIPaddConflictRelaxedBd(); these methods can be used to give for a bound change which is part of an explanation a relaxed bound; this means the relaxed bound is already efficient to be part of a valid explanation
- SCIPisConflictVarUsed() returns TRUE if the given bound change is already part of the conflict set; that is the bound change is redundant;
- SCIPgetConflictVarLb() and SCIPgetConflictVarUb() returning the lower/upper bound of the given variable within the current active conflict set
- Variable usage:
- SCIPvarsGetProbvar() in pub_var.h and var.c, which returns for a given array of variables the active, fixed or multiaggregated representation
- SCIPgetActiveVars() in scip.{h,c}, which returns for a given array of variables the active counterparts
- SCIPgetNObjVars() which returns the number of variables which have a non-zero objective coefficient
- SCIPenableVarHistory() and SCIPdisableVarHistory() which can be used to turn off and on the collection of variables statistics which is used for example for branching
- SCIPbranchVarHole() which branches a variable w.r.t. a given domain hole
- SCIPvarGetAggregatedObj() which computes for a (not active) variable the corresponding objective value
- SCIPsolIsOriginal() that returns whether a solution is defined on the original variables
- SCIPgetVarImplRedcost() which returns the implied reduced costs
- SCIPvarGetBestRootSol(), SCIPvarGetBestRootRedcost(), SCIPvarGetBestRootLPObjval() which return the best combination for a variable w.r.t. root solution value, root LP objective value and root reduced cost
- SCIPhaveVarsCommonClique() in scip.{h,c}, to check for common clique information on two given variables
- added basic creation methods SCIPcreateVarBasic() and SCIPcreateProbBasic() and setter functions for non-fundamental callbacks of variables and problems.
- added new methods SCIPvarGetBestBoundGlobal() and SCIPvarGetWorstBoundGlobal().
- Constraint Handler:
- added public wrapper functions for calling constraint handler callback methods for a single constraint: SCIPactiveCons(), SCIPdeactiveCons(), SCIPinitlpCons(), SCIPsepalpCons(), SCIPsepasolCons(), SCIPpropCons(), SCIPrespropCons(), SCIPenfopsCons(), SCIPenfolpCons()
- added basic creation methods for all constraint handlers
- SCIPchgCapacityKnapsack() which can be used to change the capacity of a knapsack constraint
- SCIPconsIsAdded() which returns whether a constraint was already to a SCIP instance
- SCIPconshdlrGetNCutsApplied() in pub_cons.h to get the number of cuts applied to the lp
- SCIPconshdlrIncNAppliedCuts() in cons.h to increase the number of applied cuts (used by sepastore.c)
- SCIPchgVarName() and SCIPchgConsName() which can be used to change name of variables and constraints in problem creation stage
- New methods SCIPgetConsVars() and SCIPgetConsNVars() which return for a given constraint the involved variables and the number of variables if the corresponding constraint supports this (optional) callbacks (corresponding callbacks need to be implemented, see above)
- Message Handler:
- SCIPmessagehdlrCapture() which captures a given message handler (increases number of uses)
- SCIPmessagehdlrRelease() which releases and possibly frees a given message handler (decreases number of uses)
- SCIPsetMessagehdlrLogfile() which can be used to write into a log file
- SCIPsetMessagehdlrQuiet() which can be used to turn the screen output on and off
Command line interface
- in the interactive shell, parameters can be fixed and unfixed with
fix
(instead ofset
), e.g.,fix heuristics rens freq TRUE
; - new shell command
change minuc
to minimize the number of unsatisfied constraints
Interfaces to external software
- beta-version of a MATLAB interface can be found under interfaces/matlab
- beta-version of a AMPL interface can be found under interfaces/ampl
Changed parameters
branching/fullstrong/reevalage
changed from an integer to a longint parameter- Removed parameters:
separating/closecuts/separootonly
constraints/quadratic/defaultbound
separating/cgmip/nodelimit
New parameters
constraints/s/timingmask
for changing the timingmask for calling the propagtion method of all constraint pluginsconstraints/and/dualpresolving
by default set to TRUE, enabling dual-presolving on and-constraintsconstraints/indicator/{sepacouplingcuts,sepacouplinglocal}
to enable separation of (local) cutsconstraints/indicator/{maxsepacuts,maxsepacutsroot}
to restrict the number of separated cutsconstraints/indicator/dualreductions
to enable dual presolving/propagation stepsconstraints/setppc/cliquelifting
,constraints/setppc/addvariablesascliques
,constraints/setppc/cliqueshrinking
, first for enabling/disabling the clique lifting algorithm in cons_setppc.c, second parameter is for trying to create extra clique constraints in lifting algorithm, third parameter is for trying to decrease the number of variable in a clique constraint in the lifting algorithmlimits/totalnodes
that allows to stop at the correct node if a restart occured; therefore the newSCIP_STATUS_TOTALNODELIMIT
is addedlp/{rootiterlim,iterlim}
to set a limit on the LP iterations spend in the initial root LP and each LP resolve, respectivelymisc/transorigsols
by default set to TRUE, that switches whether SCIP tries to transfer original solutions into the transformed space (in initsol and if a heuristic adds an original solution during solving)numerics/hugeval
that defines the smalles value counting as huge (see new method SCIPisHugeValue())numerics/recompfac
which denotes the factor, by which the absolute of an iteratively updated value has to be decreased in order to recompute the value from scratchpresolving/convertinttobin/maxdomainsize
by default is set toSCIP_LONGINT_MAX
, which deternmines the domainsize for which integers are converted to their binary representationpresolving/convertinttobin/onlypoweroftwo
by default is set to FALSE, that parameter allows you to only convert integer variables with a domainsize of 2^p-1 to their binary representationpresolving/convertinttobin/samelocksinbothdirections
by default is set to FALSE, that parameter allows you to convert only integer variables to their binary representation, which have the same amount of up- and downlockspresolving/gateextraction/sorting
by default is set to 1, that parameter determines if you want to try to extract big-gates(-1) or small-gates(1) at first by ordering bigger/smaller logicor constraint up front, or use them as they are (0)presolving/gateextraction/onlysetpart
by default is set to FALSE, that parameter allows you to only extract set-partitioning and no and-constraintspresolving/gateextraction/searchequations
by default is set to TRUE, that parameter allows you to search for logicor constraints and set-packing/-partitioning constraints with same variablespropagating/s/timingmask
for changing the timingmask for calling the propagtion method of all propagator pluginspropagating/probing/maxdepth
to set the maximal depth until the probing propagation is executedreading/cnfreader/useobj
to state whether an artificial objective, depending on the number of clauses a variable appears in, should be used, by default set to FALSE, old default behavior of reader corresponds to TRUEseparating/cgmip/{minnodelimit,maxnodelimit}
to determine node limit.separating/closecuts/maxlpiterfactor
for iteration limit in relative interior point computationseparating/oddcycle/maxunsucessfull
to automatically turn off separationoncepernode
in Rounding and Simple Rounding heuristic
Data structures
- new data structure for binary trees (
SCIP_BT
andSCIP_BTNODE
in pub_misc.h) - renamed data structure
SCIP_STAIRMAP
toSCIP_PROFILE
- added new stages
SCIP_STAGE_INITPRESOLVE
,SCIP_STAGE_EXITPRESOLVE
andSCIP_STAGE_FREE
; renamedSCIP_STAGE_FREESOLVE
toSCIP_STAGE_EXITSOLVE
- Changed the counting system within SCIP heavily.
SPARSESOLUTION
was renamed toSCIP_SPARSESOL
and moved from cons_countsols.h to struct_misc.h
Testing
- the check script now recognizes MIQCP and MINLP instances
- make test now also checks instances in wbo, cnf, osil and fzn format
- renamed parameter SCRDIR of
make testgams
to CLIENTTMPDIR and changed its default to/tmp
Build system
Makefile
- CppAD source code is now distributed with SCIP (
src/cppad
), so thatlib/cppad
is not used anymore; the default for EXPRINT has changed from none to cppad
Fixed bugs
- fixed bug with strong branching with the LP status for conflict analysis
- fixed bug w.r.t. adding a value to the objective offset of the transformed problem
- fixed wrong assert in feasibility pump stage 3
- fixed bug in solve.c, applied bounding for the initial lp was only done if root-lp-solution was valid but another solution could also have been added
- primal solutions with infinite objective value are now automatically discarded
- all plugins that solve sub-SCIPs now do not stop the whole solution process if there has been an error
- fixed bug in cip reader, wrong use of SCIPstrtok()
- Variables:
- fixed bug in shiftandpropagate w.r.t. SCIPconstructLP() which can have the side effect that variables are created
- method SCIPvarGetProbvarSum() (and thus also SCIPgetProbvarSum()) returns +/-infinity if the variable resolves to a variable fixed to +/-infinity (depending on the sign of the scalar) but does not multiply with the scalar, anymore
- better handling of infinite solution values for aggregated and negated variables
- fixed bug that disabled multi-aggregation of two integer or implicit integer variables
- fixed bug in sol.c with requesting values of transformed variables in original solution; previously this had only been handled in SCIPgetSolVal(), now the handling has been moved to SCIPsolGetVal()
- fixed several bugs writing an mps file in the reader_mps.c, e.g. writing fixed variables which are not (yet) removed and writing integer variables even with an objective value of 0, if they only exist in non-linear constraints
- Separation:
- fixed minor bugs with respect to counting generated and lifted cuts in sepa_oddcycle
- fixed bug in sepa_clique.c, could not handle only empty cliques, that were not removed
- Heuristics:
- fixed potential bugs in shiftandpropagate heuristic concerning the transformation update of a variable with free status
- fixed bug in heur_zirounding with computation of up/downslacks
- fixed bug in mutation heuristic with unnecessary aborts due to a wrong memory limit
- fixed potential bug in fix-and-infer heuristic with variables being fixed to infinite value
- fixed bug in diving heuristics with variables being fixed to values outside their domain
- fixed bug in simple rounding heuristic with column generation for variables with strictly positive lower bound
- made Octane heuristic numerically more stable to avoid asserts being caused by cancellation
- fixed bug in mutation heuristic with variables being fixed to infinite values
- do not run heur_shiftandpropagate if there is no LP
- LP Interface:
- fixed bug in Cplex LPI: after running simplex, solisbasic flag was always true, which might be wrong if Cplex hit a time limit
- fixed bug in SCIP probing mode with cleared LPI state but solved LP
- fixed assert with
LPI=none
(need to count rows/cols in lpi_none) - fixed bug in SoPlex LPI where objective sense was not correct after reading LP from file in SCIPlpiReadLP()
- Constraints:
- fixed bug in scip.c adding a constraint in SCIPgetConsCopy() to the constraint hashmap
- fixed bug in cons_linear w.r.t recalculation of unreliable activities
- fixed bug in cons_linear concerning huge activity values: besides infinite contributions, we now also treat huge contributions separately, count their occurences in a constraint and provide a relaxed activity value
- fixed bug in cons_xor.c parsing a constraint
- fixed count of propagations in cons_indicator and only try to propagate if variables are not yet fixed
- fixed some bugs in cons_disjunction.c (wrong assert, forgotten deletion of constraint, wrong SCIPreleaseCons() call)
Miscellaneous
- first release of GCG, a generic branch-cut-and-price solver built on top of SCIP
- first release of UG, a framework for solving mixed integer programs, mixed integer nonlinear programs and constraint integer programs in parallel
- new SCIP T-shirts
- renamed ZIB Optimization Suite to SCIP Optimization Suite