Release notes for SCIP 1.2
SCIP 1.2.0
Features
- 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 presolving step in cons_knapsack.c, same like
simplifyinequalities
in cons_linear.c - 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
- added new preprocessing step (mergeMultiples) in cons_setppc.c where equal variables are merged
- Black-box lexicographic dual simplex algorithm; can now run lexicographical dual algorithm (parameter
lp/lexdualalgo
) - Bounds:
- SCIP now has
lazy bounds
, which are useful for column generation: see Further remarkspricer remarks
for an explanation. Each variable has now two additionalSCIP_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! - interval arithmetic functions can work with unbounded intervals added new functions to allow more operations on intervals, including solving quadratic interval equations
- SCIP now has
- Branching:
- extended hybrid relpscost branching rule by usage of the average length of conflicts a variable appears in
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. This can be useful for column generation.
- Constraints:
- Copy constructors and i/o functionality for constraints: 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
- Constraint handler for indicator constraints and parsing them from *.lp and *.zpl files
- the indicator constraint can now try to produce a feasible solution (via heur_trysol)
- one can now write indicator constraints in LP-format
- added constraint handler for quadratic constraints
- Cuts:
- added new version of zerohalf cuts from Manuel Kutschka
- added multi-commodity-flow cut separator
- Heuristics:
- Heuristics which are applied before root LP
- 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.?)
- new trivial heuristic: tries zero solution, lower and upper bound solution and some variable lock based fixing
- 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
- Interfaces:
- 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)
- Preliminary support of non-convex MIQCPs: Constraint handler for quadratic constraints, NLP heuristic and Ipopt interface, see cons_quadratic.h.
- There are LP-interfaces to QSopt and Gurobi (rudimentary).
- Reader and Writer:
- added reader and writer for FlatZinc models (reader_fzn.{c,h})
- added writer for GAMS models (reader_gms.{c,h})
Performance improvements
- Enhanced MCF cuts: stable version, used by default
- 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 updateForrest-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 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
- Presolving:
- improved pairwise presolving in cons_and.c due to using a hashtable
- improved pairwise presolving in cons_xor.c due to using a hashtable
Interface changes
- A significant change for C++ users is that all include files of SCIP automatically detect C++ mode, i.e., no
extern
C`` is needed anymore. - Reader for Flatzinc and GAMS models
New and changed callbacks
- The callback SCIP_DECL_PRICERREDCOST(x) in the How to add variable pricers
pricers
has two new parameters:- A
result
pointer determines whether the pricer guarantees that there exist no more variables. This allows for early branching. - A pointer for providing a lower bound.
- A
- The How to add constraint handlers
constraint handlers
have two new callback methods (see type_cons.h for more details):- SCIP_DECL_CONSCOPY(x): this method can be used to copy a constraint.
- SCIP_DECL_CONSPARSE(x): this method can be used to parse a constraint in CIP format.
Deleted and changed API methods
- SCIPcalcMIR() in scip.h has two new parameter
mksetcoefsvalid
andsol
. The parametermksetcoefsvalid
stores whether the coefficients of the mixed knapsack set (mksetcoefs
) computed in SCIPlpCalcMIR() are 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() andmksetcoefs
is not valid. The input parametersol
can be used to separate a solution different from the LP solution. - new parameter
set
in SCIPconsSetInitial(). - some interval arithmetic method take an additional argument to denote which value stands for infinity in an interval
- Variables:
- SCIPgetVarClosestVlb() and SCIPgetVarClosestVub() in scip.h have a new parameter
sol
. It can be used to obtain the closest variable bound w.r.t. a solution different from the LP solution. - new parameters
lowerbound
andresult
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
- SCIPgetVarClosestVlb() and SCIPgetVarClosestVub() in scip.h have a new parameter
New API functions
- new methods to deactivate a pricer SCIPdeactivatePricer() in scip.c
- 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
- SCIPsetProbName() to set problem name in scip.h/c (SCIPprobSetName() in prob.h/c)
- Objective:
- SCIPgetTransObjscale() and SCIPgetTransObjoffset() in scip.c
- SCIPaddObjoffset() in scip.h; sets offset of objective function
- SCIPgetOrigObjoffset() in scip.h; returns the objective offset of the original problem
- SCIPgetOrigObjscale() in scip.h; returns the objective scale of the original problem
- Constraints:
- detectRedundantConstraints() in cons_xor.c and necessary hash-functions for fast pairwise presolving
- SCIPparseCons() in scip.h; parses constraint information (in cip format) out of a string
- SCIPgetConsCopy() in scip.h; which copies a constraint of the source SCIP
- Relaxation:
- 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
- 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
- Sort:
- 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 interface methods SCIPcolSort(), SCIProwSort(), SCIPcolGetIndex()
- added SCIPsortPtrPtrLongInt() and corresponding sorting/inserting/deleting methods in pub_misc.h and necessary defines in misc.c
- extended the sort template functions in sorttpl.c with a
- Variables:
- SCIPprintNodeRootPath() in scip.h This method prints all branching decisions on variables from the root to the given node
- 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
- 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
- SCIPvarGetLbLazy() and SCIPvarGetUbLazy() in pub_var.h; These methods return the lazy lower or upper bound, respectively
- SCIPvarCompareActiveAndNegated() and SCIPvarCompActiveAndNegated() in pub_var.h for comparing variables negated, active or fixed the same way
- SCIPparseVars() in scip.h; parses variable information (in cip format) out of a string
- SCIPgetNFixedonesSetppc() and SCIPgetNFixedzerosSetppc() in cons_setppc.{h,c}; these methods returns current (local) number of variables fixed to one/zero in the given setppc constraint
- SCIPgetVarConflictlengthScore(), SCIPgetVarAvgConflictlength(), SCIPgetAvgConflictlengthScore() and their pendants for the current run
- added function SCIPvarsGetProbvarBinary() in pub_var.h; gets active, fixed, or multi-aggregated problem variables of binary variables and corresponding negated status
Interfaces to external software
- LP Interfaces:
- heavily revised Mosek interface
- new interface to QSopt due to Daniel Espinoza
- First version of LP interfaces to Gurobi and QSopt
- Major performance improvements in LP interfaces to Clp, Mosek and SoPlex
- External Software:
- adjusted interface to ZIMPL (reader_zpl.{c,h} for ZIMPL version 2.10; this interface should also work with older ZIMPL versions
- Adjusted interface to Zimpl version 3.0.0
- added first version of an interface to Ipopt (only QCP, no deletion of vars/cons allowed; nlpi_ipopt.(h|c))
- SCIP Interfaces:
- On http://code.google.com/p/python-zibopt/source/checkout you find a beta version of a python interface to SCIP implemented by Ryan J. O'Neil.
Changed parameters
- removed parameter
constraints/and/initiallp
since it is not needed anymore; - set parameter
constraints/and/sepafreq
default value to 1 - display character of oneopt heuristic changed to
b
New parameters
branching/relpscost/advanced/conflenscore
, default value 0.001constraints/and/aggrlinearization
in cons_and.c, aggregated version of the linearizationconstraints/and/enforcecuts
in cons_and.c, should cuts be separated during LP enforcing?constraints/and/presolusehashing
in cons_and.c, should pairwise presolving use hashing?, default TRUEconstraints/countsols/sollimit
in cons_countsols.c, counting stops, if the given number of solutions were found (-1: no limit)constraints/xor/presolusehashing
in cons_xor.c, should pairwise presolving use hashing?, default TRUEheuristics/oneopt/duringroot
, default value TRUE
Build system
Makefile
- extend Makefile to link against Ipopt if
IPOPT=true
is set
Fixed bugs
- fixed wrong use of pointer in lp.c
- fixed bug with array dimension not reset to zero when array is freed in pseudoobj propagator
- 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 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 compiler warning
warning: dereferencing type-punned pointer will break strict-aliasing rules
which resuts in scip-crashes with gcc version 4.4.0 - 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
- increased the numerical stability of coefficient tightening for Big M formulations
- fixed bug with incorrect pseudo activities when objective of a variable switches sign in linear constraint handler
- fixed bug with empty constraints in several writing routines
- fixed
GGT-Kaibel-Bug
in var.c, prop_pseudoobj.c and cons_varbound.c that occured while computing new values using infinity values - Bounds:
- fixed bug in coefficient tightening with infinite bounds
- fixed bug in solve.c: in case lowerbound >= upperbound, SCIPsolveIsStopped() returned
SCIP_STATUS_GAPLIMIT
- Nodes:
- 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 bug in vbc tools concerning of marking probing nodes
- fixed bug in solve.c with nodes which are marked to be repropagated while enforcement
- Variables:
- fixed possible infinite loop while multiaggregating a variable in var.c
- fixed bug in SCIPgetSolVals() similar to SCIPgetSolVal(): try to get original variables of transformed ones if the solution lives in original space
- Pricing:
- fixed potential bug: restarts are now only done if no active pricers exist
- 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.
- fixed bug with invalid pseudo solution (lower bound was always >= 0) when using pricing.
- fixed bug in SCIPfreeProb() in scip.c: all pricers are deactivated now
- Memory:
- now frees debug memory
- fixed bug with exponential complexity for reallocating memory in SCIPvarGetActiveRepresentatives() in var.c
- 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 externC
lines) - 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
- Reading and Writing:
- corrected bug in reader_lp.c: earlier read bounds were thrown away (implementation was not conforming to standard)
- 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 corrupted files
- fixed bug in reader_mps.c with respect to writing transformed problems
- changed wrong writing of mps files due to constraints without any name
- fixed a bug during reading debug solution file
- fixed bug in case of reading an objective function in opb format with multiple occurrences of the same variable
- fixed bug in case of reading an objective function in lp format with multiple occurrences of the same variable
- fixed a wrong fix of a reading bug, which was in reality 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
- Separation:
- fixed bug in sepa_cmir.c, sepa_mcf.c and sepa_flowcover.c: sol different to LP solution is now separated
- corrected two asserts in sepa_redcost.c (reduced costs can be negative for fixed variables: qsopt uses this)
- fixed bug in sepa_zerohalf.c; replacement of own sorting functions by template functions was incorrect
- 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
- Cuts:
- 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)
- interrupts optimization process if a node will be cutoff, which allows the solution
- 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 solve.c caused by integer overflow due to setting the number of cuts to INT_MAX
- Presolving:
- fixed wrong result in check.awk, if infeasible problems are stopped in presolving
- fixed exponential calculation of solution values during check of original solution, therefore changed SCIPvarGetActiveRepresentatives() in var.c and flattened all multiaggregated vars at the end of presolving in exitPresolve()
- fixed bug with wrong abort criterion in presolving
- fixed bug in presol.c caused by not reseting presolver-wasdelayed status
- fixed bug in SCIPconsSetInitial() that occurred in pairwise presolving: add or delete constraint in initconss when changing the initial flag
- Constraints:
- fixed bug in cons.c caused by not resetting conshdlr data after restart
- fixed memory error in cons_countsols.c
- fixed assert in cons_and.c method SCIP_DECL_CONSINITSOL(consInitsolAnd)
- fixed bug in cons_countsols.c we respect to warning message that
The current parameter setting might cause ...
- Knapsack Constraint Handler:
- fixed wrong assert in cons_knapsack.c and handled a special this case in simplifyInequalities()
- 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
- 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
- Linear Constraint Handler:
- fixed infinity loop in simplify inequalities in cons_linear.c
- 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 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
- Heuristics:
- added and changed some SCIPisStopped() calls in several heuristics
- fixed bug in oneopt heuritic with start solution which has become infeasible due to global bound changes
- Interfaces:
- corrected several bugs in the Clp-interface concerning return values
- fixed potential interface bug: time limits of 0.0 are not anymore passed to the LP solver, which may have caused errors