SCIP 1.1.0

Features

Extended the capabilities of SCIP to output problems in different formats (LP, MPS, CIP, ...). You can output the original and transformed problem. Furthermore, generic names can be given to the variables and constraints.
The feasibility test for solutions at the end of the execution now outputs more useful information. This made some changes in the interface of constraint handlers necessary.
SCIP can now count integer feasible solutions for IPs/CIPs (without continuous variables) (see SCIPcount())
the MPS reader is now able to write a problem in MPS format
the ZIMPL reader now understands SOS type 1 and 2 constraints
the LP reader reads SOS constraints of type 1 and 2
the MPS reader reads the SOS section (but cannot yet handle 'MARKERS')
output of real values is now done with 15 digits after the decimal point
SCIP can now output a picture of the constraint matrix in PPM format.
replaced some old sorting methods in cons_knapsack.c, heur_octane.c, sepa_flowcover.c and presol_probing.c through SCIPsort... interfaces, adjusted misc.{c,h} and pub_misc.h for these changes
added ccg-reader (weighted column connectivity graph)
cons_countsols.c is now able to store the collected solution if required
check.awk now uses TeX package supertabular which supports automatic pagebreak
struct SCIP_Stat has now two additional variables: nprobboundchgs, nprobholechgs; these are used to fix the domain reduction counts in sepa.c, cons.c, branch.c and prop.c; this means, that now the domain reduction counts are reduced by those domain reduceds which are preformed during probing
The SoPlex LPI can now write basis files.
added capabilities to flatten the (multi)-aggregation graph of variables
the ZPL reader is now able to pass a starting solution to SCIP
revised lpi_clp.cpp (many small changes, in particular writing and reading of bases)
added FASTMIP settings in lpi_clp.cpp that try to improve the performance of Clp as much as possible
allow cut selection based on support of inequality in orthogonality computation
disabled zerohalf cuts by default
adjusted all predefined settings files, e.g., settings/cuts/fast.set, such that they are consistent wrt removed, added and changed parameter values of scip.
added predefined settings file presolving/aggressive.set
New cutting plane separator MCF (beta version).
Plugins
- added first version of SOS type 1 constraint handler (cons_sos1.{c,h})
- added first version of SOS type 2 constraint handler (cons_sos2.{c,h})
- less aggressive scaling in linear constraint handler presolve to improve numerics
- added reader for pseudo-Boolean problems (reader_opb.{c,h})
- added first version of constraint handler cons_countsols.{c,h}
- pseudoobj propagator now also propagates the global lower (dual) bound
- linear constraint handler now detects continuous variables that are implicit integer in dual presolve
- the c-MIR separator now also tries to get rid of implicit integer variables by aggregation
- new heuristic DINS (distance induced neighborhood search by Ghosh)
- new presolver boundshift (presol_boundshift.{c,h}); this presolver is currently turned off with default parameter setting
- new separator sepa_zerohalf.{c,h}; separates {0,1/2}-Cuts according to Caprara and Fischetti

Performance improvements

The preprocessing has been revised. It now applies bound computations in a numerically more stable way. The pairwise comparison of linear, logicor, and setppc constraints has been improved.
improved the performance of SCIPcalcMIR() and SCIPcalcStrongCG() by exploiting sparsity
better branching in SOS1/SOS2 constraints
improved pairwise presolving in cons_linear.c: reduced cache misses, reduced number of SCIPisStopped() calls and included detecting of redundant constraints with hash table in advance
small performance improvement of c-MIR aggregation heuristic
tighter memory limits in knapsack presolve lifting procedure to avoid overly expensive presolving
heavily decreased the usage of SCIPisStopped(), which costs system time
fixed performance bug with large number of unnamed constraints that will kill the name hash table (now, unnamed constraints are not put into the hash table)
reworked strong branching in lpi_clp.cpp (scaling works now, bounds can be trusted)
improved performance of SCIPvarGetLPSol(), which affects many parts of the code, in particular Gomory and strong CG cuts
do not calculate MIR and StrongCG cut aggregations if number of nonzeros in aggregated row is too large
included detecting of redundant constraints with hash table in advance in cons_logicor.c and limit other pairwise presolving
included detecting of redundant constraints with hash table in advance in cons_setppc.c and limit other pairwise presolving
limit pairwise presolving in cons_linear.c

