Release notes for SCIP 2.0

SCIP 2.0.2

Performance improvements

• improved twoopt-heuristic by considering larger search domains
• the SoPlex interface now has the capability to provide a primal ray, provided it is compiled against the next SoPlex release (>= 1.5.0.2)
• calculation of node priority now also works when variable's relaxation value is equal to a bound
• fixed issue w.r.t. calling primal heuristics after presolving detected infeasibility
• Constraints:
  • fasten propagation in cons_knapsack.c due to negated clique partitions
  • recalculating only needed partitions in cons_knapsack.c, not always both
• Memory:
  • reduced memory usage of shift-and-propagate heuristic
  • knapsack constraints are now separated faster; SCIPsolveKnapsackExactly() now works faster and requires less memory
  • fasten knapsack separation by replacing SCIPallocBuffer(Array) through SCIPallocBlockMemory(Array)
  • improved runtime and memory consumption in SCIPsolveKnapsackExactly() in cons_knapsack.c

Fixed bugs:

• fixed make/make.project
• fixed wrong assert in plugins that use SCIPcopy()
• fixed bug in DINS w.r.t. column generation
• fixed bug in var.c where a possible multiaggregation was resolved to an aggregation but the variables types were not checked to prefer more general types for aggregating; possible memory loss removed
• fixed bug in prop_vbounds.c w.r.t. infinity lower and upper bound of variable bound variables
• fixed bug w.r.t. setting wall clocks
• fixed wrong assert in var.c (replaced == through SCIPsetIsEQ()), real values do not have to be exactly the same when computed in different function
• fixed bug in SCIPsolveIsStopped() where it could happen that TRUE was reported if a nodelimit was reached but checknodelimits had been set to FALSE
• fixed three bugs when writing in fzn format (wrongly splitted writing buffer, wrong variables was used, floats were printed to short)
• fixed bug in conflict.c, infeasibility analysis with big values led to wrong result
• Heuristics:
  • fixed bug in DINS heuristic that occured when the incumbent solution value is outside the variable's current domain
  • fixed behavior of LNS heuristics when the subproblem aborts: continue in optimized mode, stop in debug mode
  • fixed segmentation fault in heur_subnlp.c which occured if resolving the NLP with a tighter feasibility tolerance failed with a solver error
  • fixed bug in heur_subnlp.c where constraints forbidding variable fixations where added if a cutoff was used in the subproblem
  • fixed bug in heur_subnlp.c where wrong constraints forbidding variable fixations where added in case of general integers
• NLP:
  • fixed bug in changing quadratic coefficients of a row in the NLP
  • fixed various small bugs in nonlinear expressions code
  • fixed removal of fixed linear variables from a nonlinear row: a fixed variable may have not been removed if there was also a multiaggregated variable
• LP:
  • implemented SCIPlpiGetPrimalRay() in SoPlex interface that has become available with SoPlex version 1.5.0.2
  • fixed two bugs at nodes with unbounded LP relaxation: don't check lp rows of infinite solution; don't analyze conflict due to primal cutoff bound of -infinity
  • fixed wrong assumption that an optimal LP solution in the root is optimal for the problem if there are no active pricers, need to check also whether all variables are in the LP
• Constraints:
  • fixed bug in reader_cip regarding reading of very long constraints
  • fixed bug while after restarting possible the aggregted variables were not removed in setppc constraints
  • fixed bug in cons_knapsack: in seldom circumstances the relaxation of a linear constraint can detect infeasibility, which was not handled properly
  • fixed bug w.r.t. to pricing variables in case new initial constraints come in during the price and cut loop
  • fixed bug in cons_soc.c w.r.t. upgrading from quadratic constraints with finite left-hand-side
  • fixed bug caused by not (correctly) counting boundchanges in cons_varbound.c
  • fixed bug in sorting mechanism in cons_xor.c
  • fixed wrong (neg)cliquepartition check in cons_knapsack.c when deleting a coefficient
  • fixed bug in cons_quadratic: in seldom cases, fixed variables may have been substituted out wrongly in presolve
  • fixed bugs in cons_countsols.c w.r.t. collecting feasible solutions and forbidding a found solution
  • fixed bug in cons_linear.c: multiaggregated variables were not removed when adding during solve, leading to a failing assert in tightenBounds due to an unsuccessful bound tightening
• Memory:
  • fixed bug concerning overflow in memsize calculation in set.c
  • fixed memory leak in SoPlex LP interface when requesting an unbounded solution
  • fixed memory leak in SoPlex LP interface when solving with LP scaling
  • fixed memory leaks in reader of TSP example

SCIP 2.0.1

Performance improvements

• SCIP with SoPlex as LP solver now uses auto pricing by default (start with devex, switch to steepest edge after some iterations); this fixes timeouts on instances where devex converges very slowly
• fixing lifting of new knapsack items which are negated items of already included items, this could lead to very long presolving
• fixed performance issue in presolving w.r.t. to computing the number of new fixings, aggregated, and so on before a constraint handler presolver is called
• in case of adding constraints during pricing with initial flag set to TRUE, we add now these constraints after the pricing round to the LP
• changed parameter values in clique separator in order to avoid very large branch-and-bound trees

Interface changes

New and changed callbacks

• allow access of transformed constraints in SCIP_STAGE_TRANSFORMED

Changed parameters

• replaced parameter constraints/quadratic/minefficacy by constraints/quadratic/minefficacysepa and constraints/quadratic/minefficacyenfo
• added possible values a and e for constraints/soc/nlpform to enable automatic choice and convex exponential-sqrt form for SOC constraint representation in NLP

Fixed bugs

