Release notes for SCIP 2.1

SCIP 2.1.2

Performance improvements

• fixed performance issue in debug mode, where SCIPvarGetLPSol_rec() calculated a value to often, which in the end lead to exponential growth in running time
• force cuts from linearizations of convex constraint in NLP relax solution into LP, thus allowing faster proving of optimality for convex NLPs

Fixed bugs

• fixed bug in varAddTransitiveImplic() in var.c, when adding implications on special aggregated, namely negated, variables
• fixed issue if a primal solution leads to a cutoff of the current focus node
• fix compilation issues with zlib 1.2.6
• fixed bug in SCIPsolveKnapsackExactly(), trying to allocate too much memory which led to an overflow and later to a segmentation fault
• fixed bug in sepa_rapidlearning, carrying on the optimization process, when already solved
• Heuristics:
  • fixed bug in heur_undercover.c, where a variable with fixed bounds but not of status SCIP_VARSTATUS_FIXED was wrongly handled
  • fixed bug in heur_oneopt.c which forgot to check LP rows if local rows are present
• Constraints:
  • fixed bug in SCIPsolveKnapsackExactly()
  • fixed bug in cons_quadratic where bounds on activity of quadratic term were not always invalidated when quadratic variables were removed
  • fixed bug in cons.c, where after a restart the arrays for all initial constraints were corrected in the initsol process instead of the initpre process, this was to late because you might change the status in presolving which lead to an assert()
  • fixed bug in NLP representation of abspower constraints handling (x+a)^2 with nonzero a
  • fixed bug parsing an and-constraint in cip format
  • fixed bug in cons_setppc, did not handle new constraints with inactive variables
  • fixed bug in cons_xor.c which did not copy the artificial integer variable (used for the lp relaxation)

SCIP 2.1.1

Features

• the pseudo objective propagator can be forced to propagate if active pricers are present; this can be done if for all (known or unknown) variables follows that: they have positive (negative) objective coefficient and the global lower (upper) bound is zero.

Performance improvements

• improvements in undercover heuristic
• improve SCIPintervalSolveBivariateQuadExpressionAllScalar() for ax=0 case if x has 0 in the interval for the linear coef.
• better domain propagation for quadratic constraints that consist of non-overlapping bilinear terms only
• ensure that a fixing of a variable in an abspower constraint is propagated to a fixing of the other variable
• improvements in undercover heuristic, e.g., bound disjunction constraints are considered when setting up the covering problem

Interface changes

Changed parameters

• changed parameter propagating/pseudoobj/maxcands to propagating/pseudoobj/minuseless (see prop_pseudoobj.c) due to revision of the pseudo objective propagator

New parameters

• added parameters heuristics/undercover/coverbd and heuristics/undercover/fixingorder

Fixed bugs

• fixed numeric issue in aggregations
• fixed pseudo cost computation
• fixed bug with setting type of slack variables to be implicitly integral
• fixed bug when copying problem data in c++ case returned with the result SCIP_DIDNOTRUN
• fixed computation of counter which state the changes since the last call of a presolver
• fixed handling of unbounded solutions, including double-checking their feasibility and that the primal ray is a valid unboundedness proof and reoptimizing the LP with modified settings if the solution is not feasible
• fixed compilation issues with negate() function in intervalarith.c on exotic platforms
• fixed bug in SCIPsortedvecDelPos...() templates
• pseudo objective propagator does not propagate it active pricers are present
• fixed bug in heur_shiftandpropagate.c concerning the treatment of unbounded variables
• workaround for trying to add variable bounds with to small coefficients
• Reading and Writing:
  • gams writer now also substitutes $-sign from variable/equation names
  • fixed bug in reader_mps.c: INTEND marker is now also written, if COLUMNS section ends with non-continous variables
  • fixed bug in flatzinc reader w.r.t. boolean expressions
• Constraints:
  • fixed constraint flags evaluation within the ZIMPL reader (reader_zpl.c)
  • fixed bug in SCIPmakeIndicatorFeasible() in cons_indicator.c
  • fixed bug with conflict clause modification in cons_indicator
  • fixed bug in cons_bounddisjunction with uninitialized return values
  • fixed bug in cons_orbitope with calling conflict analysis
  • fixed bug in nlpi_oracle w.r.t. changing linear coefs in a NLP constraint

SCIP 2.1.0

Features

