| 24 | |
| 25 | April 10, 2013 |
| 26 | |
| 27 | * Cbc [https://projects.coin-or.org/Cbc/browser/releases/2.8.0 2.8.0] has been released. |
| 28 | * Introduced **new secondaryStatus** 8 to indicate that solving stopped due to an iteration limit. |
| 29 | * **Solution pool** is now accessible via the command line and the !CbcMain* interface. |
| 30 | * New **mipstart option** to read an initial feasible solution from a file. |
| 31 | Only values for discrete variables need to be provided. |
| 32 | * Added **Proximity Search heuristic** by Fischetti and Monaci (off by default):[[BR]] |
| 33 | The simplest way to switch it on using stand-alone version is "-proximity on".[[BR]] |
| 34 | Proximity Search is the new "No-Neighborhood Search" 0-1 MIP refinement heuristic recently proposed by |
| 35 | Fischetti and Monaci (2012). The idea is to define a sub-MIP without additional constraints but with a |
| 36 | modified objective function intended to attract the search in the proximity of the incumbent. The approach |
| 37 | works well for 0-1 MIPs whose solution landscape is not too irregular (meaning the there is reasonable |
| 38 | probability of finding an improved solution by flipping a small number of binary variables), in particular |
| 39 | when it is applied to the first heuristic solutions found at the root node. |
| 40 | * An implementation of **Zero-Half-Cuts** by Alberto Caprara is now available.[[BR]] |
| 41 | By default, these cuts are off. To use add to your command line -zerohalfCuts root (or other options) or just -zero. |
| 42 | So far, they may help only on a small subset of problems and may need some tuning.[[BR]] |
| 43 | The implementation of these cuts is described in[[BR]] |
| 44 | G.{{{}}} Andreello, A. Caprara, and M. Fischetti[[BR]] |
| 45 | "Embedding Cuts in a Branch and Cut Framework: a Computational Study with {0,1/2}-Cuts"[[BR]] |
| 46 | INFORMS Journal on Computing 19(2), 229-238, 2007[[BR]] |
| 47 | http://dx.doi.org/10.1287/ijoc.1050.0162 |
| 48 | * An alternative implementation of a **reduce and split cut generator** by Giacomo Nannicini is now available. |
| 49 | By default, these cuts are off. To use add to your command line -reduce2AndSplitCuts root (or other options).[[BR]] |
| 50 | The implementation of these cuts is described in |
| 51 | G.{{{}}} Cornuejols and G. Nannicini[[BR]] |
| 52 | "Practical strategies for generating rank-1 split cuts in mixed-integer linear programming"[[BR]] |
| 53 | Mathematical Programming Computation 3(4), 281-318, 2011[[BR]] |
| 54 | http://dx.doi.org/10.1007/s12532-011-0028-6 |
| 55 | * An alternative robust implementation of a **Gomory cut generator** by Giacomo Nannicini is now available.[[BR]] |
| 56 | By default, these cuts are off. To use add to your command line -GMI root (or other options).[[BR]] |
| 57 | The implementation of these cuts is described in[[BR]] |
| 58 | G.{{{}}} Cornuejols, F. Margot, and G. Nannicini[[BR]] |
| 59 | "On the safety of Gomory cut generators"[[BR]] |
| 60 | http://faculty.sutd.edu.sg/~nannicini/index.php?page=publications |
| 61 | * To encourage the use of some of the more exotic/expensive cut generators a **parameter -slowcutpasses** has been added.[[BR]] |
| 62 | The idea is that the code does these cuts just a few times - less than the more usual cuts. The default is 10. |
| 63 | The cut generators identified by "may be slow" at present are just Lift and project and !ReduceAndSplit (both versions). |
| 64 | * Allow **initialization of random seed** by user. Pseudo-random numbers are used in Cbc and Clp. In Clp they |
| 65 | are used to break ties in degenerate problems, while in Cbc heuristics such as the Feasibility Pump use them |
| 66 | to decide whether to round up or down. So if a different pseudo-random seed is given to Clp then you may get |
| 67 | a different continuous optimum and so different cuts and heuristic solutions. This can be switched on by |
| 68 | setting randomSeed for Clp and/or randomCbcSeed for Cbc. The special value of 0 tells code to use time of day |
| 69 | for initial seed. |
| 70 | * Building on this idea, Andrea Lodi, Matteo Fischetti, Michele Monaci, Domenico Salvagnin, Yuji Shinano, and Andrea Tramontani |
| 71 | suggest that this idea be improved by **running at the root node with multiple copies** of solver, each |
| 72 | with its own different seed and then passing in the solutions and cuts so that the main solver has a richer |
| 73 | set of solutions and possibly stronger cuts. This is switched on by setting -multipleRootPasses. These can also |
| 74 | be done in parallel. |
| 75 | * Few **changes to presolve** for special variables and badly scaled problems (in !CoinUtils). |
| 76 | * New option -extraVariables <number> which switches on a trivial re-formulation that introduces extra integer variables |
| 77 | to **group together variables with same cost**. |
| 78 | * For some problems, cut generators and general branching work better if the problem would be infeasible if the cost is too high. |
| 79 | If the new option -constraintFromCutoff is set, the **objective function is added as a constraint** which rhs is set to the current |
| 80 | cutoff value (objective value of best known solution). |
| 81 | * Click [https://projects.coin-or.org/Cbc/changeset?old_path=%2Freleases%2F2.7.8&new_path=%2Freleases%2F2.8.0 here] to see changes from release [https://projects.coin-or.org/Cbc/browser/releases/2.7.8 2.7.8] |