Release notes for SCIP 3.1
SCIP 3.1.1
Features
- use clock average to reduce number of system calls via
timing/rareclockcheck
parameter - added copy mechanism for conjunction constraints
- added revised lpi_xprs for using XPRESS as LP solver
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
Interface changes
New and changed callbacks
- rename array arcdatas in digraph to arcdata
- changes in clock type are now transferred to SoPlex
- corrected wrong primal bound in statistics for unbounded problems
- forbid to call SCIPfixVar() in
SCIP_STAGE_PRESOLVED
stage, which is not allowed since it calls SCIPchgVarLb/Ub()
Deleted and changed API methods
- rename SCIPdigraphGetNodeDatas() to SCIPdigraphGetNodeData();
- rename SCIPdigraphSetNodeDatas() to SCIPdigraphSetNodeData()
- SCIPapplyProximity() has an additional parameter freesubscip, which causes the method to free the created subscip automatically at the end.
New API functions
- SCIPhasPerformedPresolve() to check, e.g., whether LP duals are accessible
- SCIPconvertRealTo[Long]Int() to convert reals that represent integers to [long] ints.
- SCIPisDualfeasEQ() and related to perform checks w.r.t. to the dual feasibility tolerance
- SCIPdeleteSubproblemProximity() to free proximity subproblem manually as external caller
Command line interface
- added dialog for writing the finite solution (calling SCIPcreateFiniteSolCopy() before writing)
Interfaces to external software
- 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 FALSEtiming/statistictiming
to enable/disable all timers for statistic output of SCIP; the default value is TRUE
Data structures
- renamed MIP matrix structure to
SCIP_MATRIX
- changed the numeric values for
PRESOLTIMING
flags
Build system
Makefile
- added Makefile support for cygwin 64 Bit
- 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
- in debug mode, SCIP checks that no NaN's are introduced in SCIPsolSetVal()
- fixed bug 697 (and 699), calling SCIPsolve() after the problem was already solved and SCIPfreeSolve() was called now does nothing anymore
- 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
- branching for continuous variables with unbounded intervals now takes
branching/clamp
into account - 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 where quieting a message handler also disabled writing to files other than stdout
- fixed bug 708, special case of implications led to a fixing
- fixed bug, variable bounds detected wrong infeasibility
- another bug fix when computing the original variable sum of a given variable in SCIPvarGetOrigvarSum()
- fixed setting solution value of multi-aggregated var in xml-solution case
- fixed bug changing the variable type of an negated variable
- fixed numerical troubles in SCIPcreateFiniteSolCopy()
- 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
- allow to call SCIPmarkConsPropagate() in INITPRESOLVE stage
- 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
- allow to read numbers like
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
- probing supports implicit binary variables
- added scaling to computation of relative interior point in SCIPcomputeLPRelIntPoint()
- Solution:
- 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
)
- added two methods to iterate over a sparse solution (
- 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
- new branching rule
- 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}
andreading/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 theSolutions
section before, namedRoot Dual Bound
andRoot Iterations
)
- added average gap based on primal-dual integral to solution statistics; can be disabled via parameter
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
- improved performance of SCIPcliquelistDel(), SCIPcliquetableAdd(), SCIPcliquetableCleanup()
- LP Solution:
- strong branching LP solutions are checked for integrality
- improved LP reoptimization for branch-and-price applications
- improved numerical stability checks for LP solution
- faster feasibility check of LP solutions (controlled by parameters
lp/checkprimfeas
andlp/checkdualfeas
)
- Presolver:
- improved methods SCIPlpiGetBInv{Row,Col,ACol} for row representation in SoPlex LP interface
- improved performance of method SCIPsolRetransform() when called during presolving with many aggregations
- minor presolving performance improvements in cons_logicor.c and cons_knapsack.c
- 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).
- added 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.
- Added parameter
- 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.
- Added parameter
- Branching Rules:
- new possible return value
SCIP_DIDNOTFIND
for SCIP_DECL_BRANCHEXECLP(), SCIP_DECL_BRANCHEXECPS(), and SCIP_DECL_BRANCHEXECEXT() callbacks to state that the branching rule searched, but did not find a branching.
- new possible return value
Deleted and changed API methods
- SCIPcalcMIR() takes an additional parameter sidetypes to determine which side of the rows to use (relevant for ranged rows)
- SCIPvarParseOriginal() and SCIPvarParseTransformed() now return the end of the parsed string
- SCIPgetConsCopy() now always captures the created constraint
- Branching:
- Added parameter
nfracimplvars
to SCIPgetLPBranchCands() - 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
- Added parameter
- LP and Cutting Planes:
- Added parameter
sidetypes
to SCIPcalcMIR() to specify the specify row side type to be used. - Added parameter
cutrank
to SCIPcalcMIR() and SCIPcalcStrongCG() which stores the rank of the returned cut; via SCIProwChgRank() the rank of a cut can be changed (default rank is 0) - 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
- removed parameter
normtype
from function SCIPcomputeLPRelIntPoint()
- Added parameter
- Misc:
- Added parameter
lazyconss
to SCIPwriteMIP() to swith writing removable rows as lazy constraints. - Added parameter
enablepropagation
to SCIPstartStrongbranch(), which can be used to enable strong branching with domain propagation. - SCIPstartStrongbranch() has a new parameter
propagate
to enable or disable propagation support for strong branching - New method SCIPgetVarStrongbranchWithPropagation() which performs strong branching with propagation on a variable.
- Added parameter
endptr
to SCIPparseVar() which stores the final string position after parsing.
- Added parameter
New API functions
- added SCIPdebugCheckConss() to the debugging mechanism and therefore created a
SCIP_SOL
(in original space) in debug.c - before copying solutions to the original solution candidate storage, infinite solution values can now be removed using SCIPcreateFiniteSolCopy()
- SCIPsortLongPtrRealBool(), SCIPsortLongPtrRealRealBool(), SCIPsortLongPtrRealRealIntBool() and corresponding methods for sorting, insertion and deletion
- SCIPstoreSolutionGap() in scip.c, to store the gap when the first and last solution is found
- SCIPwriteCliqueGraph() which allows to write a graph with node weights for fractional variables
- Separation:
- SCIPconshdlrIncNCutsFound(), SCIPsepaIncNCutsFound() and SCIPsepaIncNCutsFoundAtNode() to increase the number of found cuts
- SCIPseparateSolCutpool() to separate a cutpool w.r.t. a given solution
- Constraint Handlers:
- New method SCIPconshdlrGetStrongBranchPropTime() which returns the time used for domain propagation methods of the constraint handler during strong branching.
- New method SCIPconsIsMarkedPropagate() which returns whether a constraint is marked for propagation.
- New methods SCIPconsAddUpgradeLocks() and SCIPconsGetNUpgradeLocks() to increase or get the number of upgrade locks of a constraint.
- New method SCIPgetNCheckConss() which returns the number of checked constraints.
- Data structures:
- New methods SCIPsparseSolGetFirstSol() and SCIPsparseSolGetNextSol() to get the first sparse solution or iterate over the sparse solutions, respectively.
- New methods for the
SCIP_QUEUE
data structure in pub_misc.h to handle a (circular) queue, e.g., SCIPqueueCreate(), SCIPqueueFree(), SCIPqueueInsert(), SCIPqueueRemove(), SCIPqueueFirst(), SCIPqueueIsEmpty(), SCIPqueueNElems() - New method SCIPgmlWriteNodeWeight() to write a node section including weight to a .gml graph file.
- New methods for hash tables: SCIPhashtableRemoveAll(), SCIPhashtableGetNElements(), SCIPhashtableGetLoad()
- New methods in pub_misc.h to handle a resource activity, e.g., SCIPactivityCreate(), SCIPactivityFree(), SCIPactivityGetVar(), SCIPactivityGetDemand() ...
- New methods for digraphs: SCIPdigraphResize() to resize the graph and SCIPdigraphSetNodeDatas() and SCIPdigraphGetNodeDatas() to set and get the data attached to the nodes.
- Domain Propagation:
- New method SCIPpropGetStrongBranchPropTime() which returns the time spent by a domain propagator during strong branching.
- New methods SCIPmarkConsPropagate() and SCIPunmarkConsPropagate() to (un)mark a constraint for propagation.
- LP and Cutting Planes:
- New methods SCIPchgRowLhsDive() and SCIPchgRowRhsDive() to change left and right hand side of a row during diving.
- Added parameter
cutoff
to SCIPsolveDiveLP(), SCIPsolveProbingLP(), and SCIPsolveProbingLPWithPricing() which is a pointer to store whether the diving/probing LP was infeasible or the objective limit was reached. - SCIPgetFirstLP{Dual/Lower}boundRoot() which return the value of the first LP solved at the root node
- SCIPgetNRootFirstLPIterations() which returns the number of LP iterations for the first LP solved at the root node
- SCIPlpiGetNorms(), SCIPlpiSetNorms() and SCIPlpiFreeNorms() for getting the LP pricing norms from the LP solver, loading them back into the solver and freeing the data
- New method SCIPgetFirstLPTime() and SCIPgetNRootFirstLPIterations() to return time and iterations for the first LP solve and SCIPgetFirstLPDualboundRoot() and SCIPgetFirstLPLowerboundRoot() to return the first root LP dual and lower bound.
- 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 - New generic messagehandler output callback method SCIP_DECL_MESSAGEOUTPUTFUNC().
- Removed parameter
msglength
from callback method SCIP_DECL_ERRORPRINTING(). - New method SCIPmessageVPrintError() to print an error message.
- Removed method SCIPmessagePrintWarningHeader().
- the main output routine of message.c (
- Parameters:
- New method SCIPparamGetCharAllowedValues() to get the allowed values for a char parameter.
- New method SCIPgetParam() to get the parameter with a given name.
- Variables:
- SCIPapplyProbingVar() in prop_probing.h without deteriorating its objective value
- 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
- SCIPselectVarStrongBranching() to get the variable that fullstrongbranching would select
- New method SCIPvarGetValuehistory() to get the value-based history of a variable.
- Misc:
- New method SCIPdoNotMultaggr() which returns whether multi-aggregation was disabled.
- New method SCIPcreateFiniteSolCopy() to create a copy of a solution with infinite fixings removed.
- New method SCIPadjustImplicitSolVals() which sets implicit integer variables to an integer value in the given solution without deteriorating its objective value.
- New method SCIPcopyOrig() to copy the original problem. Analoguosly, use SCIPcopyOrigProb(), SCIPcopyOrigVars(), and SCIPcopyOrigConss() to copy original problem data, variables, or constraints, respectively.
- New method SCIPwriteCliqueGraph() to write the clique graph in GML format into a given file
- New method SCIPaddOrigObjoffset() to add an offset to the objective function. in original space and updates all orignal solutions correspondingly
- New method SCIPcopyImplicationsCliques() to copy implications and cliques to a copied SCIP instance.
- New method SCIPgetOpenNodesData() which returns all unprocessed nodes.
- 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 valueq
for forq
uotient branching score function - replaced parameter
lp/checkfeas
by two parameterslp/checkprimfeas
andlp/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 parametersreading/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 fromu
tov
, 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
- changed type of parameters
- 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 - remove parameter
separating/closecuts/relintnormtype
- changed default value of gomory cut separation parameter
New parameters
branching/checksol
andbranching/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 solutionbranching/firstsbchild
andbranching/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)conflict/fullshortenconflict
to decide whether we want to stop shortening a conflict set, when no global bound changes can be found anymoreconflict/maxvarsdetectimpliedbounds
to decide whether the a valid conflict of what maximal length will be used to derive global bound changesconstraints/{linear,knapsack}/detectcutoffbound
andconstraints/{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 LPconstraints/and/upgraderesultant
to upgrade resultants of and constraints from binary to implicit binary variables, default is TRUEconstraints/abspower/scaling
andconstraints/nonlinear/scaling
constraints/indicator/scaleslackvar
for scaling of the slack variable in indicator constraintsconstraints/indicator/trysolfromcover
for trying to construct a feasible solution from a coverconstraints/linear/checkrelmaxabs
for checking linear constraints with a side of 0.0 relative toconstraints/linear/detectpartialobjective
to enable/disable the detection of sub-equations of the objective functionconstraints/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-constraintsconstraints/xor/addflowextended
to add use the extended flow formulation in XOR-constraintsheuristics/<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.0heuristics/shiftandpropagate/fixbinlocks
for fixing binary variables with no locks in one direction to the corresponding boundheuristics/shiftandpropagate/collectstats
which decides whether variable statistics are collectedheuristics/shiftandpropagate/impliscontinuous
to decide whether implicit integer variables are treated as continuous variablesheuristics/shiftandpropagate/preferbinaries
andheuristics/shiftandpropagate/stopafterfeasible
, which decide whether binaries should be shifted first and the shifting should be stopped when no violations are leftlp/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 integralmisc/finitesolutionstore
to switch whether infinite fixings should be removed from solutions before copying them to the original solution storemisc/permuteconss
andmisc/permutevars
to control whether variables and/or constraints should be permuted, if permutationseed != -1presolving/components/feastolfactor
to increase the feasibility tolerance in all sub-SCIPs, when solving a componentpropagating/obbt/conditionlimit
to discard instable LP basesreading/(READER)/initialconss
that determines whether model constraints are initialreading/cipreader/writefixedvars
for disabling printing of fixed variables in CIP formatreading/lpreader/aggrlinearization-ands
andreading/mpsreader/aggrlinearization-ands
to enable/disable the printing of the weak or strict relaxation of and-constraints in LP and MPS format, respectivelyreading/lpreader/linearize-and-constraints
andreading/mpsreader/linearize-and-constraints
to allow and-constraints to be linearized when printing in LP and MPS format, respectivelyseparating/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 cutsseparating/gomory/sidetypebasis
to decide whether the sides of ranged rows should be determined from the basis statusseparating/oddcycle/cutthreshold
to run odd cycle separation if not enough cuts have been foundseparating/zerohalf/delayedcuts
to use the delayed cutpool for the zerohalf separatorwrite/allconss
to enable that all constraints are writtenwrite/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 bug in random generators SCIPgetRandomInt() and SCIPgetRandomReal() for large intervals
- make sure that bound changes of negated original variables are correct
- Branching:
- fixed bug w.r.t. changing the variable branching priority beyond the problem stage
- allow again branching on continuous variables with huge bounds
- Separation:
- fixed bug in sepa_cgmip computeObjWeightSize() w.r.t. equal sized rows
- fixed wrong bound calculation in sepa_rapidlearning
- fixed bug in flowcover separator to exclude unconstrained rows in aggregation
- LP and Interfaces:
- 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 several bugs in lpi_grb
- fixed wrong strong branching results in lpi_grb.c and an invalid write
- fixed bug in handling max-function in ampl interface; added support for min-function
- Presolving:
- fixed bug in prop_dualfix w.r.t. to fixing of variables to infinity after presolving
- fixed wrong presolving finished status which sometimes occurred when the time limit was hit during presolve
- fixed bug where a limit on presolving rounds was exceeded by 1
- fixed minor bugs in presolving in cons_setppc.c and cons_logicor.c
- 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
Miscellaneous
- new SCIP Optimization Suite homepages