• New original solution storage capability, which allows transfering solutions between SCIP runs
• SCIP-CPX is now threadsafe
• comparison of solutions now also works for original solutions
• can now compute the relative interior point of the current LP
• interval arithmetics for power, log, exp, bivariate quadratic expressions should be rounding safe now
• LP iterations in resolving calls can now be limited w.r.t. the average number of LP iterations in previous calls (after the root node); this is currently only done for the initial LP solve at a node and the corresponding parameter resolveiterfac is set to -1 (no limit) per default
• it is now possible in SCIP_STAGE_TRANSFORMED to call SCIPaddVarLocks() (i.e. to lock variables in initialization methods)
• changed computation of optimality gap which is now done in the same way as described in the MIPLIB 2010 paper: the gap is 0, if primalbound (pb) and dualbound (db) are equal (within tolerances), it is infinity if pb and db have opposite signs and (this changed), if both have the same sign, the difference between pb and db is devided by the minimum of the absolute values of pb and db (instead of always the dual bound)
• functionality to use the bound flipping ratio test of SoPlex is available (requires at least version 1.5.0.7)
• there exists now a solution candidate store for the original problem; during transformation these solutions are tried; during free the transformed problem the best feasible solution of the transformed problem are copied to the solution candidate store of the original problem; this useful if you solve several problems iteratively, solutions get now carried over automatically.
• reworked concept of lazy bounds: they can now also be used for problems where constraints and objective together ensure the bounds; to allow this also for diving heuristics that might change the objective and thus destroy this property, lazy bounds are explicitly put into the LP during diving and removed afterwards
• SCIP_HASHMAP now works also without block memory
• The variable deletion event is now a variable specific event and not global, anymore.
• All timing flags are now defined type_timing.h.
• all C template files are now called <plugintype>_xyz.{c,h} instead of <plugintype>_xxx.{c,h}
• Separators and Cuts:
  • reorganized computation of scores in cut filtering: instead of the computation at the time of addition, scores are now only computed w.r.t. the current LP solution and when cut filtering is performed; one can now fill the cut storage with cuts that were separated for different solutions
  • New separator for close cuts and a new function to compute relative interior points of the LP
  • added first version of sepa_closecuts.{c,h} to separate cuts w.r.t. a point that is closer to the integral polyhedron
• Constraints:
  • implement possibility to force a restart in cons_indicator if enough indicator variables have been fixed
  • the xor constraint handler can now parse its constraints
  • the bounddisjunction constraint handler can now parse its constraints
  • the knapsack, setppc and soc constraint handler can now parse their constraints
  • the varbound constraint handler can now parse its constraints
  • added beta version of variable deletion: for branch-and-price application, variables can now be completely deleted from the problem; variables that are deletable have to be marked with SCIPvarMarkDeletable(), constraint handlers can implement the new SCIP_DECL_DELVARS callback that should remove variables from the constraints; at the moment, only the linear, the setppc and the knapsack constraint handler support this callback; furthermore, when using this feature, all used plugins have to capture and release variables they store in their data, this is currently only done for the aforementioned constraint handlers as well as the and, the varbound and the logicor constraint handler; for more details about this feature, see the FAQ
  • added pseudoboolean constraint handler (cons_pseudoboolean.{c,h})
  • added first version of cons_disjunction.{c,h} which allows a disjunction of constraints
  • added constraint handler for (absolute) power constraints (cons_abspower.{c,h}) to handle equations like z = sign(x)abs(x)^n, n > 1
• Heuristics:
  • new heuristic vbounds which use the variables lower and upper bounds to fix variable and performs a neighborhood search
  • added vbound heuristic (heur_vbounds.{c,h})
  • added clique heuristic (heur_clique.{c,h})
• Reading and Writing:
  • added writing for wbo files
  • added writing for pip files (linear, quadratic, polynomial nonlinear, polynomial abspower, polynomial bivariate, and and constraints)
  • CIP format variable characters defined, e.g. SCIP_VARTYPE_INTEGER_CHAR
  • Improved support for wbo format for weighted PBO problems, IBM's xml-solution format and pip and zimpl format for polynomial mixed-integer programs
  • New reader for (standard) bounds on variables
  • Extended reader for CIP models to handle various new constraints, including all types of linear constraints
  • flatzinc reader is now capable to read cumulative constraints
  • changed opb(/wbo) reader which now creates pseudoboolean constraints instead of linear- and and-constraints, only a non-linear objective will create and-constraints inside the reader and while reading a wbo file the topcost constraint is created as well
  • added clock for determine the time for reading
  • added reader for variable bounds (reader_bnd.{c,h})
  • Removed method SCIPreadSol(); call solution reading via SCIPreadProb() which calls the solution reader for .sol files.
• Nonlinear:
  • Major extensions for nonlinear CIP, new option for n-ary branching on nonlinear variables (within pseudocost branching rule)
  • added BETA version of constraint handler for nonlinear constraints (cons_nonlinear.{c,h}) to handle nonlinear equations given by algebraic expressions using operands like addition, multiplication, power, exp, log, bivariate nonlinear constraints; currently no trigonometric functions
  • added BETA version of constraint handler for bivariate nonlinear constraints (cons_bivariate.{c,h}) to compute tight estimators for 1-convex and convex-concave bivariate nonlinear functions (given as expression tree)
  • the gams writer can now write nonlinear, abspower and bivariate constraints
  • Extended writer for GAMS and pip format to write more types of nonlinear constraints
  • the pip and zimpl reader now create nonlinear constraints for polynomials of degree > 2
• Presolving:
  • new dual presolving methods in cons_setppc and cons_logicor
  • new presolving step removeConstraintsDueToNegCliques in locigor constraint handler which updates logicor constraints to setppc constraints if a negated clique inside this constraint exist, by default is off
  • new presolving step in cons_knapsack (detectRedundantVars, deleteRedundantVars) which determines redundant variables in knapsack constraint with or without using clique information
  • cons_logicor is now able to replace all aggregated variables in presolving by there active or negation of an active variable counterpart
  • prop_pseudoobj is now working in presolving as well
  • implement presolving in exitpre() in cons_orbitope and cons_indicator