• fixed bug w.r.t. looseobjval; the counting of number of loose variables in the LP data structure was incorrect in case a variable got aggregated or multi-aggregated
• fixed bug in copy method of objvardata which should only create a new SCIP_VARDATA if the implemented subclass create a copy of the given objvardata object
• fixed bug in lp.c where in case of objlimit reached and fastmip not all variables where priced because of an incorrect dual solution
• fixed bugs in binpacking example w.r.t. empty struct and not initializing an array
• fixed bugs in sepa_clique.c concerning incorrect way to ignore implicit binary variables in cliques and non-active variables in implications
• fixed some bugs w.r.t. to casting pointer arrays
• fixed bug in vars.c which handled arrays with parts of original variables during resolving to active variables (using SCIPvarsGetProbvarBinary) wrong
• fixed bug in nlp.c: nlrowSearchQuadElem was using SCIPquadelemSortedFind() incorrectly
• Branching:
  • fixed assertion w.r.t. to probing during the propagation round of a branch-and-bound node
  • fixed computation of node's objective value estimate when branching on continuous variables (see SCIPtreeCalcChildEstimate(), SCIPtreeBranchVar())
  • fixed bug in statistic w.r.t. number of calls for external branching candidates
  • fixes to branching on continuous variables
• Reader:
  • fixed bug in reader_gms.c: linear coefficients for quadratic variables were not printed if they had no square-coefficient
  • fixed bug in reader_mps: indicator constraints do not output the slack variables anymore
• Constraints:
  • fixed bugs in SCIPcopyConss: copy all active constraints (including disabled ones), *valid was not initialized to TRUE
  • fixed bug in debug.c w.r.t. checking of constraints and continuous variables
  • fixed bug in cons.c which didn't allow the changing of the separation and enforcement flag of a constraint in the problem stage
  • corrected behavior of the copy function in cons_indicator.c: create artificial linear constraint if linear constraint was deleted
  • fixed bug in cons_indicator.c: presolving cannot delete linear constraints; several other minor bugfixes
  • fixed bugs in cons_bounddisjunction where the branching during the constraint enforcement was done incorrectly
  • fixed bugs in cons_orbitope.c: orbitopal fixing for the packing case had two bugs; also fixed one wrong assert
  • fixed bugs in cons_sos?.c: take average of objestimate
  • fixed bug in cons_logicor, implications on none SCIP_VARTYPE_BINARY variable were handled wrong
  • fixed bug in cons_linear while trying to add a conflict without any variables
  • fixed bug in cons_indicator.c: creating constraints in transformed stage is now possible
• LP Interface:
  • fixed bug w.r.t. memory allocation for all values of a column in lpi_cpx.c
  • fixed bugs in SCIPnlpiOracleChgLinearCoefs() and SCIPnlpiOracleChgQuadCoefs() for the case where new coefficients where added
  • fixed bugs in lpi_none.c w.r.t. debug and opt mode
  • fixed bug in lpi_cpx.c w.r.t. to wrong handling in case the crossover did not succeed
• Heuristics:
  • fixed bug in heur_subnlp when initialized starting values of a fixed variable in the NLP of the subscip
  • fixed bug in heur_undercover: removed option globalbounds, since we are not allowed to relax bounds at a probing node
  • fixed bug in heur_shiftandpropagate where some variables were initialized too late
  • fixed numerical issue in some heuristics: nearly-integral values that are between the feasibility and the integrality tolerance might not have been rounded correctly
  • fixed bug in heur_guideddiving: best solution is now copied to avoid deletion in case of many new solutions
  • fixed bug in DINS heuristic, information storage for binary variables could lead to bad memory access in column generation applications
  • fixed bug in heur_shiftandpropagate.c: Now, the heuristic checks rows for global infeasibility at the beginning. This check is only relevant if presolving is disabled.
  • fixed bug in heur_subnlp when forbidding a particular combination of integer variables in the main problem

SCIP 2.0.0

Features

• added relaxation structure to SCIP, it represents global relaxation information independent from a specific relaxator; at the moment, it contains information about the relaxation solution stored in the variables: objective value and validness
• SCIP may now be manually restarted
• SCIPsolveKnapsackExactly() got a new 12. parameter SCIP_Bool* success which stores if an error occured during solving(normally a memory problem)
• SCIP can now handle problems with continuous variables w.r.t. to counting (the projection to the integral variables are counted)
• an XML-parser is available in the src/xml subdirectory
• We do not distinguish between block memory for the original and the transformed problem anymore. The same block memory is now used in both problem stages.
• added new sorting method SCIPsortLongPtr(), SCIPsortDownLongPtr() and all corresponding methods
• added new sorting method SCIPsortRealIntPtr(), SCIPsortDownRealIntPtr() and all corresponding methods
• Heuristics:
  • SCIP can now copy instances (e.g. for heuristics)
  • new undercover heuristic for MINLPs: fixes variables such as to obtain a linear or convex subproblem and solves this
  • primal heuristics may now already be called before presolving, using the new timing point SCIP_HEURTIMING_BEFOREPRESOL. Note that solutions that are added before/during presolving, will be retransformed to the original space.
  • primal heuristics may now be called during presolving, using the new timing point SCIP_HEURTIMING_DURINGPRESOLLOOP
  • added heuristic zirounding (heur_zirounding.{c,h})
  • added heuristic twoopt (heur_twoopt.{c,h})
  • added new NLP heuristic (heur_subnlp.{c,h}) which solves the sub-NLP that is obtained by fixing all discrete variables in the CIP and applying SCIP's presolving
  • feasibility pump heuristic now implements all functionality for feasibility pump 2.0
• Reader:
  • can now read XML-solution files as used by CPLEX
  • the MPS reader can now read MIQPs and MIQCPs where a quadratic objective function can be specified by a QMATRIX or QUADOBJ section and the quadratic part of a quadratic constraint by a QCMATRIX
  • the MPS reader can now write quadratic and SOC constraints
  • the GAMS reader can now write SOC constraints
  • added support for bool_gt, bool_lt, bool_ge, bool_le, bool_ne, bool_not, int_times, int_minus, int_plus, int_negate, float_times, float_minus, float_plus, float_negate constraints to flatzinc reader
  • the LP reader (.lp files) can now read MIQPs and MIQCPs and write quadratic and SOC constraints
  • the LP reader (.lp files) and MPS reader can now read semicontinuous variables, they are handled by creating bound disjunction constraints
  • added new reader for polynomial mixed-integer programs (reader_pip.{c,h}) as used in the POLIP
