Release notes for SCIP 1.1

SCIP 1.1.0

Features

• SCIP can now count integer feasible solutions for IPs/CIPs (without continuous variables) (see SCIPcount())
• 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
• added capabilities to flatten the (multi)-aggregation graph of variables
• pseudoobj propagator now also propagates the global lower (dual) bound
• new heuristic DINS (distance induced neighborhood search by Ghosh)
• Output:
  • SCIP can now output a picture of the constraint matrix in PPM format.
  • output of real values is now done with 15 digits after the decimal point
  • 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.
• Presolving:
  • added predefined settings file presolving/aggressive.set
  • new presolver boundshift (presol_boundshift.{c,h}); this presolver is currently turned off with default parameter setting
• Constraints:
  • linear constraint handler now detects continuous variables that are implicit integer in dual presolve
  • 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
  • cons_countsols.c is now able to store the collected solution if required
  • 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 first version of constraint handler cons_countsols.{c,h}
• Reader:
  • added ccg-reader (weighted column connectivity graph)
  • added reader for pseudo-Boolean problems (reader_opb.{c,h})
  • the ZPL reader is now able to pass a starting solution to SCIP
  • 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)
• LPI:
  • The SoPlex LPI can now write basis files.
  • 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
• Cuts and Separation:
  • the c-MIR separator now also tries to get rid of implicit integer variables by aggregation
  • 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.
  • New cutting plane separator MCF (beta version).
  • new separator sepa_zerohalf.{c,h}; separates {0,1/2}-Cuts according to Caprara and Fischetti

Performance improvements

• heavily decreased the usage of SCIPisStopped(), which costs system time
• small performance improvement of c-MIR aggregation heuristic
• reworked strong branching in lpi_clp.cpp (scaling works now, bounds can be trusted)
• Constraints:
  • 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.
  • better branching in SOS1/SOS2 constraints
  • 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)
• Cuts and Separation:
  • improved the performance of SCIPcalcMIR() and SCIPcalcStrongCG() by exploiting sparsity
  • 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
• Presolving:
  • 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
  • tighter memory limits in knapsack presolve lifting procedure to avoid overly expensive presolving
  • 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 examples/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. Hence, also SCIPincludeReader() has changed.
• The callback CONSCHECK (SCIP_DECL_CONSCHECK()) in the constraint handlers now has a new parameter printreason that tells a constraint handler to output the reason for a possible infeasibility of the solution to be checked using SCIPinfoMessage(). Have a look at one of the constraint handlers implemented in SCIP to see how it works. This methodology makes it possible to output the reason of a violation in human readable form, for instance, for the check at the end of a SCIP run, where the obtained best solution is checked against the original formulation.
  This change often has little effect on C-implementations, since this parameter can be safely ignored with respect to the correctness of the code. The corresponding C++ method scip::ObjConshdlr::scip_check(), however, has to be extended and will not compile otherwise.
• 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, see pub_misc.h.

Deleted and changed API methods

• SCIPgetVarRedcost() now returns 0 for variables that have been aggregated out or removed in presolving. reduced cost in case of infeasible LPs)
• new parameter maxfrac for SCIPcalcStrongCG()
• new parameter maxmksetcoefs for SCIPcalcMIR() and SCIPcalcStrongCG() methods
• new parameter conshdlrname in SCIPincludeLinconsUpgrade()
• Problem:
  • new parameters extension in SCIPreadProb() defining a desired file format or NULL if file extension should be use
  • New parameters extension and genericnames in SCIPprintTransProblem(), SCIPprintOrigProblem(), SCIPwriteOrigProblem(), and SCIPwriteTransProblem() defining the requested format or NULL for default CIP format and using generic names for the variables and constraints. Examples are
    • SCIPprintTransProblem(scip, NULL, NULL, TRUE) displays the transformed problem in CIP format with generic variables and constraint names
    • SCIPprintOrigProblem(scip, NULL, lp, FALSE) displays the original problem in LP format with original variables and constraint names.
• Sorting:
  • expand sorttpl.c by some parameters
  • changed some names for sorting methods
  • 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!
• Checking:
  • SCIPcheckSolOrig() is restructured. The last two parameters have changed. They are now bools indicating whether the reason for the violation should be printed to the standard output and whether all violations should be printed. This reflects the changes in the constraint handlers above, which allow the automation of the feasibility test. The pointers to store the constraint handler or constraint are not needed anymore.
  • 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

New API functions