• Propagators:
  • added counter for number calls and timing for resolve propagation calls for constraint handler and propagators
  • Propagators are now also called in node presolving
  • the probing presolver presol_probing.{c.h} is now a propagator prop_probing.{c,h}, all corresponding parameters moved as well
  • the redcost separator sepa_redcost.{c.h} is now a propagator prop_redcost.{c,h}, all corresponding parameters moved as well
  • outsourced propAndSolve() method in solve.c which calls domain propagation and solving of the lp and relaxation
• Statistic:
  • solutions which are given by the user from the outside are now marked by # in the output
  • the Solving Time is now spitted into presolving, solving and reading time
  • Presolvers section has new column AddCons which states the number of added constraint
  • Constraints section has new column named #ResProp which show the number of resolve propagation calls of certain constraint handler
  • Constraint Timing section has a new column #ResProp which states the time spend in resolve propagation method of the constraint handler
  • improved output of propagators in display statistics
  • new section Propagator Timing which shows the time spend in different callbacks of the propagator
  • rearranged first two columns of Propagators section; #Propagate and #ResProp stating the number of call for propagation and resolve propagation; the Time column is moved into the new section Propagator Timings
  • Constraints section has new column named MaxNumber which the maximum number of active constraint of a certain constraint handler
  • added two columns Time-0-It and Calls-0-It in the LP section which states the number of LP call and time spend for solving LPs with zero iterations (only refactorization)
  • The display of statistics for presolvers, propagators, constraints and LP solving has changed.

Performance improvements

• Reorganized filtering process of separation storage (allows adding cuts for different solutions)
• Improved presolving for various constraint handlers
• Improved propagation methods for variable bound constraints
• Improved performance for quadratic constraints
• performance improvements in prop_vbounds
• child selection rules now get also applied when the relaxation value is equal to the bound changed in branching
• added dual reduction to cons_cumulative.c
• for continuous variables, the pseudo costs update and the pscost branching rule now use the same strategies for updating the pseudo costs and estimating the improvement in the LP bound
• only perform probing if the variables are locked
• performance and memory consumption improvements in xmlparse.c
• Improved knapsack cover cuts
• avoid very long separation times of LEWIs in cons_knapsack for very large minimal covers
• used SCIPallocMemoryArray() instead of SCIPallocBlockMemoryArray() which leads to fewer memory consumption in getLiftingSequence() in cons_knapsack, also improved cache use bei using an extra array instead blockmemory chunks
• switched FASTMIP from 1 to 2 for CPLEX and changed default pricing rule back to steepest edge pricing instead of quickstart steepest edge pricing
• made sorting method more robust
• LNS heuristics now use SCIPcopy() by default
• considering inactive variables in undercover heuristic; limiting effort for solving covering problem
• if during probing mode the LP relaxation is solved from scratch, e.g., when calling the shiftandpropagate heuristic before root node solving, then we clear the resulting LP state, since it might be a bad starting basis for the next solve of the LP relaxation (controlled by new parameter lp/clearinitialprobinglp)
• included LP simplifier into SoPlex LP interface, applied when solving from scratch (lpi_spx.cpp)
• new presolving steps in varbound constraint handler, tightening bounds, coefficients, sides and pairwise presolving

Interface changes

• Miscellaneous:
  • The emphasis setting types now distinguish between plugin-type specific parameter settings (default, aggressive, fast, off), which are changed by SCIPsetHeuristics/Presolving/Separating(), and global emphasis settings (default, cpsolver, easycip, feasibility, hardlp, optimality, counter), which can be set using SCIPsetEmphasis().

New and changed callbacks

• added propagator timings SCIP_PROPTIMING_BEFORELP, SCIP_PROPTIMING_DURINGLPLOOP and SCIP_PROPTIMING_AFTERLPLOOP for all propagation callbacks (see propagators and constraint handlers) which lead to calling the propagation methods of a propagator before the lp is solved, during the lp loop and after the lp solving loop
• Conflict Analysis:
  • Added parameter separate to conflict handler callback method SCIP_DECL_CONFLICTEXEC() that defines whether the conflict constraint should be separated or not.
• Constraint Handler:
  • The new constraint handler callback SCIP_DECL_CONSDELVARS() is called after variables were marked for deletion. This method is optional and only of interest if you are using SCIP as a branch-and-price framework. That means, you are generating new variables during the search. If you are not doing that just define the function pointer to be NULL. If this method gets implemented you should iterate over all constraints of the constraint handler and delete all variables that were marked for deletion by SCIPdelVar().
• NLP Solver Interface:
  • The callbacks SCIP_DECL_NLPIGETSOLUTION() and SCIP_DECL_NLPISETINITIALGUESS() got new parameters to get/set values of dual variables.
  • The callback SCIP_DECL_NLPICOPY() now passes the block memory of the target SCIP as an additional parameter.