• Indicator constraints:
  • SCIP can now handle indicator constraints (reading (from LP, ZIMPL), writing, solving, ...) see cons_indicator.h.
  • the indicator constraint can now decompose the problem, i.e., not add the linear constraint to the problem if all of its variables are continuous
  • can now read and write indicator constraints in the (extended) MPS format
  • cons_indicator tries to adapt solutions to get feasible during check
  • cons_indicator allows to store information on other linear constraints that might help to separate cuts
• Constraint handlers:
  • Solution counting extended to constraint integer programs, this also includes constraint integer programs which contain continuous variables
  • The solution behavior of SCIP can be diversified by randomly permuting constraints and variables or randomly determining a set of branching variables with a unique high priority
  • negated cliques (1<=i<=n : sum (x_i) >= n-1) were added and we are using them now inside the knapsack constraint handler, the cliquepartitioning which is returned by SCIPcalcCliquePartition() contains now integer != 0, negatives ones indicates a negated clique and positive ones indicates a normal clique
  • SCIP is now able to detect in DEBUG-mode whether a constraint or variables which will be added, was also created in the same scip instance, if not an error is thrown
  • cons_knapsack is now able to detect negated cliques due to negated cliques on knapsack constraints
  • SCIP is now able to write non-linear opb-files(linear instances with and-constraints)
  • New constraint handlers for linking constraints (only Beta), cumulative constraints, and for breaking orbitopal symmetries
  • negated cliques handling in knapsack constraint handler got changed due to the new method SCIPcalcNegatedCliquePartition() resulting in new consdata members negcliquepartition, negcliquepartitioned and nnegcliques; changed SCIPcalcCliquePartition() so all cliquepartitions (calculated by SCIPcalcCliquePartition() or SCIPcalcNegatedCliquePartition(), which uses the first one) contain again not negative integers
  • and, knapsack, linear, logic, or, quadratic, setpp, varbound, xor and clique constraint handlers can handle implicit binary variables
  • knapsack constraint handler is now able to pairwise presolving constraints
  • constraint handlers logicor, and, or can parse their output
  • constraint handler or can copy its constraints
  • added packing/partitioning orbitope constraint handler for symmetry handling (cons_orbitope.{c,h})
  • added constraint handler for second order cone constraints (cons_soc.(c|h))
  • added constraint handler cons_linking.{c,h} (see cons_linking.c for more details)
  • cons_quadratic can make solutions in CONSCHECK feasible for the quadratic constraints by moving values of linear variables and passing the modified solution to the trysol heuristic
  • constraint handler can now register their upgrade functions for quadratic constraints to cons_quadratic (similar to LINCONSUPGD)
• Separation:
  • New separators for oddcycle cuts and Chvatal-Gomory cuts using sub-MIPs
  • modified implementation of separation algorithms in cons_knapsack.c according to results of diploma thesis; including super-additive lifting (disabled)
  • uncommented decomposeProblem() in sepa_zerohalf.c (in default settings, not used anyway): was not adapted to the case that contiuous variables are allowed in a row
  • new separator rapid learning (sepa_rapidlearning.{c,h}) that produces conflicts, global bound changes, primal solutions and initializes inference values for branching
  • added Chvatal-Gomory cuts separated with a sub-MIP (sepa_cgmip.{c|h})
  • added reader for 'Weigted Boolean Optimization': problems (reader_wbo.{c,h}), this reader needs the reader_opb files
  • new separator oddcycle (sepa_oddcycle.{c,h}) separates oddcycle inequalities using the implication/conflict graph and dijkstra-algorithm based on binary heaps (dijkstra/dijkstra_bh.{c,h})
• Branching:
  • Branching on externally given candidates, the How to add branching rules 'branching rules' have a second new callback method (see type_branch.h for more details): SCIP_DECL_BRANCHEXECEXT(x) can be used to branch on external branching candidates, which can be added by a user's relaxation handler or constraint handler plugin, calling SCIPaddExternBranchCand().
  • added branchcands for relaxator solution, that can be added by the relaxator and used by branching rules
  • added relaxsol to variables, s.t. a relaxator can store a solution on which branching or separation can be done
  • SCIP can now branch on relaxation solutions that are either installed to the relaxsol field of the variables or added to the list of relaxation candidates, e.g., by constraint handlers. Branching on relaxation solutions is performed if the enforcement resulted in an unresolved infeasibility and there are no LP branching candidates, but before pseudo solution branching. The branching rules leastinf, mostinf, random and pscost implement the callback for branching on relaxation candidates.
  • SCIP can branch on continuous variables. The branching value x' must not be one of the bounds. Two children (x <= x', x >= x') will be created.
  • the vbc visualization adds the branching type (lower or upper bound change) and the new bound to the node information
  • the vbc visualization adds the new bound of the branched variable to the node information
• Statistic:
  • added statistic information about the first primal solution to SCIP statistic; in the statistic output a new line appears with this information
  • now the statistic displays the number of calls of the feasibility checking method of each constraint handler and the running time of it
• Propagation:
  • New rounding and propagation heuristics
  • New propagator for variable bounds
  • primal heuristics may now be called directly after the node's propagation loop, using the new timing point SCIP_HEURTIMING_AFTERPROPLOOP
  • following methods SCIPinferVarUbProp(), SCIPinferVarLbProp(), SCIPinferVarLbCons(), SCIPinferVarUbCons() have a new 6th parameter SCIP_Bool force which allows bound tightening even if the difference to the newbound is below bound strengthening tolerance
  • added propagator for variable lower and upper bounds (prop_vbounds.{c,h}); adjusted cons_varbound.c, var.c, and, implics.c to work correctly with the new propagator
• Nonlinear CIPs:
  • Improved constraint handler for quadratic constraints
  • New constraint handler for second order cone constraints
  • New MINLP heuristics (undercover, subnlp)
  • Preliminary support for non-linear relaxations (via expression trees)
  • Automatic branching on solutions from arbitrary relaxations and on continuous variables

Performance improvements