• 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())
• 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
• SCIPgetVectorEfficacyNorm()
• SCIPseparateRelaxedKnapsack() in cons_knapsack.h
• SCIPgetCutoffdepth() which returns the depth of first node in active path that is marked being cutoff
• SCIPflattenVarAggregationGraph()
• SCIPclockGetLastTime()
• SCIPcalcHashtableSize() to get a reasonable hash table size
• SCIPgetVarFarkasCoef() and SCIPgetColFarkasCoef() to get the farkas coefficient of a variable (analogon of
• SCIPgetRepropdepth() to get the depth of first node in active path that has to be propagated again
• SCIPmajorVersion(), SCIPminorVersion() and SCIPtechVersion() returning the corresponding version
• Read, Write and Print:
  • SCIPprintSysError() which encapsulates the strerror_r calls, the NO_STRERROR_R flag switches between the use of strerror_r and strerror inside
  • 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
  • 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
• Heuristics:
  • SCIPcutGenerationHeuristicCmir() in sepa_cmir.h
  • SCIPheurGetTimingmask() and SCIPheurSetTimingmask()
• Sorting:
  • added some downwards-sorting methods
  • SCIPbsortInd()
  • 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

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 <and> 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 make/make.project as default make include for external projects using SCIP
• added possibility to compile shared libraries in makefiles (and added make/make.linux.x86.gnu.opt-shared)
• replaced <string> by <cstring> 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.
• Flags:
  • added in all make/make.* GMP_FLAGS and GMP_LDFLAGS
  • new flag GMP with values (auto, true andfalse); in case ofauto` the library gmp is linked if ZIMPL is included
  • adapted all makefiles of the examples accordingly
• LP:
  • 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 target spx132 for SoPlex version 1.3.2

Fixed bugs

• fixed CTRL-C if NO_SIGACTION is set (e.g., for MinGW)
• added checks whether a plugin (handler) has already been included to avoid later complications e.g. with parameters.
• fixed bug with wrong tightened return value of some of the change bounds methods
• forced full propagation in presolving -> this fixes a bug that implied that variable locks became inconsistent
• 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 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.
• fixed bug in SCIPtightenVarLb/Ub() in scip.c concering forcing a bound change (bound improvement is checked now)
• improved stage checking for bound computation
• fixed usage of command test for string comparison in check-scripts (now compatible with ubuntu)
• replaced sprintf and snprintf by SCIPsnprintf() fixed potential bug with overlong strings
• corrected bug in the case when soplex threw an exception in autopricing
• fixed bug in SCIPvarGetOrigvarSum() concerning the corner case the a negated variable has no parent variable in original problem
• Aggregation:
  • avoid aggregation of implicit integers with fractional aggregation scalars
  • fixed bug in aggregateActiveIntVars(): If a < 0, multiply a*x + b*y == c by -1 (algo for finding initial solution does only work for a > 0).
  • avoiding aggregation that removes information about implicitly integer variables (removes bug)
  • fixed bug with exponential running times due to complicated recursive multi-aggregation
  • corrected bug in var.c occuring during applying boundchanges in varUpdateAggregationBounds method
• Constraints:
  • 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 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).
  • fixed typo in documentation: default value for dynamic parameter is FALSE for all constraint handlers!
  • fixed bug in preprocessing of SOS2 constraints (cons_sos2.c)
  • fixed bug in cons_countsols.c concerning variable locking
  • fixed bug in cons_varbounds.c, concerning SCIPaddVarVlb() and SCIPaddVarVub()
  • 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)
• Heuristics:
  • fixed bug with useless objective cutoff in LNS heuristics
  • removed bug for values greater than (-)infinity, heur_shifting.c, heur_intshifting.c, heur_rounding.c, heur_oneopt.c
  • fixed bug with errors occurring in heuristic LPs. In opt mode a warning will be printed, abort in dbg mode
• Linear Constraints:
  • fixed bug with wrong update of activities in linear constraints after global upper bound changes
  • 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 in cons_linear.c caused by comparing two infinity values during checking of using variable as slackvariable
  • 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 BOUNDSCALETOL adjustment in cons_linear.c. This fixes bug with slightly infeasible variable fixings in presolving; reliable resactivities should make the BOUNDSCALETOL relaxation redundant.
  • removed epsilontic bug in cons_linear.c due to adjusting left/right hand side in applyfixing
  • fixed bug with multi-aggregated variables in cons_logicor: instead of fixing them, a linear constraint will be created
  • corrected bug in cons_linear.c:applyFixings() [if variable was fixed to infinity the rhs/lhs were wrong]
  • 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
  • fixed false assert and corrected a bug caused by deleting a constraint on firstchanged position in pairwise presolving with hashing in cons_linear.c
• LP:
  • fixed handling of unbounded variables with 0 objective in SCIPlpGetModifiedPseudo[Proved]Objval() (lp.c)
  • fixed bug with uncatched LPSOLSTAT after hitting a time or iteration limit
  • corrected bug in SCIPlpGetState() if the LP is empty
  • fixed bug in SCIPlpSolveAndEval(): added extra simplex step if objlimit reached, fastmip and pricers enabled in order to get dual solution for pricing.
  • weakened two too strong asserts in lp.c concerning the LP result OBJLIMIT
  • fixed bug in SCIPlpSolveAndEval(): allow more than one extra simplex step for getting an objlimit exceeding solution with fastmip
• Memory:
  • corrected invalid memory access in tcliqueIsEdge: added check whether node1 has no neighbors (tclique_graph.c)
  • removed memory leak detected with the help of coverity in dialog.c
  • fixed bug with memory reallocation in SCIPgetProbvarLinearSum()
  • tried to fix memory leak in dialog.c occuring from different versions of the readline/history libraries
  • removed possible memory leak in objdialog.cpp
• Numerical:
  • 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 numerical bug in dual presolving of linear constraint handler
  • avoid fixing variables to infinity in order to get rid of numerical inconsistencies in the original model
• Objective:
  • added handling of the case of roundable variables with 0 objective in presol_dualfix.c
  • 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)
  • fixed bug with wrong objective sense output for transformed problem. The transformed problem is always a minimization problem!
  • fixed bug with objective scaling after restart
• Reading:
  • fixed bug with reading empty lines in TSP example
  • fixed bug with non-conformal parameter name in reader_ppm
  • fixed infinite loop in LP file reader if a line exceeds the character limit
  • fixed bug in reader_ppm while appending strings for output file
  • 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
• Separation:
  • corrected bug in priceAndCutLoop(): separation was aborted if domain reduction was applied
  • fixed bug in sepa_mir.c: size of testeddeltas-array was too small
  • corrected imlementation of SCIPlpiGetBasisInd() in lpi_clp.cpp (this fixes the bug that almost no Gomory cuts are found with Clp).
• Sorting:
  • fixed bugs in sorttpl.c: fixed wrong arraysize in shellsort; in case an has at most one element, then no sorting is applied
  • fixed wrong if condition for function call in sorttpl.c
  • 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.