• Presolving:

  • New parameters isunbounded and isinfeasible for presolving initialization (SCIP_DECL_CONSINITPRE(), SCIP_DECL_PRESOLINITPRE(), SCIP_DECL_PROPINITPRE()) and presolving deinitialization (SCIP_DECL_CONSEXITPRE(), SCIP_DECL_PRESOLEXITPRE(), SCIP_DECL_PROPEXITPRE()) callbacks of presolvers, constraint handlers and propagators, telling the callback whether the problem was already declared to be unbounded or infeasible. This allows to avoid expensive steps in these methods in case the problem is already solved, anyway.

    Note, that the C++ methods

    • scip::ObjConshdlr::scip_presol() corresponding to SCIP_DECL_CONSPRESOL()
    • scip::ObjConshdlr::scip_initpre() corresponding to SCIP_DECL_CONSINITPRE()
    • scip::ObjPresol::scip_initpre() corresponding to SCIP_DECL_PRESOLINITPRE()
    • scip::ObjProp::scip_initpre() corresponding to SCIP_DECL_PROPINITPRE()
    • scip::ObjConshdlr::scip_exitpre() corresponding to SCIP_DECL_CONSEXITPRE()
    • scip::ObjPresol::scip_exitpre() corresponding to SCIP_DECL_PRESOLEXITPRE()
    • scip::ObjProp::scip_exitpre() corresponding to and SCIP_DECL_PROPEXITPRE() are virtual functions. That means, if you are not adding the new parameters, your code will still compile, but these methods are not executed.
  • Propagators are now also called in during presolving, this is supported by the new callback methods SCIP_DECL_PROPINITPRE(), SCIP_DECL_PROPEXITPRE(), and SCIP_DECL_PROPPRESOL().
  • The new parameters nnewaddconss and naddconss were added to the constraint handler callback method SCIP_DECL_CONSPRESOL() and the presolver callback method SCIP_DECL_PRESOLEXEC(). These parameters were also added to corresponding C++ wrapper class methods (scip_presol() in objconshdlr.h and scip_exec() in objpresol.h)
• Problem Data:
  • The callback SCIP_DECL_PROBCOPY() got a new parameter global to indicate whether the global problem or a local version is copied.

Deleted and changed API methods

• implemented SCIPlpiGetPrimalRay() in SoPlex interface that has become available with SoPlex version 1.5.0.2
• allowed calling SCIPgetRowSolActivity() in SCIP_STAGE_SOLVED, since LP is still available
• various extensions and modifications for expressions and expression trees (too much to state here)
• The result value SCIP_NEWROUND has been added, it allows a separator/constraint handler to start a new separation round (without previous calls to other separators/conshdlrs).
• SCIPcalcNodeselPriority() got a new parameter branchdir, which defines the type of branching that was performed: upwards, downwards, or fixed.
• Constraint Handlers:
  • Method SCIPincludeQuadconsUpgrade() of quadratic constraint handler got new parameter active to indicate whether the upgrading method is active by default.
  • Method SCIPseparateRelaxedKnapsack() in knapsack constraint handler got new parameter cutoff, which is a pointer to store whether a cutoff was found.
• Nonlinear expressions, relaxation, and solver interface:
  • SCIPcreateNLPSol() now creates a SCIP_SOL that is linked to the solution of the current NLP relaxation
  • Various types and functions dealing with polynomial expressions have been renamed to use the proper terms monomial and polynomial in nonlinear expressions (nlpi/∗expr*); results in many renamings of types, structs and methods.
  • The methods SCIPnlpGetObjective(), SCIPnlpGetSolVals(), and SCIPnlpGetVarSolVal() have been removed, use SCIPgetNLPObjval(), SCIPvarGetNLPSol() and SCIPcreateNLPSol() to retrieve NLP solution values instead. SCIPcreateNLPSol() now returns an error if NLP or NLP solution is not available
  • Removed methods SCIPmarkRequireNLP() and SCIPisNLPRequired(), because the NLP is now always constructed if nonlinearities are present.
  • SCIPgetNLP() has been removed and NLP-methods from pub_nlp.h have been moved to scip.h, which resulted in some renamings, too.
  • renamed SCIPexprtreeEvalSol() to SCIPevalExprtreeSol() and now located in scip.h.
  • renamed SCIPexprtreeEvalIntLocalBounds() to SCIPevalExprtreeLocalBounds() and now located in scip.h.
  • renamed SCIPexprtreeEvalIntGlobalBounds() to SCIPevalExprtreeGlobalBounds() and now located in scip.h.
  • The functions SCIPnlpiGetSolution() and SCIPnlpiSetInitialGuess() got additional arguments to get/set dual values.
  • The method SCIPgetNLPI() got a new parameter nlpiproblem, which is a pointer to store the NLP solver interface problem.
• Timing:
  • SCIPincludeProp() got additional parameters to set the timing mask of the propagator and the new callbacks and parameters related to calling the propagator in presolving.
  • SCIPincludeConshdlr() got additional parameters to set the variable deletion callback function and the timing mask for propagation.
  • removed parameters timelimit and memorylimit from SCIPapplyRens()
  • The parameters timelimit and memorylimit were removed from SCIPapplyRens().
• Problem Data:
  • The method SCIPcopyProb() got a new parameter global to indicate whether the global problem or a local version is copied.
• Writing and Parsing Constraints:
  • The methods SCIPwriteVarName(), SCIPwriteVarsList(), and SCIPwriteVarsLinearsum() got a new boolean parameter type that indicates whether the variable type should be written or not.
  • The methods SCIPparseVarName() and SCIPparseVarsList() got a new output parameter endptr that is filled with the position where the parsing stopped.
  • The method SCIPwriteVarsList() got additionally a new parameter delimiter that defines the character which is used for delimitation.
