AMPL interface now returns dual multipliers if problem is an LP and presolving was turned off
Changed parameters
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
New parameters
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
timing/statistictiming to enable/disable all timers for statistic output of SCIP; the default value is TRUE
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
Fixed bugs
fixed wrong conversion of reals representing negative integer values
fixed bug in SCIPpermuteProb(): if called before transforming the problem, data structures were not initialized yet
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 GMI example: fractionality of slack variable is now computed correctly
fixed LP interface of CPLEX: functions getBInv* return the correct sign of the coefficients.
fixed bug in SCIPpermuteProb(), when called in transformed stage and non-active constraints exist
Dual:
use dual feasibility tolerance for comparisons regarding reduced costs
fixed bug in prop_dualfixing: don't fix variables to infinite values during solving
fixed sign of the dual multipliers returned by AMPL interfaces for maximization
Objective and Time Limit:
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 objective limit was not reset correctly during SCIPfreeTransform() for maximization problems
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
Heuristic:
fixed bug leading to an incorrect dual bound when solving probing LPs within a DURINGPRICINGLOOP heuristic
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 in heur_oneopt: avoid bound violations if shift value is negative due to infeasibilities
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 in trysol heuristic not saving the best solution in maximization problems
Presolve:
fixed bug in presolving of abspower constraints that lead to wrong variable locks
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
issues in component solving by presol_components do not lead to stopping the overall process, anymore, the component is just disregarded
Memory:
fixed bug with freeing problem: need to reset objective limit
fixed memory leaks in case of erroneous parsing of constraints, e.g., non-linear constraints
fixed missing memory allocation for node data in digraphs
Constraints:
fixed bug in cons_quadratic which leads to wrong min/max activities
removed wrong break in cons_pseudoboolean
fixed bug in cons_varbound.c using the wrong constraint side for updating an upper bound
fixed bug in presolve of cons_nonlinear: wrong constraint upgrades may have been performed due to outdated bound information in expression graph
fixed bug in cons_setppc, wrongly aggregating variables if dual-presolving was disabled
fixed bug in cons_sos1: locks and events were not initialized if constraint was added to transformed problem
fixed bug in cons_setppc with dual presolving disabled
corrected copy of disjunction constraints
Reading:
allow to read numbers like 42856. in lp-format
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 with reading >=1 indicator constraints in LP-files
fixed bug in reader_lp which created two indicator constraints with the same name to trigger an equality
fixed bug when reading indicator constraints for linear constraints (equations/ranged rows) from MPS files
SCIP 3.1.0
Features
added breadth first search node selection
new node selection rule UCT which balances exploration and exploitation by considering node visits
added possibility to not set a cutoff bound in the LP solver (can be enabled by setting lp/disablecutoff to TRUE)
added missing debugging solution check for cliques
added a data pointer to each node of the SCIP_DIGRAPH
SCIPgetVarCopy() will now copy the original bounds when called for an original variable
added upgrade of continuous variables to implicit variables for linear equations even if the coefficient is not equal to 1
added two methods to iterate over a sparse solution (SCIP_SPARSESOLUTION), see pub_misc.h
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
extended and corrected dual feasibility checks for LP solution (controlled by parameter lp/checkdualfeas)
Cuts and Separation:
the rank of cuts is now stored and taken into account to improve numerical stability
added possibility to separate a cutpool w.r.t. a given solution (instead of LP-solution)
Branching:
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 support for strong branching with domain propagation in full strong and reliability pseudo cost branching
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
a pricer can now return that no further pricing should be done but rather early branching, even if it added variables
LP interface:
SoPlex (>= 1.7.0.5) can compute condition number of current basis matrix via LP interface
LPI files (lpi*.[h|c]) all moved from src/scip to src/lpi
Constraints:
added propagation method to cons_xor relying on Gaussian elimination, which can also produce feasible solutions
added first implication detection in cons_linear
cons_indicator can now try to construct feasible solutions from a cover
added possibility to forbid upgrading of linear constraints
new initial constraints are now added to the LP before solving a probing LP
first implementation of parsing for nonlinear constraints in CIP format
added upgrade from varbound constraints to set-packing constraints
added upgrade from bounddisjunction constraints to set-packing/logicor constraints
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
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
XOR constraint handler can add two extended formulations (flow/asymmetric, parameter addflowextended/addextendedform)
added multi-aggregation for binary variables with at most two uplocks and two downlocks, which emerge from set- partitioning or set-packing constraints
added upgrade from quadratic constraints to set-packing constraints
generalized the linking constraint handler
Reader:
can now read and write CIP-files with (multi-)aggregated variables
all readers now take the global parameters reading/dynamic{conss|cols|rows} and reading/initialconss into account
added reader_pbm, which writes the constraint-variable incidence matrix in pbm format (possibly scaled to given size)
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 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)
Heuristic:
new primal heuristics dual value
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
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
Presolving:
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 full-dual presolving step in setppc constraint handler
dual solution can now be displayed for pure LPs when no presolving was performed
added clique presolving for xor constraints
added presolving using pairs of variable bound constraints that use the same variables
added more presolving to cons_indicator, checking whether indicator/slack variables are aggregated
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
return error if variable should be fixed to infinity after presolving (LP-solvers do not handle this consistently)
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
several new presolving steps for linear and knapsack constraints, using gcd information and many more
Statistic:
added average gap based on primal-dual integral to solution statistics; can be disabled via parameter misc/calcintegral
the statistics now include the value of the first LP solved at the root node (without cuts)
added new statistic which distinguishes between internal nodes and leaves which got processed
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)
Performance improvements
allow multiaggregation of binary variables
shorten conflicts and deriving global boundchanges from conflicts
apply lowerbound provided by pricers already during pricing loop, stop pricing if the lower bound computed by pricing already exceeds the cutoff bound
dual fixing presolver was turned into a propagator
many presolving improvements in constraint handlers
improved dual-presolving for setppc constraints in special cases
Constraints:
major improvements in pseudo-boolean constraint handler
performance improvement in domain propagation by marking constraints for propagation
added more constraint upgrading possibilities
improved handling of initial constraints created during solving
disabled scaling in feasibility check of nonlinear constraint handlers
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
fasten repropagation for set-packing and -partitioning constraints
improved merging of and-constraints
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
added upgradability for implicit binary variable cases for linear constraints
Examples and applications
new textbook Gomory mixed integer cuts example
Interface changes
removed all message length parameters in message.c and for printing error messages (not needed anymore)
New and changed callbacks
Domain Propagation:
added parameter nmarkedconss to SCIP_DECL_CONSPROP() callback which gives the number of constraints marked for propagation (these constraints are listed first in the conss array given as parameter).
Primal Heuristics:
Added parameter nodeinfeasible to SCIP_DECL_HEUREXEC() callback which states whether the current subproblem was already detected to be infeasible. In this case, the current LP solution might not respect local bounds and the heuristic must not assume that it does.
Variable Pricers:
Added parameter stopearly to callback method SCIP_DECL_PRICERREDCOST(). This boolean pointer should be used by the pricer to state whether early branching should be performed, even if new variables were added in the current pricing round.
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
LP and Cutting Planes:
Added parameter sidetypes to SCIPcalcMIR() to specify the specify row side type to be used.
Added parameter infeasible to SCIPaddCut() which is a pointer to store whether the cut is infeasible for the local bounds.
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
New method SCIPconshdlrGetStrongBranchPropTime() which returns the time used for domain propagation methods of the constraint handler during strong branching.
New methods for digraphs: SCIPdigraphResize() to resize the graph and SCIPdigraphSetNodeDatas() and SCIPdigraphGetNodeDatas() to set and get the data attached to the nodes.
New method SCIPprintDualSol() which prints the dual solution for a pure LP (works only with preprocessing disabled).
New method SCIPisCutApplicable() which returns whether a cut is good enough to be applied.
Message Handler:
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
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 method SCIPadjustImplicitSolVals() which sets implicit integer variables to an integer value in the given solution without deteriorating its objective value.
Added parameter endline to SCIPprintDisplayLine() to switch printing a newline symbol at the end of the line.
New method SCIPgetNLimSolsFound() returning the number of feasible primal solution respecting the objective limit.
Command line interface
allow dialog option to write clique graph
dual solution values can now be obtained in the interactive shell after solving a pure LP without presolving
Interfaces to external software
new SoPlex 2.0 interface, can be enabled with LPS=spx2
add support for SOS1 and SOS2 constraints to AMPL interface (see interfaces/check/testset/SOS/sos?a.mod for example)
added copy of GAMS interface from COIN-OR/GAMSlinks project; GAMS-reader in SCIP can now read model instances from .gms files
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
Changed parameters
parameter branching/scorefunction has new value q for for quotient branching score function
replaced parameter lp/checkfeas by two parameters lp/checkprimfeas and lp/checkdualfeas to decide on primal and dual feasibility checks individually
removed all local parameters reading/(READER)/dynamic{conss|cols|rows} and replaced them by global parameters reading/dynamic{conss|cols|rows}
changed default value of parameter numerics/dualfeastol to 1e-7 for safer dual bounds from LP solver
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
Constraints:
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
changed default max coefficient for big-M constraint to be initial from 1e6 to 1e9
Separation:
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
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
branching/firstsbchild and branching/forceall to specify the first child node to be investigated during strong branching (up, ddown, auto) 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)
conflict/fullshortenconflict to decide whether we want to stop shortening a conflict set, when no global bound changes can be found anymore
conflict/maxvarsdetectimpliedbounds to decide whether the a valid conflict of what maximal length will be used to derive global bound changes
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
constraints/and/upgraderesultant to upgrade resultants of and constraints from binary to implicit binary variables, default is TRUE
constraints/abspower/scaling and constraints/nonlinear/scaling
constraints/indicator/scaleslackvar for scaling of the slack variable in indicator constraints
constraints/indicator/trysolfromcover for trying to construct a feasible solution from a cover
constraints/linear/checkrelmaxabs for checking linear constraints with a side of 0.0 relative to
constraints/linear/detectpartialobjective to enable/disable the detection of sub-equations of the objective function
constraints/logicor/strengthen, should pairwise constraint comparison try to strengthen constraints by removing superflous non-zeros?
constraints/xor/addextendedform to add an extended formulation in XOR-constraints
constraints/xor/addflowextended to add use the extended flow formulation in XOR-constraints
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
heuristics/shiftandpropagate/fixbinlocks for fixing binary variables with no locks in one direction to the corresponding bound
heuristics/shiftandpropagate/collectstats which decides whether variable statistics are collected
heuristics/shiftandpropagate/impliscontinuous to decide whether implicit integer variables are treated as continuous variables
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
lp/disablecutoff to toggle usage of LP cutoff bound (0: enabled, 1: disabled, 2: auto = disabled if pricers are used)
misc/calcintegral (default TRUE) to trigger calculation of primal-dual integral
misc/finitesolutionstore to switch whether infinite fixings should be removed from solutions before copying them to the original solution store
misc/permuteconss and misc/permutevars to control whether variables and/or constraints should be permuted, if permutationseed != -1
presolving/components/feastolfactor to increase the feasibility tolerance in all sub-SCIPs, when solving a component
propagating/obbt/conditionlimit to discard instable LP bases
reading/(READER)/initialconss that determines whether model constraints are initial
reading/cipreader/writefixedvars for disabling printing of fixed variables in CIP format
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
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
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
separating/gomory/sidetypebasis to decide whether the sides of ranged rows should be determined from the basis status
separating/oddcycle/cutthreshold to run odd cycle separation if not enough cuts have been found
separating/zerohalf/delayedcuts to use the delayed cutpool for the zerohalf separator
write/allconss to enable that all constraints are written
write/genericnamesoffset when writing a generic problem to define an offset on the variable numbering
Data structures
New structure to store value-based branching and inference history (see pub_history.h).
new data structure for (circular) queues (SCIP_QUEUE)
hash tables will now increase dynamically
Moved LP solver interfaces to subdirectory src/lpi.
Testing
added McNemar tests and Wilcoxon signed rank tests to cmpres.awk evaluation scripts
added passing MEM option of testgams(cluster) target as workspace option to GAMS jobs
extended test scripts by statistical tests
Build system
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
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 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 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 minor bug in cons_linear w.r.t. disabled presolving
Propagators:
fixed bug in genvbounds propagator occurring when objective offset or scale changes after a restart
fixed bug in genvbounds propagator by replacing non-active variables on right-hand side after presolving
Readers:
fixed memory bug in reader_mps
fixed several minor bugs with handling of memory when writing aggregated variables (reader_lp, reader_mps)
fixed bug in reader_lp when writing bilinear terms (product sign was missing)
fixed bug in reading indicator constraints in mps-format
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
Constraints:
fixed several bugs where variables or constraints were not freed correctly
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 output of aggregated variables in indicator constraints in lp and 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 in cons_superindicator concerning names of upgraded constraints
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