SCIP 1.2.0

Features

Preliminary support of non-convex MIQCPs: Constraint handler for quadratic constraints, NLP heuristic and Ipopt interface
Heuristics which are applied before root LP
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 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
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.
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
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
Black-box lexicographic dual simplex algorithm; can now run lexicographical dual algorithm (parameter "lp/lexdualalgo")
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 new version of zerohalf cuts from Manuel Kutschka
Plugins
- added reader for FlatZinc models (reader_fzn.{c,h})
- added multi-commodity-flow cut separator
- 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 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.?)

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 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

Interface changes

Reader for Flatzinc and GAMS models

New and changed callbacks

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)
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

Deleted and changed API methods

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 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 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 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
some interval arithmetic method take an additional argument to denote which value stands for infinity in an interval
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

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
detectRedundantConstraints() in cons_xor.c and necessary hash-functions for fast pairwise presolving
SCIPvarCompareActiveAndNegated and SCIPvarCompActiveAndNegated in pub_var.h for comparing variables negated, active or fixed the same way
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
SCIPparseVars() in scip.h; parses variable information (in cip format) out of a string
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
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
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
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
SCIPgetVarConflictlengthScore(), SCIPgetVarAvgConflictlength(), SCIPgetAvgConflictlengthScore() and their pendants for the current run
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
SCIPsetProbName() to set problem name in scip.h/c (SCIPprobSetName() in prob.h/c)

Interfaces to external software

heavily revised mosek interface
new interface to QSopt due to Daniel Espinoza
added interface to QSopt due to Daniel Espinoza
adjusted interface to ZIMPL (reader_zpl.{c,h} for ZIMPL version 2.10; this interface should also work with older ZIMPL versions
added first version of an interface to Ipopt (only QCP, no deletion of vars/cons allowed; nlpi_ipopt.(h|c))
First version of LP interfaces to Gurobi and QSopt
Major performance improvements in LP interfaces to Clp, Mosek and SoPlex
Adjusted interface to Zimpl version 3.0.0
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.001
"constraints/and/aggrlinearization" in cons_and.c, should an aggregated version of the linearization of the
"constraints/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 TRUE
"constraints/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 TRUE
"heuristics/oneopt/duringroot", default value TRUE

Build system

Makefile

extend Makefile to link against Ipopt if IPOPT=true is set

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 <lt;= 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 >gt;= 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, therefore 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 >gt;= 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