• Variables:
  • SCIPmarkDoNotMultaggrVar()/SCIPvarMarkDoNotMultaggr() now allow to mark negated and aggregated variables
  • SCIPgetVarCopy() got a new parameter success that will be FALSE if method is called after problem creation stage and no hash map is given or no image for the given variable is contained in the given hash map.
  • SCIPchgVarType() got an extra boolean parameter to store if infeasibility is recognized while upgrading a variable from continuous type to an integer type.
  • SCIPdelVar() got a new parameter deleted, which stores whether the variable was successfully marked to be deleted.

New API functions

• information about the quality of the solution of an LP (currently the condition number of the basis matrix) can now be:
  • requested from the LPI (currently only available for CPLEX): methods SCIPlpiGetRealSolQuality() and
  • SCIPprintLPSolutionQuality() command display lpsolquality in interactive shell display column lpcond to show
  • estimate on condition number, if available
• SCIPround() and SCIPfeasRound() to round to nearest integer
• SCIPsortRealRealIntInt() and corresponding sorting/inserting/deleting methods in pub_misc.h and necessary defines in misc.c
• SCIPsortRealIntLong(), SCIPsortPtrPtrRealInt() and corresponding sorting/inserting/deleting methods in pub_misc.h and necessary defines in misc.c
• SCIPcomputeLPRelIntPoint() to compute relative interior point of the current LP
• SCIPstartSolvingTime() and SCIPstopSolvingTime() which can be used to start or stop the solving time clock
• SCIPstrToRealValue() and SCIPstrCopySection() in pub_misc.h; these methods can be used to convert a string into a SCIP_Real value and to copy a substring.
• SCIPgetBinvarRepresentatives() which gets binary variables that are equal to some given binary variables, and which are either active, fixed, or multi-aggregated, or the negated variables of active, fixed, or multi-aggregated variables
• SCIPhasPrimalRay() and SCIPgetPrimalRayVal() that return whether a primal ray is stored and which value a given variable has in the primal ray, respectively
• SCIPsetConsModifiable()
• SCIPsetParam() which is a generic parameter setter method, independent of the parameter type
• SCIPpropInitpre(), SCIPpropExitpre(), SCIPpropPresol() which initializes, exists and executes the presolving phase
• SCIProwGetAge() to access the age of a row (pub_lp.h/lp.c)
• SCIPsolGetOrigObj() in pub_sol.h which returns for a solution in the original problem space the objective value
• SCIPretransformSol() in scip.h that allows to retransform a solution to the original space
• SCIPlpiClearState() to LP interfaces for clearing basis information in the LP solver
• SCIPgetSubscipDepth() to access the depth of the current SCIP as a copied subproblem
• SCIPdebugAddSolVal() and SCIPdebugGetSolVal() to add/get values to/from a debug solution
• SCIPsepastoreRemoveInefficaciousCuts() to remove non-efficious cuts from the separation storage
• Nodes:
  • SCIPnodeGetParent() to get parent node of a node
  • SCIPnodesSharePath() in pub_tree.h that determines whether two nodes are on the same leaf-root path
  • SCIPnodesGetCommonAncestor() in pub_tree.h that finds the common ancestor node for two given nodes
• Read and Write:
  • SCIPgetReadingTime() which returns the time for reading in seconds
  • SCIPparseVarsLinearsum(), SCIPparseVarsPolynomial() and SCIPwriteVarsPolynomial() and for writing and parsing polynomials in constraint handler writing/parsing methods
• Memory:
  • SCIPcreateMesshdlrPThreads() and SCIPfreeMesshdlrPThreads() for allocating and deleting necessary memory for message handlers for parallel pthread version
  • SCIPallocClearMemoryArray() and BMSallocClearMemoryArray() for allocating cleared memory arrays in scip.h and memory.h
• Intervals:
  • SCIPintervalPowerScalarInverse() to solve an equation y = x^p for given bounds on y and scalar exponent p
  • SCIPintervalQuadBivar() to compute tight bounds on a bivariate quadratic form
  • SCIPintervalSolveBivariateQuadExpressionAllScalar() to compute tight bounds on the solutions of a bivariate quadratic equation
• Variables:
  • SCIPcomputeVarCurrent{L,U}b{Local,Global}() to compute local or global lower or upper bounds of a multiaggregated variable from the bounds of the aggregation variables
  • SCIPbranchVarValNary() for n-ary variable branching
  • SCIPgetNegatedVars() which returns all negated variables for a given array of variables, if the negated variables are not existing yet, they will be created
  • SCIPgetNTotalVars() that returns the total number of created vars, icluding variables that were deleted in the meantime
  • SCIPvarGetHashkey(), SCIPvarIsHashkeyEq(), SCIPvarGetHashkeyVal() in pub_var.h which can be used for SCIP_HASHTABLE of variables
  • SCIPvarGetNBdchgInfosLb() and SCIPvarGetNBdchgInfosUb() in pub_var.h returning the number of lower or upper bound changes on the active path
  • SCIPvarGetBdchgInfoLb() and SCIPvarGetBdchgInfoUb() returning the bound change information at the given position
  • SCIPvarMarkDeletable() to mark a variable to be deletable completely from the problem (for branch-and-price); can only be called before the variable is added to the problem
  • SCIPvarMarkNotDeletable() that marks a variable to be non-deleteable (used within SCIP for forbidding deletion of variables contained in solution, LP bases, (multi)aggregation, ...)
  • SCIPvarIsDeletable() that returns whether a variable is marked to be deletable (each variable is per default non-deletable)