• improved settings/emphasis/cpsolver.set to decrease time per node
• reworked access to pseudo solution and inference value of variables in order to reduce function calls
• changed default value of parameter nodeselection/restartdfs/selectbestfreq to 0; this means if the current node has no children the node with the best bound is selected (SCIPgetBestboundNode())
• added a dual reduction step in cons_knapsack.c
• fasten check for common cliques in SCIPcliquelistsHaveCommonClique
• SCIP with CPLEX as LP solver now uses quickstart steepest edge pricing as default instead of steepest edge pricing
• avoid unnecessary domain propagation and LP resolve at nodes with infeasible LP relaxation
• improved zerohalf cut separator: more than one delta is tested for MIR cuts, better handling of dense base inequalities, faster scaling of fractional coefficients in rows (now enabled), improved parameter settings (presolving)
• LP solution:
  • in root node, first LP solution is checked for feasibility to avoid expensive setup
  • avoided restarting if LP solution is feasible
  • separators are not called any longer for an integral initial LP solution

Examples and applications

• New branch-and-price example which includes Ryan/Foster branching (binpacking example)
• New example illustrating the use of an event handler (example/Eventhdlr)

Interface changes

• Enhanced user interface for callable library: manual restarts, predefined settings and many other features
• Support of wbo format for weighted PBO problems, IBM's xml-solution format and pip format for polynomial mixed-integer programs
• Extended reader for Flatzinc models
• new API for 'expressions interpreter': code that evaluates expression trees, including first and second derivatives
• NLP solver interface (NLPI) now independent of SCIP like LPI
• SCIP can now maintain a central NLP relaxation of the problem (similar to LP)
• SCIP can now manage a list of external codes (e.g., LP or NLP solver, ZIMPL)
• lp.h/lp.c and the lpi's were changed according to the changes mentioned below.
• adding and deletion of rows to the separation storage and to the LP can now be catched by events (SCIP_EVENTTYPE_ROWADDEDSEPA, SCIP_EVENTTYPE_ROWDELETEDSEPA, SCIP_EVENTTYPE_ROWADDEDLP, SCIP_EVENTTYPE_ROWDELETEDLP)

New and changed callbacks

• new callback SCIP_DECL_BRANCHEXECRELAX(), together with new parameter in SCIPincludeBranchrule() for branching on a relaxation solution
• Copying a SCIP instance:
  • Constraint handlers have two new callback methods. One for copying the constraint handler plugins SCIP_DECL_CONSHDLRCOPY() and the other for copying a constraint itself, SCIP_DECL_CONSCOPY().
  • All plugins, like How to add branching rules branching rules and How to add primal heuristics primal heuristics, have a new callback method (see, e.g., type_branch.h and type_heur.h for more details):
    • SCIP_DECL_BRANCHCOPY(x), SCIP_DECL_HEURCOPY(x) etc.
    • When copying a SCIP instance, these methods are called to copy the plugins.
  • The main problem has a new callback method (see type_prob.h for more details) SCIP_DECL_PROBCOPY(x) when copying a SCIP instance, this method is called to copy the problem's data.
  • Variables have a new callback method (see type_var.h for more details) SCIP_DECL_VARCOPY(x) when copying a SCIP instance, this method is called to copy the variables' data.
• Restarts:
  • The callback SCIP_DECL_PROBEXITSOL(x) in the main problem has one new parameter (see type_prob.h for more details):
    • The parameter restart is TRUE if the callback method was triggered by a restart.

Deleted and changed API methods

• All C++ objects and constructors have a SCIP pointer, now.
• added parameter scip to ObjCloneable::clone()
• changes in a row can now be catched via row events (SCIPcatchRowEvent(), SCIPdropRowEvent(), SCIP_EVENTTYPE_ROWCOEFCHANGED, SCIP_EVENTTYPE_ROWCONSTCHANGED, SCIP_EVENTTYPE_ROWSIDECHANGED)
• added new parameter varcopy to SCIPcreateVar() to add the function for copying variable data
• in case of using SCIPwriteTransProblem() the currently (locally) valid problem is written this now also includes the local constraints
• Settings:
  • The predefined setting files like settings/cuts/off.set,aggressive.set,fast.set have been replaced by interface methods like SCIPsetHeuristics(), SCIPsetPresolving(), SCIPsetSeparating(), and SCIPsetEmphasis() in scip.h and by user dialogs in the interactive shell like SCIP> set {heuristics|presolving|separating} emphasis {aggressive|fast|off} or SCIP> set emphasis {counter|cpsolver|easycip|feasibility|hardlp|optimality}
  • All functions for setting user parameters of different types like SCIPparamSetBool(), SCIPparamSetChar(), SCIPparamSetInt(), SCIPparamSetLongint(), and SCIPparamSetString() in pub_paramset.h have a new parameter quiet it prevents any output during the assign to a new value.
• NLP:
  • NLPIs can now be used without generating a SCIP instance (i.e., do not require a SCIP pointer), code moved into src/nlpi
  • NLPIs can now be managed like other SCIP plugins, i.e., they can be included into the SCIP core and accessed by methods SCIPincludeNlpi(), SCIPfindNlpi(), SCIPgetNNlpis(), SCIPgetNlpis(), SCIPsetNlpiPriority()
• Intervalarithmetic:
  • method SCIPgetVarPseudocostCurrentRun() now returns the pseudocost value of one branching direction, scaled to a unit interval, old method now called SCIPgetVarPseudocostValCurrentRun()
  • renamed SCIPintervalScalarProductRealsIntervals()/SCIPintervalScalarProduct() by SCIPintervalScalprodScalars()/SCIPintervalScalprod() and redesigned them in intervalarith.c including new methods SCIPintervalScalprodScalarsInf/Sup()