Examples and applications

Added an example for the graph coloring problem in examplex/Coloring, showing the usage of column generation.
added SOS2 example
extended TSP example

Interface changes

New and changed callbacks

new callback method SCIP_DECL_READERWRITE(x) in type_reader.h; this method is called to write a problem to file stream in the format the reader stands for; useful for writing the transformed problem in LP or MPS format
the interface method SCIP_DECL_CONSCHECK() has a new parameter "printreason"; if this comes in TRUE the constraint handler is ask to print for violated constraint a reason;
added new LPI pricing option SCIP_PRICING_LPIDEFAULT, such that every LP interface can set the default pricing strategy on its own ('auto' is not useful for this, because for CPLEX, for example, SCIP seems to be worse with 'auto' then with 'steepest edge')
added user pointer to callback methods of hash table

Deleted and changed API methods

expand sorttpl.c by some parameters
changed some names for sorting methods
new parameters "extension" and "genericnames" in SCIPprintTransProblem() defining the requested format or NULL for default CIP format and using generic names for the variables and constraints e.g, SCIPprintTransProblem(scip, NULL, NULL, TRUE) displays the transformed problem in CIP format with generic variables and constraint names
new parameters "extension" and "genericnames" in SCIPprintOrigProblem() defining the requested format or NULL for default CIP format and using generic names for the variables and constraints e.g, SCIPprintOrigProblem(scip, NULL, "lp", FALSE) displays the original problem in LP format with original variables and constraint names
new parameter "conshdlrname" in SCIPincludeLinconsUpgrade()
replaced sorting methods SCIPbsort...() by faster (quicksort/shellsort) algorithms SCIPsort...() Note that the order of the parameters has been changed to simplify the template code in sorttpl.c!
new parameter 'maxfrac' for SCIPcalcStrongCG()
the parameter list of the method SCIPcheckSolOrig() (scip.h) has changed; the new advatage is, that SCIP can print the reason for a violation as for as the violated component supports this
the parameter list of the method SCIPcheckCons() (scip.h) has changed; the new advatage is, that SCIP can print the reason for the violation of a constraint as for as the constraint handler supports that
the parameter list of the method scip_check() (objconshdlr.h) has an additional parameter "printreason" see for explanation the previous point
SCIPgetVarRedcost() now returns 0 for variables that have been aggregated out or removed in presolving. reduced cost in case of infeasible LPs)
new parameter "maxmksetcoefs" for SCIPcalcMIR() and SCIPcalcStrongCG() methods
new parameters "extension" in SCIPreadProb() defining a desired file format or NULL if file extension should be use

New API functions