• NLP:
  • SCIPgetNLPVarsNonlinearity() to get for each variable in the NLP the number of NLP rows in which this variable appears in a nonlinear way
  • SCIPnlrowGetDualsol(), SCIPgetNLPVarsLbDualsol(), SCIPgetNLPVarsUbDualsol() to retrieve dual values from an NLP solution
  • SCIPgetNLPFracVars() to get the fractional variables in an NLP solution
• Propagator:
  • SCIPpropSetPresolPriority() which changes the presolving priority of a given propagator
  • SCIPpropGetPresolPriority(), SCIPpropGetPresolTime(), SCIPpropWasPresolDelayed(), SCIPpropGetNFixedVars(), SCIPpropGetNAggrVars(), SCIPpropGetNChgVarTypes(), SCIPpropGetNChgBds(), SCIPpropGetNAddHoles(), SCIPpropGetNDelConss(), SCIPpropGetNAddConss(), SCIPpropGetNUpgdConss(), SCIPpropGetNChgCoefs(), SCIPpropGetNChgSides(), SCIPpropGetTimingmask(), SCIPpropDoesPresolve() which return corresponding presolving information
  • SCIPpropGetNRespropCalls() and SCIPconshdlrGetNRespropCalls() which return the number of times a propagator or a constraint handler was called for resolving a propagation
  • SCIPpropGetRespropTime() and SCIPconshdlrGetRespropTime() which return time spent for resolving a propagation within a propagator or a constraint handler
  • SCIPcheckCumulativeCondition(), SCIPpropCumulativeCondition() and SCIPrespropCumulativeCondition() in cons_cumulative.h; these methods can be used to check, propagate, or resolve the propagation of a cumulative condition
  • SCIPpropagateCutoffboundVar() in prop_pseudoobj.h which can be used to propagate the cutoff bound for the given variables
• Constraints:
  • added to linear constraint handler SCIPsetUpgradeConsLinear(), which (de-)activates the possibility to upgrade a linear constraint to a specialized linear constraint (e.g. knapsack)
  • SCIPconvertCutsToConss() and SCIPcopyCuts() to scip.{c,h} for copying cuts to linear constraints
  • SCIPaddCoefLogicor() to add a variable to a logic or constraint
  • SCIPfindOrigCons() which return a original constraint with the given name or NULL
  • SCIPconshdlrGetNAddConss() which returns the number of added constraints during presolving by a given constraint handler
  • SCIPpresolGetNAddConss() which returns the number of added constraints during presolving by a given presolver

Command line interface

• New funtionalities in the interactive shell (modify current CIP instance, write NLP relaxation)
• added dialog write nlp to write current NLP relaxation to a file
• new dialog change freetransproblem to free transformed problem in the interactive shell before changing the problem
• it is possible to change bounds of a variable in the interactive shell
• it is possible to add a constraint to a problem in the interactive shell

Interfaces to external software

• Improved SOPLEX interface (LP simplifier)
• Improved CPLEX interface, including measures for numerical stability

Changed parameters

• change default value of parameter nodeselection/restartdfs/selectbestfreq 100
• moved parameters for pseudoboolean constraints from opb-reader to pseudoboolean constraint handler
• changed possible parameter values of branching/pscost/strategy from bri to cdsu: default is now u, i.e., to estimate the LP gain by a branching for external branching candidates (esp. continuous variables) the same way as their pseudo costs are updated
• added possible value d for constraints/soc/nlpform to choose a convex division form for SOC constraint representation in NLP
• renamed parameter constraints/quadratic/linearizenlpsol to constraints/quadratic/linearizeheursol and do linearizations in every solution found by some heuristic
• renamed parameter constraints/quadratic/mincutefficacyenfo to constraints/quadratic/mincutefficacyenfofac and interpret it as a factor of the feasibility tolerance
• removed fastmip setting 2, which means the dualsolution would not be calculated but because SCIP always asks for the dual solution, the lp would be reoptimized to calculate them; so it had no real effect
• all parameters in cons_indicator and cons_sos1 have been converted to lower case!
• changed default value of parameter separating/gomory/maxroundsroot to 10
• changed default value of parameter separating/gomory/maxsepacutsroot to 50
• removed parameter heuristics/subnlp/nlpsolver, use nlp/solver instead

New parameters