• Branching:
  • The usage of strong branching changed. Now, SCIPstartStrongbranch() and SCIPendStrongbranch() must be called before and after strong branching, respectively.
  • The methods SCIPgetVarPseudocost() and SCIPgetVarPseudocostCurrentRun() in scip.h now return the pseudocost value of one branching direction, scaled to a unit interval. The former versions of SCIPgetVarPseudocost() and SCIPgetVarPseudocostCurrentRun() are now called SCIPgetVarPseudocostVal() and SCIPgetVarPseudocostValCurrentRun(), respectively.
  • The methods SCIPgetVarConflictScore() and SCIPgetVarConflictScoreCurrentRun() in scip.h are now called SCIPgetVarVSIDS() and SCIPgetVarVSIDSCurrentRun(), respectively.
  • The methods SCIPvarGetNInferences(), SCIPvarGetNInferencesCurrentRun(), SCIPvarGetNCutoffs(), and SCIPvarGetNCutoffsCurrentRun() are now called SCIPvarGetInferenceSum(), SCIPvarGetInferenceSumCurrentRun(), SCIPvarGetCutoffSum(), and SCIPvarGetCutoffSumCurrentRun(), respectively. Furthermore, they now return SCIP_Real instead of SCIP_Longint values.
  • The method SCIPgetVarStrongbranch() has been replaced by two methods SCIPgetVarStrongbranchFrac() and SCIPgetVarStrongbranchInt().
• Copying a SCIP instance:
  • Every new callback method resulted in a new parameter of the include function for the corresponding plugin, e.g., SCIPincludeBranchrule() has two new parameters SCIP_DECL_BRANCHCOPY((*branchcopy)) and SCIP_DECL_BRANCHEXECREL((*branchexecrel)). In the same fashion, the new callbacks SCIP_DECL_VARCOPY and SCIP_DECL_PROBCOPY led to new parameters in SCIPcreateVar() and SCIPcreateProb() in scip.c, respectively.
  • W.r.t. to copy and the C++ wrapper classes there are two new classes. These are ObjCloneable and ObjProbCloneable. The constraint handlers and variables pricers are derived from ObjProbCloneable and all other plugin are derived from ObjCloneable. Both classes implement the function iscloneable() which return whether a plugin is clone able or not. Besides that each class has a function named clone() which differ in their signature. See objcloneable.h, objprobcloneable.h, and the TSP example for more details.
  • SCIPincludeHeur() and SCIPincludeSepa() in scip.h, as well as scip::ObjSepa() and scip::ObjHeur(), have a new parameter: usessubscip: It can be used to inform SCIP that the heuristic/separator to be included uses a secondary SCIP instance.
  • The argument success in SCIP_DECL_CONSCOPY has been renamed to valid.
• Heuristics:
  • SCIPcutGenerationHeuristicCmir() in sepa_cmir.h has three new parameters:
    • maxmksetcoefs: If the mixed knapsack constraint obtained after aggregating LP rows contains more than maxmksetcoefs nonzero coefficients the generation of the c-MIR cut is aborted.
    • delta: It can be used to obtain the scaling factor which leads to the best c-MIR cut found within the cut generation heuristic. If a NULL pointer is passed, the corresponding c-MIR cut will already be added to SCIP by SCIPcutGenerationHeuristicCmir(). Otherwise, the user can generate the cut and add it to SCIP on demand afterwards.
    • deltavalid: In case, the user wants to know the best scaling factor, i.e., delta passed is not NULL, deltavalid will be TRUE if the stored scaling factor delta will lead to a violated c-MIR cut.

New API functions

• added SCIPcalcNegatedCliquePartition() to scip.c to calculate a clique partition on negations of all given binary variables
• SCIPpermuteArray() that randomly shuffles an array using the Fisher-Yates algorithm
• SCIPgetRandomSubset() that draws a random subset of disjoint elements from a given set of disjoint elements
• SCIPswapPointers()
• SCIPlpiGetSolverDesc() to get a descriptive string of an LP solver (developer, webpage, ...)
• SCIPholelistGetNext() to get the next hole of the hole list
• SCIPlpRecalculateObjSqrNorm() which is used when the old calculated square norm was unreliable
• SCIPpricerIsDelayed() which returns if the pricer is delayed (see pub_pricer.h)
• Variables:
  • SCIPvarIsBinary() which checks if a variable is (implicit) binary (see var.c for more details)
  • SCIPvarGetHolelistOriginal(), SCIPvarGetHolelistGlobal(), SCIPvarGetHolelistLocal() to get the original, global and local holes, respectively
  • SCIPvarGetProbvarHole() to tranform a given domain hole to the corresponding active, fixed, or multi-aggregated variable
• Restart:
  • allow user to trigger a restart during presolving SCIPrestartSolve()
  • SCIPrestartSolve() that allows the user to manually restart the solving process
  • SCIPisInRestart() to detect whether we are currently restarting
• Heuristics:
  • for heuristics SCIPheurSetFreq() to change the frequency of the heuristic (pub_heur.h, heur.c)
  • SCIPsepaUsesSubscip(), SCIPheurUsesSubscip()
• Intervalarithmetic:
  • SCIPeventGetHoleLeft() and SCIPeventGetHoleRight() for accessing the left right interval bound of a domain hole added or removed event
  • SCIPholelistGetLeft() and SCIPholelistGetRight()to get the left and right interval bounds of the open hole interval
  • SCIPintervalAddInf/Sup/Vectors(), SCIPintervalMulInf/Sup() in intervalarith.c
• Sorting:
  • added SCIPsortPtrPtrLongIntInt(), SCIPsortLongPtrPtrIntInt() and corresponding sorting/inserting/deleting methods in pub_misc.h and necessary defines in misc.c
  • added SCIPsortLongPtrInt() and corresponding sorting/inserting/deleting methods in pub_misc.h and necessary defines in misc.c
  • added SCIPsortPtrPtrInt() (and various other) and corresponding sorting/inserting/deleting methods in pub_misc.h and necessary defines in misc.c
  • SCIPsortPtrBool() and corresponding sorting/inserting/deleting methods in pub_misc.h and necessary defines in misc.c
• Constraint Handlers:
  • SCIPconshdlrGetEnfoConss(), SCIPconshdlrGetNEnfoConss()
  • can now forbid upgrading of individual linear constraints (SCIPmarkDoNotUpgradeConsLinear())
  • SCIPpermuteProb() that randomly permutes constraints and variables
  • SCIPgetResultantOr() which returns the resultant of an or constraint
  • SCIPmarkDoNotUpgradeConsLinear() in cons_linear.?, which allows to forbid upgrading of linear constraints
  • SCIPgetNUpgrConss() which returns the number of upgraded constraints
  • SCIPconshdlrGetCheckTime() and SCIPconshdlrGetNCheckCalls() which returns the running time in the feasibility checking of the corresponding constraint handler respectively the number of calls of the checking method (implemented in cons.c)
