CHANGELOG

SCIP version 4.0.0 ================== features: - new Graph induced neighborhood search (GINS) primal heuristic that uses neighborhoods based on distances in the variable constraint connectivity graph. In addition, the heuristic supports a rolling horizon-like procedure to solve auxiliary problems for neighborhoods with increasing distance from the starting neighborhood. - new primal heuristic LP face that tries to find an integer solution inside the optimal LP face. - implemented linear time methods for (weighted) median selection for joint arrays of various types - new statistic computed: "Root LP Estimate" that shows the root LP best-estimate with every pseudo-cost update - new SCIP_REGRESSION data structure in pub_misc.h to incrementally compute a best-fit line through pairs of observations - added leaf statistics about LP objective limit|feasible|infeasible leaves to the statistics output and to the callable library: SCIPgetNObjlimLeaves(), SCIPgetNFeasibleLeaves(), SCIPgetNInfeasibleLeaves() - added adaptive solving behavior of SCIP based on solving phases and heuristic transitions, if enabled via "solvingphases/enabled" - new presolving step for variables contained in a single quadratic constraint with proper square coefficients - can now solve relaxations within probing - will now enforce relaxation solution instead of lp or pseudosolution if lowerbound is better and the whole lp is included in the relaxation - in case of multiple relaxators the best solution is saved instead of the last one - can now separate perspective cuts for indicator constraints - added write callback for reader_bnd - added possibility to use a reference value for advanced analysis of the tree search. If a finite reference value (an objective value in original objective space) is passed via misc/referencevalue, SCIP keeps track of the number of nodes exceeding the reference value and the number of early backtracks -- path switches in the tree when a child node with lower bound smaller than the reference value was available. - add new presolving step to disaggregate second order cone constraints - added reading capabilities for partial solutions with extension *.mst - new heuristic that tries to complete partial solutions - new global shift off all random seeds (randomization/randomseedshift) and unification of all existing random seeds - use new macros SCIPdebugMsg/SCIPsetDebugMsg/SCIPstatDebugMsg at all places where it makes sense - new feature solution polishing to improve integrality of LP solutions - new random number generator in pub_misc.h - the subnlp heuristic now gives ownership of a found solution to the heuristic that constructed the starting point, if any; as a consequence, MIP heuristics may now be shown more frequently for having found a solution when solving MINLPs, even though the solutions required an additional NLP solve - add check whether variables have been released when freeing SCIP - new constraint handler for cardinality constraints - implement a storage for conflicts to have more control over active conflicts - can now analyze dual unbounded rays of primal infeasible LPs - a print callback can now be specified for user expressions - added interval-evaluation of sine and cosine - add prop_nlobbt, a nonlinear optimization-based bound propagator solving two convex NLP relaxations for each variable - add sepa_convexproj, a separator which projects onto convex relaxation and build gradient cuts at the projection - add sepa_gauge, a separator which computes an interior point of a convex relaxation and performs a binary search in the segment joining the interior point and the point to separate until it finds a point in the boundary of the feasible region where to build a gradient cut - new presolving method presol_qpkktref to add the KKT conditions of a QP - implemented and extended stuffing presolving in linear constraint handler - allow to create constraints of constraint handlers that don't need constraints - nodes can now be postponed; currently, this can only be triggered by BEFORELP propagation callbacks - new components constraint handler which replaces the components presolver; it searches for independent subproblems and solves small ones as sub-SCIPs during presolve, larger ones are solved alternatingly during the main solving process - new presolving timing FINAL: presolving methods with this timing are only called once after all other presolvers with timings FAST, MEDIUM, and EXHAUSTIVE are finished; during this timing only reductions are allowed that are self-contained, e.g., fixing all variables and deleting all constraints of an independent component; note that reductions found in this timing do not trigger a new presolving round - added method SCIPcheckCopyLimits() which can be used to check that enough time and memory is left to run a sub-SCIP after subtracting time and memory used by the main-SCIP, and SCIPcopyLimits() which copies these limits accordingly and disables all other limits (need to be set by the plugin, if needed) - changed handling of coupling constraints in cons_indicator; the cuts will not be added to the pool, but are separated by default - for users of the ampl interface, the display/logfile option has been added to set the name of a file to write the SCIP log to (additionally to stdout) - next to the number of found solution, also the number of new best solutions is now printed for each heuristic (and relaxation solutions) in the statistics in the "Primal Heuristic" section. - concurrent solving mode that allows to run multiple SCIP instances, that share solutions and global variable bounds, in parallel parameters: - new parameter "branching/sumadjustweight" to adjust branching scores by adding a sum epsilon in order to keep score differences near zero, which are otherwise completely disregarded (they are adjusted to at least sum epsilon) - new parameter "solvingphases/enabled" to activate adaptive behavior during the solution process; several further parameters in the solvingphases-section to control how to switch the parameters, and whether a restart should be performed between the phases. - new parameter "misc/referencevalue" to pass a reference value for further analysis of the tree search, see also in 'features' - new parameter "constraints/indicator/sepaperspective" to turn on separation of perspective cuts for indicator constraints - new parameter "constraints/indicator/sepapersplocal" to decide whether local cuts can be used for perspective cuts for indicator constraints - new parameter "branching/relpscost/usesmallweightsitlim" to use smaller weights for pseudo cost updates when LP iteration limit was hit - new parameter class randomization - new parameter "randomization/lpseed" to set the initial seed of the LP solver - parameters "misc/permutationseed", "misc/permuteconss", and "misc/permutevars" changed to "randomization/permutationseed", "randomization/permuteconss", and "randomization/permutevars" - setting a value for a fixed parameter will no longer return with an error, if the new value equals the one to which the parameter is fixed - new parameter "lp/solutionpolishing" to enable LP polishing only at the root LP or always - new parameter "constraints/cardinality/branchbalanced" to decide whether to use a balanced branching scheme in the enforcing of cardinality constraints - new parameter "constraints/cardinality/balanceddepth" to set the maximal depth until balanced branching is turned off - new parameter "constraints/cardinality/balancedcutoff" to determine that balanced branching is only used if the branching cut off value w.r.t. the current LP solution is greater than a given value - new parameter "constraints/quadratic/projectedcuts" to enable convex quadratics to generate gradients cuts at the projection of the point onto the region described by the constraint, which is supporting - parameters "conflict/useinflp" and "conflict/useboundlp" are now of type char (before bool) - add maximum branch-and-bound tree depth constant SCIP_MAXTREEDEPTH (replaces SCIPgetDepthLimit and SCIPtreeGetDepthLimit) constraint handler (starting with "constraints/components/") - new parameter "presolving/qpkktref/updatequadbounded" to add the KKT conditions to QPs only if all variables are bounded - new parameter "presolving/qpkktref/updatequadindef" to add the KKT conditions to QPs only if the quadratic matrix is indefinite - new parameter "presolving/qpkktref/addkktbinary" to allow the presence of binary variables for the KKT update - several new parameters "concurrent/*" and "parallel/*" for configuring the concurrent solving mode performance improvements: - use connectedness information of the clique table to speed up the clique partitioning algorithm - rewrote the propagate-and-cut-and-price loop so that successful propagations with DURINGLPLOOP timing, bound changes found by separation, and new primal solutions now trigger a new round of node solving, starting with propagation; improved tuning of propagation and heuristic timings - tuned propagation methods of several constraint handlers - make more use of SCIPmarkConsPropagate() to mark constraints for propagation and improved the internal handling of marked constraints - knapsack approximation algorithms use linear-time weighted median selection instead of sorting - improved greedy solution in SCIPsolveKnapsackApproximatelyLT() for the flow cover separation - adjusted most Large Neighborhood Search heuristics such that they collect their variable fixings first in an array, and only create and populate a sub-SCIP if enough variables will be fixed. - SCIP supports constraint compression for problem copies; constraint compression denotes the immediate removal of fixed variables from constraint data at creation time to reduce memory requirements. - changed value of parameter separating/clique/cliquedensity to 0.0 such that the separator always constructs a dense clique table which proved to be faster on the benchmarks MMM and stableset. - reduce performance variability by using a small perturbation in the undercover heuristic - reduce performance variability by using random numbers as tie-breaker for external branching candidates - 1-opt heuristic can now be repeatedly executed as long as new incumbents are found - improve propagation of absolute-value expression in the case that the sign of the argument is fixed interface: - separated header pub_misc.h from repeated methods for sorting and (weighted) median selection; those are also available in separate headers pub_misc_sort.h and pub_misc_select.h, but included into pub_misc.h - new library methods SCIPenableConsCompression(), SCIPisConsCompressionEnabled(), SCIPcopyConsCompression(), SCIPcopyOrigConsCompression() - new method SCIPcopyLargeNeighborhoodSearch() in heuristics.h that supports compressed copying and two kinds of problem copy: the MIP-relaxation or a 1-1 problem copy (by copying the constraints, and not the LP relaxation) - new files heuristics.c/heuristics.h to collect methods that are frequently used by heuristics - merged dive.c/pub_dive.h with heuristics.c/heuristics.h, removed dive.c/pub_dive.h - new library methods SCIPcopyConsCompression(), SCIPcopyOrigConsCompression() that accept an array of variables that are immediately fixed in the copy. Alternatively, local instead of global bounds can be used for compression. - spx2 is the new default LP solver interface - new function SCIPsolveProbingRelax() to solve a relaxation within probing - new optional callback CONSENFORELAX for enforcement of relaxation solutions - new parameter "includeslp" for SCIPincludeRelax() and SCIPincludeRelaxBasic() to indicate whether relaxation includes all linear rows and can be enforced - new function SCIPgetIntVarXor() to access integer variable of XOR constraints - new function SCIPgetLastStrongbranchingLPSolstat() to query the LP statuses after strong branching on a variable - CONSINITLP callback now has a new parameter 'infeasible', which is a pointer to store whether infeasibility was detected while building the initial LP relaxation - new function SCIPisDualSolAvailable() to query the dual solution availability - new method SCIPinitializeRandomSeed() - new methods SCIPprintDebugMessage(), SCIPsetPrintDebugMessage(), SCIPstatPrintDebugMessage() that output debug messages and also print the subscip depth; the first two output via the message handler; also added macros SCIPdebugMsg(), SCIPsetDebugMsg(), SCIPstatDebugMsg() - new functions SCIPdebugMsgPrint()/SCIPsetDebugMsgPrint() that output a message without "[debug]" prefix via the message handler (compare SCIPdebugPrinf()) - add new parameter to SCIPtrySolFree, SCIPtryCurrentSol, and SCIPcheckSol to check all constraints when printing violations - methods SCIPrandomGet{Int,Real}() substitutes SCIPgetRandom{Int,Real}() (marked to be deprecated) - methods SCIPrandomPermute{Int}Array() substitutes SCIPpermuteRandom{Int}Array() (marked to be deprecated) - method SCIPrandomGetSubset() substitutes SCIPgetRandomSubset() (marked to be deprecated) - new method SCIPlpiSetIntegralityInformation() to improve SoPlex' solution polishing - SCIPapplyHeurSubNlp() can now return the solution found by the sub-NLP heuristic - new function SCIPcreateConsCardinality() to create a cardinality constraint - new function SCIPcreateConsBasicCardinality() to create a basic cardinality constraint - new function SCIPchgCardvalCardinality() to changes cardinality value of cardinality constraint (i.e., right hand side of cardinality constraint) - new function SCIPaddVarCardinality() to add a variable to a cardinality constraint - new function SCIPappendVarCardinality() to append a variable to a cardinality constraint - new function SCIPgetNVarsCardinality() to get the number of variables in a cardinality constraint - new function SCIPgetVarsCardinality() to get the array of variables in a cardinality constraint - new function SCIPgetCardvalCardinality() to get the cardinality value of a cardinality constraint (i.e., right hand side of cardinality constraint) - new function SCIPgetWeightsCardinality() to get the array of weights of a cardinality constraint - SCIPinitConflictAnalysis() gets now 2 additional values: the type of the conflict and whether the current cutoff bound is used or not - bound reader uses angle bracket around variable names - new functions SCIPgetLinvarMay{Decrease,Increase}Quadratic() to get index of a variable in linear term of quadratic constraint that may be decreased without making any other constraint infeasible - in param.c/h: rename SCIPparamCheckBool() to SCIPparamIsValidBool(), SCIPparamCheckString() to SCIPparamIsValidString(), SCIPparamCheckChar() to SCIPparamIsValidChar(), SCIPparamCheckLongint() to SCIPparamIsValidLongint(); the new methods return a bool whether the given value is valid for the parameter instead of printing a warning message and returning an error code if the value is invalid - add SCIPparamIsValidInt() and SCIPparamIsValidReal() to param.c/h - in scip.c/h: rename SCIPcheckBoolParam() to SCIPisBoolParamValid(), SCIPcheckLongintParam() to SCIPisLongintParamValid(), SCIPcheckCharParam() to SCIPisCharParamValid(), SCIPcheckStringParam() to SCIPisStringParamValid(); the new methods return a bool indicating whether the given value is valid for the parameter instead of printing a warning message and returning an error code if the value is invalid - add missing functions SCIPisIntParamValid() and SCIPisRealParamValid() to scip.c/h - setting a parameter to a non-valid value now produces an error message instead of a warning - add SCIPcreateNlpiProb(), SCIPupdateNlpiProb(), and SCIPaddNlpiProbRows() to create and update a nonlinear relaxation - the parameters of SCIPlpiChgObj(), SCIPlpiSetBase(), SCIPlpiSetState(), SCIPlpiSetNorms() have been declared as const - removed SCIPvarGetLbAtIndex() and added SCIPgetVarLbAtIndex() - removed SCIPvarGetUbAtIndex() and added SCIPgetVarUbAtIndex() - removed SCIPVarGetBdAtIndex() and added SCIPgetVarBdAtIndex() - removed SCIPvarWasFixedAtIndex() and added SCIPgetVarWasFixedAtIndex() - new function SCIPswapReals() to swap two real values - new command line parameter -v to print detailed build options - the CPLEX LPI now also compiles with CPLEX 12.7.0.0 - major update ot the Gurobi LPI, which supports ranged rows now and several performance improvements, but only works with Gurobi version >= 7.0.2 - rename method SCIPgetReopSolsRun() to SCIPgetReoptSolsRun() - new macro SCIP_CALL_FINALLY to conveniently free ressources after an error return code. - SCIPcreateNlRow() gets an additional argument "curvature" - changed type of argument "timingmask" from unsigned int to SCIP_HEURTIMING in SCIPincludeHeur(), SCIPincludeHeurBasic() - added argument "initialseed" to SCIPcreateDiveset() - new function SCIPgetNNZs() to get the number of active non-zeros in the transformed/presolved problem - added functions for concurrent solving mode (see concurrent.h, concsolver.h) fixed bugs: - correct handling of implicit integer variables with fractional solution value in simplerounding heuristic - avoid numerically troublesome aggregations - fixed bug in event system: bound change events of the new focus node must be processed, even if the bound is the same as at the last focus node - fixed memory bug in SCIP_DIGRAPH - fixed bug while changing the objective value of an original value after transforming the problem - fixed bug with sorting of propagators in presolving: the order can be changed by calling probing; thus, there is a copy of the propagators, which is sorted by presolving priority - avoid numerically unstable (multi-)aggregations - added missing capturing and releasing mechanism in genvbounds propagator - improved counting of memory consumption by using more block memory and counting all allocated memory - fixed bug in XML reader concerning comments - fixed wrong representation of SOC constraints in NLP - fixed possible segmentation fault in genvbounds propagator - fixed bug with solutions from previous runs not satisfying an objective limit - the AMPL interface now writes a solve status (solve_result_num) into the .sol file - fix wrong propagation of product expressions - fix memory leaks in TSP example - return SCIP_ERROR when a memory exception is caught in SoPlex (was SCIP_LPERROR) - in the cmpres.awk (allcmpres.sh) output, the counts in the time column are now with respect to the whole set of processed instances (as with fail and solv), while before it was with respect to the set of instances where no solver failed (eval set); thus, now proc = fail + time + solv. - fixed memory leak in OSiL reader - writing of solutions or parameters to a file now works also with the message handler set to quiet - fixed bug in heur_octane with uninitialized ray direction - fixed a few issues within redundant constraint detection of (specialized) linear constraint handlers - SCIPisObjIntegral() now works correctly in SCIP_STAGE_PROBLEM - ignore lower and upper bound tightenigs beyond +/-infinity during solving - fix wrong NLP representation of logic-or constraints in the dual value heuristic - time limit of SCIP-infinity is converted to LPI-infinity when setting it - fix LP activity of a row that has been modified - fixed issue in reader_opb concerning writing of fixed variables contained in no constraints - fixed two bugs in heur_indicator: use improvesols parameter now and update pointer to indicator constraint handler misc: - dropped support for Ipopt < 3.11 - updated CppAD to 20160000 makefile: - Building with SHARED=true automatically generates the combined library libscipsolver.so for easier linking - All objective files are now placed in obj/static or obj/shared, depending on SHARED=false or SHARED=true, respectively. - All internal and external libraries are placed in lib/static and lib/shared, the include files are in lib/include. - External projects (including make.project) can use the makefile variable LINKCXXSCIPALL or LINKCCSCIPALL to link all SCIP libraries. - Running "make help" lists all makefile options. - All makefiles in examples/ and applications/ have been updated. - The binaries now contain an rpath to the SCIP directory, such that shared libraries are found. - make.project defines a variable SCIP_VERSION containing the SCIP version number - revise sub-makefiles for MSVC on MinGW - new target "dll" to build Windows dlls with MSVC - make shared libraries aware of their dependencies - link binary to shared libs when compiling with SHARED=true - 'make install' copies now all header files - sub-makefile for CrayXC systems added - rename `dll` target to `windowslib` SCIP version 3.2.1 ================== features: - new interactive shell command "write history" to write the command line history (only when compiled with Readline) - several improvements of SCIP-Jack (STP application): extended presolving for STP variants, STP-specific branching rule, dual heuristic to generate initial LP relaxation SCIP-Jack is now competitive with problem specific state-of-the-art solvers on several well-known STP variants, e.g., the (rooted) prize-collecting Steiner tree problem. - MultiObjective application renamed to PolySCIP; several improvements: better command line argument processing, overhaul of much of the source code, installation via CMake - extended python interface supporting callbacks and linear and quadratic expressions parameters: - new parameter misc/transsolorig for transfering transformed solutions to the original space (default: true) - new "force" parameter in (root)redcost propagator to run the propagator also with active pricers - new parameter propagating/rootredcost/onlybinary to propagate root reduced costs of binary variables only - new parameter constraints/sos1/perfimplanalysis to perform an implication graph analysis to deduce variable fixings and additional SOS1 constraints (this parameter replaces the old parameter constraints/sos1/updateconflpresol) - new parameter constraints/sos1/depthimplanalysis to limit the number of recursive calls of implication graph analysis - new parameter constraints/sos1/branchingrule to decide whether to use neighborhood, bipartite, or SOS1 branching (this parameter replaces the old parameters constraints/sos1/neighbranch, constraints/sos1/bipbranch, and constraints/sos1/sos1branch) performance improvements: - handle cutoffs in cons_indicator detected by infeasible inequalities - do not transfer solutions to original space, if SCIP is being freed - modified implication graph analysis of SOS1 constraint handler; a new component allows to deduce zero fixings of variables - made SOS1 constraint handler specific diving selection rule faster for the case that the SOS1 constraints do not overlap - improved disjunctive cuts by the 'monoidal cut strengthening' procedure of Balas and Jeroslow interface: - add SCIPcomputeHyperplaneThreePoints to compute a hyperplane containing three given 3-dimensional points - SCIPsolveLinearProb now uses a 1-dimensional matrix representation - made debug solution functionality thread safe (see debug.h for further information) - added interactive shell command 'display finitesolution' to print solution with infinite fixings removed, added reference to that method to 'display solution' output if there are infinite fixings - renamed MIP matrix structure to SCIP_MATRIX - changed the numeric values for PRESOLTIMING flags Makefile: - new target "dll" to build Windows dlls with MSVC - add new compiling flag OPENSOURCE to allow/forbid the usage of third party software fixed bugs: - fixed a bug in merge step of cliques during clean up phase; method did not correctly handle infeasibility in the case of multiple variable-negation pairs - fixed a previously untreated case in the linear cons simplification where coefficients only differ by slightly more than an epsilon - fixed too hard assertion in pseudoobj propagator - fixed inconsistency in knapsack constraint handler data during presolving - fixed bug in shiftandpropagate heuristic: the heuristic did not correctly handle intermediate, global bound changes of the selected variable after its tentative fixing led to a cutoff. - fixed a bug in shiftandpropagate where column positions after sorting are now correctly linked to their variables after sorting - fixed a bug in dive.c that occurred when lpsolvefreq was set to 1; after a cutoff, the solution values of the linked LP solution might have become invalid - fixed wrong check when computing cuts for factorable quadratic functions - fixed numerical problems in computation of cuts for bivariate functions in quadratic constraint handler - fixed bug in quadratic constraint handler when computing lifted-tangent inequalities - fixed bug in nonlinear constraint handler when replacing a violated nonlinear constraint leads to an infinite bound tightening of a single variable - do not analyse an infeasible LP for conflicts during diving mode when LHS/RHS of rows were changed - fixed some problem with reoptimization when the problems are infeasible or have been solved in presolving - fixed bug in SOS1 constraint handler with inconsistent data structure after restart - fixed wrong handling of negated variables in bound tightening procedure of SOS1 constraint handler - fixed bug in simple fixing heuristic of SOS1 constraint handler - fixed wrong handling of loose variables in OBBT - fixed freeing of hash for binary variables - fixed endless loop in knapsack constraint handler when continuous variables change their types to binary during presolving - squares of binary variables might not have been replaced by the binary variable itself in presolve, if the variable was originally general integer and only became binary during presolve (due to bound tightening) - fixed late change of type of slack variables in cons_indicator, if the bounds are not integral - fixed initsol and exitsol of cons_indicator, if problem has already been solved - fixed bug in parsing emphasis parameters which formerly led to completely wrong results - fixed bug in the computation of the Wilcoxon test - do not use the relative and absolute gap limit if no primal solution has been found so far - fixed two bugs in pseudoboolean constraint handler with wrong sorting of and constraints - use LPi infinity when reverting bound changes in conflict analysis - fixed bug in dive.c avoiding a check of constraints in the presence of indicator constraints - fixed bug in conflict.c with wrong reset of bounds used - fixed bug in heur_simplerounding in connection with relaxators - fixed wrong objective sense when copying the original problem - fixed bug in feaspump heuristic where last solution candidates were not updated correctly - fixed bug with transferring solutions to new runs (need to recompute objective before checking) - fixed bug in cons_indicator with changing type of slackvariable - fixed issue: constraints being parallel to objective function (after restart) sometimes led to wrongly stating infeasible - fixed issue with infinite values when checking cuts for redundancy - fixed bug during the computation of branching points for continuous variables which are almost fixed to +/- SCIPinfinity() - fixed library problems on Windows operating systems - fixed bug during coefficient tightening in varbound constraint handler - treated the case of integer variables as intermediate variables in the process of obtaining the active variable for a given binary variable - (root) reduced cost propagators are not run anymore when doing branch-and-price, since they may install upper bounds on variables which might interfere with the pricing - fixed bug with infinite shift values in heur_shifting - fixed potential memory leak in genvbound propagator SCIP version 3.2.0 ================== features: - new parameter display/allviols to print all violated constraints of the best solution during checksol in the scip shell - new parameter numerics/checkfeastolfac to scale feasibility tolerance when checking the feasibility of best found solution after the solving process finished (e.g., checksol in scip shell) - new heuristic distribution diving that bases its score function on the changes regarding solution density - extended variable branching statistics in the interactive shell by sample variance of unit gains - extended statistic output of interactive shell by more information on diving heuristic behavior - obbt propagator applies now additional separation and propagation in order to learn stronger and more bound tightenings - possible to change objective coefficients during probing mode - variable histories can be transferred between sub-SCIPs solved by LNS heuristics and the component presolver and the main SCIP to reuse this information. - tighter reliability notions introduced for reliability branching, based on pseudo-cost relative errors and comparing candidates with the best pseudo-candidate using a 2-sample student-T test. These methods are used in disjunction with the existing reliability notion that uses a fixed number as reliability threshold for every variable before turning off strong-branching. This means, the classical method must be turned off by setting parameters minreliable and maxreliable to 0. The behavior is controlled through several parameters. - new distribution branching rule to base decisions on row activity (normal) distribution over domain space - new heuristic heur_indicator that tries to make partial solutions with indicator constraints feasible. It also tries to improve them (or external solutions) by a one-opt local search. - can now output information for BAK: Branch-and-bound Analysis Kit - added scripts check_xpress.awk, check_xpress.sh, evalcheck_xpress.sh and check_cluster_xpress.sh and target "testclusterxpress" and "testxpress" in Makefile - the MPS reader can now read semi-integer variables, they are handled by creating bound disjunction constraints - the original problem can now be permuted directly after reading (if misc/permutationseed has value >= 0) - added methods to compute strongly connected components with Tarjan's Algorithm - improved clique and variable bound heuristics - the MPS reader can now handle objective constants given as (the negation of) the RHS of the objective row - we can now upgrade quadratic constraints with one bilinear term to SOC constraints - we can also upgrade general quadratic constraints with a single negative eigenvalue to SOC constraints - new parameter "misc/outputorigsol" to control whether at the end of a command line run the solution should be output in the orignal space - new score in hybrid reliability pseudocost branching that prefers nonlinear variables when solving MINLPs - new heuristic (heur_bound) which fixes all integer variables to their lower/upper bounds and solves the remaining LP - new branching rule multaggr which allows to branch on general disjunctions defined by fractional multi-aggregated variables - started support for user-defined operators in expression trees/graphs (see SCIPexprCreateUser()), interface will likely change again in future SCIP versions - in the AMPL interface, variable and constraint attributes (flags) can now be set via suffixes, where 0 (unset) stands for the default, 1 for TRUE, and other values for FALSE; see SCIPcreateVar() and SCIPcreateCons() for their meaning; for variables, "initial" and "removable" are recognized; for constraints, "initial", "separate", "enforce", "check", "propagate", "dynamic", and "removable" are recognized - Improved coordination of presolvers. There are three timings for presolvers now, FAST, MEDIUM, and EXHAUSTIVE. Each presolving callback can specify one or more of these timings in which it will be called later. Within a presolving method, the current timing can be checked and the algorithms to be performed selected based on the timing. In one presolving round, first all presolving methods with timing FAST are called, sorted by priority. If they found enough reductions, a new round is started, otherwise, all presolving methods with timing MEDIUM are called. Again, with enough reductions, a new presolving round is started, too few reductions lead to running the EXHAUSTIVE presolvers. Similar to the delay concept used before, we are not neccessarily running all EXHAUSTIVE presolvers but stop as soon as one of them found enough reductions, starting a new presolving round immediately. - new branching rules for SOS1 constraints for branching on a neighborhood or a complete bipartite subgraph of the conflict graph. In addition to variable domain fixings, it is sometimes also possible to add complementarity constraints to the branching nodes. This results in a nonstatic conflict graph, which may change dynamically with every branching node. - modified diving heuristics to handle SOS1 constraints - improved separation procedure of SOS1 constraint handler, including bound (clique) cuts and implied bound cuts - new disjunctive cut separator for SOS1 constraints - new presolving components for SOS1 constraints, including bound tightening and clique extension - added method to propagate implications of SOS1 variables - convex quadratic contraints can now generate gradient cuts which are supporting to the feasible region - new edge-concave cut separator for quadratic constraints - SoPlex interface can now (re)store dual steepest edge weights - new plugin for reoptimizing a sequence of optimization problem that differ in the objective function, e.g., sequences arising from column generation - new branching rule nodereopt to reconstruct the tree after changing the objective function - new primal heuristic for reoptimization: ofins - objective function induced neighborhood heuristic - new heuristic for reoptimization which constructs solutions based in the changes between the objective function and the optimal solution befor changing the objective function - new plugin "compr" for rearranging the search tree, currently this only works on the reoptimization tree - extended expression parsing to support power, realpower, and signpower operators - possibility to set a soft time limit which becomes active only after the first primal solution was found - the AMPL interface now passes an initial guess, if specified, as a solution (that will be checked for feasibility) to SCIP - new presolver tworowbnd for improving variable bounds and detecting redundant constraints added - new presolver dualagg for aggregating single up-/downlocked variables by a binary variable added - new presolver implfree for aggregating implied free variables added - new presolver redvub which can detect redundant variable upper bound constraints added - new presolver stuffing for fixing of singleton continuous variables added - added matrix module for getting access to the internal mixed inter linear problem matrix - new application for solving Steiner tree problems: SCIP-Jack can handle both the classical Steiner tree problem in graphs and 10 of its variants parameters: - new parameter 'DELHEADERS' for 'uninstall'-target: scip headers are only removed when invoking 'make uninstall DELHEADERS=true' - new parameter heuristics/*diving/lpresolvedomchgquot to determine the percentage of changed domains since previous LP to trigger an LP resolve [default: 0.15] (* stands for eight diving heuristics to support this feature) - new parameter heuristics/*diving/lpsolvefreq to determine the frequency for resolving LP's during the execution of this heuristic [default: 1, use 0 for a dynamic setting based on the number of domain reductions] (* stands for eight diving heuristics to support this feature) - new parameter "heuristics/shiftandpropagate/selectbest" to trigger if shiftandpropagate should select the best candidate in every round? (set to FALSE for static order) (default is FALSE) - new parameter "heuristics/shiftandpropagate/maxcutoffquot" to select a maximum percentage of allowed cutoffs before stopping the heuristic (default is 0.0) - new parameter "limits/autororestart" for triggering an automatic restart after this many nodes, or -1 for no auto restart [default is -1] - new parameter "separating/cutselrestart" for cut selection during restart copy process ('a'ge, activity 'q'uotient) [default is 'a'] - new parameter "separating/cutselsubscip" for cut selection for sub SCIPs ('a'ge, activity 'q'uotient) [default is 'a'] - new parameter "branching/relpscost/userelerrorreliability" to enable relative error based reliability - new parameter "branching/relpscost/lowerrortol" to define a lower reliability threshold for relative error based reliability - new parameter "branching/relpscost/higherrortol" to define the highest reliability threshold for relative error based reliability - new parameter "branching/relpscost/usehyptestforreliability" to enable strong branching decisions based on a 2-sample student-T test of all prior pseudo-cost observations between the best pseudo-candidate and the candidate for which to decide whether strong-branching should be applied - new parameter "branching/relpscost/usedynamicconfidence" to use a dynamic confidence level based on the amount of strong-branching simplex-iterations compared to the overall simplex iterations (default is FALSE) - new parameter "branching/relpscost/confidencelevel" to set the confidence level to be used by statistical tests - new parameter "branching/relpscost/skipbadinitcands" for skipping strong-branching candidates whose estimated gain is significantly worse than the one of the locally best (sb or pseudo) candidate - rowrepswitch set to 2.0, so row representation is activated if LP has at least 2 times more rows than columns - rename parameter "vbc/filename" to "visual/vbcfilename" - rename parameter "vbc/realtime" to "visual/realtime" - rename parameter "vbc/dispsols" to "visual/dispsols" - added parameter to switch pseudo cost update in diving heuristics (enabled by default) - one can now set emphasis parameters at the beginning of a settings file; it should start with "emphasis:" and the contain the emphasis string, e.g., "emphasis: feasibility" or "emphasis: heuristics off". - new parameter "heur/indicator/improvesols" that turns on the improvement of external solutions by one-opt - new advanced parameter "constraints/linear/rangedrowpropagation" to disabled newly implemented propagtion algorithm for ranged rows and equations - new advanced parameter "constraints/linear/multaggrremove" to perform multi-aggregations in linear constraint handler only if the constraint can be removed afterwards - at the end of a command line run the best solution can now be output in the orignal space - new advanced parameter "branching/relpscost/nlscoreweight" for weight of nonlinear score when branching on MINLPs - new parameter "constraints/SOS1/maxextensions" to define maximal number of extensions that will be computed for each SOS1 constraint in presolving - new parameter "constraints/SOS1/maxtightenbds" to define the maximal number of bound tightening rounds per presolving round - new parameter "constraints/SOS1/updateconflpresol" to update the conflict graph during the presolving procedure - new parameter "constraints/SOS1/maxsosadjacency" to define that the adjacency matrix of the conflict graph is not created in presolving if the number of SOS1 variables is too large - new parameter "constraints/SOS1/conflictprop" to define whether to use conflict graph propagation - new parameter "constraints/SOS1/implprop" to define whether to use implication graph propagation - new parameter "constraints/SOS1/sosconsprop" to define whether to use SOS1 constraint propagation - new parameter "constraints/SOS1/neighbranch" to branch on a neighborhood of the conflict graph - new parameter "constraints/SOS1/bipbranch" to branch on a complete bipartite subgraph of the conflict graph - new parameter "constraints/SOS1/sos1branch" to branch on a single SOS1 constraint, i.e., a clique of the conflict graph - new parameter "constraints/SOS1/autosos1branch" to switch to SOS1 branching if the SOS1 constraints do not overlap - new parameter "constraints/SOS1/fixnonzero": If neighborhood branching is used, then fix the branching variable (if positive in sign) to the value of the feasibility tolerance - new parameter "constraints/SOS1/addcomps" to add local complementarity constraints to the branching nodes (can be used in combination with neighborhood or bipartite branching) - new parameter "constraints/SOS1/maxaddcomps" to define the maximal number of complementarity constraints added per branching node - new parameter "constraints/SOS1/addcompsdepth" to define the maximal depth for adding complementarity constraints - new parameter "constraints/SOS1/addcompsfeas" to define a minimal feasibility value for local complementarity constraints in order to be added to the branching node - new parameter "constraints/SOS1/addbdsfeas" to define a minimal feasibility value for local bound (clique) inequalities in order to be added to the branching node - new parameter "constraints/SOS1/nstrongrounds" to define the maximal number of strong branching rounds to perform for each node (only available for neighborhood and bipartite branching) - new parameter "constraints/SOS1/nstrongiter" to define the maximal number LP iterations to perform for each strong branching round - new parameter "constraints/SOS1/boundcutsfromsos1" to define whether to separate bound (clique) inequalities from SOS1 constraints - new parameter "constraints/SOS1/boundcutsfromgraph" to define whether to separate bound (clique) inequalities from the conflict graph - new parameter "constraints/SOS1/autocutsfromsos1" to automatically switch to separating bound cuts from SOS1 constraints if the SOS1 constraints do not overlap - new parameter "constraints/SOS1/boundcutsfreq" to define the frequency for separating bound (clique) cuts - new parameter "constraints/SOS1/boundcutsdepth" to define the node depth of separating bound (clique) cuts - new parameter "constraints/SOS1/maxboundcuts" to define the maximal number of bound (clique) cuts separated per branching node - new parameter "constraints/SOS1/maxboundcutsroot" to define the maximal number of bound (clique) cuts separated per iteration in the root node - new parameter "constraints/SOS1/strthenboundcuts" to define whether to strengthen bound (clique) cuts in case bound variables are available - new parameter "constraints/SOS1/implcutsfreq" to define the frequency for separating implied bound cuts - new parameter "constraints/SOS1/implcutsdepth" to define the node depth of separating implied bound cuts - new parameter "constraints/SOS1/maximplcuts" to define the maximal number of implied bound cuts separated per branching node - new parameter "constraints/SOS1/maximplcutsroot" to define the maximal number of implied bound cuts separated per iteration in the root node - new parameter "separating/disjunctive/maxrank" to define the maximal permissible rank of a disjunctive cut that could not be scaled to integral coefficients - new parameter "separating/disjunctive/maxrankintegral" to define the maximal permissible rank of a disjunctive cut that could be scaled to integral coefficients - new parameter "separating/disjunctive/maxweightrange" to define the maximal valid range of simplex tableau row weights - new parameter "separating/disjunctive/maxdepth" to define the node depth of separating disjunctive cuts - new parameter "separating/disjunctive/maxrounds" to define the maximal number of separation rounds of disjunctive cuts in a branching node - new parameter "separating/disjunctive/maxinvcuts" to define the maximal number of disjunctive cuts investigated per iteration in a branching node - new parameter "separating/disjunctive/maxinvcutsroot" to define the maximal number of disjunctive cuts investigated per iteration in the root node - new parameter "separating/disjunctive/maxconsdelay" to delay separation of disjunctive cuts if number of SOS1 constraints is larger than predefined value - new parameter "constraints/quadratic/gaugecuts" to enable convex quadratics to generate gradients cuts which are supporting - new parameter "constraints/quadratic/advanced/interiorcomputation" to select the way of computing and interior point for gauge cuts - new paramter "misc/allowobjprop" to allow objective function propagation - new paramter "misc/allowdualreds" to allow dual reductions - new advance parameter "constraints/soc/generalsocupgrade" to allow general quadratics to be upgraded to soc - new parameter "limits/softtime" to set a soft time limit (active only after first primal solution was found) - new parameter "heuristics/shiftandpropagate/binlocksfirst" to set if binaries without locks should be preferred in ordering performance improvements: - zi rounding heuristic uses buffer data structures, thereby decreasing total memory usage of SCIP - adjusted (hard) diving heuristics to solve fewer LPs. LP's are resolved only if a parameter-defined percentage of the variable bounds changed through domain propagation or at a predefined frequency. - some of the diving heuristics additionally consider indicator variables and SOS1 variables as candidate variables and try to make these constraint types feasible before passing a rounded solution to SCIPtrySol() - improved vartype upgradability from continuous to implicit variables in cons_linear.c, depending on their objective coefficients - using sparsity information of the SoPlex LP - new presolving/propagation algorithm using the gcd for ranged rows and equations in cons_linear - improved propagation of SOS1 constraint handler using the information from a conflict interface: - avoid potential comparisons of different infinity values by adjusting the LP solution value - new callback function SCIP_DECL_CONSGETDIVEBDCHGS to provide constraint handler method to suggest dive bound changes during the generic diving algorithm, see type_cons.h for details - SCIPincludeConshdlr has a new argument to provide a divebdchg-callback for the constraint handler to include - new method SCIPaddDiveBoundChange() to add a diving bound change to the diving bound change storage of SCIP together with the information if this is a bound change for the preferred direction or not, to be used by constraint handlers inside the getDiveBdChgs-callback - new setter function SCIPsetConshdlrGetDiveBdChgs() in scip.h to set dive bound change callback for this constraint handler - SCIPintervalSign(), SCIPintervalAbs(), SCIPintervalMax(), SCIPintervalMin(), SCIPexprgraphGetNodePolynomialMonomialCurvature(), and SCIPexprgraphTightenNodeBounds() need an infinity value to decide whether an interval is empty or not - SCIPgetFeasibilityQuadratic() and SCIPgetActivityQuadratic() returns now a SCIP_RETCODE and needs an additional SCIP_Real* to store the result - new method SCIPwriteParam() to write a single parameter to a file - new methods SCIPcheckParam{Bool,Char,...}() to check whether a parameter value is within the feasible domain - new methods SCIPchgCoefLinear() and SCIPdelCoefLinear() to modify linear constraint during problem creation - new methods SCIPchgLhsQuadratic(), SCIPchgRhsQuadratic(), SCIPchgLinearCoefQuadratic(), SCIPchgSquareCoefQuadratic(), and SCIPchgBilinCoefQuadratic() to modify quadratic constraints during problem creation - new methods SCIPgetFeasibilityQuadratic() and SCIPgetActivityQuadratic() to get the feasibility and activity of a quadratic constraint in a given solution - new method SCIPcutGetLPActivityQuot() in pub_cutpool.h to get the potion of LP's where this cut was sharp in an optimal basis. - methods which support statistical tests in pub_misc.h, SCIPstudentTGetCriticalValue(), SCIPcomputeTwoSampleTTestValue() etc. - new enum SCIP_CONFIDENCE_LEVEL for different levels of confidence for statistical tests. - new struct SCIP_DIVESET that bundles options for SCIP's diving heuristics; all hard diving heuristics (those without 'obj' at the beginning) include diveset and implement only the scoring callback. - new method SCIPcreateDiveset() to add a diveset to a heuristic. Heuristics may have multiple divesets under different names - new callback SCIP_DECL_DIVESETGETSCORE to implement scoring function to guide diving - new method SCIPperformGenericDivingAlgorithm() that performs diving with periodic LP resolve according to the diveset argument. - rename all file "*_vbc.?" to the more generic "*_visual.?" - submenu for setting "vbc" settings renamed to "visual" - rename SCIPdigraphGetSuccessorsDatas() -> SCIPdigraphGetSuccessorsData() - SCIPdigraphSetNSuccessors() sets the number of successors of some digraph node to a given value - added new sorting functions SCIPsortRealRealRealBoolBoolPtr(), SCIPsortDownRealRealRealBoolBoolPtr() - added new sorting functions SCIPsortIntIntIntReal(), SCIPsortDownIntIntIntReal(), SCIPsortRealIntInt(), SCIPsortDownRealIntInt() - added SCIPcomputeArraysIntersection() to compute the set intersection of two ordered arrays - added SCIPcomputeArraysSetminus() to compute the set difference of two ordered arrays - moved buffer memory handling to blockmemory/memory.?; remove files type_buffer.h, struct_buffer.h buffer.h buffer.c; removed functions SCIP*buffer*() from scip.? and replaced them by macros; new function SCIPbuffermem() to get buffer memory; redesigned buffer interface to be similar to block memory; added checks for strange sizes - new function BMSallocClearBlockMemoryArray()/SCIPallocClearBlockMemoryArray() and BMSallocClearBufferMemoryArray(), SCIPallocClearBufferArray() to allocate arrays that are initialized to 0 - renamed SCIPconshdlrGetPropTimingmask() to SCIPconshdlrGetPropTiming(), new method SCIPconshdlrSetPropTiming() - removed SCIPconshdlrIsPresolvingDelayed() and SCIPconshdlrWasPresolvingDelayed() - new methods SCIPpresolGetTiming(), SCIPpresolSetTiming(), SCIP{conshdlr,prop}GetPresolTiming(), and SCIP{conshdlr,prop}SetPresolTiming() - removed "delay(presol)" parameter from SCIPinclude{Conshdlr,Presol,Prop}() and added "(presol)timing" parameter - new parameter "presoltiming" for method SCIPpresolCons() - SCIPvarIsSOS1() returns whether some variable is involved in an SOS1 constraint - SCIPgetConflictgraphSOS1() gets conflict graph of SOS1 constraints - SCIPvarGetNodeSOS1() returns node of SOS1 variable in the conflict graph - SCIPnodeGetVarSOS1() returns SOS1 variable associated to some given node in the conflict graph - SCIPmakeSOS1sFeasible() based on solution values, fixes variables to zero to turn all SOS1 constraints feasible - SCIPsolveLinearProb() solves a linear problem of the form Ax=b for a regular square matrix A - new methods SCIPaddSquareLinearization(), SCIPaddSquareSecant(), SCIPaddBilinLinearization(), and SCIPaddBilinMcCormick() in cons_quadratic.h to compute linear under- and overestimation for bilinear and quadratic terms - new methods for mixed inter linear matrix access (see pub_matrix.h) added fixed bugs: - fixed bug in primal.c and tree.c by using SCIPinfinity() as a cutoffbound to delete child nodes - fixed bug in cons_indicator with handling local bounds - fixed bug in cons_quadratic.c which leads to an overflow when SCIP allocates memory for a dense matrix - fixed bug in lp.c which leads to wrong primal and dual feasibility - fixed wrong comparison when executing branching rule for external branching candidates - fixed bug in cons_abspower.c: do not generate cuts with infinity right-hand-side anymore - fixed wrong handling of infinite activities and primal values in sepastore.c and lp.c - fixed assert in cons_soc.c: now soc with 1 lhs variable are allowed - fixed bug that led to an erroneous warning about the clock type - fixed setting of enforcement flag for constraints created by reformulation in nonlinear constraint handlers - fixed bug in heur_nlpdiving.c: wrong counting of fix variables - fixed bug in cons_quadratic.c: do not generate linearization cuts for disabled constraints - fix behavior of 'make install' which now sets symbolic links and short links to binaries and libraries - fix characterization of logic or constraints in SCIP's NLP relaxation - fix wrong handling of SCIP_NLPSOLSTAT_LOCALINFEASIBLE solution status in nlp.c - fix bug which lead to wrong global bound tightenings in prop_genvbounds.c - fix missing clean phase of bilinear terms with zero coefficient in cons_quadratic.c - fix handling of infinite intervals in SCIPintervalIsEmpty() - fix potentially tightening of LB/UB of a variable to +/- infinity in cons_quadratic - fix spatial branching on implicit integer variables - fixed bug in intervalarith.c: bivariate quadratic equations may have been solved wrongly if second variable is unbounded - fix wrong sorting of bilinear terms in cons_quadratic - fix wrong comparisons of values larger/less than +/- SCIPinfinity() in branch.c, lp.c, and sol.c - fixed wrong assert in cons_indicator (slack variables might be replaced by active variables that have nonzero objective) - try to handle fixings of multi-aggregated variable in cons_sos1 presolving and avoid error - fix potential memory leak in method SCIPgetConsCopy() - fix potential memory leak in method detectRedundantConstraints() of the knapsack constraint handler - fix potential memory leak in SoPlex LP interfaces when setting invalid basis - fix call to random generator for Windows operating systems in misc.c - fix late creation of auxiliary LP in cons_nonlinear.c, which lead to a segmentation fault with lpi_spx2.cpp - fixed again a bug in backward propagation of linear expressions in expression graph - fixed problem with lpisrelax flag in probing mode when doing branch-and-price - fixed bug in pseudoboolean constraint handler about negated variables misc: - moved assertions in comparison methods from scip.c to set.c - added more checks to SCIP{alloc,realloc,duplicate}BufferArray() to handle overflows properly SCIP version 3.1.1 ================== fixed bugs: - fixed bug in cons_quadratic which leads to wrong min/max activities - fixed wrong conversion of reals representing negative integer values - in debug mode, SCIP checks that no NaN's are introduced in SCIPsolSetVal() - fixed bug in proximity heuristic which attempted to enter diving mode even at nodes without a constructed LP - fixed wrong pseudo cost updates during diving heuristic execution after backtracking - fixed bug 697 (and 699), calling SCIPsolve() after the problem was already solved and SCIPfreeSolve() was called now does nothing anymore - fixed memory leaks in case of erroneous parsing of constraints, e.g., non-linear constraints - added support for character '#' in variable names in old non-linear CIP format (i.e., names without "<" and ">") - fixed bug 702, removed too hard assert when casting too big values into SCIP_Longint - removed wrong break in cons_pseudoboolean - branching for continuous variables with unbounded intervals now takes "branching/clamp" into account - fixed bug in SCIPpermuteProb(), when called in transformed stage and non-active constraints exist - corrected copy of disjunction constraints - forbid aggregations with scalar smaller feastol or larger 1/feastol - fixed bug 683, not recognizing errors/segfaults especially in free stage of SCIP by improving the check scripts - fixed bug in presolving of abspower constraints that lead to wrong variable locks - fixed bug where quieting a message handler also disabled writing to files other than stdout - fixed bug 708, special case of implications led to a fixing - allow to call SCIPmarkConsPropagate() in INITPRESOLVE stage - fixed bug, variable bounds detected wrong infeasibility - another bug fix when computing the original variable sum of a given variable in SCIPvarGetOrigvarSum() - fixed bug in cons_varbound.c using the wrong constraint side for updating an upper bound - fixed missing memory allocation for node data in digraphs - allow to read numbers like "42856." in lp-format - fixed bug in heur_oneopt: avoid bound violations if shift value is negative due to infeasibilities - fixed setting solution value of multi-aggregated var in xml-solution case - fixed wrong output of status when an objective limit was imposed but not reached yet - fixed the rare case that branching was performed even though strong branching found global bound changes leading to an infeasible/objlimit LP - fixed bug that reaching a solution limit by beforenode heuristics lead to disregarding the current node if the optimization process was restarted later - fixed bug with reading '>=1' indicator constraints in LP-files - fixed bug changing the variable type of an negated variable - use dual feasibility tolerance for comparisons regarding reduced costs - fixed bug with freeing problem: need to reset objective limit - fixed bug in presolve of cons_nonlinear: wrong constraint upgrades may have been performed due to outdated bound information in expression graph - fixed numerical troubles in SCIPcreateFiniteSolCopy() - fixed bug in SCIPpermuteProb(): if called before transforming the problem, data structures were not initialized yet - fixed bug in trysol heuristic not saving the best solution in maximization problems - fixed bug in aggregation procedure if two variables were of non-binary type but for one of the variables SCIPvarIsBinary() returned true - treat activities of pseudo solutions as invalid when containing positive and negative infinity contributions - fixed bug in cons_setppc, wrongly aggregating variables if dual-presolving was disabled - fixed bug that objective limit was not reset correctly during SCIPfreeTransform() for maximization problems - fixed bug in cons_sos1: locks and events were not initialized if constraint was added to transformed problem - fixed bug(?) in reader_mps: variables are now written in columns section even of they occur in no constraint and have an objective coefficient of 0 (otherwise, CPLEX and Gurobi cannot read the file) - fixed bug that hitting the time limit while solving a pure LP and then continuing the solving process lead to not solving the LP, but always creating a single child node until maximum depth is reached - fixed bug in reader_lp which created two indicator constraints with the same name to trigger an equality - fixed bug leading to an incorrect dual bound when solving probing LPs within a DURINGPRICINGLOOP heuristic - fixed bug in components presolver with handling of dual fixable variables: unboundedness was not detected, better handle components with single variables by dual fixing propagator - fixed bug in prop_dualfixing: don't fix variables to infinite values during solving - fixed bug in cons_setppc with dual presolving disabled - fixed sign of the dual multipliers returned by AMPL interfaces for maximization - fixed bug in GMI example: fractionality of slack variable is now computed correctly - issues in component solving by presol_components do not lead to stopping the overall process, anymore, the component is just disregarded - fixed bug when reading indicator constraints for linear constraints (equations/ranged rows) from MPS files - fixed LP interface of CPLEX: functions getBInv* return the correct sign of the coefficients. performance improvements: - improved solving of LPs in OBBT propagator - improved activity-delta computation and thereby propagation for linear constraints - improved memory management of proximity heuristic - disabled statistic timing in all subscips via new parameter timing/statistictiming features: - use clock average to reduce number of system calls via timing/rareclockcheck parameter - added copy mechanism for conjunction constraints - added Makefile support for cygwin 64 Bit - added revised lpi_xprs for using XPRESS as LP solver interface: - added methods SCIPconvertRealTo[Long]Int() to convert reals that represent integers to [long] ints. - added methods SCIPisDualfeasEQ() and related to perform checks w.r.t. to the dual feasibility tolerance - forbid to call SCIPfixVar() in SCIP_STAGE_PRESOLVED stage, which is not allowed since it calls SCIPchgVarLb/Ub() - rename SCIPdigraphGetNodeDatas() to SCIPdigraphGetNodeData(); SCIPdigraphSetNodeDatas() to SCIPdigraphSetNodeData() - rename array arcdatas in digraph to arcdata - SCIPapplyProximity() has an additional argument freesubscip, which causes the method to free the created subscip automatically at the end. - new method SCIPdeleteSubproblemProximity() to free proximity subproblem manually as external caller - added dialog for writing the finite solution (calling SCIPcreateFiniteSolCopy() before writing) - new method SCIPhasPerformedPresolve() to check, e.g., whether LP duals are accessible - AMPL interface now returns dual multipliers if problem is an LP and presolving was turned off - changes in clock type are now transferred to SoPlex - corrected wrong primal bound in statistics for unbounded problems parameters: - new parameter timing/rareclockcheck to call the system time less frequently, based on the current average time interval between two calls to SCIPsolveIsStopped(); the default value is FALSE - new parameter timing/statistictiming to enable/disable all timers for statistic output of SCIP; the default value is TRUE - changed default value of parameter heuristics/proximity/minimprove to 0.02; previous value was 0.25 - changed default value of parameter heuristics/proximity/usefinallp to FALSE Makefile: - allow to turn off block and buffer memory by the makefile parameters NOBLKMEM, NOBUFMEM, NOBLKBUFMEM; also remove the now superfluous makefiles for noblkmem, nobufmem, noblkbufmem SCIP version 3.1.0 ================== fixed bugs: - fixed bug when adding (global) clique, implications or variable bound information in solving stage that lead to global bound changes which contradict local bounds and therefore need to be stored as pending bound changes - unlinking a solution now copies solution values smaller than SCIPepsilon() avoiding some feasible solution in the transformed problem to be infeasible in the original problem - fixed bug when flushing the warning buffer when SCIP is closed - fixed wrong strong branching results in lpi_grb.c and an invalid write - fixed wrong presolving finished status which sometimes occurred when the time limit was hit during presolve - fixed several bugs where variables or constraints were not freed correctly - fixed minor bugs in presolving in cons_setppc.c and cons_logicor.c - do not multi-aggregate variables if the constant would be a huge value in order to avoid numerical troubles - fixed bug with infinite multi-aggregation constants - fixed wrong bound calculation in sepa_rapidlearning - fixed bug when a bound change contradicts a local bound and is stored as pending, but the contradicting local bound becomes global afterwards (--> node where pending bound change is valid can be cut off) - fixed bug w.r.t. changing the variable branching priority beyond the problem stage - fixed statistics bug: externally given solutions and new solutions found while transforming existing ones are now listed in line "other solutions" of primal heuristics statistics - fixed memory bug in reader_mps - fixed output of aggregated variables in indicator constraints in lp and mps-format - fixed bug in reading indicator constraints in mps-format - improved handling of initial constraints: constraints which are initial, but added during the search to an already treated node are kept and added to the LP at every node where they are active - fixed bug where a limit on presolving rounds was exceeded by 1 - fixed bug that lead to resolving the LP after diving instead of restoring the buffered solution - fixed rare bug with conflict analysis and LP/LPI having different states after diving - fixed bug in genvbounds propagator occurring when objective offset or scale changes after a restart - fixed bug in flowcover separator to exclude unconstrained rows in aggregation - fixed bug in prop_dualfix w.r.t. to fixing of variables to infinity after presolving - fixed bug in random generators SCIPgetRandomInt() and SCIPgetRandomReal() for large intervals - fixed bug in genvbounds propagator by replacing non-active variables on right-hand side after presolving - nonlinear readers now create auxiliary objective variables and constraints always as initial and not removable in order to avoid unbounded LPs due to loose variables with infinite best bound - fixed bug in cons_superindicator concerning names of upgraded constraints - fixed several bugs in lpi_grb - fixed bug in sepa_cgmip computeObjWeightSize() w.r.t. equal sized rows - fixed several minor bugs with handling of memory when writing aggregated variables (reader_lp, reader_mps) - fixed minor bug in cons_linear w.r.t. disabled presolving - fixed bug in handling max-function in ampl interface; added support for min-function - fixed bug in cons_indicator with trying to create solution in problem stage - fixed bug in cons_orbitope with fixing upper right triangle in non-root nodes - fixed bug in reader_lp when writing bilinear terms (product sign was missing) - allow again branching on continuous variables with huge bounds - make sure that bound changes of negated original variables are correct data structures: - new data structure for (circular) queues (SCIP_QUEUE) - hash tables will now increase dynamically features: - new LNS heuristic called "proximity", which solves a problem in which a local branching constraint replaces the objective function which in turn is treated as additional constraint - added average gap based on primal-dual integral to solution statistics; can be disabled via parameter "misc/calcintegral" - new LP-based rounding heuristic (heur_randround) whose randomized rounding is biased towards the LP solution value; the heuristic uses the probing mode of SCIP to generate conflict clauses on the fractional variables - added breadth first search node selection - new node selection rule UCT which balances exploration and exploitation by considering node visits - added new dual presolving for setppc-constraints - changed dualfix presolver to propagator such that dual fixing can also be applied during repropagation of the root node - added upgrade from varbound constraints to set-packing constraints - added SCIPwriteCliqueGraph() to scip.{c,h} to write the clique graph in GML format into a given file - added upgrade from bounddisjunction constraints to set-packing/logicor constraints - added two methods to iterate over a sparse solution (SCIP_SPARSESOLUTION), see pub_misc.h - added possibility to not set a cutoff bound in the LP solver (can be enabled by setting <lp/disablecutoff> to TRUE) - added passing MEM option of testgams(cluster) target as workspace option to GAMS jobs - cumulative constraint handler adds disjunctive constraints (cumulative with capacity 1) for all jobs which cannot be processed in parallel - added new clique extraction algorithm for linear constraints - added missing debugging solution check for cliques - the slack variables of indicator constraints can now be scaled - added redundancy check of sides of ranged row varbound constraint - added coefficient tightening for ranged row varbound constraint - added SCIPsortLongPtrRealBool(), SCIPsortLongPtrRealRealBool(), SCIPsortLongPtrRealRealIntBool() and corresponding methods for sorting, insertion and deletion - added a data pointer to each node of the SCIP_DIGRAPH - the statistics now include the value of the first LP solved at the root node (without cuts) - all readers now take the global parameters "reading/dynamic{conss|cols|rows}" and "reading/initialconss" into account - XOR constraint handler can add two extended formulations (flow/asymmetric, parameter "addflowextended/addextendedform") - added the possibility to copy the original problem via SCIPcopyOrig() - SCIPgetVarCopy() will now copy the original bounds when called for an original variable - added method SCIPcreateFiniteSolCopy() which creates a copy of a solution, thereby trying to reduce the solution value of variables which were fixed to infinite to the smallest feasible value - added propagation method to cons_xor relying on Gaussian elimination, which can also produce feasible solutions - new branching rule "cloud branching" that considers several alternative LP optima - additional vbc output added: branching information is printed earlier and also for nodes which were cut off - added new statistic which distinguishes between internal nodes and leaves which got processed - added reader_pbm, which writes the constraint-variable incidence matrix in pbm format (possibly scaled to given size) - added possibility to separate a cutpool w.r.t. a given solution (instead of LP-solution) - added multi-aggregation for binary variables with at most two uplocks and two downlocks, which emerge from set- partitioning or set-packing constraints - added full-dual presolving step in setppc constraint handler - added upgrade from quadratic constraints to set-packing constraints - generalized the linking constraint handler - in verblevel SCIP_VERBLEVEL_FULL, the number of non-zeros will be output for the original and presolved model - new presolving step for tightening logicor constraints using implication and clique information - can now read and write CIP-files with (multi-)aggregated variables - new method SCIPapplyProbingVar() in prop_probing.h - added first implication detection in cons_linear - several new presolving steps for linear and knapsack constraints, using gcd information and many more - cons_indicator can now try to construct feasible solutions from a cover - reader_osil can now read SOS1 and SOS2 constraints - reader_lp and reader_mps are now able to write and-constraints in form of their (weak/strict) relaxation - added possibility to forbid upgrading of linear constraints - it is now possible to add an offset for the original problem instance, all original solutions will be initialized with this value and updated, when the offset is changed - added clique presolving for xor constraints - added upgrade of continuous variables to implicit variables for linear equations even if the coefficient is not equal to 1 - added presolving using pairs of variable bound constraints that use the same variables - added strong branching with domain propagation support: in SCIPstartStrongbranch(), support for propagation can be enabled (uses the probing mode, some overhead compared to standard strong branching), after that SCIPgetVarStrongbranchWithPropagation() can be used to perform strong branching on a variable with previous domain propagation; similar to probing, valid bounds for variables are collected - strong branching with propagation can be enabled in fullstrong and relpscost branching rule - added possibility to store pricing norms of the LP solver (in addition to basis information) to speed up LP solving after a backtrack, e.g. in probing or strong branching with domain propagation - probing supports implicit binary variables - added scaling to computation of relative interior point in SCIPcomputeLPRelIntPoint() - added more presolving to cons_indicator, checking whether indicator/slack variables are aggregated - before copying solutions to the original solution candidate storage, infinite solution values can now be removed using SCIPcreateFiniteSolCopy() - new initial constraints are now added to the LP before solving a probing LP - SoPlex (>= 1.7.0.5) can compute condition number of current basis matrix via LP interface - added McNemar tests and Wilcoxon signed rank tests to cmpres.awk evaluation scripts - a pricer can now return that no further pricing should be done but rather early branching, even if it added variables - dual solution can now be displayed for pure LPs when no presolving was performed - first implementation of parsing for nonlinear constraints in CIP format - added reading capability to GAMS reader (if compiling with GAMS=true, requires a GAMS system) - added capability of writing SOS1/2 constraints to GAMS reader (introduces extra variables and equations) performance improvements: - conflict consisting of exactly two binary variables will be handled as set-packing constraint instead of an logicor constraint and the corresponding clique information is globally added - improved methods SCIPlpiGetBInv{Row,Col,ACol} for row representation in SoPlex LP interface - fasten repropagation for set-packing and -partitioning constraints - shorten conflicts and deriving global boundchanges from conflicts - disabled multi-aggregation in linear constraint handler when coefficients differ too much - improved multi-aggregation in linear constraint handler when only one variable in the aggregation has infinity contribution - improved dual-presolving for setppc constraints in special cases - apply lowerbound provided by pricers already during pricing loop, stop pricing if the lower bound computed by pricing already exceeds the cutoff bound - improved performance of method SCIPsolRetransform() when called during presolving with many aggregations - minor presolving performance improvements in cons_logicor.c and cons_knapsack.c - added upgradability for implicit binary variable cases for linear constraints - improved performance of SCIPcliquelistDel(), SCIPcliquetableAdd(), SCIPcliquetableCleanup() - improved merging of and-constraints - faster feasibility check of LP solutions (controlled by parameters lp/checkprimfeas and lp/checkdualfeas) interface: - SCIPgetLPBranchCands() can be used to retrieve the number of implicit integer variables with fractional LP solution value via an additional pointer; the corresponding implicit integer variables can be accessed together with their fractionalities and solution values in the same way as binary and integer variables before; the arrays are sorted such that binary and integer variables precede the implicit integer variables; the method SCIPbranchcandGetLPCands() has been modified in the same way - SCIPcalcMIR() gets an additional parameter "cutrank" which returns the rank of the aggregation; via SCIProwChgRank() the rank of a cut can be changed (default rank is 0) - added number of constraints which are marked for propagation to callback method consprop - SCIPcalcMIR() takes an additional parameter sidetypes to determine which side of the rows to use (relevant for ranged rows) - SCIPaddCut() has an additional parameter that determines whether the cut to be added is infeasible for local bounds - SCIPwriteMIP() has an additional parameter that allows to write removable rows as lazy constraints - SCIPstartStrongbranch() has a new parameter "propagate" to enable or disable propagation support for strong branching - removed parameter "normtype" from function SCIPcomputeLPRelIntPoint() - removed all message length parameters in message.c and for printing error messages (not needed anymore) - SCIPgetConsCopy() now always captures the created constraint - SCIPgetLPObjval() now returns the LP value of the current (suboptimal) basis if the iteration limit is hit during LP solving (instead of -infinity); this value is not necessarily a valid dual bound and must not be used as such, but can be used as an objective estimate, e.g., if strong branching is simulated using the probing mode - the HEUREXEC callback has a new parameter "nodeinfeasible" which denotes whether the current node was already detected to be infeasible - the PRICERREDCOST callback has a new parameter "stopearly", which is a bool pointer to store whether pricing should be stopped early although variables were generated, and early branching should be performed - new method SCIPadjustImplicitSolVals() which sets implicit integer variables to an integer value in a given solution without deteriorating its objective value - new methods for the SCIP_QUEUE data structure in pub_misc.h, misc.c SCIPqueueCreate(), SCIPqueueFree(), SCIPqueueClear(), SCIPqueueInsert(), SCIPqueueRemove(), SCIPqueueFirst(), SCIPqueueIsEmpty(), SCIPqueueNElems() - new methods SCIPconshdlrIncNCutsFound(), SCIPsepaIncNCutsFound(), and SCIPsepaIncNCutsFoundAtNode() to increase the number of found cuts - added function SCIPgetFirstLPTime() to return the time needed to solve the first LP of the root node - added SCIPshrinkDisjunctiveVarSet(), which takes an set of variables with corresponding bounds and boundtypes, and tries to derive global boundchanges and also to shorten this set of variables by using cliqe, implication and variable bound information - new methods SCIPgetFirstLP{Dual/Lower}boundRoot() which return the value of the first LP solved at the root node - new method SCIPgetNRootFirstLPIterations() which returns the number of LP iterations for the first LP solved at the root node - new method SCIPstoreSolutionGap() in scip.c, to store the gap when the first and last solution is found - methods SCIPparseVar(), SCIPvarParseOriginal(), and SCIPvarParseTransformed() now return the end of the parsed string - new methods SCIPcopyOrig(), SCIPcopyOrigProb(), SCIPcopyOrigVars(), and SCIPcopyOrigConss() which allow to copy the complete original problem, the problem data, variables, and constraints, respectively - new functions SCIPchgRowLhsDive() and SCIPchgRowRhsDive() that allow to change the sides of a row during diving - new function SCIPselectVarStrongBranching() to get the variable that fullstrongbranching would select - added function SCIPseparateSolCutpool() to separate a cutpool w.r.t. a given solution - added method SCIPdoNotMultaggr() returning whether multi-aggregation is completely disabled - added method SCIPconsIsMarkedPropagate() to ask whether a constraint was explicitly added for propagation - added new method SCIPaddOrigObjoffset() in scip.{c,h} which adds a value to the offset in original space and updates all orignal solutions correspondingly - added method SCIPgmlWriteNodeWeight() to write node weights - new function SCIPwriteCliqueGraph() which allows to write a graph with node weights for fractional variables - added SCIPconsAddUpgradeLocks() and SCIPconsGetNUpgradeLocks() to either add/decrease the counter on upgrade-locks on a constraint or get the current number of upgrade-locks - new methods SCIPlpiGetNorms(), SCIPlpiSetNorms(), and SCIPlpiFreeNorms() for getting the LP pricing norms from the LP solver, loading them back into the solver, and freeing the data - add method SCIPgetNCheckConss() in scip.{c,h} - new method SCIPcopyImplicationsCliques() that copies implications and cliques - allow dialog option to write clique graph - new section "Root Node" in statistics, listing objective value, iterations and solving time for the first LP solved at the root node as well as final dual bound of the root node and LP iterations for processing the root node (those where listed in the "Solutions" section before, named "Root Dual Bound" and "Root Iterations") - add support for SOS1 and SOS2 constraints to AMPL interface (see interfaces/check/testset/SOS/sos?a.mod for example) - added a copy of the GAMS/SCIP interface to interfaces/gams - beta version of a python interface for the scipoptsuite is now available under interfaces/python - beta version of a Java native interface is now available under interfaces/jni parameters: - parameter "branching/scorefunction" has new value 'q' for for 'q'uotient branching score function - new parameters "branching/firstsbchild" and "branching/forceall" to specify the first child node to be investigated during strong branching ('u'p, 'd'down, 'a'uto) and whether always both children should be solved (only for strong branching with domain propagation, per default, the second child is not looked at when the first is infeasible) - new parameters "branching/checksol" and "branching/heursbsol" to specify whether the strong branching LP solution should be checked for feasibility and whether a simple rounding heuristic should be run on this solution - added "conflict/maxvarsdetectimpliedbounds" parameter to decide whether the a valid conflict of what maximal length will be used to derive global bound changes - added "conflict/fullshortenconflict" parameter to decide whether we want to stop shortening a conflict set, when no global bound changes can be found anymore - new parameter "constraints/indicator/scaleslackvar" for scaling of the slack variable in indicator constraints - new parameter "constraints/xor/addextendedform" to add an extended formulation in XOR-constraints - new parameter "constraints/xor/addflowextended" to add use the extended flow formulation in XOR-constraints - new parameter "constraints/indicator/trysolfromcover" for trying to construct a feasible solution from a cover - new parameter "constraints/linear/checkrelmaxabs" for checking linear constraints with a side of 0.0 relative to - new parameter "constraints/logicor/strengthen", should pairwise constraint comparison try to strengthen constraints by removing superflous non-zeros? - new parameter constraints/and/upgraderesultant to upgrade resultants of and constraints from binary to implicit binary variables, default is TRUE - added parameter "constraints/abspower/scaling" and "constraints/nonlinear/scaling" - changed type of parameters "constraints/bivariate/scaling", "constraints/quadratic/scaling", "constraints/soc/scaling" from boolean to character - changed default for "constraints/{abspower,bivariate,nonlinear,quadratic,soc}/scaling" to off - new possible values for parameter "heuristics/shiftandpropagate/sortkey" for sorting variables w.r.t. their norm, default changed from 'u' to 'v', which means sorting downwards by violations - new parameter "heuristics/shiftandpropagate/collectstats" which decides whether variable statistics are collected - new parameters "heuristics/shiftandpropagate/preferbinaries" and "heuristics/shiftandpropagate/stopafterfeasible", which decide whether binaries should be shifted first and the shifting should be stopped when no violations are left - new parameters "heuristics/"<heurname>"/lplimfac" for LNS heuristics to limit the number of LPs solved in a subproblem the maximum absolute value in the activity instead of 1.0 - new parameter "heuristics/shiftandpropagate/fixbinlocks" for fixing binary variables with no locks in one direction to the corresponding bound - new parameter "heuristics/shiftandpropagate/impliscontinuous" to decide whether implicit integer variables are treated as continuous variables - new parameter "lp/disablecutoff" to toggle usage of LP cutoff bound (0: enabled, 1: disabled, 2: auto = disabled if pricers are used) - replaced parameter "lp/checkfeas" by two parameters "lp/checkprimfeas" and "lp/checkdualfeas" to decide on primal and dual feasibility checks individually - new parameter "misc/calcintegral" (default TRUE) to trigger calculation of primal-dual integral - new parameter "misc/finitesolutionstore" to switch whether infinite fixings should be removed from solutions before copying them to the original solution store - new advanced parameters "misc/permuteconss" and "misc/permutevars" to control whether variables and/or constraints should be permuted, if permutationseed != -1 - removed all local parameters "reading/(READER)/dynamic{conss|cols|rows}" and replaced them by global parameters "reading/dynamic{conss|cols|rows}" - new parameter "propagating/obbt/conditionlimit" to discard instable LP bases - new advanced parameter "presolving/components/feastolfactor" to increase the feasibility tolerance in all sub-SCIPs, when solving a component - new parameter "reading/(READER)/initialconss" that determines whether model constraints are initial - new parameter "reading/cipreader/writefixedvars" for disabling printing of fixed variables in CIP format - new parameters "reading/lpreader/linearize-and-constraints" and "reading/mpsreader/linearize-and-constraints" to allow and-constraints to be linearized when printing in LP and MPS format, respectively - new parameter "reading/lpreader/aggrlinearization-ands" and "reading/mpsreader/aggrlinearization-ands" to enable/disable the printing of the weak or strict relaxation of and-constraints in LP and MPS format, respectively - new parameter "separating/gomory/sidetypebasis" to decide whether the sides of ranged rows should be determined from the basis status - new parameter "separating/oddcycle/cutthreshold" to run odd cycle separation if not enough cuts have been found - remove parameter "separating/closecuts/relintnormtype" - new parameter "separating/feastolfac" to allow dynamic decrease of relaxation feasibility tolerance depending on feasibility to applied cuts, i.e., allow relaxation solutions to have a primal infeasibility of at most this factor times the infeasibility of applied cuts - new parameter "separating/zerohalf/delayedcuts" to use the delayed cutpool for the zerohalf separator - new parameter "write/allconss" to enable that all constraints are written - new parameter "write/genericnamesoffset" when writing a generic problem to define an offset on the variable numbering - changed default value of parameter numerics/dualfeastol to 1e-7 for safer dual bounds from LP solver - changed default max coefficient for big-M constraint to be initial from 1e6 to 1e9 - changed default value of gomory cut separation parameter "separating/gomory/maxrank" from 0 to 3, to take also gomory cuts that could not be scaled to integral coefficients, with maximal rank 3 into account - new parameters "constraints/{linear,knapsack}/detectcutoffbound" and "constraints/{linear,knapsack}/detectlowerbound" to enable/disable detection of constraint parallel to the objective function that will add an cutoffbound or an lowerbound respectively, and these constraints will be prevented from entering the LP - new parameters "constraints/linear/detectpartialobjective" to enable/disable the detection of sub-equations of the objective function core: - added presolve.{c,h} which should be used for all preprocessing mechanisms executed from within SCIP, corresponding to solve.{c,h}, and also for presprocessing methods which can be called from different plugins or from the core to avoid code doubling - the main output routine of message.c (bufferMessage - now handleMessage) has been rewritten: it now does not need a copy of the string to be output anymore, which makes the code much simpler (and also faster); it is passed a function pointer to the output function and uses it to directly output the (buffered) messages - extended and corrected dual feasibility checks for LP solution (controlled by parameter "lp/checkdualfeas") - return error if variable should be fixed to infinity after presolving (LP-solvers do not handle this consistently) - LPI files (lpi*.[h|c]) all moved from src/scip to src/lpi Makefile: - default flag for ZIMPL is now "auto", which means that it is built if and only if GMP is available (GMP=true) - fixed make install for older Mac systems where install command does not have option -t - dropped support for Ipopt < 3.10 misc: - added SCIPdebugCheckConss() to the debugging mechanism and therefor created a SCIP_SOL (in original space) in debug.c SCIP version 3.0.2 ================== fixed bugs: - fixed assert in solve.c with branched status and LP reached the objective limit - fixed bug in cons_bounddisjunction with satisfied literal of multi-aggregated variable - fixed bug in upgrade method of cons_soc - fixed bug in heur_oneopt.c and heur_clique.c which was caused by side-effects when calling SCIPconstructLP(); when adding new variables in this method (e.g. adding new variables needed for a relaxation), this changes the variables array of SCIP - fixed issue with negated variables in cons_xor.c - fixed issues with ungraceful termination when encountering unsupported expression operands in AMPL interface - fixed bug in cons_xor.c calling method on null pointer row - fixed bug in cons_abspower.c handling infinity values in propagation - fixed bug in parsing bounds from CIP-files - fixed problem that diving did not save status for infeasible LPs - fixed several bugs in propagation of cons_xor: need to take integral variables into account - fixed several asserts in cons_xor presolving - fixed fieldtypes in sorting template - fixed bug concerning the userinterrupt flag, which was not reset - fixed potential performance issue with tree depth always assumed to be zero when propagating in probing mode - fixed memory leak in lp.c (probably never occurred so far since array was not used) - fixed bug in reader_gms.c w.r.t. writing nonlinear expressions with polynomials with constants - fixed bug in sepa_zerohalf.c not copying the displays to the subscip, but still changing a display parameter there - fixed bug in SCIPlpComputeRelIntPoint() with wrong iteration limit and with wrong recompution - fixed iteration limit determination in sepa_closecuts - fixed bug in prop_vbound w.r.t. creation of variables during the search - fixed bug using a too hard comparison on the objective-infeasible-decision in constraint enforcement - fixed possible cycling in enforcement of nonlinear constraints due to too early removal of newly added cuts from LP - fixed solution collection when counting solutions - fixed bug wrongly removing constraints locally while counting - fixed bug in Undercover with "pseudo-"quadratic constraints - fixed bug with quadratic constraints not being upgraded - fixed bug with storing original solutions - fixed bug in cons_and.c when a constraint was not correctly propagated which led to wrong dual-presolve reductions - fixed bugs in cons_bivariate.c when the nonlinear function is not differentiable on the boundary of the domain - fixed bug in cons_indicator.c:SCIPmakeIndicatorFeasible() with handling fixed variables - fixed bug in sepa_zerohalf.c where the maxcuts(root) parameters led to an invalid memory allocation call - fixed bug in sepa_closecuts: need to make sure that variable values of separation point satisfy bounds - fixed bug in intervalarith.c: bivariate quad. equations may have been solved wrongly if second variable is unbounded - fixed bug in cons_integral: need to make sure that all implicit integer variables are integral when a solution is checked - fixed bug in cons_abspower: wrong infinity check when propagating bounds - fixed bugs in sepa_oddcylce: number of arcs have to be adjusted, handle implicit binary variables, fixed bug in heuristic separation method, fixed asserts - fixed bugs with freeing C++ object data for problem and variables - fixed wrong bound calculation in sepa_rapidlearning - fixed bug with infinite multi-aggregation constants - fixed bug that old LP size was not updated for deadend if no LP was solved - fixed bug that removing reverse implication did not reset closestvblpcount - fixed bug that the number aggregated variables were not counted in presol_inttobinary.c - fixed bug that duplicate solutions stopped copying of solutions to original solution candidate store - forbid branching on variables with huge bounds; such huge values cannot be enumerated with fixed precision floating point arithmetics - fixed bug in backward propagation of linear expressions in expression graph - fixed bug that Ipopt's error message was not fully shown due to exiting before the message handler buffer was emptied - fixed 'bug' when reading a mps formated file with a missing bound in the bound section - unlinking a solution now copies solution values smaller than SCIPepsilon() avoiding some feasible solution in the transformed problem to be infeasible in the original problem - allow to add columns (rows) with nonzero indices beyond current number of rows (columns) in SoPlex LPi - fixed bug in presol_domcol: locks are now checked to see whether rounding was forbidden for a variable - updated get.ASL script to cope with broken ftp access to netlib server features: - can now output the solutions in the solution pool in the interactive shell - updated Mosek interface to compile with Mosek 7, too - reading erroneous CIP files can now output some indication of syntax errors - can now run splint on core files - cons_xor now uses the integral variable in propagation - allowed to switch on/off the solution debugging performance improvements: - improved SCIPlpiAdd{Cols,Rows}() in SoPlex LPi interface: - remove problematic function cons_indicator:SCIPsetSlackVarIndicator() - added methods SCIPmarkColNotRemovableLocal() and SCIPmarkRowNotRemovableLocal() to forbid removal of an column/row from the LP in the current node - added method SCIPmessageVPrintError() SCIP version 3.0.1 ================== fixed bugs: - fixed bug when adding linear constraints with non active variables in solving process, during propagation this resulted in changing the row, which is not possible for unmodifiable constraints/locked rows - fixed bug in copying nonlinear constraints during presolve (nonlinear part was not copied) - fixed issue with deleting varbound constraints in case the bound change was not applied - fixed small issue in pseudo objective propagator w.r.t. propagating the lower bound globally - fixed issue with applying the effective root depth during the search - fixed bugs in parsing dis-/conjunctive constraints - fixed minor bug in conjunctive constraint handler printing wrong constraint - fixed bug in disjunctive constraint handler when enforcing a constraint - fixed bug with handling of empty logicor and bounddisjunction constraints - fixed bug which disabled iteration limit in SCIPlpSolveAndEval() - fixed bug in cumulative constraint handler w.r.t. getting active variables - fixed bug concerning usage of dualbound and lowerbound - fixed bug trying to color probing nodes, which are not added to the vbc output anymore - fixed bug in sorting template - fixed bug in cons_orbitope: in rare cases one cannot repropagate - fixed behaviour change of indicator constraint handler when solving another instance after solving one using the interactive shell - fixed bug of wrong result code in propagation in prop_genvbound.c - fixed several issues in cumulative constraint handler - fixed issue in cumulative constraint and separation - fixed feasibility decision bug when replacing inactive variables by their active counterparts, which might change the redundancy status of a bounddisjunction constraint due to numerics - fixed numerical bug adding a relaxed bound for conflict analysis in cons_varbound - fixed bug in cumulative constraint handler concerning conflict analysis - fixed bug in CppAD when using signpower functions with expression pointers that do not fit into an unsigned int - fixed issue in cumulative constraint w.r.t. separation - fixed issue in cumulative constraint w.r.t. conflict analysis - fixed numerical bug in conflict.c relaxing bounds while keeping an infeasibility proof - fixed wrong solving status (OPTIMAL) in case an unbounded solution was provided or found by heuristic before presolve - fixed wrong basis rstat values in CPLEX LPI - fixed bug leading to removing a ranged row parallel to the objective function, although one of the sides was still needed - fixed a bug correcting the binvarssorted flag in cons_linear.c - fixed bug in cons_varbound.c not resolving multi-aggregated variables - fixed bug when sorting knapsack constraints with the same weights - ensure consistency of LP bounds during OBBT diving, i.e., that lower <= upper holds exactly - fixed numerical bug in conflict analysis of genvbounds propagator - relaxed assert in SCIPvarCh{Lb,Ub}{Global,Local} that new bound must be tighter to feastol - fixed bug in heur_subnlp running with tightened tolerances: sumepsilon must be tightened like feastol and epsilon - fixed contra-intuitive behavior when using SCIP with objective limits and solution limit at the same time; SCIP now only stops when sufficiently many solutions better than the objective limit have been found - fixed bug when adding binary implications with non-vartype binary variables - fixed bug resulting in trying to delete an upgraded linear constraint a second time in exitpre callback - fixed bug in nlp diving heuristic for fractional variables with values slightly outside of their domain - set lpsolstat to SCIP_LPSOLSTAT_NOTSOLVED in SCIPchg{Lp,Dual}feastol - use tighter dual feasibility tolerance for LPs solved during optimization-based bound tightening - fixed bug with LP not being flushed after bound changes on columns that are not in the LPI - methods SCIPlpiIs{PrimalFeasible,DualFeasible,DualUnbounded}() in SoPlex LPi now check that the LP is not perturbed, which may happen when stopping due to iteration or time limit - fixed inconsistencies between methods SCIPlpiIs{PrimalFeasible,DualFeasible,Optimal,...} in SoPlex LPi - fixed bug adding binary implications on binary variables with type != SCIP_VARTYPE_BINARY - fixed bug concerning different tolerances for reached objective limit in case of pricing with fastmip - fixed bug with unflushed LP arising from global bound changes in strong branching performance improvements: - also copying active tight cuts from the delayed cut pool when calling SCIPcopyCuts() - sort genvbounds only when root node is finished; apply more often features: - added delayed cutpool which only gets separated if the sepastore is empty after a separation round - sepa_cgmip can now take the objective row into account - added possibility to run clang compiler interface: - fixed spelling in the method name SCIPgmlWriteClosing() - new method SCIPgetNLimSolsFound() to get number of solutions that respect the objective limit - when using an objective limit, heuristic characters are not displayed any longer for worse solutions - statistics now include output on number of solutions that respect objective limit SCIP version 3.0.0 ================== datastructure: - new data structure for binary trees (SCIP_BT and SCIP_BTNODE in pub_misc.h) - renamed data structure SCIP_STAIRMAP to SCIP_PROFILE - renamed data structure SPARSESOLUTION to SCIP_SPARSESOL and moved it from cons_countsols.h to struct_misc.h interface - new method SCIPisConflictAnalysisApplicable() which return FALSE is the conflict will not runs; can be used to avoid unnecessary initialization of the conflict analysis - the methods SCIPsortedvecInsert*() have an additional parameter which can be used to receive the position where the new element was inserted, if this is not of interest a NULL pointer can be given - SCIPcolGetStrongbranchLPAge(), SCIPgetVarStrongbranchLPAge(), SCIPgetNLPs(), SCIPgetNPrimalLPs(), SCIPgetNDualLPs(), SCIPgetNBarrierLPs(), SCIPgetNResolveLPs(), SCIPgetNPrimalResolveLPs(), SCIPgetNDualResolveLPs(), SCIPgetNNodeLPs(), SCIPgetNNodeInitLPs(), SCIPgetNDivingLPs(), SCIPgetNStrongbranchs(), SCIPgetNRootStrongbranchs() now return a longint instead of an integer - added propagation timing as parameter "proptiming" to SCIP_DECL_CONSPROP() and SCIP_DECL_PROPEXEC() as well as to the corresponding C++ wrapper classes - new method SCIPpropIsPresolDelayed() which return if a propagator is delay during presolving - changed parameters of function SCIPpropagateCutoffboundVar() in prop_pseudoobj.{c,h} - SCIPcomputeCoverUndercover() now has an additional parameter coverbd - the code in src/dijkstra and src/xml has been changed to (increasingly) conform to the SCIP coding style; all function (and variable) names have been changed (do not contain "_" anymore). - rename SCIPvarGetBestBound() to SCIPvarGetBestBoundLocal() - rename SCIPvarGetWorstBound() to SCIPvarGetWorstBoundLocal() - new methods SCIPvarGetBestBoundGlobal() to SCIPvarGetWorstBoundGlobal() - new method SCIPcalcBinomCoef() in pub_misc.h and misc.c which calculates a binomial coefficient up to 33 over 16 - new method SCIPheurPassSolAddSol() in heur_trysol.c; solution which are passed via this method are just added without any feasibility check - new method SCIPvarsGetProbvar() in pub_var.h and var.c, which returns for a given array of variables the active, fixed or multiaggregated representation - new method SCIPgetGlobalPseudoObjval() which returns the global pseudo objective value which is all variables set to their best (w.r.t. the objective function) global bound - new method SCIPhashtableClear() which removes all elements of a hash table - new callback methods in constraint handler SCIP_DECL_CONSGETVARS and SCIP_DECL_CONSGETNVARS which are optional and returns for a constraint the involved variables and the number of variables - new methods SCIPgetConsVars() and SCIPgetConsNVars() which return for a given constraint the involved variables and the number of variables if the corresponding constraint supports this (optional) callbacks - new method SCIPisUpdateUnreliable() to check whether an iteratively updated value should be recomputed from scratch (e.g., for activities; uses new parameter misc/num_recompfac) - new method SCIPgetActiveVars() in scip.{h,c}, which returns for a given array of variables the active counterparts - added method SCIPgetNObjVars() which returns the number of variables which have a non-zero objective coefficient - new method SCIPupdateCutoffbound() which can be used to pass a cutoff bound - new method SCIPchgCapacityKnapsack() which can be used to change the capacity of a knapsack constraint - new method SCIPconsIsAdded() which returns whether a constraint was already added to a SCIP instance - new method SCIPisPresolveFinished() which returns whether the presolving process would be stopped after the current presolving round, given no further reductions will be found; can be used to ensure that a presolver is called very late - new methods SCIPenableVarHistory() and SCIPdisableVarHistory() which can be used to turn off and on the collection of variables statistics which is used for example for branching - allowed to start diving mode even if LP is not flushed, not solved, or not solved to optimality - changed the message handler system within SCIP heavily such that it is thread save - the follwing methods additionally need the SCIP pointer as parameter to make the output thread save: SCIPprintVersion(), SCIPsetMessagehdlr(), SCIPgetMessagehdlr(), and SCIPwarningMessage() - the following methods additionally need a message handler: SCIPdispLongint(), SCIPdispInt(), SCIPdispTime(), all message handler methods (see pub_message.h), SCIPhashtablePrintStatistics(), SCIPhashmapPrintStatistics(), SCIPlpiCreate() - new method SCIPmessagehdlrCapture() which captures a given message handler (increases number of uses) - new method SCIPmessagehdlrRelease() which releases and possibly frees a given message handler (decreases number of uses) - new method SCIPsetMessagehdlrLogfile() which can be used to write into a log file - new method SCIPsetMessagehdlrQuiet() which can be used to turn the screen output on and off - removed method SCIPcreateMesshdlr(), please use SCIPmessagehdlrCreate() (see pub_message.c) - removed method SCIPfreeMesshdlr(), please use SCIPmessagehdlrRelease() (see pub_message.c) - the error messages are not handled via the message handler anymore; per default the error message a written to stderr - the error printing method can be replaced using the method SCIPmessageSetErrorPrinting(); the default error message printing can be recoverd via SCIPmessageSetErrorPrintingDefault() (see pub_message.h) - method SCIPprintError() does not need the file stream anymore. The error is written via the error message callback. - since the error messages are not handled via the messages handler anymore, the parameter list of SCIPmessagehdlrCreate() changes; see pub_message.h and type_message.h. - new NLPI callback SCIP_DECL_NLPISETMESSAGEHDLR() to set message handler in NLP solver interfaces - new parameter in SCIPcopyPlugins() to indicate whether the message handler from the source SCIP should be passed to the target SCIP (only the pointer is copied and the usage counter of the message handler is increased) - removed SCIPparamSetBool(), please use SCIPchgBoolParam() - removed SCIPparamSetInt(), please use SCIPchgIntParam() - removed SCIPparamSetLongint(), please use SCIPchgLongintParam() - removed SCIPparamSetReal(), please use SCIPchgRealParam() - removed SCIPparamSetChar(), please use SCIPchgCharParam() - removed SCIPparamSetString(), please use SCIPchgStringParam() - remove SCIPcolPrint() and SCIProwPrint(), please use SCIPprintCol() SCIPprintRow() see scip.h - new method SCIPmemccpy() in pub_misc.h and misc.c which copies either a specified number of charcters of a source string to a destination string or until it hits a stoping character - new method SCIPchgCutoffboundDive() to change the cutoffbound in diving mode - added forgotten implementation of SCIPfreeMemorySize(), SCIPfreeMemorySizeNull() in scip.h and BMSfreeMemorySize(), BMSfreeMemorySizeNull() in memory.h - new methods BMSmoveMemory(), BMSmoveMemoryArray(), BMSmoveMemorySize() and corresponding BMSmoveMemory_call() in memory.{h,c} too move memory elements - added public wrapper functions for calling constraint handler callback methods for a single constraint: SCIPactiveCons(), SCIPdeactiveCons(), SCIPinitlpCons(), SCIPsepalpCons(), SCIPsepasolCons(), SCIPpropCons(), SCIPrespropCons(), SCIPenfopsCons(), SCIPenfolpCons() - added new stages SCIP_STAGE_INITPRESOLVE, SCIP_STAGE_EXITPRESOLVE, and SCIP_STAGE_FREE; renamed SCIP_STAGE_FREESOLVE to SCIP_STAGE_EXITSOLVE - new method SCIPisHugeValue() to check whether a value is huge and should be handled separately from other values (e.g., in activity computations), and SCIPgetHugeValue() to get the smallest value counting as huge - new methods SCIPaddConflictRelaxedLb(), SCIPaddConflictRelaxedUb(), and SCIPaddConflictRelaxedBd(); these methods can be used to give for a bound change which is part of an explanation a relaxed bound; this means the relaxed bound is already efficient to be part of a valid explanation - new method SCIPisConflictVarUsed() returns TRUE if the given bound change is already part of the conflict set; that is the bound change is redundant; - new methods SCIPgetConflictVarLb() and SCIPgetConflictVarUb() returning the lower/upper bound of the given variable within the current active conflict set - the resolve propagation methods for the constraint handler and propagator getting a new parameter called relaxedbd; explaining/resolving this relaxed bound is sufficient - new method SCIPbranchVarHole() which branches a variable w.r.t. a given domain hole - default integer comparer SCIPsortCompInt() (see pub_misc.h) - renamed SCIPstairmap*Core() to SCIPstairmap*Stair() - tcliqueMaxClique has an additional parameter to store the number of used branch-and-bound nodes - new methods SCIPfixParam() and SCIPunfixParam() to fix and unfix a parameter, respectively; the fixing status of a parameter can be requested by SCIPparamIsFixed(); in the interactive shell, this can be done with 'fix' (instead of 'set'), e.g., "fix heuristics rens freq TRUE"; - added new method SCIPvarGetAggregatedObj() which computes for a (not active) variable the corresponding objective value - renamed parameter SCRDIR of "make testgams" to CLIENTTMPDIR and changed its default to "/tmp" - renamed SCIPmarkNonlinearitiesPresent() to SCIPenableNLP(), removed SCIPmarkContinuousNonlinearitiesPresent(), renamed SCIPhasContinuousNonlinearitiesPresent() to SCIPhasNLPContinuousNonlinearity() and allow call only during initsolve and solve, renamed SCIPhasNonlinearitiesPresent() to SCIPisNLPEnabled() - new method SCIPsolIsOriginal() that returns whether a solution is defined on the original variables - SoPlex LPI supports setting of SCIP_LPPAR_DUALFEASTOL when using SoPlex version 1.6.0.5 and higher - new method SCIPsetBasePointClosecuts() to set the base point for close cut separation - method SCIPvarGetProbvarSum() is not public anymore, use SCIPgetProbvarSum() instead; also method SCIPexprtreeRemoveFixedVars() is not public anymore - all objscip *.h file now use the default SCIP interface macros (this should avoid errors when changing the interface) - added "basic" inclusion methods which have only fundamental data of the plug-ins as arguments; added setter functions for all non-fundamental callbacks of the plug-ins; the plug-in types with basic inclusion functions are: readers, constraint handlers, conflict handlers, presolvers, propagators, heuristics, separators, relaxation handlers, branching rules, node selectors, and pricers - added basic creation methods for all constraint handlers - added basic creation methods SCIPcreateVarBasic() and SCIPcreateProbBasic() and setter functions for non-fundamental callbacks of variables and problems. - new functions SCIPcreateEmptyRowCons(), SCIPcreateEmptyRowSepa(), SCIPcreateRowCons(), and SCIPcreateRowSepa() that allow to set the originating constraint handler or separator of a row respectively; this is, for instance, needed for statistics on the number of applied cuts. If rows are created outside a constraint handler or separator use SCIPcreateRowUnspec() and SCIPcreateEmptyRowUnspec(). The use of SCIPcreateEmptyRow() and SCIPcreateRow() is deprecated; - new functions SCIProwGetOrigintype and SCIProwGetOriginCons SCIProwGetOriginSepa to obtain the originator that created a row - new functions SCIPconshdlrGetNCutsApplied() in pub_cons.h to get the number of cuts applied to the lp - new function SCIPconshdlrIncNAppliedCuts() in cons.h to increase the number of applied cuts (used by sepastore.c) - new LPI method SCIPlpiGetObjsen() to query objective sense - new method SCIPgetVarImplRedcost() which returns the implied reduced costs - new methods SCIPvarGetBestRootSol(), SCIPvarGetBestRootRedcost(), SCIPvarGetBestRootLPObjval() which return the best combination for a variable w.r.t. root solution value, root LP objective value, and root reduced cost - removed method SCIPvarGetRootRedcost() replaced by SCIPvarGetBestRootRedcost() - SCIPprintCons() does not print termination symbol ";\n" anymore; if wanted, use SCIPinfoMessage() to print ";\n" manually - new method SCIPhaveVarsCommonClique() in scip.{h,c}, to check for common clique information on two given variables - forbid problem modifications in SCIP_STAGE_{INIT,EXIT}PRESOLVE - new parameter numerics/lpfeastol for primal feasibility tolerance used in LP solver - new macro SCIPdebugPrintCons() to print constraint only if SCIP_DEBUG flag is set - new method SCIPchgVarName() and SCIPchgConsName() which can be used to change name of variables and constraints in problem creation stage - new parameter in SCIPcopy() to indicate whether the message handler from the source SCIP should be passed to the target SCIP (only the pointer is copied and the usage counter of the message handler is increased), in multi theaded enviroment this parameter needs to be set to FALSE - new method for SCIP_SPARSESOL usage, SCIPsparseSolCreate(), SCIPsparseSolFree(), SCIPsparseSolGetVars(), SCIPsparseSolGetNVars(), SCIPsparseSolGetLbs(), SCIPsparseSolGetUbs() in (pub_)misc.{c,h} - renamed SCIPgetCountedSparseSolutions() to SCIPgetCountedSparseSols() in cons_countsols.{c,h} - SCIPcomputeLPRelIntPoint() takes two new arguments giving a time and iteration limit - added a SCIP_CONS* parameter to SCIPcreateConsDisjunction() which can represent the linear relaxation of the whole disjunction constraint as a conjunction constraint, or NULL performance improvements: - improved scaling of linear constraints, linear constraints with integral variables will now be scale with 1e+06/MAX(maximal absolute coefficient, 1.0) instead of 1e+03/MAX(maximal absolute coefficient, 1.0); if all coefficients are in absolute value equal they will be scaled by that - if probing reached the end of all variables it will restart the probing cycle correctly - improved intdiving heuristic by activating backtracking to a different fixing value - improved scaling by choosing the smallest scaler - if first root lp is solved and the optimality is rejected by SCIP, there won't be an unnecessary solving of the lp from scratch again - automatically turn off separation in sepa_oddcycle if it was too unsuccessful within the last calls - use faster Dijkstra variants in sepa_oddcycle - improved pseudo objective propagator - streamlined initlp functions in cons_indicator, cons_sos1, cons_sos2 (add rows only if needed) - added clique presolving for and-constraints, which checks if two operands or one operand and the resultant are in a clique and then fixes the resultant to 0 and in the former case we can delete the and-constraint too - improved probing by ordering the variables differently and applying the one-branch before the zero-branch - improved lp-, mps-, opb-reading time - improved time used for adding implications - improved tcliquegraphAddImplicsVars() in sepa_clique.c to faster add possible variables - added parameters mincoveredrel and mincoveredabs to heur_undercover to only run if problem is sufficiently nonlinear - heur_undercover treats indicator constraints as nonlinear and fixes the binary variable for linearization - speed up in linear constraint handler replacing aggregated variables - speed up in SCIPboolarrayExtend() in misc.c replacing a for loop with BMSmoveMemoryArray() call - speed up mps reader asking parameters only once - speed up in var.c changing some recursive calls into iterative calls and reducing the number of VARFIX event that are thrown for fixation, aggregation or multi-aggregations - changed emphasis settings: knapsack disaggregation is now allowed in fast presolving, CG-MIP separator disabled in aggressive separation - revised reduced cost propagator - increased performance in SCIPcliqueAddVar(), adding a variable to a clique - tighten primal and dual feasibility tolerances independently if they are not reached in LP solving - when all nonlinearities have been fixed and the number of nonfixed variables is 1 in cons_nonlinear/cons_quadratic/ cons_bivariate, handle it by a bound change instead of adding a linear constraint - removed 'targetscip' parameter from SCIPconvertCutsToConss(), now this function can only convert cuts on one instance, otherwise use SCIPcopyCuts() - added 'ncutsadded' parameter to SCIPcopyCuts() to be able to store the number of copied/converted cuts - new method SCIPpermuteIntArray() in pub_misc.h and misc.c for permuting an integer array plugins: - added new presolver convertinttobin, which converts bounded integer variables to their binary representation, e.g. for integer variable 0 <= x <= 10 the binary variables y0, y1, y2, and y3 are created, such that 1 y0 + 2 y1 + 4 y2 + 8 y3 <= 10 and x = 1 y0 + 2 y1 + 4 y2 + 8 y3 - added nlpdiving heuristic that comprises several diving heuristics using an NLP relaxation - added new presolver gateextraction, which tries to find and-gates/constraints which are linearized e.g. (x + y + z >= 1, x + y <= 1 and x + z <= 1 => x == AND(~y,~z)), in special cases it also detects set-partitioning constraints e.g. (x + y + z >= 1, x + y <= 1, x + z <= 1 and y + z <= 1 => x + y + z == 1)); gate-extractor is also able to detect logicor constraints and set-packing/-partitioning constraints with the same variables, to upgrade these both constraints to a set-partitioning constraint - added reader for MI(NL)Ps in OSiL (Optimization Services Instance Language) format - added new presolver components, that searches for independent components in the problem structure and solves these components as sub-SCIPs when they are small enough (per default <= 20 discrete variables, nodelimit of 10000) - added new presolver domcol that looks for dominated columns in a MIP and tries to fix them - added zeroobj heuristic that solves a copy of the problem without an objective function and with quite strict limits on the number of nodes and LP iterations - complete reworking of the vbounds propagator: it now takes into account variable bounds, cliques, and implications, stores bounds of variables which were changed, and performs a forward propagation from these bounds, i.e., tries to derive new bounds for other variables; during propagation, bound changes are propagated in an (almost) topological order fixed bugs: - fixed potential bugs in shiftandpropagate heuristic concerning the transformation update of a variable with free status - fixed minor bugs with respect to counting generated and lifted cuts in sepa_oddcycle - fixed bug in heur_zirounding with computation of up/downslacks - fixed bug in cons_linear w.r.t recalculation of unreliable activities - fixed bug with strong branching with the LP status for conflict analysis - fixed bug in scip.c adding a constraint in SCIPgetConsCopy() to the constraint hashmap - fixed bug in shiftandpropagate w.r.t. SCIPconstructLP() which can have the side effect that variables are created - fixed bug w.r.t. adding a value to the objective offset of the transformed problem - fixed bug in solve.c, applied bounding for the initial lp was only done if root-lp-solution was valid but another solution could also have been added - fixed bug in cons_linear concerning huge activity values: besides infinite contributions, we now also treat huge contributions separately, count their occurences in a constraint, and provide a relaxed activity value - fixed bug in mutation heuristic with unnecessary aborts due to a wrong memory limit - fixed bug in Cplex LPI: after running simplex, solisbasic flag was always true, which might be wrong if Cplex hit a time limit - fixed bug in SCIP probing mode with cleared LPI state but solved LP - fixed bug in SoPlex LPI where objective sense was not correct after reading LP from file in SCIPlpiReadLP() - fixed potential bug in fix-and-infer heuristic with variables being fixed to infinite value - fixed bug in diving heuristics with variables being fixed to values outside their domain - method SCIPvarGetProbvarSum() (and thus also SCIPgetProbvarSum()) returns +/-infinity if the variable resolves to a variable fixed to +/-infinity (depending on the sign of the scalar) but does not multiply with the scalar, anymore - primal solutions with infinite objective value are now automatically discarded - better handling of infinite solution values for aggregated and negated variables - fixed bug that disabled multi-aggregation of two integer or implicit integer variables - fixed bug in sol.c with requesting values of transformed variables in original solution; previously this had only been handled in SCIPgetSolVal(), now the handling has been moved to SCIPsolGetVal() - fixed bug in cons_xor.c parsing a constraint - fixed wrong assert in feasibility pump stage 3 - fixed bug in simple rounding heuristic with column generation for variables with strictly positive lower bound - made Octane heuristic numerically more stable to avoid asserts being caused by cancellation - fixed bug in mutation heuristic with variables being fixed to infinite values - fixed several bugs writing an mps file in the reader_mps.c, e.g. writing fixed variables which are not (yet) removed and writing integer variables even with an objective value of 0, if they only exist in non-linear constraints - fixed bug in sepa_clique.c, could not handle only empty cliques, that were not removed - all plugins that solve sub-SCIPs now do not stop the whole solution process if there has been an error - fixed assert with LPI=none (need to count rows/cols in lpi_none) - do not run heur_shiftandpropagate if there is no LP - fixed count of propagations in cons_indicator and only try to propagate if variables are not yet fixed - fixed some bugs in cons_disjunction.c (wrong assert, forgotten deletion of constraint, wrong SCIPreleaseCons() call) - fixed bug in cip reader, wrong use of SCIPstrtok() parameters: - new parameter <presolving/convertinttobin/maxdomainsize> by default is set to SCIP_LONGINT_MAX, which deternmines the domainsize for which integers are converted to their binary representation - new parameter <presolving/convertinttobin/onlypoweroftwo> by default is set to FALSE, that parameter allows you to only convert integer variables with a domainsize of 2^p - 1 to their binary representation - new parameter <presolving/convertinttobin/samelocksinbothdirections> by default is set to FALSE, that parameter allows you to convert only integer variables to their binary representation, which have the same amount of up- and downlocks - branching/fullstrong/reevalage changed from an integer to a longint parameter - new parameter for changing the timingmask for calling the propagtion method of all propagator plugins propagating/%s/timingmask and all constraint plugins constraints/%s/timingmask - new parameter constraints/indicator/dualreductions to enable dual presolving/propagation steps - new parameters constraints/indicator/{sepacouplingcuts,sepacouplinglocal} to enable separation of (local) cuts - new parameters constraints/indicator/{maxsepacuts,maxsepacutsroot} to restrict the number of separated cuts - new parameter separating/oddcycle/maxunsucessfull to automatically turn off separation - new parameter numerics/recompfac which denotes the factor, by which the absolute of an iteratively updated value has to be decreased in order to recompute the value from scratch - new parameters separating/cgmip/{minnodelimit,maxnodelimit} to determine node limit. Removed parameter separating/cgmip/nodelimit. - new parameter <presolving/gateextraction/onlysetpart> by default is set to FALSE, that parameter allows you to only extract set-partitioning and no and-constraints - new parameter oncepernode in Rounding and Simple Rounding heuristic - new parameter <numerics/hugeval> that defines the smalles value counting as huge (see new method SCIPisHugeValue()) - new parameter <limits/totalnodes> that allows to stop at the correct node if a restart occured; therefor the new SCIP_STATUS_TOTALNODELIMIT is added - new parameter propagating/probing/maxdepth to set the maximal depth until the probing propagation is executed - new parameter <presolving/gateextraction/searchequations> by default is set to TRUE, that parameter allows you to search for logicor constraints and set-packing/-partitioning constraints with same variables - new parameter <presolving/gateextraction/sorting> by default is set to 1, that parameter determines if you want to try to extract big-gates(-1) or small-gates(1) at first by ordering bigger/smaller logicor constraint up front, or use them as they are (0) - new parameter <reading/cnfreader/useobj> to state whether an artificial objective, depending on the number of clauses a variable appears in, should be used, by default set to FALSE, old default behavior of reader corresponds to TRUE - new parameter <constraints/and/dualpresolving> by default set to TRUE, enabling dual-presolving on and-constraints - new parameter <misc/transorigsols> by default set to TRUE, that switches whether SCIP tries to transfer original solutions into the transformed space (in initsol and if a heuristic adds an original solution during solving) - new parameters lp/{rootiterlim,iterlim} to set a limit on the LP iterations spend in the initial root LP and each LP resolve, respectively - removed superfluous parameter <separating/closecuts/separootonly> - removed <constraints/quadratic/defaultbound> - new parameters constraints/setppc/cliquelifting, constraints/setppc/addvariablesascliques, constraints/setppc/cliqueshrinking, first for enabling/disabling the clique lifting algorithm in cons_setppc.c, second parameter is for trying to create extra clique constraints in lifting algorithm, third parameter is for trying to decrease the number of variable in a clique constraint in the lifting algorithm - new parameter <separating/closecuts/maxlpiterfactor> for iteration limit in relative interior point computation features: - SCIPcomputeLPRelIntPoint with normtype='s' now uses homogenized LP for computing rel.int. point too and allow to set relaxrows = FALSE - the check script now recognizes MIQCP and MINLP instances - new column showing the pseudo objective value - time for initpre and exitpre methods is now also measured in presolving time - digraph structure added to misc.c and pub_misc.h that can be used to handle directed graphs, compute undirected components in the graph, and sort these components (almost) topologically - beta-version of a MATLAB interface can be found under interfaces/matlab - SCIP does now print an info message when the root LP could not be solved or is unbounded - added setup timer to all plugins and therefor SCIP<plugin-type>GetSetupTime() methods in all pub_plugin-type.h to ask for this time (, e.g. SCIPeventhdlrGetSetupTime() in pub_event.h) - added counter and clock for SCIPcopy() calls - better handling of memory limits, in particular for large problems - estimate memory consumption for sub-SCIP and do not copy them if close to memory limit - number of presolving calls of plugins is counted and displayed in the statistics, can be accessed via SCIPpresolGetNCalls() and SCIP<prop/conshdlr>getNPresolCalls() - new methods SCIPhashGetKeyStandard() which returns the element itself as the key, SCIPhashKeyEqPtr(), SCIPhashKeyValPtr() which do the hash-comparison/-conversion on a pointer in pub_misc.h - correct initialization of steepest edge weights with SoPlex 1.6.0.4 - CNF reader now creates feasibility instances per default, usage of an objective has to be set by a parameter - make test now also checks instances in wbo, cnf, osil, and fzn format - parameters can now be fixed, which means that their value cannot be changed unless they are unfixed, first; the fixing status of a parameter is copied to sub-SCIPs, which allows to ensure that certain parameters are also not changed when, e.g., heuristics change emphasis settings or also specific parameters - added dual presolving for and-constraints - the statistics shows for a branching rule the number of calls for LP, extern, and pseudo candidates - new NLPI parameter SCIP_NLPPAR_FASTFAIL to enable convergence checks in NLP solver to stop early on seemingly difficult instances (no guarantees) - new switch SCIP_STATISTIC and new macros SCIPstatisticMessage(), SCIPstatisticPrintf() and SCIPstatistic() to output statistic and execute code lines which are only needed therefor. Works as SCIP_DEBUG and SCIPdebugXyz() - new GML(Graph Modeling Language) methods SCIPgmlWriteOpening(), SCIPgmlWriteCosing(), SCIPgmlWriteArc(), SCIPgmlWriteEdge(), SCIPgmlWriteNode() wo write to a given GML file - automatic transfer of original solutions (e.g., provided by the user, from solution pool, after restart, from heuristic adding original solution during solve) to the transformed space (might fail due to, e.g., dual fixings) - new constraint handler "superindicator" for indicator constraints with slack constraints of arbitrary type - added possibility to use GUBs for lifting knapsack cuts (disabled) - added statistics on the number of cuts/rows that have actually been applied to the lp for each constraint handler and separator; use SCIPcreate(Empty)RowCons() and SCIPcreate(Empty)RowSepa() to support the statistics. - implemented first clique lifting procedure in cons_setppc.c (by default is off) - oneopt can now be called before presolving - beta-version of a AMPL interface can be found under interfaces/ampl - the conjunction and disjunction constraint handlers are now able to parse their CIP output format - added a presolving step in the disjunctive constraint handler, removing disjunction, where a sub-constraint was deleted, which means this sub-constraint is redundant, which again means it is always TRUE or will be enforced by another constraint - added pre- and post-conditions in doxygen documentation for all methods of scip.<c,h> Makefile - CppAD source code is now distributed with SCIP (src/cppad), so that lib/cppad is not used anymore; the default for EXPRINT has changed from none to cppad SCIP version 2.1.2 ================== fixed bugs: - fixed bug in SCIPsolveKnapsackExactly() - fixed bug in varAddTransitiveImplic() in var.c, when adding implications on special aggregated, namely negated, variables - fixed bug in cons_quadratic where bounds on activity of quadratic term were not always invalidated when quadratic variables were removed - 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 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 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 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 heur_oneopt.c which forgot to check LP rows if local rows are present - fixed bug in SCIPsolveKnapsackExactly(), trying to allocate too much memory which led to an overflow and later to a segmentation fault - fixed bug in cons_xor.c which did not copy the artificial integer variable (used for the lp relaxation) - fixed bug in sepa_rapidlearning, carrying on the optimization process, when already solved 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 SCIP version 2.1.1 ================== performance improvements: - revised pseudo objective propagator - 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 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. fixed bugs: - fixed bug in reader_mps.c: INTEND marker is now also written, if COLUMNS section ends with non-continous variables - fixed numeric issue in aggregations - fixed pseudo cost computation - pseudo objective propagator does not propagate it active pricers are present - 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 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 bug in cons_orbitope with calling conflict analysis - fixed bug in flatzinc reader w.r.t. boolean expressions - fixed bug in nlpi_oracle w.r.t. changing linear coefs in a NLP constraint - fixed compilation issues with negate() function in intervalarith.c on exotic platforms - gams writer now also substitutes $-sign from variable/equation names - fixed bug in SCIPsortedvecDelPos...() templates - fixed bug in heur_shiftandpropagate.c concerning the treatment of unbounded variables - workaround for trying to add variable bounds with to small coefficients parameters: - changed parameter "propagating/pseudoobj/maxcands" to "propagating/pseudoobj/minuseless" (see prop_pseudoobj.c) due to revision of the pseudo objective propagator - added parameters "heuristics/undercover/coverbd" and "heuristics/undercover/fixingorder" SCIP version 2.1.0 ================== interface: - new method SCIPstartSolvingTime() and SCIPstopSolvingTime() which can be used to start or stop the solving time clock - new methods SCIPcheckCumulativeCondition(), SCIPpropCumulativeCondition, and SCIPrespropCumulativeCondition in cons_cumulative.h; these methods can be used to check, propagate, or resolve the propagation of a cumulative condition - new methods 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. - the methods SCIPwriteVarName() SCIPwriteVarsList(), and SCIPwriteVarsLinearsum() have a new parameter named "type" of type SCIP_Bool which determines if the variable type should be written or not - the methods SCIPparseVarName() and SCIPparseVarsList() got one new output parameter "endptr" which is filled with the position where the parsing stopped - new functions SCIPround() and SCIPfeasRound() to round to nearest integer - new functions 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 - new method SCIPsetConsModifiable() - new method SCIPgetNegatedVars() which returns all negated variables for a given array of variables, if the negated variables are not existing yet, they will be created - methods SCIPexprtreeEvalSol(), SCIPexprtreeEvalIntLocalBounds(), and SCIPexprtreeEvalIntGlobalBounds() have been renamed to SCIPevalExprtreeSol(), SCIPevalExprtreeLocalBounds(), and SCIPevalExprtreeGlobalBounds() (now located in scip.h) - new method 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 - new methods SCIPvarGetNBdchgInfosLb() and SCIPvarGetNBdchgInfosUb() in pub_var.h returning the number of lower or upper bound changes on the active path - new methods SCIPvarGetBdchgInfoLb() and SCIPvarGetBdchgInfoUb() returning the bound change information at the given position - new parameter success in SCIPgetVarCopy() 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 - SCIPcopyProb() and SCIP_DECL_PROBCOPY got a new parameter global - using proper terms "monomial" and "polynomial" (instead of "monom" and "polynom") in nonlinear expressions (nlpi/*expr*) results in many renamings of types, structs, and methods - added function SCIPcomputeLPRelIntPoint() to compute relative interior point of the current LP - added function SCIPsepastoreRemoveInefficaciousCuts() to remove non-efficious cuts from the separation storage - added result value SCIP_NEWROUND that allows a separator/constraint handler to start a new separation round (without previous calls to other separators/conshdlrs) - implemented SCIPlpiGetPrimalRay() in SoPlex interface that has become available with SoPlex version 1.5.0.2 - SCIPchgVarType got an extra boolean to store infeasibility while upgrading a variable from continuous type to an integer type - added function SCIPaddCoefLogicor() to add a variable to a logic or constraint - new methods SCIPhasPrimalRay() and SCIPgetPrimalRayVal() that return whether a primal ray is stored and which value a given variable has in the primal ray, respectively - new method SCIPfindOrigCons() which return a original constraint with the given name or NULL - new method SCIPgetReadingTime() which returns the time for reading in seconds - new method SCIPconshdlrGetNAddConss() which returns the number of added constraints during presolving by a given constraint handler - new method SCIPpresolGetNAddConss() which returns the number of added constraints during presolving by a given presolver - added two parameters to the callback methods SCIP_DECL_CONSPRESOL() and SCIP_DECL_PRESOLEXEC(), these are nnewaddconss and naddconss; these parameters are also added to corresponding C++ wrapper class methods; these are scip_presol() in objconshdlr.h and scip_exec() in objpresol.h - added method SCIPsortRealRealIntInt() and corresponding sorting/inserting/deleting methods in pub_misc.h and necessary defines in misc.c - added SCIPconvertCutsToConss() and SCIPcopyCuts() to scip.{c,h} for copying cuts to linear constraints - new method SCIPnodeGetParent() to get parent node of a node - added methods SCIPsortRealIntLong(), SCIPsortPtrPtrRealInt() and corresponding sorting/inserting/deleting methods in pub_misc.h and necessary defines in misc.c - new method SCIPnodesSharePath() in pub_tree.h that determines whether two nodes are on the same leaf-root path - new method SCIPnodesGetCommonAncestor() in pub_tree.h that finds the common ancestor node for two given nodes - new method SCIPgetNLPFracVars() to get the fractional variables in an NLP solution - new methods SCIPcreateMesshdlrPThreads() and SCIPfreeMesshdlrPThreads() for allocating and deleting necessary memory for message handlers for parallel pthread version - new methods SCIPallocClearMemoryArray() and BMSallocClearMemoryArray() for allocating cleared memory arrays in scip.h and memory.h - removed methods SCIPnlpGetObjective(), SCIPnlpGetSolVals(), SCIPnlpGetVarSolVal(); added methods SCIPgetNLPObjval() and SCIPvarGetNLPSol(); SCIPcreateNLPSol() now returns an error if NLP or NLP solution is not available - removed methods SCIPmarkRequireNLP() and SCIPisNLPRequired(), NLP is now always constructed if nonlinearities are present - removed NLP methods from pub_nlp.h and added corresponding methods to scip.h; removed SCIPgetNLP() - added method SCIPgetNLPVarsNonlinearity() to get for each variable in the NLP the number of NLP rows in which this variable appears in a nonlinear way - added methods SCIPparseVarsLinearsum(), SCIPparseVarsPolynomial() and SCIPwriteVarsPolynomial() and for writing and parsing polynomials in constraint handler writing/parsing methods - new method SCIPsetParam() which is a generic parameter setter method, independent of the parameter type - the callbacks NLPIGETSOLUTION and NLPISETINITIALGUESS and the functions SCIPnlpiGetSolution() and SCIPnlpiSetInitialGuess() now also take arguments to get/set dual values - added methods SCIPnlrowGetDualsol(), SCIPgetNLPVarsLbDualsol(), SCIPgetNLPVarsUbDualsol() to retrieve dual values from an NLP solution - added method SCIPbranchVarValNary() for n-ary variable branching - the callback NLPICOPY gets the block memory of the target SCIP as additional parameter - due to adding SCIP_DECL_PROPINITPRE, SCIP_DECL_PROPEXITPRE, SCIP_DECL_PROPPRESOL, new timing flag and presolving parameters for propagators the SCIPincludeProp() method has a new list of parameters - new methods SCIPpropInitpre, SCIPpropExitpre, SCIPpropPresol which initializes, exists and executes the presolving phase - due to the new timingmask for propagation calls SCIPincludeConshdlr() has the timingmask as a new parameter - new method SCIProwGetAge() to access the age of a row (pub_lp.h/lp.c) - allowed calling SCIPgetRowSolActivity() in SCIP_STAGE_SOLVED, since LP is still available - removed parameters timelimit and memorylimit from SCIPapplyRens() - added parameter to SCIPincludeQuadconsUpgrade() to indicates whether the given upgrade method should be active by default - new methods SCIPdebugAddSolVal() and SCIPdebugGetSolVal() to add/get values to/from a debug solution - various extensions and modifications for expressions and expression trees (too much to state here) - split off PARAMEMPHASIS from PARAMSETTING (in pub_paramset.c/paramset.c) - added new method to linear constraint handler SCIPsetUpgradeConsLinear(), which (de-)activates the possibility to upgrade a linear constraint to a specialized linear constraint (e.g. knapsack) - new method SCIPsolGetOrigObj() in pub_sol.h which returns for a solution in the original problem space the objective value - new method SCIPretransformSol() in scip.h that allows to retransform a solution to the original space - added method SCIPlpiClearState() to LP interfaces for clearing basis information in the LP solver - new method SCIPgetSubscipDepth() to access the depth of the current SCIP as a copied subproblem - new method 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 - new method SCIPvarMarkNotDeletable() that marks a variable to be non-deleteable (used within SCIP for forbidding deletion of variables contained in solution, LP bases, (multi)aggregation, ...) - new method SCIPvarIsDeletable() that returns whether a variable is marked to be deletable (each variable is per default non-deletable) - new callback SCIP_DECL_DELVARS for constraint handlers, that is called after variables were marked for deletion and should remove these variables from its constraints - new method SCIPpropagateCutoffboundVar() in prop_pseudoobj.h which can be used to propagate the cutoff bound for the given variables - SCIPdelVar() got a new parameter "deleted", which stores whether the variable was successfully marked to be deleted - callbacks SCIP_DECL_CONSINITPRE, SCIP_DECL_CONSEXITPRE, SCIP_DECL_PROPINITPRE, SCIP_DECL_PROPEXITPRE, SCIP_DECL_PRESOLINITPRE, and SCIP_DECL_PRESOLEXITPRE and corresponding c++ functions got two new SCIP_Bool parameters "isunbounded" and "isinfeasible" which state whether the problem is already declared to be unbounded or infeasible respectively - SCIPmarkDoNotMultaggrVar()/SCIPvarMarkDoNotMultaggr() now allow to mark negated and aggregated variables - new method SCIPgetNTotalVars() that returns the total number of created vars, icluding variables that were deleted in the meantime - added parameter "separate" to conflict handler callback method SCIP_DECL_CONFLICTEXEC() that defines whether the conflict constraint should be separated or not - SCIPcalcNodeselPriority() got a new parameter "branchdir", which defines the type of branching that was performed: upwards, downwards, or fixed performance improvements: - 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 - 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 fixed bugs: - fixed bug in propagation of indicator constraints: cannot fix slack variable to 0 if linear constraint is disabled/not active - fixed bug in cons_bounddisjunction where branching on multiaggregated variables was tried while all aggregation variables are fixed - fixed assertion in tree.c w.r.t. node estimation - fixed bug in presolving of cons_logicor.c: adding variable implications can lead to further reductions; added call to applyFixings() - 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 reader_fzn.c w.r.t. cumulative constraints - 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 memory leak in reader_pip.c - 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 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 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 cons_orbitope:resprop() for the packing case - fixed bug in reader_mps.c: if a variables first occurence is in the bounds section, then the corresponding variable bound was lost - fixed bug trying to print big messages bigger than SCIP_MAXSTRLEN - fixed bug in copying NLPI interfaces that use block-memory (NLPI copy used block memory from source SCIP) - fixed several issues in flatzinc reader - fixed bug w.r.t. counting feasible solutions and turned of sparse solution test - fixed wrong changing of wasdelayed flag for propagators - fixed bug in cons_countsols.c w.r.t. none active variables - deactived checking of zero solution in Zimpl reader when no starting values are provided - 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 memory leak in coloring part of maximum clique algorithm (tclique_coloring.c) - 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 - fixed bugs in changing the initial and checked flags for constraints in original problem - fixed bug using wrong sign in infinity check in prop_pseudoobj - fixed bug trying to tighten multiaggregated variables, which have only one active representation, and this variable is already tightened - fixed bug in ZI round heuristic that led to infeasible shiftings for numerically slightly infeasible rows with close-to-zero coefficients - fixed memory leak in coloring part of maximum clique algorithm (tclique_coloring.c) in a better way - fixed assert in sepa_clique.c which is currently not valid because implicit binary variables in cliques are ignored - fixed bug in redcost propagator: can only be called if the current node has an LP - fixed numerical issue in octane heuristic: close-to-zero values for ray direction could have led to bad computations - 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 sepa_zerohalf.c concerning inconsistent construction of solution array of variables and fixed wrong assert about variable bounds - fixed possible buffer overrun in tclique_graph.c - fixed bug w.r.t. infinity loop during propagation - fixed bug in handling of lazy bounds that resulted in putting the bounds explicitly into the LP - 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 cons_linear.c, scaling could have led to wrong values - 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 conflict.c, where LPi was manipulated, but not marked as not solved - reader_lp is now able to read lines longer than 65534 characters - 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) plugins: - added vbound heuristic (heur_vbounds.{c,h}) - added clique heuristic (heur_clique.{c,h}) - added pseudoboolean constraint handler (cons_pseudoboolean.{c,h}) - all C template files are now called <plugintype>_xyz.{c,h} instead of <plugintype>_xxx.{c,h} - added first version of cons_disjunction.{c,h} which allows a disjunction of constraints - added first version of sepa_closecuts.{c,h} to separate cuts w.r.t. a point that is closer to the integral polyhedron - added reader for variable bounds (reader_bnd.{c,h}) - 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; currently no trigonometric functions - added constraint handler for (absolute) power constraints (cons_abspower.{c,h}) to handle equations like z = sign(x)abs(x)^n, n > 1 - 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) parameters: - added parameter <constraints/quadratic/disaggregate> to split a block-separable quadratic constraint into several quadratic constraint - added parameter <constraints/indicator/removeindicators> to remove indicator constraints if corresponding vub has been added - change default value of parameter "nodeselection/restartdfs/selectbestfreq" 100 - added parameter "nodeselection/restartdfs/countonlyleafs" in node selector restart dfs which can be used to select the counting process of processed nodes - added parameter <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 - added parameter <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 - added parameters <constraints/linear/nmincomparisons> and <constraints/linear/mingainpernmincomparisons> to influence stopping criterium for pairwise comparison of linear constraints - added parameter <constraints/indicator/maxconditionaltlp> to enable a quality check for the solution of the alternative LP - moved parameters for pseudoboolean constraints from opb-reader to pseudoboolean constraint handler - new parameter for pseudoboolean constraints <constraints/pseudoboolean/decompose>, to transform pseudoboolean constraints into linear- and and-constraints - added parameters <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 - added parameter <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 - added parameter <branching/delaypscostupdate> to delay the update of pseudo costs for continuous variables behind the separation round: default is TRUE - 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 - added parameters <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 - added parameter <constraints/indicator/generatebilinear> to generate bilinear (quadratic) constraints instead of indicator constraints - added parameter <timing/reading> to add reading time to solving time - added parameter <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 - 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 - added parameters <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) - added parameter <separating/closecuts/maxunsucessful> to turn off separation if we can not find cuts - added parameter <propagating/%s/presolpriority> for all propagators which allows to change the priority of calling the given propagator - added parameter <propagating/%s/maxprerounds> for all propagators which allows to change to maximal number of rounds of presolving where this propagator participates in - added parameter <propagating/%s/presoldelay> for all propagators which allows to change if the presolving call of the given propagator should be delayed - added parameter <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 - added parameter <reading/gmsreader/signpower> to enable writing sign(x)abs(x)^n as the rarely used gams function signpower(x,n) - added parameters <constraints/indicator/forcerestart> and <constraints/indicator/restartfrac> to control forced restart in cons_indicator - new parameter <limit/maxorigsol> which defines the size of the solution candidate store (default value is 10) - all parameters in cons_indicator and cons_sos1 have been converted to lower case! - new parameters "conflict/bounddisjunction/continuousfrac" which defines the maximum percantage of continuous variables within a conflict create by the bounddisjunction consflict handler - added parameter <presolving/donotaggr> to deactivate aggregation of variables globally - added parameter <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) - added parameter <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) - added parameters <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 - added parameter <conflict/separate> which enables or disables the separation of conflict constraints - added parameter <lp/clearinitialprobinglp> to clear LP state at end of probing mode, if LP was initially unsolved - changed default value of parameter <separating/gomory/maxroundsroot> to 10 - changed default value of parameter <separating/gomory/maxsepacutsroot> to 50 - added parameter <constraints/varbound/presolpairwise> that allows pairwise presolving of varbound constraints, default is TRUE - added parameter <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 - added parameter <heuristics/shiftandpropagate/onlywithoutsol> to switch whether the heuristic should be called in case a primal solution is already present - removed parameter <heuristics/subnlp/nlpsolver>, use <nlp/solver> instead features: - flatzinc reader is now capable to read cumulative constraints - new heuristic vbounds which use the variables lower and upper bounds to fix variable and performs a neighborhood search - new method SCIPvarGetHashkey(), SCIPvarIsHashkeyEq(), SCIPvarGetHashkeyVal() in pub_var.h which can be used for SCIP_HASHTABLE of variables - the xor constraint handler can now parse its constraints - the bounddisjunction constraint handler can now parse its constraints - SCIP-CPX is now threadsafe - new dual presolving methods in cons_setppc and cons_logicor - added dialog "write nlp" to write current NLP relaxation to a file - new data structure SCIP_STAIRMAP - 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 - comparison of solutions now also works for original solutions - added writing for wbo files - 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 - moved code of scip.c:SCIPreadSol() to reader_sol.c; call solution reading via SCIPreadProb() - 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 - added scripts check_gams.sh, evalcheck_gams.sh and check_gams.awk and target "testgams" in Makefile - can now compute the relative interior point of the current LP - interval arithmetics for power, log, and exp should be rounding safe now - added counter for number calls and timing for resolve propagation calls for constraint handler and propagators - new methods SCIPpropGetNRespropCalls() and SCIPconshdlrGetNRespropCalls() which return the number of times a propagator or a constraint handler was called for resolving a propagation - new method SCIPpropGetRespropTime() and SCIPconshdlrGetRespropTime() which return time spent for resolving a propagation within a propagator or a constraint handler - 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 - added writing for pip files (linear, quadratic, polynomial nonlinear, polynomial abspower, polynomial bivariate, and and constraints) - 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 - 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 - added clock for determine the time for reading - new presolving step in cons_knapsack (detectRedundantVars, deleteRedundantVars) which determines redundant variables in knapsack constraint with or without using clique information - SCIPcreateNLPSol() now creates a SCIP_SOL that is linked to the solution of the current NLP relaxation - it is now possible in SCIP_STAGE_TRANSFORMED to call SCIPaddVarLocks (i.e. to lock variables in initialization methods) - cons_logicor is now able to replace all aggregated variables in presolving by there active or negation of an active variable counterpart - reader_gms is now able to write indicator constraints (reformulated either via big-M or sos1), see new parameters <reading/gmsreader/bigmdefault> and <reading/gmsreader/indicatorreform> - propagators can now presolve, added three callback functionalities SCIP_DECL_PROPINITPRE, SCIP_DECL_PROPEXITPRE, and SCIP_DECL_PROPPRESOL - prop_pseudoobj is now working in presolving as well - 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 - improved output of propagators in display statistics - new method SCIPpropSetPresolPriority which changes the presolving priority of a given propagator - new methods SCIPpropGetPresolPriority, SCIPpropGetPresolTime, SCIPpropWasPresolDelayed, SCIPpropGetNFixedVars, SCIPpropGetNAggrVars, SCIPpropGetNChgVarTypes, SCIPpropGetNChgBds, SCIPpropGetNAddHoles, SCIPpropGetNDelConss, SCIPpropGetNAddConss, SCIPpropGetNUpgdConss, SCIPpropGetNChgCoefs, SCIPpropGetNChgSides, SCIPpropGetTimingmask, SCIPpropDoesPresolve which return corresponding presolving information - 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) - new dialog "change freetransproblem" to free transformed problem in the interactive shell before changing the problem - the knapsack, setppc, and soc constraint handler can now parse their constraints - new method SCIPintervalPowerScalarInverse() to solve an equation y = x^p for given bounds on y and scalar exponent p - new method SCIPintervalQuadBivar() to compute tight bounds on a bivariate quadratic form - new method SCIPintervalSolveBivariateQuadExpressionAllScalar() to compute tight bounds on the solutions of a bivariate quadratic equation - the gams writer can now write nonlinear, abspower, and bivariate constraints - the pip and zimpl reader now create nonlinear constraints for polynomials of degree > 2 - implement presolving in exitpre() in cons_orbitope and cons_indicator - implement possibility to force a restart in cons_indicator if enough indicator variables have been fixed - 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. - solutions which are given by the user from the outside are now marked by '#' in the output - implemented possibility to buffer and restore LP solution after diving without having to resolve the LP; currently turned off, because performance impact is unclear; controlled by parameters lp/resolverestore and lp/freesolvalbuffers - 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 - 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 design: - SCIP_HASHMAP now works also without block memory - 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 - moved all timings to type_timing.h - outsourced propAndSolve() method in solve.c which calls domain propagation and solving of the lp and relaxation - CIP format variable characters defined, e.g. SCIP_VARTYPE_INTEGER_CHAR - add expression graph data structures and methods for reformulation, domain propagation, and simple convexity check on nonlinear expressions statistic: - 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 - 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) Makefile - 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) - new variable $(INSTALLDIR) in Makefile which define installation directory for the libraries, $(INSTALLDIR)/lib/, binary, $(INSTALLDIR)/bin, and include headers, $(INSTALLDIR)/include, the default value is the empty string - 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 - the 'make' parameter 'PARASCIP=true' leads to threadsafe message handlers where you need to call SCIPcreateMesshdlrPThreads and SCIPmessageSetHandler/SCIPmessageSetDefaultHandler and SCIPfreeMesshdlrPThreads; therefor we need to link with pthread library - 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 - new target "make libs" which compiles only the libraries - to link against Clp, only the base directory of an Clp installation needs to be specified now - moved *.test and *.solu files to subdirectory testset in check directory and adjusted test scripts - 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 - removed target "lintfiles", this target is now imitated by the "lint" target and a none empty variable FILES SCIP version 2.0.2 ================== fixed bugs: - fixed bug in heur_subnlp.c where constraints forbidding variable fixations where added if a cutoff was used in the subproblem - fixed wrong assert in plugins that use SCIPcopy() - fixed wrong (neg)cliquepartition check in cons_knapsack.c when deleting a coefficient - 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 - fixed bug while after restarting possible the aggregted variables were not removed in setppc constraints - fixed various small bugs in nonlinear expressions code - fixed bug in DINS heuristic that occured when the incumbent solution value is outside the variable's current domain - fixed bug in DINS w.r.t. column generation - fixed bug in heur_subnlp.c where wrong constraints forbidding variable fixations where added in case of general integers - 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 behavior of LNS heuristics when the subproblem aborts: continue in optimized mode, stop in debug mode - fixed bug in prop_vbounds.c w.r.t. infinity lower and upper bound of variable bound variables - fixed make/make.project - 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 bug w.r.t. setting wall clocks - implemented SCIPlpiGetPrimalRay() in SoPlex interface that has become available with SoPlex version 1.5.0.2 - fixed bug concerning overflow in memsize calculation in set.c - fixed segmentation fault in heur_subnlp.c which occured if resolving the NLP with a tighter feasibility tolerance failed with a solver error - 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 - 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 bug in sorting mechanism in cons_xor.c - fixed bug in changing quadratic coefficients of a row in the NLP - fixed bug caused by not (correctly) counting boundchanges in cons_varbound.c - fixed three bugs when writing in fzn format (wrongly splitted writing buffer, wrong variables was used, floats were printed to short) - 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 - fixed bug in reader_cip regarding reading of very long 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 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 - fixed bug w.r.t. to pricing variables in case new initial constraints come in during the price and cut loop - fixed bug in conflict.c, infeasibility analysis with big values led to wrong result - fixed bug in cons_soc.c w.r.t. upgrading from quadratic constraints with finite left-hand-side performance improvements: - fasten propagation in cons_knapsack.c due to negated clique partitions - recalculating only needed partitions in cons_knapsack.c, not always both - calculation of node priority now also works when variable's relaxation value is equal to a bound - fasten knapsack separation by replacing SCIPallocBuffer(Array) through SCIPallocBlockMemory(Array) - fixed issue w.r.t. calling primal heuristics after presolving detected infeasibility - improved runtime and memory consumption in SCIPsolveKnapsackExactly() in cons_knapsack.c SCIP version 2.0.1 ================== interface: - allow access to transformed constraints in SCIP_STAGE_TRANSFORMED 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 fixed bugs: - fixed bug in heur_subnlp when initialized starting values of a fixed variable in the NLP of the subscip - fixed bugs in SCIPcopyConss: copy all active constraints (including disabled ones), *valid was not initialized to TRUE - fixed bug in reader_mps: indicator constraints do not output the slack variables anymore - fixed bug in heur_undercover: removed option globalbounds, since we are not allowed to relax bounds at a probing node - 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 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 debug.c w.r.t. checking of constraints and continuous variables - fixed bug w.r.t. memory allocation for all values of a column in lpi_cpx.c - 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 heur_shiftandpropagate where some variables were initialized too late - fixed bug in cons.c which didn't allow the changing of the separation and enforcement flag of a constraint in the problem stage - 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 SCIPnlpiOracleChgLinearCoefs and SCIPnlpiOracleChgQuadCoefs for the case where new coefficients where added - fixed bug in nlp.c: nlrowSearchQuadElem was using SCIPquadelemSortedFind incorrectly - fixed bugs in cons_bounddisjunction where the branching during the constraint enforcement was done incorrectly - 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 assertion w.r.t. to probing during the propagation round of a branch-and-bound node - fixed bugs in lpi_none.c w.r.t. debug and opt mode - fixed bugs in cons_orbitope.c: orbitopal fixing for the packing case had two bugs; also fixed one wrong assert - fixed computation of node's objective value estimate when branching on continuous variables (see SCIPtreeCalcChildEstimate, SCIPtreeBranchVar) - fixed bugs in cons_sos?.c: take average of objestimate - 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 statistic w.r.t. number of calls for external branching candidates - fixed bug in lpi_cpx.c w.r.t. to wrong handling in case the crossover did not succeed - fixes to branching on continuous variables - fixed bug in cons_logicor, implications on none SCIP_VARTYPE_BINARY variable were handled wrong - fixed bug in DINS heuristic, information storage for binary variables could lead to bad memory access in column generation applications - fixed some bugs w.r.t. to casting pointer arrays - fixed bug in cons_linear while trying to add a conflict without any variables - 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 vars.c which handled arrays with parts of original variables during resolving to active variables (using SCIPvarsGetProbvarBinary) wrong - fixed bug in reader_gms.c: linear coefficients for quadratic variables were not printed if they had no square-coefficient - fixed bug in heur_subnlp when forbidding a particular combination of integer variables in the main problem - fixed bug in cons_indicator.c: creating constraints in transformed stage is now possible 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 SCIP version 2.0.0 ================== interface: - new method SCIPbranchruleGetNRelaxCalls() to get the total number of times, a particular branching rule was called on a relaxation solutions - new method SCIPpermuteArray() that randomly shuffles an array using the Fisher-Yates algorithm - new method SCIPgetRandomSubset() that draws a random subset of disjoint elements from a given set of disjoint elements - new method SCIPpermuteProb() that randomly permutes constraints and variables - new method SCIPrestartSolve() that allows the user to manually restart the solving process - new method SCIPbranchRelax() to branch on a relaxation solution - new method SCIPbranchVarVal() to branch on an arbitrary value within the variable's bounds - new method SCIPbranchGetBranchingPoint() and SCIPgetBranchingPoint() to select branching point for a variable, e.g., ensure branching point is inside the interval for a continuous variable - new callback SCIP_DECL_BRANCHEXECRELAX(), together with new parameter in SCIPincludeBranchrule() for branching on a relaxation solution - added SCIPsortPtrPtrInt (and various other) and corresponding sorting/inserting/deleting methods in pub_misc.h and necessary defines in misc.c - added to the callback method SCIP_DECL_PROBEXITSOL(x) (type_prob.h) the parameter restart; this parameter is set to TRUE if the exit solve call was triggered by a restart? - new method SCIPswapPointers() - new method 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 - added SCIPsortRealRealRealPtr() and corresponding sorting/inserting/deleting methods in pub_misc.h and necessary defines in misc.c - added to the method SCIPapplyRens() the parameter uselprows, this allows to switch between LP row and SCIP constraints as basis for the subSCIP, setting ist to TRUE (uses LP rows) will lead to same version as before - new parameters "maxmksetcoefs", "delta", and "deltavalid" in sepa_cmir.c: SCIPcutGenerationHeuristicCmir() - added SCIP_DECL_...COPY for all plugins - added SCIP pointer to all C++ objects and constructors - added parameter scip to ObjCloneable::clone() - method SCIPgetVarPseudocost() now returns the pseudocost value of one branching direction, scaled to a unit interval. The old method is now called SCIPgetVarPseudocostVal() - method SCIPgetVarPseudocostCurrentRun() now returns the pseudocost value of one branching direction, scaled to a unit interval, old method now called SCIPgetVarPseudocostValCurrentRun() - methods SCIPgetVarConflictScore and SCIPgetVarConflictScoreCurrentRun() now called SCIPgetVarVSIDS() and SCIPgetVarVSIDSCurrentRun(), resp. - methods SCIPvarGetNInferences(), SCIPvarGetNInferencesCurrentRun(), SCIPvarGetNCutoffs(), and SCIPvarGetNCutoffsCurrentRun() now called SCIPvarGetInferenceSum(), SCIPvarGetInferenceSumCurrentRun(), SCIPvarGetCutoffSum(), and SCIPvarGetCutoffSumCurrentRun(), resp., return SCIP_Real values instead of SCIP_Longint - new method SCIPinitVarBranchStats() to initialize the branching statistics (such as pseudo costs, VSIDS, inference values) of a variable - new methods SCIPsetHeuristics() which set the heuristics to aggressive, fast, off, or default settings, depending on the SCIP_PARAMSET parameter - new methods SCIPsetSeparating() which sets separation to aggressive, fast, off, or default settings, depending on the SCIP_PARAMSET parameter - new methods SCIPsetPresolving() which sets presolving to aggressive, fast, off, or default settings, depending on the SCIP_PARAMSET parameter - new method for heuristics SCIPheurSetFreq() to change the frequency of the heuristic (pub_heur.h, heur.c) - new method 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 - new method 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 - 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) - 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() - 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 - new API for "expressions interpreter" - code that evaluates expression trees, including first and second derivatives - added SCIPsortPtrPtrLongIntInt(), SCIPsortLongPtrPtrIntInt() and corresponding sorting/inserting/deleting methods in pub_misc.h and necessary defines in misc.c - added SCIPcalcNegatedCliquePartition() to scip.c to calculate a clique partition on negations of all given binary variables - new method SCIPcopy() to clone a SCIP instance - new methods SCIPcopyPlugins(), SCIPcopyParamSettings(), SCIPcopyVars(), SCIPcopyConss(), SCIPgetVarCopy() to copy individual parts of a SCIP instance separately. - SCIP can now maintain a central NLP relaxation of the problem (similar to LP) - added SCIPsortLongPtrInt() and corresponding sorting/inserting/deleting methods in pub_misc.h and necessary defines in misc.c - SCIP can now manage a list of external codes (e.g., LP or NLP solver, ZIMPL) - new method SCIPlpiGetSolverDesc() to get a descriptive string of an LP solver (developer, webpage, ...) - new method SCIPisInRestart() to detect whether we are currently restarting - new method SCIPgetResultantOr() which returns the resultant of an "or" constraint - new method SCIPmarkDoNotUpgradeConsLinear() in cons_linear.?, which allows to forbid upgrading of linear constraints - added parameter "quiet" to SCIPparamSet...() which allows to turn on an output showing the new parameter value - new methods SCIPeventGetHoleLeft() and SCIPeventGetHoleRight() for accessing the left right interval bound of a domain hole added or removed event - new method SCIPprintSolReaderFzn() which prints the best solution in Flatzinc format w.r.t. to the output annotations in the input file of the flatzinc model - new methods SCIPvarGetHolelistOriginal(), SCIPvarGetHolelistGlobal(), SCIPvarGetHolelistLocal() to get the original, global, and local holes, respectively - new methods SCIPholelistGetLeft() and SCIPholelistGetRight()to get the left and right interval bounds of the open hole interval - new method SCIPholelistGetNext() to get the next hole of the hole list - new method SCIPvarGetProbvarHole() to tranform a given domain hole to the corresponding active, fixed, or multi-aggregated variable - new method SCIPgetNUpgrConss() which returns the number of upgraded constraints - new method SCIPlpRecalculateObjSqrNorm() which is used when the old calculated square norm was unreliable - added SCIPsortPtrBool() and corresponding sorting/inserting/deleting methods in pub_misc.h and necessary defines in misc.c - new method SCIPresetParam() to reset the value of a single parameter to its default value - new method SCIPpricerIsDelayed() which returns if the pricer is delayed (see pub_pricer.h) - new methods 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) - use of strongbranching changed: Now SCIPstartStrongbranch()/SCIPendStrongbranch() have to be called before/after strongbranching - SCIPgetVarStrongbranch() replaced by SCIPgetVarStrongbranchFrac()/SCIPgetVarStrongbranchInt() - two new functions SCIPgetVarsStrongbranchesFrac()/SCIPgetVarsStrongbranchesInt() for computing strong branching information for several variables - lp.h/lp.c and the lpi's were changed according to the above changes. - 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) - changes in a row can now be catched via row events (SCIPcatchRowEvent(), SCIPdropRowEvent(), SCIP_EVENTTYPE_ROWCOEFCHANGED, SCIP_EVENTTYPE_ROWCONSTCHANGED, SCIP_EVENTTYPE_ROWSIDECHANGED) - new methods SCIPintervalAddInf/Sup/Vectors(), SCIPintervalMulInf/Sup() in intervalarith.c - renamed SCIPintervalScalarProductRealsIntervals()/SCIPintervalScalarProduct() by SCIPintervalScalprodScalars()/SCIPintervalScalprod() and redesigned them in intervalarith.c including new methods SCIPintervalScalprodScalarsInf/Sup() - new parameter "usessubscip" for SCIPincludeHeur(), SCIPincludeSepa() and constructors ObjSepa(), ObjHeur() - new methods SCIPsepaUsesSubscip(), SCIPheurUsesSubscip() - new methods SCIPconshdlrGetEnfoConss(), SCIPconshdlrGetNEnfoConss() - new method SCIPcopyProbData and SCIPprobCopyProbData() which copies the probdata from a sourcescip to a targetscip - new method SCIPsetSubscipsOff() which disables all plugins that uses subscips - new method SCIPsepaSetFreq() to set the calling frequency of a separator - added new callback "SCIP_DECL_VARCOPY" for variables data to be able to copy (see type_var.h) - added new parameter "varcopy" to SCIPcreateVar() to add the function for copying variable data - the SoPlex interface now includes equilibrium scaling on lp's solved from scratch without starting basis - the parameter "success" in "SCIP_DECL_CONSCOPY" has been renamed to "valid" features: - constraint handler can now register their upgrade functions for quadratic constraints to cons_quadratic (similar to LINCONSUPGD) - 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 - 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 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. - 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. - 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. - SCIP may now be manually restarted - 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 - 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 - new undercover heuristic for MINLPs: fixes variables such as to obtain a linear or convex subproblem and solves this - modified implementation of separation algorithms in cons_knapsack.c according to results of diploma thesis; including super-additive lifting (disabled) - 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 - 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 statistic information about the first primal solution to SCIP statistic; in the statistic output a new line appears with this information - primal heuristics may now be called directly after the node's propagation loop, using the new timing point SCIP_HEURTIMING_AFTERPROPLOOP - SCIP is now able to write non-linear opb-files(linear instances with and-constraints) - primal heuristics may now be called during presolving, using the new timing point SCIP_HEURTIMING_DURINGPRESOLLOOP - added new dialog for writing all solutions which are collected during the counting process (see cons_countsols.{c,h}) - support for FreeBSD (32- and 64-bit) including minor changes in several scripts in the check-directory - minor changes on several evaluation scripts (new statuses: better, solved, sollimit, gaplimit) and short-mode for cmpres.awk - added new sorting method SCIPsortLongPtr, SCIPsortDownLongPtr and all corresponding methods - knapsack constraint handler is now able to pairwise presolving constraints - "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 - added new sorting method SCIPsortRealIntPtr, SCIPsortDownRealIntPtr and all corresponding methods - 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 - added new dialog for setting heuristics to aggressive, fast, or off in interactive shell - the vbc visualization adds the branching type (lower or upper bound change) and the new bound to the node information - 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 - the vbc visualization adds the new bound of the branched variable to the node information - allow user to trigger a restart during presolving SCIPrestartSolve() - SCIPsolveKnapsackExactly got a new 12. parameter "SCIP_Bool* success" which stores if an error occured during solving(normally a memory problem) - "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 - 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 - cons_knapsack is now able to detect negated cliques due to negated cliques on knapsack constraints - 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 - new method SCIPvarIsBinary() which checks if a variable is (implicit) binary (see var.c for more details) - and constraint handler can handle implicit binary variables - knapsack constraint handler can handle implicit binary variables - linear or constraint handler can handle implicit binary variables - logic or constraint handler can handle implicit binary variables - or constraint handler can handle implicit binary variables - quadratic or constraint handler can handle implicit binary variables - setppc constraint handler can handle implicit binary variables - varbound constraint handler can handle implicit binary variables - xor constraint handler can handle implicit binary variables - cliques can contain implicit binary variables - new constraint handler cons_linking.{c,h} (see cons_linking.c for more details) - new method SCIPwriteVarName() which writes a variable in cip-format to given stream - new method SCIPwriteVarsList() which writes an array of variables in cip-Format to given stream - new method SCIPparseVarName() which parses a string in cip-format as a variable name - new method SCIPparseVarList() which parses a string as a variable list in cip-format - constraint handler "logicor" can parse its output - constraint handler "and" can parse its output - constraint handler "or" can parse its output - constraint handler "or" can copy its constraints - can now forbid upgrading of individual linear constraints (SCIPmarkDoNotUpgradeConsLinear()) - 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 setting the SCIP parameters for counting "SCIP> set emphasis counting" - new method SCIPsetParamsCountsols() which sets the parameter for a valid counting process - SCIP can now handle problems with continuous variables w.r.t. to counting (the projection to the integral variables are counted) - added new dialog for setting the SCIP parameters for feasibility problems "SCIP> set emphasis feasibility" - new method SCIPwriteVarsLinearsum() which writes an array of variables and coefficients as linear sum in cip-Format to given stream - implemented the data structure and events for global and local domain holes added and removed - 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 - can now read and write indicator constraints in the (extended) MPS format - an XML-parser is available in the src/xml subdirectory - can now read XML-solution files as used by CPLEX - added new dialog "display pricers" which displays all included pricers - now the statistic displays the number of calls of the feasibility checking method of each constraint handler and the running time of it - the LP reader (.lp files) can now read MIQPs and MIQCPs and write quadratic and SOC constraints - 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 - the LP reader (.lp files) and MPS reader can now read semicontinuous variables, they are handled by creating bound disjunction constraints - in case of using SCIPwriteTransProblem() the currently (locally) valid problem is written this now also includes the local constraints - added new dialog for setting the SCIP parameters for hardlp, optimality, easy CIP, CP like search 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 - 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) - 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()) - separators are not called any longer for an integral initial LP solution - in root node, first LP solution is checked for feasibility to avoid expensive setup - added a dual reduction step in cons_knapsack.c - avoided restarting if LP solution is feasible - 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 fixed bugs: - fixed bug in lpi_clp.cpp: SCIPlpiChgBounds checks if the column status exists in Clp before using it - fixed bug concerning assert(!SCIPlpDivingObjChanged(lp)) which was caused by wrong infinity double parameters for cplex - fixed bug in reader_zpl.c which appeared using the parameter "reading/zplreader/parameters" - fixed bug in trivial heuristic: the locking solution might have falsely initialized some values to zero - fixed bug in cons_setppc: aggregated variables were not correctly removed in presolving - fixed bug in cons_linear.c: binary variables should not be multi-aggregated - fixed bug in tree.c: propagate implications on multi-aggregated should not be performed - 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 bug in conflict.c in the method conflictsetAddBound() - fixed "bug" in projects Makefiles w.r.t. "make clean" - 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 bugs do to HEUR_TIMING SCIP_HEURTIMING_AFTERPROPLOOP which appeared during repropagation - 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!" - fixed bug in sepa_rapidlearning.c, stop processing if there are no binary variables left - fixed bug in cons_quadratic.c: curvature of bivariate quadratic constraints was not detected correctly - 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 sepa_rapidlearning.c, corrected computation of right dualbound - fixed bug in lp.c: in sumMIRRow() rowtoolong was not set correctly - fixed bugs in sepa_zerohalf.c, e.g., handling of intscaling and substitution of variable bounds - fixed buglist entry 35, which was caused by a wrong read in correction when the reading buffer was full in reader_opb.c - fixed bug in lp.c w.r.t. objective limit reached and the chosen comparison (fixed buglist entry 40) - 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 - fixed bug in cons_knapsack.c w.r.t. to items with zero weight - fixed bug in lp.c w.r.t. to the number of "active" pricer - 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 in cutpool.c: the hashkey computation was not constant over time - fixed bug in presolving of linear constraint handler: in redundancy detection, two different numerical epsilons were used - corrected wrong assert in DINS heuristic when called for an empty problem - corrected several asserts in linear and quadratic constraint handler concerning parsing of CIP format - 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 bug in sepastore.c in sepastoreApplyLb/Ub being to hard on feasibility decisions - 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 potential bug in OCTANE heuristic with nonbasic solutions - fixed wrong assert in Cplex LPI: Due to numerical inaccuracies, a few pivots might be performed after refactorization - 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 cons_sos2.c: the branching position was sometimes mistakenly increased - 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_knapsack.c: In SCIPseparateRelaxedKnapsack() not all variables need to be active in deeper regions of the tree - fixed potential bug with pseudo solution branching on free variables - 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_bounddisjunction.c: presolve may have tried to tighten bounds on a multiaggregated variable (now upgrades to linear constraint) - 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 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 makefile system for OSTYPE=darwin w.r.t. to CPLEX as LP solver - fixed bug with debugging a solution: during restarts erroneously it was claimed that the primal solution is cut off - fixed bug in copy procedure of AND constraint handler, negated variables have been copied to their originals - 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 that SCIP could not be continued after it has been stopped due to a limit - fixed bug in message handler w.r.t. to messages which are longer then SCIP_MAXSTRLEN - fixed bugs in reader_fzn.c w.r.t. parsing and solution output in Flatzinc format - fixed bug in var.c: SCIPvarChgLbOriginal() and SCIPvarChgUbOriginal() cannot access original bounds if the variable is negated - 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 when aborting pricing with Ctrl-C - fixed bug when deleting a constraint where the update was delayed and not processed yet (in cons.c) - 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 bug in SoPlex autopricing due to which autopricing had behaved like steepest edge pricing so far - fixed bug in cons_linear.c:applyFixings() which could lead to lhs/rhs smaller/larger than -/+infinity - fixed bug w.r.t. ObjDialog and displaying the description of the dialog - 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 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 lp.c: SCIPlpGetUnboundedSol() did not ensure that unbounded solution lies withing the bounds of the variables - fixed bug concering the incorrect assumption that everry solution computed in SCIPlpGetUnboundedSol() is integral (we will not branch but return "infeasible or unbounded" like in presolving) - fixed bug in sepa_flowcover.c: numerical issues while computing candidate set for lambda - 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 - 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 - fixed bug in tree.c: if an explicit branching point is given, we may not recompute a better centering point - 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 in reader_fzn.c w.r.t. comment lines - fixed bug in reader_opb.c w.r.t. comment lines - fixed bug in sub-MIP heuristics with parameter change if some default plugins are not included - fixed bug with resolving LPs at infeasible root node - fixed bug in cons_knapsack.c: mergeMultiples() now detects whether a node can be cut off - fixed bug in trivial heuristic with bounds that are greater than the heuristic's infinity value plugins: - added constraint handler for second order cone constraints (cons_soc.(c|h)) - added packing/partitioning orbitope constraint handler for symmetry handling (cons_orbitope.<c/h>) - added heuristic zirounding (heur_zirounding.{c,h}) - new separator rapid learning (sepa_rapidlearning.{c,h}) that produces conflicts, global bound changes, primal solutions and initializes inference values for branching - 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 - added heuristic twoopt (heur_twoopt.{c,h}) - 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 - added interface to CppAD (nlpi/exprinterpret_cppad.cpp) - 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}) - 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 - added new reader for polynomial mixed-integer programs (reader_pip.{c,h}) as used in the POLIP - feasibility pump heuristic now implements all functionality for feasibility pump 2.0 parameters: - added parameter <misc/usesmalltables> which results in using smaller tables for names, cliques and cuts and improves the performace for smaller instances, default value FALSE - added parameter <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 - removed parameter constraints/knapsack/maxnumcardlift and adapted setting files - added parameter <reading/zplreader/usestartsol> which allows to switch ZIMPL start solutions off, default value TRUE - added parameter <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) - added parameter <heuristics/crossover/dontwaitatroot> that allows to call crossover at root node independently from nwaitingnodes - added parameter <heuristics/rens/uselprows> that allows to switch between LP row and SCIP constraints as basis for the subSCIP, default is TRUE (uses LP rows) - added parameter <constraints/knapsack/presolpairwise> that allows pairwise presolving of knapsack constraints, default is TRUE - added parameter <constraints/knapsack/presolusehashing> that allows fast pairwise presolving of knapsack constraints, default is TRUE - added parameter <constraints/indicator/noLinconsCon> which controls whether the linear constraint is not explicitly added to the problem. default is FALSE - added parameter <constraints/indicator/enforceCuts> that allows to check for violated cust in enforcement - added parameter <constraints/indicator/addCouplingCons> that allows to add variable upper bounds if addCoupling is true - added parameter <constraints/indicator/maxCouplingValue> for the maximal value of the coefficient in a coupling inequality/constraint - added parameter <branching/random/seed> to change the initial seed value of the branching rule random - added parameter <branching/clamp> to set the minimal fractional distance of a branching point to a continuous variable' bounds - added parameter <misc/permutationseed> to change the permutation seed value for permuting the problem after the problem is transformed (-1 means no permutation) - added parameter <constraints/knapsack/dualpresolving> to switch dualpresolving on/off inside the knapsack constraint handler, default is TRUE - added parameter <lp/threads> to change the number of threads used to solve the LP relaxation (default is 0: automatic) - added parameter <vbc/dispsols> to propose if the nodes where solutions are found should be visualized in the branch and bound tree - 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). - added parameter <misc/lexdualstalling> that turns on the lex dual algorithm if the separation process is stalling design: - removed two different block memories for the original and transformed problem Makefile - 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 $(MAINFILE) target, add $(NLPILIBFILE) behind $(LPILIBFILE) in the dependencies and add $(LINKCXX_l)$(NLPILIB)$(LINKLIBSUFFIX) to the linker flags SCIP version 1.2.0 ================== interface: - new parameter "mksetcoefsvalid" in lp.c: SCIPlpCalcMIR(), scip.c: SCIPcalcMIR(), and sepa_cmir.c: tryDelta() to store whether "mksetcoefs" computed in SCIPlpCalcMIR() is valid. If the mixed knapsack constraint obtained after aggregating LP rows is empty or contains too many nonzero elements the generation of the c-MIR cut is aborted in SCIPlpCalcMIR() and mksetcoefs is not valid. - new parameter "set" in SCIPconsSetInitial(). - new methods SCIPchgVarLbLazy() and SCIPchgVarUbLazy() in scip.h; These methods can be used to change the lazy lower or upper bound of a variable; This might has the consequences that the bounds of the corresponding variable is not in LP. This is the case if the lazy lower or upper bound is greater or less than the local lower or upper bound, respectively - new method SCIPvarGetLbLazy() and SCIPvarGetUbLazy() in pub_var.h; These methods return the lazy lower or upper bound, respectively - new methods SCIPgetNFixedonesSetppc() and SCIPgetNFixedzerosSetppc() in cons_setppc.{h,c}; these methods returns curr[5~ent (local) number of variables fixed to one/zero in the given setppc constraint - new methods SCIPprintNodeRootPath() in scip.h This method prints all branching decisions on variables from the root to the given node - new methods SCIPnodeGetParentBranchings(), SCIPnodeGetAncestorBranchings(), SCIPnodeGetAncestorBranchingPath(); These methods return the set of variable branchings that were performed in the parent node / all ancestor nodes to create a given node - new methods SCIPgetVarConflictlengthScore(), SCIPgetVarAvgConflictlength(), SCIPgetAvgConflictlengthScore() and their pendants for the current run - new method to deactivate a pricer SCIPdeactivatePricer() in scip.c - new function SCIPsetProbName() to set problem name in scip.h/c (SCIPprobSetName() in prob.h/c) - new parameters "lowerbound" and "result" in type_pricer.h: lowerbound can save a lower bound computed by the pricer, result indicates whether the pricer guarantees that there exist no more variables if no variable was found - new methods SCIPisLPRelax() and SCIPisRootLPRelax() in scip.c and scip.h returning whether the current/root LP is a relaxation of the current/root problem and thus defines a valid lower bound - new methods SCIPlpSetIsRelax() and SCIPlpSetRootLPIsRelax() in lp.c and lp.h to set the information, whether the lp is a valid relaxation; this information is per default set to true and constraint be used. The aggregated version has only 2 linear constraints the default linearization has nvars + 1 - added function SCIPgetTransObjscale() and SCIPgetTransObjoffset() in scip.c - new interface methods SCIPcolSort(), SCIProwSort(), SCIPcolGetIndex() - extended the sort template functions in sorttpl.c with a "five" array; now it possible to used this template to sort up to five arrays - new callback method SCIP_DECL_CONSCOPY(x) in type_cons.h; this method can be use to copy a constraint - new callback method SCIP_DECL_CONSPARSE(x) in type_cons.h; this method can be use to pasre a constraint in CIP format - added function SCIPaddObjoffset() in scip.h; sets offset of objective function - added function SCIPgetOrigObjoffset() in scip.h; returns the objective offset of the original problem - added function SCIPgetOrigObjscale() in scip.h; returns the objective scale of the original problem - added function SCIPparseVars() in scip.h; parses variable information (in cip format) out of a string - added function SCIPparseCons() in scip.h; parses constraint information (in cip format) out of a string - added function SCIPgetConsCopy() in scip.h; which copies a constraint of the source SCIP - new parameter "sol" in lp.c: SCIPlpCalcMIR(), scip.c: SCIPcalcMIR(), and sepa_cmir.c: tryDelta() to separate a sol different from the LP solution - new parameter "sol" in scip.c: SCIPgetVarClosestVlb() and SCIPgetVarClosestVub() and var.c: SCIPvarGetClosestVlb() and SCIPvarGetClosestVub() to get closest variable bound w.r.t. sol different from LP solution - new methods in pub_misc.h/misc.c to access hash map lists and elements of a hash map list and to clear all entries in a hash map - some interval arithmetic method take an additional argument to denote which value stands for infinity in an interval - extend Makefile to link against Ipopt if IPOPT=true is set - added function SCIPvarsGetProbvarBinary() in pub_var.h; gets active, fixed, or multi-aggregated problem variables of binary variables and corresponding negated status - added SCIPsortPtrPtrLongInt() and corresponding sorting/inserting/deleting methods in pub_misc.h and necessary defines in misc.c - added detectRedundantConstraints() in cons_xor.c and necessary hash-functions for fast pairwise presolving - added function SCIPvarCompareActiveAndNegated and SCIPvarCompActiveAndNegated in pub_var.h for comparing variables negated, active or fixed the same way - heavily revised mosek interface features: - new trivial heuristic: tries zero solution, lower and upper bound solution and some variable lock based fixing - adjusted hard memory limit to (soft memory limit)*1.1 + 100mb in check.sh, checkcount.sh, check_cplex.sh, check_cluster.sh and check_cbc.sh - new interface to QSopt due to Daniel Espinoza - new reader for reading and writing FlatZinc models - new presolving step in cons_knapsack.c, same like "simplifyinequalities" in cons_linear.c - each variable has now two additional SCIP_Real parameter which define a lazy lower and upper bound; lazy means that there exists constraints which implies these (lazy) bounds. If the lazy lower or upper bound is greater or less than the local lower or upper bound, respectively, then the corresponding bound is not put into the LP. The bounds are set to minus and plus infinity per default which yields the same behavior as before. With the methods SCIPchgVarLbLazy() and SCIPchgVarUbLazy() these bounds can be set. This is of interest if SCIP gets used as a branch-and-price framework. Attention! The lazy bounds need to be valid for each feasible LP solution. If the objective function implies bounds on the variables for each optimal LP solution, but these bounds may be violated for arbitrary LP solutions, these bounds must not be declared lazy! - added new timing point, SCIP_HEURTIMING_DURINGPRICINGLOOP, for calling heuristics; If this timing point is used the corresponding heuristics is called during the pricing loop of variables; we also added this timing point to heur_simplerounding.{h,c} which has the effect that a LP solution which satisfies all integrality conditions during the pricing loop is detected - extended hybrid relpscost branching rule by usage of the average length of conflicts a variable appears in - one can now write indicator constraints in LP-format - now it's possible to write strings with more than "SCIP_MAXSTRLEN" amount of characters in all message.c functions - the current/root lp can be marked to be no relaxation of the current/root problem - "early branching"-functionality added: in a branch-and-price code, the user can stop pricing at a node although there may exist variables with negative reduced costs. In this case, the lp-lowerbound will not be used. The pricer has, however, the option to return a lower bound. - the infrastructure for parsing CIP format is set; each constraint handler has now an callback method SCIP_DECL_CONSPARSE() (see type_cons.h) - the infrastructure for copying constraints is set; each constraint handler has now an callback method SCIP_DECL_CONSCOPYE() (see type_cons.h) - all linear type constraint handlers are able to copy constraints using the function SCIPgetConsCopy() in scip.h - the linear constraint handler is able to parse a string in CIP format and create a corresponding linear constraint - interval arithmetic functions can work with unbounded intervals added new functions to allow more operations on intervals, including solving quadratic interval equations - added new preprocessing step (mergeMultiples) in cons_setppc.c where equal variables are merged - can now run lexicographical dual algorithm (parameter lp/lexdualalgo) - the indicator constraint can now try to produce a feasible solution (via heur_trysol) - added new version of zerohalf cuts from Manuel Kutschka performance improvements: - replaced some function calls in loop conditions - in sepa_cmir.c, if mksetcoefs is invalid for delta=1 no other values of delta are tested anymore - changed the timing of the feasibility pump in case of pricing - removed changing of update rule to "ETA" from standard soplex update "Forrest-Tomlin" in lpi_spx.cpp - improved memory usage in heur_octane.c - improved reading time of opb-files, due to using a hashtable for all "and"-constraints - improved pairwise presolving in cons_and.c due to using a hashtable - improved performance of merging variables in mergeMultiples() in cons_knapsack.c - improved performance in tightenWeightsLift() and SCIPseparateRelaxedKnapsack() in cons_knapsack.c, due to now sparse-cleaning "global" arrays instead of using BMSclearMemory... functions for cleaning local arrays each time - improved performance in SCIPcliquelistRemoveFromCliques() - improved performance in SCIPcalcCliquePartition() - improved performance in SCIPvarGetActiveRepresentatives() in var.c - improved pairwise presolving in cons_xor.c due to using a hashtable fixed bugs: - fixed bug in SCIPlpSolveAndEval(): if fastmip and pricers enabled and objlimit was reached but CPLEX did not perform the final pivot step in order to exceed the objlimit, do one additional simplex step with pricing strategy steepest edge, if this doesn't suffice, turn off fastmip temporarily and solve again. Also consider solstat of the new solution. - corrected two asserts in sepa_redcost.c (reduced costs can be negative for fixed variables - qsopt uses this) - corrected several bugs in the Clp-interface concerning return values - corrected bug in reader_lp.c: earlier read bounds were thrown away (implementation was not conforming to standard) - fixed potential interface bug: time limits of 0.0 are not anymore passed to the LP solver, which may have caused errors - fixed wrong result in check.awk, if infeasible problems are stopped in presolving - fixed wrong use of pointer in lp.c - fixed memory error in cons_countsols.c - fixed bug in SCIPsolveNode() concerning the case that the time limit was hit while solving the LP relaxation of a subproblem which is already an LP (branching on pseudo solution is not possible) - fixed wrong fixing of reading bug which was in real a writing bug in MPS format; integer variables in mps format without bounds are binary variables, if the bound of an integer variable is infinity you have to write this bound - fixed bug in chgRhs() and chgLhs() of cons_linear.c: after changing lhs or rhs of a constraints lhs <= rhs has to be satisfied without numerical tolerances - fixed bug in sepa_zerohalf.c; replacement of own sorting functions by template functions was incorrect - fixed bug in sepa_cmir.c concerning uninitialized mksetcoefs (if MIR-cut generation is aborted because the aggregated constraint is empty or contains too many nonzero elements mksetcoefs is invalid) - fixed bug in SCIPconsSetInitial() that occurred in pairwise presolving: add or delete constraint in initconss when changing the initial flag - fixed "GGT-Kaibel-Bug" in var.c, prop_pseudoobj.c and cons_varbound.c that occured while computing new values using infinity values - fixed assert in cons_and.c method SCIP_DECL_CONSINITSOL(consInitsolAnd) - fixed bug with exponential complexity for reallocating memory in SCIPvarGetActiveRepresentatives in var.c - fixed possible infinite loop while multiaggregating a variable in var.c - fixed bug with array dimension not reset to zero when array is freed in pseudoobj propagator - fixed bug with empty constraints in several writing routines - fixed bug with invalid pseudo solution (lower bound was always >= 0) when using pricing. - fixed bug with incorrect pseudo activities when objective of a variable switches sign in linear constraint handler - fixed bug with enforcement of pseudo solutions: if pseudo solution is choosen because LP hit a limit, it has to be enforced in any case - fixed bug in vbc tools concerning of marking probing nodes - fixed infinity loop in simplify inequalities in cons_linear.c - fixed exponential calculation of solution values during check of original solution, therefor changed SCIPvarGetActiveRepresentatives() in var.c and flattened all multiaggregated vars at the end of presolving in exitPresolve() - added and changed some SCIPisStopped() calls in several heuristics - changed wrong writing of mps files due to constraints without any name - now frees debug memory - fixed a bug during reading debug solution file - interrupts optimization prozess if a node will be cutoff, which allows the solution - fixed bug with wrong abort criterion in presolving - fixed wrong assert in cons_knapsack.c and handled a special this case in simplifyInequalities() - fixed bug in SCIPgetSolVals() similar to SCIPgetSolVal(): try to get original variables of transformed ones if the solution lives in original space - fixed potential bug in coloring example: SCIPcreateChild() is now given an estimate in terms of the transformed problem by SCIPgetLocalTransEstimate(), no longer the estimated original problem value. Also clarified this in the comments for SCIPcreateChild() - fixed potential bug: restarts are now only done if no active pricers exist - fixed bug in cons_countsols.c we respect to warning message that "The current parameter setting might cause ..." - fixed bug in reader_lp.c with respect to constraint and variable names which start with two or more dots ".." - fixed bug in all readers w.r.t. SCIPgetProbvarLinearSum() - fixed bug in reader_mps.c with respect to writing transformed problems - fixed bug in solve.c with nodes which are marked to be repropagated while enforcement - fixed compiler warning 'warning: dereferencing type-punned pointer will break strict-aliasing rules' which resuts in scip-crashes with gcc version 4.4.0 - fixed bug in cons.c caused by not resetting conshdlr data after restart - fixed bug in case of reading an objective function in opb format with multiple occurrences of the same variable - fixed bug in sepa_cmir.c, sepa_mcf.c and sepa_flowcover.c: sol different to LP solution is now separated - fixed bug in case of reading an objective function in lp format with multiple occurrences of the same variable - fixed bug in sepa_impliedbounds.c and sepa_intobj.c: if separating a sol, this sol is now also given to SCIPaddCut() so that the efficacy of the cut is now computed correctly - fixed bug in cons_linear.c: do not select variable as slack variable for multiaggregation in convertLongEquality if it has been marked as not-multiaggregable - fixed bug in cons_linear.c: also do not multiaggregate variables in dual preproccessing if it has been marked as not-multiaggregable - fixed bug in cons_linear.c: slight decrease of epsilon in order to make sure that scaled coefficients are really integral - fixed casting of void* pointers in memory.h for C++, adjusted the same for C in memory.h, and due to that adjusted all header files(set whole files in extern "C") and cpp-files(removed unnecessary extern "C" lines) - fixed some bugs in simplifyInequalities() in cons_knapsack.c - fixed bug in mergeMultiples() in cons_knapsack.c - adjusted ConsData and ConsHdlrData in cons_knapsack.c - fixed compiler warning caused by no initialization of two integer in cons_knapsack.c - adjusted assert in var.c - fixed bug in SCIPvarGetActiveRepresentatives() in var.c - fixed bug with objective limit in lp.c: previously the infinity value of SCIP was used as default - now the value of LPI is used. In the earlier version in many cases the problems where never infeasible. - added and adjusted some asserts, initialized some values - fixed bug in presol.c caused by not reseting presolver-wasdelayed status - fixed bug in solve.c caused by integer overflow due to setting the number of cuts to INT_MAX - fixed bug in cons_knapsack.c caused by having a multi-aggregated variable in a knapsack constraint, now applyFixing is able to resolve a binary multi-aggregation with integral values - fixed bug in SCIPfreeProb() in scip.c: all pricers are deactivated now - fixed bug in reader_mps.c with respect to corrupted files - fixed bug in oneopt heuritic with start solution which has become infeasible due to global bound changes - increased the numerical stability of coefficient tightening for Big M formulations - fixed bug in coefficient tightening with infinite bounds - removed memory leak in connection with freeing branch and bound nodes: focusnode was not freed if both children could be cut off due to bounding - fixed bug in solve.c: in case lowerbound >= upperbound, SCIPsolveIsStopped() returned SCIP_STATUS_GAPLIMIT - fixed bug in var.c, cons_knapsack.c, and sepa_flowcover.c: variable bounds corresponding to implication are not generated if coefficient is large, variable bounds with large coefficients are ignored for construction of knapsack and snf relaxations - fixed bug in sepa_impliedbound.c concerning redundant implications plugins: - added interface to QSopt due to Daniel Espinoza - added reader for FlatZinc models (reader_fzn.{c,h}) - added multi-commodity-flow cut separator - adjusted interface to ZIMPL (reader_zpl.{c,h} for ZIMPL version 2.10; this interface should also work with older ZIMPL versions - added writer for GAMS models (reader_gms.{c,h}) - added constraint handler for quadratic constraints - added first version of an interface to NLP solvers (type_nlpi.h, struct_nlpi.h, nlpi.h, nlpi.c, nlpi_oracle.h, nlpi_oracle.c) - added first version of an interface to Ipopt (only QCP, no deletion of vars/cons allowed; nlpi_ipopt.(h|c)) - added heuristic that performs a local search in an NLP (takes only linear and quadratic constraints into account so far) - added heuristic that gets a solution from other components and tries it (heur_trysol.?) parameters: - removed parameter <constraints/and/initiallp> since it is not needed anymore; - new parameter <constraints/and/enforcecuts> in cons_and.c, should cuts be separated during LP enforcing? - new parameter <constraints/and/presolusehashing> in cons_and.c, should pairwise presolving use hashing?, default TRUE - new parameter <constraints/and/aggrlinearization> in cons_and.c, should an aggregated version of the linearization of the - set parameter <constraints/and/sepafreq> default value to 1 - new parameter <constraints/countsols/sollimit> in cons_countsols.c, counting stops, if the given number of solutions were found (-1: no limit) - new parameter <constraints/xor/presolusehashing> in cons_xor.c, should pairwise presolving use hashing?, default TRUE - new parameter <branching/relpscost/advanced/conflenscore>, default value 0.001 - new parameter <heuristics/oneopt/duringroot>, default value TRUE - display character of oneopt heuristic changed to 'b' SCIP version 1.1.0 ================== compiling: - added in all make/make.* "GMP_FLAGS" and "GMP_LDFLAGS" - new flag GMP with values ("auto", "true, and "false"); in case of "auto" the library gmp is linked if ZIMPL is included - modified makefiles to accept ZIMPLOPT and LPSOPT flags (with values "opt" or "dbg" and default being "opt"), and removed LPS=spxdbg and LPS=clpdbg - added "make/make.project" as default make include for external projects using SCIP - adapted all makefiles of the examples accordingly - added possibility to compile shared libraries in makefiles (and added make/make.linux.x86.gnu.opt-shared) - replaced <string> by <cstring> in all C++-interfaces to get 'strlen()' included (gcc-4.3 gave an error) - Moved -rpath option for ld to linux-specific Makefiles. - Re-activated readline library on darwin/ppc. - added target spx132 for SoPlex version 1.3.2 - removed tag make testpre (useless without corresponding scripts) - added tag testcount (make testcount); this allows for testing counting problem interface: - new method SCIPchgChildPrio() to change the node selection priority of the given child - new method SCIPconsGetPos() - new parameters "extension" and "genericnames" in SCIPprintTransProblem() defining the requested format or NULL for default CIP format and using generic names for the variables and constraints e.g, SCIPprintTransProblem(scip, NULL, NULL, TRUE) displays the transformed problem in CIP format with generic variables and constraint names - new parameters "extension" and "genericnames" in SCIPprintOrigProblem() defining the requested format or NULL for default CIP format and using generic names for the variables and constraints e.g, SCIPprintOrigProblem(scip, NULL, "lp", FALSE) displays the original problem in LP format with original variables and constraint names - new callback method SCIP_DECL_READERWRITE(x) in type_reader.h; this method is called to write a problem to file stream in the format the reader stands for; useful for writing the transformed problem in LP or MPS format - new parameter "conshdlrname" in SCIPincludeLinconsUpgrade() - new method SCIPrepropagateNode() to mark a node for repropagation - new method SCIPcount() (in cons_countsols.h) for counting all feasible solution of a given CIP - new method SCIPcreateRootDialog() (in dialog_default.h) which creates a root dialog - new method SCIPbsortInd() - replaced sorting methods SCIPbsort...() by faster (quicksort/shellsort) algorithms SCIPsort...() Note that the order of the parameters has been changed to simplify the template code in sorttpl.c! - expand sorttpl.c by some parameters - added some downwards-sorting methods - changed some names for sorting methods - new parameter 'maxfrac' for SCIPcalcStrongCG() - the parameter list of the method SCIPcheckSolOrig() (scip.h) has changed; the new advatage is, that SCIP can print the reason for a violation as for as the violated component supports this - the parameter list of the method SCIPcheckCons() (scip.h) has changed; the new advatage is, that SCIP can print the reason for the violation of a constraint as for as the constraint handler supports that - the interface method SCIP_DECL_CONSCHECK() has a new parameter "printreason"; if this comes in TRUE the constraint handler is ask to print for violated constraint a reason; - the parameter list of the method scip_check() (objconshdlr.h) has an additional parameter "printreason" see for explanation the previous point - new method SCIPgetVectorEfficacyNorm() - new method SCIPcutGenerationHeuristicCmir() in sepa_cmir.h - new method SCIPseparateRelaxedKnapsack() in cons_knapsack.h - new method SCIPgetCutoffdepth() which returns the depth of first node in active path that is marked being cutoff - added user pointer to callback methods of hash table - new method SCIPflattenVarAggregationGraph() - new method SCIPclockGetLastTime() - new methods SCIPsortedvecInsert...(), SCIPsortedvecInsertDown...(), SCIPsortedvecDelPos...(), SCIPsortedvecDelPosDown...(), SCIPsortedvecFind...(), and SCIPsortedvecFindDown...() to manage sorted vectors or groups of vectors of various data types that are sorted w.r.t. the first vector - new method SCIPcalcHashtableSize() to get a reasonable hash table size - new methods SCIPheurGetTimingmask() and SCIPheurSetTimingmask() - added new LPI pricing option SCIP_PRICING_LPIDEFAULT, such that every LP interface can set the default pricing strategy on its own ('auto' is not useful for this, because for CPLEX, for example, SCIP seems to be worse with 'auto' then with 'steepest edge') - SCIPgetVarRedcost() now returns 0 for variables that have been aggregated out or removed in presolving. - new methods SCIPgetVarFarkasCoef() and SCIPgetColFarkasCoef() to get the farkas coefficient of a variable (analogon of reduced cost in case of infeasible LPs) - new parameter "maxmksetcoefs" for SCIPcalcMIR() and SCIPcalcStrongCG() methods - new method SCIPprintSysError which encapsulates the strerror_r calls, the NO_STRERROR_R flag switches between the use of strerror_r and strerror inside - new method SCIPgetRepropdepth() to get the depth of first node in active path that has to be propagated again - new method SCIPsnprintf() safe version of snprintf (and sprintf) - Many changes in the SoPlex interface: The current one is tailored towards SoPlex 1.4 (aka 1.3.3). All SoPlex functions (where applicable) should now have an exception handling. The Bugfix for adding columns has been moved to SoPlex. One can use ROW representation. Reading/writing of a basis has been implemented. - new parameters "extension" in SCIPreadProb() defining a desired file format or NULL if file extension should be use - new methods SCIPreaderCanRead() and SCIPreaderCanWrite() in pub_reader.h, these return TRUE if the corresponding reader is capable to read or write, respectively - new methods SCIPmajorVersion, SCIPminorVersion, and SCIPtechVersion() returning the corresponding version - changed default frequency parameters for RINS, Local Branching, Crossover and Mutation heuristic This should not change the performance but happened just for consistency reasons features: - the MPS reader is now able to write a problem in MPS format - new method SCIPwriteOrigProblem(), e.g., SCIPwriteOrigProblem(scip, "orig.lp", NULL, FALSE) prints the original problem in LP format in the file "orig.lp" - new method SCIPwriteTransProblem(), e.g., SCIPwriteTransProblem(scip, NULL, NULL, FALSE) displays the transformed problem in CIP format - new method SCIPgetProbvarLinearSum() - added SOS2 example - extended TSP example - the ZIMPL reader now understands SOS type 1 and 2 constraints - the LP reader reads SOS constraints of type 1 and 2 - the MPS reader reads the SOS section (but cannot yet handle 'MARKERS') - output of real values is now done with 15 digits after the decimal point - new method SCIPgetResultantAnd() which returns the resultant variable of an "and" constraint - SCIP is now able to count all feasible solutions of a given CIP (SCIPcount() in cons_countsols.h) - SCIP can now output a picture of the constraint matrix in PPM format. - replaced some old sorting methods in cons_knapsack.c, heur_octane.c, sepa_flowcover.c and presol_probing.c through SCIPsort... interfaces, adjusted misc.{c,h} and pub_misc.h for these changes - updated mmm.{test,solu}, mittelmann.{test,solu}, miplib3.solu, miplib.solu, shortmiplib.test and added mittelmann_current.test, mittelmann_old.test - LPI now has a function SCIPlpiGetSolverPointer() that returns a solver dependent pointer. This can be used to directly access the LP solver. This should, of course, only be used by people that know exactly what they are doing. - added ccg-reader (weighted column connectivity graph) - cons_countsols.c is now able to store the collected solution if required - check.awk now uses TeX package supertabular which supports automatic pagebreak - struct SCIP_Stat has now two additional variables: nprobboundchgs, nprobholechgs; these are used to fix the domain reduction counts in sepa.c, cons.c, branch.c, and prop.c; this means, that now the domain reduction counts are reduced by those domain reduceds which are preformed during probing - The SoPlex LPI can now write basis files. - added capabilities to avoid multi-aggregation of a single variable by setting a corresponding flag (SCIPmarkDoNotMultaggrVar()) - added capabilities to flatten the (multi)-aggregation graph of variables - the ZPL reader is now able to pass a starting solution to SCIP - revised lpi_clp.cpp (many small changes, in particular writing and reading of bases) - added FASTMIP settings in lpi_clp.cpp that try to improve the performance of Clp as much as possible - added coloring example in examples/Coloring - added test scripts for testing counting (make testcount) - allow cut selection based on support of inequality in orthogonality computation - advanced reading and writing dialog in interactive shell - replaced tcsh by bash and gawk by awk in all check scripts to achieve higher compatibility plugins: - added first version of SOS type 1 constraint handler (cons_sos1.{c,h}) - added first version of SOS type 2 constraint handler (cons_sos2.{c,h}) - less aggressive scaling in linear constraint handler presolve to improve numerics - added reader for pseudo-Boolean problems (reader_opb.{c,h}) - added first version of constraint handler cons_countsols.{c,h} - pseudoobj propagator now also propagates the global lower (dual) bound - linear constraint handler now detects continuous variables that are implicit integer in dual presolve - the c-MIR separator now also tries to get rid of implicit integer variables by aggregation - new heuristic DINS (distance induced neighborhood search by Ghosh) - new presolver boundshift (presol_boundshift.{c,h}); this presolver is currently turned off with default parameter setting - new separator sepa_zerohalf.{c,h}; separates {0,1/2}-Cuts according to Caprara and Fischetti parameters: - new parameter "constraints/and/linearize" to enable linearization of all <and> constraints (in presolving), - new parameter "constraints/linear/aggregatevariables" to search for aggregations in equations in the presolving step - changed parameter default values for the priority of presolver "dualfix" and "inttobinary" - new parameter "constraint/linear/upgrade/binpack" to enable or disable the linear upgrading process - new parameter "constraint/linear/upgrade/eqknapsack" to enable or disable the linear upgrading process - new parameter "constraint/linear/upgrade/invarknapsack" to enable or disable the linear upgrading process - new parameter "constraint/linear/upgrade/knapsack" to enable or disable the linear upgrading process - new parameter "constraint/linear/upgrade/logicor" to enable or disable the linear upgrading process - new parameter "constraint/linear/upgrade/setppc" to enable or disable the linear upgrading process - new parameter "constraint/linear/upgrade/varbound" to enable or disable the linear upgrading process - new parameter "constraints/SOS1/branchSOS" to enable or disable branching on SOS1 constraints - new parameter "constraints/SOS1/branchNonzeros" to decide whether SOS1 constraint with largest number of nonzero variables is picked for branching - new parameter "constraints/indicator/branchIndicators" to decide whether it is branched on indicator constraints in enforcing - new parameter "constraints/indicator/genLogicor" to decide whether logicor constraints instead of cuts are generated - new parameter "constraints/indicator/sepaAlternativeLP" to decide whether separation takes place using the alternative LP - new parameter "constraints/linear/simplifyinequalities" to enable a simplification step for inequalities; default value is set to FALSE = disabled - new parameter "constraints/linear/dualpresolving" to disable dual presolving step in the linear constraint handler; default value is TRUE - new parameter "heuristics/mutation/minimprove" - new parameter "constraints/and/initiallp" to turn on, off, or 'auto' that the LP relaxation of the AND constraints are in the initial LP; - new parameter "constraints/countsols/collect" to enable the storing of the solutions; default value FALSE; - new parameter "constraints/indicator/addCoupling" to enable generation of relaxation - removed parameter "separating/cmir/maxtestdeltaroot" - new value 'l' for parameter "lp/pricing", which is the new default - new parameter "separating/cmir/densityoffset" to allow for more c-MIR cuts on small models - new parameter "heuristics/feaspump/beforecuts" to allow the feaspump to be called before cut separation - new parameter "separating/orthofunc" to choose function for scalar product computation in orthogonality test - new parameter "constraints/setppc/presolusehashing" to use hashing comparison in cons_setppc.c; default value is TRUE - new parameter "constraints/logicor/presolusehashing" to use hashing comparison in cons_logicor.c; default value is TRUE - new parameter "constraints/linear/presolusehashing" to use hashing comparison in cons_linear.c; default value is TRUE - disabled zerohalf cuts by default - adjusted all predefined settings files, e.g., settings/cuts/fast.set, such that they are consistent wrt removed, added, and changed parameter values of scip. - added predefined settings file presolving/aggressive.set - new parameter "presol/donotmultaggr" which disables multiaggregation for all variables of the problem performance improvements: - improved the performance of SCIPcalcMIR() and SCIPcalcStrongCG() by exploiting sparsity - better branching in SOS1/SOS2 constraints - improved pairwise presolving in cons_linear.c: reduced cache misses, reduced number of SCIPisStopped() calls and included detecting of redundant constraints with hash table in advance - small performance improvement of c-MIR aggregation heuristic - tighter memory limits in knapsack presolve lifting procedure to avoid overly expensive presolving - heavily decreased the usage of SCIPisStopped(), which costs system time - fixed performance bug with large number of unnamed constraints that will kill the name hash table (now, unnamed constraints are not put into the hash table) - reworked strong branching in lpi_clp.cpp (scaling works now, bounds can be trusted) - improved performance of SCIPvarGetLPSol(), which affects many parts of the code, in particular Gomory and strong CG cuts - do not calculate MIR and StrongCG cut aggregations if number of nonzeros in aggregated row is too large - included detecting of redundant constraints with hash table in advance in cons_logicor.c and limit other pairwise presolving - included detecting of redundant constraints with hash table in advance in cons_setppc.c and limit other pairwise presolving - limit pairwise presolving in cons_linear.c fixed bugs: - added handling of the case of roundable variables with 0 objective in presol_dualfix.c - fixed handling of unbounded variables with 0 objective in SCIPlpGetModifiedPseudo[Proved]Objval() (lp.c) - fixed CTRL-C if NO_SIGACTION is set (e.g., for MinGW) - fixed bug that a missing CONSTRANS in constraint handler leads to NULL pointer as constraint data for the copied constraints instead of pointer copies of the consdata (as explained in the constraint handler "HowTo") - fixed bug with reading empty lines in TSP example - fixed bug with writing the MIP relaxation to a file concerning the objective function; in case the original objective function is requested, the transformed objective function gets re-transformed (scaling, offset) - added checks whether a plugin (handler) has already been included to avoid later complications e.g. with parameters. - fixed obvious bug in linear constraint data sorting. Most part of the code assumed pure index sorting, but in fact, it was sorted by variable type as first criterion and index as second criterion. - fixed bug with wrong objective sense output for transformed problem. The transformed problem is always a minimization problem! - fixed numerical issue in linear constraint propagation: need slightly more aggressive tightening such that probing does not choose a wrong value for fixing inside an epsilon interval - fixed bug with objective scaling after restart - fixed bug with useless objective cutoff in LNS heuristics - fixed bug with wrong 'tightened' return value of some of the change bounds methods - fixed bug with non-conformal parameter name in reader_ppm - fixed bugs in sorttpl.c: fixed wrong arraysize in shellsort; in case an has at most one element, then no sorting is applied - fixed bug in cons_countsols.c concerning variable locking - fixed wrong if condition for function call in sorttpl.c - forced full propagation in presolving -> this fixes a bug that implied that variable locks became inconsistent - avoid aggregation of implicit integers with fractional aggregation scalars - fixed infinite loop in LP file reader if a line exceeds the character limit - replaced calls to perror() by SCIP error message using strerror(errno); this avoids problems with the error output stream - fixed bug in method SCIPgetProbvarLinearSum() - fixed bug in aggregateActiveIntVars(): If a < 0, multiply a*x + b*y == c by -1 (algo for finding initial solution does only work for a > 0). - fixed bugs in second part of consdataTightenCoefs(): Removed min/maxleftactisinfinity (definition was not correct), fixed calculation of min/maxleftactivity, and removed asserts concerning whether all redundant vars were deleted (led to different behavior in debug and opt mod). - corrected invalid memory access in tcliqueIsEdge: added check whether node1 has no neighbors (tclique_graph.c) - fixed numerical bug in dual presolving of linear constraint handler - fixed typo in documentation: default value for "dynamic" parameter is FALSE for all constraint handlers! - fixed bug with multi-aggregated variables in cons_logicor: instead of fixing them, a linear constraint will be created - fixed bug with uncatched LPSOLSTAT after hitting a time or iteration limit - fixed bug with wrong update of activities in linear constraints after global upper bound changes - avoid fixing variables to infinity in order to get rid of numerical inconsistencies in the original model - fixed bug in reader_ppm while appending strings for output file - fixed bug with errors occurring in sub-MIPs. Search is only aborted in dbg mode, in opt mode a warning will be printed - fixed bug in tclique-graph datastructure concerning insertion of edges into nonempty graph - corrected bug in SCIPtreeBranchVar() (tree.c) - several comparison functions needed a 'feas'. - corrected bug in SCIPlpGetState if the LP is empty - corrected bug in cons_linear.c:applyFixings() [if variable was fixed to infinity the rhs/lhs were wrong] - corrected bug in priceAndCutLoop(): separation was aborted if domain reduction was applied - fixed bug in SCIPlpSolveAndEval(): added extra simplex step if objlimit reached, fastmip and pricers enabled in order to get dual solution for pricing. - fixed bug in cons_varbounds.c, concerning SCIPaddVarVlb() and SCIPaddVarVub() - fixed bugs in pairwise presolving of cons_linear.c concerning deletion of upgraded constraints and inconsistent update of nchgsides in case of coefsequal and coefsnegated - avoiding aggregation that removes information about implicitly integer variables (removes bug) - fixed false assert and corrected a bug caused by deleting a constraint on "firstchanged" position in pairwise presolving with hashing in cons_linear.c - removed memory leak detected with the help of coverity in dialog.c - fixed bug in applyFixings() in cons_varbound.c concerning tightening the bound of a variable left in a redundant constraint (bound change is forced now) - fixed bug in SCIPtightenVarLb/Ub() in scip.c concering forcing a bound change (bound improvement is checked now) - fixed bug in preprocessConstraintPairs() in cons_linear.c concerning updating the flags of the constraint that stayes in the problem (nonredundant information were lost before) - fixed bug with exponential running times due to complicated recursive multi-aggregation - fixed bug with memory reallocation in SCIPgetProbvarLinearSum() - improved stage checking for bound computation - fixed usage of command test for string comparision in check-scripts (now compatible with ubuntu) - corrected imlementation of SCIPlpiGetBasisInd() in lpi_clp.cpp (this fixes the bug that almost no Gomory cuts are found with Clp). - weakened two too strong asserts in lp.c concerning the LP result OBJLIMIT - fixed bug in cons_linear.c caused by comparing two infinity values during checking of using variable as slackvariable - tried to fix memory leak in dialog.c occuring from different versions of the readline/history libraries - corrected bug in var.c occuring during applying boundchanges in varUpdateAggregationBounds method - replaced sprintf and snprintf by SCIPsnprintf fixed potential bug with overlong strings - fixed bug in SCIPlpSolveAndEval(): allow more than one extra simplex step for getting an objlimit exceeding solution with fastmip - fixed bug in sepa_mir.c: size of testeddeltas-array was too small - removed bug for values greater than (-)infinity, heur_shifting.c, heur_intshifting.c, heur_rounding.c, heur_oneopt.c - removed bug for rhs/lhs greater than (-)infinity, cons_linear.c - removed bug caused by hashcomparison for non-sorted constraints, cons_linear.c - fixed bugs with wrong presolving due to cancellation in (res-)activities in cons_linear.c - removed possible memory leak in objdialog.cpp - fixed bug in preprocessing of SOS2 constraints (cons_sos2.c) - removed BOUNDSCALETOL adjustment in cons_linear.c. This fixes bug with slightly infeasible variable fixings in presolving; reliable resactivities should make the BOUNDSCALETOL relaxation redundant. - corrected bug in the case when soplex threw an exception in autopricing - removed "epsilontic" bug in cons_linear.c due to adjusting left/right hand side in applyfixing - fixed bug in SCIPvarGetOrigvarSum() concerning the corner case the a negated variable has no parent variable in original problem - fixed some SCIP_RETCODE bugs in reader_fix.c, reader_sol.c, reader_sos.c, and reader_zpl.c - fixed docu in type_reader.h - fixed bug with multi-aggregated variables which are de facto aggregated or fixed after flattening the aggregation tree - fixed bug with bound changes of variables in modifiable constraints during full dual presolving of linear conshdlr - increased compiler compatibility for C++ wrapper classed by adding extern "C" in obj*.cpp files and changing strlen calls to std::strlen - fixed bug with errors occurring in heuristic LPs. In opt mode a warning will be printed, abort in dbg mode SCIP version 1.00 ================= compiling: - added .exe extension to binaries of MinGW - added "LPS=none" for compiling SCIP without a LP solver - modified the default LP solver to be SoPlex instead of CPLEX - removed the ".static" extension associated to the LINK variable from the Makefile system (If you want to build makefiles for shared library generation, use the OPT variable. For example, you could create a makefile "make/make.linux.x86.gnu.opt-shared" and compile it with "make OPT=opt-shared".) - added version numbers to library files (There will be a softlink generated in the lib/ and bin/ directories without version number that point to the latest compiled version.) - made ZIMPL=true the default; if you do not want to include ZIMPL support, call "make ZIMPL=false" interface: - new callback method SCIPdialogFree() - new method SCIPreadSol() - new method SCIPgetVarRedcost() - new method SCIPnodeUpdateLowerboundLP() - linear and knapsack constraint handler may now deal with coefficients of value zero - parameters are now separated into basic and advanced, the latter ones have been moved to extra submenus - new method SCIPwriteMIP() - calling SCIPwriteLP is now possible in Solved Stage - new parameter "maxbounddist" for SCIPincludeSepa() and constructor ObjSepa() - new method SCIPsepaGetMaxbounddist() - removed parameter "branchdir" from SCIPbranchVar() - new parameters "leftchild", "eqchild", and "downchild" for SCIPbranchVar() - new method SCIPcalcNodeselPriority() - new parameter "estimate" for SCIPcreateChild() - removed method SCIPnodeGetPriority() - new method SCIPnodeGetEstimate() - new methods SCIPgetLocalOrigEstimate() and SCIPgetLocalTransEstimate() - new parameter "restart" for method SCIPfreeSolve() - new method SCIPnodeGetDomchg() - new methods SCIPboundchgGetNewbound(), SCIPboundchgGetVar(), SCIPboundchgGetBoundchgtype(), SCIPboundchgGetBoundtype(), SCIPboundchgIsRedundant(), SCIPdomchgGetNBoundchgs(), SCIPdomchgGetBoundchg() - new method SCIPisStopped() - SCIPgetVarStrongbranch() now also returns lperror == TRUE if the solving process should be stopped, e.g., because of a time limit - new method SCIProwIsInGlobalCutpool() - removed parameter "lowestboundfirst" from SCIPincludeNodesel() - replaced methods SCIPvarGetClosestVlb() and SCIPvarGetClosestVub() from pub_var.h by new methods SCIPgetVarClosestVlb() and SCIPgetVarClosestVlb() in scip.h - new method SCIPresetParams() - modified SCIP_SUBVERSION to be a number instead of a string (to be able to use #if SCIP_SUBVERSION >= ...) - SCIPsubversion() now returns an int instead of a const char* - new methods SCIPtightenVarLbGlobal() and SCIPtightenVarUbGlobal() - new method SCIPgetRootNode() (in combination with SCIPcutoffNode(), this allows the immediate finishing of the optimization) - new parameter "force" for SCIPtightenVarLb() and SCIPtightenVarUb() plugins: - new C templates disp_xxx.h and dialog_xxx.h, and C++ wrapper classes objdisp.h and objdialog.h, respectively - new improvement heuristic "oneopt" - improved performance of linear constraint propagation by delaying some floor/ceil calculations - new node selection rule "estimate" (best estimate search) - best estimate search is now used in all large neighborhood search heuristics - new heuristic "actconsdiving" following an idea of John Chinneck - new node selection rule "hybridestim" - improved performance of clique cut separator - modified reader "sol", st. files which where created via typing the order of commands 'set log *.sol', 'disp sol var -', 'set log cplex.log' in Cplex can now be read - modified probing presolver to do multiple cycles if called in subsequent runs - greatly improved performance of LP file reader by replacing string copies with pointer copies - changed sort algorithm in probing presolver - added flow cover separator - gomory cuts are now also separated for integral slack variables - less aggressive in Gomory cut separation - strong CG cuts are now also separated for integral slack variables - default dialog menu now includes the commands "set default" and "display parameters" - new dummy LP interface "lpi_none.c"; useful for running SCIP without a LP solver parameters: - new parameter "separating/clique/backtrackfreq" to speed up clique cut separation in heuristic fashion - new parameters "separating/*/maxbounddist" to have individual maxbounddist parameters per separator - changed default value of global "separating/maxbounddist" to 1.0 - new parameter "separating/redcost/continuous" - new parameter "heuristics/feaspump/maxstallloops" - priority parameters are now restricted to be in [INT_MIN/4,INT_MAX/4] to avoid overflow errors in comparison methods - new parameter "presolving/immrestartfac" - changed default value of "numerics/boundstreps" to 0.05 in order to avoid very long propagation loops on continuous variables - new parameter "nodeselection/childsel" to control the child selection - new parameters "heuristics/*diving/backtrack" to activate 1-level backtracking for most of the diving heuristics - increased priority of "estimate" node selector, such that this is the new default node selector - changed default value of "separating/objparalfac" to 0.01 for performance reasons - changed default values of "heuristics/*diving/backtrack to TRUE - changed default value of "nodeselection/restartdfs/stdpriority" to 10000 - changed meaning of parameter setting "nodeselection/childsel = l"; old meaning is now called 'r' - changed default value of "presolving/restartfac" to 0.05 - changed default value of "presolving/restartminred" to 0.10 - changed default value of "constraints/linear/propfreq" to 1 - changed default value of "separating/objparalfac" to 0.0001 - changed default value of "conflict/maxvarsfac" to 0.1 - changed default value of "conflict/useprop" to TRUE - changed default value of "conflict/useinflp" to TRUE - changed default value of "conflict/usepseudo" to TRUE - changed default value of "conflict/maxlploops" to 2 - changed default value of "conflict/lpiterations" to 10 - changed default value of "conflict/interconss" to -1 - changed default value of "conflict/reconvlevels" to -1 - changed default value of "conflict/settlelocal" to FALSE - new parameter "conflict/enable" to globally enable or disable conflict analysis - new parameters "constraints/linear/maxcardbounddist" and "constraints/knapsack/maxcardbounddist" features: - the doxygen documentation now has HowTo's for all plugin types - the doxygen documentation now contains a FAQ - SCIP now has a couple of specialized settings, all called scip_*.set - SCIP is now compatible to the Exception branch of SoPlex - presolving, cut separation, primal heuristics, and strong branching now better respect time limit - time limit is now forwarded to lp solving algorithm - added option to write node LP and MIP relaxations to LP file from interactive shell - modified cut selection code - cut conversion into linear constraints after a restart now works better - if possible, objective function is scaled to make objective value integral with gcd 1 - slightly modified bound substitution heuristic in SCIPcalcMIR() and SCIPcalcStrongCG() - slightly less conservative in numerics for SCIPmakeRowIntegral() - removed performance bottleneck with non-bfs based node selectors and large leaf queues at the cost of a small memory overhead (2 ints per node in the leaf queue); this improves performance quite a bit on instances that take a large number of branching nodes - slightly modified automatic constraint aging strategy - the documentation has now a TAB Modules; there you can find list of available constraint handles, presolvers, propagators, lpi interfaces, file readers, and so on fixed bugs: - fixed bug in rowScale() concerning deletion of almost zero coefficients - fixed bug in SCIPcutpoolAddNewRow() concerning update of minidx and maxidx of added row - removed wrong assert in bounddisjunction constraint enforcement - fixed bug with wrong bound changes of loose variables - fixed bug with aggregated variables in debug solution test - fixed numerical buf with slightly different LP optimum after resolving due to probing/diving - fixed bug in cmir and flowcover separator with variables which are currently not in the LP - weakened assert in primal.c in order to avoid numerical troubles - changed wrong assert in SCIPnodeAddBoundinfer() - fixed bug in intshifting and oneopt heuristic with variables which are currently not in the LP - fixed bug in integer objective seperator with restarts - fixed bug in integer objective seperator with dynamic columns - fixed numerical bug in propagator of varbound constraint handler - fixed numerical bug in rowScaling of lp.c, which possibly cut off feasible solutions - fixed bug with too long variable names - fixed bug with strange user descriptions of plugins - changed position of some asserts to prevent segmentation faults - SCIPgetAvgPseudocostCount() and SCIPgetAvgPseudocostCountCurrentRun() now return the average over all integer variables instead of all variables, since pseudo costs are not recorded for continuous variables - fixed wrong sorting of plugins with priorities close to INT_MIN or INT_MAX - replaced "line" by "read" in Makefile, since "line" is non-standard - fixed bug in variable bound constraint handler with changing bounds on multi-aggregated variables - fixed bug in variable bounds search and insertion method - fixed bug with LP size management in probing if column generation is used - fixed bug with branching rules that produce only one child with no changes to the problem - fixed bug in linear constraint handler: only tight cuts are transformed into linear constraints after restart - fixed bug in LP file reader with row names identical to section keywords - fixed bug that external relaxator is not reset appropriately for a new problem instance - fixed potential bugs due to errors in resolving the LP after diving or probing - removed wrong assert in function paramWrite() - fixed potential bugs in SCIPpriceLoop() and priceAndCutLoop(), st. now all LP solution stati are handled appropriately - fixed bug with uninitialized in check.awk - fixed bug with primal heuristics reducing the cutoff bound such that the current node is cut off - now it is possible to add original solutions - fixed bug that cut age was not reset to zero for violated cuts - fixed bugs with SCIPgetBestsol() returning NULL after a restart with user objective limit - fixed wrong status code in presence of user objective limit and a feasible solution that is not better than the limit - fixed bug regarding modifying bounds in original problem if negated original variables exist - fixed bug in ZIMPL file reader for multiple occurrences of a single variable in the objective function - fixed bug with deleting variables from the transformed problem that are contained in the implication graph - fixed bug in oneopt heuristic: must not be called on pseudo nodes if continuous variables are present - significantly improved performance of c-MIR and Gomory cuts by caching closest VLB and VUB info - fixed bug in root reduced cost fixing propagator that leads to an empty domain for a variable as a proof of optimality of the current incumbent - fixed bug in bounddisjunction constraint handler with propagation of multi-aggregated variables - fixed bug with almost integral multi-aggregation in dual presolve of linear constraint handler - fixed bug with numerics in update of min/maxactivity in linear constraint handler - fixed bug with numerics in linear constraint handler due to non-representable BOUNDSCALETOL - SCIPwrite{LP,MIP} may no longer be called after solving, since the LP data structures may not be valid - fixed potential bug with non-existent LP in SCIPwrite{LP,MIP} - fixed bug with multiple pending bound changes on some variable - fixed bug with fractional coefficients of binary variables in cont --> impl int upgrading SCIP version 0.90 ================= compiling: - added ncurses to the readline entries in the make/make.* files - added quotes to sed expressions in Makefile (needed under Windows) - modified makefiles for Windows/Intel - added automatic query script in the Makefile for soft-link names interface: - new parameter "solinfeasible" for constraint handler callback methods ENFOLP and ENFOPS - new method SCIPgetVerbLevel() - slightly changed the meaning of the result codes returned by external relaxators: if they modify the LP or tighten bounds of variables, they are not automatically be called again (it is assumed that they already made use of these changes). They are only called again, if they returned SCIP_SUSPENDED or if some other plugin modified the LP. - new parameter "escapecommand" for SCIPdialoghdlrAddHistory() - new method SCIPescapeString() - renamed all occurences of "removeable" by the correct English word "removable": SCIPconsIsRemovable(), SCIPsetConsRemovable(), SCIPvarIsRemovable(), SCIPcolIsRemovable(), SCIProwIsRemovable() - new parameter "sticktonode" in SCIPcreateCons(), SCIPcreateConsAnd(), SCIPcreateConsBounddisjunction(), SCIPcreateConsKnapsack(), SCIPcreateConsLinear(), SCIPcreateConsLogicor(), SCIPcreateConsOr(), SCIPcreateConsVarbound(), SCIPcreateConsXor(), SCIPcreateConsSetpart(), SCIPcreateConsSetpack(), SCIPcreateConsSetcover(): usually, you should set this to FALSE; if you want to add constraints as node markers with node data and, e.g., use the "activate" and "deactivate" callbacks to get informed about the activation and deactivation of the node, you should set this flag to TRUE in order to make sure, that the constraint will always be associated to the node and not moved to a more global node if this would be possible - removed method SCIPgetVarData(); use SCIPvarGetData() from pub_var.h instead - replaced callback parameter "inlploop" and "inplunging" by "heurtiming" in SCIP_DECL_HEUREXEC - replaced parameters "pseudonodes", "duringplunging", "duringlploop", and "afternode" by "timingmask" in SCIPincludeHeur() and constructor of ObjHeur() class use the following table to translate old settings into the new timingmask: PSEUDONODES DURINGPLUNGING DURINGLPLOOP AFTERNODE timingmask FALSE FALSE FALSE FALSE SCIP_HEURTIMING_BEFORENODE TRUE FALSE FALSE FALSE SCIP_HEURTIMING_BEFORENODE FALSE TRUE FALSE FALSE SCIP_HEURTIMING_BEFORENODE TRUE TRUE FALSE FALSE SCIP_HEURTIMING_BEFORENODE FALSE FALSE TRUE FALSE SCIP_HEURTIMING_BEFORENODE | SCIP_HEURTIMING_DURINGLPLOOP TRUE FALSE TRUE FALSE SCIP_HEURTIMING_BEFORENODE | SCIP_HEURTIMING_DURINGLPLOOP FALSE TRUE TRUE FALSE SCIP_HEURTIMING_BEFORENODE | SCIP_HEURTIMING_DURINGLPLOOP TRUE TRUE TRUE FALSE SCIP_HEURTIMING_BEFORENODE | SCIP_HEURTIMING_DURINGLPLOOP FALSE FALSE FALSE TRUE SCIP_HEURTIMING_AFTERLPPLUNGE TRUE FALSE FALSE TRUE SCIP_HEURTIMING_AFTERPLUNGE FALSE TRUE FALSE TRUE SCIP_HEURTIMING_AFTERLPNODE TRUE TRUE FALSE TRUE SCIP_HEURTIMING_AFTERNODE FALSE FALSE TRUE TRUE SCIP_HEURTIMING_AFTERLPPLUNGE | SCIP_HEURTIMING_DURINGLPLOOP TRUE FALSE TRUE TRUE SCIP_HEURTIMING_AFTERPLUNGE | SCIP_HEURTIMING_DURINGLPLOOP FALSE TRUE TRUE TRUE SCIP_HEURTIMING_AFTERLPNODE | SCIP_HEURTIMING_DURINGLPLOOP TRUE TRUE TRUE TRUE SCIP_HEURTIMING_AFTERNODE | SCIP_HEURTIMING_DURINGLPLOOP - new calls SCIPgetLPBInvCol() and SCIPgetLPBInvACol() to access the basis inverse and simplex tableau columnwise - new parameter "ndomredsfound" of SCIPpropagateProbing() - new parameters "fixintegralrhs", "maxfrac", "mksetcoefs", and "fracnotinrange" in SCIPcalcMIR() - modified SCIPfixVar() such that in problem creation stage it will change the bounds as requested even if the fixing value is outside of the current bounds - new methods SCIPgetGlobalCutpool(), SCIPgetPoolCuts(), SCIPcutpoolGetCuts(), SCIPcutGetRow(), and SCIPcutGetAge() - slightly changed semantics of SCIPaddConsNode() and SCIPaddConsLocal(), such that a constraint which is added to the root node now enters the global problem (and is still existing after a restart) - new methods SCIPconsGetNLocksPos() and SCIPconsGetNLocksNeg() plugins: - new primal heuristic "rens" - new primal heuristic "mutation" - slightly modified crossover and rins heuristics - improved presolving of and, or, and xor constraints - improved performance of intdiving heuristic - new primal heuristic "veclendiving" - improved heuristic "octane" - improved heuristic "shifting" - slightly modified rens and localbranching heuristics - modified guided diving heuristic such that it equals the original version of the heuristic (i.e., round in direction of the current incumbent solution instead of the average of all primal feasible solutions) - modified c-MIR cut separator to more closely resemble the original version of Marchand and Wolsey - implemented additional dual presolving in linear constraint handler - slightly modified presolving of varbound constraint handler - c-MIR cuts try now to scale the cut to integral values; however, cuts are still generated if this fails - ID character for intdiving heuristic is now 'I' - new heuristic "intshifting" (ID character 'i') parameters: - new parameter "reading/zplreader/changedir" to control behavior of path switching of ZIMPL file reader - new parameter "reading/zplreader/parameters" to pass additional parameters to ZIMPL - new parameter "propagating/abortoncutoff" - changed default value of "heuristics/octane/usediffray" to FALSE - new parameter "heuristics/octane/useavgwgtray" - removed parameter "heuristics/octane/usediffbwray" - renamed parameter "heuristics/octane/useavgray" to "heuristics/octane/useavgnbray" - new parameter "heuristics/octane/useavgray" - changed default value of "heuristics/rens/binarybounds" to TRUE - changed default value of "heuristics/octane/freq" to -1 in order to deactivate Octane - new parameter "separating/cmir/aggrtol" - new parameter "separating/cmir/fixintegralrhs" - new parameter "separating/cmir/densityscore" - new parameter "separating/maxruns" - new parameters "conflict/restartnum" and "conflict/restartfac" - parameter "heuristics/feaspump/maxsols" is now strict, i.e., if n solutions were already found, the feasibility pump starts to work only if maxsols <= n, instead of maxsols < n - new parameter "presolving/restartminred" which forbids another restart if the last one was not successful enough - new parameter "limits/absgap" to define an absolute gap limit features: - primal heuristics that run before the node is solved now know already whether the LP will be solved at the current node or not - command shell now understands escape characters ",', and \ which makes it possible to read in files with spaces in the name - updated XPress interface to XPress-MP 17 (contributed by Michael Perregaard) - the EXITSOL callback of the plugins is now called before the LP and the global cut pool are freed - possibility of SAT-like restarts after a number of conflict constraints have been found - in the root node of the very first run, heuristics with timing AFTERNODELPNODE, AFTERLPPLUNGE, AFTERPSEUDONODE, and AFTERPSEUDOPLUNGE are now called before the enforcement of the constraint handlers, in particular before the branching rules; in this way, the branching rule can already benefit from a tighter primal bound - if a heuristic found a better solution after the LP loop (and in particular the AFTERNODE heuristics in the root node of the very first run, see above), domain propagation and LP solving is triggered again; this allows for additional reduced cost tightening and other dual propagations - hard-coded relative objective gain to consider a separation loop to be stalling is now changed from 1e-3 to 1e-4, which means that separation is not aborted as early as before fixed bugs: - fixed bug with adding constraints with INITIAL=true and separating them afterwards, which lead to a second addition of the constraint's relaxation in the child node - fixed bug in cmir cut separator, that 8*delta was not tried - fixed bug in cmir cut separator with wrong sign of slack in row score function - fixed bug with string pointer copy instead of string content duplication in constructors of C++ wrapper classes - fixed bug in CPLEX interface with basis access methods that dualopt has to be called for more error status codes - fixed bug with inserting two variable bounds of the same type on the same variable with the same bounding variable but with different sign of coefficient (e.g., x <= 10*z + 5 and x <= -5*z + 10); in previous version, one of the two was removed, although both have a useful meaning; now, we keep both, and detect a stronger global bound in the implication graph presolving - fixed bug in cmir cut separator with weights fixed to zero, thus making the current aggregation invalid - fixed bug that SCIPvarGetAvgSol() always returned the upper bound (affected guided diving heuristic) - fixed bug in RENS, RINS, Local Branching, Crossover, and Mutation heuristics with wrong variable - subvariable assignments - fixed bug in cmir cut separator with wrong calculation of cut efficacies - objective function is now also checked for integrality after problem transformation (fixed a bug that a solution which was generated between transformation and presolving for an integral objective function did not reduce the cutoff bound by one) - fixed a bug with cmir cut efficacy calculation (however, on my first tests, the performance reduced slightly!) - fixed bug in infeasible/bound-exceeding LP conflict analysis if the bounds were relaxed in diving (happens in intshifting heuristic) - too large deltas are now also rejected in c-MIR cut separation - separation LPs are now immediately resolved after a bound change was generated by a cut separator; before, the separation round was prematurely aborted, which means that a separation round limit was sometimes reached very quickly and some of the separators were not even called a single time SCIP version 0.82 ================= compiling: - removed ncurses and pthread libraries from the Makefile; pthread is now only linked if CPLEX is used interface: - new method SCIPsolveProbingLPWithPricing() - new methods SCIPcolGetMinPrimsol() and SCIPcolGetMaxPrimsol() - new method SCIPgetColRedcost() - new method SCIPvarGetRootRedcost() - new methods SCIPgetLPRootObjval(), SCIPgetLPRootColumnObjval(), and SCIPgetLPRootLooseObjval() - new methods SCIPchgVarLbRoot() and SCIPchgVarUbRoot() - new method SCIPinRepropagation() - new methods SCIPgetAvgPseudocostScore(), SCIPgetAvgPseudocostScoreCurrentRun(), SCIPgetAvgConflictScore(), SCIPgetAvgConflictScoreCurrentRun(), SCIPgetAvgInferenceScore(), SCIPgetAvgInferenceScoreCurrentRun(), SCIPgetAvgCutoffScore(), and SCIPgetAvgCutoffScoreCurrentRun() - new methods SCIPaddDialogInputLine() and SCIPaddDialogHistoryLine() - method SCIPgetNConflictClausesFound() renamed to SCIPgetNConflictConssFound() - method SCIPgetNConflictClausesFoundNode() renamed to SCIPgetNConflictConssFoundNode() - method SCIPgetNConflictClausesApplied() renamed to SCIPgetNConflictConssApplied() - new method SCIPgetFocusDepth() - methods SCIPisLbBetter() and SCIPisUbBetter() have an additional parameter and slightly different meaning (they now compare the bound improvement *relatively* to the width of the domain and the bound itself) - new solution status code SCIP_STATUS_STALLNODELIMIT - slightly modified semantics of the CONSINITLP callback in the constraint handlers - marking a constraint to be "initial" now means in addition, that if the constraint is added to a local node it will enter the LP at the time the node is first processed, even if parameters forbid separation at this node - SCIPgetNSols() now returns an int instead of SCIP_Longint - new method SCIPtransformProb() to create the transformed problem; enables the user, e.g., to add primal solutions before the presolving begins - method SCIPreadProb() does not call SCIPfreeTransform() anymore; file readers that want to extend the existing problem must now call SCIPfreeTransform() themselves before modifying the original problem - method SCIPgetBinvarRepresentative() can now also be called in problem creation stage - additional parameter "maxpricerounds" in method SCIPsolveProbingLPWithPricing() - changed name of method SCIPpresolGetNVarTypes() to SCIPpresolGetNChgVarTypes() - changed name of method SCIPconshdlrGetNVarTypes() to SCIPconshdlrGetNChgVarTypes() - new method SCIPcreateSolCopy() - new method SCIPareSolsEqual() - method SCIPsplitFilenames() now treats both versions of slashes, '/' and '\', as directory delimiters (under MinGW and CygWin, both are valid; so, we cannot treat file names anymore where the other slash is used as a regular character) plugins: - new primal heuristic "shifting" - new separator "redcost" which replaces the internal reduced cost strengthening - new propagator "rootredcost" which applies reduced cost fixing at the root node whenever a best new primal solution was found - new constraint handler "bounddisjunction" - new methods SCIPgetRowKnapsack(), SCIPgetRowLinear(), SCIPgetRowLogicor(), SCIPgetRowSetppc(), and SCIPgetRowVarbound() for obtaining the linear relaxation of a corresponding constraint - new methods SCIPgetNVarsAnd() and SCIPgetVarsAnd() - new methods SCIPgetWeightsKnapsack(), SCIPgetNVarsKnapsack(), SCIPgetVarsKnapsack(), and SCIPgetWeightsKnapsack() - new methods SCIPgetNVarsLinear(), SCIPgetVarsLinear(), and SCIPgetValsLinear() - new methods SCIPgetNVarsOr() and SCIPgetVarsOr() - new methods SCIPgetLhsVarbound(), SCIPgetRhsVarbound(), SCIPgetVarVarbound(), SCIPgetVbdvarVarbound(), and SCIPgetVbdcoefVarbound() - new methods SCIPgetNVarsXor() and SCIPgetVarsXor() - knapsack presolver now generates cliques in the clique table (this essentially solves neos1.mps) - LP and MPS file readers are now able to parse lazy constraints and user cuts sections - diving heuristics abort earlier (did not come back in reasonable time on fast0507) - renamed "sol" file reader to "fix" file reader (reads partial solution files and fixes variables to the given values) - added "sol" file reader which reads complete solution files and adds the solutions to the solution pool - additional flag "delay" for pricers - new presolver "inttobinary" - new display column "lpobj" parameters: - new parameter constraints/linear/separateall - new parameter conflict/lpiterations - new parameter conflict/keepreprop - removed parameter propagating/redcostfreq, because reduced cost strengthening is now an external separator plugin - new parameters branching/relpscost/conflictweight, branching/relpscost/inferenceweight, branching/relpscost/cutoffweight, and branching/relpscost/pscostweight - new parameter conflict/settlelocal - removed parameter conflict/maxunfixed - parameter conflict/maxclauses renamed to conflict/maxconss - parameter conflict/interclauses renamed to conflict/interconss - parameter conflict/reconvclauses replaced by conflict/reconvlevels - new parameter conflict/depthscorefac - parameter conflict/uselp replaced by conflict/useinflp and conflict/useboundlp - new parameter limits/stallnodes - changed default value of constraints/obsoleteage to -1 - changed default value of branching/relpscost/conflictweight to 0.01 - changed default value of branching/relpscost/inferenceweight to 0.0001 - changed default value of branching/relpscost/cutoffweight to 0.0001 - in bfs node selector, parameter "minplungedepth" is now stronger than "maxplungedepth" if they conflict features: - extensions to the LP are kept even if the LP is not solved at the current node; however, if the LP turned out to be numerically instable, the extensions of the current node are still discarded - slightly changed priorities of constraint handlers - command line syntax changed to support batch modus without piping stdin with "<" or "|" operators - now, conflict constraints are also created if they were generated in strong branching or diving with insertion depth equal to the current depth - advanced command line syntax: -l <logfile> : copy output into log file -q : suppress screen messages -s <settings> : load parameter settings (.set) file -f <problem> : load and solve problem file -b <batchfile>: load and execute dialog command batch file (can be used multiple times) -c "command" : execute single line of dialog commands (can be used multiple times) - added removal of bound-redundant rows from the LP during root node LP solving loop fixed bugs: - fixed bug with invalid lazy updates after a restart where the LP is not solved again (e.g., due to all variables being fixed) - fixed bug in MPS file reader with OBJSENSE - fixed numerical bug in SCIPrealToRational() [thanks to Anders Schack-Nielsen] - fixed bug in crossover heuristic with negative timelimit - fixed bugs resulting from inactive general integer variables being member of the variable bounds array of a variable - removed bug in conflict analysis with wrong redundancy check - fixed bug that unexpected end of stdin (Ctrl-D or piped-in file without "quit" command) gives a segmentation fault - fixed bug in knapsack constraint disaggregation that may lead to acceptance of infeasible solutions - fixed bug with inconsistent data structures after a global bound was changed at a local subproblem and the local bounds are not contained anymore in the new global bounds - fixed bug in LP reader with potentially uninitialized pointers [thanks to Martin Mueller] - fixed bug in SCIPcliqueSearchVar() [thanks to Anders Schack-Nielsen] - fixed bug in SCIPcliqueAddVar() [thanks to Anders Schack-Nielsen] - fixed bug in updatePseudocost() with wrong lpgain distribution on multiple branching variables [thanks to Anders Schack-Nielsen] - it is now possible to branch on constraints without the risk of going into an infinite loop, because constraints marked as "initial" will be put to the LP relaxation (of the child nodes) even if separation is prohibited by the parameter settings - fixed bug with missing LP size updates after pricing or cut separation in probing [thanks to Marc Nuenkesser] - fixed bug that locally valid varbound constraints produce VLB/VUB entries [thanks to Anders Schack-Nielsen] - fixed bug in knapsack constraint handler where a modifiable constraint may be declared redundant - fixed bug in knapsack presolving with redundancy check after applyFixings() [thanks to Anders Schack-Nielsen] - fixed bug in objconshdlr.h where member variable scip_maxprerounds_ was declared as an SCIP_Bool instead of an int - fixed bug in CPLEX interface with getting basis information after the LP was modified and restored - fixed bug in knapsack separator with empty initial covers - fixed bug that SCIPgetLPSolstat() returns a valid status code even if the LP was not yet constructed for the current node - fixed bug with adding implications that fix the implication variable to the opposite value (due to the bug, it was returned that the whole problem is infeasible) - branching on nearly-integral variables is now avoided in relpscost branching, which lead to a numerical assertion - removed wrong assert in varRemoveImplicsVbs() - fixed bug with updating LP size in probing - fixed dependency generation in example Makefiles SCIP version 0.81 ================= examples: - added two small pricer examples (for C and C++) - updated example code (s.t. it compiles again) interface: - new method SCIPgetCuts() - callback method CONSSEPA of constraint handler was split into two methods CONSSEPALP and CONSSEPASOL - replaced method SCIPconshdlrWasSeparationDelayed() by two methods SCIPconshdlrWasLPSeparationDelayed() and SCIPconshdlrWasSolSeparationDelayed() - callback method SEPAEXEC of separator was split into two methods SEPAEXECLP and SEPAEXECSOL - replaced method SCIPsepaWasDelayed() by SCIPsepaWasLPDelayed() and SCIPsepaWasSolDelayed() - additional parameter "sol" for methods SCIPaddCut(), SCIPgetCutEfficacy(), and SCIPisCutEfficacious() - additional parameter "sol" for method SCIPseparateKnapsackCover() - new methods SCIPsepaGetNConssFound() and SCIPsepaGetNDomredsFound() - new methods SCIPgetVarConflictScore(), and SCIPgetVarConflictScoreCurrentRun() - new method SCIPvarSetData() - new method SCIPcreateUnknownSol() - primal solutions may now contain values marked to be unknown (value is SCIP_UNKNOWN); unknown values don't contribute to the objective value of the solution; an unknown solution value should be treated as an arbitrary value in the variable's bounds, e.g., in the calculation of the feasibility of a constraint, a value inside the variable's bounds should be selected that makes the constraint as feasible as possible - new method SCIPgetNConflictClausesFoundNode() - new methods SCIPvarSetDelorigData(), SCIPvarSetTransData(), and SCIPvarSetDeltransData() - new method SCIPvarHasBinaryImplic() - renamed method SCIPgetNGlobalConss() to SCIPgetNConss() - added methods SCIPgetConss(), SCIPgetNOrigConss(), and SCIPgetOrigConss() - new parameter "printzeros" for methods SCIPprintSol(), SCIPprintTransSol(), SCIPprintBestSol(), and SCIPprintBestTransSol() - new methods SCIPgetFixedVars() and SCIPgetNFixedVars() - new method SCIPconstructLP() to force constructing the LP of the current node - new method SCIPisLPConstructed() plugins: - new presolver "implics" to find bound changes and aggregations out of the implication graph - logic or constraint handler now adds implications on clauses with 2 literals to the implication graph - and/or constraint handlers now add implications to the implication graph - xor constraint handler now uses stronger LP relaxation without auxiliary variable for xor constraint with 2 operands - modified probing order in probing presolver - LP file reader now accepts the keyword "Integer" for defining the start of the integer variables section - added preliminary version of "intdiving" heuristic (disabled in default settings) - slightly modified restartdfs node selector - added crossover heuristic - new file reader for (partial) solutions - added "write statistics" command to default user dialogs parameters: - modified meaning of parameter presolving/probing/maxtotaluseless - new parameter branching/inference/conflictweight - heuristics with freq = 0 and freqofs > 0 are now called in depth level freqofs instead of being called in the root node - added some parameters in local branching and RINS heuristic - new parameter values 'p'rimal simplex and 'd'ual simplex in lp/initalgorithm and lp/resolvealgorithm features: - changed handling of added constraints in separation calls - modified bookkeeping of locally added and disabled constraints such that the order of enabling and disabling constraints stays the same - improved performance of the priority queue in conflict analysis Makefile and Compilation: - included version number in binary file name - tried to make the code Windows compatible fixed bugs: - fixed bug in ZIMPL model reader with wrong chdir, if .zpl file is in current directory - fixed bug in LP file reader with signed values without space between sign and value (e.g. "+2x" instead of "+ 2x") - fixed various bugs in LP file reader - also removed history_length, if NO_REMOVE_HISTORY is defined to support older versions of the readline library - removed bug in implication addition - fixed wrong assert with implications that imply a fixed variable - fixed numerics in check method of linear constraint handler - hopefully fixed bug with wrong path slash '/' under Windows - fixed numerics in probing and linear constraint handler (rentacar was detected to be infeasible in presolving) - fixed bug with calling heuristics in depths smaller than their frequency offset - fixed bug with aggregating fixed variables - fixed bugs in local branching and RINS heuristic - fixed bug in LP file reader with explicit zero coefficients - fixed bug in transitive implication addition - fixed bug with numerical error in LP resolve after probing or diving known bugs: - if one uses column generation and restarts, a solution that contains variables that are only present in the transformed problem (i.e., variables that were generated by a pricer) is not pulled back into the original space correctly, since the priced variables have no original counterpart SCIP version 0.80 ================= interface: - MAJOR CHANGE: preceeded all data types with "SCIP_" - you may use shell script reptypes_scip.sh to rename the SCIP data types in your own source code (But use with care! Create a backup copy of your source first!) - additional parameter "validnode" for SCIPaddConsLocal() and SCIPaddConsNode() - new method SCIPgetNConflictClausesApplied() - new method SCIPdelVar() - new method SCIPgetVarStrongbranchLPAge() - new method SCIPgetNConflictClausesApplied() - new event type SCIP_EVENTTYPE_VARDELETED - new method SCIPconsGetValidDepth() - new method SCIPhashtableExists() - method SCIPhashtableRemove() can now also be called, if the element does not exist in the table - new method SCIPhashmapExists() - method SCIPhashmapRemove() can now also be called, if the element does not exist in the map - new method SCIPvarIsTransformedOrigvar() - new method SCIPvarIsDeleted() - new callback parameter "validnode" for the CONFLICTEXEC method of conflict handlers, which should be passed to SCIPaddConsNode() - new method SCIPnodeGetNumber() - new method SCIPsolveProbingLP() to solve the LP in a probing node (enables mixing of propagation and LP solving for diving heuristics) - new method SCIProwGetDualfarkas() - new method SCIPgetCurrentNode() - new method SCIPinterruptSolve() - new file i/o methods SCIPfopen(), SCIPfclose(), SCIPfprintf(), ... that operate on the data type SCIPFILE; these methods automatically use zlib methods if the zlib is enabled - additional parameter "branchdir" for SCIPbranchVar() - replaced method SCIPmessage() by SCIPverbMessage() with additional parameter "file" - new methods SCIPerrorMessage(), SCIPwarningMessage(), SCIPdialogMessage(), and SCIPinfoMessage() - new methods SCIPsetMessagehdlr(), SCIPsetDefaultMessagehdlr(), and SCIPgetMessagehdlr() - new method SCIPpropagateProbingImplications() - new methods SCIPvarGetNCliques(), SCIPvarGetCliques(), SCIPvarsHaveCommonClique(), SCIPvarHasImplic() - new methods SCIPcliqueGetNVars(), SCIPcliqueGetVars(), SCIPcliqueGetValues(), SCIPcliqueGetId() - new methods SCIPaddClique(), SCIPcalcCliquePartition() - new event SCIP_EVENTTYPE_IMPLADDED - new method SCIPgetLPI() which makes all methods in scip/lpi.h available to the user - put block memory shell and tclique algorithm into separate subdirectories - new parameter "duringlploop" of SCIPincludeHeur() - heuristics can now run during the price-and-cut loop at a node - new methods SCIPgetRandomInt() and SCIPgetRandomReal() - new method SCIPstrtok() - new methods SCIPsetConsInitial(), SCIPsetConsSeparated(), SCIPsetConsEnforced(), SCIPsetConsChecked(), SCIPsetConsPropagated(), SCIPsetConsLocal(), SCIPsetConsDynamic(), SCIPsetConsRemoveable() - new method SCIPheurGetNBestSolsFound() - new event types SCIP_EVENTTYPE_GLBCHANGED and SCIP_EVENTTYPE_GUBCHANGED plugins: - added command "write solution" to default dialog - changed restart dfs nodeselector to sort leaves by node number instead of node depth to aviod jumping around in the search tree after a restart was applied and the current dive ended due to infeasibility - removed "objfeaspump" heuristic, because the functionality can be achieved by using the "feaspump" heuristic - diving heuristics are now applying propagation after each bound change - new primal heuristic "octane" - slightly changed feaspump heuristic, s.t. after finding a new best solution the target integral solution is modified randomly - new method SCIPgetDualfarkasLinear() of linear constraint handler - new method SCIPgetDualfarkasLogicor() of logicor constraint handler - new method SCIPgetDualfarkasSetppc() of setppc constraint handler - new method SCIPgetDualsolKnapsack() of knapsack constraint handler - new method SCIPgetDualfarkasKnapsack() of knapsack constraint handler - new method SCIPgetDualsolVarbound() of varbound constraint handler - new method SCIPgetDualfarkasVarbound() of varbound constraint handler - new Message Handler plugin - added commands "write problem" and "write transproblem" to default dialog - modified probing presolver to not add implications that are already included in the implication graph and clique table - added file reader for LP format parameters: - replaced parameter presolving/restartbdchgs with parameters presolving/maxrestarts and presolving/restartfac - new parameter conflict/maxclauses - new parameter conflict/allowlocal - new parameter branching/fullstrong/reevalage - changed default values of heuristics/*/maxdiveavgquot and heuristics/*/maxdiveavgquotnosol to 0 - additional setting SCIP_VERBLEVEL_DIALOG in display/verblevel parameter - additional LP pricing setting "partial" - parameters constraints/agelimit and constraints/obsoleteage now iterprete the value 0 as a dynamic setting - changed default values of constraints/agelimit and constraints/obsoleteage to 0 - changed default values of heuristics/objpscostdiving/maxsols and heuristics/rootsoldiving/maxsols to -1 - new parameter constraints/knapsack/disaggregation - changed default value of separating/strongcg/maxroundsroot to 20 - changed default value of separating/cmir/maxroundsroot to 10 - new parameters separating/cmir/maxfails, separating/cmir/maxfailsroot and separating/cmir/trynegscaling - number of fractional variables included in parameter separating/maxstallrounds - changed default value of separating/maxstallrounds to 5 - new parameter presolving/probing/maxtotaluseless - changed default value of presolving/probing/maxfixings to 50 - changed default parameter values to MIP settings: - conflict/useprop = FALSE - conflict/usepseudo = FALSE - display/verblevel = 4 - separating/poolfreq = 0 - constraints/linear/sepafreq = 0 - constraints/and/sepafreq = 0 - constraints/conjunction/sepafreq = 0 - constraints/knapsack/sepafreq = 0 - constraints/knapsack/sepacardfreq = 0 - constraints/logicor/sepafreq = 0 - constraints/or/sepafreq = 0 - constraints/setppc/sepafreq = 0 - constraints/varbound/sepafreq = 0 - constraints/xor/sepafreq = 0 - separating/clique/freq = 0 - separating/cmir/freq = 0 - separating/gomory/freq = 0 - separating/impliedbounds/freq = 0 - separating/strongcg/freq = 0 - replaced parameter constraints/linear/maxpresolaggrrounds with constraints/linear/maxpresolpairrounds - changed default value of constraints/linear/maxaggrnormscale to 0.0, which means to not apply aggregation features: - reactivated multiaggregation in cons_linear.c on binary variables again (possible due to bug fix below) - introduced subversion string - adding variable bounds automatically adds the corresponding implication - conflict clauses are now collected in a conflict store, redundant clauses are eliminated, and only the best "conflict/maxclauses" clauses are added permanently to the problem; the remaining clauses are only added temporarily, if they can be used for repropagation - improved debugging for infeasible cuts and propagations, given a primal feasible solution - slightly changed LP resolving loop in conflict analysis - diving heuristics now apply propagation at each step - if CPLEX returns that the LP exceeds the bound and if no additional LP solves are allowed in conflict analysis, we have to perform one additional simplex iteration to get the dual solution that actually violates the objective limit - modified the influence of the depth level in conflict analysis - new event type SCIP_EVENTTYPE_PRESOLVEROUND - added zlib support - replaced all abort() calls by SCIPABORT(); this is defined in def.h to be assert(FALSE) - modified the Makefile to accept an additional parameter VERBOSE={true,false} - improved knapsack cover separation - changed linear constraint presolving s.t. redundant sides are not removed if constraint is an equality - incorporated clique and implication information in knapsack constraint presolving - improved performance of c-MIR separator - cut pool is now also separated in root node (to find cuts again that were removed from the LP due to aging) - improved preprocessing of variable bounds constraints - removed transitive clique generation, because this produces way too many cliques - improved preprocessing abort criteria - added flags READLINE=true/false, ZLIB=true/false, ZIMPL=true/false to Makefile - added possibility to disable certain features by using "make USRFLAGS=-DNO_REMOVE_HISTORY", "make USRFLAGS=-DNO_SIGACTION", "make USRFLAGS=-DNO_RAND_R", or "make USRFLAGS=-DNO_STRTOK_R" - linear constraint handler now catches events of variables after the problem was completely transformed in order to avoid the whole bunch of LOCKSCHANGED events that are generated at problem transformation stage - added redundancy detection for pairs of constraints in setppc constraint handler fixed bugs: - LP primal feasibility for bounds is now defined as absolute measure (was relative to the bound before); this fixes a bug (see alu8_9.mps), that an LP with an integral variable fixed to a large value yields an accepted solution with that variable slightly different than the fixed value; the integrality feasibility condition is measured with absolute differences, which leads to the fixed integer variable being fractional; this leads to an error if branching is performed on this variable - locally fixed variables are no longer used as branching candidates even if their LP solution value is fractional (due to numerical reasons, see above) - fixed minor bugs in debug code of primal.c and sol.c - variables that are being multiaggregated are now automatically removed from all other variables' variable bound and implication arrays; this fixes bugs with methods, that rely on the fact, that the entries in the variable bound and implication arrays are active variables only - aggregations are now always performed in a way, such that the variable of more general type is aggregated (with type generality being cont > implint > int > bin); in this way, a binary variable's representant is always binary (which was not the case before, and resulted in a bug in SCIPgetBinvarRepresentative()) - removed wrong asserts from lpi_cpx.c - global bound changes now lead to the removal of redundant implications (such that the asserts in sepa_implbounds.c are now correct) - due to usage of variable bounds, SCIPcalcMIR() may return LOOSE variables in the cut -> modified sepa_cmir.c, sepa_gomory.c, and sepa_strongcg.c to use SCIPcreateEmptyRow() and SCIPaddVarsToRow() instead of SCIPcreateRow() which only works for COLs - removed bug in presol_probing.c: the vars of the sorted variables array have to be captured - fixed bug in the output of solutions with priced variables - fixed bug in propagation with parameters prop_maxrounds and prop_maxroundsroot - removed wrong assertion in varAddImplic() - conflict analysis can now handle errors in LP solving calls - fixed bug in linear constraint handler with variables fixed to infinity - fixed bug with potential infinite loop if a separator is delayed and the LP is infeasible - fixed numerical bug in pseudo objective propagator with only slightly tightened bounds - fixed bug with constraint handlers that can only enforce their constraints by adding cuts, but the maximal number of cuts to separate is set to 0; now, cuts that are generated in the constraint enforcement are used in any case - removed bug in SCIPvarAddVlb() and SCIPvarAddVub() with fractional vlb/vubcoefs - removed bug that an LP might be declared to be solved even if it was marked erroneous due to numerical problems - fixed bug with redundant self implications that wrongly lead to the detection of infeasibility - fixed bug that primal or dual rays might not be available because the wrong solver was used - included message.o in LPI library, s.t. one can link this library indepentent of SCIP - fixed bug that if diving heuristic that changes the objective values finds a solution, the cutoff is reinstalled in the LP solver (although the objective value has no meaning due to the objective function modification) - fixed bug in knapsack constraint presolving with tightening coefficients and capacity - fixed bug with modifiable constraints in linear constraint handler preprocessing - fixed bug in clique separator that reduced performance - increased performance of clique separator by allowing only a certain number of zero-weighted fill ins - fixed bug in linear constraint handler that global activities are not updated after global bound changes SCIP version 0.79 ================= interface: - constraint handler callback methods CONSLOCK and CONSUNLOCK are replaced by a single method CONSLOCK with the number of locks being positive or negative - methods SCIPvarLock(), SCIPvarLockDown(), SCIPvarLockUp(), SCIPvarLockBoth(), SCIPvarUnlock(), SCIPvarUnlockDown(), SCIPvarUnlockUp(), and SCIPvarUnlockBoth() are replaced by SCIPaddVarLocks() which returns a RETCODE - methods SCIPvarLockDownCons(), SCIPvarLockUpCons(), SCIPvarUnlockDownCons(), and SCIPvarUnlockUpCons() are replaced by SCIPlockVarCons() and SCIPunlockVarCons() which return a RETCODE - methods SCIPlockConsVars() and SCIPunlockConsVars() replaced with method SCIPaddConsLocks() - additional parameter "maxproprounds" in SCIPpropagateProbing() - changed memory interface (see memory.h), MEMHDR is now called BLKMEM - additional parameter "aggregated" in SCIPmultiaggregateVars() - new method SCIPgetObjNorm() - new methods SCIPvarGetLbOriginal() and SCIPvarGetUbOriginal() for original problem variables - methods SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal() now return the corresponding values of the transformed problem or current subproblem even for original problem variables - removed method SCIPsolGetObj() - use SCIPgetSolOrigObj() or SCIPgetSolTransObj() instead - additional parameter "checkbounds" for SCIPtrySol(), SCIPtrySolFree(), SCIPcheckSol() - new method SCIPcreateOrigSol() - new method SCIPwriteImplicationConflictGraph() - new callback methods INITSOL and EXITSOL for variable pricers, primal heuristics, conflict handlers, relaxators, separators, propagators, event handlers, node selectors, and display columns - new parameter delay for presolvers - new parameter delaypresol for constraint handlers - new possible result SCIP_DELAYED for EXEC method of separators, presolvers, and propagators, and SEPA, PROP, and PRESOL methods of constraint handlers - new methods SCIPsepaIsDelayed(), SCIPsepaWasDelayed(), SCIPpropIsDelayed(), SCIPpropWasDelayed(), SCIPpresolIsDelayed(), SCIPpresolWasDelayed(), SCIPconshdlrIsSeparationDelayed(), SCIPconshdlrIsPropagationDelayed(), SCIPconshdlrIsPresolvingDelayed(), SCIPconshdlrWasSeparationDelayed(), SCIPconshdlrWasPropagationDelayed(), and SCIPconshdlrWasPresolvingDelayed() - new method SCIPinProbing() - new method SCIPgetProbName() - source code was moved into subdirectories: replace includes #include "scip.h" by #include "scip/scip.h" and #include "objscip.h" by #include "objscip/objscip.h"; This should allow a user to have include files of the same name as the ones of SCIP, e.g. "tree.h" or "var.h". - method SCIPreadProb() does not free the current problem - this is done in SCIPcreateProb() now, which is usually called by a problem reader; in this way, a reader can generate "extra information" for the current problem, s.t. the full problem information can be distributed to different files read by different readers - methods SCIPgetVarStrongbranch() and SCIPgetVarStrongbranchLast() now have two additional parameters that can be used to check, whether the returned values are correct dual bounds - new method SCIPisLPSolBasic() to check, whether the current LP solution is basic (i.e. due to a simplex algorithm or barrier with crossover) - event handlers are now available as C++ wrapper class - method SCIPconshdlrGetNConss() is replaced by SCIPconshdlrGetNActiveConss() (returning the number of active constraints); method SCIPconshdlrGetNConss() does now return the total number of existing constraints, active and inactive - method SCIPconshdlrGetStartNConss() is now called SCIPconshdlrGetStartNActiveConss() - method SCIPconshdlrGetMaxNConss() is now called SCIPconshdlrGetMaxNActiveConss() - new flag "afterrelaxation" for primal heuristics - method SCIPdisableConsNode() is replaced by SCIPdelConsNode() - method SCIPdisableConsLocal() is replaced by SCIPdelConsLocal() - new method SCIPenableCons() - new method SCIPdisableCons() - new method SCIPenableConsSeparation() - new method SCIPdisableConsSeparation() - new method SCIPconsIsSeparationEnabled() - added new parameter "dynamic" to SCIPcreateCons() and all plugin methods SCIPcreateCons...() - callback method CONFLICTEXEC of conflict handlers receive additional parameters "dynamic" and "removeable" - new methods SCIPgetAvgPseudocost(), SCIPgetAvgPseudocostCurrentRun(), SCIPgetAvgPseudocostCount(), SCIPgetAvgPseudocostCountCurrentRun(), SCIPgetAvgInferences(), SCIPgetAvgInferencesCurrentRun(), SCIPgetAvgCutoffs(), SCIPgetAvgCutoffsCurrentRun(), - new methods SCIPgetNPrimalLPs(), SCIPgetNPrimalLPIterations(), SCIPgetNDualLPs(), SCIPgetNDualLPIterations(), SCIPgetNBarrierLPs(), SCIPgetNBarrierLPIterations() - new methods SCIPgetNPrimalResolveLPs(), SCIPgetNPrimalResolveLPIterations(), SCIPgetNDualResolveLPs(), SCIPgetNDualResolveLPIterations() - new methods SCIPgetVarNStrongbranchs(), SCIPcolGetNStrongbranchs() - new methods SCIPfindSimpleRational(), SCIPselectSimpleValue() - new method SCIPvarGetImplIds() - methods SCIPvarGetProbvar(), SCIPvarGetProbvarBinary() now return the fixed or multi-aggregated variable instead of returning NULL or aborting with an error message; in SCIPvarGetProbvarBinary(), the fixing of a fixed variable does not influence the negation status anymore - method SCIPvarGetProbvarBound() returns the multi-aggregated variable instead of aborting with an error message - method SCIPvarGetProbvarSum() does not set *var to NULL for fixed variables anymore; it may also return a multi-aggregated variable instead of aborting with an error message - method SCIPgetBinvarRepresentative() now returns the fixed or multi-aggregated variable instead of returning NULL or aborting with an error message - new method SCIPvarGetOrigvarSum() - method SCIPdispDecimal() is replaced by SCIPdispInt() and SCIPdispLongint() plugins: - new implementation of the feasibility pump heuristic by Timo Berthold (replaces old implementation); old implementation is now called "objfeaspump"; parameter names have been changed accordingly - diving heuristics now compare their number of LP iterations with the number of node LP iterations instead of the total number (including their own) LP iterations - new plugin: probing presolver - new plugin: clique separator for clique cuts with at least 3 elements - changed implementation of reliability value calculation in reliability branching; slightly modified influence of maximal total number of strong branching LP iterations in reliability branching - changed implementation of maximal strong branching iterations calculation in reliability branching - modified the automatic objfactor setting of feaspump heuristic to let the objective function have stronger influence - changed implementation of automatic minplungedepth and maxplungedepth calculation in bfs node selector - new plugin: implied bound cuts separator - during probing, propagation of bounds is now always performed in linear constraint handler, ignoring the parameter "tightenboundsfreq" - new implementation of the clique graph construction method in clique separator - new constraint handler "cons_cumulative.{c,h}" parameters: - new parameters lp/cleanupcolsroot and lp/cleanuprowsroot to distinguish cleanup settings between root node and other nodes - new parameters heuristics/fixandinfer/proprounds and heuristics/fixandinfer/minfixings - default frequency offset of fracdiving heuristic changed to 3 - default frequency offset of (new) feaspump heuristic changed to 0 - default frequency offset of objfeaspump heuristic changed to 8 - changed default priority of primal heuristics - renamed parameter limits/sol to limits/solutions - changed default check priority of knapsack constraint handler to -600000 - new parameters separating/.../delay - new parameters presolving/.../delay - new parameters propagating/.../delay - new parameters constraints/.../delaysepa - new parameters constraints/.../delayprop - new parameters constraints/.../delaypresol - changed default priority of Gomory cut separator to -1000 (will now be called after constraint handlers!) - changed default priority of strong CG cut separator to -2000 - changed default priority of cmir cut separator to -3000 - new parameters lp/initalgorithm and lp/resolvealgorithm for switching between simplex and barrier algorithm - new parameter numerics/barrierconvtol to set the convergence tolerance in the barrier algorithm - new parameter lp/pricing to set the pricing strategy used in the LP solver - changed default of parameter lp/pricing to 's'teepest edge pricing - new parameter lp/checkstability to disable stability check of LP solver's result code - default parameter branching/relpscost/minreliable changed to 1.0 - default parameter branching/relpscost/maxlookahead changed to 8 - default parameter branching/relpscost/sbiterofs changed to 100000 - default parameter heuristics/coefdiving/maxlpiterquot changed to 0.05 - default parameter heuristics/fracdiving/maxlpiterquot changed to 0.05 - default parameter heuristics/guideddiving/maxlpiterquot changed to 0.05 - default parameter heuristics/linesearchdiving/maxlpiterquot changed to 0.05 - default parameter heuristics/pscostdiving/maxlpiterquot changed to 0.05 - default parameter heuristics/feaspump/freq changed to 20 - default parameter heuristics/objfeaspump/freq changed to 20 - default parameter heuristics/objpscostdiving/freq changed to 20 - default parameter heuristics/rootsoldiving/freq changed to 20 - new parameter conflict/dynamic - new parameter conflict/removeable - new parameter reading/mpsreader/dynamicconss - new parameter reading/cnfreader/dynamicconss - new parameter heuristics/coefdiving/maxlpiterofs - new parameter heuristics/feaspump/maxlpiterofs - new parameter heuristics/fracdiving/maxlpiterofs - new parameter heuristics/guideddiving/maxlpiterofs - new parameter heuristics/linesearchdiving/maxlpiterofs - new parameter heuristics/objfeaspump/maxlpiterofs - new parameter heuristics/objpscostdiving/maxlpiterofs - new parameter heuristics/pscostdiving/maxlpiterofs - new parameter heuristics/rootsoldiving/maxlpiterofs - new parameter heuristics/feaspump/maxsols - new parameter heuristics/objfeaspump/maxsols - new parameter heuristics/objpscostdiving/maxsols - new parameter heuristics/rootsoldiving/maxsols - new parameter branching/scorefunc - default parameter separating/clique/maxtreenodes changed to -1 features: - aging and cleanup now only remove non-basic columns and basic rows, s.t. resolving can be applied with 0 simplex iterations - calling SCIPaddCut() with forcecut=TRUE will add the cut to the LP even if it is redundant - command line history in interactive shell now only stores "useful" commands - probing is now also possible in presolving stage - it is now possible to create subnodes in probing and use backtracking to undo probing changes - it is now possible to interrupt and continue presolving - bounds of variables are included in the feasibility checks for solutions - support for barrier algorithm - added TSP example in examples/TSP - SCIPaddVarImplication() now also adds variable lower and upper bounds, if the implied variable is non-binary - removed storing of dual norms in LPI state of CPLEX interface (too memory consuming) - included debugging module to check whether cutting planes cut off the optimal solution - if verblevel is at least NORMAL, an automatical check of the best solution is performed in the original problem, and an error message is displayed, if it violates an original constraint - due to the new constraint handler "cons_cumulative.{c,h}" SCIP can resource-constraint scheduling problem fixed bugs: - fixed bug in MPS file reader - fixed bugs in separation store with single coefficient cuts that are converted into bound changes - at least one cut per separation round is added to the LP to avoid cycling, even if the cut is redundant - removed bug with applying reduced cost strengthening before pricing in all necessary variables - negated variables must also be reset in SCIPvarInitSolve() - removed bug with objective norm calculation and column variables not in the LP (pricing) - removed conflict analysis of infeasible diving LP if pricing is activated - removed bug in knapsack constraint handler with merging multiple items if more than two items of the same variable appear in the constraint - fixed bug in SCIProwCalcIntegralScalar() with rows consisting of only continuous variables (appeared in gomory cut separator on miplib/dcmulti.mps) - fixed documentation of CONSLOCK-method (missing parameter "scip" in SCIPaddVarLocks()) - included missing "objrelax.h" in includes of objscip.h - fixed bug that presolving time is not counted to solving time, if presolving is called explicitly with SCIPpresolve() - fixed bug where presolving fixings are counted even if the variable was already fixed - fixed bug that CONSLOCK method of constraint handlers that don't need constraints is not called - fixed bug that after a resolve and further preprocessing, existing primal solutions may get corrupted due to aggregations or fixings that are possible due to the primal bound (given by the best solution) - fixeg bug in setppc constraint handler with pairs of aggregated variables in the same constraint - removed bug with dual presolver, that declared a problem to be unbounded or infeasible, if it could fix a variable to infinity even if its objective value is zero - fixed bug in knapsack constraint handler that fixed variables are sometimes not removed in presolving - made conflict analysis available in presolving stage (for probing conflicts) - removed bug in knapsack constraint handler with merging negated variables of equal weight at the end of the variables' array - fixed bug with primal bound becoming wrong, if in a prior run the optimal solution was found and the cutoff bound was thereby reduced due to further domain propagation w.r.t. the objective function - fixed bug with unresolved numerical troubles in LP that don't render the LP useless at the current node - fixed bug in SCIPisObjIntegral() - LP error on forced LP resolve (due to 0 unfixed integers) now leads to an error (instead of accepting the pseudo solution as feasible) - fixed bug in SCIPprintError() with file == NULL - fixed bug with globally deleting constraints, that have attached rows which are therefore not released in exitsol methods - fixed bugs in intobj separator - fixed bug in CPLEX LP interface with dual norms - heuristic's display character is now only shown the first time, the new solution was found - fixed bug that SCIPreadProb() doesn't discard the transformed problem - fixed bug in cmir separator with empty rows - fixed bug in linear constraint handler's knapsack relaxation separator - fixed numerical bugs in rounding heuristic and rootsoldiving heuristic - fixed bug in implied bound cut separator: only implications between binary variables were generated before - fixed bug in linear constraint handler with eventdatas, if the original constraint has no variables - fixed bug with wrong euclidean norm calculation of row, if multiple coefficients for the same variable are added and the sorting of the row was delayed with SCIProwDelaySort() - fixed bug with adding implications: wrong insertion position, if only the lower bound change was present but not the upper bound change - fixed bug in SCIPvarAddImplics() with wrong variable used in varAdjustBd() - fixed bug in method reduced() of tclique_branch.c with sorting nodes in V SCIP version 0.78 ================= interface: - new method SCIPvarIsInLP() - new methods SCIPgetLPColumnObjval() and SCIPgetLPLooseObjval() - new method SCIPcalcIntegralScalar() with arbitrary array of Real values - new plugin class for relaxators (external relaxations, that can be used in parallel with LP relaxations) - if more than one result code applies to a plugin's execution, it should return the one that is higher in the call's documentation list - new method SCIPaddCoefKnapsack() in knapsack constraint handler - removed SCIPisFeasible(); use !SCIPisFeasNegative() instead - methods SCIPisIntegral(), SCIPisFracIntegral(), SCIPfloor(), SCIPceil(), and SCIPfrac() don't use the feasibility tolerance anymore (default: 1e-06); instead, they are using epsilon (default: 1e-09); instead, for handling integrality of a variable "in feasibility tolerances", new methods SCIPisFeasIntegral(), SCIPisFeasFracIntegral(), SCIPfeasFloor(), SCIPfeasCeil(), and SCIPfeasFrac() should be used - new method SCIPisScalingIntegral() to check, whether the scaling of a value would lead to an integral value, measured against epsilon which is also scaled by the same scalar - new methods SCIPgetRealarrayMinIdx(), SCIPgetRealarrayMaxIdx(), SCIPgetIntarrayMinIdx(), SCIPgetIntarrayMaxIdx(), SCIPgetBoolarrayMinIdx(), SCIPgetBoolarrayMaxIdx(), SCIPgetPtrarrayMinIdx(), and SCIPgetPtrarrayMaxIdx() - new methods SCIPbsortPtrInt(), and SCIPbsortPtrIntInt() - in LPI, the semantics of SCIPlpiHasPrimalRay() and SCIPlpiHasDualRay() changed: methods return TRUE, if a ray exists and the solver can return it; new methods SCIPlpiExistsPrimalRay() and SCIPlpiExistsDualRay() check whether a ray exists without checking, if the solver knows and can return the ray - new method SCIPvarWasFixedAtIndex() - new method SCIPaddConflictBd() - even in optimized mode, the simple functions that are implemented as defines in the include files exist in the library, s.t. one can include the include files without NDEBUG and use the optimized library - new method SCIPprintMemoryDiagnostic() - new methods SCIPfindObj...() and SCIPgetObj...() in C++ wrapper interface to get the corresponding plugin object - new branching rule plugin methods INITSOL and EXITSOL parameters: - slightly changed the meaning of parameter presolving/abortfac: a value of 0 now means to abort presolving only after no more change has been found features: - changed SCIProwCalcIntegralScalar() to a slightly different algorithm - improved knapsack relaxation in linear constraint handler separator to scale the constraint in order to get integral coefficients instead of just rounding down all coefficients - improved presolving of linear constraint handler: aggregation of two constraints with equal coefficient vector into single constraint - improved presolving of knapsack constraint handler: aggregation of equal or negated variables in same constraint - priority of separators, propagators, and presolvers decide whether the plugin is called before the corresponding constraint handler methods or after: plugins with nonnegative priorities are called before, plugins with negative priorities are called after the constraint handlers fixed bugs: - removed bug in knapsack constraint handler that appears if a variable is fixed to zero in knapsack presolving, which triggers a variable of the same knapsack to be fixed to one due to aggregation - fixed bugs in consdataSwitchWatchedVars() of "or" and "and" constraint handlers - fixed bug in all-fullstrong branching with getting strong branching information for columns not in current LP - assigning a value to a fixed variable in a solution with SCIPsetSolVal() does not return an error anymore, if the value is equal to the fixed value of the variable - implemented missing case in solve.c with branching rules that add constraints - solving loop is now immediately aborted, if a node on the active path is marked to be cut off - removed bug in resolving an interrupted problem, after the last solved node was cut off - removed bug with infinite solving loop if LP solving is turned off - removed bug in knapsack presolver - removed bug with aborted solving in root node (e.g. due to time limit) that is tagged to be restarted - changed numerics for integrality check of coefficients (fixed bug with accumulated errors in rows s.t. the row's activity is no longer integral although the row is marked being integer) - fixed bugs in constraint handlers (and, logicor, or, setppc, xor) with calling conflict analysis during presolving - slightly changed numerics in linear constraint handler presolving to fix a bug with coefficients detected to be scaled to an integral value, that are not integral after scaling due to a large scalar that increased the integrality gap to a value larger than epsilon - fixed wrong assertion in xor constraint handler with switching both watched variables to unwatched - removed bug in SCIPisScalingIntegral() - removed bugs with calling SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPinferVarLbCons(), SCIPinferVarUbCons(), SCIPinferVarLbProp(), and SCIPinferVarUbProp() in PROBLEM stage - fixed bug in presolving with wrong number of newly fixed/aggregated/... variables/bounds/... after a restart SCIP version 0.77 ================= installation: - the file names in the archive file are now preceeded with a directory "scip-<version>/" - the compiler is now also represented in the LP solver library names (e.g. you have to rename the softlink "libcplex.linux.x86.a" to "libcplex.linux.x86.gnu.a") interface: - added methods SCIPgetVarsLogicor() and SCIPgetNVarsLogicor() in logic or constraint handler - methode SCIPgetGap() and SCIPgetTransGap() now return infinity, if primal and dual bound have opposite sign (this removes the oddness with the gap increasing while the dual bound approaches zero) parameters: - lp/colagelimit and lp/rowagelimit may now be set to -1 to disable deletion of columns/rows due to aging features: - infeasible LPs in diving now produce conflict clauses (if LP conflict analysis is enabled) - conflict analysis was slightly modified - slightly changed aging strategy of logic or constraint handler fixed bugs: - removed bug in conflict analysis that appears if the conflict is only active at the current depth level - missing SCIPlpiIsPrimalFeasible() and SCIPlpiIsDualFeasible() implemented in lpi_spx.cpp and lpi_spx121.cpp - removed preprocessing of linear constraint pairs with modifiable constraints - removed wrong assert "assert(eventfilter->len == 0 || eventfilter->eventmask != 0x00000000)" from event.c - removed wrong assert in conflict analysis (appeared on analyzing diving LP conflicts with both bounds of a non-binary variable changed) SCIP version 0.76 ================= interface: - new method SCIPchgVarBranchDirection() - new method SCIPvarGetBranchDirection() - new possible result code SCIP_DELAYED for primal heuristics - changed SCIPcatchVarEvent() and SCIPdropVarEvent() - method SCIPstage() is now called SCIPgetStage() - method SCIPprintStatus() is now called SCIPprintStage() - new method SCIPgetStatus() returns the solution status - new method SCIPprintStatus() outputs the solution status (beware, that the old SCIPprintStatus() method is now called SCIPprintStage()) plugins: - new method SCIPgetActivityLinear() in linear constraint handler - new method SCIPgetFeasibilityLinear() in linear constraint handler parameters: - new parameter separating/efficacynorm to choose between Euclidean, maximum, sum, and discrete norm in efficacy calculation - changed default frequency offset of pscostdiving (heuristics/pscostdiving/freqofs) to 2, and frequency offset of fracdiving (heuristics/feaspump/freqofs) to 0 in order to not call pscostdiving in root node, where nearly all pseudo costs are uninitialized features: - creation of reconvergence clauses in conflict analysis - first node of each plunging is not treated as plunging node w.r.t. calling primal heuristics - improved performance of logic or constraint handler due to better watched variables handling fixed bugs: - removed bugs in CLP Solver interface - SCIP returned "gap limit reached" even if the problem was solved to optimality, if the optimal solution was found at a node with lower bound equal to the global lower bound - after conversion of the focus node into a junction (e.g. in case of numerical troubles while solving the node's LP), the child nodes got the wrong LP fork attached (the common LP fork of the old and new focus node instead of the old focus node's LP fork) - bug reconvergence clauses in conflict analysis if bounds on non-binary variables were the reason for the fixing of the uip to create a reconvergence clause for - wrong sub calls in SCIPvarGet...CurrentRun() for aggregated variables - variables' conflict set counter was not reset when the problem was resolved again known bugs (still not fixed): - unbounded models lead to an error - air04 and air05 return wrong optimal value (1 too large): possibly due to strong branching or setppc propagation? SCIP version 0.75 ================= - started change log