• branching/delaypscostupdate to delay the update of pseudo costs for continuous variables behind the separation round: default is TRUE
• branching/lpgainnormalize to set the strategy how the LP gain for a continuous variable is normalized when updating the variables pseudocosts: default is to divide LP gain by reduction of variable's domain in sibling node
• branching/pscost/nchildren and branching/pscost/nary* to enable and customize n-ary branching on external branching candidates (e.g., in spatial branching for MINLP)
• conflict/bounddisjunction/continuousfrac which defines the maximum percantage of continuous variables within a conflict create by the bounddisjunction conflict handler
• conflict/separate which enables or disables the separation of conflict constraints
• constraints/{nonlinear,quadratic,soc,abspower}/sepanlpmincont to specify minimal required fraction of continuous variables in problem to enable linearization of convex constraints in NLP relaxation solution in root
• constraints/indicator/forcerestart and constraints/indicator/restartfrac to control forced restart in cons_indicator
• constraints/indicator/generatebilinear to generate bilinear (quadratic) constraints instead of indicator constraints
• constraints/indicator/maxconditionaltlp to enable a quality check for the solution of the alternative LP
• constraints/indicator/removeindicators to remove indicator constraints if corresponding vub has been added
• constraints/linear/nmincomparisons and constraints/linear/mingainpernmincomparisons to influence stopping criterium for pairwise comparison of linear constraints
• constraints/pseudoboolean/decompose, for pseudoboolean constraints to transform pseudoboolean constraints into linear- and and-constraints
• constraints/quadratic/binreforminitial to indicate whether linear (non-varbound) constraints added due to reformulation of products with binary variables in a quadratic constraints should be initial (if the quadratic constraint is initial), default is FALSE
• constraints/quadratic/checkfactorable to disable check for factorable quadratic functions (xAx = (ax+b)*(cx+d)) in quadratic constraints and not to use of this information in separation (generates lifted tangent inequalities according to Belotti/Miller/Namazifar if also linear vars are present)
• constraints/quadratic/disaggregate to split a block-separable quadratic constraint into several quadratic constraint
• constraints/quadratic/maxproprounds and constraints/quadratic/maxproproundspresolve to limit the number of propagations rounds for quadratic constraints within one propagation round of SCIP solve or during SCIP presolve
• constraints/varbound/presolpairwise that allows pairwise presolving of varbound constraints, default is TRUE
• heuristics/shiftandpropagate/onlywithoutsol to switch whether the heuristic should be called in case a primal solution is already present
• limit/maxorigsol which defines the size of the solution candidate store (default value is 10)
• lp/resolverestore controlling how LP solution is restored after diving: if TRUE by resolving them, if FALSE by buffering them; if lp/freesolvalbuffers is TRUE, we free the buffer memory each time (FALSE by default)
• lp/clearinitialprobinglp to clear LP state at end of probing mode, if LP was initially unsolved
• lp/resolveitermin and lp/resolveiterfac to limit the number of LP iterations in resolving calls: resolveiterfac is a factor by which the average number of iterations per call is multiplied to get the limit, but the limit is at least resolveitermin; default is -1 (no limit) for resolveiterfac and 1000 for resolveitermin
• lp/resolverestore and lp/freesolvalbuffers possibility to buffer and restore LP solution after diving without having to resolve the LP; currently turned off, because performance impact is unclear;
• misc/improvingsols which states whether only solutions which have a better (or equal) primal bound as the best known are checked; this is of interest if the check of a solution is expensive; default value is FALSE
• misc/resetstat which state if the statistics should be reseted if the transformed problem is freed (in case of a benders decomposition this parameter should be set to FALSE) default value is TRUE
• nodeselection/restartdfs/countonlyleafs in node selector restart dfs which can be used to select the counting process of processed nodes
• presolving/donotaggr to deactivate aggregation of variables globally
• pricing/delvars and pricing/delvarsroot that define, whether variables created at a node / the root node should be deleted when the node is solved in case they are not present in the LP anymore
• propagating/s/maxprerounds for all propagators which allows to change to maximal number of rounds of presolving where this propagator participates in
• propagating/s/presoldelay for all propagators which allows to change if the presolving call of the given propagator should be delayed
• propagating/s/presolpriority for all propagators which allows to change the priority of calling the given propagator
• propagating/pseudoobj/propfullinroot for allowing to propagate all variables in the root node, instead of stopping after maxcands which is set by a parameter as well
• reading/gmsreader/bigmdefault and reading/gmsreader/indicatorreform reader_gms is now able to write indicator constraints (reformulated either via big-M or sos1)
• reading/gmsreader/signpower to enable writing sign(x)abs(x)^n as the rarely used gams function signpower(x,n)
• separating/closecuts/maxunsucessful to turn off separation if we can not find cuts
• timing/reading to add reading time to solving time

Data structures

• split off PARAMEMPHASIS from PARAMSETTING (in pub_paramset.c/paramset.c)
• new data structure SCIP_STAIRMAP
• add expression graph data structures and methods for reformulation, domain propagation, simple convexity check on nonlinear expressions and simplification for expression trees and graphs

Testing

• New scripts for running tests with GAMS
• added scripts check_gams.sh, evalcheck_gams.sh and check_gams.awk and target testgams in Makefile
• adjusted all test scripts to use the same new optimality gap computation as in SCIP
• added Makefile option VALGRIND=true to enable running the SCIP checks (make test) through valgrind; valgrind errors and memory leaks are reported as fails
• moved *.test and *.solu files to subdirectory testset in check directory and adjusted test scripts

Build system

Makefile