• Copy:
  • SCIPcopy() to clone a SCIP instance
  • SCIPcopyPlugins(), SCIPcopyParamSettings(), SCIPcopyVars(), SCIPcopyConss(), SCIPgetVarCopy() to copy individual parts of a SCIP instance separately.
  • SCIPcopyProbData() and SCIPprobCopyProbData() which copies the probdata from a sourcescip to a targetscip
• Branching:
  • two new functions SCIPgetVarsStrongbranchesFrac()/SCIPgetVarsStrongbranchesInt() for computing strong branching information for several variables
  • SCIPbranchruleGetNRelaxCalls() to get the total number of times, a particular branching rule was called on a relaxation solutions
  • SCIPbranchRelax() to branch on a relaxation solution
  • SCIPbranchVarVal() to branch on an arbitrary value within the variable's bounds
  • SCIPbranchGetBranchingPoint() and SCIPgetBranchingPoint() to select branching point for a variable, e.g., ensure branching point is inside the interval for a continuous variable
  • SCIPexecRelpscostBranching() in branch_relpscost.{c,h}; this method allows of calling the reliability pseudo cost branching algorithm for given set of branching candidates from the outside
  • SCIPinitVarBranchStats() to initialize the branching statistics (such as pseudo costs, VSIDS, inference values) of a variable
  • SCIPselectBranchVarPscost() in branch_pscost.{c,h}; this method selects from a given candidate array a branching variable w.r.t. pseudo cost branching for relax candidates
• Reading, Writing and Parsing:
  • SCIPparseVarName() which parses a string in cip-format as a variable name
  • SCIPparseVarList() which parses a string as a variable list in cip-format
  • the Flatzinc reader can now handle the output annotations of the Flatzinc format; the method SCIPprintSolReaderFzn() outputs the given solution in Flatzinc format w.r.t. the output annotations
  • SCIPprintSolReaderFzn() which prints the best solution in Flatzinc format w.r.t. to the output annotations in the input file of the flatzinc model
  • SCIPwriteVarName() which writes a variable in cip-format to given stream
  • SCIPwriteVarsList() which writes an array of variables in cip-Format to given stream
  • SCIPwriteVarsLinearsum() which writes an array of variables and coefficients as linear sum in cip-Format to given stream
• Copying a SCIP instance:
  • SCIPapplyRens() in heur_rens.h has a new parameter uselprows. It can be used to switch from LP rows to SCIP constraints as basis of the sub-SCIP constructed in the RENS heuristic.
• Parameters:
  • SCIPsetParamsCountsols() which sets the parameter for a valid counting process
  • SCIPsetEmphasis() which sets parameter to detect feasibility fast, handle hard LP, solves easy CIPs fast, behaves like a CP solver, set parameter for a valid counting process; the desired behavior is triggered via a parameter of the function
  • SCIPresetParam() to reset the value of a single parameter to its default value
• Settings:
  • added SCIPsortRealRealRealPtr() and corresponding sorting/inserting/deleting methods in pub_misc.h and necessary defines in misc.c as basis for the subSCIP, setting ist to TRUE (uses LP rows) will lead to same version as before
  • SCIPsetHeuristics(), SCIPsetSeparating(), SCIPsetPresolving() which set the heuristics to aggressive, fast, off, or default settings, depending on the SCIP_PARAMSET parameter
  • SCIPsetSubscipsOff() which disables all plugins that uses subscips
  • SCIPsepaSetFreq() to set the calling frequency of a separator

Command line interface

• added new dialog for setting the SCIP parameters for hardlp, optimality, easy CIP, CP like search
• added new dialog for setting the SCIP parameters for feasibility problems SCIP> set emphasis feasibility
• added new dialog for setting the SCIP parameters for counting SCIP> set emphasis counting
• added new dialog for setting presolving to aggressive, fast, or off in interactive shell
• added new dialog for setting separation to aggressive, fast, or off in interactive shell
• added new dialog for writing all solutions which are collected during the counting process (see cons_countsols.{c,h})
• added new dialog for setting heuristics to aggressive, fast, or off in interactive shell
• added new dialog display pricers which displays all included pricers

Interfaces to external software

• added interface to CppAD (nlpi/exprinterpret_cppad.cpp)
• Improved Xpress, CPLEX, SoPlex interfaces
• the SoPlex interface now includes equilibrium scaling on lp's solved from scratch without starting basis
• the SoPlex interface can now double check each SoPlex result against CPLEX (lpi_spx.cpp)
• the SoPlex interface has the option to restore basis only after entire strong branching phase instead of after each strong branch (off, because it mostly appears to increase strong branching time and iterations) (lpi_spx.cpp)

Changed parameters

• removed parameter constraints/knapsack/maxnumcardlift and adapted setting files
• changed parameter lp/fastmip from boolean to integer, possible values are 0 (off), 1 (medium, default), 2 (full, must not be used with branch-and-price).

New parameters

