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.
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}
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)
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
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)
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())
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
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 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
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
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
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 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 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.