• Variables:
  • via PARASCIP=true as a Makefile option it is possible to compile SCIP threadsafe in DEBUG-mode, (in OPT-mode it's only necessary if non-default messagehandler or CppAD is used)
  • the make parameter PARASCIP=true leads to threadsafe message handlers where you need to call SCIPcreateMesshdlrPThreads() and SCIPmessageSetHandler()/SCIPmessageSetDefaultHandler() and SCIPfreeMesshdlrPThreads(); therefore we need to link with pthread library
  • new variable in Makefile which define installation directory for the libraries, /lib/, binary, /bin and include headers, /include, the default value is the empty string
• Linking:
  • Linking against Clp and Ipopt has been simplified. Only the directory where the package has been installed need to be provided now. For details see the INSTALL file.
  • to link against IPOPT, only the base directory of an Ipopt installation need to be specified now; additionally, if building with gnu compilers, the Ipopt libraries directory is stored in the SCIP binary, which should make it easier to run with Ipopt shared libraries
  • to link against Clp, only the base directory of an Clp installation needs to be specified now
• Targets:
  • New targets (un)install in Makefile, support for valgrind in testing environment
  • new target make libs which compiles only the libraries
  • new target in Makefile install performs make and copies using the install command the include headers, binary, and libraries
  • new target in Makefile uninstall removes libraries, binary and include headers form INSTALLDIR
  • removed target lintfiles, this target is now imitated by the lint target and a none empty variable FILES

Fixed bugs

• fixed bug in copying if the target SCIP already is in solving stage: it might be that the copy of a variable cannot be found/created
• fixed bug trying to print big messages bigger than SCIP_MAXSTRLEN
• fixed bug w.r.t. counting feasible solutions and turned of sparse solution test
• LP solution status is now checked when checking root LP solution. Otherwise, due to different time measurements, it might happen that the LP solving was stopped due to the time limit, but SCIP did not reach the limit, yet.
• fixed bug trying to tighten multiaggregated variables, which have only one active representation and this variable is already tightened
• fixed possible buffer overrun in tclique_graph.c
• fixed issue with interactive shell in case (user) plugins are included after the default plugins
• fixed bug where mutiaggregating leads to an aggregation and both variables were of implicit or integral type
• fixed bug in conflict.c, where LPi was manipulated, but not marked as not solved
• Tree:
  • fixed assertion in tree.c w.r.t. node estimation
  • fixed bug in debug.c: removed tree nodes had not been checked if they were pruned due to an incumbent solution found by a diving heuristic
• Bounds:
  • fixed bug which occured when changing a bound in the solving stage when this variables got upgraded from continuous to a integer type, where the bounds of this variable were still not integral; due to that SCIPchgVarType() has changed (see above)
  • fixed bug in handling of lazy bounds that resulted in putting the bounds explicitly into the LP
• Separation:
  • fixed assert in sepa_clique.c which is currently not valid because implicit binary variables in cliques are ignored
  • fixed bug in sepa_zerohalf.c concerning inconsistent construction of solution array of variables and fixed wrong assert about variable bounds
• Constraints:
  • fixed not correct merging of variable in logicor constraint handler and changed the name of the method to a common name used by other constraint handlers too(findPairsAndSets->mergeMultiples)
  • fixed bugs in changing the initial and checked flags for constraints in original problem
  • fixed bug in cons_linear.c, when scaling a constraint maxabscoef was not set correctly, furthermore the correction of maxabscoef was not handled correctly
  • fixed bug in cons_indicator.c trying to copy a constraint where the pointer to the linear constraint did not point to the already transformed linear constraint (, happend when SCIPcopy() is used after transforming before presolving)
  • fixed numerical bug in linear constraint handler: polishing of coefficients after fixing variables led to wrong results for continuous variables fixed to a close-to-zero value.
  • fixed bug in cons_bounddisjunction where branching on multiaggregated variables was tried while all aggregation variables are fixed
  • fixed bug in presolving of cons_logicor.c: adding variable implications can lead to further reductions; added call to applyFixings()
  • fixed bug in cons_countsols.c w.r.t. none active variables
  • fixed bug in cons_linear.c, scaling could have led to wrong values
• Reader:
  • fixed bug in reader_fzn.c w.r.t. cumulative constraints
  • fixed bug in reader_mps.c: if a variables first occurence is in the bounds section, then the corresponding variable bound was lost
  • fixed several issues in flatzinc reader
  • deactived checking of zero solution in Zimpl reader when no starting values are provided
  • reader_lp is now able to read lines longer than 65534 characters
• Memory:
  • fixed bug in copying NLPI interfaces that use block-memory (NLPI copy used block memory from source SCIP)
  • fixed memory leak in reader_pip.c
  • fixed memory leak in coloring part of maximum clique algorithm (tclique_coloring.c)
  • fixed memory leak in coloring part of maximum clique algorithm (tclique_coloring.c) in a better way
• Numerics:
  • fixed bug which occured when the dual farkas multipliers were not available in the lpi because the LP could only be solved with the primal simplex due to numerical problems
  • fixed bug in ZI round heuristic that led to infeasible shiftings for numerically slightly infeasible rows with close-to-zero coefficients
  • fixed numerical issue in octane heuristic: close-to-zero values for ray direction could have led to bad computations
• Propagation:
  • fixed bug in propagation of indicator constraints: cannot fix slack variable to 0 if linear constraint is disabled/not active
  • fixed bug in cons_linear.c while sorting the eventdatas during the binary variable sorting for propagation
  • fixed bug and wrong assert in heur_shiftandpropagate.c when relaxing continuous variables from the problem
  • fixed bug in cons_orbitope:resprop() for the packing case
  • fixed wrong changing of wasdelayed flag for propagators
  • fixed bug using wrong sign in infinity check in prop_pseudoobj
  • fixed bug in redcost propagator: can only be called if the current node has an LP
  • fixed bug w.r.t. infinity loop during propagation

Miscellaneous

• The interface contains several additional callback functions and parameters for plugins. Some effort may be required to compile your old projects with SCIP 2.1. For details see section Changes between version 2.0 and 2.1 in the doxygen documentation.