• branching/clamp to set the minimal fractional distance of a branching point to a continuous variable' bounds
• branching/random/seed to change the initial seed value of the branching rule random
• constraints/indicator/addCouplingCons that allows to add variable upper bounds if addCoupling is true
• constraints/indicator/enforceCuts that allows to check for violated cust in enforcement
• constraints/indicator/maxCouplingValue for the maximal value of the coefficient in a coupling inequality/constraint
• constraints/indicator/noLinconsCon which controls whether the linear constraint is not explicitly added to the problem. default is FALSE
• constraints/knapsack/dualpresolving to switch dualpresolving on/off inside the knapsack constraint handler, default is TRUE
• constraints/knapsack/presolpairwise that allows pairwise presolving of knapsack constraints, default is TRUE
• constraints/knapsack/presolusehashing that allows fast pairwise presolving of knapsack constraints, default is TRUE
• heuristics/crossover/dontwaitatroot that allows to call crossover at root node independently from nwaitingnodes
• heuristics/rens/uselprows that allows to switch between LP row and SCIP constraints as basis for the subSCIP, default is TRUE (uses LP rows)
• lp/rowrepswitch telling simplex solver to switch to row representation of the basis (if possible), if number of rows divided by number of columns exceeds this value (default value infinity, i.e. never switch)
• lp/threads to change the number of threads used to solve the LP relaxation (default is 0: automatic)
• misc/lexdualstalling that turns on the lex dual algorithm if the separation process is stalling
• misc/usevartable and misc/useconstable which turns on/off the usage of hashtables mapping from variable/constraint names to the variables/constraints; when turned off, SCIPfindVar() and SCIPfindCons() may not be used; the hashtables can be turned off for subMIPs to improve the performance, default value TRUE
• misc/usesmalltables which results in using smaller tables for names, cliques and cuts and improves the performace for smaller instances, default value FALSE
• misc/permutationseed to change the permutation seed value for permuting the problem after the problem is transformed (-1 means no permutation)
• reading/zplreader/usestartsol which allows to switch ZIMPL start solutions off, default value TRUE
• vbc/dispsols to propose if the nodes where solutions are found should be visualized in the branch and bound tree

Data structures

• implemented the data structure and events for global and local domain holes added and removed
• new data structures and methods to handle nonlinear expressions in NLPI ({type_, struct_, pub_}expression.{h,c}): nlpioracle can store and evaluate general NLPs now, nlpi_ipopt can solve general NLPs now

Testing

• minor changes on several evaluation scripts (new statuses: better, solved, sollimit, gaplimit) and short-mode for cmpres.awk
• support for FreeBSD (32- and 64-bit) including minor changes in several scripts in the check-directory

Build system

Makefile

• added scripts check_*.sh, evalcheck_*.sh and check_*.awk for blis, glkp, gurobi and symphony (including targets in Makefile) and slightly modified scripts for cplex, cbc and mosek and cmpres-script
• added target lintfiles which allows to call flexelint with a list of file, for example, make lintfiles FILES=src/scip/prop_vbounds.c
• the NLP solver interfaces and expression interpreter are located in a separate library (libnlpi.*; similar to the lpi library) and is required to link against the SCIP library also projects that use SCIP via make/make.project need to change their Makefile (!!!): in the target, add behind in the dependencies and add to the linker flags
• The additional NLPI library requires a change in the Makefile of SCIP's project: The target now has as additional dependency and the linking command requires as additional argument.
• A bug in the Makefiles of older versions of the SCIP examples may cause data loss. If you have a custom Makefile, please ensure that the target clean is changed as described here: http://scip.zib.de/download/bugfixes/scip-1.2.0/make.txt.

Fixed bugs

• fixed bug in conflict.c in the method conflictsetAddBound()
• fixed bug in projects Makefiles w.r.t. make clean
• fixed bug in rapid learning with wrong ordering of dual and primal bound update, primal bound is now updated inside rapid learning
• fixed potential bug in rapid learning with dual reductions
• fixed potential bug where SCIPselectSimpleValue() returns a value slightly outside of the given bounds due to rounding errors (probably cancelation in subtraction in SCIPfindSimpleRational), now use rounding control and check result
• fixed bug that SCIP could not be continued after it has been stopped due to a limit
• fixed bug in var.c: SCIPvarChgLbOriginal() and SCIPvarChgUbOriginal() cannot access original bounds if the variable is negated
• fixed potential bug with pseudo solution branching on free variables
• fixed bug with multiaggregations whose infimum and supremum are both infinite: in such a case multiaggregation is now forbidden
• fixed numerical issue with multiaggregations which are infinite in one direction: value of multiaggregated variable could have been larger then inifinity
• fixed bug w.r.t. of adding a variable bound variable to its self
• fixed bug concering the incorrect assumption that every solution computed in SCIPlpGetUnboundedSol() is integral (we will not branch but return infeasible or unbounded like in presolving)
• fixed bug while breaking an clique down to their impications (in SCIPcliquetableCleanup() in implics.c) where the variable was not of vartype SCIP_VARTYPE_BINARY, instead of adding an implication we add a variable bound
• fixed bug with debugging a solution: during restarts erroneously it was claimed that the primal solution is cut off
• Interface:
  • fixed bug w.r.t. ObjDialog and displaying the description of the dialog
  • fixed bug when aborting pricing with Ctrl-C
• LP:
  • fixed bug in scip.c w.r.t. to call of conflict analysis for LPs which reached the objective limit in case of diving
  • fixed bug with resolving LPs at infeasible root node
  • fixed bug in lp.c: in sumMIRRow() rowtoolong was not set correctly
  • fixed bug in lp.c w.r.t. objective limit reached and the chosen comparison (fixed buglist entry 40)
  • fixed bug in lp.c: if in SCIPlpSolveAndEval() the LP has to be solved from scratch due to numerical troubles, reset SCIP_LPPARAM_FROMSCRATCH to FALSE afterwards
  • fixed bug in lp.c SCIProwGetObjParallelism() due to a wrong parallelism value which arised from cancellations during calculation of squared euclidean norm of objective function vector of column variables
  • fixed bug in lp.c: SCIPlpGetUnboundedSol() did not ensure that unbounded solution lies withing the bounds of the variables
  • fixed bug in lp.c w.r.t. to the number of active pricer
• Solve:
  • fixed bug in solve.c where relaxation branching candidates were cleared, but the relaxation was still marked solved and not called again, furthermore, adjusted criterions for solving a relaxation again
  • fixed bugs in solve.c: even with LP solving disabled, the root LP was solved in case continous variables are contained; setting pricing/maxvars(root) to 1 resulted in not calling the pricers
  • fixed bug in solve.c: make sure SCIP terminates correctly also when a user interrupt or gap limit is reached, i.e., avoid error pricing was aborted, but no branching could be created!
• Tree:
  • fixed bug in tree.c: if an explicit branching point is given, we may not recompute a better centering point
  • fixed bug in tree.c: propagate implications on multi-aggregated should not be performed