added some downwards-sorting methods
LPI now has a function SCIPlpiGetSolverPointer() that returns a solver dependent pointer. This can be used to directly access the LP solver. This should, of course, only be used by people that know exactly what they are doing.
added capabilities to avoid multi-aggregation of a single variable by setting a corresponding flag (SCIPmarkDoNotMultaggrVar())
SCIPwriteOrigProblem(), e.g., SCIPwriteOrigProblem(scip, "orig.lp", NULL, FALSE) prints the original problem in LP format in the file "orig.lp"
SCIPwriteTransProblem(), e.g., SCIPwriteTransProblem(scip, NULL, NULL, FALSE) displays the transformed problem in CIP format
SCIPgetProbvarLinearSum()
SCIPgetResultantAnd() which returns the resultant variable of an "and" constraint
SCIPchgChildPrio() to change the node selection priority of the given child
SCIPconsGetPos()
SCIPrepropagateNode() to mark a node for repropagation
SCIPcount() (in cons_countsols.h) for counting all feasible solution of a given CIP
SCIPcreateRootDialog() (in dialog_default.h) which creates a root dialog
SCIPbsortInd()
SCIPgetVectorEfficacyNorm()
SCIPcutGenerationHeuristicCmir() in sepa_cmir.h
SCIPseparateRelaxedKnapsack() in cons_knapsack.h
SCIPgetCutoffdepth() which returns the depth of first node in active path that is marked being cutoff
SCIPflattenVarAggregationGraph()
SCIPclockGetLastTime()
SCIPsortedvecInsert...(), SCIPsortedvecInsertDown...(), SCIPsortedvecDelPos...(), SCIPsortedvecDelPosDown...(), SCIPsortedvecFind...() and SCIPsortedvecFindDown...() to manage sorted vectors or groups of vectors of various data types that are sorted w.r.t. the first vector
SCIPcalcHashtableSize() to get a reasonable hash table size
SCIPheurGetTimingmask() and SCIPheurSetTimingmask()
SCIPgetVarFarkasCoef() and SCIPgetColFarkasCoef() to get the farkas coefficient of a variable (analogon of
SCIPprintSysError which encapsulates the strerror_r calls, the NO_STRERROR_R flag switches between the use of strerror_r and strerror inside
SCIPgetRepropdepth() to get the depth of first node in active path that has to be propagated again
SCIPsnprintf() safe version of snprintf (and sprintf)
SCIPreaderCanRead() and SCIPreaderCanWrite() in pub_reader.h, these return TRUE if the corresponding reader is capable to read or write, respectively
SCIPmajorVersion, SCIPminorVersion and SCIPtechVersion() returning the corresponding version

Command line interface

advanced reading and writing dialog in interactive shell

Interfaces to external software

Many changes in the SoPlex interface: The current one is tailored towards SoPlex 1.4 (aka 1.3.3). All SoPlex functions (where applicable) should now have an exception handling. The Bugfix for adding columns has been moved to SoPlex. One can use ROW representation. Reading/writing of a basis has been implemented.

Changed parameters

changed default frequency parameters for RINS, Local Branching, Crossover and Mutation heuristic This should not change the performance but happened just for consistency reasons
changed parameter default values for the priority of presolver "dualfix" and "inttobinary"
removed parameter "separating/cmir/maxtestdeltaroot"
new value 'l' for parameter "lp/pricing", which is the new default

New parameters

"constraints/and/linearize" to enable linearization of all <lt;and>gt; constraints (in presolving),
"constraints/and/initiallp" to turn on, off, or 'auto' that the LP relaxation of the AND constraints are in the initial LP;
"constraints/countsols/collect" to enable the storing of the solutions; default value FALSE;
"constraints/indicator/addCoupling" to enable generation of relaxation
"constraints/indicator/branchIndicators" to decide whether it is branched on indicator constraints in enforcing
"constraints/indicator/genLogicor" to decide whether logicor constraints instead of cuts are generated
"constraints/indicator/sepaAlternativeLP" to decide whether separation takes place using the alternative LP
"constraints/linear/aggregatevariables" to search for aggregations in equations in the presolving step
"constraints/linear/dualpresolving" to disable dual presolving step in the linear constraint handler; default value is TRUE
"constraints/linear/simplifyinequalities" to enable a simplification step for inequalities; default value is set to FALSE = disabled
"constraints/linear/upgrade/binpack" to enable or disable the linear upgrading process
"constraints/linear/upgrade/eqknapsack" to enable or disable the linear upgrading process
"constraints/linear/upgrade/invarknapsack" to enable or disable the linear upgrading process
"constraints/linear/upgrade/knapsack" to enable or disable the linear upgrading process
"constraints/linear/upgrade/logicor" to enable or disable the linear upgrading process
"constraints/linear/upgrade/setppc" to enable or disable the linear upgrading process
"constraints/linear/upgrade/varbound" to enable or disable the linear upgrading process
"constraints/linear/presolusehashing" to use hashing comparison in cons_linear.c; default value is TRUE
"constraints/logicor/presolusehashing" to use hashing comparison in cons_logicor.c; default value is TRUE
"constraints/setppc/presolusehashing" to use hashing comparison in cons_setppc.c; default value is TRUE
"constraints/SOS1/branchNonzeros" to decide whether SOS1 constraint with largest number of nonzero variables is picked for branching
"constraints/SOS1/branchSOS" to enable or disable branching on SOS1 constraints
"heuristics/feaspump/beforecuts" to allow the feaspump to be called before cut separation
"heuristics/mutation/minimprove"
"presol/donotmultaggr" which disables multiaggregation for all variables of the problem
"separating/cmir/densityoffset" to allow for more c-MIR cuts on small models
"separating/orthofunc" to choose function for scalar product computation in orthogonality test

Testing

updated mmm.{test,solu}, mittelmann.{test,solu}, miplib3.solu, miplib.solu, shortmiplib.test and added mittelmann_current.test, mittelmann_old.test
added test scripts for testing counting (make testcount)
removed tag make testpre (useless without corresponding scripts)
added tag testcount (make testcount); this allows for testing counting problem
replaced tcsh by bash and gawk by awk in all check scripts to achieve higher compatibility

Build system

Makefile

added in all make/make.* "GMP_FLAGS" and "GMP_LDFLAGS"
new flag GMP with values ("auto", "true and "false"); in case of "auto" the library gmp is linked if ZIMPL is included
modified makefiles to accept ZIMPLOPT and LPSOPT flags (with values "opt" or "dbg" and default being "opt"), and removed LPS=spxdbg and LPS=clpdbg
added "make/make.project" as default make include for external projects using SCIP
adapted all makefiles of the examples accordingly
added possibility to compile shared libraries in makefiles (and added make/make.linux.x86.gnu.opt-shared)
replaced <lt;string>gt; by <lt;cstring>gt; in all C++-interfaces to get 'strlen()' included (gcc-4.3 gave an error)
Moved -rpath option for ld to linux-specific Makefiles.
Re-activated readline library on darwin/ppc.
added target spx132 for SoPlex version 1.3.2

Fixed bugs

added handling of the case of roundable variables with 0 objective in presol_dualfix.c
fixed handling of unbounded variables with 0 objective in SCIPlpGetModifiedPseudo[Proved]Objval() (lp.c)
fixed CTRL-C if NO_SIGACTION is set (e.g., for MinGW)
fixed bug that a missing CONSTRANS in constraint handler leads to NULL pointer as constraint data for the copied constraints instead of pointer copies of the consdata (as explained in the constraint handler "HowTo")
fixed bug with reading empty lines in TSP example
fixed bug with writing the MIP relaxation to a file concerning the objective function; in case the original objective function is requested, the transformed objective function gets re-transformed (scaling, offset)
added checks whether a plugin (handler) has already been included to avoid later complications e.g. with parameters.
fixed obvious bug in linear constraint data sorting. Most part of the code assumed pure index sorting, but in fact, it was sorted by variable type as first criterion and index as second criterion.
fixed bug with wrong objective sense output for transformed problem. The transformed problem is always a minimization problem!
fixed numerical issue in linear constraint propagation: need slightly more aggressive tightening such that probing does not choose a wrong value for fixing inside an epsilon interval
fixed bug with objective scaling after restart
fixed bug with useless objective cutoff in LNS heuristics
fixed bug with wrong 'tightened' return value of some of the change bounds methods
fixed bug with non-conformal parameter name in reader_ppm
fixed bugs in sorttpl.c: fixed wrong arraysize in shellsort; in case an has at most one element, then no sorting is applied
fixed bug in cons_countsols.c concerning variable locking
fixed wrong if condition for function call in sorttpl.c
forced full propagation in presolving ->gt; this fixes a bug that implied that variable locks became inconsistent
avoid aggregation of implicit integers with fractional aggregation scalars
fixed infinite loop in LP file reader if a line exceeds the character limit
replaced calls to perror() by SCIP error message using strerror(errno); this avoids problems with the error output stream
fixed bug in method SCIPgetProbvarLinearSum()
fixed bug in aggregateActiveIntVars(): If a <lt; 0, multiply a*x + b*y == c by -1 (algo for finding initial solution does only work for a >gt; 0).
fixed bugs in second part of consdataTightenCoefs(): Removed min/maxleftactisinfinity (definition was not correct), fixed calculation of min/maxleftactivity and removed asserts concerning whether all redundant vars were deleted (led to different behavior in debug and opt mod).
corrected invalid memory access in tcliqueIsEdge: added check whether node1 has no neighbors (tclique_graph.c)
fixed numerical bug in dual presolving of linear constraint handler
fixed typo in documentation: default value for "dynamic" parameter is FALSE for all constraint handlers!
fixed bug with multi-aggregated variables in cons_logicor: instead of fixing them, a linear constraint will be created
fixed bug with uncatched LPSOLSTAT after hitting a time or iteration limit
fixed bug with wrong update of activities in linear constraints after global upper bound changes
avoid fixing variables to infinity in order to get rid of numerical inconsistencies in the original model
fixed bug in reader_ppm while appending strings for output file
fixed bug with errors occurring in sub-MIPs. Search is only aborted in dbg mode, in opt mode a warning will be printed
fixed bug in tclique-graph datastructure concerning insertion of edges into nonempty graph
corrected bug in SCIPtreeBranchVar() (tree.c) - several comparison functions needed a 'feas'.
corrected bug in SCIPlpGetState if the LP is empty
corrected bug in cons_linear.c:applyFixings() [if variable was fixed to infinity the rhs/lhs were wrong]
corrected bug in priceAndCutLoop(): separation was aborted if domain reduction was applied
fixed bug in SCIPlpSolveAndEval(): added extra simplex step if objlimit reached, fastmip and pricers enabled in order to get dual solution for pricing.
fixed bug in cons_varbounds.c, concerning SCIPaddVarVlb() and SCIPaddVarVub()
fixed bugs in pairwise presolving of cons_linear.c concerning deletion of upgraded constraints and inconsistent update of nchgsides in case of coefsequal and coefsnegated
avoiding aggregation that removes information about implicitly integer variables (removes bug)
fixed false assert and corrected a bug caused by deleting a constraint on "firstchanged" position in pairwise presolving with hashing in cons_linear.c
removed memory leak detected with the help of coverity in dialog.c
fixed bug in applyFixings() in cons_varbound.c concerning tightening the bound of a variable left in a redundant constraint (bound change is forced now)
fixed bug in SCIPtightenVarLb/Ub() in scip.c concering forcing a bound change (bound improvement is checked now)
fixed bug in preprocessConstraintPairs() in cons_linear.c concerning updating the flags of the constraint that stayes in the problem (nonredundant information were lost before)
fixed bug with exponential running times due to complicated recursive multi-aggregation
fixed bug with memory reallocation in SCIPgetProbvarLinearSum()
improved stage checking for bound computation
fixed usage of command test for string comparison in check-scripts (now compatible with ubuntu)
corrected imlementation of SCIPlpiGetBasisInd() in lpi_clp.cpp (this fixes the bug that almost no Gomory cuts are found with Clp).
weakened two too strong asserts in lp.c concerning the LP result OBJLIMIT
fixed bug in cons_linear.c caused by comparing two infinity values during checking of using variable as slackvariable
tried to fix memory leak in dialog.c occuring from different versions of the readline/history libraries
corrected bug in var.c occuring during applying boundchanges in varUpdateAggregationBounds method
replaced sprintf and snprintf by SCIPsnprintf fixed potential bug with overlong strings
fixed bug in SCIPlpSolveAndEval(): allow more than one extra simplex step for getting an objlimit exceeding solution with fastmip
fixed bug in sepa_mir.c: size of testeddeltas-array was too small
removed bug for values greater than (-)infinity, heur_shifting.c, heur_intshifting.c, heur_rounding.c, heur_oneopt.c
removed bug for rhs/lhs greater than (-)infinity, cons_linear.c
removed bug caused by hashcomparison for non-sorted constraints, cons_linear.c
fixed bugs with wrong presolving due to cancellation in (res-)activities in cons_linear.c
removed possible memory leak in objdialog.cpp
fixed bug in preprocessing of SOS2 constraints (cons_sos2.c)
removed BOUNDSCALETOL adjustment in cons_linear.c. This fixes bug with slightly infeasible variable fixings in presolving; reliable resactivities should make the BOUNDSCALETOL relaxation redundant.
corrected bug in the case when soplex threw an exception in autopricing
removed "epsilontic" bug in cons_linear.c due to adjusting left/right hand side in applyfixing
fixed bug in SCIPvarGetOrigvarSum() concerning the corner case the a negated variable has no parent variable in original problem
fixed some SCIP_RETCODE bugs in reader_fix.c, reader_sol.c, reader_sos.c and reader_zpl.c
fixed docu in type_reader.h
fixed bug with multi-aggregated variables which are de facto aggregated or fixed after flattening the aggregation tree
fixed bug with bound changes of variables in modifiable constraints during full dual presolving of linear conshdlr
increased compiler compatibility for C++ wrapper classed by adding extern "C" in obj*.cpp files and changing strlen calls to std::strlen
fixed bug with errors occurring in heuristic LPs. In opt mode a warning will be printed, abort in dbg mode