• Constraints:
  • corrected several asserts in linear and quadratic constraint handler concerning parsing of CIP format
  • fixed bug while deleting redundant variables, which have no influence on changing the feasibility of the linear constraints, we need to update the sides of the constraint at each step, bug number 51 in bugzilla
  • fixed bug in copy procedure of AND constraint handler, negated variables have been copied to their originals
  • fixed bug when deleting a constraint where the update was delayed and not processed yet (in cons.c)
  • fixed bug in cons_linear.c: binary variables should not be multi-aggregated
  • fixed bug in cons_quadratic.c: curvature of bivariate quadratic constraints was not detected correctly
  • fixed bug in cons_sos2.c: the branching position was sometimes mistakenly increased
  • fixed bug in propagation of cons_sos2.c: the node can be cut off at more places: the previous version was not sucessfull in this respect
  • fixed bug in cons_linear.c:applyFixings() which could lead to lhs/rhs smaller/larger than -/+infinity
  • fixed bug in cons_linear.c in detectRedundantConstraints() and corrected old bug fix in SCIProwCreate(): we want lhs <= rhs to be satisfied without numerical tolerances in order to avoid numerical problems in the LP solver
• Knapsack Constraint Handler:
  • fixed bug in cons_knapsack.c: mergeMultiples() now detects whether a node can be cut off
  • fixed bug in cons_knapsack.c w.r.t. to items with zero weight
  • fixed bug in cons_knapsack.c: In SCIPseparateRelaxedKnapsack() not all variables need to be active in deeper regions of the tree
  • fixed bug in cons_knapsack.c and sepa_clique.c: the assumption that implications are always nonredundant and contain only active variables is not correct anymore as the corresponing vbound might be missing because of numerics
• Separation and Cuts:
  • fixed bug in cutpool.c: the hashkey computation was not constant over time
  • fixed bug in cutpool.c: hashkey of a row changed during the solving process (if a row is made integral after creation, maxabsval can be invalid when adding it to the pool, but might be recomputed later on)
  • fixed bug in sepa_rapidlearning.c, stop processing if there are no binary variables left
  • fixed bug in sepa_rapidlearning.c, corrected computation of right dualbound
  • fixed bugs in sepa_zerohalf.c, e.g., handling of intscaling and substitution of variable bounds
  • fixed bug in sepastore.c in sepastoreApplyLb/Ub being to hard on feasibility decisions
  • fixed bug in sepa_flowcover.c: numerical issues while computing candidate set for lambda
• LP Interfaces:
  • fixed bug in SoPlex autopricing due to which autopricing had behaved like steepest edge pricing so far
  • fixed bug in lpi_clp.cpp: SCIPlpiChgBounds() checks if the column status exists in Clp before using it
  • fixed wrong assert in Cplex LPI: Due to numerical inaccuracies, a few pivots might be performed after refactorization
  • fixed bug concerning assert(!SCIPlpDivingObjChanged(lp)) which was caused by wrong infinity double parameters for cplex
  • fixed makefile system for OSTYPE=darwin w.r.t. to CPLEX as LP solver
• Presolving:
  • fixed bug in cons_setppc: aggregated variables were not correctly removed in presolving
  • fixed bug in presolving of linear constraint handler: in redundancy detection, two different numerical epsilons were used
  • fixed bug in presolving while not applying a bound change on a variable in a single-variable constraint (e.g. x1 = 0.03) in cons_linear which is too small, that lead to another bound change in presol_trivial which is not allowed, so now this bound change will be forced
  • fixed SCIPvarIsTransformedOrigvar() in var.c (variables generated by presol_inttobinary returned false)
  • fixed bug w.r.t. an assert in presol_inttobinary.c; it was assumed that the aggregation which is performed there will never lead to an infeasibility, this is not true, see comment in presol_inttobinary.c
  • fixed bug in presol_trivial.c trying to fix continuous variables, now uses a less stricter comparison to fix variables
  • fixed bug in cons_bounddisjunction.c: presolve may have tried to tighten bounds on a multiaggregated variable (now upgrades to linear constraint)
• Reading, Writing and Messages:
  • fixed bug while trying to write a MIP where SCIP needs to flush the lp changes first
  • fixed potential resource leak when running out of memory while writing files
  • fixed bug in reader_zpl.c which appeared using the parameter reading/zplreader/parameters
  • fixed bugs in flatzinc readers with constraints that exclusively consist of constants
  • fixed bug in reader_gms: correct handling of nonstandard bounds on general integer variables
  • fixed buglist entry 35, which was caused by a wrong read in correction when the reading buffer was full in reader_opb.c
  • fixed bugs in reader_fzn.c w.r.t. parsing and solution output in Flatzinc format
  • fixed bug in reader_fzn.c w.r.t. comment lines
  • fixed bug in reader_opb.c w.r.t. comment lines
  • fixed bug in message handler w.r.t. to messages which are longer then SCIP_MAXSTRLEN
• Heuristics:
  • fixed bugs do to HEUR_TIMING SCIP_HEURTIMING_AFTERPROPLOOP which appeared during repropagation
  • fixed bug in trivial heuristic: the locking solution might have falsely initialized some values to zero
  • fixed bug in heur_oneopt.c w.r.t. to SCIPtrySol(); it is necessary that the bound of the solution is check otherwise, infeasible solution could be accepted as feasible
  • fixed bug in heur_trivial.c w.r.t. to debug messages after a solution was freed
  • fixed bug for HEUR_TIMING SCIP_HEURTIMING_BEFOREPRESOL and modifiable constraints
  • corrected wrong assert in DINS heuristic when called for an empty problem
  • fixed potential bug in OCTANE heuristic with nonbasic solutions
  • fixed bug in sub-MIP heuristics with parameter change if some default plugins are not included
  • fixed bug in trivial heuristic with bounds that are greater than the heuristic's infinity value

Miscellaneous

• As the interface contains several additional callback functions and parameters for plugins, some effort may be required to compile your own projects with SCIP 2.0. See also Changes between version 1.2 and 2.0 in the doxygen documentation for additional information.